src/fmt.c

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