Title: [94108] trunk
- Revision
- 94108
- Author
- [email protected]
- Date
- 2011-08-30 13:53:45 -0700 (Tue, 30 Aug 2011)
Log Message
refactor box-ordinal-group handling so we don't timeout on large values
https://bugs.webkit.org/show_bug.cgi?id=65783
Reviewed by David Hyatt.
Source/WebCore:
The old code walked from 1 to the last box-ordinal-group while
iterating over each flex item. The new code collects ordinals as
we do the first walk and sorts them. Each additional iteration
through the flex items gets the next oridnal from the sorted list.
This maintains the single pass for the common case of no
box-ordinal-groups specified. If there are ordinal groups,
the runtime is O(n*m + m lg m) where n is the # of flex items and
m is the number of unique box-ordinal-group values. The memory
usage is O(2m).
Test: fast/flexbox/box-ordinal-group.html
* rendering/RenderDeprecatedFlexibleBox.cpp:
(WebCore::FlexBoxIterator::FlexBoxIterator):
(WebCore::FlexBoxIterator::reset):
(WebCore::FlexBoxIterator::next):
(WebCore::FlexBoxIterator::compareFlexOrder):
LayoutTests:
* fast/flexbox/box-ordinal-group-expected.txt: Added.
* fast/flexbox/box-ordinal-group.html: Added.
Modified Paths
Added Paths
Diff
Modified: trunk/LayoutTests/ChangeLog (94107 => 94108)
--- trunk/LayoutTests/ChangeLog 2011-08-30 20:45:11 UTC (rev 94107)
+++ trunk/LayoutTests/ChangeLog 2011-08-30 20:53:45 UTC (rev 94108)
@@ -1,3 +1,13 @@
+2011-08-30 Tony Chang <[email protected]>
+
+ refactor box-ordinal-group handling so we don't timeout on large values
+ https://bugs.webkit.org/show_bug.cgi?id=65783
+
+ Reviewed by David Hyatt.
+
+ * fast/flexbox/box-ordinal-group-expected.txt: Added.
+ * fast/flexbox/box-ordinal-group.html: Added.
+
2011-08-30 Caio Marcelo de Oliveira Filho <[email protected]>
Emit last progress notification before calling dispatchDidFinishLoad
Added: trunk/LayoutTests/fast/flexbox/box-ordinal-group-expected.txt (0 => 94108)
--- trunk/LayoutTests/fast/flexbox/box-ordinal-group-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/flexbox/box-ordinal-group-expected.txt 2011-08-30 20:53:45 UTC (rev 94108)
@@ -0,0 +1,12 @@
+This tests to make sure that large box-ordinal-group values don't hang the renderer. This test passes if it does not timeout.
+
+1
+2
+3
+4
+5
+3
+4
+1
+2
+5
Property changes on: trunk/LayoutTests/fast/flexbox/box-ordinal-group-expected.txt
___________________________________________________________________
Added: svn:eol-style
Added: trunk/LayoutTests/fast/flexbox/box-ordinal-group.html (0 => 94108)
--- trunk/LayoutTests/fast/flexbox/box-ordinal-group.html (rev 0)
+++ trunk/LayoutTests/fast/flexbox/box-ordinal-group.html 2011-08-30 20:53:45 UTC (rev 94108)
@@ -0,0 +1,72 @@
+<html>
+<head>
+<style>
+div.box {
+ display: -moz-box;
+ display: -webkit-box;
+ display: box;
+}
+
+div.number {
+ border: 2px solid black;
+ padding: 4px;
+ margin: 4px;
+}
+
+.first {
+ -moz-box-ordinal-group: 1;
+ -webkit-box-ordinal-group: 1;
+ box-ordinal-group: 1;
+}
+
+.second {
+ -moz-box-ordinal-group: 1000000000;
+ -webkit-box-ordinal-group: 1000000000;
+ box-ordinal-group: 1000000000;
+}
+
+.third {
+ -moz-box-ordinal-group: 2000000000;
+ -webkit-box-ordinal-group: 2000000000;
+ box-ordinal-group: 2000000000;
+}
+
+.fourth {
+ -moz-box-ordinal-group: 3000000000;
+ -webkit-box-ordinal-group: 3000000000;
+ box-ordinal-group: 3000000000;
+}
+
+.fifth {
+ -moz-box-ordinal-group: 4000000000;
+ -webkit-box-ordinal-group: 4000000000;
+ box-ordinal-group: 4000000000;
+}
+
+</style>
+<script>
+if (window.layoutTestController)
+ layoutTestController.dumpAsText();
+</script>
+<body>
+<p>
+This tests to make sure that large box-ordinal-group values don't hang the renderer.
+This test passes if it does not timeout.
+</p>
+<div class="box">
+ <div class="number first">1</div>
+ <div class="number second">2</div>
+ <div class="number third">3</div>
+ <div class="number fourth">4</div>
+ <div class="number fifth">5</div>
+</div>
+
+<div class="box" style="-webkit-box-direction: reverse">
+ <div class="number third">3</div>
+ <div class="number second">4</div>
+ <div class="number fifth">1</div>
+ <div class="number fourth">2</div>
+ <div class="number first">5</div>
+</div>
+</body>
+</html>
Property changes on: trunk/LayoutTests/fast/flexbox/box-ordinal-group.html
___________________________________________________________________
Added: svn:eol-style
Modified: trunk/Source/WebCore/ChangeLog (94107 => 94108)
--- trunk/Source/WebCore/ChangeLog 2011-08-30 20:45:11 UTC (rev 94107)
+++ trunk/Source/WebCore/ChangeLog 2011-08-30 20:53:45 UTC (rev 94108)
@@ -1,3 +1,29 @@
+2011-08-30 Tony Chang <[email protected]>
+
+ refactor box-ordinal-group handling so we don't timeout on large values
+ https://bugs.webkit.org/show_bug.cgi?id=65783
+
+ Reviewed by David Hyatt.
+
+ The old code walked from 1 to the last box-ordinal-group while
+ iterating over each flex item. The new code collects ordinals as
+ we do the first walk and sorts them. Each additional iteration
+ through the flex items gets the next oridnal from the sorted list.
+
+ This maintains the single pass for the common case of no
+ box-ordinal-groups specified. If there are ordinal groups,
+ the runtime is O(n*m + m lg m) where n is the # of flex items and
+ m is the number of unique box-ordinal-group values. The memory
+ usage is O(2m).
+
+ Test: fast/flexbox/box-ordinal-group.html
+
+ * rendering/RenderDeprecatedFlexibleBox.cpp:
+ (WebCore::FlexBoxIterator::FlexBoxIterator):
+ (WebCore::FlexBoxIterator::reset):
+ (WebCore::FlexBoxIterator::next):
+ (WebCore::FlexBoxIterator::compareFlexOrder):
+
2011-08-30 Abhishek Arya <[email protected]>
Removed m_owner accessed in custom scrollbars.
Modified: trunk/Source/WebCore/rendering/RenderDeprecatedFlexibleBox.cpp (94107 => 94108)
--- trunk/Source/WebCore/rendering/RenderDeprecatedFlexibleBox.cpp 2011-08-30 20:45:11 UTC (rev 94107)
+++ trunk/Source/WebCore/rendering/RenderDeprecatedFlexibleBox.cpp 2011-08-30 20:53:45 UTC (rev 94108)
@@ -38,7 +38,7 @@
public:
FlexBoxIterator(RenderDeprecatedFlexibleBox* parent)
: m_box(parent)
- , m_lastOrdinal(1)
+ , m_largestOrdinal(1)
{
if (m_box->style()->boxOrient() == HORIZONTAL && !m_box->style()->isLeftToRightDirection())
m_forward = m_box->style()->boxDirection() != BNORMAL;
@@ -48,8 +48,8 @@
// No choice, since we're going backwards, we have to find out the highest ordinal up front.
RenderBox* child = m_box->firstChildBox();
while (child) {
- if (child->style()->boxOrdinalGroup() > m_lastOrdinal)
- m_lastOrdinal = child->style()->boxOrdinalGroup();
+ if (child->style()->boxOrdinalGroup() > m_largestOrdinal)
+ m_largestOrdinal = child->style()->boxOrdinalGroup();
child = child->nextSiblingBox();
}
}
@@ -60,7 +60,7 @@
void reset()
{
m_currentChild = 0;
- m_currentOrdinal = m_forward ? 0 : m_lastOrdinal + 1;
+ m_ordinalIteration = -1;
}
RenderBox* first()
@@ -73,33 +73,48 @@
{
do {
if (!m_currentChild) {
- if (m_forward) {
- ++m_currentOrdinal;
- if (m_currentOrdinal > m_lastOrdinal)
+ ++m_ordinalIteration;
+
+ if (!m_ordinalIteration)
+ m_currentOrdinal = m_forward ? 1 : m_largestOrdinal;
+ else {
+ if (m_ordinalIteration >= m_ordinalValues.size() + 1)
return 0;
- m_currentChild = m_box->firstChildBox();
- } else {
- --m_currentOrdinal;
- if (!m_currentOrdinal)
- return 0;
- m_currentChild = m_box->lastChildBox();
+
+ // Only copy+sort the values once per layout even if the iterator is reset.
+ if (static_cast<size_t>(m_ordinalValues.size()) != m_sortedOrdinalValues.size()) {
+ copyToVector(m_ordinalValues, m_sortedOrdinalValues);
+ sort(m_sortedOrdinalValues.begin(), m_sortedOrdinalValues.end());
+ }
+ m_currentOrdinal = m_forward ? m_sortedOrdinalValues[m_ordinalIteration - 1] : m_sortedOrdinalValues[m_sortedOrdinalValues.size() - m_ordinalIteration];
}
- }
- else
+
+ m_currentChild = m_forward ? m_box->firstChildBox() : m_box->lastChildBox();
+ } else
m_currentChild = m_forward ? m_currentChild->nextSiblingBox() : m_currentChild->previousSiblingBox();
- if (m_currentChild && m_currentChild->style()->boxOrdinalGroup() > m_lastOrdinal)
- m_lastOrdinal = m_currentChild->style()->boxOrdinalGroup();
+
+ if (m_currentChild && notFirstOrdinalValue())
+ m_ordinalValues.add(m_currentChild->style()->boxOrdinalGroup());
} while (!m_currentChild || (!m_currentChild->isAnonymous()
&& (m_currentChild->style()->boxOrdinalGroup() != m_currentOrdinal || m_currentChild->style()->visibility() == COLLAPSE)));
return m_currentChild;
}
private:
+ bool notFirstOrdinalValue()
+ {
+ unsigned int firstOrdinalValue = m_forward ? 1 : m_largestOrdinal;
+ return m_currentOrdinal == firstOrdinalValue && m_currentChild->style()->boxOrdinalGroup() != firstOrdinalValue;
+ }
+
RenderDeprecatedFlexibleBox* m_box;
RenderBox* m_currentChild;
bool m_forward;
unsigned int m_currentOrdinal;
- unsigned int m_lastOrdinal;
+ unsigned int m_largestOrdinal;
+ HashSet<unsigned int> m_ordinalValues;
+ Vector<unsigned int> m_sortedOrdinalValues;
+ int m_ordinalIteration;
};
RenderDeprecatedFlexibleBox::RenderDeprecatedFlexibleBox(Node* node)
_______________________________________________
webkit-changes mailing list
[email protected]
http://lists.webkit.org/mailman/listinfo.cgi/webkit-changes
