home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / APPS / lout2.lzh / LOUT2 / z14.c < prev    next >
Text File  |  1994-01-23  |  28KB  |  662 lines
  1. /*@z14.c:Fill Service:Declarations@*******************************************/
  2. /*                                                                           */
  3. /*  LOUT: A HIGH-LEVEL LANGUAGE FOR DOCUMENT FORMATTING (VERSION 2.05)       */
  4. /*  COPYRIGHT (C) 1993 Jeffrey H. Kingston                                   */
  5. /*                                                                           */
  6. /*  Jeffrey H. Kingston (jeff@cs.su.oz.au)                                   */
  7. /*  Basser Department of Computer Science                                    */
  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 1, 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., 675 Mass Ave, Cambridge, MA 02139, USA.                */
  24. /*                                                                           */
  25. /*  FILE:         z14.c                                                      */
  26. /*  MODULE:       Fill Service                                               */
  27. /*  EXTERNS:      FillObject()                                               */
  28. /*                                                                           */
  29. /*****************************************************************************/
  30. #include "externs"
  31. #define TOO_TIGHT_BAD    1048576    /* 2^20; badness of a too tight line         */
  32. #define TOO_LOOSE_BAD    65536    /* 2^16; the max badness of a too loose line */
  33. #define    TIGHT_BAD    4096    /* 2^12; the max badness of a tight line     */
  34. #define    LOOSE_BAD    4096    /* 2^12; the max badness of a loose line     */
  35. #define    HYPH_BAD    2048    /* 2^11; threshold for calling hyphenation   */
  36. #define SQRT_TOO_LOOSE    256    /* 2^ 8; sqrt(TOO_LOOSE_BAD)                 */
  37. #define    SQRT_TIGHT_BAD    64    /* 2^ 6; sqrt(TIGHT_BAD)                     */
  38. #define    SQRT_LOOSE_BAD    64    /* 2^ 6; sqrt(LOOSE_BAD)                     */
  39. #define MAX_EXPAND    1
  40. #define MAX_SHRINK    3
  41.  
  42.  
  43. typedef struct {
  44.   OBJECT llink;            /* link to gap before left end of interval   */
  45.   OBJECT rlink;            /* link to gap before right end of interval  */
  46.   LENGTH nat_width;        /* natural width of interval                 */
  47.   LENGTH space_width;        /* natural width of spaces in the interval   */
  48.   int     badness;        /* badness of this interval             */
  49.   unsigned char   class;    /* badness class of this interval         */
  50.   unsigned char     tab_count;    /* number of gaps with tab mode in interval  */
  51.   LENGTH tab_pos;        /* if tab_count > 0, this holds the position */
  52.                 /*  of the left edge of the object following */
  53.                 /*  the rightmost tab gap in the interval    */
  54.   LENGTH width_to_tab;        /* if tab_count > 0, the interval width up   */
  55.                 /*  to but not including the rightmost tab   */
  56. } INTERVAL;
  57.  
  58. #define unbreakable(g, hyph_allowed)                    \
  59. (width(g)==0 && (!hyph_allowed || (mode(g)!=HYPH_MODE && mode(g)!=ADD_HYPH)))
  60.  
  61.  
  62. /*****************************************************************************/
  63. /*                                                                           */
  64. /*  Badness classes                                                          */
  65. /*                                                                           */
  66. /*****************************************************************************/
  67.  
  68. #define TOO_LOOSE    0    /* interval is too loose             */
  69. #define LOOSE        1    /* interval is loose but not too loose         */
  70. #define TIGHT        2    /* interval is tight but not too tight         */
  71. #define TOO_TIGHT    3    /* interval is too tight              */
  72. #define TAB_OVERLAP    4    /* interval has a tab and left part overlaps */
  73. #define AT_END        5    /* interval ends at right end of paragraph   */
  74. #define ZERO_AT_LEFT    6    /* interval has a zero-width gap at left     */
  75. #define ZERO_AT_RIGHT    7    /* interval has a zero-width gap at right    */
  76. #define EMPTY_INTERVAL    8    /* interval is empty                         */
  77.  
  78. /*@::SetIntervalBadness()@****************************************************/
  79. /*                                                                           */
  80. /*  SetIntervalBadness(I)                                                    */
  81. /*                                                                           */
  82. /*  Private, calculates the badness and badness class of an interval.        */
  83. /*  Does not take into account any zero-width gap at either end.             */
  84. /*                                                                           */
  85. /*****************************************************************************/
  86.  
  87. #define SetIntervalBadness(I, max_width, etc_width)            \
  88. { OBJECT g; int badness;                        \
  89.   LENGTH col_width;                            \
  90.   if( I.llink == x )                            \
  91.   { col_width = max_width;                        \
  92.     I.badness = 0;                            \
  93.   }                                    \
  94.   else                                    \
  95.   { col_width = etc_width;                        \
  96.     Child(g, I.llink);                            \
  97.     I.badness = save_badness(g);                    \
  98.   }                                    \
  99.                                     \
  100.   if( I.tab_count > 0 && I.width_to_tab > I.tab_pos )            \
  101.   { I.class = TAB_OVERLAP;                        \
  102.     I.badness += TOO_TIGHT_BAD;                        \
  103.   }                                    \
  104.   else if( MAX_EXPAND*(col_width-I.nat_width) > 2*I.space_width )    \
  105.   { I.class = I.tab_count > 0 ? LOOSE : TOO_LOOSE;            \
  106.     badness = (SQRT_TOO_LOOSE*(col_width - I.nat_width)) / col_width;    \
  107.     I.badness += badness * badness;                    \
  108.   }                                    \
  109.   else if( I.nat_width <= col_width )                    \
  110.   { I.class = LOOSE;                            \
  111.     badness = (SQRT_LOOSE_BAD*(col_width - I.nat_width)) / col_width;    \
  112.     I.badness += badness * badness;                    \
  113.   }                                    \
  114.   else if( MAX_SHRINK*(I.nat_width-col_width) <= I.space_width )    \
  115.   { I.class = TIGHT;                            \
  116.     badness = (SQRT_TIGHT_BAD*(col_width - I.nat_width)) / col_width;    \
  117.     I.badness += badness * badness;                    \
  118.   }                                    \
  119.   else { I.class = TOO_TIGHT;  I.badness += TOO_TIGHT_BAD; }        \
  120. } /* end macro SetIntervalBadness */
  121.  
  122. /*@::CorrectOversizeError()@**************************************************/
  123. /*                                                                           */
  124. /*  CorrectOversizeError(x, link, y, etc_width)                              */
  125. /*                                                                           */
  126. /*  Child y of x, whose link is link, has caused an oversize error, either   */
  127. /*  because it is wider than etc_width, or because it is joined by zero-     */
  128. /*  width gaps on the left to other objects with oversize total size.        */
  129. /*  In the first case, the correction is to replace the object by an         */
  130. /*  empty object; in the second case, the correction is to widen the gap.    */
  131. /*                                                                           */
  132. /*****************************************************************************/
  133.  
  134. static CorrectOversizeError(x, link, y, etc_width, hyph_allowed)
  135. OBJECT x, link, y;  LENGTH etc_width;  BOOLEAN hyph_allowed;
  136. { OBJECT tmp, g;  BOOLEAN done = FALSE;
  137.  
  138.   if( PrevDown(link) != x ) /* make any preceding unbreakable gap breakable */
  139.   { Child(g, PrevDown(link));
  140.     assert( type(g) == GAP_OBJ, "CorrectOversizeError: left gap!" );
  141.     if( unbreakable(gap(g), hyph_allowed) )
  142.     { done = TRUE;  SetGap(gap(g), FALSE, TRUE, FIXED_UNIT, EDGE_MODE, 1);
  143.       Error(WARN, &fpos(g), "line break may occur here due to wide object");
  144.     }
  145.   }
  146.   if( !done ) /* else replace the wide object by an empty object */
  147.   { Error(WARN, &fpos(y), "%s object deleted (too wide for %s paragraph)",
  148.         EchoLength(size(y, COL)), EchoLength(etc_width));
  149.     tmp = MakeWord(WORD, STR_EMPTY, &fpos(x));
  150.     back(tmp, COL) = fwd(tmp, COL) = back(tmp, ROW) = fwd(tmp, ROW) = 0;
  151.     word_font(tmp) = 0;  Link(link, tmp);  DisposeChild(link);
  152.   }
  153. } /* end CorrectOversizeError */
  154.  
  155.  
  156. /*@::MoveRightToGap()@********************************************************/
  157. /*                                                                           */
  158. /*  MoveRightToGap(I, x, rlink, right, max_width, etc_width, hyph_word)      */
  159. /*                                                                           */
  160. /*  Private.  Shared by IntervalInit and IntervalShiftRightEnd, for moving   */
  161. /*  to the next gap to the right, setting save_space(newg), checking for     */
  162. /*  hyphenation case, and setting the interval badness.                      */
  163. /*                                                                           */
  164. /*****************************************************************************/
  165.  
  166. #define MoveRightToGap(I,x,rlink,right,max_width,etc_width,hyph_word)    \
  167. { OBJECT newg, foll;                            \
  168.   BOOLEAN zero_at_right = FALSE;                    \
  169.                                     \
  170.   /* search onwards to find newg, the next true breakpoint */        \
  171.   NextDefiniteWithGap(x, rlink, foll, newg);                \
  172.                                     \
  173.   /* set right link and calculate badness of the new interval */    \
  174.   if( rlink != x )                            \
  175.   {                                     \
  176.     /* set save_space(newg) now so that it is OK to forget right */    \
  177.     if( mode(gap(newg)) == TAB_MODE )                    \
  178.     { save_space(newg) = ActualGap(0, back(foll,COL), fwd(foll,COL),    \
  179.       &gap(newg), etc_width, 0) - back(foll, COL);            \
  180.     }                                    \
  181.     else                                \
  182.     { save_space(newg) = ActualGap(fwd(right, COL), back(foll, COL),    \
  183.       fwd(foll,COL), &gap(newg), etc_width,                \
  184.       I.nat_width - fwd(right,COL))                    \
  185.       - back(foll, COL) - fwd(right, COL);                \
  186.     }                                    \
  187.                                     \
  188.     /* if interval ends with hyphen, add hyph_word to nat_width */    \
  189.     /* NB ADD_HYPH is possible after a restart                  */    \
  190.     if( hyph_allowed &&                            \
  191.     (mode(gap(newg)) == HYPH_MODE || mode(gap(newg)) == ADD_HYPH) )    \
  192.     { if( is_word(type(right)) &&                     \
  193.      !(string(right)[StringLength(string(right))-1] == CH_HYPHEN) )    \
  194.       {                                    \
  195.     /* make sure hyph_word exists and is of the right font */    \
  196.     if( hyph_word == nil )                        \
  197.     { hyph_word = MakeWord(WORD, STR_HYPHEN, &fpos(x));        \
  198.       word_font(hyph_word) = 0;                    \
  199.     }                                \
  200.     if( word_font(hyph_word) != font(save_style(x)) )        \
  201.     { word_font(hyph_word) = font(save_style(x));            \
  202.       FposCopy(fpos(hyph_word), fpos(x));                \
  203.       FontWordSize(hyph_word);                    \
  204.     }                                \
  205.                                     \
  206.     mode(gap(newg)) = ADD_HYPH;                    \
  207.     I.nat_width += size(hyph_word, COL);                \
  208.     debug0(DOF, DD, "   adding hyph_word from nat_width\n");    \
  209.       }                                    \
  210.     }                                    \
  211.     else if( unbreakable(gap(newg), hyph_allowed) ) zero_at_right=TRUE;    \
  212.                                     \
  213.     I.rlink = Up(newg);                            \
  214.   }                                    \
  215.   else I.rlink = x;                            \
  216.   SetIntervalBadness(I, max_width, etc_width);                \
  217.   if( zero_at_right )  I.class = ZERO_AT_RIGHT;                \
  218. }
  219.  
  220. /*@::IntervalInit(), IntervalShiftRightEnd()@*********************************/
  221. /*                                                                           */
  222. /*  IntervalInit(I, x, max_width, etc_width, hyph_word)                      */
  223. /*                                                                           */
  224. /*  Set I to the first interval of x.                                        */
  225. /*                                                                           */
  226. /*****************************************************************************/
  227.  
  228. #define IntervalInit(I, x, max_width, etc_width, hyph_word)        \
  229. { OBJECT rlink, right;                            \
  230.   I.llink = x;                                \
  231.                                     \
  232.   FirstDefinite(x, rlink, right);                    \
  233.   if( rlink == x )  I.class = AT_END, I.rlink = x;            \
  234.   else                                    \
  235.   {                                     \
  236.     /* have first definite object, so set interval width etc. */    \
  237.     I.nat_width = size(right, COL);                    \
  238.     I.space_width = 0;                            \
  239.     I.tab_count = 0;                            \
  240.                                     \
  241.     /* move to gap, check hyphenation there etc. */            \
  242.     MoveRightToGap(I,x,rlink,right,max_width,etc_width,hyph_word);     \
  243.   }                                    \
  244. } /* end macro IntervalInit */
  245.  
  246.  
  247. /*****************************************************************************/
  248. /*                                                                           */
  249. /*  IntervalShiftRightEnd(I, x, hyph_word, max_width, etc_width)             */
  250. /*                                                                           */
  251. /*  Shift the right end of interval I one place to the right.                */
  252. /*                                                                           */
  253. /*****************************************************************************/
  254.  
  255. #define IntervalShiftRightEnd(I, x, hyph_word, max_width, etc_width)     \
  256. { OBJECT rlink, g, right;                        \
  257.   assert( I.class != AT_END, "IntervalShiftRightEnd: AT_END!" );    \
  258.   rlink = I.rlink;                            \
  259.   if( rlink == x ) I.class = AT_END;                    \
  260.   else                                    \
  261.   {                                    \
  262.     /* I is optimal here so save its badness and left endpoint */    \
  263.     Child(g, rlink);                            \
  264.     assert( type(g) == GAP_OBJ, "IntervalShiftRightEnd: type(g)!" );    \
  265.     save_badness(g) = I.badness;                    \
  266.     save_prev(g) = I.llink;                        \
  267.                                     \
  268.     /* if hyphenation case, must take away width of hyph_word */    \
  269.     if( mode(gap(g)) == ADD_HYPH )                    \
  270.     { I.nat_width -= size(hyph_word,COL);                \
  271.       debug0(DOF, DD, "   subtracting hyph_word from nat_width");    \
  272.     }                                    \
  273.                                     \
  274.     /* find definite object which must lie just to the right of g */    \
  275.     NextDefinite(x, rlink, right);                    \
  276.     assert( rlink != x, "IntervalShiftRightEnd: rlink == x!" );        \
  277.                                     \
  278.     /* modify I to reflect the addition of g and right */        \
  279.     if( mode(gap(g)) == TAB_MODE )                    \
  280.     { I.tab_count++;                            \
  281.       I.tab_pos = save_space(g);                    \
  282.       I.width_to_tab = I.nat_width;                    \
  283.       I.nat_width = save_space(g) + size(right, COL);            \
  284.       I.space_width = 0;                        \
  285.     }                                    \
  286.     else                                \
  287.     { I.nat_width += save_space(g) + size(right, COL);            \
  288.       I.space_width += save_space(g);                    \
  289.     }                                    \
  290.                                     \
  291.     /* now shift one step to the right */                \
  292.     MoveRightToGap(I, x, rlink, right, max_width, etc_width,hyph_word);    \
  293.   }                                    \
  294. } /* end macro IntervalShiftRightEnd */
  295.  
  296.  
  297. /*@::IntervalShiftLeftEnd(), IntervalBadness()@*******************************/
  298. /*                                                                           */
  299. /*  IntervalShiftLeftEnd(I, x, max_width, etc_width)                         */
  300. /*                                                                           */
  301. /*  Shift the left end of interval I one place to the right.                 */
  302. /*                                                                           */
  303. /*****************************************************************************/
  304.  
  305. #define IntervalShiftLeftEnd(I, x, max_width, etc_width)        \
  306. { OBJECT llink, left, lgap, y;                        \
  307.   debug1(DOF, DDD, "IntervalShiftLeftEnd(%s)", IntervalPrint(I, x));    \
  308.   assert( I.class != AT_END, "IntervalShiftLeftEnd: AT_END!" );        \
  309.                                     \
  310.   /* find left, the leftmost definite object of I */            \
  311.   llink = I.llink;                            \
  312.   NextDefinite(x, llink, left);                        \
  313.   assert( llink != x, "IntervalShiftLeftEnd: llink == x!" );        \
  314.                                     \
  315.   /* find lgap, the first true breakpoint following left */        \
  316.   NextDefiniteWithGap(x, llink, y, lgap);                \
  317.   assert( llink != x, "IntervalShiftLeftEnd: llink == x!" );        \
  318.                                     \
  319.   /* calculate width and badness of interval minus left and lgap */    \
  320.   if( mode(gap(lgap)) == TAB_MODE )                    \
  321.   { assert( I.tab_count > 0 || Up(lgap) == I.rlink,            \
  322.             "IntervalShiftLeftEnd: tab_count <= 0!" );    \
  323.     I.tab_count--;                            \
  324.     if( I.tab_count == 0 )  I.nat_width -= save_space(lgap);        \
  325.   }                                    \
  326.   else /* take from nat_width, or if tab, from width_to_tab */        \
  327.   { if( I.tab_count == 0 )                        \
  328.     { I.nat_width -= save_space(lgap) + size(left, COL);        \
  329.       I.space_width -= save_space(lgap);                \
  330.     }                                    \
  331.     else if( I.tab_count == 1 )                        \
  332.     { I.width_to_tab -= save_space(lgap) + size(left, COL);        \
  333.     }                                    \
  334.     /* else no changes since tabs hide them */                \
  335.   }                                    \
  336.   I.llink = Up(lgap);                            \
  337.   if( I.llink == I.rlink )  I.class = EMPTY_INTERVAL;            \
  338.   else                                    \
  339.   { SetIntervalBadness(I, max_width, etc_width);            \
  340.     if( unbreakable(gap(lgap), hyph_allowed) )  I.class = ZERO_AT_LEFT;    \
  341.   }                                    \
  342.   debug1(DOF, DDD, "IShiftLeftEnd returning %s", IntervalPrint(I, x));    \
  343. } /* end macro IntervalShiftLeftEnd */
  344.  
  345.  
  346. /*****************************************************************************/
  347. /*                                                                           */
  348. /*  IntervalBadness(I)                                                       */
  349. /*                                                                           */
  350. /*  Return the badness of interval I.                                        */
  351. /*                                                                           */
  352. /*****************************************************************************/
  353.  
  354. #define IntervalBadness(I)    (I.badness)
  355.  
  356.  
  357. /*@IntervalClass(), IntervalPrint()@******************************************/
  358. /*                                                                           */
  359. /*  IntervalClass(I)                                                         */
  360. /*                                                                           */
  361. /*  Return the badness class of interval I.                                  */
  362. /*                                                                           */
  363. /*****************************************************************************/
  364.  
  365. #define IntervalClass(I)    (I.class)
  366.  
  367.  
  368. #if DEBUG_ON
  369. /*****************************************************************************/
  370. /*                                                                           */
  371. /*  IntervalPrint(I, x)                                                      */
  372. /*                                                                           */
  373. /*  Return string image of the contents of interval I of ACAT x.             */
  374. /*                                                                           */
  375. /*****************************************************************************/
  376.  
  377. FULL_CHAR *IntervalPrint(I, x)
  378. INTERVAL I;  OBJECT x;
  379. { static char *class_name[] =
  380.     { "TOO_LOOSE", "LOOSE", "TIGHT", "TOO_TIGHT", "TAB_OVERLAP", "AT_END",
  381.       "ZERO_AT_LEFT", "ZERO_AT_RIGHT" };
  382.   static FULL_CHAR res[300];
  383.   OBJECT link, y, g, prev, z; int i;
  384.   if( I.llink == I.rlink )  return AsciiToFull("[]");
  385.   StringCopy(res, AsciiToFull("["));
  386.   g = nil;
  387.   for( link = NextDown(I.llink);  link != I.rlink;  link = NextDown(link) )
  388.   { assert(link != x, "IntervalPrint: link == x!");
  389.     Child(y, link);
  390.     assert(y != x, "IntervalPrint: y == x!");
  391.     if( type(y) == GAP_OBJ )
  392.     { g = y;
  393.       if( Down(g) != g )
  394.       {    Child(z, Down(g));
  395.     StringCat(res, STR_SPACE);
  396.     StringCat(res, EchoCatOp(ACAT, mark(gap(g)), join(gap(g)))),
  397.     StringCat(res, is_word(type(z)) ? string(z) : Image(type(z)));
  398.     StringCat(res, STR_SPACE);
  399.       }
  400.       else for( i = 1;  i <= hspace(g) + vspace(g); i++ )
  401.          StringCat(res, STR_SPACE);
  402.     }
  403.     else StringCat(res, is_word(type(z)) ? string(z) : Image(type(z)));
  404.   }
  405.   StringCat(res, AsciiToFull("] n"));
  406.   StringCat(res, EchoLength(I.nat_width));
  407.   StringCat(res, AsciiToFull(", "));
  408.   StringCat(res, EchoLength(I.space_width));
  409.   StringCat(res, AsciiToFull(" ("));
  410.   StringCat(res, AsciiToFull(class_name[I.class]));
  411.   StringCat(res, AsciiToFull(" "));
  412.   StringCat(res, StringInt(I.badness));
  413.   StringCat(res, AsciiToFull(")"));
  414.   if( I.tab_count > 0 )
  415.   { StringCat(res, AsciiToFull(" <"));
  416.     StringCat(res, StringInt(I.tab_count));
  417.     StringCat(res, STR_SPACE);
  418.     StringCat(res, EchoLength(I.width_to_tab));
  419.     StringCat(res, AsciiToFull(":"));
  420.     StringCat(res, EchoLength(I.tab_pos));
  421.     StringCat(res, AsciiToFull(">"));
  422.   }
  423.   return res;
  424. } /* end IntervalPrint */
  425. #endif
  426.  
  427.  
  428. /*@::FillObject()@************************************************************/
  429. /*                                                                           */
  430. /*  FillObject(x, c)                                                         */
  431. /*                                                                           */
  432. /*  Break ACAT x into lines using optimal breakpoints.                       */
  433. /*                                                                           */
  434. /*****************************************************************************/
  435.  
  436. OBJECT FillObject(x, c)
  437. OBJECT x;  CONSTRAINT *c;
  438. { INTERVAL I, BestI;  OBJECT res, gp, tmp, z, y, link, prev;
  439.   LENGTH max_width, etc_width, outdent_margin, f;
  440.   static OBJECT hyph_word = nil;
  441.   BOOLEAN can_hyphenate;    /* TRUE when it is possible to call Hyphenate() */
  442.   BOOLEAN hyph_allowed;        /* TRUE when hyphenation of words is permitted  */
  443.   assert( type(x) == ACAT, "FillObject: type(x) != ACAT!" );
  444.  
  445.   /* set max_width (width of 1st line) and etc_width (width of later lines) */
  446.   max_width = min(fc(*c), bfc(*c));
  447.   if( display_style(save_style(x)) == DISPLAY_OUTDENT )
  448.   { outdent_margin = 2 * FontSize(font(save_style(x)), x);
  449.     etc_width = max_width - outdent_margin;
  450.   }
  451.   else etc_width = max_width;
  452.   assert( size(x, COL) > max_width, "FillObject: initial size!" );
  453.  
  454.   /* add &1rt {} to end of paragraph */
  455.   gp = New(GAP_OBJ);  hspace(gp) = 1;  vspace(gp) = 0;
  456.   SetGap(gap(gp), FALSE, TRUE, AVAIL_UNIT, TAB_MODE, 1*FR);
  457.   tmp = MakeWord(WORD, STR_GAP_RJUSTIFY, &fpos(x));
  458.   Link(gp, tmp);  Link(x, gp);
  459.   tmp = MakeWord(WORD, STR_EMPTY, &fpos(x));
  460.   back(tmp, COL) = fwd(tmp, COL) = back(tmp, ROW) = fwd(tmp, ROW) = 0;
  461.   word_font(tmp) = 0;
  462.   Link(x, tmp);
  463.   debug2(DOF, D, "FillObject(x, %s); %s",
  464.     EchoConstraint(c), EchoStyle(&save_style(x)));
  465.   ifdebug(DOF, DD, DebugObject(x); fprintf(stderr, "\n\n") );
  466.  
  467.   /* initially we can hyphenate if hyphenation is on, but not first pass */
  468.   if( hyph_style(save_style(x)) == HYPH_UNDEF )
  469.     Error(FATAL, &fpos(x), "hyphen or nohyphen option missing");
  470.   can_hyphenate = (hyph_style(save_style(x)) == HYPH_ON);
  471.   hyph_allowed = FALSE;
  472.  
  473.   /* initialize I to first interval, BestI to best ending here, and run */
  474.   RESTART:
  475.   IntervalInit(I, x, max_width, etc_width, hyph_word);  BestI = I;
  476.   while( IntervalClass(I) != AT_END )
  477.   {
  478.     debug1(DOF, D, "loop:  %s", IntervalPrint(I, x));
  479.     switch( IntervalClass(I) )
  480.     {
  481.  
  482.       case TOO_LOOSE:
  483.       
  484.     /* too loose, so save best and shift right end */
  485.     if( IntervalBadness(BestI) < IntervalBadness(I) )  I = BestI;
  486.     debug1(DOF, D, "BestI: %s\n", IntervalPrint(I, x));
  487.     /* NB no break */
  488.  
  489.  
  490.       case ZERO_AT_RIGHT:
  491.  
  492.     IntervalShiftRightEnd(I, x, hyph_word, max_width, etc_width);
  493.     BestI = I;
  494.     break;
  495.  
  496.  
  497.       case LOOSE:
  498.       case TIGHT:
  499.       
  500.     /* reasonable, so check best and shift left end */
  501.     if( IntervalBadness(I) < IntervalBadness(BestI) )  BestI = I;
  502.     /* NB no break */
  503.  
  504.  
  505.       case ZERO_AT_LEFT:
  506.       case TAB_OVERLAP:
  507.       case TOO_TIGHT:
  508.       
  509.     /* too tight, or zero-width gap at left end, so shift left end */
  510.     IntervalShiftLeftEnd(I, x, max_width, etc_width);
  511.     break;
  512.  
  513.  
  514.       case EMPTY_INTERVAL:
  515.  
  516.     PrevDefinite(x, I.llink, y);
  517.     if( can_hyphenate )
  518.     { x = Hyphenate(x);
  519.       can_hyphenate = FALSE;
  520.       hyph_allowed = TRUE;
  521.     }
  522.     else CorrectOversizeError(x, I.llink, y, etc_width, hyph_allowed);
  523.     goto RESTART;
  524.     break;
  525.  
  526.  
  527.       default:
  528.       
  529.     Error(INTERN, &fpos(x), "FillObject: unknown interval class!");
  530.     break;
  531.  
  532.     }
  533.   }
  534.  
  535.   /* do end processing */
  536.   ifdebug(DOF, D,
  537.     debug0(DOF, D, "final result:");
  538.     debug1(DOF, D, "%s", IntervalPrint(BestI, x));
  539.     while( BestI.llink != x )
  540.     { BestI.rlink = BestI.llink;
  541.       Child(gp, BestI.rlink);
  542.       BestI.llink = save_prev(gp);
  543.       debug1(DOF, D, "%s", IntervalPrint(BestI, x));
  544.     }
  545.   );
  546.  
  547.   if( I.llink == x )
  548.   { /* since line did not fit initally, this must mean either that a large  */
  549.     /* word was discarded, or else that the line was only slightly tight    */
  550.     res = x;
  551.     back(res, COL) = 0;  fwd(res, COL) = max_width;
  552.   }
  553.   else if( can_hyphenate && IntervalBadness(BestI) > HYPH_BAD )
  554.   { x = Hyphenate(x);
  555.     can_hyphenate = FALSE;
  556.     hyph_allowed = TRUE;
  557.     goto RESTART;
  558.   }
  559.   else
  560.   { OBJECT lgap, llink;
  561.     res = New(VCAT);
  562.     back(res, COL) = 0;  fwd(res, COL) = max_width;
  563.     ReplaceNode(res, x);
  564.     llink = I.llink;
  565.  
  566.     /* break the lines of x */
  567.     while( llink != x )
  568.     { y = New(ACAT);
  569.       FposCopy(fpos(y), fpos(x));
  570.       StyleCopy(save_style(y), save_style(x));
  571.       if( Down(res) != res &&
  572.         (display_style(save_style(y)) == DISPLAY_ADJUST ||
  573.          display_style(save_style(y)) == DISPLAY_OUTDENT) )
  574.      display_style(save_style(y)) = DO_ADJUST;
  575.       back(y, COL) = 0;
  576.       fwd(y, COL) = max_width;
  577.  
  578.       /* if outdented paragraphs, add 2.0f @Wide & to front of new line */
  579.       if( display_style(save_style(x)) == DISPLAY_OUTDENT )
  580.       {
  581.     OBJECT t1, t2, z;
  582.     t1 = MakeWord(WORD, STR_EMPTY, &fpos(x));
  583.     back(t1, COL) = fwd(t1, COL) = back(t1, ROW) = fwd(t1, ROW) = 0;
  584.     word_font(t1) = 0;
  585.     t2 = New(WIDE);
  586.     SetConstraint(constraint(t2), MAX_LEN, outdent_margin, MAX_LEN);
  587.     back(t2, COL) = 0;  fwd(t2, COL) = outdent_margin;
  588.     Link(t2, t1);
  589.     Link(y, t2);
  590.     z = New(GAP_OBJ);
  591.     hspace(z) = vspace(z) = 0;
  592.     SetGap(gap(z), FALSE, TRUE, FIXED_UNIT, EDGE_MODE, 0);
  593.     Link(y, z);
  594.       }
  595.  
  596.       /* move the line to below y */
  597.       TransferLinks(NextDown(llink), x, y);
  598.  
  599.       /* add hyphen to end of previous line, if lgap is ADD_HYPH */
  600.       Child(lgap, llink);
  601.       if( mode(gap(lgap)) == ADD_HYPH )
  602.       { OBJECT z = New(GAP_OBJ);
  603.     debug0(DOF, DD, "   adding hyphen\n");
  604.     hspace(z) = vspace(z) = 0;
  605.     SetGap(gap(z), FALSE, TRUE, FIXED_UNIT, EDGE_MODE, 0);
  606.     Link(x, z);
  607.     z = MakeWord(WORD, STR_HYPHEN, &fpos(y));
  608.     word_font(z) = font(save_style(x));
  609.     FontWordSize(z);
  610.     Link(x, z);
  611.       }
  612.  
  613.       /* attach y to res, recycle lgap for gap separating the two lines */
  614.       Link(NextDown(res), y);
  615.       MoveLink(llink, NextDown(res), PARENT);
  616.       hspace(lgap) = 0;
  617.       vspace(lgap) = 1;
  618.       GapCopy(gap(lgap), line_gap(save_style(x)));
  619.  
  620.       /* move on to previous line */
  621.       llink = save_prev(lgap);
  622.     }
  623.  
  624.     /* attach first line, x, to res */
  625.     Link(NextDown(res), x);
  626.     back(x, COL) = 0;
  627.     fwd(x, COL) = max_width;
  628.     if( display_style(save_style(x)) == DISPLAY_ADJUST ||
  629.     display_style(save_style(x)) == DISPLAY_OUTDENT )
  630.       display_style(save_style(x)) = DO_ADJUST;
  631.  
  632.     /* delete the final &1rt {} from the last line, to help clines */
  633.     Child(y, LastDown(res));
  634.     assert( Down(y) != LastDown(y), "FillObject: empty last line!" );
  635.     Child(z, LastDown(y));
  636.     assert( type(z)==WORD && string(z)[0] == '\0', "FillObject: last word!" );
  637.     DisposeChild(LastDown(y));
  638.     Child(z, LastDown(y));
  639.     assert( type(z) == GAP_OBJ, "FillObject: last gap_obj!" );
  640.     DisposeChild(LastDown(y));
  641.  
  642.     /* recalculate the width of the last line, since it is smaller */
  643.     FirstDefinite(y, link, z);
  644.     assert( link != y, "FillObject: last line is empty!" );
  645.     f = back(z, COL);  prev = z;
  646.     NextDefiniteWithGap(y, link, z, gp);
  647.     while( link != y )
  648.     {
  649.       f += MinGap(fwd(prev, COL), back(y, COL), fwd(y, COL), &gap(gp));
  650.       prev = z;
  651.       NextDefiniteWithGap(y, link, z, gp);
  652.     }
  653.     fwd(y, COL) = f + fwd(prev, COL);
  654.  
  655.     /* make last line DO_ADJUST if it is oversize */
  656.     if( size(y, COL) > max_width )  display_style(save_style(y)) = DO_ADJUST;
  657.   }
  658.  
  659.   debug0(DOF, D, "FillObject exiting");
  660.   return res;
  661. } /* end FillObject */
  662.