src/fmt.c

   1 /* GNU fmt -- simple text formatter.
   2    Copyright (C) 94, 95, 1996 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* Written by Ross Paterson <rap@doc.ic.ac.uk>.  */
  19
  20 #include <config.h>
  21 #include <stdio.h>
  22 #include <sys/types.h>
  23 #include <getopt.h>
  24
  25 #if HAVE_LIMITS_H
  26 # include <limits.h>
  27 #endif
  28
  29 #ifndef UINT_MAX
  30 # define UINT_MAX ((unsigned int) ~(unsigned int) 0)
  31 #endif
  32
  33 #ifndef INT_MAX
  34 # define INT_MAX ((int) (UINT_MAX >> 1))
  35 #endif
  36
  37 /* Redefine.  Otherwise, systems (Unicos for one) with headers that define
  38    it to be a type get syntax errors for the variable declaration below.  */
  39 #define word unused_word_type
  40
  41 #include "system.h"
  42 #include "error.h"
  43 #include "xstrtol.h"
  44
  45 /* The following parameters represent the program's idea of what is
  46    "best".  Adjust to taste, subject to the caveats given.  */
  47
  48 /* Default longest permitted line length (max_width).  */
  49 #define WIDTH   75
  50
  51 /* Prefer lines to be LEEWAY % shorter than the maximum width, giving
  52    room for optimization.  */
  53 #define LEEWAY  7
  54
  55 /* The default secondary indent of tagged paragraph used for unindented
  56    one-line paragraphs not preceded by any multi-line paragraphs.  */
  57 #define DEF_INDENT 3
  58
  59 /* Costs and bonuses are expressed as the equivalent departure from the
  60    optimal line length, multiplied by 10.  e.g. assigning something a
  61    cost of 50 means that it is as bad as a line 5 characters too short
  62    or too long.  The definition of SHORT_COST(n) should not be changed.
  63    However, EQUIV(n) may need tuning.  */
  64
  65 typedef long COST;
  66
  67 #define MAXCOST (~(((unsigned long) 1) << (8 * sizeof (COST) -1)))
  68
  69 #define SQR(n)          ((n) * (n))
  70 #define EQUIV(n)        SQR ((COST) (n))
  71
  72 /* Cost of a filled line n chars longer or shorter than best_width.  */
  73 #define SHORT_COST(n)   EQUIV ((n) * 10)
  74
  75 /* Cost of the difference between adjacent filled lines.  */
  76 #define RAGGED_COST(n)  (SHORT_COST (n) / 2)
  77
  78 /* Basic cost per line.  */
  79 #define LINE_COST       EQUIV (70)
  80
  81 /* Cost of breaking a line after the first word of a sentence, where
  82    the length of the word is N.  */
  83 #define WIDOW_COST(n)   (EQUIV (200) / ((n) + 2))
  84
  85 /* Cost of breaking a line before the last word of a sentence, where
  86    the length of the word is N.  */
  87 #define ORPHAN_COST(n)  (EQUIV (150) / ((n) + 2))
  88
  89 /* Bonus for breaking a line at the end of a sentence.  */
  90 #define SENTENCE_BONUS  EQUIV (50)
  91
  92 /* Cost of breaking a line after a period not marking end of a sentence.
  93    With the definition of sentence we are using (borrowed from emacs, see
  94    get_line()) such a break would then look like a sentence break.  Hence
  95    we assign a very high cost -- it should be avoided unless things are
  96    really bad.  */
  97 #define NOBREAK_COST    EQUIV (600)
  98
  99 /* Bonus for breaking a line before open parenthesis.  */
 100 #define PAREN_BONUS     EQUIV (40)
 101
 102 /* Bonus for breaking a line after other punctuation.  */
 103 #define PUNCT_BONUS     EQUIV(40)
 104
 105 /* Credit for breaking a long paragraph one line later.  */
 106 #define LINE_CREDIT     EQUIV(3)
 107
 108 /* Size of paragraph buffer, in words and characters.  Longer paragraphs
 109    are handled neatly (cf. flush_paragraph()), so there's little to gain
 110    by making these larger.  */
 111 #define MAXWORDS        1000
 112 #define MAXCHARS        5000
 113
 114 /* Extra ctype(3)-style macros.  */
 115
 116 #define isopen(c)       (strchr ("([`'\"", c) != NULL)
 117 #define isclose(c)      (strchr (")]'\"", c) != NULL)
 118 #define isperiod(c)     (strchr (".?!", c) != NULL)
 119
 120 /* Size of a tab stop, for expansion on input and re-introduction on
 121    output.  */
 122 #define TABWIDTH        8
 123
 124 /* Miscellaneous definitions.  */
 125
 126 typedef unsigned int bool;
 127 #undef TRUE
 128 #define TRUE    1
 129 #undef FALSE
 130 #define FALSE   0
 131
 132 /* Word descriptor structure.  */
 133
 134 typedef struct Word WORD;
 135
 136 struct Word
 137   {
 138
 139     /* Static attributes determined during input.  */
 140
 141     const char *text;           /* the text of the word */
 142     short length;               /* length of this word */
 143     short space;                /* the size of the following space */
 144     bool paren:1;               /* starts with open paren */
 145     bool period:1;              /* ends in [.?!])* */
 146     bool punct:1;               /* ends in punctuation */
 147     bool final:1;               /* end of sentence */
 148
 149     /* The remaining fields are computed during the optimization.  */
 150
 151     short line_length;          /* length of the best line starting here */
 152     COST best_cost;             /* cost of best paragraph starting here */
 153     WORD *next_break;           /* break which achieves best_cost */
 154   };
 155
 156 /* Forward declarations.  */
 157
 158 static void set_prefix __P ((char *p));
 159 static void fmt __P ((FILE *f));
 160 static bool get_paragraph __P ((FILE *f));
 161 static int get_line __P ((FILE *f, int c));
 162 static int get_prefix __P ((FILE *f));
 163 static int get_space __P ((FILE *f, int c));
 164 static int copy_rest __P ((FILE *f, int c));
 165 static bool same_para __P ((int c));
 166 static void flush_paragraph __P ((void));
 167 static void fmt_paragraph __P ((void));
 168 static void check_punctuation __P ((WORD *w));
 169 static COST base_cost __P ((WORD *this));
 170 static COST line_cost __P ((WORD *next, int len));
 171 static void put_paragraph __P ((WORD *finish));
 172 static void put_line __P ((WORD *w, int indent));
 173 static void put_word __P ((WORD *w));
 174 static void put_space __P ((int space));
 175
 176 /* The name this program was run with.  */
 177 const char *program_name;
 178
 179 /* If nonzero, display usage information and exit.  */
 180 static int show_help = 0;
 181
 182 /* If nonzero, print the version on standard output and exit.  */
 183 static int show_version = 0;
 184
 185 /* Option values.  */
 186
 187 /* If TRUE, first 2 lines may have different indent (default FALSE).  */
 188 static bool crown;
 189
 190 /* If TRUE, first 2 lines _must_ have different indent (default FALSE).  */
 191 static bool tagged;
 192
 193 /* If TRUE, each line is a paragraph on its own (default FALSE).  */
 194 static bool split;
 195
 196 /* If TRUE, don't preserve inter-word spacing (default FALSE).  */
 197 static bool uniform;
 198
 199 /* Prefix minus leading and trailing spaces (default "").  */
 200 static const char *prefix;
 201
 202 /* User-supplied maximum line width (default WIDTH).  The only output
 203    lines
 204    longer than this will each comprise a single word.  */
 205 static int max_width;
 206
 207 /* Values derived from the option values.  */
 208
 209 /* The length of prefix minus leading space.  */
 210 static int prefix_full_length;
 211
 212 /* The length of the leading space trimmed from the prefix.  */
 213 static int prefix_lead_space;
 214
 215 /* The length of prefix minus leading and trailing space.  */
 216 static int prefix_length;
 217
 218 /* The preferred width of text lines, set to LEEWAY % less than max_width.  */
 219 static int best_width;
 220
 221 /* Dynamic variables.  */
 222
 223 /* Start column of the character most recently read from the input file.  */
 224 static int in_column;
 225
 226 /* Start column of the next character to be written to stdout.  */
 227 static int out_column;
 228
 229 /* Space for the paragraph text -- longer paragraphs are handled neatly
 230    (cf. flush_paragraph()).  */
 231 static char parabuf[MAXCHARS];
 232
 233 /* A pointer into parabuf, indicating the first unused character position.  */
 234 static char *wptr;
 235
 236 /* The words of a paragraph -- longer paragraphs are handled neatly
 237    (cf. flush_paragraph()).  */
 238 static WORD word[MAXWORDS];
 239
 240 /* A pointer into the above word array, indicating the first position
 241    after the last complete word.  Sometimes it will point at an incomplete
 242    word.  */
 243 static WORD *word_limit;
 244
 245 /* If TRUE, current input file contains tab characters, and so tabs can be
 246    used for white space on output.  */
 247 static bool tabs;
 248
 249 /* Space before trimmed prefix on each line of the current paragraph.  */
 250 static int prefix_indent;
 251
 252 /* Indentation of the first line of the current paragraph.  */
 253 static int first_indent;
 254
 255 /* Indentation of other lines of the current paragraph */
 256 static int other_indent;
 257
 258 /* To detect the end of a paragraph, we need to look ahead to the first
 259    non-blank character after the prefix on the next line, or the first
 260    character on the following line that failed to match the prefix.
 261    We can reconstruct the lookahead from that character (next_char), its
 262    position on the line (in_column) and the amount of space before the
 263    prefix (next_prefix_indent).  See get_paragraph() and copy_rest().  */
 264
 265 /* The last character read from the input file.  */
 266 static int next_char;
 267
 268 /* The space before the trimmed prefix (or part of it) on the next line
 269    after the current paragraph.  */
 270 static int next_prefix_indent;
 271
 272 /* If nonzero, the length of the last line output in the current
 273    paragraph, used to charge for raggedness at the split point for long
 274    paragraphs chosen by fmt_paragraph().  */
 275 static int last_line_length;
 276
 277 static void
 278 usage (int status)
 279 {
 280   if (status != 0)
 281     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 282              program_name);
 283   else
 284     {
 285       printf (_("Usage: %s [-DIGITS] [OPTION]... [FILE]...\n"), program_name);
 286       fputs (_("\
 287 Reformat each paragraph in the FILE(s), writing to standard output.\n\
 288 If no FILE or if FILE is `-', read standard input.\n\
 289 \n\
 290 Mandatory arguments to long options are mandatory for short options too.\n\
 291   -c, --crown-margin        preserve indentation of first two lines\n\
 292   -p, --prefix=STRING       combine only lines having STRING as prefix\n\
 293   -s, --split-only          split long lines, but do not refill\n\
 294   -t, --tagged-paragraph    indentation of first line different from second\n\
 295   -u, --uniform-spacing     one space between words, two after sentences\n\
 296   -w, --width=NUMBER        maximum line width (default of 75 columns)\n\
 297       --help                display this help and exit\n\
 298       --version             output version information and exit\n\
 299 \n\
 300 In -wNUMBER, the letter `w' may be omitted.\n"),
 301              stdout);
 302       puts (_("\nReport bugs to textutils-bugs@gnu.ai.mit.edu"));
 303     }
 304   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 305 }
 306
 307 /* Decode options and launch execution.  */
 308
 309 static const struct option long_options[] =
 310 {
 311   {"crown-margin", no_argument, NULL, 'c'},
 312   {"help", no_argument, &show_help, 1},
 313   {"prefix", required_argument, NULL, 'p'},
 314   {"split-only", no_argument, NULL, 's'},
 315   {"tagged-paragraph", no_argument, NULL, 't'},
 316   {"uniform-spacing", no_argument, NULL, 'u'},
 317   {"version", no_argument, &show_version, 1},
 318   {"width", required_argument, NULL, 'w'},
 319   {0, 0, 0, 0},
 320 };
 321
 322 int
 323 main (register int argc, register char **argv)
 324 {
 325   int optchar;
 326   FILE *infile;
 327
 328   program_name = argv[0];
 329   setlocale (LC_ALL, "");
 330   bindtextdomain (PACKAGE, LOCALEDIR);
 331   textdomain (PACKAGE);
 332
 333   crown = tagged = split = uniform = FALSE;
 334   max_width = WIDTH;
 335   prefix = "";
 336   prefix_length = prefix_lead_space = prefix_full_length = 0;
 337
 338   if (argc > 1 && argv[1][0] == '-' && ISDIGIT (argv[1][1]))
 339     {
 340       max_width = 0;
 341       /* Old option syntax; a dash followed by one or more digits.
 342          Move past the number. */
 343       for (++argv[1]; ISDIGIT (*argv[1]); ++argv[1])
 344         {
 345           /* FIXME: use strtol to detect overflow.  */
 346           max_width = max_width * 10 + *argv[1] - '0';
 347         }
 348       /* Make the options we just parsed invisible to getopt. */
 349       argv[1] = argv[0];
 350       argv++;
 351       argc--;
 352     }
 353
 354   while ((optchar = getopt_long (argc, argv, "0123456789cstuw:p:",
 355                                  long_options, NULL))
 356          != -1)
 357     switch (optchar)
 358       {
 359       default:
 360         usage (1);
 361
 362       case 0:
 363         break;
 364
 365       case 'c':
 366         crown = TRUE;
 367         break;
 368
 369       case 's':
 370         split = TRUE;
 371         break;
 372
 373       case 't':
 374         tagged = TRUE;
 375         break;
 376
 377       case 'u':
 378         uniform = TRUE;
 379         break;
 380
 381       case 'w':
 382         {
 383           long int tmp_long;
 384           if (xstrtol (optarg, NULL, 10, &tmp_long, "") != LONGINT_OK
 385               || tmp_long <= 0 || tmp_long > INT_MAX)
 386             error (EXIT_FAILURE, 0, _("invalid line number increment: `%s'"),
 387                    optarg);
 388           max_width = (int) tmp_long;
 389         }
 390         break;
 391
 392       case 'p':
 393         set_prefix (optarg);
 394         break;
 395
 396       }
 397
 398   if (show_version)
 399     {
 400       printf ("fmt (%s) %s\n", GNU_PACKAGE, VERSION);
 401       exit (EXIT_SUCCESS);
 402     }
 403
 404   if (show_help)
 405     usage (0);
 406
 407   best_width = max_width * (2 * (100 - LEEWAY) + 1) / 200;
 408
 409   if (optind == argc)
 410     fmt (stdin);
 411   else
 412     for (; optind < argc; optind++)
 413       if (strcmp (argv[optind], "-") == 0)
 414         fmt (stdin);
 415       else
 416         {
 417           infile = fopen (argv[optind], "r");
 418           if (infile != NULL)
 419             {
 420               fmt (infile);
 421               fclose (infile);
 422             }
 423           else
 424             error (0, errno, argv[optind]);
 425         }
 426
 427   exit (EXIT_SUCCESS);
 428 }
 429
 430 /* Trim space from the front and back of the string P, yielding the prefix,
 431    and record the lengths of the prefix and the space trimmed.  */
 432
 433 static void
 434 set_prefix (register char *p)
 435 {
 436   register char *s;
 437
 438   prefix_lead_space = 0;
 439   while (*p == ' ')
 440     {
 441       prefix_lead_space++;
 442       p++;
 443     }
 444   prefix = p;
 445   prefix_full_length = strlen (p);
 446   s = p + prefix_full_length;
 447   while (s > p && s[-1] == ' ')
 448     s--;
 449   *s = '\0';
 450   prefix_length = s - p;
 451 }
 452
 453 /* read file F and send formatted output to stdout.  */
 454
 455 static void
 456 fmt (FILE *f)
 457 {
 458   tabs = FALSE;
 459   other_indent = 0;
 460   next_char = get_prefix (f);
 461   while (get_paragraph (f))
 462     {
 463       fmt_paragraph ();
 464       put_paragraph (word_limit);
 465     }
 466 }
 467
 468 /* Read a paragraph from input file F.  A paragraph consists of a
 469    maximal number of non-blank (excluding any prefix) lines subject to:
 470    * In split mode, a paragraph is a single non-blank line.
 471    * In crown mode, the second and subsequent lines must have the
 472    same indentation, but possibly different from the indent of the
 473    first line.
 474    * Tagged mode is similar, but the first and second lines must have
 475    different indentations.
 476    * Otherwise, all lines of a paragraph must have the same indent.
 477    If a prefix is in effect, it must be present at the same indent for
 478    each line in the paragraph.
 479
 480    Return FALSE if end-of-file was encountered before the start of a
 481    paragraph, else TRUE.  */
 482
 483 static bool
 484 get_paragraph (FILE *f)
 485 {
 486   register int c;
 487
 488   last_line_length = 0;
 489   c = next_char;
 490
 491   /* Scan (and copy) blank lines, and lines not introduced by the prefix.  */
 492
 493   while (c == '\n' || c == EOF
 494          || next_prefix_indent < prefix_lead_space
 495          || in_column < next_prefix_indent + prefix_full_length)
 496     {
 497       c = copy_rest (f, c);
 498       if (c == EOF)
 499         {
 500           next_char = EOF;
 501           return FALSE;
 502         }
 503       putchar ('\n');
 504       c = get_prefix (f);
 505     }
 506
 507   /* Got a suitable first line for a paragraph.  */
 508
 509   prefix_indent = next_prefix_indent;
 510   first_indent = in_column;
 511   wptr = parabuf;
 512   word_limit = word;
 513   c = get_line (f, c);
 514
 515   /* Read rest of paragraph (unless split is specified).  */
 516
 517   if (split)
 518     other_indent = first_indent;
 519   else if (crown)
 520     {
 521       if (same_para (c))
 522         {
 523           other_indent = in_column;
 524           do
 525             {                   /* for each line till the end of the para */
 526               c = get_line (f, c);
 527             }
 528           while (same_para (c) && in_column == other_indent);
 529         }
 530       else
 531         other_indent = first_indent;
 532     }
 533   else if (tagged)
 534     {
 535       if (same_para (c) && in_column != first_indent)
 536         {
 537           other_indent = in_column;
 538           do
 539             {                   /* for each line till the end of the para */
 540               c = get_line (f, c);
 541             }
 542           while (same_para (c) && in_column == other_indent);
 543         }
 544
 545       /* Only one line: use the secondary indent from last time if it
 546          splits, or 0 if there have been no multi-line paragraphs in the
 547          input so far.  But if these rules make the two indents the same,
 548          pick a new secondary indent.  */
 549
 550       else if (other_indent == first_indent)
 551         other_indent = first_indent == 0 ? DEF_INDENT : 0;
 552     }
 553   else
 554     {
 555       other_indent = first_indent;
 556       while (same_para (c) && in_column == other_indent)
 557         c = get_line (f, c);
 558     }
 559   (word_limit - 1)->period = (word_limit - 1)->final = TRUE;
 560   next_char = c;
 561   return TRUE;
 562 }
 563
 564 /* Copy to the output a line that failed to match the prefix, or that
 565    was blank after the prefix.  In the former case, C is the character
 566    that failed to match the prefix.  In the latter, C is \n or EOF.
 567    Return the character (\n or EOF) ending the line.  */
 568
 569 static int
 570 copy_rest (FILE *f, register int c)
 571 {
 572   register const char *s;
 573
 574   out_column = 0;
 575   if (in_column > next_prefix_indent && c != '\n' && c != EOF)
 576     {
 577       put_space (next_prefix_indent);
 578       for (s = prefix; out_column != in_column && *s; out_column++)
 579         putchar (*s++);
 580       put_space (in_column - out_column);
 581     }
 582   while (c != '\n' && c != EOF)
 583     {
 584       putchar (c);
 585       c = getc (f);
 586     }
 587   return c;
 588 }
 589
 590 /* Return TRUE if a line whose first non-blank character after the
 591    prefix (if any) is C could belong to the current paragraph,
 592    otherwise FALSE.  */
 593
 594 static bool
 595 same_para (register int c)
 596 {
 597   return (next_prefix_indent == prefix_indent
 598           && in_column >= next_prefix_indent + prefix_full_length
 599           && c != '\n' && c != EOF);
 600 }
 601
 602 /* Read a line from input file F, given first non-blank character C
 603    after the prefix, and the following indent, and break it into words.
 604    A word is a maximal non-empty string of non-white characters.  A word
 605    ending in [.?!]["')\]]* and followed by end-of-line or at least two
 606    spaces ends a sentence, as in emacs.
 607
 608    Return the first non-blank character of the next line.  */
 609
 610 static int
 611 get_line (FILE *f, register int c)
 612 {
 613   int start;
 614   register char *end_of_parabuf;
 615   register WORD *end_of_word;
 616
 617   end_of_parabuf = &parabuf[MAXCHARS];
 618   end_of_word = &word[MAXWORDS - 2];
 619
 620   do
 621     {                           /* for each word in a line */
 622
 623       /* Scan word.  */
 624
 625       word_limit->text = wptr;
 626       do
 627         {
 628           if (wptr == end_of_parabuf)
 629             flush_paragraph ();
 630           *wptr++ = c;
 631           c = getc (f);
 632         }
 633       while (c != EOF && !ISSPACE (c));
 634       in_column += word_limit->length = wptr - word_limit->text;
 635       check_punctuation (word_limit);
 636
 637       /* Scan inter-word space.  */
 638
 639       start = in_column;
 640       c = get_space (f, c);
 641       word_limit->space = in_column - start;
 642       word_limit->final = (c == EOF
 643                            || (word_limit->period
 644                                && (c == '\n' || word_limit->space > 1)));
 645       if (c == '\n' || c == EOF || uniform)
 646         word_limit->space = word_limit->final ? 2 : 1;
 647       if (word_limit == end_of_word)
 648         flush_paragraph ();
 649       word_limit++;
 650       if (c == EOF)
 651         return EOF;
 652     }
 653   while (c != '\n');
 654   return get_prefix (f);
 655 }
 656
 657 /* Read a prefix from input file F.  Return either first non-matching
 658    character, or first non-blank character after the prefix.  */
 659
 660 static int
 661 get_prefix (FILE *f)
 662 {
 663   register int c;
 664   register const char *p;
 665
 666   in_column = 0;
 667   c = get_space (f, getc (f));
 668   if (prefix_length == 0)
 669     next_prefix_indent = prefix_lead_space < in_column ?
 670       prefix_lead_space : in_column;
 671   else
 672     {
 673       next_prefix_indent = in_column;
 674       for (p = prefix; *p != '\0'; p++)
 675         {
 676           if (c != *p)
 677             return c;
 678           in_column++;
 679           c = getc (f);
 680         }
 681       c = get_space (f, c);
 682     }
 683   return c;
 684 }
 685
 686 /* Read blank characters from input file F, starting with C, and keeping
 687    in_column up-to-date.  Return first non-blank character.  */
 688
 689 static int
 690 get_space (FILE *f, register int c)
 691 {
 692   for (;;)
 693     {
 694       if (c == ' ')
 695         in_column++;
 696       else if (c == '\t')
 697         {
 698           tabs = TRUE;
 699           in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
 700         }
 701       else
 702         return c;
 703       c = getc (f);
 704     }
 705 }
 706
 707 /* Set extra fields in word W describing any attached punctuation.  */
 708
 709 static void
 710 check_punctuation (register WORD *w)
 711 {
 712   register const char *start, *finish;
 713
 714   start = w->text;
 715   finish = start + (w->length - 1);
 716   w->paren = isopen (*start);
 717   w->punct = ISPUNCT (*finish);
 718   while (isclose (*finish) && finish > start)
 719     finish--;
 720   w->period = isperiod (*finish);
 721 }
 722
 723 /* Flush part of the paragraph to make room.  This function is called on
 724    hitting the limit on the number of words or characters.  */
 725
 726 static void
 727 flush_paragraph (void)
 728 {
 729   WORD *split_point;
 730   register WORD *w;
 731   int shift;
 732   COST best_break;
 733
 734   /* In the special case where it's all one word, just flush it.  */
 735
 736   if (word_limit == word)
 737     {
 738       printf ("%*s", wptr - parabuf, parabuf);
 739       wptr = parabuf;
 740       return;
 741     }
 742
 743   /* Otherwise:
 744      - format what you have so far as a paragraph,
 745      - find a low-cost line break near the end,
 746      - output to there,
 747      - make that the start of the paragraph.  */
 748
 749   fmt_paragraph ();
 750
 751   /* Choose a good split point.  */
 752
 753   split_point = word_limit;
 754   best_break = MAXCOST;
 755   for (w = word->next_break; w != word_limit; w = w->next_break)
 756     {
 757       if (w->best_cost - w->next_break->best_cost < best_break)
 758         {
 759           split_point = w;
 760           best_break = w->best_cost - w->next_break->best_cost;
 761         }
 762       if (best_break <= MAXCOST - LINE_CREDIT)
 763         best_break += LINE_CREDIT;
 764     }
 765   put_paragraph (split_point);
 766
 767   /* Copy text of words down to start of parabuf -- we use memmove because
 768      the source and target may overlap.  */
 769
 770   memmove (parabuf, split_point->text, (size_t) (wptr - split_point->text));
 771   shift = split_point->text - parabuf;
 772   wptr -= shift;
 773
 774   /* Adjust text pointers.  */
 775
 776   for (w = split_point; w <= word_limit; w++)
 777     w->text -= shift;
 778
 779   /* Copy words from split_point down to word -- we use memmove because
 780      the source and target may overlap.  */
 781
 782   memmove ((char *) word, (char *) split_point,
 783          (word_limit - split_point + 1) * sizeof (WORD));
 784   word_limit -= split_point - word;
 785 }
 786
 787 /* Compute the optimal formatting for the whole paragraph by computing
 788    and remembering the optimal formatting for each suffix from the empty
 789    one to the whole paragraph.  */
 790
 791 static void
 792 fmt_paragraph (void)
 793 {
 794   register WORD *start, *w;
 795   register int len;
 796   register COST wcost, best;
 797   int saved_length;
 798
 799   word_limit->best_cost = 0;
 800   saved_length = word_limit->length;
 801   word_limit->length = max_width;       /* sentinel */
 802
 803   for (start = word_limit - 1; start >= word; start--)
 804     {
 805       best = MAXCOST;
 806       len = start == word ? first_indent : other_indent;
 807
 808       /* At least one word, however long, in the line.  */
 809
 810       w = start;
 811       len += w->length;
 812       do
 813         {
 814           w++;
 815
 816           /* Consider breaking before w.  */
 817
 818           wcost = line_cost (w, len) + w->best_cost;
 819           if (start == word && last_line_length > 0)
 820             wcost += RAGGED_COST (len - last_line_length);
 821           if (wcost < best)
 822             {
 823               best = wcost;
 824               start->next_break = w;
 825               start->line_length = len;
 826             }
 827           len += (w - 1)->space + w->length;    /* w > start >= word */
 828         }
 829       while (len < max_width);
 830       start->best_cost = best + base_cost (start);
 831     }
 832
 833   word_limit->length = saved_length;
 834 }
 835
 836 /* Return the constant component of the cost of breaking before the
 837    word THIS.  */
 838
 839 static COST
 840 base_cost (register WORD *this)
 841 {
 842   register COST cost;
 843
 844   cost = LINE_COST;
 845
 846   if (this > word)
 847     {
 848       if ((this - 1)->period)
 849         {
 850           if ((this - 1)->final)
 851             cost -= SENTENCE_BONUS;
 852           else
 853             cost += NOBREAK_COST;
 854         }
 855       else if ((this - 1)->punct)
 856         cost -= PUNCT_BONUS;
 857       else if (this > word + 1 && (this - 2)->final)
 858         cost += WIDOW_COST ((this - 1)->length);
 859     }
 860
 861   if (this->paren)
 862     cost -= PAREN_BONUS;
 863   else if (this->final)
 864     cost += ORPHAN_COST (this->length);
 865
 866   return cost;
 867 }
 868
 869 /* Return the component of the cost of breaking before word NEXT that
 870    depends on LEN, the length of the line beginning there.  */
 871
 872 static COST
 873 line_cost (register WORD *next, register int len)
 874 {
 875   register int n;
 876   register COST cost;
 877
 878   if (next == word_limit)
 879     return 0;
 880   n = best_width - len;
 881   cost = SHORT_COST (n);
 882   if (next->next_break != word_limit)
 883     {
 884       n = len - next->line_length;
 885       cost += RAGGED_COST (n);
 886     }
 887   return cost;
 888 }
 889
 890 /* Output to stdout a paragraph from word up to (but not including)
 891    FINISH, which must be in the next_break chain from word.  */
 892
 893 static void
 894 put_paragraph (register WORD *finish)
 895 {
 896   register WORD *w;
 897
 898   put_line (word, first_indent);
 899   for (w = word->next_break; w != finish; w = w->next_break)
 900     put_line (w, other_indent);
 901 }
 902
 903 /* Output to stdout the line beginning with word W, beginning in column
 904    INDENT, including the prefix (if any).  */
 905
 906 static void
 907 put_line (register WORD *w, int indent)
 908 {
 909   register WORD *endline;
 910
 911   out_column = 0;
 912   put_space (prefix_indent);
 913   fputs (prefix, stdout);
 914   out_column += prefix_length;
 915   put_space (indent - out_column);
 916
 917   endline = w->next_break - 1;
 918   for (; w != endline; w++)
 919     {
 920       put_word (w);
 921       put_space (w->space);
 922     }
 923   put_word (w);
 924   last_line_length = out_column;
 925   putchar ('\n');
 926 }
 927
 928 /* Output to stdout the word W.  */
 929
 930 static void
 931 put_word (register WORD *w)
 932 {
 933   register const char *s;
 934   register int n;
 935
 936   s = w->text;
 937   for (n = w->length; n != 0; n--)
 938     putchar (*s++);
 939   out_column += w->length;
 940 }
 941
 942 /* Output to stdout SPACE spaces, or equivalent tabs.  */
 943
 944 static void
 945 put_space (int space)
 946 {
 947   register int space_target, tab_target;
 948
 949   space_target = out_column + space;
 950   if (tabs)
 951     {
 952       tab_target = space_target / TABWIDTH * TABWIDTH;
 953       if (out_column + 1 < tab_target)
 954         while (out_column < tab_target)
 955           {
 956             putchar ('\t');
 957             out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
 958           }
 959     }
 960   while (out_column < space_target)
 961     {
 962       putchar (' ');
 963       out_column++;
 964     }
 965 }