This is a single-page compendium of all the pages found in the HTML original version. It provides an easier way to print than stepping through the individual pages.

This page is very large and pulls in many images.

This page has dysfunctional links.

Design Notes [PENDING : Obsolete documentation]

An easy to print version of this document is available.

The formal notation used to denote relationship between classes and objects is UML. The design is described and documented with the well known Gang of Four's system of pattern. Despite the number of source dealing with coding standard our main guidelines are rather simples. Our naming conventions are also quite conventional.

The system decomposition according to high level topics provides a good entry point to browse the specification.

Scanning the API documentation generated by Javadoc is another way to get a better view of the design, since we provide cross references between both documents.

* Main Design Guidelines

  • Program to an interface, not an implementation.
  • Favor object composition over class inheritance.

Keeping in mind the goal of providing an extensible framework this explain why interfaces prevail in the Java API. Ideally the design should be completely captured in interfaces. In particular, the classes should collaborate through interfaces, not concrete classes.

* Naming Conventions

Exception class:
Error class:
Constants and public class variables:
Private variables:
Reading accessor:
Type getValueName()
Writing accessor:
void setValueName(Type aValue)
boolean isPredicatTrueOrFalse()
Factory method:
Type newObject()

* High Level Topics


The API cross references give an immediate access to relevant interfaces and classes.

* Point

A point is a location with two coordinates.


* Rectangle

A rectangle is an area defined by it's top left corner, its width and its height.


* Dimension

A dimension is a rectangle with an entry point. Its upper left corner and its virtual exit point coordinates are given according to the entry point.


* Size

A size is a dimension with an explicit exit point.


* Various

* Position

A position is a point with respect to some origin which is either the father or the brother.

* Transformer

A transformer translate some coordinates according to its origin.

* API Cross References

Box Structure

The API cross references give an immediate access to relevant interfaces and classes.

* Box Structure

We make no distinction between composite objects and leaves. The glyph concept is a key one as it acts as the fundation of the composite structure. A node of the whole-part hierarchie knows about its parent and children. On the other hand leaves require a specific attention.

Here is our position on safety and transparency in composite.


* Atoms

Atoms are the leaves of the box structure. They do not have children and provide the basics of formatting and drawing tasks. As an application may use many of them, their storage cost is really sensitive. The naive design (unshared atom) is well suited for unusual terminals. When you think in term of key-word then you should use instead the DecoratedSharedAtom.

Here are some implementation issues relative to text drawing in java relevant to the design of atoms.


For common use, the shared atom is the only way to deal with big structure. To do that, each objet shares as much as possible of its state. The extrinsic part (origin, parent, ...) can't be share, but the intrinsic part (text and size) is stored in a flyweight. A flyweight registry maintain a list of all shared flyweight. We use reference counting to remove unused objects. When formatting a shared atom, first we ask the registry for the given value (string or character code) in the given font before allocating a new one.


* Updates

The box structure updates are made through the visit of a modification path. The path building visitor is used during the building stage. The mark stable/mark unstable operation allows the synchronization of the formatting and building threads. The path modification visitor is used during the interactive updates. This visitor computes the damaged area from removed or replaced boxes. The boxes are also tagged for incremental formatting.

The available Operations are :
  • inserting a new child
  • removing a child
  • replacing a child with a new glyph
  • marking a glyph as stable (i.e. ready for format)
  • marking a glyph as unstable (i.e.e not ready for format)

* Glyph

A glyph is an abstract notion representing all objects that we manage in a document. They know how to draw themselves, how much space they need, their relationship with their parent and children, how to interact with the user and how to manage exceptional situation.

Also a glyph knows how to manage its origin, its size, its format status its modification tag. As the size is a computed value, a glyph could manage a dependent (i.e. an object that needs to be notified when the size changes) and provides access to the current size value, to the accurate value (eager value) or lazy value (accurate value if there is no previous old value).


The main point is to maintain the components as small as possible since each attached information could have a major impact on derived classes. Heavy used concrete classes likes atoms share extrinsic information like size and datas.

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Root Glyph

The root glyph is specific in that it holds a reference to the facade.

* Change Graphical Context

The attributes attached to a change graphical context are inherited by all subsequent children. Resources specification with a style is preferable to the use of an anonymous way with explicit font and color. When drawing the previous graphical context is saved in a context memento.


* Horizontal

An horizontal arranges its children in horizontal mode. The space between consecutive element is given by the interword. The alignement is made between the exit point and the entry point of two consecutive elements. The only formatting action it knows on its own is reducing the interword.

