Docs: add some

1 files changed, 493 insertions, 0 deletions

diff --git a/docs/ideas/boxes.txt b/docs/ideas/boxes.txt
new file mode 100644
index 000000000..f1fa2360a
--- /dev/null
+++ b/docs/ideas/boxes.txt
@@ -0,0 +1,493 @@
+Box tree dynamism
+=================
+
+The first building block needed for event-driven layout is for the box tree
+construction and subsequent maintenance to become event driven and for the
+box tree management implementation to emit events marking parts of the tree
+changed so that the layout calculator can react to them.
+
+We expect the box tree to be in normal form at all times (and certainly
+whenever an event is emitted). The box tree manager must ensure that this is
+the case.
+
+[Note: the box tree manager could be plumbed into the existing content handler
+with a little effort: have the box tree constructed dynamically during the
+parse, but ignore box tree events and perform layout computation at the same
+place as currently. As box tree events are ignored, subsequent changes to the
+tree will not result in updated layout computations -- this might produce weird
+effects, so an option might be to forcibly relayout the entire tree on receipt
+of box tree change events received after the initial layout has been performed.
+This would not be substantially different from the existing reformatting on
+viewport dimension changes, and similarly heavyweight]
+
+The box tree manager needs to know when any of the various inputs that
+determine the shape of the box tree changes. These inputs comprise:
+
+  1. Style changes
+  2. DOM changes
+  3. Dynamic pseudo classes
+  4. Other non-DOM changes (predominantly Media Queries)
+
+The following sections consider the each of these inputs and attempts to scope
+out the impact of changes made to them.
+
+
+Style changes
+-------------
+
+Style information can change as the source document is parsed and as external
+stylesheets are fetched. Script may also modify style information via the CSS
+Object Model or simply injecting its own style attribute values into Elements.
+Changes to any of this information has the potential to cause wide-ranging
+ripples across the box tree structure.
+
+
+DOM changes
+-----------
+
+Given CSS 3 selectors and combinators, the impact of DOM changes is thus:
+
+  1. Adding a new Element node:
+       Selection must be re-run for all children of the new node's parent
+       and their descendants (i.e. all trees derived from the new node and
+       its siblings).
+       [XXX: is this correct?] If it is known that neither the :nth-last-child()/:nth-last-of-type()
+       pseudo-classes nor the sibling combinators are in use, the selection
+       re-run can be limited to the preceding siblings and the new node (and
+       their descendants).
+  2. Removing a new Element node:
+       Selection must be re-run for all children of the node's former parent
+       and their descendants (i.e. all trees derived from the node's siblings)
+  3. Moving an Element node:
+       This is effectively a removal (see: 2) followed by an addition (see: 1)
+       There is an optimisation to be had if the node is attached to one of
+       its ancestors: in that case, selection need not be re-run on removal
+       (as all of the affected nodes will be in a subtree of the node's
+       siblings on re-insertion).
+  4. Addition/Removal/Modification of an Element node's Attributes:
+       Selection must be re-run for all children of the Element node's parent
+       and their descendants (i.e. all trees derived from the node and its
+       siblings).
+
+
+Dynamic pseudo classes
+----------------------
+
+These require dynamic re-selection based on user activity. The most
+aggressive of which is :hover (as, in theory, causes changes whenever the
+user moves the mouse). So this probably requires the presence of some
+debouncing logic to avoid excessive reselection every time the mouse
+pointer moves 1px in any direction.
+
+The set of affected nodes is as for node addition (where the directly
+affected node serves as the added node).
+
+
+Other Non-DOM changes
+---------------------
+
+Media queries will require re-selection to happen whenever any of the
+queries properties (e.g. viewport dimension) changes. The impact in this
+case, however, is completely unconstrained -- potentially the entire document
+tree may require reselection.
+
+
+
+Change detection
+----------------
+
+In general we want, wherever possible, to minimise the amount of work performed
+to make the box tree reflect reality. This will be achieved through aggressive
+filtering out of unnecessary work and reuse of existing results where possible.
+
+The following sections consider change detection for each of the information
+sources.
+
+
+Detecting selection context changes
+-----------------------------------
+
+Style selection for a node is performed using a selection context
+(simplistically: an ordered list of stylesheets). If a suitable hashing
+scheme can be devised such that we can detect:
+
+  a. changes to the contents of a stylesheet (e.g. as a result of rules
+     or properties being added/removed/changed via the CSS Object Model)
+  b. addition/removal/reordering of stylesheets within a selection context
+
+and we record the aggregation of this information as a single hash value
+within the selection context and also record this hash value alongside the
+computed style for a node, then it becomes trivial to compare the recorded
+value with the live value within the selection context to determine if there
+is any need to do any work.
+
+If work is necessary, and assuming no ability to determine the differences
+between the prior and current set of input styles, a change to the selection
+context effectively invalidates the computed styles for the entire tree. This
+may require further optimisation, however.
+
+
+Detecting DOM changes
+---------------------
+
+Changes to a given Element node that might affect style selection rules are:
+
+  1. The Element's QName
+  2. The Attributes associated with the Element
+
+Assuming a suitable hashing scheme for this information exists, then we can
+compute a hash for the Element whenever any of these items change. This
+"Node Hash" value is stored on the Element itself.
+
+As described above, the position of a node within the DOM also affects the set
+of selection rules that apply to it. Specifically, there are two sets of
+relevant information:
+
+  a. the chain of ancestor nodes up to the document root (and details of any
+     attributes attached to them) 
+  b. the ordered set of children of a node's parent (and details of any
+     attributes attached to them) -- i.e. the node and its siblings
+
+If a suitable hashing scheme for an ordered list of Node Hashes (the
+"Positional Node Hash") can be devised then, on insertion of a node into the
+DOM we can compute:
+
+  1. The hash of the parent node's children, including the inserted node
+     (the "Children Hash")
+  2. The parent node's (if any -- we may be the document root Element)
+     ancestor chain hash plus the hash of the inserted node (the "Ancestor
+     Chain Hash")
+  3. Recursively, the Ancestor Chain Hash of the inserted node's descendants
+     (taking the inserted node as the initial parent and applying (2) to the
+     children, and updating the parent as we recurse down the tree).
+
+The Children Hash is stored on the inserted node's parent.
+The Ancestor Chain Hash is stored on the inserted node itself.
+
+Note that the positional hashing scheme MUST take the Element order into
+account.
+
+On removal of a node from the DOM we must compute:
+
+  1. The (former) parent node's Children Hash, excluding the removed
+     node.
+  2. An invalidation of the stored Ancestor Chain Hash values on the subtree
+     rooted at the removed node (the Children Hashes are unaffected until
+     nodes within the subtree are moved or altered)
+
+As for insertion, the Children Hash is stored on the former parent of the
+removed node.
+
+If, at the point of selection, we record alongside the computed style for the
+target element:
+
+  a. the target Element's Node Hash
+  b. the target Element's Ancestor Chain Hash
+  c. the target Element's parent node's Children Hash
+
+then, when asked to reselect style information for the target node we can
+compare the recorded values with those found on the live DOM tree to determine
+if anything has changed. [Implementation Note: we can save storage space by
+combining the three separate hash values here into a single value by treating
+them as a list of Node Hashes and feeding them to the Positional Node Hash
+function].
+
+
+Detecting changes to pseudo classes
+-----------------------------------
+
+Changes to structural pseudo classes should fall out of the generic DOM change
+detection described above: the DOM tree will have to change for these to do so.
+
+Dynamic pseudo classes, however, are a right pain, particularly in the case
+where you have rules containing selectors that include combinators in
+conjunction with pseudo classes. In these cases, the pseudo class might become
+engaged on any other element in the tree (be that ancestral or siblings, or
+both) surrounding the target element. Thus, there's no trivial way to
+pre-compute an answer and test against it efficiently.
+
+Consider something like this:
+
+div:first-child + :hover wibble :last-child > foo { ... }
+
+This will match a "foo" element whose parent is the last child of "foo"'s
+grandparent and "foo"'s parent has an ancestor element, "wibble" and "wibble"
+has an ancestor element that the user is hovering over and that ancestor
+element is immediately preceded by a "div" that is the first child of their
+parent. If the user isn't hovering over the intermediate ancestor, this rule
+will not match, regardless of the shape of the document tree.
+
+To make matters even more involved, the user may be considered to be hovering
+over the intermediate ancestor as a result of hovering over some other
+descendant of that ancestor. Also, because any ancestor of "wibble" with a
+preceding first child "div" will do, the identity of that ancestor could
+equally well change but the rule still match.
+
+Perhaps, therefore, it becomes necessary to gather the set of nodes for which
+each dynamic pseudo class is active and record this on the document element.
+Then, for each subsequent selection, gather the set of nodes to which these
+pseudo classes apply at that time. This gives two sets:
+
+  a. The previous set of nodes for which each dynamic pseudo class was active
+  b. The current set of nodes for which each dynamic pseudo class is active
+
+The disjunctive union of these two sets produces a set of nodes for which the
+active state of each dynamic pseudo class has changed between selections. Any
+descendant of any node in this set, or of any sibling of any node in this set,
+will require reselection.
+
+The current set of nodes for which each dynamic pseudo class is active will be
+recorded on the document element each time. [Note: it may be possible to
+minimise the set sizes by taking account of the rules involving the relevant
+pseudo class -- in the extreme case, no rules use the relevant pseudo class and
+so the set will always be empty].
+
+
+Detecting other non-DOM changes
+-------------------------------
+
+Media Queries Level 4 permits testing against a variety of mostly-static
+properties of the rendering device. Some properties may change dynamically
+(e.g. viewport width/height when the window is resized). Assuming that all
+property values are always provided and they do not change regularly, the
+simple approach would be to hash the information provided (i.e. property
+names and values) and store the hash alongside computed styles. If the
+hash value changes, then reselection must occur.
+
+If the hash value changes, a more granular additional test would be to apply
+the input properties to all known media queries and cache the results, thus
+ensuring that range-based properties continue to match until they don't even
+if there are slight changes to their declared values. The assumption is that
+this matching will be performant (if it is not, more intelligence is likely
+required).
+
+
+Construction nuances
+--------------------
+
+Avoiding repetitious selection during document construction (assuming no
+scripting causing DOM changes) would be desireable. Given the rules above,
+performing selection for the Element node children of a node is best done
+after the last child of the parent has been added to the document (i.e. when
+the parser encounters the parent Element's closing tag in well-formed
+document source).
+
+This may, however, be difficult to detect reliably from the DOM event stream
+(where only node insertion/removal events are emitted). In a well-formed
+document, we know that a node's subtree is complete once either:
+
+  a) a subsequent sibling is inserted into the node's parent; or
+  b) a subsequent relation is inserted into one of the node's ancestors
+
+In the case of the document root node, the completion of the parse is the
+relevant point (as, until then, children may be changing).
+
+Where the source document is not well-formed (i.e. the likes of the HTML5
+adoption agency are in play), it is possible for nodes to be moved around
+the tree or inserted in unlikely locations in the first place. Where this
+happens, it will be difficult to avoid repetitious selection in a reliable
+manner.
+
+In either case, if repetitious selection is avoided at all, the box tree
+will not be complete until the entire document parse has ended (and the
+event-based box tree builder must take great care to ensure the tree is
+in normal form at all times).
+
+Assuming a well-formed input, all stylesheet references and inline styles
+should be known when the Body Element is inserted into the document. There
+is no point attempting to build any part of the box tree until all the style
+information is available, so waiting until all of the external stylesheets
+have been fetched is probably sensible (perhaps with some timeout to avoid
+waiting forever -- if style information arrives late, then too bad, you get
+to enjoy a load of repetitious selection).
+
+
+Migration considerations
+------------------------
+
+The existing box tree structure conflates a variety of things. Specifically,
+the box tree is not "just" a structure containing nodes to be laid out but it
+also contains large swathes of information that is already stored in the DOM,
+and also pieces of information that have no bearing on how the document is
+laid out or displayed (e.g. form gadgets, which really belong on the DOM, and
+object parameters).
+
+Additionally, there are special-case box types for floated boxes (even using
+different types to distinguish between left and right floated boxes),
+linebreaks, and flex-layout boxes. There are also custom INLINE_CONTAINER
+boxes (which serve as a transparent container for INLINE boxes when the
+containing block only contains INLINE children, but act as a BLOCK box when
+the containing block has both BLOCK and INLINE children). There's also the
+magical INLINE_END box type which represents the far end of a fragmented
+INLINE box.
+
+Retaining the myriad box types (including the special cases) is possible, but
+care will need to be taken to ensure that the box tree remains in normal form
+as and when the type of a box changes (i.e. because the display or float
+property values change).
+
+Boxes also contain various pieces of information created by the layout
+calculator and stashed away for future use. Some generic mechanism to permit
+the layout calculator to associate state with a box is is probably needed
+(with such information being invalidated whenever the relevant section of the
+tree changes).
+
+There is some magic handling of trailing space characters in text elements
+(simplistically: they're flagged on the preceding text box). This was probably
+an optimisation at the time (as the box structure is relatively large), but
+makes many things more complex. This optimisation should be removed entirely
+and, instead, the boxes should reference the underlying text data attached to
+the source DOM nodes (Note: some consideration needs to be given to whitespace
+squashing here, to ensure that continues to happen in a sensible way,
+preferably without duplicating the entire textual contents of the DOM into the
+box tree).
+
+Ideally, then, the box tree contents will be reduced to solely the information
+needed to lay the document out and render it. Where possible, anything that is
+already stored on the DOM should not be duplicated (as it is easy to obtain the
+corresponding DOM node from the box and then query that).
+
+It would be nice to retire talloc, too, as object lifetimes are now
+well-defined.
+
+
+Outwith the HTML content handler, there are several parts of the code that
+expect to be able to access box objects and their contents:
+
+  1. iframe handling
+
+     This involves unpleasant collusion between the HTML content handler and
+     the desktop UI. This layering violation should be cleaned up by
+     introducing a proper orthogonal interface (if needed, or something else,
+     if not). The public "html_redraw_a_box" API should die with it.
+
+  2. save as text
+
+     This is a similar layering violation -- the code is simply in the wrong
+     place. It should be moved down into the HTML content handler and the
+     higher level code should simply dispatch the operation through the content
+     system.
+
+There are also the following things that grub around inside the DOM to fish
+out the box pointer:
+
+  1. The JavaScript Canvas binding
+
+     This is done so it can then call html__redraw_a_box, which is an API
+     private to the HTML content implementation. Bad Daniel, no biscuit.
+
+     The fix here is probably to have the binding fire a "redraw needed" event
+     at the canvas dom_node (which it already knows) and for that to be caught
+     and handled by the HTML content handler itself.
+
+Additionally there are a few places that leak box pointers through APIs:
+
+  1. The content_html_object struct contains the box pointer
+
+     This is used by:
+
+       a. save complete
+
+          This simply checks that the pointer is non-NULL to determine whether
+          to save the corresponding content for the object. Like save as text
+          (described above), this arises as a result of a layering violation.
+          The implementation should be pushed down into the HTML content
+          handler and the higher level code should simply dispatch the
+          operation through the content system. (This would also permit
+          retirement of the similarly anachronistic html_get_document API).
+
+       b. reload
+
+          This cares not about the box pointer, but does process the objects to
+          invalidate their caching status. Again, a layering violation: push
+          the implementation down and invoke it via the content system.
+
+  2. The textsearch_bounds content interface accepts box pointers (as does
+     content_textsearch_add_match)
+
+     While this is internal to the content infrastructure it would be better
+     all round for the exposure of box pointers here to go away and be replaced
+     with something more orthogonal.
+
+There are also places where box pointers might once have been used and no
+longer are, but where vestiges remain:
+
+  1. The core text selection object contains a pointless box pointer field
+     (it is initialised to NULL and never used)
+  2. The Windows frontend's browser_mouse object contains a pointless box
+     pointer field (it is never used).
+
+  These should just be cleaned up.
+
+
+Layout calculation
+------------------
+
+The layout calculators will be notified about changes to the box tree. Change
+events will report the containing block-boxes in which the alterations were
+made. This is analogous to the DOM's SubtreeModified event which is targetted
+at the parent Element containing the modified subtree. (TBD whether one event
+per containing block or one fat event, or some combination of the two -- in the
+situation where positioned and/or floated boxes are involved, changes to the
+in-flow box tree structure may result in *multiple* parent containing blocks
+being affected).
+
+The layout calculators will operate on the box tree to lay it out for a given
+viewport width (where possible, only needing to reflow the altered containing
+block contents, thus performing the minimal amount of work). The resulting
+layout information should be cached on each box tree element (potentially with
+some magic for inlines, as they get (de)fragmented depending upon available
+space).
+
+Once the position and dimensions of all boxes have been determined, the entire
+document should be rendered *unclipped* to produce the intermediate structure
+used for redraw. We expect this step to produce a stack of device-independent
+render operations (one stack level per layer).
+
+"Pictorally":
+
+  [canvas] -> [command, ...]
+  [     1] -> [command, ...]
+  [     2] -> [command, ...]
+  [     3] -> [command, ...]
+  [     4] -> [command, ...]
+
+where the document is then drawn layer-by-layer (canonically: starting at the
+canvas and moving down the stack, overdrawing each layer on top of what has
+been drawn before). [Note: the layers in this structure may not directly
+reflect the z-indexes specified in the source stylesheets in part as a result
+of the magical handling of elements which can create new stack levels -- see
+Appendix E of CSS2.1 for the gory details].
+
+With the exception of text plotting commands, the render operations are
+entirely independent of the originating document and box tree. Text commands
+will necessarily reference the source text data by holding references to the
+relevant DOM string data, and whatever metadata is needed to index into it.
+(As this data is referenced, if the DOM changes, the old text will continue
+to be rendered safely until the redraw stack is updated).
+
+To ensure that the document may be redrawn at any time, regardless of the
+underlying state of the DOM, box tree, or layout calculation, and to ensure
+that redraw output is consistent the redraw stack must be updated atomically
+(simplistically: build a new one, flip the old and new pointers, and destroy
+the old one; more optimised solutions are likely available).
+
+[Note: we omit the precise detail about how the layout calculation is perfomed
+as this is left for future work. The overall event flow and decoupling of
+layout from rendering is, however, important to record].
+
+
+Redraw
+------
+
+Redraw operates solely using the render stack. This is the point that clipping
+is applied (e.g. to skip over any commands that would render outside the clip
+boundary). Additionally, if output scaling is desired, it can be applied at
+this point, too (i.e. by transforming the device-independent render operations
+into device-dependent ones -- just apply a transformation matrix, right?).
+
+Multiple buffering, if desired, is left up to the plotter implementation
+provided by the client (as different frontends may wish to do things
+differently).
+
+[Note: again, the precise detail is omitted here].