% -*- Mode: LaTeX; Package: CLIM-USER -*-

\chapter {Incremental Redisplay}
\label {incremental-redisplay}

Incremental Redisplay is a facility to allow you to change the output in an
output history (and hence, on the screen or other output device).  It allows you
to redisplay pieces of the existing output differently, under your control.

It is ``incremental'' in the sense that the system will try to minimize the
changes to the output device in order to convert the output to follow your
specification.

There are two different ways to do incremental redisplay.

\issue {SWM} {This whole chapter still needs serious work.}

\issue {SWM} {Prefer using parent/children terminology to superior/inferiors.}

The first is to call \cl{redisplay} on an output record.  This essentially tells
the system to start that output record over from scratch.  It compares the
results with the existing output and tries to do minimal redisplay.  The
\cl{updating-output} form allows you to assist the system by informing it that
entire branches of the output history are known not to have changed.
\cl{updating-output} also allows you to communicate the fact that a piece of the
output record hierarchy has moved.

\issue {DCPL} {What does ``moved'' mean?  Does it mean ``changed its sibling
ordering'' or can it also mean ``changed its ancestry''?  The former is a lot
easier (and perhaps cleaner and more intuitive) than the latter.  The whole
``move'' concept also points out that there are really three IDs (unique, cache
and position) but only two get documented and the third is not only behind the
scenes but very magical.}

\issue {SWM} {I think that the ``position id'' stuff should be flushed from the
spec, but implementations should not be forbidden from implementing it.  It is
very difficult to specify closely, and is altogether too magic, even though it
is useful.  This would also kill the last remaining strong reason for storing
transformations explicitly in output records.}

The second way to do incremental redisplay is to manually do the updates to the
output history, and then call \cl{inferior-output-record-changed} on an output
record.  This allows the system to propagate the changes up the output record
history hierarchy and allow parent output records to readjust themselves to
account for your changes.

Each is appropriate under different circumstances.  \cl{redisplay} is often
easier to code, and more useful in cases where there might be large changes
between two passes, or where you have little idea as to what the changes might
be.  \cl{inferior-output-record-changed} can be more efficient for small changes
at the bottom of the output record hierarchy, or in cases where you are well
informed as to the specific changes necessary and can help the system out.

The behavior of incremental redisplay can be modified or customized by replacing
the generic functions that make up the Incremental Redisplay protocol.


\section {Examples of Incremental Redisplay}

The usual technique of incremental redisplay is to use \cl{updating-output} to
inform CLIM what output has changed, and use \cl{redisplay} to recompute and
redisplay that output.

The outermost call to \cl{updating-output} identifies a program fragment that
produces incrementally redisplayable output.  A nested call to
\cl{updating-output} (that is, a call to \cl{updating-output} that occurs during
the execution of the body of the outermost \cl{updating-output} and specifies
the same stream) identifies an individually redisplayable piece of output, the
program fragment that produces that output, and the circumstances under which
that output needs to be redrawn.

The outermost call to \cl{updating-output} executes its body, producing the
initial version of the output, and returns an incremental redisplay record that
captures the body in a closure.  Each nested call to \cl{updating-output} stores
its \cl{:unique-id} and \cl{:cache-value} arguments and the portion of the
output produced by its body.

\cl{redisplay} takes an incremental redisplay record and executes the captured
body of \cl{updating-output} over again.  When a nested call to
\cl{updating-output} is executed during redisplay, \cl{updating-output} decides
whether the cached output can be reused or the output needs to be redrawn.  This
is controlled by the \cl{:cache-value} argument to \cl{updating-output}.  If its
value matches its previous value, the body would produce output identical to the
previous output and thus is unnecessary.  In this case the cached output is
reused and \cl{updating-output} does not execute its body.  If the cache value
does not match, the output needs to be redrawn, so \cl{updating-output} executes
its body and the new output drawn on the stream replaces the previous output.
The \cl{:cache-value} argument is only meaningful for nested calls to
\cl{updating-output}.

In order to compare the cache to the output record, two pieces of information
are necessary:

