Meeting 2013 06 14

Servo layout meeting 2013-06-14

agenda

• floats
• tables
• what edge cases exist?
• incremental reflow

Attending

pcwalton, brson, eston, dbaron, eatkinson, seth, simon, bz, jack, tkuehn

• dbaron: in terms of placing floats, they are placed in order. problem is they have an anchor point. spec calls 'placeholder'. anchor point of float need not be at linebreak point. can be in middle of non-breakable line.

• dbaron: constraint is that a float cannot be higher than top of line containing its anchor point, but it must be as high as possible while satisfying constraints. so if it must go (higher) than anchor point you must.

• dbaron: ?

• dbaron: in gecko we have weird multi-pass code that is avoidable had it been designed differently.

• dbaron: multiple cases where we do multi-passes to handle cases where we realize something didn't work, try again

• dbaron: placing float next to line containing anchor point reduces space available for line

• db: (something) can increa

• db: in turn reduce the width available for that line. because you could already have floats that intrude

• db: floats can have 'clear' on them. situations with small float, then bigger float below it, but still placing lines up tope. the avail width of content for line is a fn of floats that intersect the line. not all browsers implement correctly. they tend to show overlapping text on wikipedia

• db: other problem requiring multipass in gecko is we don't do vertical alignment until line lineout. don't know height of lines - they may end up bigger than we thought and need to be redone.

• db: would be better as one pass

• db: need to do vertical alignment as we place breakable units on the line

• db: there are 'unbreakable units' (could involve arbitrary num elements). we have a model that commits to placing them. before commiting figure out what changes in vertical alignment that causes

• db: 2 models of v. align. top-bottom and everything else. 'everything else' cases is anchored to parent. top-bottom is relative to the line, everything else is relative to the parent

• db: process of commiting unbreakable unit: figure out effects on vertical alignment, total line height; figure out if that reduces available space; commit unbreakable unit; place floats with anchor points within that unbreakable unit or before the next one.

• db: those floats might fit adjacent to line or might be below it

• db: if you want knuth-style linebreaking this doesn't work

• db: fun cases: adding something to a line makes line taller, makes avail width narrower

• db: fun cases: if you were to add something to line, makes line taller, makes avail width narrow, prevents adding to the line. if you hit that case where do you put stuff in the line?

• db: assuming it reduces e.g. space avail on left side. spec doesn't address

• db: (missed)

• db: say you have an image in the line or something with large font size, toward end of line. if you put that on line then line is taller such that it hits a float.

• db: if line is left aligned does it start (there) or (there) even though it doesn't intersect the float at all

• db: in gecko, there are three nested loops where we do multipass layout. LINE_REFLOW_REDO_NO_PULL, LINE_REFLOW_REDO_MORE_FLOATS, LINE_REFLOW_REDO_NEXT_BAND. LINE_REFLOW_REDO_NEXT_BAND says 'we now intersect more floats so need to redo'. (note: that wasn't true)

• db: we sometimes commit things that are only a piece of an unbreakable unit, LINE_REFLOW_REDO_NO_PULL is the case where we committed some things but then discover there's more stuff before the next breakpoint and it doesn't fit.

• db: LINE_REFLOW_REDO_NEXT_BAND - no unbreakable unit fits on this line at all. therefore you keep pushing it down until there are no more floats or it fits. if you have a word that is long enough such that it doesn't fit next to any floats, then you either keep searching or you search until there are no floats.

• eric: if you get to a spot where there are floats but they are outside the current block.

• db: the spec initially described this stuff in terms of a model where what mattered was whether there were any floats in the block context. but you can have floats that are in a previous block that is wider. say you have two ensted blocks, first one is 100px wide, inner is 50px wide. which float rules care that there is a float there and which ones don't? the answer is all of them, but no browser has implemented that. were going to change the spec but IE10 implemented it. in theory you're supposed to consider the stuff outside. if the inner block is 200px wide and it's a 250px long word, you have to push it down.

• bz: think you've covered the main gotchas. there's the fact you really have to do layout on float before placing next float, right? have to figure out hegiht of first before next, unless they can fit side-to-side next to each other.

• db: in most cases you can do the layout of floats in advance

• bz: except auto-width ones?

• bz: width does not depend on width of other floats around because we got rid of the quirk way floats all the way on the right were really skinny

• db: except there's a quirk with tables of width something-or-other (he actually said this)

• bz: so you lay them out sequentially?

• db: think so

• eric: need to know float's heighth?

• db: to place it. but the height is not a function of the placement. it can be computed in isolation. well, if it has a % height that is resolvable from style in cases where it's (mumble)

• bz: yes

• db: want to go back to clearance. it's harder than it looks. doing it efficiently is hard. our code in gecko is not efficient. it has some bugs. i don't remember the 'fun stuff' with clearance

• bz: me either. that's roc

• db: felt when roc reimplemented that there was an alternative model that was more efficient but roc implemented it using the spec model. I think the spec model is picky enough that an alternative model probably doesn't work any more.

• pcwalton: maybe it makes sense for eric to describe what you've sketched out.

• eric: couple options for placing floats and determining free area around them. it's not super-complicated yet. trying to integrate that into layout traversal. want to make sure i'm not making assumptions that need to change later

• pcwalton: are floats hanging off blocks or is there a float manager?

• eric: floats in flow tree in same place they were in dom. if flow is inline of element in doc tree it's a child of that inline flow. have to do that for weird cases where (can't hear)