Here are some implementation issues relative to optimization of such basic combinator.


* Vertical

A vertical arranges its children in vertical mode. The space between consecutive lines is given by the interline. The indentation is a withdrawal applied to each element except the first. The only formatting action it knows on its own is reducing the indentation.

Here are some implementation issues relative to optimization of such basic combinator.


* Paragraph

A paragraph puts its elements in horizontal mode while there is enough room till the right margin. Next it switchs to a new line and so on. So it can be view as a vertical whose each element is an horizontal. In fact, we use for the implementation Line and Column which are some kind of horizontal and vertical. Their behaviour only differ when formatting as an overflow will trigger a new line action.

* Lighweight Component Adapter

A lightweight component adapter holds a reference to a java lightweight component. Its allows glyphs and java lightweight components to be mixed.

* Decorations

A decorated glyph holds a reference to its component. Its default behavior is to delegate all operations. Its main purpose is adding reponsibilities, as subclasses are free to add specific operations.

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Path

A path is a hierarchical data structure used to update box structure and selection path. The rank is the logical order of the node in the target (box structure or selection path). Each node may contain operations. These operations are used via a multiple dispatch scheme during path visiting. Linear path is just a lighter implementation used when we know the path is a simple one (for exemple, when generating pointing events).


* Path Visiting

Our path visiting scheme is a variation of the standard visitor design pattern. In fact, the multiple dispatch occurs between the operations of the modification path, the visitor and eventually the target (box structure or selection path), not directly between the path and the visitor. According to the context of use, we can update the selection path with a selection path visitor, or update the box structure. A path visitor incremental used in an interactive context compute the damaged area for an optimal refresh.

Here is a simple vision of the multiple dispatch occurring when visiting a modification path. We iterate in parallel through each hierarchical structure (boxes, selection path, modification path). For a given level, we iterate over the path operations and make them accept the current visitor. When the operation accepts, it callbacks the visitor with encoding the type of the operation in the method signature. For example, an InsertGlyph operation will callback the insertGlyph method of the visitor, whereas a shrink operation will callback the shrinkSelection method. A particular visitor may implement various behaviour for a given callback.

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Selection

A selection is defined by its color, its background and its priority level. We use the priority level to choose between multiple selections. A selection is associate to the box structure through a selection path.

Here is the reason for not using a font attribute.


* Selection Path

A selection path is a multiple path relative to the box structure. Each node may contain some selections.


* Updates

The updates are made throught the visit of a modification path. The PathSelectionVisitor used during interactive updates computes the damaged area. The available operations are :
  • extending a selection
  • shrinking a selection
  • inversing a selection (i.e. switching from select to unselect or vice versa)

* API Cross References

Resources Management

The API cross references give an immediate access to relevant interfaces and classes.

* Resource Factory

A resource factory declares an interface for creating each resource (font, color, style, graphical context). A concrete resource factory such for AWT implements the resources in a specific context.

Here is the reason to deal with resources through abstract factory.


* Font

Here is the reason for reifiying family and style.


* Color

Here is the reason for reifiying basic colors.


* Style

A style is the conjunction of font, foreground and background colors.


* Defered Resources

A defered resource allows reference to resources before we want or know how to allocate concrete one like fonts, colors or styles. As soon as the defered resource is loaded, there is no subsequent cost in speed or memory.A resource owner provides indirect access to the resource factory and write accessor to assign the concrete resource.

A defered resource acts like a kind of lazy proxy. The allocation process occurs the first time the concrete resource is needed. Here is the reason we do not use proxy.

* International Resources

We use the standard java.util.ResourceBundle to manage locale-specific objects, like messages.

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Draw

A drawable element knows how to draw itself on a graphical context with or without active selection. The box coordinates are relative to the given transformation and the drawing area is restricted to a refresh zone.

Efficiency explains the presence of method signature with or without selection, as in most cases the selection path will be very light. The "draw clean" methods address problems relative to multi-threading. We do not talk of the only (temporary ?!) cost of synchonized code in current java implementation, but also of the cost bind to design. For example, there is no need to check every child before drawing it, if we already know that the father is clean (i.e. formatted). We could also draw a cleaned and ordered combinator (like vertical) with a dichotomy algorithm relative to the refresh area.


* Graphical Context

