Reverse style resolution to avoid N^2 walk when building the render tree

Source/core/rendering/RenderRegion.cpp

 /*
  * Copyright (C) 2011 Adobe Systems Incorporated. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  *
  * 1. Redistributions of source code must retain the above
  *    copyright notice, this list of conditions and the following
  *    disclaimer.
@@ skipping 532 matching lines @@
 
     // FIXME: Region styling fails for pseudo-elements because the renderers don't have a node.
     Element* element = toElement(object->node());
     RefPtr<RenderStyle> renderObjectRegionStyle = object->view()->document().styleResolver()->styleForElement(element, 0, DisallowStyleSharing, MatchAllRules, this);
 
     return renderObjectRegionStyle.release();
 }
 
 void RenderRegion::computeChildrenStyleInRegion(const RenderObject* object)
 {
-    for (RenderObject* child = object->firstChild(); child; child = child->nextSibling()) {
+    for (RenderObject* child = object->lastChild(); child; child = child->previousSibling()) {
 
         RenderObjectRegionStyleMap::iterator it = m_renderObjectRegionStyle.find(child);
 
         RefPtr<RenderStyle> childStyleInRegion;
         bool objectRegionStyleCached = false;
         if (it != m_renderObjectRegionStyle.end()) {
             childStyleInRegion = it->value.style;
             objectRegionStyleCached = true;
         } else {
             if (child->isAnonymous() || child->isInFlowRenderFlowThread())
@@ skipping 31 matching lines @@
     styleInfo.cached = objectRegionStyleCached;
     m_renderObjectRegionStyle.set(object, styleInfo);
 }
 
 void RenderRegion::clearObjectStyleInRegion(const RenderObject* object)
 {
     ASSERT(object);
     m_renderObjectRegionStyle.remove(object);
 
     // Clear the style for the children of this object.
-    for (RenderObject* child = object->firstChild(); child; child = child->nextSibling())
+    for (RenderObject* child = object->lastChild(); child; child = child->previousSibling())
         clearObjectStyleInRegion(child);
 }
 
 void RenderRegion::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
 {
     if (!isValid()) {
         RenderBlock::computeIntrinsicLogicalWidths(minLogicalWidth, maxLogicalWidth);
         return;
     }
 
@@ skipping 29 matching lines @@
 
     LayoutUnit autoHeight = hasOverrideHeight() ? overrideLogicalContentHeight() : computedAutoHeight();
 
     LayoutUnit newLogicalHeight = autoHeight + borderAndPaddingLogicalHeight();
     ASSERT(newLogicalHeight < LayoutUnit::max() / 2);
     if (newLogicalHeight > logicalHeight())
         setLogicalHeight(newLogicalHeight);
 }
 
 } // namespace WebCore