REGRESSION (r254483): media/track/track-cues-sorted-before-dispatch.html became very flaky
https://bugs.webkit.org/show_bug.cgi?id=206225
<rdar://problem/58634315>
Reviewed by Jer Noble.
The list of text track cues that are to fire events are sorted before events are
fired. Cue were being sorted by track, then by start time, and then by end time.
This meant that the sort order of two cues in the same track with identical start
and end times was not stable, causing this test to be flaky. The spec says to sort
by a cue's position in the track cue list when start and end times are identical,
so do that.
No new tests, this fixes a flaky test.
* html/track/TextTrackCue.cpp:
(WebCore::TextTrackCue::cueIndex const):
(WebCore::TextTrackCue::isOrderedBefore const):
* html/track/TextTrackCue.h:
* html/track/TextTrackCueList.cpp:
(WebCore::cueSortsBefore):
(WebCore::TextTrackCueList::cueIndex const):
(WebCore::TextTrackCueList::add):
(WebCore::TextTrackCueList::updateCueIndex):
(WebCore::compareCues): Deleted.
* html/track/TextTrackCueList.h:
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@254767 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/WebCore/ChangeLog b/Source/WebCore/ChangeLog
index 31dcf99..78d9053 100644
--- a/Source/WebCore/ChangeLog
+++ b/Source/WebCore/ChangeLog
@@ -1,3 +1,32 @@
+2020-01-17 Eric Carlson <eric.carlson@apple.com>
+
+ REGRESSION (r254483): media/track/track-cues-sorted-before-dispatch.html became very flaky
+ https://bugs.webkit.org/show_bug.cgi?id=206225
+ <rdar://problem/58634315>
+
+ Reviewed by Jer Noble.
+
+ The list of text track cues that are to fire events are sorted before events are
+ fired. Cue were being sorted by track, then by start time, and then by end time.
+ This meant that the sort order of two cues in the same track with identical start
+ and end times was not stable, causing this test to be flaky. The spec says to sort
+ by a cue's position in the track cue list when start and end times are identical,
+ so do that.
+
+ No new tests, this fixes a flaky test.
+
+ * html/track/TextTrackCue.cpp:
+ (WebCore::TextTrackCue::cueIndex const):
+ (WebCore::TextTrackCue::isOrderedBefore const):
+ * html/track/TextTrackCue.h:
+ * html/track/TextTrackCueList.cpp:
+ (WebCore::cueSortsBefore):
+ (WebCore::TextTrackCueList::cueIndex const):
+ (WebCore::TextTrackCueList::add):
+ (WebCore::TextTrackCueList::updateCueIndex):
+ (WebCore::compareCues): Deleted.
+ * html/track/TextTrackCueList.h:
+
2020-01-17 Andres Gonzalez <andresg_22@apple.com>
Rename AXIsolatedTreeNode.cpp/h to match AXIsolatedObject class name.
diff --git a/Source/WebCore/html/track/TextTrackCue.cpp b/Source/WebCore/html/track/TextTrackCue.cpp
index c6ffc3f..e5df3c3 100644
--- a/Source/WebCore/html/track/TextTrackCue.cpp
+++ b/Source/WebCore/html/track/TextTrackCue.cpp
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2011, 2013 Google Inc. All rights reserved.
- * Copyright (C) 2011-2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2020 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
@@ -50,6 +50,7 @@
#include "TextTrackCueList.h"
#include "VTTCue.h"
#include "VTTRegionList.h"
+#include <limits.h>
#include <wtf/HexNumber.h>
#include <wtf/IsoMallocInlines.h>
#include <wtf/MathExtras.h>
@@ -338,9 +339,29 @@
m_displayTree->remove();
}
+unsigned TextTrackCue::cueIndex() const
+{
+ ASSERT(m_track && m_track->cues());
+ if (!m_track || !m_track->cues())
+ return std::numeric_limits<unsigned>::max();
+
+ return m_track->cues()->cueIndex(*this);
+}
+
bool TextTrackCue::isOrderedBefore(const TextTrackCue* other) const
{
- return startMediaTime() < other->startMediaTime() || (startMediaTime() == other->startMediaTime() && endMediaTime() > other->endMediaTime());
+ // ... cues must be sorted by their start time, earliest first;
+ if (startMediaTime() != other->startMediaTime())
+ return startMediaTime() < other->startMediaTime();
+
+ // then, any cues with the same start time must be sorted by their end time, latest first;
+ if (endMediaTime() != other->endMediaTime())
+ return endMediaTime() > other->endMediaTime();
+
+ // and finally, any cues with identical end times must be sorted in the order they were last added to
+ // their respective text track list of cues, oldest first (so e.g. for cues from a WebVTT file, that
+ // would initially be the order in which the cues were listed in the file)
+ return cueIndex() < other->cueIndex();
}
bool TextTrackCue::cueContentsMatch(const TextTrackCue& cue) const
diff --git a/Source/WebCore/html/track/TextTrackCue.h b/Source/WebCore/html/track/TextTrackCue.h
index c7bd75e..6f3eeab 100644
--- a/Source/WebCore/html/track/TextTrackCue.h
+++ b/Source/WebCore/html/track/TextTrackCue.h
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2011 Google Inc. All rights reserved.
- * Copyright (C) 2012-2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2012-2020 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
@@ -127,6 +127,8 @@
virtual void setFontSize(int, const IntSize&, bool important);
virtual void updateDisplayTree(const MediaTime&) { };
+ unsigned cueIndex() const;
+
protected:
TextTrackCue(ScriptExecutionContext&, const MediaTime& start, const MediaTime& end, DocumentFragment&&);
TextTrackCue(ScriptExecutionContext&, const MediaTime& start, const MediaTime& end);
diff --git a/Source/WebCore/html/track/TextTrackCueList.cpp b/Source/WebCore/html/track/TextTrackCueList.cpp
index a0f8823..8a0fd0b 100644
--- a/Source/WebCore/html/track/TextTrackCueList.cpp
+++ b/Source/WebCore/html/track/TextTrackCueList.cpp
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2011 Google Inc. All rights reserved.
- * Copyright (C) 2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2017-2020 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -34,19 +34,22 @@
#undef CHECK_SORTING
#ifdef CHECK_SORTING
-#define ASSERT_SORTED(begin, end) ASSERT(std::is_sorted(begin, end, compareCues))
+#define ASSERT_SORTED(begin, end) ASSERT(std::is_sorted(begin, end, cueSortsBefore))
#else
#define ASSERT_SORTED(begin, end) ((void)0)
#endif
namespace WebCore {
-static inline bool compareCues(const RefPtr<TextTrackCue>& a, const RefPtr<TextTrackCue>& b)
+static inline bool cueSortsBefore(const RefPtr<TextTrackCue>& a, const RefPtr<TextTrackCue>& b)
{
- return a->isOrderedBefore(b.get());
+ if (a->startMediaTime() < b->startMediaTime())
+ return true;
+
+ return a->startMediaTime() == b->startMediaTime() && a->endMediaTime() > b->endMediaTime();
}
-unsigned TextTrackCueList::cueIndex(TextTrackCue& cue) const
+unsigned TextTrackCueList::cueIndex(const TextTrackCue& cue) const
{
ASSERT(m_vector.contains(&cue));
return m_vector.find(&cue);
@@ -93,7 +96,7 @@
ASSERT(cue->endMediaTime() >= MediaTime::zeroTime());
RefPtr<TextTrackCue> cueRefPtr { WTFMove(cue) };
- unsigned insertionPosition = std::upper_bound(m_vector.begin(), m_vector.end(), cueRefPtr, compareCues) - m_vector.begin();
+ unsigned insertionPosition = std::upper_bound(m_vector.begin(), m_vector.end(), cueRefPtr, cueSortsBefore) - m_vector.begin();
ASSERT_SORTED(m_vector.begin(), m_vector.end());
m_vector.insert(insertionPosition, WTFMove(cueRefPtr));
ASSERT_SORTED(m_vector.begin(), m_vector.end());
@@ -113,7 +116,7 @@
m_activeCues->m_vector.clear();
}
-void TextTrackCueList::updateCueIndex(TextTrackCue& cue)
+void TextTrackCueList::updateCueIndex(const TextTrackCue& cue)
{
auto cuePosition = m_vector.begin() + cueIndex(cue);
auto afterCuePosition = cuePosition + 1;
@@ -121,11 +124,11 @@
ASSERT_SORTED(m_vector.begin(), cuePosition);
ASSERT_SORTED(afterCuePosition, m_vector.end());
- auto reinsertionPosition = std::upper_bound(m_vector.begin(), cuePosition, *cuePosition, compareCues);
+ auto reinsertionPosition = std::upper_bound(m_vector.begin(), cuePosition, *cuePosition, cueSortsBefore);
if (reinsertionPosition != cuePosition)
std::rotate(reinsertionPosition, cuePosition, afterCuePosition);
else {
- reinsertionPosition = std::upper_bound(afterCuePosition, m_vector.end(), *cuePosition, compareCues);
+ reinsertionPosition = std::upper_bound(afterCuePosition, m_vector.end(), *cuePosition, cueSortsBefore);
if (reinsertionPosition != afterCuePosition)
std::rotate(cuePosition, afterCuePosition, reinsertionPosition);
}
diff --git a/Source/WebCore/html/track/TextTrackCueList.h b/Source/WebCore/html/track/TextTrackCueList.h
index f2ad157..c4f786b 100644
--- a/Source/WebCore/html/track/TextTrackCueList.h
+++ b/Source/WebCore/html/track/TextTrackCueList.h
@@ -1,6 +1,6 @@
/*
* Copyright (C) 2011 Google Inc. All rights reserved.
- * Copyright (C) 2017 Apple Inc. All rights reserved.
+ * Copyright (C) 2017-2020 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -40,11 +40,11 @@
TextTrackCue* item(unsigned index) const;
TextTrackCue* getCueById(const String&) const;
- unsigned cueIndex(TextTrackCue&) const;
+ unsigned cueIndex(const TextTrackCue&) const;
void add(Ref<TextTrackCue>&&);
void remove(TextTrackCue&);
- void updateCueIndex(TextTrackCue&);
+ void updateCueIndex(const TextTrackCue&);
void clear();