\begin{itemize}
\item An association between the output being done by the program and a
particular cache.  This is supplied in the \cl{:unique-id} option to
\cl{updating-output}.

\item A means of determining whether this particular cache is valid.  This is
the \cl{:cache-value} option to \cl{updating-output}.
\end{itemize}

Normally, the programmer would supply both options. The unique-id would be some
data structure associated with the corresponding part of output.  The cache
value would be something in that data structure that changes whenever the output
changes.

It is valid to give the \cl{:unique-id} and not the \cl{:cache-value}.  This is
done to identify a parent in the hierarchy.  By this means, the children
essentially get a more complex unique id when they are matched for output.  (In
other words, it is like using a telephone area code.)  The cache without a cache
value is never valid.  Its children always have to be checked.

It is also valid to give the \cl{:cache-value} and not the \cl{:unique-id}.  In
this case, unique ids are just assigned sequentially.  So, if output associated
with the same thing is done in the same order each time, it isn't necessary to
invent new unique ids for each piece.  This is especially true in the case of
children of a cache with a unique id and no cache value of its own.  In this
case, the parent marks the particular data structure, whose components can
change individually, and the children are always in the same order and properly
identified by their parent and the order in which they are output.

A unique id need not be unique across the entire redisplay, only among the
children of a given output cache; that is, among all possible (current and
additional) uses made of \cl{updating-output} that are dynamically (not
lexically) within another.

To make incremental redisplay maximally efficient, the programmer should attempt
to give as many caches with \cl{:cache-value} as possible.  For instance, if the
thing being redisplayed is a deeply nested tree, it is better to be able to know
when whole branches have not changed than to have to recurse to every single
leaf and check it.  So, if there is a modification tick in the leaves, it is
better to also have one in their parent of the leaves and propagate the
modification up when things change.  While the simpler approach works, it
requires CLIM to do more work than is necessary.

The following function illustrates the standard use of Incremental Redisplay:

\begin{verbatim}
(defun test (stream)
  (let* ((list (list 1 2 3 4 5))
         (record
           (updating-output (stream)
             (do* ((elements list (cdr elements))
                   (count 0 (1+ count)))
                  ((null elements))
               (let ((element (first elements)))
                 (updating-output (stream :unique-id count
                                          :cache-value element)
                   (format stream "Element ~D" element)
                   (terpri stream)))))))
    (sleep 10)
    (setf (nth 2 list) 17)
    (redisplay record stream)))
\end{verbatim}

When this function is run on a window, the initial display will look like:

\begin{verbatim}
  Element 1
  Element 2
  Element 3
  Element 4
  Element 5
\end{verbatim}

After the sleep has terminated, the display will look like:

\begin{verbatim}
  Element 1
  Element 2
  Element 17
  Element 4
  Element 5
\end{verbatim}

Incremental Redisplay takes care of ensuring that only the third line gets
erased and redisplayed.  In the case where items moved around (try the example
substituting

\begin{verbatim}
(setf list (sort list #'(lambda (x y)
                          (declare (ignore x y))
                          (zerop (random 2))))) 
\end{verbatim}
for the form after the call to \cl{sleep}), Incremental Redisplay would ensure
that the minimum amount of work would be done in updating the display, thereby
minimizing ``flashiness'' while providing a powerful user interface.

See the discussion of Application Building Tools elsewhere in this document for
examples of how to use Incremental Redisplay automatically within your
application.


\section {Standard Programmer Interface}

