482889 - [FIX]Switch table anonymous frame construction to a simpler algorithm

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Boris Zbarsky [:bzbarsky]]

Patches coming up.  I wrote this as an mq with three patches: one for tests, one for some refactoring of the callers of the existing CreateRequiredPseudoFrames to do all that from AdjustParentFrame, and one for switching to the new setup.  I'm not sure whether it's easier to review the refactoring and then separately the switch, or just the combined diff, since the refactoring has to preserve some niggly code very carefully and then the switch gets rid of all of it.  So I'll attach the patches individually, as well as attaching the combined diff; reviewers can do whatever they find convenient.

To summarize the change, the idea is to get rid of all the GetPseudoParent/ProcessPseudoFrames stuff we do now.  Instead, we take the FrameConstructionItemList of kids our frame has, and preprocess it before constructing frames from it.  The preprocessing takes all runs of kids that want a different kind of parent frame and wraps them in whatever the frame "one down" from the parent is by creating a FrameConstructionItem for that frame and replacing the run with that item in the list.  The run becomes kids of the item.  There's some complexity to do with whitespace handling and the fact that if the parent is a table, then column and row kids need to get wrapped separately from each other, but that's the basic idea.  Then during frame construction from items, we use the already-existing childlist in the item instead of calling ProcessChildren().

Compared to the current code this is much simpler, but may be a bit slower.  In particular, in a worst-case scenario (e.g. lots of cells in a block parent or lots of rows in a row parent) we might need to walk the item list three times.  For example, if a bunch of rows are kids of a row, the first walk will wrap them in a cell, the next walk in a table, and the third walk in a rowgroup.  To mitigate this, there are some fast-paths through this code:

1)  If all the kids have the right parent type already (tracked in the
    FrameConstructionItem), we don't do the walk at all.  This is the case
    normal HTML tables will hit.
2)  If all the kids can be grouped together, we do a fast-pathed swap of the
    list to the new FrameConstructionItem.  I added this pretty late, and I'm
    not completely sure it's needed, but it was easy to do.

There's also a comment describing some other possible optimizations, but they'd involve behavior changes.  I happen to think those would be changes for the better, but I was aiming to preserve existing behavior in as much detail as possible in this patch.  The one exception to that is whitespace behavior, which was so weird as to not be worth preserving, I think.  For example:

  <div style="display: inline;">
    <span>a</span>
    <span style="display: table-cell">b</span>
    <span style="display: table-cell">c</span>
    <span>d</span>
  </div>

used to render as "a bcd", because all the whitespace got moved to before the anonymous table in the frametree.  With my patch it renders as "a bc d", which I think is a lot saner.

Going forward, I do think we'll want to make the optimization described in that comment, and change the whitespace behavior a bit more.  The current one is really pretty suboptimal.

If we really want, I could probably implement something closer to the current setup on top of FrameConstructionItemList, with a single pass down the list, opening and closing containers of various sorts as I go, but the complexity would be a lot higher, I think.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 1: the tests

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 2. Refactor calls to CreateRequiredPseudoFrames to all happen in AdjustParentFrame

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 3. The main change.

I just realized I did slip in one non-table-related change here: in ProcessChildren, the check for needing to wrap kids of a box in a block now uses an integer equality check on the item list instead of groveling through the frame list.  The assertions that claim this is equivalent don't fire on any of our tests, or on our browser UI, so I think I'm good there.

Comment 4

[Boris Zbarsky [:bzbarsky]]

Attachment: Combined diff; might be easier to review

Comment 5

[Boris Zbarsky [:bzbarsky]]

I tried doing a diff -w too, but it's much harder to sort out; I can provide those if people really want, though.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Oh, I tried pushing this to try server; doesn't seem to slow down any of our talos tests (and might be speeding up Ts a bit?).

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+#define PARENT_TYPE_SIZE 3
+#define PARENT_TYPE_OFFSET                                       \
+  (PR_BITS_PER_BYTE*sizeof(((FrameConstructionData*)0)->mBits) - \
+   PARENT_TYPE_SIZE)
+  /* Macro to get the desired parent type out of an mBits member of
+     FrameConstructionData */
+#define FCDATA_DESIRED_PARENT_TYPE(_bits)       \
+  ParentType((_bits) >> PARENT_TYPE_OFFSET)
+  /* Macro to create FrameConstructionData bits out of a desired parent type */
+#define FCDATA_DESIRED_PARENT_TYPE_TO_BITS(_type) \
+  (((PRUint32)(_type)) << PARENT_TYPE_OFFSET)