• simon: you need a place for the other

• db: float is parented to nearest block and there's also a float manager for block formatting contents. doing incremental relayout efficiently might require having better ways of getting to the float than going through all the inlines.

• db: the other fun piece of floats is paginating this whole thing. idk how much you've thought about it?

• eric: haven't. important for column layout?

• db: yes, also called 'fragmentation'. one of fun things about floats is that if you hit a fragmentation container, the end of your fragment, the flow can continue into the next frag even though parent doesn't. then what if that fragment has different width?

• db: you can not only have continuation into next frame but also starting in next frame. this is even more fun that absolute, static positioning, in that we haven't solved a lot of these issues

• eric: how fully is fragmentation speced

• bz: (hearty laughter)

• bz: there's a lot of this behavior is undefined. people writing spec have no idea how to deal with this. doesn't help us because we have to figure it out

• db: there's a harder case with float fragmentation that I'm forgetting about. case where first frag gets pushed to next is fun, especially if you want them to follow all the rules correctly. there are cases in gecko where we might get the floats out of order.

• brson: want to make sure dbaron understands what our design is and whether he agrees with it.

• eric: i wanted to know whether hangign the floats off the flow tree like i described is a good play for incremental layout.

• db: one of the fun things with inc layout: if you want to reflow a small piece of the layout. there might be data structs that could help solve this problem better. if you have some incremental change, you want to be able ot recover the state without going through all the original ocnstruction work. gecko doesn't store the state everywhere, and we recover it along the path. it might be solvable with a datatructure that records what the state is at different points. i'm not crazy about the entire design of our incremental layout code in gecko, although it's pretty important for performance. there ought to be a way to do that better, but i don't know what that is.

• pcwalton: we want to avoid decisios that compormise our ability to do incremental layout in the future. what don't you like about inc layout in gecko even if you don't have a better idea now?

• db: part of what i don't like about it is that we have to write it all separately. maybe it's not so horrible, but in the block case it's pretty bad. essentially teh model is that ignoring instrinsic widths, there are two bits. nsframe_is_dirty and ns_frame_has_dirty_children. first is this frame and all descendents have to relayout. second means this frame is mostly ok, but a child needs relayout or this is an edge case that almost means the same thing, like removing a child.

• db: what happens in gecko now, is that you can choose to make optimizations based on these two bits.

• bz: inc layout starts at the root and walks the tree. the paretn can say child has no

• pwalton: how are the dirty bits computed?

• db: whenever styles change propagate change to the nearest reflow root

• db: one of the thingsi that bugs me about block is that the web imposes severe performance constraints on blocks. page might want 10,000 blocks in a row and then want a text editor in that, and we need to keep up with a user typing. there could be floats in there an other fun things.

• db: the whole state recovery problem (state involving floats and state involving margin collapse) in a single block with thousands of children is sort of painful. tehre is a lot of code in block frame to deal with these cases. some cases can use the optimization and some can't. the incremental modifications case is seaprate from resizing optimizations case.

• db: parent decides to reflow the children based on resize and/or dirty bits.

• pcwalton: is there a way to not have the dirty bits?

• db: haven't thought about it

• bz: need to figure out which things need to get layout. obvious options: start at root and look for needed changes; start at the thing changed, redo it, and go up tree with fixups. benefit of dirty bits is it can leverage normal non-incremental layout path. it looks like normal layout that skips some of the work.

• pcwalton: better for parallelism? once dirty bits are computed can do the parallel algo, but it skips work. set dirty bits sequentially then do parallel layout. may short circuit nodes.

• bz: dirtybits set sequential naturally. they arrive from style changes or dom mutations. dom mutations are naturally sequential, style changes not, but setting dirty bits is easy. can record which need to be set and serialize. never seen dirty marking show up in profiles

• bz: potential for having lots of work is limited by leaves in tree. in typical page maybe 10k nodes

• pcwalton: how does webkit do it?

• bz: idk

• pcwalton: dirty bit approach sounds good.

