Sorting floats

Floats are sorted, to make binary search possible, in these lists:

for each generator: dw::OutOfFlowMgr::TBInfo::leftFloatsGB and dw::OutOfFlowMgr::TBInfo::rightFloatsGB;
for the container: dw::OutOfFlowMgr::leftFloatsCB and dw::OutOfFlowMgr::rightFloatsCB.

The other two lists, dw::OutOfFlowMgr::leftFloatsAll and dw::OutOfFlowMgr::rightFloatsAll are not sorted at all.

New floats are always added to the end of either list; this order is called generation order. See also above: GB lists and CB lists.

On the other hand, there are different sorting criteria, implemented by different comparators, so that different kinds of keys may be used for searching. These sorting criteria are equivalent to the generation order.

dw::OutOfFlowMgr::Float::CompareSideSpanningIndex compares sideSpanningIndex* (used to compare floats to those on the respective other side); if you look at the definition (dw::OutOfFlowMgr::addWidgetOOF) it becomes clear that this order is equivalent to the generation order.

dw::OutOfFlowMgr::Float::CompareGBAndExtIndex compares externalIndex for floats with same generators, otherwise: (i) if one generator (T1) is a direct ancestor of the other generator (T2), the child of T1, which is an ancestor of, or identical to, T2 is compared to the float generated by T1, using externalIndex, as in this example:

T1 -+-> child --> ... -> T2 -> Float
    `-> Float

Otherwise, the two blocks are compared, according to their position in dw::OutOfFlowMgr::tbInfos:

common ancestor -+-> ... --> T1 -> Float
                  `-> ... --> T2 -> Float

This is equivalent to the generation order, as long it is ensured that externalIndex* reflects the generation order within a generating block, for both floats and child blocks.

dw::OutOfFlowMgr::Float::ComparePosition ...

Miscellaneous notes

Handling collisions

The CSS specification allows two strategies to deal with colliding floats: placing the second float beside or below the first one. Many other browsers implement the first approach, while dillo implements the second one, which may cause problems when the author assumes the first. Example: the "tabs" at the top of every page at Wikipedia ("Article", "Talk", ...).

Float containers in flow

Consider the following HTML snippet:

<body>
  <img src="....jpg" style="float:right">
  <p style="overflow:hidden">Text</p>
</body>

Interestingly, dillo shows "Text" always below the image, even if there is enough space left of it. An investigation shows that the paragraph (<p>) is regarded as own floats container (because of overflow:hidden*), so the floats container above (<body>) regards this block as widget which must be fit between the floats (dw::Textblock::mustBorderBeRegarded > dw::Textblock::getWidgetRegardingBorderForLine). However, since a textblock in flow always covers (at least) the whole available width, which is defined without considering floats, the space left of the float will always be to narrow, so that the paragraph is moved below the float, by inserting an empty line before.

When searching for a solution, several difficulties show up:

The available width, which is used for the width of the textblock, is defined independent of floats. Aside from problems when changing this definition, a dependance on floats would be difficult to implement, since sizeRequest is independent of a position. (See also Handling Elements Out Of Flow.)
I must admit that I do not rembember the exact rationale and the test case behind adding the exception in dw::Textblock::getWidgetRegardingBorderForLine (see above), but simply removing this exception will result in a possible overlapping of floats from both containers, since no collisions are tested for.
On the other hand, mixing the float containers (interaction of two or more instances of dw::oof::OOFFloatsMgr), e. g. for collision tests, would become too complex and possibly result in performance problems.

Instead, this approach is focussed:

Goal: the paragraph is narrowed so it fits, as a whole, between the floats.
The approach is to remove the exception in dw::Textblock::getWidgetRegardingBorderForLine. A textblock, which is a float container in flow (as this paragraph), is returned by this method and so dw::Textblock::mustBorderBeRegarded returns true*. This will put this paragraph again at the correct position.
To avoid overlappings, the linebreaking width of this paragraph (which is also used for positioning of floats) is the available width, minus the maximal float width on either side. (This is an approach similar to the one dw::Ruler will use soon). Most likely, some new methods will have to be added to calculate this.
For paragraphs like this, dw::Textblock::borderChanged must rewrap all lines; y is irrelevant in this case.
Since the textblock will tend to become taller when getting narrower, and so possibly cover more (wider) floats, and so become narrower again etc., there may be multible solutions for calculating the size. Generally, a smaller height (and so larger width) is preferred.
There remains a problem: what if a word is too large? Should a textblock of this kind then reard the floats in detail, to insert empty lines when needed?

Real-world cases: Overflow:hidden is set for headings in Wikipedia, and so this case occurs when there is a float (thumb image) before a heading. See e. g. this page and scroll a bit up; the company logos should be right of this section.

Priority: Since this is not a regression, compared to not supporting floats at all, a fix is not urgent for a new release.

Resizing

Has the case that a float changes its position to be regarded? Probably yes, but cases where no other mechanisms come into play are rather unlikely.

Priority: If this plays a role, this means a regression compared to not supporting floats at all.