1 /* GNU fmt -- simple text formatter.
2 Copyright (C) 94, 95, 1996 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
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.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 /* Written by Ross Paterson <rap@doc.ic.ac.uk>. */
23 #include <sys/types.h>
31 # define UINT_MAX ((unsigned int) ~(unsigned int) 0)
35 # define INT_MAX ((int) (UINT_MAX >> 1))
38 /* Redefine. Otherwise, systems (Unicos for one) with headers that define
39 it to be a type get syntax errors for the variable declaration below. */
40 #define word unused_word_type
46 /* The following parameters represent the program's idea of what is
47 "best". Adjust to taste, subject to the caveats given. */
49 /* Default longest permitted line length (max_width). */
52 /* Prefer lines to be LEEWAY % shorter than the maximum width, giving
53 room for optimization. */
56 /* The default secondary indent of tagged paragraph used for unindented
57 one-line paragraphs not preceded by any multi-line paragraphs. */
60 /* Costs and bonuses are expressed as the equivalent departure from the
61 optimal line length, multiplied by 10. e.g. assigning something a
62 cost of 50 means that it is as bad as a line 5 characters too short
63 or too long. The definition of SHORT_COST(n) should not be changed.
64 However, EQUIV(n) may need tuning. */
68 #define MAXCOST (~(((unsigned long) 1) << (8 * sizeof (COST) -1)))
70 #define SQR(n) ((n) * (n))
71 #define EQUIV(n) SQR ((COST) (n))
73 /* Cost of a filled line n chars longer or shorter than best_width. */
74 #define SHORT_COST(n) EQUIV ((n) * 10)
76 /* Cost of the difference between adjacent filled lines. */
77 #define RAGGED_COST(n) (SHORT_COST (n) / 2)
79 /* Basic cost per line. */
80 #define LINE_COST EQUIV (70)
82 /* Cost of breaking a line after the first word of a sentence, where
83 the length of the word is N. */
84 #define WIDOW_COST(n) (EQUIV (200) / ((n) + 2))
86 /* Cost of breaking a line before the last word of a sentence, where
87 the length of the word is N. */
88 #define ORPHAN_COST(n) (EQUIV (150) / ((n) + 2))
90 /* Bonus for breaking a line at the end of a sentence. */
91 #define SENTENCE_BONUS EQUIV (50)
93 /* Cost of breaking a line after a period not marking end of a sentence.
94 With the definition of sentence we are using (borrowed from emacs, see
95 get_line()) such a break would then look like a sentence break. Hence
96 we assign a very high cost -- it should be avoided unless things are
98 #define NOBREAK_COST EQUIV (600)
100 /* Bonus for breaking a line before open parenthesis. */
101 #define PAREN_BONUS EQUIV (40)
103 /* Bonus for breaking a line after other punctuation. */
104 #define PUNCT_BONUS EQUIV(40)
106 /* Credit for breaking a long paragraph one line later. */
107 #define LINE_CREDIT EQUIV(3)
109 /* Size of paragraph buffer, in words and characters. Longer paragraphs
110 are handled neatly (cf. flush_paragraph()), so there's little to gain
111 by making these larger. */
112 #define MAXWORDS 1000
113 #define MAXCHARS 5000
115 /* Extra ctype(3)-style macros. */
117 #define isopen(c) (strchr ("([`'\"", c) != NULL)
118 #define isclose(c) (strchr (")]'\"", c) != NULL)
119 #define isperiod(c) (strchr (".?!", c) != NULL)
121 /* Size of a tab stop, for expansion on input and re-introduction on
125 /* Miscellaneous definitions. */
127 typedef unsigned int bool;
133 /* Word descriptor structure. */
135 typedef struct Word WORD;
140 /* Static attributes determined during input. */
142 const char *text; /* the text of the word */
143 short length; /* length of this word */
144 short space; /* the size of the following space */
145 bool paren:1; /* starts with open paren */
146 bool period:1; /* ends in [.?!])* */
147 bool punct:1; /* ends in punctuation */
148 bool final:1; /* end of sentence */
150 /* The remaining fields are computed during the optimization. */
152 short line_length; /* length of the best line starting here */
153 COST best_cost; /* cost of best paragraph starting here */
154 WORD *next_break; /* break which achieves best_cost */
157 /* Forward declarations. */
159 static void set_prefix __P ((char *p));
160 static void fmt __P ((FILE *f));
161 static bool get_paragraph __P ((FILE *f));
162 static int get_line __P ((FILE *f, int c));
163 static int get_prefix __P ((FILE *f));
164 static int get_space __P ((FILE *f, int c));
165 static int copy_rest __P ((FILE *f, int c));
166 static bool same_para __P ((int c));
167 static void flush_paragraph __P ((void));
168 static void fmt_paragraph __P ((void));
169 static void check_punctuation __P ((WORD *w));
170 static COST base_cost __P ((WORD *this));
171 static COST line_cost __P ((WORD *next, int len));
172 static void put_paragraph __P ((WORD *finish));
173 static void put_line __P ((WORD *w, int indent));
174 static void put_word __P ((WORD *w));
175 static void put_space __P ((int space));
177 /* The name this program was run with. */
178 const char *program_name;
180 /* If nonzero, display usage information and exit. */
181 static int show_help = 0;
183 /* If nonzero, print the version on standard output and exit. */
184 static int show_version = 0;
188 /* If TRUE, first 2 lines may have different indent (default FALSE). */
191 /* If TRUE, first 2 lines _must_ have different indent (default FALSE). */
194 /* If TRUE, each line is a paragraph on its own (default FALSE). */
197 /* If TRUE, don't preserve inter-word spacing (default FALSE). */
200 /* Prefix minus leading and trailing spaces (default ""). */
201 static const char *prefix;
203 /* User-supplied maximum line width (default WIDTH). The only output
205 longer than this will each comprise a single word. */
206 static int max_width;
208 /* Values derived from the option values. */
210 /* The length of prefix minus leading space. */
211 static int prefix_full_length;
213 /* The length of the leading space trimmed from the prefix. */
214 static int prefix_lead_space;
216 /* The length of prefix minus leading and trailing space. */
217 static int prefix_length;
219 /* The preferred width of text lines, set to LEEWAY % less than max_width. */
220 static int best_width;
222 /* Dynamic variables. */
224 /* Start column of the character most recently read from the input file. */
225 static int in_column;
227 /* Start column of the next character to be written to stdout. */
228 static int out_column;
230 /* Space for the paragraph text -- longer paragraphs are handled neatly
231 (cf. flush_paragraph()). */
232 static char parabuf[MAXCHARS];
234 /* A pointer into parabuf, indicating the first unused character position. */
237 /* The words of a paragraph -- longer paragraphs are handled neatly
238 (cf. flush_paragraph()). */
239 static WORD word[MAXWORDS];
241 /* A pointer into the above word array, indicating the first position
242 after the last complete word. Sometimes it will point at an incomplete
244 static WORD *word_limit;
246 /* If TRUE, current input file contains tab characters, and so tabs can be
247 used for white space on output. */
250 /* Space before trimmed prefix on each line of the current paragraph. */
251 static int prefix_indent;
253 /* Indentation of the first line of the current paragraph. */
254 static int first_indent;
256 /* Indentation of other lines of the current paragraph */
257 static int other_indent;
259 /* To detect the end of a paragraph, we need to look ahead to the first
260 non-blank character after the prefix on the next line, or the first
261 character on the following line that failed to match the prefix.
262 We can reconstruct the lookahead from that character (next_char), its
263 position on the line (in_column) and the amount of space before the
264 prefix (next_prefix_indent). See get_paragraph() and copy_rest(). */
266 /* The last character read from the input file. */
267 static int next_char;
269 /* The space before the trimmed prefix (or part of it) on the next line
270 after the current paragraph. */
271 static int next_prefix_indent;
273 /* If nonzero, the length of the last line output in the current
274 paragraph, used to charge for raggedness at the split point for long
275 paragraphs chosen by fmt_paragraph(). */
276 static int last_line_length;
282 fprintf (stderr, _("Try `%s --help' for more information.\n"),
286 printf (_("Usage: %s [-DIGITS] [OPTION]... [FILE]...\n"), program_name);
288 Reformat each paragraph in the FILE(s), writing to standard output.\n\
289 If no FILE or if FILE is `-', read standard input.\n\
291 Mandatory arguments to long options are mandatory for short options too.\n\
292 -c, --crown-margin preserve indentation of first two lines\n\
293 -s, --split-only split long lines, but do not refill\n\
294 -t, --tagged-paragraph indentation of first line different from second\n\
295 -u, --uniform-spacing one space between words, two after sentences\n\
296 -w, --width=NUMBER maximum line width (default of 75 columns)\n\
297 -p, --prefix=STRING combine only lines having STRING as prefix\n\
298 --help display this help and exit\n\
299 --version output version information and exit\n\
301 In -wNUMBER, the letter `w' may be omitted.\n"),
303 puts (_("\nReport bugs to bug-textutils@gnu.ai.mit.edu"));
305 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
308 /* Decode options and launch execution. */
310 static const struct option long_options[] =
312 {"crown-margin", no_argument, NULL, 'c'},
313 {"help", no_argument, &show_help, 1},
314 {"prefix", required_argument, NULL, 'p'},
315 {"split-only", no_argument, NULL, 's'},
316 {"tagged-paragraph", no_argument, NULL, 't'},
317 {"uniform-spacing", no_argument, NULL, 'u'},
318 {"version", no_argument, &show_version, 1},
319 {"width", required_argument, NULL, 'w'},
324 main (register int argc, register char **argv)
329 program_name = argv[0];
330 setlocale (LC_ALL, "");
331 bindtextdomain (PACKAGE, LOCALEDIR);
332 textdomain (PACKAGE);
334 crown = tagged = split = uniform = FALSE;
337 prefix_length = prefix_lead_space = prefix_full_length = 0;
339 if (argc > 1 && argv[1][0] == '-' && ISDIGIT (argv[1][1]))
342 /* Old option syntax; a dash followed by one or more digits.
343 Move past the number. */
344 for (++argv[1]; ISDIGIT (*argv[1]); ++argv[1])
346 /* FIXME: use strtol to detect overflow. */
347 max_width = max_width * 10 + *argv[1] - '0';
349 /* Make the options we just parsed invisible to getopt. */
355 while ((optchar = getopt_long (argc, argv, "0123456789cstuw:p:",
385 if (xstrtol (optarg, NULL, 10, &tmp_long, NULL) != LONGINT_OK
386 || tmp_long <= 0 || tmp_long > INT_MAX)
387 error (EXIT_FAILURE, 0, _("invalid line number increment: `%s'"),
389 max_width = (int) tmp_long;
401 printf ("fmt (%s) %s\n", GNU_PACKAGE, VERSION);
408 best_width = max_width * (2 * (100 - LEEWAY) + 1) / 200;
413 for (; optind < argc; optind++)
414 if (strcmp (argv[optind], "-") == 0)
418 infile = fopen (argv[optind], "r");
425 error (0, errno, argv[optind]);
431 /* Trim space from the front and back of the string P, yielding the prefix,
432 and record the lengths of the prefix and the space trimmed. */
435 set_prefix (register char *p)
439 prefix_lead_space = 0;
446 prefix_full_length = strlen (p);
447 s = p + prefix_full_length;
448 while (s > p && s[-1] == ' ')
451 prefix_length = s - p;
454 /* read file F and send formatted output to stdout. */
461 next_char = get_prefix (f);
462 while (get_paragraph (f))
465 put_paragraph (word_limit);
469 /* Read a paragraph from input file F. A paragraph consists of a
470 maximal number of non-blank (excluding any prefix) lines subject to:
471 * In split mode, a paragraph is a single non-blank line.
472 * In crown mode, the second and subsequent lines must have the
473 same indentation, but possibly different from the indent of the
475 * Tagged mode is similar, but the first and second lines must have
476 different indentations.
477 * Otherwise, all lines of a paragraph must have the same indent.
478 If a prefix is in effect, it must be present at the same indent for
479 each line in the paragraph.
481 Return FALSE if end-of-file was encountered before the start of a
482 paragraph, else TRUE. */
485 get_paragraph (FILE *f)
489 last_line_length = 0;
492 /* Scan (and copy) blank lines, and lines not introduced by the prefix. */
494 while (c == '\n' || c == EOF
495 || next_prefix_indent < prefix_lead_space
496 || in_column < next_prefix_indent + prefix_full_length)
498 c = copy_rest (f, c);
508 /* Got a suitable first line for a paragraph. */
510 prefix_indent = next_prefix_indent;
511 first_indent = in_column;
516 /* Read rest of paragraph (unless split is specified). */
519 other_indent = first_indent;
524 other_indent = in_column;
526 { /* for each line till the end of the para */
529 while (same_para (c) && in_column == other_indent);
532 other_indent = first_indent;
536 if (same_para (c) && in_column != first_indent)
538 other_indent = in_column;
540 { /* for each line till the end of the para */
543 while (same_para (c) && in_column == other_indent);
546 /* Only one line: use the secondary indent from last time if it
547 splits, or 0 if there have been no multi-line paragraphs in the
548 input so far. But if these rules make the two indents the same,
549 pick a new secondary indent. */
551 else if (other_indent == first_indent)
552 other_indent = first_indent == 0 ? DEF_INDENT : 0;
556 other_indent = first_indent;
557 while (same_para (c) && in_column == other_indent)
560 (word_limit - 1)->period = (word_limit - 1)->final = TRUE;
565 /* Copy to the output a line that failed to match the prefix, or that
566 was blank after the prefix. In the former case, C is the character
567 that failed to match the prefix. In the latter, C is \n or EOF.
568 Return the character (\n or EOF) ending the line. */
571 copy_rest (FILE *f, register int c)
573 register const char *s;
576 if (in_column > next_prefix_indent && c != '\n' && c != EOF)
578 put_space (next_prefix_indent);
579 for (s = prefix; out_column != in_column && *s; out_column++)
581 put_space (in_column - out_column);
583 while (c != '\n' && c != EOF)
591 /* Return TRUE if a line whose first non-blank character after the
592 prefix (if any) is C could belong to the current paragraph,
596 same_para (register int c)
598 return (next_prefix_indent == prefix_indent
599 && in_column >= next_prefix_indent + prefix_full_length
600 && c != '\n' && c != EOF);
603 /* Read a line from input file F, given first non-blank character C
604 after the prefix, and the following indent, and break it into words.
605 A word is a maximal non-empty string of non-white characters. A word
606 ending in [.?!]["')\]]* and followed by end-of-line or at least two
607 spaces ends a sentence, as in emacs.
609 Return the first non-blank character of the next line. */
612 get_line (FILE *f, register int c)
615 register char *end_of_parabuf;
616 register WORD *end_of_word;
618 end_of_parabuf = ¶buf[MAXCHARS];
619 end_of_word = &word[MAXWORDS - 2];
622 { /* for each word in a line */
626 word_limit->text = wptr;
629 if (wptr == end_of_parabuf)
634 while (c != EOF && !ISSPACE (c));
635 in_column += word_limit->length = wptr - word_limit->text;
636 check_punctuation (word_limit);
638 /* Scan inter-word space. */
641 c = get_space (f, c);
642 word_limit->space = in_column - start;
643 word_limit->final = (c == EOF
644 || (word_limit->period
645 && (c == '\n' || word_limit->space > 1)));
646 if (c == '\n' || c == EOF || uniform)
647 word_limit->space = word_limit->final ? 2 : 1;
648 if (word_limit == end_of_word)
655 return get_prefix (f);
658 /* Read a prefix from input file F. Return either first non-matching
659 character, or first non-blank character after the prefix. */
665 register const char *p;
668 c = get_space (f, getc (f));
669 if (prefix_length == 0)
670 next_prefix_indent = prefix_lead_space < in_column ?
671 prefix_lead_space : in_column;
674 next_prefix_indent = in_column;
675 for (p = prefix; *p != '\0'; p++)
682 c = get_space (f, c);
687 /* Read blank characters from input file F, starting with C, and keeping
688 in_column up-to-date. Return first non-blank character. */
691 get_space (FILE *f, register int c)
700 in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
708 /* Set extra fields in word W describing any attached punctuation. */
711 check_punctuation (register WORD *w)
713 register const char *start, *finish;
716 finish = start + (w->length - 1);
717 w->paren = isopen (*start);
718 w->punct = ISPUNCT (*finish);
719 while (isclose (*finish) && finish > start)
721 w->period = isperiod (*finish);
724 /* Flush part of the paragraph to make room. This function is called on
725 hitting the limit on the number of words or characters. */
728 flush_paragraph (void)
735 /* In the special case where it's all one word, just flush it. */
737 if (word_limit == word)
739 printf ("%*s", wptr - parabuf, parabuf);
745 - format what you have so far as a paragraph,
746 - find a low-cost line break near the end,
748 - make that the start of the paragraph. */
752 /* Choose a good split point. */
754 split_point = word_limit;
755 best_break = MAXCOST;
756 for (w = word->next_break; w != word_limit; w = w->next_break)
758 if (w->best_cost - w->next_break->best_cost < best_break)
761 best_break = w->best_cost - w->next_break->best_cost;
763 if (best_break <= MAXCOST - LINE_CREDIT)
764 best_break += LINE_CREDIT;
766 put_paragraph (split_point);
768 /* Copy text of words down to start of parabuf -- we use memmove because
769 the source and target may overlap. */
771 memmove (parabuf, split_point->text, (size_t) (wptr - split_point->text));
772 shift = split_point->text - parabuf;
775 /* Adjust text pointers. */
777 for (w = split_point; w <= word_limit; w++)
780 /* Copy words from split_point down to word -- we use memmove because
781 the source and target may overlap. */
783 memmove ((char *) word, (char *) split_point,
784 (word_limit - split_point + 1) * sizeof (WORD));
785 word_limit -= split_point - word;
788 /* Compute the optimal formatting for the whole paragraph by computing
789 and remembering the optimal formatting for each suffix from the empty
790 one to the whole paragraph. */
795 register WORD *start, *w;
797 register COST wcost, best;
800 word_limit->best_cost = 0;
801 saved_length = word_limit->length;
802 word_limit->length = max_width; /* sentinel */
804 for (start = word_limit - 1; start >= word; start--)
807 len = start == word ? first_indent : other_indent;
809 /* At least one word, however long, in the line. */
817 /* Consider breaking before w. */
819 wcost = line_cost (w, len) + w->best_cost;
820 if (start == word && last_line_length > 0)
821 wcost += RAGGED_COST (len - last_line_length);
825 start->next_break = w;
826 start->line_length = len;
828 len += (w - 1)->space + w->length; /* w > start >= word */
830 while (len < max_width);
831 start->best_cost = best + base_cost (start);
834 word_limit->length = saved_length;
837 /* Return the constant component of the cost of breaking before the
841 base_cost (register WORD *this)
849 if ((this - 1)->period)
851 if ((this - 1)->final)
852 cost -= SENTENCE_BONUS;
854 cost += NOBREAK_COST;
856 else if ((this - 1)->punct)
858 else if (this > word + 1 && (this - 2)->final)
859 cost += WIDOW_COST ((this - 1)->length);
864 else if (this->final)
865 cost += ORPHAN_COST (this->length);
870 /* Return the component of the cost of breaking before word NEXT that
871 depends on LEN, the length of the line beginning there. */
874 line_cost (register WORD *next, register int len)
879 if (next == word_limit)
881 n = best_width - len;
882 cost = SHORT_COST (n);
883 if (next->next_break != word_limit)
885 n = len - next->line_length;
886 cost += RAGGED_COST (n);
891 /* Output to stdout a paragraph from word up to (but not including)
892 FINISH, which must be in the next_break chain from word. */
895 put_paragraph (register WORD *finish)
899 put_line (word, first_indent);
900 for (w = word->next_break; w != finish; w = w->next_break)
901 put_line (w, other_indent);
904 /* Output to stdout the line beginning with word W, beginning in column
905 INDENT, including the prefix (if any). */
908 put_line (register WORD *w, int indent)
910 register WORD *endline;
913 put_space (prefix_indent);
914 fputs (prefix, stdout);
915 out_column += prefix_length;
916 put_space (indent - out_column);
918 endline = w->next_break - 1;
919 for (; w != endline; w++)
922 put_space (w->space);
925 last_line_length = out_column;
929 /* Output to stdout the word W. */
932 put_word (register WORD *w)
934 register const char *s;
938 for (n = w->length; n != 0; n--)
940 out_column += w->length;
943 /* Output to stdout SPACE spaces, or equivalent tabs. */
946 put_space (int space)
948 register int space_target, tab_target;
950 space_target = out_column + space;
953 tab_target = space_target / TABWIDTH * TABWIDTH;
954 if (out_column + 1 < tab_target)
955 while (out_column < tab_target)
958 out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
961 while (out_column < space_target)