50  PART 10: DATA STRUCTURES FOR BOXES AND THEIR FRIENDS  TEX82 §133

133. Data structures for boxes and their friends. From the computer’s standpoint, TEX’s chief mission is to create horizontal and vertical lists. We shall now investigate how the elements of these lists are represented internally as nodes in the dynamic memory.

A horizontal or vertical list is linked together by link fields in the first word of each node. Individual nodes represent boxes, glue, penalties, or special things like discretionary hyphens; because of this variety, some nodes are longer than others, and we must distinguish different kinds of nodes. We do this by putting a ‘type’ field in the first word, together with the link and an optional ‘subtype’.

define type(#) ≡ mem[#].hh.b0 { identifies what kind of node this is }

define subtype(#) ≡ mem[#].hh.b1 { secondary identification in some cases }

134. A char node, which represents a single character, is the most important kind of node because it accounts for the vast majority of all boxes. Special precautions are therefore taken to ensure that a char node does not take up much memory space. Every such node is one word long, and in fact it is identifiable by this property, since other kinds of nodes have at least two words, and they appear in mem locations less than hi mem min. This makes it possible to omit the type field in a char node, leaving us room for two bytes that identify a font and a character within that font.

Note that the format of a char node allows for up to 256 different fonts and up to 256 characters per font; but most implementations will probably limit the total number of fonts to fewer than 75 per job, and most fonts will stick to characters whose codes are less than 128 (since higher codes are more difficult to access on most keyboards).

Extensions of TEX intended for oriental languages will need even more than 256 × 256 possible characters, when we consider different sizes and styles of type. It is suggested that Chinese and Japanese fonts be handled by representing such characters in two consecutive char node entries: The first of these has font = font base, and its link points to the second; the second identifies the font and the character dimensions. The saving feature about oriental characters is that most of them have the same box dimensions. The character field of the first char node is a “charext ” that distinguishes between graphic symbols whose dimensions are identical for typesetting purposes. (See the manual.) Such an extension of TEX would not be difficult; further details are left to the reader.

In order to make sure that the character code fits in a quarterword, TEX adds the quantity min quarterword to the actual code.

Character nodes appear only in horizontal lists, never in vertical lists.

§135  TEX82  PART 10: DATA STRUCTURES FOR BOXES AND THEIR FRIENDS 51

define is char node(#) ≡ (# ≥ hi mem min) { does the argument point to a char node? } define font ≡ type { the font code in a char node } define character ≡ subtype { the character code in a char node } 135. An hlist node stands for a box that was made from a horizontal list. Each hlist node is seven words long, and contains the following fields (in addition to the mandatory type and link , which we shall not mention explicitly when discussing the other node types): The height and width and depth are scaled integers denoting the dimensions of the box. There is also a shift amount field, a scaled integer indicating how much this box should be lowered (if it appears in a horizontal list), or how much it should be moved to the right (if it appears in a vertical list). There is a list ptr field, which points to the beginning of the list from which this box was fabricated; if list ptr is null , the box is empty. Finally, there are three fields that represent the setting of the glue: glue set (p) is a word of type glue ratio that represents the proportionality constant for glue setting; glue sign(p) is stretching or shrinking or normal depending on whether or not the glue should stretch or shrink or remain rigid; and glue order (p) specifies the order of infinity to which glue setting applies (normal , fil , fill , or filll ). The subtype field is not used.

define hlist node = 0 { type of hlist nodes } define box node size = 7 { number of words to allocate for a box node } define width offset = 1 { position of width field in a box node } define depth offset = 2 { position of depth field in a box node } define height offset = 3 { position of height field in a box node } define width(#) ≡ mem[# + width offset ].sc { width of the box, in sp } define depth(#) ≡ mem[# + depth offset ].sc { depth of the box, in sp } define height (#) ≡ mem[# + height offset ].sc { height of the box, in sp } define shift amount (#) ≡ mem[# + 4].sc { repositioning distance, in sp } define list offset = 5 { position of list ptr field in a box node } define list ptr (#) ≡ link (# + list offset ) { beginning of the list inside the box } define glue order (#) ≡ subtype(# + list offset ) { applicable order of infinity } define glue sign(#) ≡ type(# + list offset ) { stretching or shrinking } define normal = 0 { the most common case when several cases are named } define stretching = 1 { glue setting applies to the stretch components } define shrinking = 2 { glue setting applies to the shrink components } define glue offset = 6 { position of glue set in a box node } define glue set (#) ≡ mem[# + glue offset ].gr { a word of type glue ratio for glue setting }

136. The new null box function returns a pointer to an hlist node in which all subfields have the values corresponding to ‘ ’. The subtype field is set to min quarterword , since that’s the desired span count value if this hlist node is changed to an unset node. function new null box : pointer ; { creates a new box node }

var p: pointer ; { the new node } begin p ← get node(box node size); type(p) ← hlist node; subtype(p) ← min quarterword ; width(p) ← 0; depth(p) ← 0; height (p) ← 0; shift amount (p) ← 0; list ptr (p) ← null ; glue sign(p) ← normal ; glue order (p) ← normal ; set glue ratio zero(glue set (p)); new null box ← p; end;

137. A vlist node is like an hlist node in all respects except that it contains a vertical list. define vlist node = 1 { type of vlist nodes }

138. A rule node stands for a solid black rectangle; it has width, depth, and height fields just as in an hlist node. However, if any of these dimensions is −2^{30}, the actual value will be determined by running the rule up to the boundary of the innermost enclosing box. This is called a “running dimension.” The width is never running in an hlist; the height and depth are never running in a vlist.

define rule node = 2 { type of rule nodes } define rule node size = 4 { number of words to allocate for a rule node } define null flag ≡ −´ 10000000000 { −2^{30}, signifies a missing item } define is running (#) ≡ (# = null flag ) { tests for a running dimension } 139. A new rule node is delivered by the new rule function. It makes all the dimensions “running,” so you have to change the ones that are not allowed to run. function new rule: pointer ;

var p: pointer ; { the new node }

begin p ← get node(rule node size); type(p) ← rule node; subtype(p) ← 0; { the subtype is not used } width(p) ← null flag ; depth(p) ← null flag ; height (p) ← null flag ; new rule ← p; end;

140. Insertions are represented by ins node records, where the subtype indicates the corresponding box number. For example, ‘ ’ leads to an ins node whose subtype is 250 + min quarterword . The height field of an ins node is slightly misnamed; it actually holds the natural height plus depth of the vertical list being inserted. The depth field holds the split max depth to be used in case this insertion is split, and the split top ptr points to the corresponding split top skip. The float cost field holds the floating penalty that will be used if this insertion floats to a subsequent page after a split insertion of the same class. There is one more field, the ins ptr , which points to the beginning of the vlist for the insertion.

define ins node = 3 { type of insertion nodes }

define ins node size = 5 { number of words to allocate for an insertion }

define float cost (#) ≡ mem[# + 1].int { the floating penalty to be used }

define ins ptr (#) ≡ info(# + 4) { the vertical list to be inserted }

define split top ptr (#) ≡ link (# + 4) { the split top skip to be used }

141. A mark node has a mark ptr field that points to the reference count of a token list that contains the user’s text. This field occupies a full word instead of a halfword, because there’s nothing to put in the other halfword; it is easier in Pascal to use the full word than to risk leaving garbage in the unused half.

define mark node = 4 { type of a mark node }

define small node size = 2 { number of words to allocate for most node types }

define mark ptr (#) ≡ mem[# + 1].int { head of the token list for a mark }

142. An adjust node, which occurs only in horizontal lists, specifies material that will be moved out into the surrounding vertical list; i.e., it is used to implement TEX’s ‘ ’ operation. The adjust ptr field points to the vlist containing this material.

define adjust node = 5 { type of an adjust node }

define adjust ptr ≡ mark ptr { vertical list to be moved out of horizontal list }

143. A ligature node, which occurs only in horizontal lists, specifies a character that was fabricated from the interaction of two or more actual characters. The second word of the node, which is called the lig char word, contains font and character fields just as in a char node. The characters that generated the ligature have not been forgotten, since they are needed for diagnostic messages and for hyphenation; the lig ptr field points to a linked list of character nodes for all original characters that have been deleted. (This list might be empty if the characters that generated the ligature were retained in other nodes.)

The subtype field is 0, plus 2 and/or 1 if the original source of the ligature included implicit left and/or right boundaries.

define ligature node = 6 { type of a ligature node }

define lig char (#) ≡ # + 1 { the word where the ligature is to be found }

define lig ptr (#) ≡ link (lig char (#)) { the list of characters } 144. The new ligature function creates a ligature node having given contents of the font , character , and lig ptr fields. We also have a new lig item function, which returns a two-word node having a given character field. Such nodes are used for temporary processing as ligatures are being created. function new ligature(f, c : quarterword ; q : pointer ): pointer ;

var p: pointer ; { the new node }

begin p ← get node(small node size); type(p) ← ligature node; font (lig char (p)) ← f;

character (lig char (p)) ← c; lig ptr (p) ← q; subtype(p) ← 0; new ligature ← p;

end; function new lig item(c : quarterword ): pointer ;

var p: pointer ; { the new node }

begin p ← get node(small node size); character (p) ← c; lig ptr (p) ← null ; new lig item ← p; end;

145. A disc node, which occurs only in horizontal lists, specifies a “discretionary” line break. If such a break occurs at node p, the text that starts at pre break (p) will precede the break, the text that starts at post break (p) will follow the break, and text that appears in the next replace count (p) nodes will be ignored. For example, an ordinary discretionary hyphen, indicated by ‘ ’, yields a disc node with pre break pointing to a char node containing a hyphen, post break = null , and replace count = 0. All three of the discretionary texts must be lists that consist entirely of character, kern, box, rule, and ligature nodes.

If pre break (p) = null , the ex hyphen penalty will be charged for this break. Otherwise the hyphen penalty will be charged. The texts will actually be substituted into the list by the line-breaking algorithm if it decides to make the break, and the discretionary node will disappear at that time; thus, the output routine sees only discretionaries that were not chosen.

define disc node = 7 { type of a discretionary node }

define replace count ≡ subtype { how many subsequent nodes to replace }

define pre break ≡ llink { text that precedes a discretionary break }

define post break ≡ rlink { text that follows a discretionary break } function new disc: pointer ; { creates an empty disc node }

var p: pointer ; { the new node }

begin p ← get node(small node size); type(p) ← disc node; replace count (p) ← 0; pre break (p) ← null ; post break (p) ← null ; new disc ← p; end;

146. A whatsit node is a wild card reserved for extensions to TEX. The subtype field in its first word says what ‘whatsit ’ it is, and implicitly determines the node size (which must be 2 or more) and the format of the remaining words. When a whatsit node is encountered in a list, special actions are invoked; knowledgeable people who are careful not to mess up the rest of TEX are able to make TEX do new things by adding code at the end of the program. For example, there might be a ‘TEXnicolor’ extension to specify different colors of ink, and the whatsit node might contain the desired parameters.

The present implementation of TEX treats the features associated with ‘ ’ and ‘ ’ as if they were extensions, in order to illustrate how such routines might be coded. We shall defer further discussion of extensions until the end of this program.

define whatsit node = 8 { type of special extension nodes } 147. A math node, which occurs only in horizontal lists, appears before and after mathematical formulas. The subtype field is before before the formula and after after it. There is a width field, which represents the amount of surrounding space inserted by .

define math node = 9 { type of a math node }

define before = 0 { subtype for math node that introduces a formula }

define after = 1 { subtype for math node that winds up a formula } function new math(w : scaled ; s : small number ): pointer ;

var p: pointer ; { the new node }

begin p ← get node(small node size); type(p) ← math node; subtype(p) ← s; width(p) ← w; new math ← p; end;

148. TEX makes use of the fact that hlist node, vlist node, rule node, ins node, mark node, adjust node, ligature node, disc node, whatsit node, and math node are at the low end of the type codes, by permitting a break at glue in a list if and only if the type of the previous node is less than math node. Furthermore, a node is discarded after a break if its type is math node or more.

define precedes break (#) ≡ (type(#) < math node)

define non discardable(#) ≡ (type(#) < math node)

149. A glue node represents glue in a list. However, it is really only a pointer to a separate glue specification, since TEX makes use of the fact that many essentially identical nodes of glue are usually present. If p points to a glue node, glue ptr (p) points to another packet of words that specify the stretch and shrink components, etc.

Glue nodes also serve to represent leaders; the subtype is used to distinguish between ordinary glue (which is called normal ) and the three kinds of leaders (which are called a leaders , c leaders , and x leaders ). The leader ptr field points to a rule node or to a box node containing the leaders; it is set to null in ordinary glue nodes.

Many kinds of glue are computed from TEX’s “skip” parameters, and it is helpful to know which parameter has led to a particular glue node. Therefore the subtype is set to indicate the source of glue, whenever it originated as a parameter. We will be defining symbolic names for the parameter numbers later (e.g., line skip code = 0, baseline skip code = 1, etc.); it suffices for now to say that the subtype of parametric glue will be the same as the parameter number, plus one.

In math formulas there are two more possibilities for the subtype in a glue node: mu glue denotes an (where the units are scaled instead of scaled ); and cond math glue denotes the ‘ ’ feature that cancels the glue node immediately following if it appears in a subscript.

define glue node = 10 { type of node that points to a glue specification }

define cond math glue = 98 { special subtype to suppress glue in the next node }

define mu glue = 99 { subtype for math glue }

define a leaders = 100 { subtype for aligned leaders }

define c leaders = 101 { subtype for centered leaders }

define x leaders = 102 { subtype for expanded leaders }

define glue ptr ≡ llink { pointer to a glue specification }

define leader ptr ≡ rlink { pointer to box or rule node for leaders } 150. A glue specification has a halfword reference count in its first word, representing null plus the number of glue nodes that point to it (less one). Note that the reference count appears in the same position as the link field in list nodes; this is the field that is initialized to null when a node is allocated, and it is also the field that is flagged by empty flag in empty nodes.

Glue specifications also contain three scaled fields, for the width, stretch, and shrink dimensions. Finally, there are two one-byte fields called stretch order and shrink order ; these contain the orders of infinity (normal , fil , fill , or filll ) corresponding to the stretch and shrink values.

define glue spec size = 4 { number of words to allocate for a glue specification } define glue ref count (#) ≡ link (#) { reference count of a glue specification } define stretch(#) ≡ mem[# + 2].sc { the stretchability of this glob of glue } define shrink (#) ≡ mem[# + 3].sc { the shrinkability of this glob of glue } define stretch order ≡ type { order of infinity for stretching } define shrink order ≡ subtype { order of infinity for shrinking } define fil = 1 { first-order infinity } define fill = 2 { second-order infinity } define filll = 3 { third-order infinity }

⟨ Types in the outer block 18 ⟩ +≡ glue ord = normal . . filll ; { infinity to the 0, 1, 2, or 3 power }

151. Here is a function that returns a pointer to a copy of a glue spec. The reference count in the copy is null , because there is assumed to be exactly one reference to the new specification. function new spec(p : pointer ): pointer ; { duplicates a glue specification }

var q: pointer ; { the new spec } begin q ← get node(glue spec size); mem[q] ← mem[p]; glue ref count (q) ← null ; width(q) ← width(p); stretch(q) ← stretch(p); shrink (q) ← shrink (p); new spec ← q; end;

152. And here’s a function that creates a glue node for a given parameter identified by its code number; for example, new param glue(line skip code) returns a pointer to a glue node for the current . function new param glue(n : small number ): pointer ;

var p: pointer ; { the new node }

q: pointer ; { the glue specification } begin p ← get node(small node size); type(p) ← glue node; subtype(p) ← n + 1; leader ptr (p) ← null ; q ← ⟨ Current mem equivalent of glue parameter number n 224 ⟩; glue ptr (p) ← q; incr (glue ref count (q)); new param glue ← p; end;

153. Glue nodes that are more or less anonymous are created by new glue, whose argument points to a glue specification. function new glue(q : pointer ): pointer ;

var p: pointer ; { the new node } begin p ← get node(small node size); type(p) ← glue node; subtype(p) ← normal ; leader ptr (p) ← null ; glue ptr (p) ← q; incr (glue ref count (q)); new glue ← p; end; 154. Still another subroutine is needed: this one is sort of a combination of new param glue and new glue. It creates a glue node for one of the current glue parameters, but it makes a fresh copy of the glue specification, since that specification will probably be subject to change, while the parameter will stay put. The global variable temp ptr is set to the address of the new spec. function new skip param(n : small number ): pointer ;

var p: pointer ; { the new node }

begin temp ptr ← new spec(⟨ Current mem equivalent of glue parameter number n 224 ⟩); p ← new glue(temp ptr ); glue ref count (temp ptr ) ← null ; subtype(p) ← n + 1; new skip param ← p; end;

155. A kern node has a width field to specify a (normally negative) amount of spacing. This spacing correction appears in horizontal lists between letters like A and V when the font designer said that it looks better to move them closer together or further apart. A kern node can also appear in a vertical list, when its ‘width’ denotes additional spacing in the vertical direction. The subtype is either normal (for kerns inserted from font information or math mode calculations) or explicit (for kerns inserted from and commands) or acc kern (for kerns inserted from non-math accents) or mu glue (for kerns inserted from specifications in math formulas).

define kern node = 11 { type of a kern node }

define explicit = 1 { subtype of kern nodes from and }

define acc kern = 2 { subtype of kern nodes from accents }

156. The new kern function creates a kern node having a given width. function new kern(w : scaled ): pointer ;

var p: pointer ; { the new node }

begin p ← get node(small node size); type(p) ← kern node; subtype(p) ← normal ; width(p) ← w; new kern ← p; end;

157. A penalty node specifies the penalty associated with line or page breaking, in its penalty field. This field is a fullword integer, but the full range of integer values is not used: Any penalty ≥ 10000 is treated as infinity, and no break will be allowed for such high values. Similarly, any penalty ≤ −10000 is treated as negative infinity, and a break will be forced.

define penalty node = 12 { type of a penalty node }

define inf penalty = inf bad { “infinite” penalty value }

define eject penalty = −inf penalty { “negatively infinite” penalty value }

define penalty (#) ≡ mem[# + 1].int { the added cost of breaking a list here }

158. Anyone who has been reading the last few sections of the program will be able to guess what comes next. function new penalty (m : integer ): pointer ;

var p: pointer ; { the new node }

begin p ← get node(small node size); type(p) ← penalty node; subtype(p) ← 0;

{ the subtype is not used } penalty (p) ← m; new penalty ← p; end; 159. You might think that we have introduced enough node types by now. Well, almost, but there is one more: An unset node has nearly the same format as an hlist node or vlist node; it is used for entries in or that are not yet in their final form, since the box dimensions are their “natural” sizes before any glue adjustment has been made. The glue set word is not present; instead, we have a glue stretch field, which contains the total stretch of order glue order that is present in the hlist or vlist being boxed. Similarly, the shift amount field is replaced by a glue shrink field, containing the total shrink of order glue sign that is present. The subtype field is called span count ; an unset box typically contains the data for qo(span count ) + 1 columns. Unset nodes will be changed to box nodes when alignment is completed.

define unset node = 13 { type for an unset node }

define glue stretch(#) ≡ mem[# + glue offset ].sc { total stretch in an unset node } define glue shrink ≡ shift amount { total shrink in an unset node } define span count ≡ subtype { indicates the number of spanned columns }

160. In fact, there are still more types coming. When we get to math formula processing we will see that a style node has type = 14; and a number of larger type codes will also be defined, for use in math mode only.

161. Warning: If any changes are made to these data structure layouts, such as changing any of the node sizes or even reordering the words of nodes, the copy node list procedure and the memory initialization code below may have to be changed. Such potentially dangerous parts of the program are listed in the index under ‘data structure assumptions’. However, other references to the nodes are made symbolically in terms of the macro definitions above, so that format changes will leave TEX’s other algorithms intact.