src/fmt.c

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