src/fmt.c

   1 /* GNU fmt -- simple text formatter.
   2    Copyright (C) 1994-2006, 2008-2012 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 "fadvise.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 proper_name ("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 /* Option values.  */
 172
 173 /* If true, first 2 lines may have different indent (default false).  */
 174 static bool crown;
 175
 176 /* If true, first 2 lines _must_ have different indent (default false).  */
 177 static bool tagged;
 178
 179 /* If true, each line is a paragraph on its own (default false).  */
 180 static bool split;
 181
 182 /* If true, don't preserve inter-word spacing (default false).  */
 183 static bool uniform;
 184
 185 /* Prefix minus leading and trailing spaces (default "").  */
 186 static const char *prefix;
 187
 188 /* User-supplied maximum line width (default WIDTH).  The only output
 189    lines longer than this will each comprise a single word.  */
 190 static int max_width;
 191
 192 /* Values derived from the option values.  */
 193
 194 /* The length of prefix minus leading space.  */
 195 static int prefix_full_length;
 196
 197 /* The length of the leading space trimmed from the prefix.  */
 198 static int prefix_lead_space;
 199
 200 /* The length of prefix minus leading and trailing space.  */
 201 static int prefix_length;
 202
 203 /* The preferred width of text lines, set to LEEWAY % less than max_width.  */
 204 static int best_width;
 205
 206 /* Dynamic variables.  */
 207
 208 /* Start column of the character most recently read from the input file.  */
 209 static int in_column;
 210
 211 /* Start column of the next character to be written to stdout.  */
 212 static int out_column;
 213
 214 /* Space for the paragraph text -- longer paragraphs are handled neatly
 215    (cf. flush_paragraph()).  */
 216 static char parabuf[MAXCHARS];
 217
 218 /* A pointer into parabuf, indicating the first unused character position.  */
 219 static char *wptr;
 220
 221 /* The words of a paragraph -- longer paragraphs are handled neatly
 222    (cf. flush_paragraph()).  */
 223 static WORD word[MAXWORDS];
 224
 225 /* A pointer into the above word array, indicating the first position
 226    after the last complete word.  Sometimes it will point at an incomplete
 227    word.  */
 228 static WORD *word_limit;
 229
 230 /* If true, current input file contains tab characters, and so tabs can be
 231    used for white space on output.  */
 232 static bool tabs;
 233
 234 /* Space before trimmed prefix on each line of the current paragraph.  */
 235 static int prefix_indent;
 236
 237 /* Indentation of the first line of the current paragraph.  */
 238 static int first_indent;
 239
 240 /* Indentation of other lines of the current paragraph */
 241 static int other_indent;
 242
 243 /* To detect the end of a paragraph, we need to look ahead to the first
 244    non-blank character after the prefix on the next line, or the first
 245    character on the following line that failed to match the prefix.
 246    We can reconstruct the lookahead from that character (next_char), its
 247    position on the line (in_column) and the amount of space before the
 248    prefix (next_prefix_indent).  See get_paragraph() and copy_rest().  */
 249
 250 /* The last character read from the input file.  */
 251 static int next_char;
 252
 253 /* The space before the trimmed prefix (or part of it) on the next line
 254    after the current paragraph.  */
 255 static int next_prefix_indent;
 256
 257 /* If nonzero, the length of the last line output in the current
 258    paragraph, used to charge for raggedness at the split point for long
 259    paragraphs chosen by fmt_paragraph().  */
 260 static int last_line_length;
 261
 262 void
 263 usage (int status)
 264 {
 265   if (status != EXIT_SUCCESS)
 266     emit_try_help ();
 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   fadvise (f, FADVISE_SEQUENTIAL);
 467   tabs = false;
 468   other_indent = 0;
 469   next_char = get_prefix (f);
 470   while (get_paragraph (f))
 471     {
 472       fmt_paragraph ();
 473       put_paragraph (word_limit);
 474     }
 475 }
 476
 477 /* Set the global variable 'other_indent' according to SAME_PARAGRAPH
 478    and other global variables.  */
 479
 480 static void
 481 set_other_indent (bool same_paragraph)
 482 {
 483   if (split)
 484     other_indent = first_indent;
 485   else if (crown)
 486     {
 487       other_indent = (same_paragraph ? in_column : first_indent);
 488     }
 489   else if (tagged)
 490     {
 491       if (same_paragraph && in_column != first_indent)
 492         {
 493           other_indent = in_column;
 494         }
 495
 496       /* Only one line: use the secondary indent from last time if it
 497          splits, or 0 if there have been no multi-line paragraphs in the
 498          input so far.  But if these rules make the two indents the same,
 499          pick a new secondary indent.  */
 500
 501       else if (other_indent == first_indent)
 502         other_indent = first_indent == 0 ? DEF_INDENT : 0;
 503     }
 504   else
 505     {
 506       other_indent = first_indent;
 507     }
 508 }
 509
 510 /* Read a paragraph from input file F.  A paragraph consists of a
 511    maximal number of non-blank (excluding any prefix) lines subject to:
 512    * In split mode, a paragraph is a single non-blank line.
 513    * In crown mode, the second and subsequent lines must have the
 514    same indentation, but possibly different from the indent of the
 515    first line.
 516    * Tagged mode is similar, but the first and second lines must have
 517    different indentations.
 518    * Otherwise, all lines of a paragraph must have the same indent.
 519    If a prefix is in effect, it must be present at the same indent for
 520    each line in the paragraph.
 521
 522    Return false if end-of-file was encountered before the start of a
 523    paragraph, else true.  */
 524
 525 static bool
 526 get_paragraph (FILE *f)
 527 {
 528   int c;
 529
 530   last_line_length = 0;
 531   c = next_char;
 532
 533   /* Scan (and copy) blank lines, and lines not introduced by the prefix.  */
 534
 535   while (c == '\n' || c == EOF
 536          || next_prefix_indent < prefix_lead_space
 537          || in_column < next_prefix_indent + prefix_full_length)
 538     {
 539       c = copy_rest (f, c);
 540       if (c == EOF)
 541         {
 542           next_char = EOF;
 543           return false;
 544         }
 545       putchar ('\n');
 546       c = get_prefix (f);
 547     }
 548
 549   /* Got a suitable first line for a paragraph.  */
 550
 551   prefix_indent = next_prefix_indent;
 552   first_indent = in_column;
 553   wptr = parabuf;
 554   word_limit = word;
 555   c = get_line (f, c);
 556   set_other_indent (same_para (c));
 557
 558   /* Read rest of paragraph (unless split is specified).  */
 559
 560   if (split)
 561     {
 562       /* empty */
 563     }
 564   else if (crown)
 565     {
 566       if (same_para (c))
 567         {
 568           do
 569             {                   /* for each line till the end of the para */
 570               c = get_line (f, c);
 571             }
 572           while (same_para (c) && in_column == other_indent);
 573         }
 574     }
 575   else if (tagged)
 576     {
 577       if (same_para (c) && in_column != first_indent)
 578         {
 579           do
 580             {                   /* for each line till the end of the para */
 581               c = get_line (f, c);
 582             }
 583           while (same_para (c) && in_column == other_indent);
 584         }
 585     }
 586   else
 587     {
 588       while (same_para (c) && in_column == other_indent)
 589         c = get_line (f, c);
 590     }
 591   (word_limit - 1)->period = (word_limit - 1)->final = true;
 592   next_char = c;
 593   return true;
 594 }
 595
 596 /* Copy to the output a line that failed to match the prefix, or that
 597    was blank after the prefix.  In the former case, C is the character
 598    that failed to match the prefix.  In the latter, C is \n or EOF.
 599    Return the character (\n or EOF) ending the line.  */
 600
 601 static int
 602 copy_rest (FILE *f, int c)
 603 {
 604   const char *s;
 605
 606   out_column = 0;
 607   if (in_column > next_prefix_indent || (c != '\n' && c != EOF))
 608     {
 609       put_space (next_prefix_indent);
 610       for (s = prefix; out_column != in_column && *s; out_column++)
 611         putchar (*s++);
 612       if (c != EOF && c != '\n')
 613         put_space (in_column - out_column);
 614       if (c == EOF && in_column >= next_prefix_indent + prefix_length)
 615         putchar ('\n');
 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     }
 692   while (c != '\n' && c != EOF);
 693   return get_prefix (f);
 694 }
 695
 696 /* Read a prefix from input file F.  Return either first non-matching
 697    character, or first non-blank character after the prefix.  */
 698
 699 static int
 700 get_prefix (FILE *f)
 701 {
 702   int c;
 703
 704   in_column = 0;
 705   c = get_space (f, getc (f));
 706   if (prefix_length == 0)
 707     next_prefix_indent = prefix_lead_space < in_column ?
 708       prefix_lead_space : in_column;
 709   else
 710     {
 711       const char *p;
 712       next_prefix_indent = in_column;
 713       for (p = prefix; *p != '\0'; p++)
 714         {
 715           unsigned char pc = *p;
 716           if (c != pc)
 717             return c;
 718           in_column++;
 719           c = getc (f);
 720         }
 721       c = get_space (f, c);
 722     }
 723   return c;
 724 }
 725
 726 /* Read blank characters from input file F, starting with C, and keeping
 727    in_column up-to-date.  Return first non-blank character.  */
 728
 729 static int
 730 get_space (FILE *f, int c)
 731 {
 732   while (true)
 733     {
 734       if (c == ' ')
 735         in_column++;
 736       else if (c == '\t')
 737         {
 738           tabs = true;
 739           in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
 740         }
 741       else
 742         return c;
 743       c = getc (f);
 744     }
 745 }
 746
 747 /* Set extra fields in word W describing any attached punctuation.  */
 748
 749 static void
 750 check_punctuation (WORD *w)
 751 {
 752   char const *start = w->text;
 753   char const *finish = start + (w->length - 1);
 754   unsigned char fin = *finish;
 755
 756   w->paren = isopen (*start);
 757   w->punct = !! ispunct (fin);
 758   while (start < finish && isclose (*finish))
 759     finish--;
 760   w->period = isperiod (*finish);
 761 }
 762
 763 /* Flush part of the paragraph to make room.  This function is called on
 764    hitting the limit on the number of words or characters.  */
 765
 766 static void
 767 flush_paragraph (void)
 768 {
 769   WORD *split_point;
 770   WORD *w;
 771   int shift;
 772   COST best_break;
 773
 774   /* In the special case where it's all one word, just flush it.  */
 775
 776   if (word_limit == word)
 777     {
 778       fwrite (parabuf, sizeof *parabuf, wptr - parabuf, stdout);
 779       wptr = parabuf;
 780       return;
 781     }
 782
 783   /* Otherwise:
 784      - format what you have so far as a paragraph,
 785      - find a low-cost line break near the end,
 786      - output to there,
 787      - make that the start of the paragraph.  */
 788
 789   fmt_paragraph ();
 790
 791   /* Choose a good split point.  */
 792
 793   split_point = word_limit;
 794   best_break = MAXCOST;
 795   for (w = word->next_break; w != word_limit; w = w->next_break)
 796     {
 797       if (w->best_cost - w->next_break->best_cost < best_break)
 798         {
 799           split_point = w;
 800           best_break = w->best_cost - w->next_break->best_cost;
 801         }
 802       if (best_break <= MAXCOST - LINE_CREDIT)
 803         best_break += LINE_CREDIT;
 804     }
 805   put_paragraph (split_point);
 806
 807   /* Copy text of words down to start of parabuf -- we use memmove because
 808      the source and target may overlap.  */
 809
 810   memmove (parabuf, split_point->text, wptr - split_point->text);
 811   shift = split_point->text - parabuf;
 812   wptr -= shift;
 813
 814   /* Adjust text pointers.  */
 815
 816   for (w = split_point; w <= word_limit; w++)
 817     w->text -= shift;
 818
 819   /* Copy words from split_point down to word -- we use memmove because
 820      the source and target may overlap.  */
 821
 822   memmove (word, split_point, (word_limit - split_point + 1) * sizeof *word);
 823   word_limit -= split_point - word;
 824 }
 825
 826 /* Compute the optimal formatting for the whole paragraph by computing
 827    and remembering the optimal formatting for each suffix from the empty
 828    one to the whole paragraph.  */
 829
 830 static void
 831 fmt_paragraph (void)
 832 {
 833   WORD *start, *w;
 834   int len;
 835   COST wcost, best;
 836   int saved_length;
 837
 838   word_limit->best_cost = 0;
 839   saved_length = word_limit->length;
 840   word_limit->length = max_width;       /* sentinel */
 841
 842   for (start = word_limit - 1; start >= word; start--)
 843     {
 844       best = MAXCOST;
 845       len = start == word ? first_indent : other_indent;
 846
 847       /* At least one word, however long, in the line.  */
 848
 849       w = start;
 850       len += w->length;
 851       do
 852         {
 853           w++;
 854
 855           /* Consider breaking before w.  */
 856
 857           wcost = line_cost (w, len) + w->best_cost;
 858           if (start == word && last_line_length > 0)
 859             wcost += RAGGED_COST (len - last_line_length);
 860           if (wcost < best)
 861             {
 862               best = wcost;
 863               start->next_break = w;
 864               start->line_length = len;
 865             }
 866
 867           /* This is a kludge to keep us from computing 'len' as the
 868              sum of the sentinel length and some non-zero number.
 869              Since the sentinel w->length may be INT_MAX, adding
 870              to that would give a negative result.  */
 871           if (w == word_limit)
 872             break;
 873
 874           len += (w - 1)->space + w->length;    /* w > start >= word */
 875         }
 876       while (len < max_width);
 877       start->best_cost = best + base_cost (start);
 878     }
 879
 880   word_limit->length = saved_length;
 881 }
 882
 883 /* Return the constant component of the cost of breaking before the
 884    word THIS.  */
 885
 886 static COST
 887 base_cost (WORD *this)
 888 {
 889   COST cost;
 890
 891   cost = LINE_COST;
 892
 893   if (this > word)
 894     {
 895       if ((this - 1)->period)
 896         {
 897           if ((this - 1)->final)
 898             cost -= SENTENCE_BONUS;
 899           else
 900             cost += NOBREAK_COST;
 901         }
 902       else if ((this - 1)->punct)
 903         cost -= PUNCT_BONUS;
 904       else if (this > word + 1 && (this - 2)->final)
 905         cost += WIDOW_COST ((this - 1)->length);
 906     }
 907
 908   if (this->paren)
 909     cost -= PAREN_BONUS;
 910   else if (this->final)
 911     cost += ORPHAN_COST (this->length);
 912
 913   return cost;
 914 }
 915
 916 /* Return the component of the cost of breaking before word NEXT that
 917    depends on LEN, the length of the line beginning there.  */
 918
 919 static COST
 920 line_cost (WORD *next, int len)
 921 {
 922   int n;
 923   COST cost;
 924
 925   if (next == word_limit)
 926     return 0;
 927   n = best_width - len;
 928   cost = SHORT_COST (n);
 929   if (next->next_break != word_limit)
 930     {
 931       n = len - next->line_length;
 932       cost += RAGGED_COST (n);
 933     }
 934   return cost;
 935 }
 936
 937 /* Output to stdout a paragraph from word up to (but not including)
 938    FINISH, which must be in the next_break chain from word.  */
 939
 940 static void
 941 put_paragraph (WORD *finish)
 942 {
 943   WORD *w;
 944
 945   put_line (word, first_indent);
 946   for (w = word->next_break; w != finish; w = w->next_break)
 947     put_line (w, other_indent);
 948 }
 949
 950 /* Output to stdout the line beginning with word W, beginning in column
 951    INDENT, including the prefix (if any).  */
 952
 953 static void
 954 put_line (WORD *w, int indent)
 955 {
 956   WORD *endline;
 957
 958   out_column = 0;
 959   put_space (prefix_indent);
 960   fputs (prefix, stdout);
 961   out_column += prefix_length;
 962   put_space (indent - out_column);
 963
 964   endline = w->next_break - 1;
 965   for (; w != endline; w++)
 966     {
 967       put_word (w);
 968       put_space (w->space);
 969     }
 970   put_word (w);
 971   last_line_length = out_column;
 972   putchar ('\n');
 973 }
 974
 975 /* Output to stdout the word W.  */
 976
 977 static void
 978 put_word (WORD *w)
 979 {
 980   const char *s;
 981   int n;
 982
 983   s = w->text;
 984   for (n = w->length; n != 0; n--)
 985     putchar (*s++);
 986   out_column += w->length;
 987 }
 988
 989 /* Output to stdout SPACE spaces, or equivalent tabs.  */
 990
 991 static void
 992 put_space (int space)
 993 {
 994   int space_target, tab_target;
 995
 996   space_target = out_column + space;
 997   if (tabs)
 998     {
 999       tab_target = space_target / TABWIDTH * TABWIDTH;
1000       if (out_column + 1 < tab_target)
1001         while (out_column < tab_target)
1002           {
1003             putchar ('\t');
1004             out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
1005           }
1006     }
1007   while (out_column < space_target)
1008     {
1009       putchar (' ');
1010       out_column++;
1011     }
1012 }