% -*- 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.