Why do we need this hackery? Is there a problem with hardcoding a mask and bit-offset? An assertion somewhere would catch any bugs.

+    // XXXbz should this just be a method on Iterator, with Iterator holding a
+    // ref to its list?

Yeah I think so, especially since the iterator is modified.

+    // Drop the item pointed to by aIter and point aIter to the next item
+    void DropItem(Iterator& aIter);

RemoveItem?

+   * aFrameItems.  This function will create table pseudo-frames as needed if
+   * aAllowPseudoFrameCreation is true..
    */
   nsresult ConstructFramesFromItemList(nsFrameConstructorState& aState,
                                        FrameConstructionItemList& aItems,
                                        nsIFrame* aParentFrame,
                                        nsFrameItems& aFrameItems);
-
+  

There is no aAllowPseudoFrameCreation parameter. Also you're adding trailing whitespace.

+      case eTypeRow:
+        wrapperType = eTypeBlock;
+        break;

You might want to add a comment here that this will actually create a cell. It's a bit confusing.

The overall algorithm is fantastic, however.

I think that StealItems should not require an empty destination list. We can just guard the optimization with an IsEmpty() check.

+  if (aItem->mIsAllInline) {
+    ++mInlineCount;
+  }
+  if (aItem->mFCData->mBits & FCDATA_IS_LINE_PARTICIPANT) {
+    ++mLineParticipantCount;
+  }
+  ++mItemCount;
+  ++mDesiredParentCounts[aItem->DesiredParentType()];

For all this code I think we should have a helper, something like
FrameConstructionItemList::AdjustCountsForItem(FrameConstructionItem* aItem, PRInt32 aDelta).

Comment 8

[Boris Zbarsky [:bzbarsky]]

> Is there a problem with hardcoding a mask and bit-offset?

Probably not; I have a PR_STATIC_ASSERT around in an case that the TYPE_SIZE is big enough.  The initial cut of the patch stored two parent types (desired one and ours), but the second one turned out to not be needed.  I should have dropped more complexity.

> Yeah I think so, especially since the iterator is modified.

OK.  Will do.

> RemoveItem?

It's more than that, since it also deletes the item.  Maybe DestroyItem?

> There is no aAllowPseudoFrameCreation parameter.  Also you're adding trailing
> whitespace.

Er, indeed.  Forgot to fix the comments.  Will fix the whitespace.  

> You might want to add a comment here that this will actually create a cell.
> It's a bit confusing.

Will do.

> I think that StealItems should not require an empty destination list. We can
> just guard the optimization with an IsEmpty() check.

Good point.  Will do.

> For all this code I think we should have a helper

Ah, good idea.  That was bothering me to.  Will do.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to comment #8)
> > RemoveItem?
> 
> It's more than that, since it also deletes the item.  Maybe DestroyItem?

There are other places where Remove methods destroy the things they're removing, notably nsIFrame::RemoveFrames. DeleteItem would be fine too though.

Comment 10

[Boris Zbarsky [:bzbarsky]]

Attachment: Part 3 updated to roc's comments.

Comment 11

[Bernd]

There is that old comment: before ConstructTable

// Construct the outer, inner table frames and the children frames for the table.
// XXX Page break frames for pseudo table frames are not constructed to avoid the risk
// associated with revising the pseudo frame mechanism. The long term solution
// of having frames handle page-break-before/after will solve the problem. 

Would that be now feasible?

Comment 12

[Boris Zbarsky [:bzbarsky]]

It would be, but it's not clear when you'd need page-breaks for pseudo table frames.  After all, those style contexts never have page-break styles.  One could do it based on the kids the table frame is wrapping or something, but it's not quite clear how that should behave.  Say if you have a bunch of rows and the first row has "page-break-before: always", we might want to break before the table.  But what if it has "page-break-after:always"?  And should the anonymous table behave differently than a "real" table would in this case?

