src/fmt.c

   1 /* GNU fmt -- simple text formatter.
   2    Copyright (C) 1994-2006, 2008-2011 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     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 267              program_name);
 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 \n\
 275 "), stdout);
 276       fputs (_("\
 277 Mandatory arguments to long options are mandatory for short options too.\n\
 278 "), stdout);
 279       fputs (_("\
 280   -c, --crown-margin        preserve indentation of first two lines\n\
 281   -p, --prefix=STRING       reformat only lines beginning with STRING,\n\
 282                               reattaching the prefix to reformatted lines\n\
 283   -s, --split-only          split long lines, but do not refill\n\
 284 "),
 285              stdout);
 286       fputs (_("\
 287   -t, --tagged-paragraph    indentation of first line different from second\n\
 288   -u, --uniform-spacing     one space between words, two after sentences\n\
 289   -w, --width=WIDTH         maximum line width (default of 75 columns)\n\
 290 "), stdout);
 291       fputs (HELP_OPTION_DESCRIPTION, stdout);
 292       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 293       fputs (_("\
 294 \n\
 295 With no FILE, or when FILE is -, read standard input.\n"),
 296              stdout);
 297       emit_ancillary_info ();
 298     }
 299   exit (status);
 300 }
 301
 302 /* Decode options and launch execution.  */
 303
 304 static struct option const long_options[] =
 305 {
 306   {"crown-margin", no_argument, NULL, 'c'},
 307   {"prefix", required_argument, NULL, 'p'},
 308   {"split-only", no_argument, NULL, 's'},
 309   {"tagged-paragraph", no_argument, NULL, 't'},
 310   {"uniform-spacing", no_argument, NULL, 'u'},
 311   {"width", required_argument, NULL, 'w'},
 312   {GETOPT_HELP_OPTION_DECL},
 313   {GETOPT_VERSION_OPTION_DECL},
 314   {NULL, 0, NULL, 0},
 315 };
 316
 317 int
 318 main (int argc, char **argv)
 319 {
 320   int optchar;
 321   bool ok = true;
 322   char const *max_width_option = NULL;
 323
 324   initialize_main (&argc, &argv);
 325   set_program_name (argv[0]);
 326   setlocale (LC_ALL, "");
 327   bindtextdomain (PACKAGE, LOCALEDIR);
 328   textdomain (PACKAGE);
 329
 330   atexit (close_stdout);
 331
 332   crown = tagged = split = uniform = false;
 333   max_width = WIDTH;
 334   prefix = "";
 335   prefix_length = prefix_lead_space = prefix_full_length = 0;
 336
 337   if (argc > 1 && argv[1][0] == '-' && ISDIGIT (argv[1][1]))
 338     {
 339       /* Old option syntax; a dash followed by one or more digits.  */
 340       max_width_option = argv[1] + 1;
 341
 342       /* Make the option we just parsed invisible to getopt.  */
 343       argv[1] = argv[0];
 344       argv++;
 345       argc--;
 346     }
 347
 348   while ((optchar = getopt_long (argc, argv, "0123456789cstuw:p:",
 349                                  long_options, NULL))
 350          != -1)
 351     switch (optchar)
 352       {
 353       default:
 354         if (ISDIGIT (optchar))
 355           error (0, 0, _("invalid option -- %c; -WIDTH is recognized\
 356  only when it is the first\noption; use -w N instead"),
 357                  optchar);
 358         usage (EXIT_FAILURE);
 359
 360       case 'c':
 361         crown = true;
 362         break;
 363
 364       case 's':
 365         split = true;
 366         break;
 367
 368       case 't':
 369         tagged = true;
 370         break;
 371
 372       case 'u':
 373         uniform = true;
 374         break;
 375
 376       case 'w':
 377         max_width_option = optarg;
 378         break;
 379
 380       case 'p':
 381         set_prefix (optarg);
 382         break;
 383
 384       case_GETOPT_HELP_CHAR;
 385
 386       case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 387
 388       }
 389
 390   if (max_width_option)
 391     {
 392       /* Limit max_width to MAXCHARS / 2; otherwise, the resulting
 393          output can be quite ugly.  */
 394       unsigned long int tmp;
 395       if (! (xstrtoul (max_width_option, NULL, 10, &tmp, "") == LONGINT_OK
 396              && tmp <= MAXCHARS / 2))
 397         error (EXIT_FAILURE, 0, _("invalid width: %s"),
 398                quote (max_width_option));
 399       max_width = tmp;
 400     }
 401
 402   best_width = max_width * (2 * (100 - LEEWAY) + 1) / 200;
 403
 404   if (optind == argc)
 405     fmt (stdin);
 406   else
 407     {
 408       for (; optind < argc; optind++)
 409         {
 410           char *file = argv[optind];
 411           if (STREQ (file, "-"))
 412             fmt (stdin);
 413           else
 414             {
 415               FILE *in_stream;
 416               in_stream = fopen (file, "r");
 417               if (in_stream != NULL)
 418                 {
 419                   fmt (in_stream);
 420                   if (fclose (in_stream) == EOF)
 421                     {
 422                       error (0, errno, "%s", file);
 423                       ok = false;
 424                     }
 425                 }
 426               else
 427                 {
 428                   error (0, errno, _("cannot open %s for reading"),
 429                          quote (file));
 430                   ok = false;
 431                 }
 432             }
 433         }
 434     }
 435
 436   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 437 }
 438
 439 /* Trim space from the front and back of the string P, yielding the prefix,
 440    and record the lengths of the prefix and the space trimmed.  */
 441
 442 static void
 443 set_prefix (char *p)
 444 {
 445   char *s;
 446
 447   prefix_lead_space = 0;
 448   while (*p == ' ')
 449     {
 450       prefix_lead_space++;
 451       p++;
 452     }
 453   prefix = p;
 454   prefix_full_length = strlen (p);
 455   s = p + prefix_full_length;
 456   while (s > p && s[-1] == ' ')
 457     s--;
 458   *s = '\0';
 459   prefix_length = s - p;
 460 }
 461
 462 /* read file F and send formatted output to stdout.  */
 463
 464 static void
 465 fmt (FILE *f)
 466 {
 467   fadvise (f, FADVISE_SEQUENTIAL);
 468   tabs = false;
 469   other_indent = 0;
 470   next_char = get_prefix (f);
 471   while (get_paragraph (f))
 472     {
 473       fmt_paragraph ();
 474       put_paragraph (word_limit);
 475     }
 476 }
 477
 478 /* Set the global variable `other_indent' according to SAME_PARAGRAPH
 479    and other global variables.  */
 480
 481 static void
 482 set_other_indent (bool same_paragraph)
 483 {
 484   if (split)
 485     other_indent = first_indent;
 486   else if (crown)
 487     {
 488       other_indent = (same_paragraph ? in_column : first_indent);
 489     }
 490   else if (tagged)
 491     {
 492       if (same_paragraph && in_column != first_indent)
 493         {
 494           other_indent = in_column;
 495         }
 496
 497       /* Only one line: use the secondary indent from last time if it
 498          splits, or 0 if there have been no multi-line paragraphs in the
 499          input so far.  But if these rules make the two indents the same,
 500          pick a new secondary indent.  */
 501
 502       else if (other_indent == first_indent)
 503         other_indent = first_indent == 0 ? DEF_INDENT : 0;
 504     }
 505   else
 506     {
 507       other_indent = first_indent;
 508     }
 509 }
 510
 511 /* Read a paragraph from input file F.  A paragraph consists of a
 512    maximal number of non-blank (excluding any prefix) lines subject to:
 513    * In split mode, a paragraph is a single non-blank line.
 514    * In crown mode, the second and subsequent lines must have the
 515    same indentation, but possibly different from the indent of the
 516    first line.
 517    * Tagged mode is similar, but the first and second lines must have
 518    different indentations.
 519    * Otherwise, all lines of a paragraph must have the same indent.
 520    If a prefix is in effect, it must be present at the same indent for
 521    each line in the paragraph.
 522
 523    Return false if end-of-file was encountered before the start of a
 524    paragraph, else true.  */
 525
 526 static bool
 527 get_paragraph (FILE *f)
 528 {
 529   int c;
 530
 531   last_line_length = 0;
 532   c = next_char;
 533
 534   /* Scan (and copy) blank lines, and lines not introduced by the prefix.  */
 535
 536   while (c == '\n' || c == EOF
 537          || next_prefix_indent < prefix_lead_space
 538          || in_column < next_prefix_indent + prefix_full_length)
 539     {
 540       c = copy_rest (f, c);
 541       if (c == EOF)
 542         {
 543           next_char = EOF;
 544           return false;
 545         }
 546       putchar ('\n');
 547       c = get_prefix (f);
 548     }
 549
 550   /* Got a suitable first line for a paragraph.  */
 551
 552   prefix_indent = next_prefix_indent;
 553   first_indent = in_column;
 554   wptr = parabuf;
 555   word_limit = word;
 556   c = get_line (f, c);
 557   set_other_indent (same_para (c));
 558
 559   /* Read rest of paragraph (unless split is specified).  */
 560
 561   if (split)
 562     {
 563       /* empty */
 564     }
 565   else if (crown)
 566     {
 567       if (same_para (c))
 568         {
 569           do
 570             {                   /* for each line till the end of the para */
 571               c = get_line (f, c);
 572             }
 573           while (same_para (c) && in_column == other_indent);
 574         }
 575     }
 576   else if (tagged)
 577     {
 578       if (same_para (c) && in_column != first_indent)
 579         {
 580           do
 581             {                   /* for each line till the end of the para */
 582               c = get_line (f, c);
 583             }
 584           while (same_para (c) && in_column == other_indent);
 585         }
 586     }
 587   else
 588     {
 589       while (same_para (c) && in_column == other_indent)
 590         c = get_line (f, c);
 591     }
 592   (word_limit - 1)->period = (word_limit - 1)->final = true;
 593   next_char = c;
 594   return true;
 595 }
 596
 597 /* Copy to the output a line that failed to match the prefix, or that
 598    was blank after the prefix.  In the former case, C is the character
 599    that failed to match the prefix.  In the latter, C is \n or EOF.
 600    Return the character (\n or EOF) ending the line.  */
 601
 602 static int
 603 copy_rest (FILE *f, int c)
 604 {
 605   const char *s;
 606
 607   out_column = 0;
 608   if (in_column > next_prefix_indent || (c != '\n' && c != EOF))
 609     {
 610       put_space (next_prefix_indent);
 611       for (s = prefix; out_column != in_column && *s; out_column++)
 612         putchar (*s++);
 613       if (c != EOF && c != '\n')
 614         put_space (in_column - out_column);
 615       if (c == EOF && in_column >= next_prefix_indent + prefix_length)
 616         putchar ('\n');
 617     }
 618   while (c != '\n' && c != EOF)
 619     {
 620       putchar (c);
 621       c = getc (f);
 622     }
 623   return c;
 624 }
 625
 626 /* Return true if a line whose first non-blank character after the
 627    prefix (if any) is C could belong to the current paragraph,
 628    otherwise false.  */
 629
 630 static bool
 631 same_para (int c)
 632 {
 633   return (next_prefix_indent == prefix_indent
 634           && in_column >= next_prefix_indent + prefix_full_length
 635           && c != '\n' && c != EOF);
 636 }
 637
 638 /* Read a line from input file F, given first non-blank character C
 639    after the prefix, and the following indent, and break it into words.
 640    A word is a maximal non-empty string of non-white characters.  A word
 641    ending in [.?!]["')\]]* and followed by end-of-line or at least two
 642    spaces ends a sentence, as in emacs.
 643
 644    Return the first non-blank character of the next line.  */
 645
 646 static int
 647 get_line (FILE *f, int c)
 648 {
 649   int start;
 650   char *end_of_parabuf;
 651   WORD *end_of_word;
 652
 653   end_of_parabuf = &parabuf[MAXCHARS];
 654   end_of_word = &word[MAXWORDS - 2];
 655
 656   do
 657     {                           /* for each word in a line */
 658
 659       /* Scan word.  */
 660
 661       word_limit->text = wptr;
 662       do
 663         {
 664           if (wptr == end_of_parabuf)
 665             {
 666               set_other_indent (true);
 667               flush_paragraph ();
 668             }
 669           *wptr++ = c;
 670           c = getc (f);
 671         }
 672       while (c != EOF && !isspace (c));
 673       in_column += word_limit->length = wptr - word_limit->text;
 674       check_punctuation (word_limit);
 675
 676       /* Scan inter-word space.  */
 677
 678       start = in_column;
 679       c = get_space (f, c);
 680       word_limit->space = in_column - start;
 681       word_limit->final = (c == EOF
 682                            || (word_limit->period
 683                                && (c == '\n' || word_limit->space > 1)));
 684       if (c == '\n' || c == EOF || uniform)
 685         word_limit->space = word_limit->final ? 2 : 1;
 686       if (word_limit == end_of_word)
 687         {
 688           set_other_indent (true);
 689           flush_paragraph ();
 690         }
 691       word_limit++;
 692     }
 693   while (c != '\n' && c != EOF);
 694   return get_prefix (f);
 695 }
 696
 697 /* Read a prefix from input file F.  Return either first non-matching
 698    character, or first non-blank character after the prefix.  */
 699
 700 static int
 701 get_prefix (FILE *f)
 702 {
 703   int c;
 704
 705   in_column = 0;
 706   c = get_space (f, getc (f));
 707   if (prefix_length == 0)
 708     next_prefix_indent = prefix_lead_space < in_column ?
 709       prefix_lead_space : in_column;
 710   else
 711     {
 712       const char *p;
 713       next_prefix_indent = in_column;
 714       for (p = prefix; *p != '\0'; p++)
 715         {
 716           unsigned char pc = *p;
 717           if (c != pc)
 718             return c;
 719           in_column++;
 720           c = getc (f);
 721         }
 722       c = get_space (f, c);
 723     }
 724   return c;
 725 }
 726
 727 /* Read blank characters from input file F, starting with C, and keeping
 728    in_column up-to-date.  Return first non-blank character.  */
 729
 730 static int
 731 get_space (FILE *f, int c)
 732 {
 733   while (true)
 734     {
 735       if (c == ' ')
 736         in_column++;
 737       else if (c == '\t')
 738         {
 739           tabs = true;
 740           in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
 741         }
 742       else
 743         return c;
 744       c = getc (f);
 745     }
 746 }
 747
 748 /* Set extra fields in word W describing any attached punctuation.  */
 749
 750 static void
 751 check_punctuation (WORD *w)
 752 {
 753   char const *start = w->text;
 754   char const *finish = start + (w->length - 1);
 755   unsigned char fin = *finish;
 756
 757   w->paren = isopen (*start);
 758   w->punct = !! ispunct (fin);
 759   while (start < finish && isclose (*finish))
 760     finish--;
 761   w->period = isperiod (*finish);
 762 }
 763
 764 /* Flush part of the paragraph to make room.  This function is called on
 765    hitting the limit on the number of words or characters.  */
 766
 767 static void
 768 flush_paragraph (void)
 769 {
 770   WORD *split_point;
 771   WORD *w;
 772   int shift;
 773   COST best_break;
 774
 775   /* In the special case where it's all one word, just flush it.  */
 776
 777   if (word_limit == word)
 778     {
 779       fwrite (parabuf, sizeof *parabuf, wptr - parabuf, stdout);
 780       wptr = parabuf;
 781       return;
 782     }
 783
 784   /* Otherwise:
 785      - format what you have so far as a paragraph,
 786      - find a low-cost line break near the end,
 787      - output to there,
 788      - make that the start of the paragraph.  */
 789
 790   fmt_paragraph ();
 791
 792   /* Choose a good split point.  */
 793
 794   split_point = word_limit;
 795   best_break = MAXCOST;
 796   for (w = word->next_break; w != word_limit; w = w->next_break)
 797     {
 798       if (w->best_cost - w->next_break->best_cost < best_break)
 799         {
 800           split_point = w;
 801           best_break = w->best_cost - w->next_break->best_cost;
 802         }
 803       if (best_break <= MAXCOST - LINE_CREDIT)
 804         best_break += LINE_CREDIT;
 805     }
 806   put_paragraph (split_point);
 807
 808   /* Copy text of words down to start of parabuf -- we use memmove because
 809      the source and target may overlap.  */
 810
 811   memmove (parabuf, split_point->text, wptr - split_point->text);
 812   shift = split_point->text - parabuf;
 813   wptr -= shift;
 814
 815   /* Adjust text pointers.  */
 816
 817   for (w = split_point; w <= word_limit; w++)
 818     w->text -= shift;
 819
 820   /* Copy words from split_point down to word -- we use memmove because
 821      the source and target may overlap.  */
 822
 823   memmove (word, split_point, (word_limit - split_point + 1) * sizeof *word);
 824   word_limit -= split_point - word;
 825 }
 826
 827 /* Compute the optimal formatting for the whole paragraph by computing
 828    and remembering the optimal formatting for each suffix from the empty
 829    one to the whole paragraph.  */
 830
 831 static void
 832 fmt_paragraph (void)
 833 {
 834   WORD *start, *w;
 835   int len;
 836   COST wcost, best;
 837   int saved_length;
 838
 839   word_limit->best_cost = 0;
 840   saved_length = word_limit->length;
 841   word_limit->length = max_width;       /* sentinel */
 842
 843   for (start = word_limit - 1; start >= word; start--)
 844     {
 845       best = MAXCOST;
 846       len = start == word ? first_indent : other_indent;
 847
 848       /* At least one word, however long, in the line.  */
 849
 850       w = start;
 851       len += w->length;
 852       do
 853         {
 854           w++;
 855
 856           /* Consider breaking before w.  */
 857
 858           wcost = line_cost (w, len) + w->best_cost;
 859           if (start == word && last_line_length > 0)
 860             wcost += RAGGED_COST (len - last_line_length);
 861           if (wcost < best)
 862             {
 863               best = wcost;
 864               start->next_break = w;
 865               start->line_length = len;
 866             }
 867
 868           /* This is a kludge to keep us from computing `len' as the
 869              sum of the sentinel length and some non-zero number.
 870              Since the sentinel w->length may be INT_MAX, adding
 871              to that would give a negative result.  */
 872           if (w == word_limit)
 873             break;
 874
 875           len += (w - 1)->space + w->length;    /* w > start >= word */
 876         }
 877       while (len < max_width);
 878       start->best_cost = best + base_cost (start);
 879     }
 880
 881   word_limit->length = saved_length;
 882 }
 883
 884 /* Return the constant component of the cost of breaking before the
 885    word THIS.  */
 886
 887 static COST
 888 base_cost (WORD *this)
 889 {
 890   COST cost;
 891
 892   cost = LINE_COST;
 893
 894   if (this > word)
 895     {
 896       if ((this - 1)->period)
 897         {
 898           if ((this - 1)->final)
 899             cost -= SENTENCE_BONUS;
 900           else
 901             cost += NOBREAK_COST;
 902         }
 903       else if ((this - 1)->punct)
 904         cost -= PUNCT_BONUS;
 905       else if (this > word + 1 && (this - 2)->final)
 906         cost += WIDOW_COST ((this - 1)->length);
 907     }
 908
 909   if (this->paren)
 910     cost -= PAREN_BONUS;
 911   else if (this->final)
 912     cost += ORPHAN_COST (this->length);
 913
 914   return cost;
 915 }
 916
 917 /* Return the component of the cost of breaking before word NEXT that
 918    depends on LEN, the length of the line beginning there.  */
 919
 920 static COST
 921 line_cost (WORD *next, int len)
 922 {
 923   int n;
 924   COST cost;
 925
 926   if (next == word_limit)
 927     return 0;
 928   n = best_width - len;
 929   cost = SHORT_COST (n);
 930   if (next->next_break != word_limit)
 931     {
 932       n = len - next->line_length;
 933       cost += RAGGED_COST (n);
 934     }
 935   return cost;
 936 }
 937
 938 /* Output to stdout a paragraph from word up to (but not including)
 939    FINISH, which must be in the next_break chain from word.  */
 940
 941 static void
 942 put_paragraph (WORD *finish)
 943 {
 944   WORD *w;
 945
 946   put_line (word, first_indent);
 947   for (w = word->next_break; w != finish; w = w->next_break)
 948     put_line (w, other_indent);
 949 }
 950
 951 /* Output to stdout the line beginning with word W, beginning in column
 952    INDENT, including the prefix (if any).  */
 953
 954 static void
 955 put_line (WORD *w, int indent)
 956 {
 957   WORD *endline;
 958
 959   out_column = 0;
 960   put_space (prefix_indent);
 961   fputs (prefix, stdout);
 962   out_column += prefix_length;
 963   put_space (indent - out_column);
 964
 965   endline = w->next_break - 1;
 966   for (; w != endline; w++)
 967     {
 968       put_word (w);
 969       put_space (w->space);
 970     }
 971   put_word (w);
 972   last_line_length = out_column;
 973   putchar ('\n');
 974 }
 975
 976 /* Output to stdout the word W.  */
 977
 978 static void
 979 put_word (WORD *w)
 980 {
 981   const char *s;
 982   int n;
 983
 984   s = w->text;
 985   for (n = w->length; n != 0; n--)
 986     putchar (*s++);
 987   out_column += w->length;
 988 }
 989
 990 /* Output to stdout SPACE spaces, or equivalent tabs.  */
 991
 992 static void
 993 put_space (int space)
 994 {
 995   int space_target, tab_target;
 996
 997   space_target = out_column + space;
 998   if (tabs)
 999     {
1000       tab_target = space_target / TABWIDTH * TABWIDTH;
1001       if (out_column + 1 < tab_target)
1002         while (out_column < tab_target)
1003           {
1004             putchar ('\t');
1005             out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
1006           }
1007     }
1008   while (out_column < space_target)
1009     {
1010       putchar (' ');
1011       out_column++;
1012     }
1013 }