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 "error.h"
  44 #include "xstrtol.h"
  45
  46 /* The following parameters represent the program's idea of what is
  47    "best".  Adjust to taste, subject to the caveats given.  */
  48
  49 /* Default longest permitted line length (max_width).  */
  50 #define WIDTH   75
  51
  52 /* Prefer lines to be LEEWAY % shorter than the maximum width, giving
  53    room for optimization.  */
  54 #define LEEWAY  7
  55
  56 /* The default secondary indent of tagged paragraph used for unindented
  57    one-line paragraphs not preceded by any multi-line paragraphs.  */
  58 #define DEF_INDENT 3
  59
  60 /* Costs and bonuses are expressed as the equivalent departure from the
  61    optimal line length, multiplied by 10.  e.g. assigning something a
  62    cost of 50 means that it is as bad as a line 5 characters too short
  63    or too long.  The definition of SHORT_COST(n) should not be changed.
  64    However, EQUIV(n) may need tuning.  */
  65
  66 typedef long COST;
  67
  68 #define MAXCOST (~(((COST) 1) << (8 * sizeof (COST) -1)))
  69
  70 #define SQR(n)          ((n) * (n))
  71 #define EQUIV(n)        SQR ((COST) (n))
  72
  73 /* Cost of a filled line n chars longer or shorter than best_width.  */
  74 #define SHORT_COST(n)   EQUIV ((n) * 10)
  75
  76 /* Cost of the difference between adjacent filled lines.  */
  77 #define RAGGED_COST(n)  (SHORT_COST (n) / 2)
  78
  79 /* Basic cost per line.  */
  80 #define LINE_COST       EQUIV (70)
  81
  82 /* Cost of breaking a line after the first word of a sentence, where
  83    the length of the word is N.  */
  84 #define WIDOW_COST(n)   (EQUIV (200) / ((n) + 2))
  85
  86 /* Cost of breaking a line before the last word of a sentence, where
  87    the length of the word is N.  */
  88 #define ORPHAN_COST(n)  (EQUIV (150) / ((n) + 2))
  89
  90 /* Bonus for breaking a line at the end of a sentence.  */
  91 #define SENTENCE_BONUS  EQUIV (50)
  92
  93 /* Cost of breaking a line after a period not marking end of a sentence.
  94    With the definition of sentence we are using (borrowed from emacs, see
  95    get_line()) such a break would then look like a sentence break.  Hence
  96    we assign a very high cost -- it should be avoided unless things are
  97    really bad.  */
  98 #define NOBREAK_COST    EQUIV (600)
  99
 100 /* Bonus for breaking a line before open parenthesis.  */
 101 #define PAREN_BONUS     EQUIV (40)
 102
 103 /* Bonus for breaking a line after other punctuation.  */
 104 #define PUNCT_BONUS     EQUIV(40)
 105
 106 /* Credit for breaking a long paragraph one line later.  */
 107 #define LINE_CREDIT     EQUIV(3)
 108
 109 /* Size of paragraph buffer, in words and characters.  Longer paragraphs
 110    are handled neatly (cf. flush_paragraph()), so there's little to gain
 111    by making these larger.  */
 112 #define MAXWORDS        1000
 113 #define MAXCHARS        5000
 114
 115 /* Extra ctype(3)-style macros.  */
 116
 117 #define isopen(c)       (strchr ("([`'\"", c) != NULL)
 118 #define isclose(c)      (strchr (")]'\"", c) != NULL)
 119 #define isperiod(c)     (strchr (".?!", c) != NULL)
 120
 121 /* Size of a tab stop, for expansion on input and re-introduction on
 122    output.  */
 123 #define TABWIDTH        8
 124
 125 /* Miscellaneous definitions.  */
 126
 127 typedef unsigned int bool;
 128 #undef TRUE
 129 #define TRUE    1
 130 #undef FALSE
 131 #define FALSE   0
 132
 133 /* Word descriptor structure.  */
 134
 135 typedef struct Word WORD;
 136
 137 struct Word
 138   {
 139
 140     /* Static attributes determined during input.  */
 141
 142     const char *text;           /* the text of the word */
 143     short length;               /* length of this word */
 144     short space;                /* the size of the following space */
 145     bool paren:1;               /* starts with open paren */
 146     bool period:1;              /* ends in [.?!])* */
 147     bool punct:1;               /* ends in punctuation */
 148     bool final:1;               /* end of sentence */
 149
 150     /* The remaining fields are computed during the optimization.  */
 151
 152     short line_length;          /* length of the best line starting here */
 153     COST best_cost;             /* cost of best paragraph starting here */
 154     WORD *next_break;           /* break which achieves best_cost */
 155   };
 156
 157 /* Forward declarations.  */
 158
 159 static void set_prefix __P ((char *p));
 160 static void fmt __P ((FILE *f));
 161 static bool get_paragraph __P ((FILE *f));
 162 static int get_line __P ((FILE *f, int c));
 163 static int get_prefix __P ((FILE *f));
 164 static int get_space __P ((FILE *f, int c));
 165 static int copy_rest __P ((FILE *f, int c));
 166 static bool same_para __P ((int c));
 167 static void flush_paragraph __P ((void));
 168 static void fmt_paragraph __P ((void));
 169 static void check_punctuation __P ((WORD *w));
 170 static COST base_cost __P ((WORD *this));
 171 static COST line_cost __P ((WORD *next, int len));
 172 static void put_paragraph __P ((WORD *finish));
 173 static void put_line __P ((WORD *w, int indent));
 174 static void put_word __P ((WORD *w));
 175 static void put_space __P ((int space));
 176
 177 /* The name this program was run with.  */
 178 const char *program_name;
 179
 180 /* If nonzero, display usage information and exit.  */
 181 static int show_help = 0;
 182
 183 /* If nonzero, print the version on standard output and exit.  */
 184 static int show_version = 0;
 185
 186 /* Option values.  */
 187
 188 /* If TRUE, first 2 lines may have different indent (default FALSE).  */
 189 static bool crown;
 190
 191 /* If TRUE, first 2 lines _must_ have different indent (default FALSE).  */
 192 static bool tagged;
 193
 194 /* If TRUE, each line is a paragraph on its own (default FALSE).  */
 195 static bool split;
 196
 197 /* If TRUE, don't preserve inter-word spacing (default FALSE).  */
 198 static bool uniform;
 199
 200 /* Prefix minus leading and trailing spaces (default "").  */
 201 static const char *prefix;
 202
 203 /* User-supplied maximum line width (default WIDTH).  The only output
 204    lines
 205    longer than this will each comprise a single word.  */
 206 static int max_width;
 207
 208 /* Values derived from the option values.  */
 209
 210 /* The length of prefix minus leading space.  */
 211 static int prefix_full_length;
 212
 213 /* The length of the leading space trimmed from the prefix.  */
 214 static int prefix_lead_space;
 215
 216 /* The length of prefix minus leading and trailing space.  */
 217 static int prefix_length;
 218
 219 /* The preferred width of text lines, set to LEEWAY % less than max_width.  */
 220 static int best_width;
 221
 222 /* Dynamic variables.  */
 223
 224 /* Start column of the character most recently read from the input file.  */
 225 static int in_column;
 226
 227 /* Start column of the next character to be written to stdout.  */
 228 static int out_column;
 229
 230 /* Space for the paragraph text -- longer paragraphs are handled neatly
 231    (cf. flush_paragraph()).  */
 232 static char parabuf[MAXCHARS];
 233
 234 /* A pointer into parabuf, indicating the first unused character position.  */
 235 static char *wptr;
 236
 237 /* The words of a paragraph -- longer paragraphs are handled neatly
 238    (cf. flush_paragraph()).  */
 239 static WORD word[MAXWORDS];
 240
 241 /* A pointer into the above word array, indicating the first position
 242    after the last complete word.  Sometimes it will point at an incomplete
 243    word.  */
 244 static WORD *word_limit;
 245
 246 /* If TRUE, current input file contains tab characters, and so tabs can be
 247    used for white space on output.  */
 248 static bool tabs;
 249
 250 /* Space before trimmed prefix on each line of the current paragraph.  */
 251 static int prefix_indent;
 252
 253 /* Indentation of the first line of the current paragraph.  */
 254 static int first_indent;
 255
 256 /* Indentation of other lines of the current paragraph */
 257 static int other_indent;
 258
 259 /* To detect the end of a paragraph, we need to look ahead to the first
 260    non-blank character after the prefix on the next line, or the first
 261    character on the following line that failed to match the prefix.
 262    We can reconstruct the lookahead from that character (next_char), its
 263    position on the line (in_column) and the amount of space before the
 264    prefix (next_prefix_indent).  See get_paragraph() and copy_rest().  */
 265
 266 /* The last character read from the input file.  */
 267 static int next_char;
 268
 269 /* The space before the trimmed prefix (or part of it) on the next line
 270    after the current paragraph.  */
 271 static int next_prefix_indent;
 272
 273 /* If nonzero, the length of the last line output in the current
 274    paragraph, used to charge for raggedness at the split point for long
 275    paragraphs chosen by fmt_paragraph().  */
 276 static int last_line_length;
 277
 278 static void
 279 usage (int status)
 280 {
 281   if (status != 0)
 282     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 283              program_name);
 284   else
 285     {
 286       printf (_("Usage: %s [-DIGITS] [OPTION]... [FILE]...\n"), program_name);
 287       fputs (_("\
 288 Reformat each paragraph in the FILE(s), writing to standard output.\n\
 289 If no FILE or if FILE is `-', read standard input.\n\
 290 \n\
 291 Mandatory arguments to long options are mandatory for short options too.\n\
 292   -c, --crown-margin        preserve indentation of first two lines\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   -p, --prefix=STRING       combine only lines having STRING as prefix\n\
 298       --help                display this help and exit\n\
 299       --version             output version information and exit\n\
 300 \n\
 301 In -wNUMBER, the letter `w' may be omitted.\n"),
 302              stdout);
 303     }
 304   exit (status);
 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          != EOF)
 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, NULL) != LONGINT_OK
 385               || tmp_long <= 0 || tmp_long > INT_MAX)
 386             error (1, 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\n", PACKAGE_VERSION);
 401       exit (0);
 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 (0);
 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; out_column++)
 579         putchar (*s++);
 580     }
 581   while (c != '\n' && c != EOF)
 582     {
 583       putchar (c);
 584       c = getc (f);
 585     }
 586   return c;
 587 }
 588
 589 /* Return TRUE if a line whose first non-blank character after the
 590    prefix (if any) is C could belong to the current paragraph,
 591    otherwise FALSE.  */
 592
 593 static bool
 594 same_para (register int c)
 595 {
 596   return (next_prefix_indent == prefix_indent
 597           && in_column >= next_prefix_indent + prefix_full_length
 598           && c != '\n' && c != EOF);
 599 }
 600
 601 /* Read a line from input file F, given first non-blank character C
 602    after the prefix, and the following indent, and break it into words.
 603    A word is a maximal non-empty string of non-white characters.  A word
 604    ending in [.?!]["')\]]* and followed by end-of-line or at least two
 605    spaces ends a sentence, as in emacs.
 606
 607    Return the first non-blank character of the next line.  */
 608
 609 static int
 610 get_line (FILE *f, register int c)
 611 {
 612   int start;
 613   register char *end_of_parabuf;
 614   register WORD *end_of_word;
 615
 616   end_of_parabuf = &parabuf[MAXCHARS];
 617   end_of_word = &word[MAXWORDS - 2];
 618
 619   do
 620     {                           /* for each word in a line */
 621
 622       /* Scan word.  */
 623
 624       word_limit->text = wptr;
 625       do
 626         {
 627           if (wptr == end_of_parabuf)
 628             flush_paragraph ();
 629           *wptr++ = c;
 630           c = getc (f);
 631         }
 632       while (c != EOF && !isspace (c));
 633       in_column += word_limit->length = wptr - word_limit->text;
 634       check_punctuation (word_limit);
 635
 636       /* Scan inter-word space.  */
 637
 638       start = in_column;
 639       c = get_space (f, c);
 640       word_limit->space = in_column - start;
 641       word_limit->final = (c == EOF
 642                            || (word_limit->period
 643                                && (c == '\n' || word_limit->space > 1)));
 644       if (c == '\n' || c == EOF || uniform)
 645         word_limit->space = word_limit->final ? 2 : 1;
 646       if (word_limit == end_of_word)
 647         flush_paragraph ();
 648       word_limit++;
 649       if (c == EOF)
 650         return EOF;
 651     }
 652   while (c != '\n');
 653   return get_prefix (f);
 654 }
 655
 656 /* Read a prefix from input file F.  Return either first non-matching
 657    character, or first non-blank character after the prefix.  */
 658
 659 static int
 660 get_prefix (FILE *f)
 661 {
 662   register int c;
 663   register const char *p;
 664
 665   in_column = 0;
 666   c = get_space (f, getc (f));
 667   if (prefix_length == 0)
 668     next_prefix_indent = prefix_lead_space < in_column ?
 669       prefix_lead_space : in_column;
 670   else
 671     {
 672       next_prefix_indent = in_column;
 673       for (p = prefix; *p != '\0'; p++)
 674         {
 675           if (c != *p)
 676             return c;
 677           in_column++;
 678           c = getc (f);
 679         }
 680       c = get_space (f, c);
 681     }
 682   return c;
 683 }
 684
 685 /* Read blank characters from input file F, starting with C, and keeping
 686    in_column up-to-date.  Return first non-blank character.  */
 687
 688 static int
 689 get_space (FILE *f, register int c)
 690 {
 691   for (;;)
 692     {
 693       if (c == ' ')
 694         in_column++;
 695       else if (c == '\t')
 696         {
 697           tabs = TRUE;
 698           in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
 699         }
 700       else
 701         return c;
 702       c = getc (f);
 703     }
 704 }
 705
 706 /* Set extra fields in word W describing any attached punctuation.  */
 707
 708 static void
 709 check_punctuation (register WORD *w)
 710 {
 711   register const char *start, *finish;
 712
 713   start = w->text;
 714   finish = start + (w->length - 1);
 715   w->paren = isopen (*start);
 716   w->punct = ispunct (*finish);
 717   while (isclose (*finish) && finish > start)
 718     finish--;
 719   w->period = isperiod (*finish);
 720 }
 721
 722 /* Flush part of the paragraph to make room.  This function is called on
 723    hitting the limit on the number of words or characters.  */
 724
 725 static void
 726 flush_paragraph (void)
 727 {
 728   WORD *split_point;
 729   register WORD *w;
 730   int shift;
 731   COST best_break;
 732
 733   /* In the special case where it's all one word, just flush it.  */
 734
 735   if (word_limit == word)
 736     {
 737       printf ("%*s", wptr - parabuf, parabuf);
 738       wptr = parabuf;
 739       return;
 740     }
 741
 742   /* Otherwise:
 743      - format what you have so far as a paragraph,
 744      - find a low-cost line break near the end,
 745      - output to there,
 746      - make that the start of the paragraph.  */
 747
 748   fmt_paragraph ();
 749
 750   /* Choose a good split point.  */
 751
 752   split_point = word_limit;
 753   best_break = MAXCOST;
 754   for (w = word->next_break; w != word_limit; w = w->next_break)
 755     {
 756       if (w->best_cost - w->next_break->best_cost < best_break)
 757         {
 758           split_point = w;
 759           best_break = w->best_cost - w->next_break->best_cost;
 760         }
 761       if (best_break <= MAXCOST - LINE_CREDIT)
 762         best_break += LINE_CREDIT;
 763     }
 764   put_paragraph (split_point);
 765
 766   /* Copy text of words down to start of parabuf -- we use memmove because
 767      the source and target may overlap.  */
 768
 769   memmove (parabuf, split_point->text, (size_t) (wptr - split_point->text));
 770   shift = split_point->text - parabuf;
 771   wptr -= shift;
 772
 773   /* Adjust text pointers.  */
 774
 775   for (w = split_point; w <= word_limit; w++)
 776     w->text -= shift;
 777
 778   /* Copy words from split_point down to word -- we use memmove because
 779      the source and target may overlap.  */
 780
 781   memmove ((char *) word, (char *) split_point,
 782          (word_limit - split_point + 1) * sizeof (WORD));
 783   word_limit -= split_point - word;
 784 }
 785
 786 /* Compute the optimal formatting for the whole paragraph by computing
 787    and remembering the optimal formatting for each suffix from the empty
 788    one to the whole paragraph.  */
 789
 790 static void
 791 fmt_paragraph (void)
 792 {
 793   register WORD *start, *w;
 794   register int len;
 795   register COST wcost, best;
 796   int saved_length;
 797
 798   word_limit->best_cost = 0;
 799   saved_length = word_limit->length;
 800   word_limit->length = max_width;       /* sentinel */
 801
 802   for (start = word_limit - 1; start >= word; start--)
 803     {
 804       best = MAXCOST;
 805       len = start == word ? first_indent : other_indent;
 806
 807       /* At least one word, however long, in the line.  */
 808
 809       w = start;
 810       len += w->length;
 811       do
 812         {
 813           w++;
 814
 815           /* Consider breaking before w.  */
 816
 817           wcost = line_cost (w, len) + w->best_cost;
 818           if (start == word && last_line_length > 0)
 819             wcost += RAGGED_COST (len - last_line_length);
 820           if (wcost < best)
 821             {
 822               best = wcost;
 823               start->next_break = w;
 824               start->line_length = len;
 825             }
 826           len += (w - 1)->space + w->length;    /* w > start >= word */
 827         }
 828       while (len < max_width);
 829       start->best_cost = best + base_cost (start);
 830     }
 831
 832   word_limit->length = saved_length;
 833 }
 834
 835 /* Return the constant component of the cost of breaking before the
 836    word THIS.  */
 837
 838 static COST
 839 base_cost (register WORD *this)
 840 {
 841   register COST cost;
 842
 843   cost = LINE_COST;
 844
 845   if (this > word)
 846     {
 847       if ((this - 1)->period)
 848         {
 849           if ((this - 1)->final)
 850             cost -= SENTENCE_BONUS;
 851           else
 852             cost += NOBREAK_COST;
 853         }
 854       else if ((this - 1)->punct)
 855         cost -= PUNCT_BONUS;
 856       else if (this > word + 1 && (this - 2)->final)
 857         cost += WIDOW_COST ((this - 1)->length);
 858     }
 859
 860   if (this->paren)
 861     cost -= PAREN_BONUS;
 862   else if (this->final)
 863     cost += ORPHAN_COST (this->length);
 864
 865   return cost;
 866 }
 867
 868 /* Return the component of the cost of breaking before word NEXT that
 869    depends on LEN, the length of the line beginning there.  */
 870
 871 static COST
 872 line_cost (register WORD *next, register int len)
 873 {
 874   register int n;
 875   register COST cost;
 876
 877   if (next == word_limit)
 878     return 0;
 879   n = best_width - len;
 880   cost = SHORT_COST (n);
 881   if (next->next_break != word_limit)
 882     {
 883       n = len - next->line_length;
 884       cost += RAGGED_COST (n);
 885     }
 886   return cost;
 887 }
 888
 889 /* Output to stdout a paragraph from word up to (but not including)
 890    FINISH, which must be in the next_break chain from word.  */
 891
 892 static void
 893 put_paragraph (register WORD *finish)
 894 {
 895   register WORD *w;
 896
 897   put_line (word, first_indent);
 898   for (w = word->next_break; w != finish; w = w->next_break)
 899     put_line (w, other_indent);
 900 }
 901
 902 /* Output to stdout the line beginning with word W, beginning in column
 903    INDENT, including the prefix (if any).  */
 904
 905 static void
 906 put_line (register WORD *w, int indent)
 907 {
 908   register WORD *endline;
 909
 910   out_column = 0;
 911   put_space (prefix_indent);
 912   fputs (prefix, stdout);
 913   out_column += prefix_length;
 914   put_space (indent - out_column);
 915
 916   endline = w->next_break - 1;
 917   for (; w != endline; w++)
 918     {
 919       put_word (w);
 920       put_space (w->space);
 921     }
 922   put_word (w);
 923   last_line_length = out_column;
 924   putchar ('\n');
 925 }
 926
 927 /* Output to stdout the word W.  */
 928
 929 static void
 930 put_word (register WORD *w)
 931 {
 932   register const char *s;
 933   register int n;
 934
 935   s = w->text;
 936   for (n = w->length; n != 0; n--)
 937     putchar (*s++);
 938   out_column += w->length;
 939 }
 940
 941 /* Output to stdout SPACE spaces, or equivalent tabs.  */
 942
 943 static void
 944 put_space (int space)
 945 {
 946   register int space_target, tab_target;
 947
 948   space_target = out_column + space;
 949   if (tabs)
 950     {
 951       tab_target = space_target / TABWIDTH * TABWIDTH;
 952       if (out_column + 1 < tab_target)
 953         while (out_column < tab_target)
 954           {
 955             putchar ('\t');
 956             out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
 957           }
 958     }
 959   while (out_column < space_target)
 960     {
 961       putchar (' ');
 962       out_column++;
 963     }
 964 }