A graphical context is an area on which a drawable component could draw itself. The current font, color and background are used when drawing and formatting. The current resources are masked by active selections and decorating boxes. We use the priority level of the selection to choose between multiple selections. A selection prevail on a Decoration. We save and restore the current resources within a context memento.
The concrete implementation for AWT provides display operations without flash by the adoption of a classical double buffer

Here is the reason to reify the graphical context.
Here is the reason we draw array of bytes instead of simple strings.

A graphical context carrys also some operations used for Thread Synchronization. The graphical context is indeed a pivot used by both threads when they are working at the box level. So for example, when the draw thread (respectively the format thread) is waiting for the advance of the format thread (respectively the build thread) for a given box, it is natural to use the graphical context to notify of some advance. Without this protocol we will be forced to go through the box structure from parent to parent, until we reach the root and get the Facade and its other pivot : the notifying thread state. These methods are typical guarded methods awaiting that their condition holds.

* Context Memento

A context memento provides a convenient way to save and restore the state of a graphical context (i.e. current font, color and background).


* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Font Metrics

We use font metrics to compute the size of atoms for a given graphical context. As the rendering of a font is dependent of the context font metric are cached in it.

The measures are given according to the baseline. The ascent is the difference between the baseline and the top. The descent is the difference between the baseline and the bottom. The width give the size but may differ from the drawing area as for some fonts characters may overflow.

Here is the reason to manage array of byte instead of strings or chars.

* Distance

A distance is a value whose evaluation returns the available space till the right margin. There is two kinds of distances : immediate distance which is given and lazy distance which is computed according to previous results. For lazy distance dwe can get the accurate (eager) value or the last value computed. A distance knows if there is sufficient place to contain a given dimension. While formatting we maintain a link to the associated glyph, a link to the decalage produced by the children of the box and a reference to the distance of the father. The dependent associated to the value is a pointer to the object that needs to be evaluated after each change.


* Decalage

A decalage is a value whose evaluation returns the space consume by the children of a glyph according to their father. There is two kind of decalages : decalage to a father and decalages to a brother. As decalages are lazy values we can get the accurate (eager) value or the last value computed. While formatting we maintain a link to the father, and for all non first children a reference to the previous brother. The dependent associated to the value is a pointer to the object that needs to be evaluated after each change.


* Choosing and Executing a Formatting Action

While formatting we use an alternative structure to keep track of the current proposed formatting action and box location. When the algorithm uses the decalage history to propose another action, first we check that the action is complient with the glyph, next we choose the action whose is better than the other. Currently, the available actions are :

  • reducing the interword,
  • reducing the indentation,
  • shrinking a glyph,
  • shrinking some children of a glyph,
  • breaking a line,
  • doing nothing.


* Formatting Algorithm

A box knows how to compute its size. As this information will be computed in different context (i.e. interactive/ batch mode, incremental or not), we use functors to customize the default behavior. This value is a computed one and allow lazy evaluation or memo function. Dependent objects will be notified when the value changed. Before we can compute the size we must format the box, i.e. determine how to arrange the various children according to the current font metric and within the available space given by the distance. Beside computing distance and decalage, we must provide alternatives that the formatting algorithm will try when the current choice failled. A particular box may or not be complient with a format action and if true implements the associated action.


