src/fmt.c

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