
\chapter{The boxes produced by the typesetter}

\section{Introduction}

The {\TeXmacs} typesetter essentially translates a document
represented by a tree into a graphical box, which can either
be displayed on the screen or on a printer.
Contrary to a system like {\LaTeX}, the graphical box actually
contains much more information than is necessary for
a graphical rendering. Roughly speaking, this information
can be subdivided into the following categories:
\begin{itemize}
  \item Logical and physical bounding boxes.
  \item A method for graphical rendering.
  \item Miscellaneous typesetting information.
  \item Keeping track of the source subtree which led to box.
  \item Computing the positions of cursors and selections.
  \item Event handlers for dynamic content.
\end{itemize}

The logical bounding box is used by the typesetter to position
the box with respect to other boxes. A certain amount of other
information, such as the slant of the box, is also stored
for the typesetter. The physical bounding box encloses
the graphical representation of the box. This knowledge
is needed when partially redrawing a box in an efficient way.

In order to position the cursor or when making a selection,
it is necessary to have a correspondence between logical positions
in the source tree and physical positions in the typesetted boxes.
More precisely, boxes and their subboxes are logically organized
as a tree. Boxes provide routines to translate between paths
in the box tree and the source tree and to find the path
which is associated to a graphical point.

\section{The correspondence between a box and its source}

\subsection{Discussion of the problems being encountered}

In order to implement the correspondence between paths
in the source tree and the box tree, one has to face several
simultaneous difficulties:
\begin{enumerate}
  \item Due to line breaking, footnotes and macro expansions,
        the correspondence may be non straightforward.
  \item The correspondence has to be reasonably time and space efficient.
  \item Some boxes, such header and footers, or certain results
        of macro expansions, may not be ``accessible''.
        Although one should be able to find a reasonable
        cursor position when clicking on them,
        the contents of this box can not be edited directly.
  \item The correspondence has to be reasonably complete
        (see the next section).
\end{enumerate}

The first difficulty forces us to store a path in the source tree
along with any box. In order to save storage, this path is stored
in a reversed manner, so that common heads can be shared.
This common head sharing is also necessary to quickly change
the source locations when modifying the source tree,
for instance by inserting a new paragraph.

In order to cope with the third difficulty, the inverse path
may start with a negative number, which indicates that the box
can not directly be edited (we also say that the box is a decoration).
In this case, the tail of the inverse path corresponds to
a location in the source tree, where the cursor should be positioned
when clicking on the box. The negative number influences the way
in which this is done.

\subsection{The three kinds of paths}

More precisely, we have to deal with three kinds of paths
\begin{description}
  \item[Tree paths.]
    These paths correspond to paths in the source tree.
    Actually, the path minus its last item point to a subtree of
    the source tree. The last item gives a position in this subtree:
    if the subtree is a leaf, i.e. a string, it is a position in this string.
    Otherwise a zero indicates a position before the subtree and
    a one a position after the subtree.
  \item[Inverse paths.]
    These are just reverted tree paths (with shared tails),
    with an optional negative head. A negative head indicates
    that the tree path is not accessible, i.e. the corresponding
    subtree does not correspond to editable content.
    If the negative value is $-2$, $-3$ or $-4$,
    then a zero or one has to be put behind the tree path,
    depending on the value and the cursor position.
  \item[Box paths.]
    These paths correspond to logical paths in the box tree.
    Again, the path minus its last item point to a subbox of
    the main box, and the last item gives a position in this subtree:
    if the subbox corresponds to a text box it is a position in this string.
    Otherwise a zero indicates a position before the subbox and
    a one a position after it. In the case of side boxes,
    a two and a three may also indicate the position after
    the left script resp. before the right script.
\end{description}

\subsection{The conversion routines}

In order to implement the convertion between the three kinds
of paths, every box comes with a reference inverse path ĪipĪ
in the source tree. Composite boxes also come with
a left and a right inverse path ĪlipĪ resp. ĪripĪ,
which correspond to the left-most and right-most
accessible paths in its subboxes (if there are such subboxes).

The routine
\begin{verbatim}
    virtual path box_rep::find_tree_path (path bp)
\end{verbatim}
transforms a box path into a tree path. This routine
(which only uses ĪipĪ) is fast and has a linear time complexity
as a function of the lengths of the paths. The routine
\begin{verbatim}
    virtual path box_rep::find_box_path (path p)
\end{verbatim}
does the inverse conversion. Unfortunately, in the worst case,
it may be necessary to search for the matching tree path in all subboxes.
Nevertheless, in the best case, a dichotomic algorithm
(which uses ĪlipĪ and ĪripĪ), finds the right branch how to descend
in a logarithmic time. This algorithm also has a quadratic time
complexity as a function of the lengths of the paths,
because we frequently need to revert paths.

\section{The cursor and selections}

In order to fulfill the requirement of being a ``structured editor'',
{\TeXmacs} needs to provide a (reasonably) complete correspondance
between logical tree paths and physical cursor positions.
This yields an additional difficulty in the case of
``environment changes'', such as a change in font or color.
Indeed, when you are on the border of such a change,
it is not clear {\em a priori\/} which environement you are in.

In {\TeXmacs}, the cursor position therefore contains an $x$ and
a $y$ coordinate, as well as an additional infinitesimal $x$-coordinate,
called $\delta$. A change in environment is then represented by
a box with an infinitesimal width. Although the $\delta$-position
of the cursor is always zero when you select using the mouse,
it may be non zero when moving around using the cursor keys.
The linear time routine
\begin{verbatim}
    virtual path box_rep::find_box_path (SI x, SI y, SI delta)
\end{verbatim}
as a function of the length of the path
searches the box path which corresponds to a cursor position.
Inversily, the routine
\begin{verbatim}
    virtual cursor box_rep::find_cursor (box bp)
\end{verbatim}
yields a graphical representation for the cursor at a certain box path.
The cursor is given by its $x$, $y$ and $\delta$ coordinates and
a line segment relative to this origin, given by its extremities
$(x_1, y_1)$ and $(x_2, y_2)$.

In a similar way, the routine
\begin{verbatim}
    virtual selection box_rep::find_selection (box lbp, box rbp)
\end{verbatim}
computes the selection between two given box paths.
This selection comprises two delimiting tree paths and
a graphical representation in the form of a list of rectangles.
