News feeds
Layout Algorithm Improvements for Web User Interfaces
- , ,
The algorithms used today to lay out documents on the Web are based primarily on the algorithms that have been used for millenia. The basic document layout algorithm involves placing content on a line until the line is full and then continuing to a new line until all the content has been placed. When this algorithm is used for horizontal scripts such as the Latin alphabet, the width of the content is an input and the height is an output, both for the layout algorithm as a whole and for the layout of parts of the content.
The algorithms used to lay out user interfaces of many computer applications are very different. Heights and widths are treated more symmetrically, and can be inputs or outputs as needed. Output dimensions are often derived from dimensions that are intrinsic to a part of the content, i.e., the dimensions of the text or other content.
Many Web pages contain document-like content inside of or adjacent to user-interface-like content. Today these Web pages are written using standards designed for document-like layout. With today's Web standards, creating pages with the height dependence or space distribution patterns typical of user interface layout often requires sacrificing some of the benefits of today's standards:
robustness under small to moderate variations in window size or font size (sometimes sacrificed by preventing such variation entirely), and
use of semantic markup and semantic ordering of markup, which can be important for accessibility.
The first step to building standards that provide features of user interface layout to the Web is to determine which features are needed.
Document Layout
Traditional document layout, as described above, is based on the algorithm of filling lines of an already-chosen width with text or other content and then moving to the next line, until all the content has been placed, yielding the final height. (I'll use terms like width and height as they are used for horizontal text, even though that makes the descriptions incorrect for vertical text. However, they are much easier to read than "inline progression dimension" and "block progression dimension".)
There are various additions to this algorithm used in traditional documents that do not change it fundamentally. These additions generally handle content that is more complex than simple text by dealing with it in the ways that are good for usability of printed documents. This does not imply that they are the most usable solution to the equivalent problem for documents displayed on a computer. Content is often split into pages; this means that the following line may appear at the top of the next page instead of immediately below the previous line. Sometimes a page, or part of a page, is likewise split into columns. Large objects, such as drawings, figures, tables, and photographs, are sometimes placed within the document. When this happens either the text stops above the figure and restarts below it, or it wraps around the figure. Sometimes the margins separating the edge of the paper from the edge of the text are varied, and sometimes borders are drawn around parts of text. All of these features, with the exception of columns, are handled well by well-established Web standards ([CSS1], [CSS2]), and the handling of columns is under development ([CSS3-MULTICOL]).
Web Extensions to Document Layout
Well-established Web standards ([HTML32], [CSS2]) also provide for the content of one of the above types of objects, tables, in a form other than raster images. But the traditional behavior of HTML tables actually represents slightly more than what was present in traditional document layout, in two ways.
First, tables provided some ability to do height-dependent layout, even sometimes with percentage heights, although some of that ability was not sanctioned by the official specifications. In other words, they provide limited ability to use heights as input rather than output. This capability has not been extended to features other than tables, and it is somewhat difficult to implement because it does not fit well with the rest of the algorithm.
Second, tables depend on intrinsic widths of content. In other words, the table layout algorithm, and similar algorithms used for floats and absolute positioning, depend on widths as output rather than input. Content to be placed in traditional document layout generally has two intrinsic widths. First, its preferred width is the widest width that it can fill. In the simplest case this is the width of the longest paragraph of text when laid out on a single line. Second, its minimum width is the narrowest width that it can fit in without overflow. In the simplest case this is the width of the longest word. A commonly used mathematical expression in determining final widths in algorithms that depend on intrinsic widths is max(W_{min}, min(W_{pref}, W_{avail})), where W_{avail} is the standard input width in document layout (the width of the page, viewport, or other container) and W_{min} and W_{pref} are these two widths that are the output of a pass of the layout algorithm that precedes the final layout.
Algorithms involving intrinsic widths are useful on the Web because they provide robustness in handling variation in font size, display size, and other conditions that authors might not have expected. Use of intrinsic widths in layout algorithms helps avoid overlap and/or overflow out of the viewport over wider variation of these conditions. (The table layout algorithm in particular is somewhat problematic, though, since it gives prevention of minor overlap precedence over prevention of major overflow of the viewport.) However, the flexibility and robustness provided by working only with intrinsic widths and with very limited use of heights as input is limited, and the types of layout that often have these problems might be achieved better using layout algorithms based less on traditional document layout.
User-Interface Layout
The layout of computer user interfaces is often based on significantly different algorithms. Application interfaces in windowing systems are often displayed at significantly varying sizes, and with different font sizes. Thus graphical applications like Web browsers, word processors, email clients, graphical debuggers, and music players design their interface to fit the space available. Typically this involves fixed-dimension content around the edges and more flexible content in the middle. Both the height and width of the toplevel window are input to the algorithm, but when multiple flexible pieces of content are present, their intrinsic sizes may also be input to the algorithm so that the available space can be distributed appropriately between them.
There are many existing systems for user interface layout. Some are part of the widget toolkits that come with major windowing systems (Windows, GTK+, Qt). Some are part of cross-platform widget toolkits that go on top of those (Java Swing, Mozilla XUL). I do not intend to compare those systems here, nor am I currently qualified to do so.
Other Layout on the Web
There is another class of layout systems used on the Web: those designed for animation and graphics where the author chooses all object positions rather than having a layout algorithm do so (with the possible exception of scaling the final result). These include CSS absolute and fixed positioning [CSS2] and Scalable Vector Graphics [SVG]. Such layout systems are powerful, but they are very blunt tools. It is difficult to use them in a way that adapts to variation in display size, font size, and other aspects of the user's environment. Since there is no algorithm to provide any such adaptation, the author is responsible for doing (or not doing) it all himself.
Gathering Requirements
Many major Web pages have significant pieces of content of a type that is more typically positioned using a layout system for user interface than using a traditional document layout algorithm.
Many Web authors work around the limitations of the existing document-oriented Web standards by doing all of the positioning themselves in at least one dimension (width) if not both. Pages designed this way respond very poorly to display size changes and (when both dimensions are fixed) font size changes. Sometimes such width allocations are done using percentages, which produces slightly better results for display size variation among large sizes, but still does not work well given large fonts or narrow displays, which cause the narrower pieces not to fit within their assigned percentages. Thus the limitations of the current layout algorithms on the Web harm the user experience.
Web authors who tend to try to produce user interface layouts that respond to display and font size changes the way user interfaces typically do tend to do so by misusing existing standards in extremely complex ways. For example, the commonly used sliding doors technique [SLIDING-DOORS] uses floats (which were designed so that text would wrap around them) to place pieces of content in a line with no wrapping text in sight. This type of layout can be achieved much more simply using the layout models common to many of the user interface toolkits. However, authors have to translate a concept of the layout behavior they want into a programming model that doesn't have a direct way to express that concept. This makes it harder to design Web pages than it should be, which increases Web authoring costs and reduces investment in other parts of authoring, such as improving content and user experience.
Web authors also often have to make tradeoffs between quality of markup and quality of layout. In particular, authors often need to either choose to reorder or add to their markup in a way that does not match the semantics or give up on trying to get the layout that they want with the correctly markup. For example, authors often have to split the user interface that goes around the edges of a Web page between the beginning and end of the markup, and sometimes even have to place parts of it in the middle. While techniques like one true layout [ONETRUELAYOUT] try to reduce these tradeoffs (although still generally sacrificing some quality of layout, in this case by using percentages), these techniques are extremely complex, fragile, and hard for authors to write. Authors should be able to get the layout concepts they want with the semantic markup that they choose without this complexity. Since layout systems that don't require the author to do all positioning depend on the content order when laying out the content, this requires that there be mechanisms for reordering the content before or when it reaches the layout algorithm.
These observations about the Web show two areas where Web standards could be improved to significant benefit to both users and authors: layout algorithms and content reordering. Discussions about standardization of user interface layout so far have not reached conclusions on which improvements are more important or on how closely improvements in the two areas should be related to each other. A number of questions are open:
How do the existing user interface layout algorithms differ in features, complexity of implementation, and ease of authoring, and what concepts from them should be part of Web standards?
Does the content reordering required to position semantic markup in appropriate areas of the screen need to be usable with all layout algorithms, or only with the user interface layout algorithm?
Where and how are user-interface and document layout algorithms required to interact? In particular, at boundaries where content laid out using one of the two algorithms contains content laid out using the other, which options are required among the possible ways that dimensions of the boundary rectangle could be determined by the inner algorithm, the outer algorithm, or some as-yet-unknown combination of the two?
Is the only important use case for interaction between document layout and user interface layout the placement of document layout inside of user-interface layout, or are there use cases that require placing user-interface layout inside of document layout? If there are such use cases, what requirements do they impose on size negotiation of the dimensions of the boundary rectangle?
Improvements in the layout algorithms available to Web authors could have significant benefits both for Web authors and Web users. More agreement on what improvements should be made and their relative priority could help lead to progress on providing a programming model for Web authors that corresponds more closely to the layout concepts that they are trying to achieve.
Bibliography
[CSS1] Lie, Håkon Wium, and Bert Bos. Cascading Style Sheets, level 1. 17 Dec 1996. URL: http://www.w3.org/TR/REC-CSS1-961217
[CSS2] Bos, Bert, Håkon Wium Lie, Chris Lilley, and Ian Jacobs. Cascading Style Sheets, level 2. 12 May 1998. URL: http://www.w3.org/TR/1998/REC-CSS2-19980512/
[CSS3-MULTICOL] Lie, Håkon Wium. CSS3 module: multi column layout. Working draft. URL: http://www.w3.org/TR/css3-multicol/
[HTML32] Raggett, Dave. HTML 3.2 Reference Specification. 14 Jan 1997. URL: http://www.w3.org/TR/REC-html32-19970114
[ONETRUELAYOUT] Robinson, Alex. In Search of the One True Layout. 21 Oct 2005. URL: http://www.positioniseverything.net/articles/onetruelayout/
[SLIDING-DOORS] Bowman, Douglas. Sliding Doors of CSS. 20 Oct 2003. URL: http://www.alistapart.com/articles/slidingdoors/ and Douglas Bowman. Sliding Doors of CSS, Part II. 30 Oct 2003. URL: http://www.alistapart.com/articles/slidingdoors2/
[SVG] Ferraiolo, Jon, 藤沢 淳 (FUJISAWA Jun), and Dean Jackson. Scalable Vector Graphics (SVG) 1.1 Specification. 14 Jan 2003. URL: http://www.w3.org/TR/2003/REC-SVG11-20030114/