\Defmacro {updating-output} {(stream
                              \rest args
                              \key unique-id (id-test \#'\cl{eql})
                                   cache-value (cache-test \#'\cl{eql})
                                   copy-cache-value fixed-position all-new
                                   output-record record-type)
                             \body body}

Introduces a caching point for incremental redisplay.  If this is used outside
the dynamic scope of an incremental redisplay, it has no particular effect.
However, when incremental redisplay is occurring, the supplied \arg{cache-value}
is compared with the value stored in the cache identified by \arg{unique-id}.
If the values differ or the code in \arg{body} has not been run before, the code
in \arg{body} runs, and \arg{cache-value} is saved for next time.  If the cache
values are the same, the code in \arg{body} is not run, because the current
output is still valid.

The \arg{stream} argument is not evaluated, and must be a symbol that is bound to
an output recording stream.  If \arg{stream} is \cl{t}, \cl{*standard-output*} is
used.  \arg{body} may have zero or more declarations as its first forms.

\arg{unique-id} provides a means to uniquely identify the output done by
\arg{body}.  If \arg{unique-id} is not supplied, CLIM will generate one that is
guaranteed to be unique.  \arg{unique-id} may be any object as long as it is
unique with respect to the \arg{id-test} predicate among all such unique ids in
the current incremental redisplay.  \arg{id-test} is a function of two arguments
that is used for comparing unique ids; it has indefinite extent.

\arg{cache-value} is a value that remains constant if and only if the output
produced by body does not need to be recomputed.  If the cache value is not
supplied, CLIM will not use a cache for this piece of output.  \arg{cache-test}
is a function of two arguments that is used for comparing cache values; it has
indefinite extent.  If \arg{copy-cache-value} is \term{true}, then the supplied
cache value will be copied using \cl{copy-seq} before it is stored in the output
record.  The default for \arg{copy-cache-value} is \term{false}.

If \arg{fixed-position} is \term{true}, then the location of this output is
fixed relative to its parent output record.  When CLIM redisplays an output
record that has a fixed position, then if the contents have not changed, the
position of the output record will not change.  If the contents have changed,
CLIM assumes that the code will take care to preserve its position.  The default
for \arg{fixed-position} is \term{false}.

If \arg{all-new} is \term{true}, that indicates that all of the output done by
\arg{body} is new, and will never match output previously recorded.  The default
for \arg{all-new} is \term{false}.

\arg{record-type} specifies the class of output record to create.  The default
is \cl{standard-updating-output-record}.  This argument should only be supplied
by a programmer if there is a new class of output record that supports the
updating output record protocol.


\Defun {redisplay} {record stream}

This function simply calls \cl{redisplay-output-record} on the arguments
\arg{record} and \arg{stream}.

\Defgeneric {redisplay-output-record} {record stream \optional x y parent-x parent-y}

\issue {SWM} {The coordinate system stuff affected by the x/y and parent-x/y
arguments is entirely bogus.  My proposal to make ``stream relative''
coordinates for output records instead of ``parent relative'' coordinates will
eliminate this completely.}

\cl{(redisplay-output-record \arg{record} \arg{stream})} causes the output of
\arg{record} to be recomputed.  CLIM redisplays the changes ``incrementally'',
that is, it only displays those parts that have been changed. \arg{record} must
already be part of the output history of the \term{output recording stream}
\arg{stream}, although it can be anywhere inside the hierarchy.

The optional arguments can be used to specify where on the \arg{stream} the
output record should be redisplayed.  \arg{x} and \arg{y} represent where the
cursor should be, relative to (\cl{output-record-parent} record), before we
start redisplaying \arg{record}.  \arg{parent-x} and \arg{parent-y} can be
supplied to say: do the output as if the parent started at positions
\arg{parent-x} and \arg{parent-y} (which are in absolute coordinates).  The
default values for \arg{x} and \arg{y} are \cl{(output-record-start-position
\arg{record})}.  The default values for \arg{parent-x} and \arg{parent-y}
are

\begin{verbatim}
(convert-from-relative-to-absolute-coordinates 
  stream (output-record-parent record))
\end{verbatim}

\arg{record} will usually be an output record created by \cl{updating-output}.
If it is not, then \cl{redisplay-output-record} will be equivalent to
\cl{replay-output-record}.


\section {Incremental Redisplay Protocol}

\Defprotoclass {updating-output-record}

The protocol class corresponding to records that support incremental redisplay;
a subclass of \cl{output-record}.
\IfYouWantClass {an} {updating output record} {updating-output-record}

\Defun {updating-output-record-p} {object}

Returns \term{true} if \arg{object} is an \term{updating output record},
otherwise returns \term{false}.

\definitarg {:unique-id}
\definitarg {:id-test}
\definitarg {:cache-value}
\definitarg {:cache-test}
\Definitarg {:fixed-position}

All subclasses of \cl{updating-output-record} must handle these four initargs,
which are used to specify, respectively, the unique id and id test, cache value
and cache test, and the ``fixed position'' component of the output record.

\Defclass {standard-updating-output-record}

The instantiable class of output record that supports incremental redisplay.
This is a subclass of \cl{updating-output-record}.


\Defgeneric {output-record-unique-id} {record}

Returns the unique id associated with the updating output record \arg{record}.

\Defgeneric {output-record-cache-value} {record}

Returns the cache value associated with the updating output record \arg{record}.

\Defgeneric {output-record-fixed-position} {record}

Returns \term{true} if the updating output record \arg{record} is at a fixed
location on the output stream, otherwise returns \term{false}.  Output records
that are not at fixed location on the output stream will be moved by incremental
redisplay when any of their siblings adjust their size or position.

\Defgeneric {output-record-displayer} {record}

Returns the function that produces the output for this output record.  This is
the function that is called during redisplay to produce new output if the cache
value mismatches.

\Defgeneric {inferior-output-record-changed} {record child mode old-position old-extent stream
                                              \optional erases moves draws erase-overlapping move-overlapping
                                              \key check-overlapping}

\cl{inferior-output-record-changed} assumes that the output history already
reflects the changes made, but that no output (screen, or hardcopy, or ...) has
been done yet.  (Some) parent will (eventually) do the appropriate updates.
You must pass the ``differences list'' (output in the style of
\cl{compute-differences}) to \cl{inferior-output-record-changed}.  If you don't
know the optimized form of the differences, then you must call
\cl{compute-differences} before you update the output record history, and pass
the results to \cl{inferior-output-record-changed}.

\arg{mode} is one of \cl{:delete}, \cl{:add}, \cl{:change}, \cl{:move}, or
\cl{:none}

\arg{old-position} and \arg{old-extent} are where \arg{child} was before it
was moved.

This is the protocol that must be supported by any output records that wish to
be compatible with incremental redisplay.

{\sl Matching and automatic adjustment:}

\Defgeneric {match-output-records} {record \rest init-args}

Returns \term{true} if record matches the supplied init-args, otherwise returns
\term{false}.

\Defgeneric {find-inferior-output-record} {record use-old-elements record-type
                                           \rest init-args
                                           \key unique-id unique-id-test}

Finds a child of \arg{record} matching the \arg{record-type} and
\arg{init-args} supplied.  \arg{unique-id} and \arg{unique-id-test} are used to
match against the children as well.  \arg{use-old-elements} controls whether
the desired record is to be found in the previous (before redisplay) contents of
the record.

\Defgeneric {decache-inferior-output-record} {record child use-old-elements}

To be supplied.

\Defgeneric {output-record-contents-ok} {record}

To be supplied.

\Defgeneric {recompute-contents-ok} {record}

Compares the old (before redisplay) and new contents of \arg{record} to
determine whether or not this record changed in such a way so that the display
needs updating.

{\sl The following functions are called by} \cl{updating-output}.

\Defgeneric {cache-output-record} {record child unique-id}

\arg{record} stores \arg{child} such that it can be located later using \arg{unique-id}.

\Defgeneric {find-cached-output-record} {record use-old-elements record-type
                                        \rest init-args
                                        \key unique-id unique-id-test \allow}

Finds a previously cached child matching \arg{record-type}, \arg{init-args},
\arg{unique-id}, and \arg{unique-id-test}.  \arg{use-old-elements} controls
whether the desired record is to be found in the previous (before redisplay)
contents of the record.

{\sl The following functions are called by} \cl{redisplay-output-record}.

\Defgeneric {new-output-records} {record stream}

The contract of \cl{new-output-records} is to modify an output history to what
the record should look like now.  It must record all of the old positions in
old-extent, old-start-position, and old-elements.

It recurses down the descendents doing \cl{new-output-records} on each
child.

\cl{new-output-records} of an output record of type \cl{updating-output-record}
runs the displayer, which gives the behavior of incremental redisplay.  That is,
it reruns the code (getting hints from \cl{updating-output}) and figures out the
changes from there by comparing it to the old output history.

\Defgeneric {compute-differences} {record \optional check-overlapping
                                                    (offset-x \cl{0}) (offset-y \cl{0})
                                                    (old-offset-x \cl{0}) (old-offset-y \cl{0})} 

This operation compares the old and new versions of \arg{record} and returns the
differences as 5 multiple values.  The values returned are \arg{erases},
\arg{draws}, \arg{moves}, \arg{erase-overlapping}, and \arg{move-overlapping}.
Each is a list of lists of the form:

\begin{itemize}
\item \arg{erases} are lists of (record old-extent)
\item \arg{draws} are lists of (record old-extent)
\item \arg{moves} are lists of (record old-extent new-position)
\item \arg{erase-overlapping} is a list of (record old-extent)
\item \arg{move-overlapping}, is a list of (record extent new-position)
\end{itemize}

{\sl The following functions are called by} \cl{inferior-output-record-changed}.

\Defgeneric {augment-draw-set} {record}

To be supplied.

\Defgeneric {propagate-inferior-output-record-changes-p} {record child mode 
                                                          old-position old-extent}

\cl{propagate-inferior-output-record-changes-p} is a predicate which returns
\term{true} if the change made to the child will cause \arg{record} to be
redisplayed in any way.  Otherwise, it returns \term{false}.  \arg{mode} is one
of \cl{:delete}, \cl{:add}, \cl{:change}, \cl{:move}, or \cl{:none}.

\Defgeneric {propagate-output-record-changes} 
            {record child mode 
             \optional (old-child-position \cl{(output-record-old-start-position child)})
                       (old-child-extent \cl{(output-record-old-extent child)})
                       erases moves draws erase-overlapping move-overlapping check-overlapping}

To be supplied.

\section {Incremental Redisplay Stream Protocol}

\Defgeneric {stream-redisplayable-p} {stream}

Returns \term{true} for any stream that maintains an output history and supports
the incremental redisplay protocol, otherwise returns \term{false}.

\Defgeneric {incremental-redisplay} {stream position erases moves draws 
                                     erase-overlapping move-overlapping} 

\arg{erases}, \arg{moves}, \arg{draws}, \arg{erase-overlapping}, and
\arg{move-overlapping} are differences lists as returned by
\cl{compute-differences}.  

\cl{incremental-redisplay} can be called on any stream that can set the cursor
position and replace existing output.

\section {Random Comments}

Since we allow incremental redisplay to work on any output record,
\cl{updating-output} is just a hint.  It can tell us about two different kinds
of things: (1) whether things have changed at all and (2) what this new
output record corresponds to in the old hierarchy.

There are four ways to determine the output record in the current history that
\arg{body} corresponds to.  The first is if the programmer passes in
\cl{:output-record}.  The rest all rely on \cl{:unique-id} and \cl{:id-test}.
The tree of \cl{updating-output} defines a caching structure where mappings from
a unique-id to an output record are maintained.  If the programmer specifies an
output record $P$ with \cl{:parent-cache}, then we try to find a corresponding
output record with the matching unique-id in the cache belonging to $P$.  If
neither \cl{:output-record} nor \cl{:parent-cache} is provided, then we look for
the unique-id in the immediately dynamically enclosing \cl{updating-output}.
Finally, if all else fails, we use the unique-id to find the output record that
is an child of \cl{(output-recording-stream-output-record \arg{stream})}.

Alternatively, you can specify \cl{:all-new t}, which guarantees that nothing in
this output record (or in any of its descendants) will match anything on the
screen, so don't even bother trying.

Once we have a correspondence, we can use the cache-value and cache-test to
tell us whether this output record has changed.  If it hasn't, and it's on the
screen, we can just move the bits on the screen around.
