src/fmt.c

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