http://www.inria.fr/croap/figue/index.html
|
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]
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
- Package:
- fr.inria.croap.lowercase
- Class:
- CapitalizedWithInternalWordsAlsoCapitalized
- Exception class:
- ClassNameEndsWithException
- Error class:
- ClassNameEndsWithError
- Interface:
- NameEndsWithInterface
- Constants and public class variables:
- UPPER_CASE_WITH_UNDERSCORES
- Private variables:
- _leadingUnderscoreFirstWordLowerCaseButInternalWordsCapitalized
- Method:
- firstWordLowerCaseButInternalWordsCapitalized()
- Reading accessor:
- Type getValueName()
- Writing accessor:
- void setValueName(Type aValue)
- Predicat:
- boolean isPredicatTrueOrFalse()
- Factory method:
- Type newObject()
High Level Topics
Geometry
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
- Interfaces:
- Classes:
- Exceptions:
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
- Interfaces:
- Classes:
- Exceptions:
Combinators
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
- Interfaces:
- Classes:
- Exceptions:
Paths
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.
.
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
- Interfaces:
- Classes:
- Exceptions:
Selections
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
- Interfaces:
- Classes:
- Exceptions:
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.
we do not use proxy.
International Resources
We use the standard java.util.ResourceBundle
to manage locale-specific objects, like messages.
API Cross References
- Interfaces:
- Classes:
- Exceptions:
Drawing
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.
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
- Interfaces:
- Classes:
- Exceptions:
Formatting
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.
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);
aDistance.checkAfter(this,anAlternative);
}
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);
theNewDistance.checkBefore(anAlternative);
aReadyToFormatStrategy.doAlgorithm(aContext,theCurrentSon);
theCurrentSon.format2D(...);
theNewDistance.newBrother(theCurrentSon);
theImproveSizeStrategyForChildren.doAlgorithm(...);
}
computeSize(...);
theNewDistance.upperLevel();
}
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
- Interfaces:
- Classes:
- Exceptions:
Incrementality
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).
,
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
- Interfaces:
- Classes:
- Exceptions:
Concurrency
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
break;
}
}
_condition.await();
}
// notify relevant state change
_condition.signal();
_otherCondition.signal();
...
}
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.
public final void run() {
synchronized ( _condition ) {
while ( true ) {
if ( isInRightState() ) {
execute();
}
else {
_condition.await();
}
}
}
}
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
- Interfaces:
- Classes:
- Exceptions:
Interaction
The API cross references
give an immediate access to relevant interfaces and classes.
API Cross References
- Interfaces:
- Classes:
- Exceptions:
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
- Interfaces:
- Classes:
- Exceptions:
Code Reuse
The API cross references
give an immediate access to relevant interfaces and classes.
API Cross References
- Interfaces:
- Classes:
- Exceptions:
System Customization
The API cross references
give an immediate access to relevant interfaces and classes.
Global Constants
API Cross References
- Interfaces:
- Classes:
- Exceptions:
Utilities
The API cross references
give an immediate access to relevant interfaces and classes.
Debugging
API Cross References
- Interfaces:
- Classes:
- Exceptions:
Various
The API cross references
give an immediate access to relevant interfaces and classes.
API Cross References
- Interfaces:
- Classes:
- Exceptions:
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 |