In any case, I do think we can look into that, but as a followup bug.

Comment 13

[Bernd]

Random review notes for my self just to keep them organized:  

AdjustParentFrame does only one thing it looks up if the child is a caption and then calls AdjustCaptionParentFrame. 
AdjustParentFrame is a misnomer now it doesnt describe what goes on in the function.
All the code could also go into AdjustCaptionParentFrame with a early bail out if this the child is not a caption with a rename to AdjustIfCaptionParentFrame. 

FCDATA_DISALLOW_OUT_OF_FLOW is set at row group and col group pseudos but not on the row and cell pseudos, do we allow out of flow pseudo rows?

Comment 14

[Boris Zbarsky [:bzbarsky]]

> AdjustParentFrame is a misnomer now it doesnt describe what goes on in the
> function.

Good point.  I'm still looking for a way to get rid of this function, for what it's worth...

> All the code could also go into AdjustCaptionParentFrame

Yes, but there's another callsite into AdjustCaptionParentFrame that wants something a bit different out of it...

> FCDATA_DISALLOW_OUT_OF_FLOW is set at row group and col group pseudos but not
> on the row and cell pseudos, do we allow out of flow pseudo rows?

No, but those are using a FrameFullConstructor, and hence shouldn't be using that bit no matter what.  FCDATA_DISALLOW_OUT_OF_FLOW is needed if ConstructFrameFromItemInternal will be handling the appending the the frame list itself, so it knows what frame list to add to.  For rows and cells, the append is done directly inside the ConstructTableRow or ConstructTableCell function, and it just puts it in the in-flow parent list.

Comment 15

[Bernd]

Its hard to guess from the source of the patch for me how this thing works. My
feeling is that we switched from a can this parent be our parent to a can this
child be our child algorithm.

I might have missed the comment, but a comment around CreateNeededTablePseudos
how this algorithm works in general would be helpful.

The way I see the algorithm is: we see that the children can't be direct
children we walk over a all children till we find one that can be a direct child, we stuff then the whole run excluding the stopping one into one item where we place the run as the children of this item and trigger a special processing. This repeats over all potential children 
As the result we get a new list of items which can be direct children of the
parent frame and we go and construct them. 
During the frame construction this will repeat till all necessary pseudos are
created.

If so this is correct it corresponds so much more the tree creation that we
usually do.

Comment 16

[Boris Zbarsky [:bzbarsky]]

The "can this parent be our parent?" and "can this child be our child?" questions have identical answers, so there really isn't a change there, in some sense.  What's changed is that instead of constructing, for each child, the full stack of parents it wants given its current parent and then pushing/popping that stack as we go through kids we now go through our list of kids, find all the ones that don't want us as a parent, and wrap them in something that will get them closer to the parent they want.  When we later process this wrapper, we might wrap its kids again, as needed.  So there's a lot less state being maintained, and the price is the possible multiple child list traversals I mentioned above.

> I might have missed the comment, but a comment around CreateNeededTablePseudos
> how this algorithm works in general would be helpful.

I'll write one.

> The way I see the algorithm is

You see it correctly, yes.  And yes, this is indeed much closer to how we normally do frame construction.  :)

Comment 17

[Bernd]

Comment on attachment 367212 [details] [diff] [review]
Part 3 updated to roc's comments.

r+ with the algorithm description

Comment 18

[Boris Zbarsky [:bzbarsky]]

Checked in with that comment.  Tree looks green, Talos seems to be happy, 6KB codesize savings on Linux, 8KB on Mac.

Marking in-testsuite+, though this is really a black-box change; the tests were testing existing code too (except for the one white-space test that became better).

bernd, roc, thanks for the quick reviews!

Comment 19

[Boris Zbarsky [:bzbarsky]]

Oh, and the relevant changesets were:

http://hg.mozilla.org/mozilla-central/rev/da61aad96bf9
http://hg.mozilla.org/mozilla-central/rev/523942ee51c8
http://hg.mozilla.org/mozilla-central/rev/237db3258d19