The standard algorithm for atoms is to check after the placement that the distance is still sufficient.

  public final void format2D( ... ) {
      _flyWeight = _flyWeight.format2D(aFontMetric,aDistance);

For combinators we update the distance structure when going down to the lower level, going to the next brother or going up to the upper level. Before iterating on a child we check before that the space is still sufficient. Finally, when all the children have been formatted we compute the size.

  public final void format2D( ... ) {
      DistanceInterface theNewDistance = aDistance.lowerLevel(this);
      GlyphInterface theCurrentSon = null;
      while ( theRank < numberOfChildren() ) {
	    theCurrentSon = getChild(theRank);

In the following example, we show the evolution of the distance structure. A new distance with a reference to the older is created when we go to the lower level. This distance is updated when we go through the successive brothers. Finally, the distance is destroyed when we go back to the upper level. The dependent relationship shows how an update must be propagated along the various elements.


* Algorithm Customization

As we use the same generic formatting algorithm in different context, functors provide the basis for customization.

  • In interactive mode, the StrategySetOrigin.INCREMENTAL save the old origin before storing the new value. This information will be use to compute the optimal refresh area.
  • In interactive mode, the StrategySetSize.INCREMENTAL save the old dimension before storing the new value. This information will be use to compute the optimal refresh area.
  • When building a big box structure with parallel display the StrategyReadyToFormat.UNSAFE will test that the box is stable before trying to format.
  • When building a big box structure with parallel display the StrategyImproveSizeEstimation.ACTIVE will trigger regular formatting of the current box structure to allow early display.

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Value

We reify the value notion in order to manage easily chain of computations involving distances, decalages and sizes. We distinguish between immediate value who just contains an immediate value and Computed Value who knows how to update themselves. Computed value acts also as lazy evaluation and memo function as we could trust or not a previous value and differ the evaluation until we must use the result. A dependent (i.e. a computed value) can be attached to a value and be nofified when the value changes. The notification could be an eager one or not. Since, the result of the evaluation is an integer for distances/ decalages and a dimension in the case of sizes we can't provide an uniform interface to access the result.


* Modification

To be incremental, we must minimize the refresh area and the (re)formatting cost. When updating the box structure or the selections we first compute the damaged (hear the removed/replaced elements) area while visiting the path. Next, we use the modification status to keep track of movements in the boxes after formatting. In interactive mode, before we reset the origin or the size we save the old value. As soon as the box structure is cleaned we go through the tree from the top along modified nodes. When we reach a modified node, we update the refresh zone according to the new and old values (we must draw the new location but also clear the old one).

At the time, the incremental formatting is rather simple. First, we use the format status to distinguish among dirty glyphs and new one. Next, when updating the box structure we mark touched glyph from parent to parent. Then we use particular property of combinators to avoid a whole reformat. For example, there is no need to reformat the children of an horizontal until we reach the first modified son. For a vertical we just have to reformat dirty glyph since the old ones will still have the same space. The update operations (insert glyph, remove glyph, replace glyph of the path modification visitor call the markAllBranchDirty who calls the sonModified method. Each combinator is free to implement in this method a particular behavior, i.e. mark boxes needing reformat according to its particular semantic.

* Path Visiting

When updating box structure or selections in interactive mode, we use a special visitor which compute the damaged area for an optimal refresh before we lose the size or origin information. We compute the intersection of the volatile size with the visible area and consolidate the result with the current damaged area.


* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Guarded Methods and Thread Conditions

Guarded methods are those that block if the target object is not in a state in which the associated actions can be executed, later proceeding when conditions change. This is not a busy-wait loop, so all methods that cause relevant state changes must provide notifications to wake up waiting threads.


Thread conditions encapsulate the waits and notifications used in guarded methods.


A typical guarded method implementation looks like :

  public void executeWhenConditionHold() {
    synchronized ( _condition ) {
      synchronized ( this ) {
	if ( conditionHold() ) {
	  // do actions
    // notify relevant state change

* Notifying Thread State

Notifying thread state is a concept for tracking and notifying about thread state changes. Its main use is to express conditions used in guarded methods. A state knows about its current thread status (drawing, formatting, building), the actions that could be initiated (start action),those that could be stopped (end action), and the resulting new state. The notifier encapsulates the state and awake the observer on relevant state changes (i.e. after end action).


Currently, we have adopt the main following rules (these constraints are dictate by the synchronization of the threads) :

  • We can not initiate an update of the glyphs when there is only drawing or formatting operations in background.
  • We can not initiate a formatting as long as the current drawing operation is not done.
  • There is two special states:
    • An invalid one where we fall after a bad transition. For the moment, the only purpose of this state is in reporting a fatal error. But it could be used in close futur as a mean for error recovery (i.e. resynchronization of faultly tasks).
    • A busy one which is virtual, as we only need to hold on the lock in the inactive state.

These rules are reflect by the automata:


* Thread

A thread is a thread of execution in a program. We have a thread for each basic task, i.e. building, formatting and drawing.Each thread has a condition describing its right state. The notifying thread state wakes up the threads after each relevant transition.

The following template method describes the activation scheme :
  public final void run() {
    synchronized ( _condition ) {
      while ( true ) {
	if ( isInRightState() ) {
	else {

* Thread Synchronization

The thread launching and awakening are synchronized throught using the notifying thread state at the task level. The format status is used at glyph level when a task must wait for the advance of another. Typically, the draw thread will wait for advance of the format thread when he finds a dirty glyph. The format thread will wait for advance of the build thread when he finds an unstable glyph. The proceed status is used when building an huge box structure and allows intermediate drawing, when we know that a particular box will not changed (sounds to us like "Netscape Effect"). The new status is a kind of dirty status introduced just for incrementality.


The next diagram shows how the depth first search from left to right used by the threads introduce constraints in synchronization. This scheme also explains some forbidden state transitions in the previous automata, since each thread assumes from the previous no backtrack in the done work. For example, when a build cycle is done we must wait for the end of the current drawing and formatting actions before a new build cycle could be initiate.


* Intermediate Drawing

When we are building the global box structure in batch mode (by opposition to interactive updates) we want to give the user a first result as soon as possible. To do so, we check during formatting if the glyph and all ancestors are unconditionnal. If true, we know that we could compute an intermediate size and start drawing. As this process costs a lot and may involve many redundant computations, we first estimate the height of formatted children and notify advance only when a sufficient height is done. As soon as, a glyph is ready for an intermediate drawing it is marked with proceed status. For the moment, only vertical, change graphical context and decorated glyph of which the component is unconditionnal are unconditionnal. For efficiency purpose, we are not concerned with neither atom nor horizontal.


* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* API Cross References

Exceptions Management

The API cross references give an immediate access to relevant interfaces and classes.

* Errors

An error indicates serious problems that an application should not try to catch.

* Exceptions

An exception indicates problems that an application might want to catch.

* Error Handler

An error handler implements a chain of responsibility to deal with bug report and warning. Each member of the chain knows how to access its successor and how to handle a request. This scheme is a flexible way to adapt error management to a specific application. The default error handler reports bugs by throwing an error and writes warning on the standard error output stream. In the case of a broken chain of responsability, we delegate the request to the DefaultErrorHandler class variable.

Here is the reason we do not rely on exception to propagate errors.


* API Cross References

Code Reuse

The API cross references give an immediate access to relevant interfaces and classes.

* API Cross References

System Customization

The API cross references give an immediate access to relevant interfaces and classes.

* Global Constants

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* Debugging

* API Cross References


The API cross references give an immediate access to relevant interfaces and classes.

* API Cross References

Notes on Design

* Why Dealing with Resources through Abstract Factory ?

Because we must stay independent of AWT. For example, we could move to ASCII, Postscript, PDF or Java2D. In this case the colors, fonts and metrics will depend of the concrete implementation.

* Why Reifiying Codes ?

Because Java has no enum, encoding the enum as a class is the only solution to get strong typing.

* Why not Using a Proxy for Defered Resources ?

Because we don't want to pay the cost of delegation for such heavy used objects. When the resource is loaded there is no good reason to maintain the indirection.

* Why not Using Exceptions to Propagate Errors ?

Because exception specification is a real maintenance nightmare. A chain of responsability is more flexible and is sometimes the only solution. For exemple, in Java you can not cause an exception (different of ThreadDeath and InterruptedException) in another thread. So we need to set up explicit communication between the threads via a shared object.

* Trade-off Between Safety and Transparency in Composite

We opt for transparency and maximize the component interface. But the implementation of problematic operations on leaves raises an error. We prefer to bypass a programming style based on dynamic cast. We think that visitor and iterator patterns provide also a good way to deal with the whole-part hierarchie uniformly.

* Why not Providing a Font Attribute for Selection

Because this would involve a formatting cost for a very current and so sensitive operation (selecting text). In addition, we could mix this scheme with another one where the selections are first class objects of the box structure.

* Why Reifiying Graphical Context ?

We are using AWT for the current effort, but Java environment is still moving. Reifying the context is a provision to deal with the raise of a new library (java2D, swing, ...). This could also be an issue if we want to move to formatting of ASCII or Postscript files. We could also use double buffering or not with few modifications.

Implementation Issues

* Working with Text in AWT

After some code profiling and trace [Runtime.getRuntime().traceMethodCalls(true); and use of java_g] we notice in java 1.1.x many object allocation during a single drawString (mainly String to Vector/char conversion). Some tests with drawBytes raise problem under linux (drawBytes don't use the correct font).

* Cost of Synchronized Method

In the JDK interpreter, calling a synchronized method is typically 10 times slower than calling an unsynchronized method. With JIT compilers, this performance gap has increased to 50-100 time.

* Basic Combinator and Optimization

As basic combinators (Horizontal or Vertical) will provide the building block of more complex combinators, we must adopt a good trade-off between efficiency and maintainability. A rapid analysis of the context of use shows that vertical display/formatting is the true problem. Horizontal ineffiency is less sensitive as from ergonomic point of view a display should be complient with a standard screen.

Copyright ©1998 INRIA