• bz: drawback, if you have 1 thing in dirty block, the block scans all kids to find which is dirty. ideally you have low-constant order N thing going on. not obvious if there are good ways to get around it, block layout already has order N stuff. might be worth being faster if you can figure it out, can be added later

• pcwalton: do we optimize that case in gecko?

• bz: it does a linear scan

• pcwalton: sounds parallelizable

• bz: yes

• pcwalton: I'm basically satisfied about incremental layout. eric?

• eric: no. it sonuds like this should integrate well with parallelism

• pcwalten: def. bz or dbaron if you have ideas about how to do this better please get in touch

• pcwalton: last thing. tables. they are used a lot.

• eric: what db recommend we do for tables

• db: want to go back to floats. that quirk where width of float depends on other things around it in one case. we currently impl that inside nsBlockFrame flow_inplace_float only for tables in quirks mode. might be you can get away w/o but not sure.

• db: tables: i know about width calc but not as much about height. wanted to rewrite height calc before IE 6 died, but now web is stuck with our height calc rules because webkit and ie 7 reverse engineered us. IE6 was better.

• db: width calc: doc explaining this: (http://dbaron.org/css/intrinsic/)

• db: basic model of width calculation: everything has min intrinsic and pref intrinsic width. built up from leaves to ancestors (can't follow)

• db: build them up from leaves to ancestors. every cell in table has one of these. then compute intrinsic width on columns fromt intr. width on cells. basically trivial except for col. spans.

• db: distributing intr. width of col. span cells to the cols they span is basically same as final (something) layout. come back to that in a sec.

• db: a table cell essentially has 4 widths: a cell might have specified width, which might be %. turns out that basic model in tables is % trumps everything. specified width beats non-specified width.

• db: a column has two intrinsic width: min intrinsic (max intrinsic of cells), pref intrinsic (may or may not come from spec width). if (didn't follow logic)

• db: if there are () then it's the largest of either the max(specified non-% width, min intrinsic width), or min(intrinsic width of (something))

• db: i

(missed lots of logic)

• db: have problem when actually laying out table. shrink-wrap algo max(min intrinsic width) + min(preferred intrinsic width).

• db: then you have columns with data about them and you want to figure out how to distribute actual width of table to columns. if actual width is less than the table's preferred intrinsic width there are 4 possibilities. take linear combination of those closest

• db: first assignment, min intrinsic. second is % width. .... fourth assignment is all columns without specified with their pref width.

• db: if you layout at a particular width, it's going to be in between those two and (missed)

• db: and there is a case of what happens when you try to assign a width that is bigger than pref width. then there's a set of priorities for who gets the extra space. give it to columns proportionally to their pref width. and so on. it's documented in the code and should be comprehensible. file is basic_table_layout_strategy

• db: heights are just crazy. in IE6 heights work like widths, but in gecko they are just crazy. there are still going to be quirks and the web depends on them. css specifies that % heights are only honored inside a container with a fixed height. there are weird extra cases where % heights get honored sometimes outside of a fixed ehight container.

• bz: like in webkit it's the table that's the container, but in gecko it's the table row.

• db: in IE6, things like % height behave like % widths; there is a balancing algorithm. in gecko it matters what your containing block is. % heights on cell's children have to be honored soem of the time and it matters which cases you do it for. if you have two cells in a row and one has a specified height, then the other has to be that height too unless its contents are bigger than that. there are cases where the basis of the % is stuff in another cell. the rules are just weird.

(missed)

• eric: this sounds like absolute positioning.

• db: absolute positioning has the advantage that it's specified how it works.

• eric: has gecko's height algorithm been documented?

• db: no

• pcwalton: how much does the web deepnd on gecko's height algo?

• db: it's not clear. it's possible we could implement the IE6 thing. i'm not sure if we could get away with it or not. this area is not interoperable.

• gz: have we talked about colspans?

• db: it's the same distribution algoirthm as final width.

• bz: there's weirdness like you distribute in order of the colspan values. there's weirdness is around that stuff.

• db: that's not interoperable. in some browsers you get into a situation when you swap the order of rows the width will change because of the way they commit colspan data. in gecko we have two buffers. we do all the cells with no colspans and accum width data. and that's all committed as it happens. then we look at all the cells with colspan=2 and commit those to a secondary buffer and we run the distribution algo distributing the width to colspan=1 cells. you do distribution for each without looking at the other ones.

• db: i think this is the right way to do this because it avoids the cases where the widths switch when you swap order of rows.

• bz: other thing to consider for tables: for fragmentation how do you plan to do headers and footers? gecko's approach is not going to work

• db: when you fragment tables the header/footer repeat every fragment

• bz: gecko does this in a way that does not work with incremental reflow. we don't allow fragmenting tables except during printing.

• bz: would be nice not to have that restriction