1 /*@z44.c:Vertical Hyphenation:VerticalHyphenate()@****************************/
2 /* */
3 /* THE LOUT DOCUMENT FORMATTING SYSTEM (VERSION 3.39) */
4 /* COPYRIGHT (C) 1991, 2008 Jeffrey H. Kingston */
5 /* */
6 /* Jeffrey H. Kingston (jeff@it.usyd.edu.au) */
7 /* School of Information Technologies */
8 /* The University of Sydney 2006 */
9 /* AUSTRALIA */
10 /* */
11 /* This program is free software; you can redistribute it and/or modify */
12 /* it under the terms of the GNU General Public License as published by */
13 /* the Free Software Foundation; either Version 3, or (at your option) */
14 /* any later version. */
15 /* */
16 /* This program is distributed in the hope that it will be useful, */
17 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
18 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
19 /* GNU General Public License for more details. */
20 /* */
21 /* You should have received a copy of the GNU General Public License */
22 /* along with this program; if not, write to the Free Software */
23 /* Foundation, Inc., 59 Temple Place, Suite 330, Boston MA 02111-1307 USA */
24 /* */
25 /* FILE: z44.c */
26 /* MODULE: Vertical Hyphenation */
27 /* EXTERNS: VerticalHyphenate(), ConvertGalleyList() */
28 /* */
29 /*****************************************************************************/
30 #include "externs.h"
31
32
33 /*****************************************************************************/
34 /* */
35 /* FirstDefiniteCompressed(x, link, y) */
36 /* NextDefiniteWithGapCompressed(x, link, y, g) */
37 /* */
38 /* Like FirstDefinite() and NextDefiniteWithGap(), except that these */
39 /* versions assume that x is of type VCAT, and they compress any VCAT */
40 /* objects found within x as they go. */
41 /* */
42 /*****************************************************************************/
43
44 #define FirstDefiniteCompressed(x, link, y) \
45 { BOOLEAN jn; \
46 FirstDefinite(x, link, y, jn); \
47 while( link != x && type(y) == VCAT ) \
48 { TransferLinks(Down(y), y, link); \
49 DisposeChild(link); \
50 FirstDefinite(x, link, y, jn); \
51 } \
52 assert( link==x || is_definite(type(y)), "FirstDefiniteCompressed!"); \
53 }
54
55 #define NextDefiniteWithGapCompressed(x, link, y, g) \
56 { OBJECT start_link = PrevDown(link), ylink, yg, z; \
57 BOOLEAN jn; \
58 NextDefiniteWithGap(x, link, y, g, jn); \
59 while( link != x && type(y) == VCAT ) \
60 { FirstDefinite(y, ylink, z, jn); \
61 if( ylink != y && PrevDown(ylink) != y ) \
62 { Child(yg, PrevDown(ylink)); \
63 assert( type(yg)==GAP_OBJ && mode(gap(yg)) != NO_MODE, "NDWGC!"); \
64 MoveLink(PrevDown(ylink), Up(g), PARENT); \
65 MoveLink(Up(g), ylink, PARENT); \
66 } \
67 TransferLinks(Down(y), y, link); \
68 DisposeChild(link); \
69 link = NextDown(start_link); \
70 NextDefiniteWithGap(x, link, y, g, jn); \
71 } \
72 assert( link==x || is_definite(type(y)), "FirstDefiniteCompressed!"); \
73 assert( link==x || mode(gap(g)) != NO_MODE, \
74 "FirstDefiniteWithGapCompressed: mode(gap(g))!" ); \
75 }
76
77
78 /*@@**************************************************************************/
79 /* */
80 /* OBJECT FindTarget(index) */
81 /* */
82 /* Work out what the given index is pointing at, or nilobj if nothing. */
83 /* */
84 /*****************************************************************************/
85
FindTarget(OBJECT index)86 static OBJECT FindTarget(OBJECT index)
87 { OBJECT res = nilobj;
88 debug1(DVH, DD, "FindTarget(%s)", Image(type(index)));
89 switch( type(index) )
90 {
91 case DEAD:
92
93 res = nilobj;
94 break;
95
96
97 case UNATTACHED:
98 case GALL_PREC:
99 case GALL_FOLL:
100 case GALL_FOLL_OR_PREC:
101
102 res = pinpoint(index);
103 break;
104
105
106 case RECEPTIVE:
107 case RECEIVING:
108 case RECURSIVE:
109 case SCALE_IND:
110 case COVER_IND:
111 case EXPAND_IND:
112
113 res = actual(index);
114 break;
115
116
117 case PRECEDES:
118 case FOLLOWS:
119 case CROSS_TARG:
120 case CROSS_PREC:
121 case CROSS_FOLL:
122 case CROSS_FOLL_OR_PREC:
123 case PAGE_LABEL_IND:
124
125 res = nilobj; /* somewhat doubtful */
126 break;
127
128
129 case GALL_TARG:
130
131 res = nilobj; /* somewhat doubtful */
132 break;
133
134
135 default:
136
137 assert1(FALSE, "FindTarget: unknown index", Image(type(index)));
138 break;
139 }
140 debug1(DVH, DD, "FindTarget returning %s", EchoObject(res));
141 return res;
142 } /* end FindTarget */
143
144
145 /*@@**************************************************************************/
146 /* */
147 /* OBJECT WhichComponent(target) */
148 /* */
149 /* Return the component of the enclosing galley that contains target, */
150 /* or nilobj if some problem. */
151 /* */
152 /*****************************************************************************/
153
WhichComponent(OBJECT target)154 static OBJECT WhichComponent(OBJECT target)
155 { OBJECT prnt;
156 debug1(DVH, DD, "WhichComponent(%s)", EchoObject(target));
157 while( Up(target) != target )
158 { Parent(prnt, Up(target));
159 if( type(prnt) == HEAD )
160 { debug1(DVH, DD, "WhichComponent returning %s", EchoObject(target));
161 return target;
162 }
163 target = prnt;
164 }
165 debug0(DVH, DD, "WhichComponent returning nilobj");
166 return nilobj;
167 } /* end WhichComponent */
168
169
170 /*****************************************************************************/
171 /* */
172 /* OBJECT EncloseInHcat(nxt, y, replace) */
173 /* */
174 /* Enclose object nxt in an HCAT, similar to HCAT y, at position replace. */
175 /* The link to nxt will now link to the new HCAT. */
176 /* */
177 /*****************************************************************************/
178
EncloseInHcat(OBJECT nxt,OBJECT y,OBJECT replace)179 static OBJECT EncloseInHcat(OBJECT nxt, OBJECT y, OBJECT replace)
180 { OBJECT new_y, new_row_thread, s1, new_s1, s2, new_s2, link, sh, new_sh, tmp;
181 assert( Up(nxt) != nxt, "EncloseInHCat: Up(nxt) == nxt!" );
182 New(new_y, HCAT);
183 adjust_cat(new_y) = FALSE;
184 MoveLink(Up(nxt), new_y, CHILD);
185 assert( Up(nxt) == nxt, "EncloseInHCat: Up(nxt) != nxt!" );
186 FposCopy(fpos(new_y), fpos(y));
187 back(new_y, COLM) = back(y, COLM);
188 fwd(new_y, COLM) = fwd(y, COLM);
189 back(new_y, ROWM) = back(nxt, ROWM);
190 fwd(new_y, ROWM) = fwd(nxt, ROWM);
191 New(new_row_thread, ROW_THR);
192 back(new_row_thread, ROWM) = back(new_y, ROWM);
193 fwd(new_row_thread, ROWM) = fwd(new_y, ROWM);
194 thr_state(new_row_thread) = SIZED;
195 for( link = Down(y); link != y; link = NextDown(link) )
196 { Child(s1, link);
197 if( type(s1) == GAP_OBJ )
198 { New(new_s1, GAP_OBJ);
199 FposCopy(fpos(new_s1), fpos(s1));
200 GapCopy(gap(new_s1), gap(s1));
201 hspace(new_s1) = hspace(s1);
202 vspace(new_s1) = vspace(s1);
203 Link(new_y, new_s1);
204 continue;
205 }
206 if( type(s1) == WIDE || type(s1) == ONE_COL )
207 Child(s2, Down(s1));
208 else s2 = s1;
209 assert( type(s2) == SPLIT, "EncloseInHcat: type(s2) != SPLIT!" );
210 Child(sh, DownDim(s2, COLM));
211 New(new_s2, SPLIT);
212 FposCopy(fpos(new_s2), fpos(s2));
213 if( s2 != s1 )
214 { New(new_s1, type(s1));
215 back(new_s1, COLM) = back(s1, COLM);
216 fwd(new_s1, COLM) = fwd(s1, COLM);
217 back(new_s1, ROWM) = back(new_row_thread, COLM);
218 fwd(new_s1, ROWM) = fwd(new_row_thread, COLM);
219 Link(new_y, new_s1);
220 Link(new_s1, new_s2);
221 }
222 else Link(new_y, new_s2);
223 if( sh == replace )
224 {
225 /* replace sh by nxt in the copy */
226 new_sh = nxt;
227 back(new_sh, COLM) = back(s2, COLM);
228 fwd(new_sh, COLM) = fwd(s2, COLM);
229 }
230 else
231 {
232 /* replace sh by an empty object of the same width in the copy */
233 New(new_sh, WIDE);
234 FposCopy(fpos(new_sh), fpos(sh));
235 SetConstraint(constraint(new_sh), back(sh,COLM),size(sh,COLM),fwd(sh,COLM));
236 back(new_sh, COLM) = back(sh, COLM);
237 fwd(new_sh, COLM) = fwd(sh, COLM);
238 back(new_sh, ROWM) = fwd(new_sh, ROWM) = 0;
239 tmp = MakeWord(WORD, STR_EMPTY, &fpos(sh));
240 back(tmp, COLM) = fwd(tmp, COLM) = 0;
241 back(tmp, ROWM) = fwd(tmp, ROWM) = 0;
242 underline(tmp) = UNDER_OFF;
243 Link(new_sh, tmp);
244 }
245 Link(new_s2, new_sh);
246 back(new_s2, COLM) = back(new_sh, COLM);
247 fwd(new_s2, COLM) = fwd(new_sh, COLM);
248 Link(new_s2, new_row_thread);
249 back(new_s2, ROWM) = back(new_row_thread, ROWM);
250 fwd(new_s2, ROWM) = fwd(new_row_thread, ROWM);
251 Link(new_row_thread, new_sh);
252 }
253 return new_y;
254 } /* end EncloseInHcat */
255
256
257 /*@::VerticalHyphenate()@*****************************************************/
258 /* */
259 /* BOOLEAN VerticalHyphenate(OBJECT y) */
260 /* */
261 /* Attempt to vertically hyphenate galley component y, of type HCAT. */
262 /* */
263 /*****************************************************************************/
264
VerticalHyphenate(OBJECT y)265 BOOLEAN VerticalHyphenate(OBJECT y)
266 { OBJECT large_comp, index, z, link, g, large_comp_split = nilobj;
267 OBJECT row_thread, s1, s2, sh, sv, shp, prev = nilobj, nxt = nilobj;
268 FULL_LENGTH rump_fwd;
269 debug1(DVH, D, "[ VerticalHyphenate(y: %s), y =", EchoLength(size(y, ROWM)));
270 ifdebug(DVH, D, DebugObject(y));
271 debug0(DVH, DD, "galley before vertical hyphenation:");
272 ifdebug(DVH, DD, Parent(z, Up(y)); DebugGalley(z, y, 2));
273
274 /* find large_comp, the largest VCAT component, or else return FALSE */
275 row_thread = large_comp = nilobj;
276 rump_fwd = 0;
277 assert( type(y) == HCAT, "VerticalHyphenate: type(y) != HCAT!" );
278 for( link = Down(y); link != y; link = NextDown(link) )
279 { Child(s1, link);
280 if( type(s1) == GAP_OBJ )
281 { if( !join(gap(s1)) )
282 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (not joined)");
283 return FALSE;
284 }
285 continue;
286 }
287
288 /* check that s2 is a SPLIT object whose children look right */
289 if( type(s1) == WIDE || type(s1) == ONE_COL )
290 Child(s2, Down(s1));
291 else s2 = s1;
292 if( type(s2) != SPLIT )
293 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (child not SPLIT)");
294 return FALSE;
295 }
296 Child(sh, DownDim(s2, COLM));
297 Child(sv, DownDim(s2, ROWM));
298 if( type(sv) != ROW_THR )
299 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (no ROW_THR)");
300 return FALSE;
301 }
302 if( row_thread == nilobj ) row_thread = sv;
303 if( sv != row_thread )
304 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (different ROW_THR)");
305 return FALSE;
306 }
307 Parent(shp, UpDim(sh, ROWM));
308 if( shp != row_thread )
309 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (sh parent)");
310 return FALSE;
311 }
312
313 /* Now sh is one of the HCAT components */
314 if( type(sh) != VCAT )
315 { rump_fwd = find_max(rump_fwd, fwd(sh, ROWM));
316 }
317 else if( large_comp != nilobj )
318 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (two VCATs)");
319 return FALSE;
320 }
321 else
322 { large_comp = sh;
323 large_comp_split = s2;
324 }
325 }
326
327 /* if no large_comp, return */
328 if( large_comp == nilobj )
329 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (no VCAT)");
330 return FALSE;
331 }
332
333 /* check that large_comp has at least two components */
334 FirstDefiniteCompressed(large_comp, link, prev);
335 if( link == large_comp )
336 { debug0(DVH,D, "] VerticalHyphenate returning FALSE (VCAT: no components)");
337 return FALSE;
338 }
339 NextDefiniteWithGapCompressed(large_comp, link, nxt, g);
340 if( link == large_comp )
341 { debug0(DVH,D, "] VerticalHyphenate returning FALSE (VCAT: one component)");
342 return FALSE;
343 }
344
345 /* make sure that first gap does not change when rearranging */
346 rump_fwd = find_max(rump_fwd, fwd(prev, ROWM));
347 if( MinGap(rump_fwd, back(nxt, ROWM), fwd(nxt, ROWM), &gap(g)) !=
348 MinGap(fwd(prev, ROWM), back(nxt, ROWM), fwd(nxt, ROWM), &gap(g)) )
349 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (first gap changes)");
350 return FALSE;
351 }
352
353 /* check that large_comp has no joins */
354 for( link = Down(large_comp); link != large_comp; link = NextDown(link) )
355 { Child(z, link);
356 if( type(z) == GAP_OBJ && mode(gap(z)) != NO_MODE && join(gap(z)) )
357 { debug0(DVH, D, "] VerticalHyphenate returning FALSE (VCAT: joined)");
358 return FALSE;
359 }
360 }
361
362 /* enclose all definite components after the first in HCATs */
363 for( link = NextDown(Up(prev)); link != large_comp; link = NextDown(link) )
364 { Child(nxt, link);
365 if( type(nxt) == GAP_OBJ ) continue;
366 if( is_definite(type(nxt)) )
367 nxt = EncloseInHcat(nxt, y, large_comp);
368 }
369
370 /* move all components after the first to the top level */
371 TransferLinks(Up(g), large_comp, NextDown(Up(y)));
372
373 /* change the size of y to its new, smaller value */
374 fwd(y, ROWM) = fwd(row_thread, ROWM) = fwd(large_comp, ROWM)
375 = fwd(large_comp_split, ROWM) = fwd(prev, ROWM);
376
377 /* set link to the link of the first thing before y which is not an index */
378 for( link = PrevDown(Up(y)); type(link) == LINK; link = PrevDown(link) )
379 { Child(index, link);
380 if( !is_index(type(index)) ) break;
381 }
382
383 /* for each index, find where it's pointing and possibly move it */
384 while( NextDown(link) != Up(y) )
385 { Child(index, NextDown(link));
386 assert( is_index(type(index)), "MoveIndexes: is_index!" );
387 z = FindTarget(index);
388 if( z != nilobj )
389 { z = WhichComponent(z);
390 if( z != nilobj && z != y )
391 { MoveLink(NextDown(link), Up(z), PARENT);
392 }
393 else link = NextDown(link);
394 }
395 else link = NextDown(link);
396 }
397
398 debug1(DVH, D, "] VerticalHyphenate returning TRUE (y: %s)",
399 EchoLength(size(y, ROWM)));
400 debug0(DVH, DD, "galley after vertical hyphenation:");
401 ifdebug(DVH, DD, Parent(z, Up(y)); DebugGalley(z, y, 2));
402 return TRUE;
403 } /* end VerticalHyphenate */
404
405
406 /*****************************************************************************/
407 /* */
408 /* static OBJECT BuildMergeTree(int n, OBJECT x, OBJECT *lenv, *lact) */
409 /* */
410 /* Build a balanced tree of n-1 @Merge symbols, whose parameters are the */
411 /* first n children of x. Return in lenv the environment of the root */
412 /* @Merge symbol, and in *lact the symbol table entry for the parent of */
413 /* this @Merge symbol. */
414 /* */
415 /*****************************************************************************/
416
BuildMergeTree(int n,OBJECT x,OBJECT * lenv,OBJECT * lact)417 static OBJECT BuildMergeTree(int n, OBJECT x, OBJECT *lenv, OBJECT *lact)
418 { OBJECT res, merge, link, y = nilobj, l, r, env, act, left_par, right_par;
419 debug2(DHY, DD, "BuildMergeTree(%d, %s, -. -)", n, EchoObject(x));
420
421 if( n == 1 )
422 { New(res, ENV_OBJ);
423 Child(y, Down(x));
424 MoveLink(Down(x), res, PARENT);
425 assert(type(y)==CLOSURE && has_merge(actual(y)), "BuildMergeTree: has_m!");
426 *lact = actual(y);
427 *lenv = DetachEnv(y);
428 AttachEnv(*lenv, res);
429 }
430 else
431 {
432 /* build the two subtrees */
433 l = BuildMergeTree(n/2, x, lenv, lact);
434 r = BuildMergeTree( n - n/2, x, &env, &act);
435
436 /* set merge to new @Merge closure */
437 for( link = Down(act); link != act; link = NextDown(link) )
438 { Child(y, link);
439 if( is_merge(y) ) break;
440 }
441 assert( y != act, "BuildMergeTree: y!" );
442 New(merge, CLOSURE);
443 actual(merge) = y;
444
445 /* build left parameter of the new @Merge */
446 New(left_par, PAR);
447 actual(left_par) = ChildSym(y, LPAR);
448 Link(merge, left_par);
449 Link(left_par, l);
450
451 /* build right parameter of the new @Merge */
452 New(right_par, PAR);
453 actual(right_par) = ChildSym(y, RPAR);
454 Link(merge, right_par);
455 Link(right_par, r);
456
457 New(res, ENV_OBJ);
458 Link(res, merge);
459 Link(res, env);
460 }
461
462 debug2(DHY, DD, "BuildMergeTree returning %s (*lact = %s)",
463 EchoObject(res), SymName(*lact));
464 return res;
465 } /* end BuildMergeTree */
466
467
468 /*****************************************************************************/
469 /* */
470 /* OBJECT ConvertGalleyList(x) */
471 /* */
472 /* Convert a set of galleys x into a single galley containing a balanced */
473 /* tree of @Merge symbols. */
474 /* */
475 /*****************************************************************************/
476
ConvertGalleyList(OBJECT x)477 OBJECT ConvertGalleyList(OBJECT x)
478 { OBJECT res, y, link, junk1, junk2, obj; int n;
479 debug1(DHY, DD, "ConvertGalleyList(%s)", EchoObject(x));
480 Child(res, Down(x));
481 Child(y, Down(res));
482 MoveLink(Down(x), y, CHILD);
483 DeleteLink(Down(res));
484 MoveLink(Up(x), res, CHILD);
485 for( link = Down(x), n = 0; link != x; link = NextDown(link), n++ );
486 y = BuildMergeTree(n, x, &junk1, &junk2);
487 assert( Down(x) == x && Up(x) == x, "ConvertGalleyList: x!" );
488 Dispose(x);
489 Child(obj, Down(y));
490 MoveLink(Down(y), res, PARENT);
491 MoveLink(LastDown(y), obj, PARENT);
492 assert( Down(y) == y && Up(y) == y, "ConvertGalleyList: y!" );
493 Dispose(y);
494 debug0(DHY, DD, "ConvertGalleyList returning, res =");
495 ifdebug(DHY, DD, DebugObject(res));
496 return res;
497 } /* end ConvertGalleyList */
498
499
500 /*****************************************************************************/
501 /* */
502 /* OBJECT BuildEnclose(hd) */
503 /* */
504 /* Build the @Enclose object for galley hd. */
505 /* */
506 /*****************************************************************************/
507
BuildEnclose(OBJECT hd)508 OBJECT BuildEnclose(OBJECT hd)
509 { OBJECT sym = nilobj, parsym, x, y, link, par, val, env, res;
510 debug1(DOM, D, "BuildEnclose(%s)", SymName(actual(hd)));
511
512 /* find @Enclose symbol and check that it has just one parameter */
513 for( link = Down(actual(hd)); link != actual(hd); link = NextDown(link) )
514 { Child(sym, link);
515 if( is_enclose(sym) ) break;
516 }
517 assert( link != actual(hd), "BuildEnclose: no enclose!" );
518 parsym = nilobj;
519 for( link = Down(sym); link != sym; link = NextDown(link) )
520 { Child(y, link);
521 switch( type(y) )
522 {
523 case LPAR:
524 case NPAR:
525
526 Error(44, 1, "%s may not have a left or named parameter", FATAL,
527 &fpos(y), KW_ENCLOSE);
528 break;
529
530
531 case RPAR:
532
533 if( has_body(sym) )
534 Error(44, 2, "%s may not have a body parameter", FATAL,
535 &fpos(y), KW_ENCLOSE);
536 parsym = y;
537 break;
538
539
540 default:
541
542 break;
543 }
544 }
545 if( parsym == nilobj )
546 Error(44, 3, "%s must have a right parameter", FATAL, &fpos(sym),KW_ENCLOSE);
547
548 /* set x to new @Enclose closure with dummy actual right parameter */
549 New(x, CLOSURE);
550 FposCopy(fpos(x), fpos(hd));
551 actual(x) = sym;
552 New(par, PAR);
553 FposCopy(fpos(par), fpos(hd));
554 actual(par) = parsym;
555 Link(x, par);
556 val = MakeWord(WORD, AsciiToFull("???"), &fpos(hd));
557 Link(par, val);
558
559 /* set env to the appropriate environment for this symbol */
560 /* strictly speaking y should not be included if sym is a parameter */
561 Child(y, Down(hd));
562 assert(type(y) == CLOSURE, "BuildEnclose: hd child!");
563 y = CopyObject(y, &fpos(hd));
564 env = SetEnv(y, nilobj);
565
566 /* build res, an ENV_OBJ with x at left and env at right */
567 New(res, ENV_OBJ);
568 Link(res, x);
569 Link(res, env);
570
571 debug1(DOM, D, "BuildEnclose returning %s", EchoObject(res));
572 return res;
573 } /* end BuildEnclose */
574