src/fmt.c

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