Eric Atkinson visit 2013 09 10
Lars Bergstrom edited this page Sep 18, 2013
·
3 revisions
The key idea is that incremental flow construction is a bottom-up tree traversal with some extra stuff for keeping around old flows.
Gecko has frame construction items (FCIs) that contain the flows that need to happen. Each flow yields a frame or a frame construction item.
In servo, as a kid of a block, we would make a frame construction item (which might have multiple frames or boxes). Then, we get either a flow or another frame construction item.
If you get to a flow and your parents are not dirty, then you are done (e.g., a block). You don't always need to re-create your parents' flows.
Absolutes will have to be put in frame construction items until we get to the containing items. Table cells, absolutes, and fixed, and inline block splits (inlines in general).
Fixed are fixed to the viewport, so they may have to go at the top of the page. If we can keep them as a separate flow tree, that will make things simpler, since keeping them in the root will force you to re-create the root items.
The flow tree would change to what we have now plus an array of fixeds.
- eric: the trick is that if you add a node, you need to re-create the construction items of its parent. You don't need to re-create all of them.
- pcw: you have to re-create until you have created a flow and then you're done. You have isDirty and isDirtyChildren.
- jack: as you go up you may have some frameconstructionitems and some flows, so as you go up the tree, you may have to keep going up.
- pcw: the question is something of ib-splits. if you have something like inline kids (from a DIV with three SPANs in it), and we add another span to that set, the HTML and DIV will be marked HDC (has dirty children) and the new span will be marked D (dirty). That span will create a FrameConstructionItem. HDC basically means "I might need to create a FrameConstructionItem if I can't construct a complete flow, but if I can " The new span creates a FrameConstructionItem : InlineFrameConstructionItem(RenderBlock("chocolate")) We then create one InlineFlow for all three spans
The DOM nodes do not currently store anything, but will need to store (weak) pointers to their flows. At least DIVs, possibly SPANs. SPANs probably need to store a range of construction items
There will probably have to be some logic that will look at all of the FCIs and the boxes we already have is that we have to merge them.
-
eric: on the DIV, we could just re-run its kernel function
-
pcw: we would have to run the childrens' kernel functions to get their flows again to merge them
-
pcw: we probably need special case heuristics for all of the different types of changes and then a "reboot" if it fails
-
eric: what if we kept around the flow construction items?
-
pcw: Then we could just merge them together again.
In that example, we have a BF->IF->{I, Like, Truffles} The RenderBoxes may need to be reference counted since they are accessed by multiple things, because copying them may be kind of ugly. Because of that, maybe it's easier just to write logic to merge existing RenderBoxes and FlowConstructionItems.
- eric: in either way you need to do something special with the boxes. somewhere along the line you need to have references to either a box or a flow
- pcw: so maybe something like this in each node:
NoRenderer,
BoxRenderer(WeakRef<Flow>, WeakRef<RenderBox>),
FrameConstructionItemRenderer(RenderBox)
}```
every BlockFlow has a render box, right?
- eric: yes, everything that goes on a screen is a Box at some point
- pcw: so every node has a pointer to its flow and render box
- eric: can a node have more than one renderbox?
- pcw: yes, generated content. maybe not worry about that case for now and just slide it in there? WebKit has a concept of each Renderer
script tasks should never look at a renderer.
The goal of a kernel function is to look at all your kids, take their renderers, update their boxes to be renderer (or no renderer for display:none).
Iterate over your kids' renderers and re-create all their boxes. Over time you can get smarter.
- eric: when can't a child turn its box into a renderer already?
- pcw: if there are nested spans, the child might not know which flow it will be a part of
- pcw: the FCI-R is where it lives until it migrates to the flow
## renderers and pointers thereto
- jack: what are renderers?
- pcw: they are the things attached to nodes
- eric: box renderer is what you hold onto after you've created the flow tree
- pcw: hold onto the box and flow renderers
- jack: why not index?
- eric: probably a range, for infline flows
- jack: might be on multiple lines
- pcw: might have to update it as you do the reflow
- eric: what's the reason you need the renderbox? oh, it's for the next time around so you know the boxes you made for each node
- pcw: the FCI is temporary
- jack: what do you use the FCIs for?
- eric: they are lazy box renderers. they store the same information but you haven't put them in the final spot in the flow tree yet. the box renderers are going to have to be some kind of weak reference because you want the allocation to be done in the flow tree. but the fcirenderer is the strong reference to the pointer.
- jack: but they don't stay fcirenerders, right?
- eric: you should have them around when you create the flow
- pcw: as you go up the tree, you swap them out for the *whole* subtree
- eric: e.g., nested spans down at the bottom
- pcw: no, bubble the FCIRs at each level maybe eagerly?
- jack: but the point stands that the FCIRs turn into BoxRenderers. It's an insert, so there might be boxes on either side
- pcw: in the three SPAN to four SPAN, you have three render boxes and a FCIRenderer, you then stitch it in (insert) and then replace it
- eric: the first time around, aren't all the three SPAN-owned BoxRenderers going to be collapsed into one when you go up?
## merging
- eric: merging can only be done when you convert FCIRs into BoxRenderers.
- pcw: need to gather all inlines in your subtree and then convert them all at once
- eric: yes, if you stored a list of render boxes you might be OK, but it would make it a lot harder for other future inserts
## line breaking results
- jack: can we save the line breaking results?
- pcw: gecko does: it floods everything to the right with dirty bits. but text breaking happens later.
jack: no, this is incremental because we've already line broken once
- pcw: for RTL or LTR it's the same, just dirty bits in the direction of break
- jack: the only examples I've seen is numbers or names, etc.
- eric: in BIDI you can switch (e.g. RTL arabic then LTR Patrick)
- jack: in BIDI, just ditch it and rebreak it all?
- pcw: I think we can still just look at where the break is and where we went and mark the rest of the line (in source input order) dirty
- pcw: there is the "child became non-inline" case, though
- eric: instead of using dirty bits, could you maybe decide when visiting the child to invalidate the parent or not?
If you add a node, you always invalidate the parent. If you switch the effective display, you invalidate the parent.
- jack: why wouldn't HDC work there?
- pcw: eric's is just possibly easier.
## adding divs to nested spans
- eric: what if you have nested spans and add a div?
- pcw: the added div does not get an FCI; it gets a block
- eric: previously you had a boxrenderer at the span with an inline flow part
so we're changing the display on that span. we need to redo that node and it children, getting a BoxRenderer
- pcw: blocks give you a BoxRenderer
- eric: we get that BoxRenderer and hand it up to the parent span. That span needs to have some kind of state that has been kept around.
- pcw: its box renderer could be an inlineflow
- eric: we wipe that out and re-create it
- pcw: when a node is dirty if its children are not all FCIs
- pcw: how do you decide a frame needs to be nuked?
- eric: yes, when do you invalidate your parent node?
if you have dirty children, when do you invalidate yourself?
- pcw: invalidating your parent is equivalent to turning yourself into an FCI and nuking your box. So, invalid means having an FCI instead of a Box. So, you need a notion of when you turn yourself back into a FrameConstructionItem.
## frame construction items
- eric: first time through the tree, we get FCIs at the leaves.
- pcw: they stay there and you want to mark everything dirty up the way
- eric: so just bubble it all up into a list on the way?
- pcw: when you get to the top you have to know you need to look at all your children to find the inlines
if we pretend it all starts out as NoRenderer, we still need to know if it's dirty
- eric: we should probably bring the list up
ok, so we merge the RCIs as we go up the trees. at the top we turn them into boxes. so then do we have to turn the items at the leaves into BoxRenderers?
- pcw: how do we know we need to? we need to store it all somehow
- eric: then we change everything to BoxRenderers all the way up
- pcw: they each point to inline flows except the top one. the identity of the BR tells us
- eric: you can just look at the DOM node. we have the before/after styles at each node
- pcw: no, selector matching happens after flow construction
it would be extra work to store it. if we can just look at the flows…
- eric: not convinced that will handle every case. may need a style difference on the nodes
<<returning to example>>
so we nuke one of the SPANs and create a DIV instead (i.e., its display changed)
- pcw: that is where the traversal will start. we have the old node around.
- eric: so we add an FCI at that nuked node
when you change the renderer you need to invalidate your parent. So your parent becomes an FCI, all the way up to the parent.
- pcw: once you get to a box, you can stop there. the parent of the changed item gets an FCI, whereas below you have a new BR. The rest of the way up you get FCIs.
- eric: in tables or {ib}-splits, if you change to display:none, you may need to push a change up
in general, always invalidate your parent if your display changes
- pcw: but the maze solver relies on it! it's like 900 divs…
- eric: the only place where it's safe is if you have a div where your parent is a div. you'll go up to the div, see that you have no children and then stop there
- pcw: if you make an FCI, you always invalidate your parent. which makes sense; they indicate that your parent has something to do. there are cases where you create a BoxRenderer and still have to invalidate your parent.
- pcw: the tricky thing is where you have some items in other places and you are trying to figure out how to save as much as possible and merge your existing items. that is going to be messy
- eric: at least that ugliness will not overflow in servo into the other cases of basic merging
the problem with the merger is that the boxrenderers have to index into and possibly merge into the inline flow's list of boxes
- pcw: thinking linked lists? but so much overhead… still, all browsers use linked lists there. they don't have renderboxes separate from inline flows. the overhead of five pointers per render box may be more than the cost of just nuking and re-create. can we do something smart by exploiting that you are invalidating mainly to the right
if the renderbox list looks like N items and you are at 3, maybe just nuke the items after #3? the flat lists of render boxes might save a huge amount of memory for us.
## absolutes and {ib}-splits
- pcw: absolutes and {ib}-splits need to bubble up to the top
- eric: positions that are static need to be pushed up
- pcw: we can avoid the current containing block and dealing with it
- eric: the containing block also prevents parallelization because the threads need to block on it
## display lists
- eric: display lists. do them built up incrementally? Or alternatively pre-compute the displaylist size and z-indexes, allocate at once, and then stuff everything together in-place.
- pcw: could we put it all in an array and then sort it at the end?
- eric: on our GPU version, we compute how many display items you need for your subtree. Then at top-down, you can push down the indices to children.
- pcw: z-indices?
- eric: multiple insertion points, and then afterwards add the offset
- pcw: when do we know? floats on top of non-floats, etc?
- eric: there's a specified ordering, but nothing scary about it. without specified z-indexes, you sum the number of float display items, position display items, and then you find the insertion points for each one.
- pcw: calculate the insertion points using BU then TD…
- eric: you can write during the TD! you don't even have to compute the whole display list on diffs, but you could just keep around the display list and then just send a diff to the renderer. you'd be re-allocating them all and then re-creating it all.
## interruptable layout
- pcw: what about interruptable layout? chrome is doing partial layout and then returning (which will probably regress performance!). we're hoping to use ReflowGoal to pass a channel through layout so the interrupted result can be resumed
- eric: just need to insert a yield point to check to for queries. also interested in mobile
- pcw: can we ask for just the viewport's worth of data
- eric: so some kind of partial pass. speculating that they fill the viewport
- pcw: need to look at all of the flow tree objects
- pcw: position:fixed can go anywhere. negative margins can also mess you up in choosing the early viewport
## merging
- eric: how does merge work?
- pcw: if it's a BR, leave it alone. if it's got an FCI, it goes into the kids
- eric: when you merge an FCI with a bunch of BRs, what are you doing?
near the top, how do we avoid re-visiting those children? regardless of the abstraction, you want to take your inline flow (which has a vector of boxes) you want to split them in two and wrap them in a new inline flow.
- pcw: that's what webkit does
- eric: so if the BR stores a range, you can do that?
- pcw: you still need to update the inline flows, which means you need to go down and visit all of the guys to update the flow pointer
## reflow
- eric: probably better to have reflow be slow than the first pass, right?
- pcw: rather neither, but yeah, reflow
- eric: at some point we have to do the fixup to merge an existing node with a new one
- jack: easier to hide work in reflow since it's only a piece of the document. only do the initial one once, but reflow all the time
- pcw: incremental rendering also gets you like if the HTML is not yet loaded
- jack: need a solution to late image load
- pcw: it's just adding nodes to the partial dom
- eric: don't you need to reparse it?
- pcw: nope, it's in a separate thread in ours. hrm, can we suspend and redo reflow, right?
- eric: as you start with the words as spans, create the temporary FCIs. then, when you go up, put an FCI up the nodes but actually swap out the bottom ones fro BoxRenderers and then you don't have to do it when you go down. BoxRenderers would then have to have some kind of abstract information. Then what you want to do when you try to merge an FCI with a BoxRenderer, you have to do the complicated merge.
- pcw: I'm confused. What do you put in that BoxRenderer's flow incrementally?
- eric: I'm not sure about this. The BR should just be something you can merge for FCIs
- pcw: but it also records what flow and RB each belongs to, which is important for querying in layout
- eric: what kind of stuff do we need to query?
- pcw: position, width, heigh, all content boxes associated with the nodes
- eric: can we get those off the display lists?
- pcw: I think so, but we have to build that display list… might be slower. stupid benchmarks to offset.x over and over and over
- pcw: if we can go from a renderbox to its flow then it would be fine
- eric: but then it's not a tree!
## Style queries
- eric: what kind of style queries do we need to do? For get bounding style rect, we need to go further down in the render tree
- pcw: not concerned about those questions
