1 /* GNU fmt -- simple text formatter.
2 Copyright (C) 1994-2006 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 Foundation,
16 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
18 /* Written by Ross Paterson <rap@doc.ic.ac.uk>. */
22 #include <sys/types.h>
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
34 /* The official name of this program (e.g., no `g' prefix). */
35 #define PROGRAM_NAME "fmt"
37 #define AUTHORS "Ross Paterson"
39 /* The following parameters represent the program's idea of what is
40 "best". Adjust to taste, subject to the caveats given. */
42 /* Default longest permitted line length (max_width). */
45 /* Prefer lines to be LEEWAY % shorter than the maximum width, giving
46 room for optimization. */
49 /* The default secondary indent of tagged paragraph used for unindented
50 one-line paragraphs not preceded by any multi-line paragraphs. */
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. */
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. */
64 typedef long int COST;
66 #define MAXCOST TYPE_MAXIMUM (COST)
68 #define SQR(n) ((n) * (n))
69 #define EQUIV(n) SQR ((COST) (n))
71 /* Cost of a filled line n chars longer or shorter than best_width. */
72 #define SHORT_COST(n) EQUIV ((n) * 10)
74 /* Cost of the difference between adjacent filled lines. */
75 #define RAGGED_COST(n) (SHORT_COST (n) / 2)
77 /* Basic cost per line. */
78 #define LINE_COST EQUIV (70)
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))
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))
88 /* Bonus for breaking a line at the end of a sentence. */
89 #define SENTENCE_BONUS EQUIV (50)
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
96 #define NOBREAK_COST EQUIV (600)
98 /* Bonus for breaking a line before open parenthesis. */
99 #define PAREN_BONUS EQUIV (40)
101 /* Bonus for breaking a line after other punctuation. */
102 #define PUNCT_BONUS EQUIV(40)
104 /* Credit for breaking a long paragraph one line later. */
105 #define LINE_CREDIT EQUIV(3)
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
114 #define MAXWORDS 1000
115 #define MAXCHARS 5000
117 /* Extra ctype(3)-style macros. */
119 #define isopen(c) (strchr ("([`'\"", c) != NULL)
120 #define isclose(c) (strchr (")]'\"", c) != NULL)
121 #define isperiod(c) (strchr (".?!", c) != NULL)
123 /* Size of a tab stop, for expansion on input and re-introduction on
127 /* Word descriptor structure. */
129 typedef struct Word WORD;
134 /* Static attributes determined during input. */
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 */
144 /* The remaining fields are computed during the optimization. */
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 */
151 /* Forward declarations. */
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);
171 /* The name this program was run with. */
172 const char *program_name;
176 /* If true, first 2 lines may have different indent (default false). */
179 /* If true, first 2 lines _must_ have different indent (default false). */
182 /* If true, each line is a paragraph on its own (default false). */
185 /* If true, don't preserve inter-word spacing (default false). */
188 /* Prefix minus leading and trailing spaces (default ""). */
189 static const char *prefix;
191 /* User-supplied maximum line width (default WIDTH). The only output
192 lines longer than this will each comprise a single word. */
193 static int max_width;
195 /* Values derived from the option values. */
197 /* The length of prefix minus leading space. */
198 static int prefix_full_length;
200 /* The length of the leading space trimmed from the prefix. */
201 static int prefix_lead_space;
203 /* The length of prefix minus leading and trailing space. */
204 static int prefix_length;
206 /* The preferred width of text lines, set to LEEWAY % less than max_width. */
207 static int best_width;
209 /* Dynamic variables. */
211 /* Start column of the character most recently read from the input file. */
212 static int in_column;
214 /* Start column of the next character to be written to stdout. */
215 static int out_column;
217 /* Space for the paragraph text -- longer paragraphs are handled neatly
218 (cf. flush_paragraph()). */
219 static char parabuf[MAXCHARS];
221 /* A pointer into parabuf, indicating the first unused character position. */
224 /* The words of a paragraph -- longer paragraphs are handled neatly
225 (cf. flush_paragraph()). */
226 static WORD word[MAXWORDS];
228 /* A pointer into the above word array, indicating the first position
229 after the last complete word. Sometimes it will point at an incomplete
231 static WORD *word_limit;
233 /* If true, current input file contains tab characters, and so tabs can be
234 used for white space on output. */
237 /* Space before trimmed prefix on each line of the current paragraph. */
238 static int prefix_indent;
240 /* Indentation of the first line of the current paragraph. */
241 static int first_indent;
243 /* Indentation of other lines of the current paragraph */
244 static int other_indent;
246 /* To detect the end of a paragraph, we need to look ahead to the first
247 non-blank character after the prefix on the next line, or the first
248 character on the following line that failed to match the prefix.
249 We can reconstruct the lookahead from that character (next_char), its
250 position on the line (in_column) and the amount of space before the
251 prefix (next_prefix_indent). See get_paragraph() and copy_rest(). */
253 /* The last character read from the input file. */
254 static int next_char;
256 /* The space before the trimmed prefix (or part of it) on the next line
257 after the current paragraph. */
258 static int next_prefix_indent;
260 /* If nonzero, the length of the last line output in the current
261 paragraph, used to charge for raggedness at the split point for long
262 paragraphs chosen by fmt_paragraph(). */
263 static int last_line_length;
268 if (status != EXIT_SUCCESS)
269 fprintf (stderr, _("Try `%s --help' for more information.\n"),
273 printf (_("Usage: %s [-DIGITS] [OPTION]... [FILE]...\n"), program_name);
275 Reformat each paragraph in the FILE(s), writing to standard output.\n\
276 If no FILE or if FILE is `-', read standard input.\n\
280 Mandatory arguments to long options are mandatory for short options too.\n\
283 -c, --crown-margin preserve indentation of first two lines\n\
284 -p, --prefix=STRING reformat only lines beginning with STRING,\n\
285 reattaching the prefix to reformatted lines\n\
286 -s, --split-only split long lines, but do not refill\n\
290 -t, --tagged-paragraph indentation of first line different from second\n\
291 -u, --uniform-spacing one space between words, two after sentences\n\
292 -w, --width=WIDTH maximum line width (default of 75 columns)\n\
294 fputs (HELP_OPTION_DESCRIPTION, stdout);
295 fputs (VERSION_OPTION_DESCRIPTION, stdout);
298 With no FILE, or when FILE is -, read standard input.\n"),
300 printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
305 /* Decode options and launch execution. */
307 static const struct option long_options[] =
309 {"crown-margin", no_argument, NULL, 'c'},
310 {"prefix", required_argument, NULL, 'p'},
311 {"split-only", no_argument, NULL, 's'},
312 {"tagged-paragraph", no_argument, NULL, 't'},
313 {"uniform-spacing", no_argument, NULL, 'u'},
314 {"width", required_argument, NULL, 'w'},
315 {GETOPT_HELP_OPTION_DECL},
316 {GETOPT_VERSION_OPTION_DECL},
321 main (int argc, char **argv)
325 char const *max_width_option = NULL;
327 initialize_main (&argc, &argv);
328 program_name = argv[0];
329 setlocale (LC_ALL, "");
330 bindtextdomain (PACKAGE, LOCALEDIR);
331 textdomain (PACKAGE);
333 atexit (close_stdout);
335 crown = tagged = split = uniform = false;
338 prefix_length = prefix_lead_space = prefix_full_length = 0;
340 if (argc > 1 && argv[1][0] == '-' && ISDIGIT (argv[1][1]))
342 /* Old option syntax; a dash followed by one or more digits. */
343 max_width_option = argv[1] + 1;
345 /* Make the option we just parsed invisible to getopt. */
351 while ((optchar = getopt_long (argc, argv, "0123456789cstuw:p:",
357 if (ISDIGIT (optchar))
358 error (0, 0, _("invalid option -- %c; -WIDTH is recognized\
359 only when it is the first\noption; use -w N instead"),
361 usage (EXIT_FAILURE);
380 max_width_option = optarg;
387 case_GETOPT_HELP_CHAR;
389 case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
393 if (max_width_option)
395 /* Limit max_width to MAXCHARS / 2; otherwise, the resulting
396 output can be quite ugly. */
397 unsigned long int tmp;
398 if (! (xstrtoul (max_width_option, NULL, 10, &tmp, "") == LONGINT_OK
399 && tmp <= MAXCHARS / 2))
400 error (EXIT_FAILURE, 0, _("invalid width: %s"),
401 quote (max_width_option));
405 best_width = max_width * (2 * (100 - LEEWAY) + 1) / 200;
411 for (; optind < argc; optind++)
413 char *file = argv[optind];
414 if (STREQ (file, "-"))
419 in_stream = fopen (file, "r");
420 if (in_stream != NULL)
423 if (fclose (in_stream) == EOF)
425 error (0, errno, "%s", file);
431 error (0, errno, _("cannot open %s for reading"),
439 exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
442 /* Trim space from the front and back of the string P, yielding the prefix,
443 and record the lengths of the prefix and the space trimmed. */
450 prefix_lead_space = 0;
457 prefix_full_length = strlen (p);
458 s = p + prefix_full_length;
459 while (s > p && s[-1] == ' ')
462 prefix_length = s - p;
465 /* read file F and send formatted output to stdout. */
472 next_char = get_prefix (f);
473 while (get_paragraph (f))
476 put_paragraph (word_limit);
480 /* Set the global variable `other_indent' according to SAME_PARAGRAPH
481 and other global variables. */
484 set_other_indent (bool same_paragraph)
487 other_indent = first_indent;
490 other_indent = (same_paragraph ? in_column : first_indent);
494 if (same_paragraph && in_column != first_indent)
496 other_indent = in_column;
499 /* Only one line: use the secondary indent from last time if it
500 splits, or 0 if there have been no multi-line paragraphs in the
501 input so far. But if these rules make the two indents the same,
502 pick a new secondary indent. */
504 else if (other_indent == first_indent)
505 other_indent = first_indent == 0 ? DEF_INDENT : 0;
509 other_indent = first_indent;
513 /* Read a paragraph from input file F. A paragraph consists of a
514 maximal number of non-blank (excluding any prefix) lines subject to:
515 * In split mode, a paragraph is a single non-blank line.
516 * In crown mode, the second and subsequent lines must have the
517 same indentation, but possibly different from the indent of the
519 * Tagged mode is similar, but the first and second lines must have
520 different indentations.
521 * Otherwise, all lines of a paragraph must have the same indent.
522 If a prefix is in effect, it must be present at the same indent for
523 each line in the paragraph.
525 Return false if end-of-file was encountered before the start of a
526 paragraph, else true. */
529 get_paragraph (FILE *f)
533 last_line_length = 0;
536 /* Scan (and copy) blank lines, and lines not introduced by the prefix. */
538 while (c == '\n' || c == EOF
539 || next_prefix_indent < prefix_lead_space
540 || in_column < next_prefix_indent + prefix_full_length)
542 c = copy_rest (f, c);
552 /* Got a suitable first line for a paragraph. */
554 prefix_indent = next_prefix_indent;
555 first_indent = in_column;
559 set_other_indent (same_para (c));
561 /* Read rest of paragraph (unless split is specified). */
572 { /* for each line till the end of the para */
575 while (same_para (c) && in_column == other_indent);
580 if (same_para (c) && in_column != first_indent)
583 { /* for each line till the end of the para */
586 while (same_para (c) && in_column == other_indent);
591 while (same_para (c) && in_column == other_indent)
594 (word_limit - 1)->period = (word_limit - 1)->final = true;
599 /* Copy to the output a line that failed to match the prefix, or that
600 was blank after the prefix. In the former case, C is the character
601 that failed to match the prefix. In the latter, C is \n or EOF.
602 Return the character (\n or EOF) ending the line. */
605 copy_rest (FILE *f, int c)
610 if (in_column > next_prefix_indent && c != '\n' && c != EOF)
612 put_space (next_prefix_indent);
613 for (s = prefix; out_column != in_column && *s; out_column++)
615 put_space (in_column - out_column);
617 while (c != '\n' && c != EOF)
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,
632 return (next_prefix_indent == prefix_indent
633 && in_column >= next_prefix_indent + prefix_full_length
634 && c != '\n' && c != EOF);
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.
643 Return the first non-blank character of the next line. */
646 get_line (FILE *f, int c)
649 char *end_of_parabuf;
652 end_of_parabuf = ¶buf[MAXCHARS];
653 end_of_word = &word[MAXWORDS - 2];
656 { /* for each word in a line */
660 word_limit->text = wptr;
663 if (wptr == end_of_parabuf)
665 set_other_indent (true);
671 while (c != EOF && !isspace (c));
672 in_column += word_limit->length = wptr - word_limit->text;
673 check_punctuation (word_limit);
675 /* Scan inter-word space. */
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)
687 set_other_indent (true);
695 return get_prefix (f);
698 /* Read a prefix from input file F. Return either first non-matching
699 character, or first non-blank character after the prefix. */
707 c = get_space (f, getc (f));
708 if (prefix_length == 0)
709 next_prefix_indent = prefix_lead_space < in_column ?
710 prefix_lead_space : in_column;
714 next_prefix_indent = in_column;
715 for (p = prefix; *p != '\0'; p++)
717 unsigned char pc = *p;
723 c = get_space (f, c);
728 /* Read blank characters from input file F, starting with C, and keeping
729 in_column up-to-date. Return first non-blank character. */
732 get_space (FILE *f, int c)
741 in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
749 /* Set extra fields in word W describing any attached punctuation. */
752 check_punctuation (WORD *w)
754 char const *start = w->text;
755 char const *finish = start + (w->length - 1);
756 unsigned char fin = *finish;
758 w->paren = isopen (*start);
759 w->punct = !! ispunct (fin);
760 while (start < finish && isclose (*finish))
762 w->period = isperiod (*finish);
765 /* Flush part of the paragraph to make room. This function is called on
766 hitting the limit on the number of words or characters. */
769 flush_paragraph (void)
776 /* In the special case where it's all one word, just flush it. */
778 if (word_limit == word)
780 fwrite (parabuf, sizeof *parabuf, wptr - parabuf, stdout);
786 - format what you have so far as a paragraph,
787 - find a low-cost line break near the end,
789 - make that the start of the paragraph. */
793 /* Choose a good split point. */
795 split_point = word_limit;
796 best_break = MAXCOST;
797 for (w = word->next_break; w != word_limit; w = w->next_break)
799 if (w->best_cost - w->next_break->best_cost < best_break)
802 best_break = w->best_cost - w->next_break->best_cost;
804 if (best_break <= MAXCOST - LINE_CREDIT)
805 best_break += LINE_CREDIT;
807 put_paragraph (split_point);
809 /* Copy text of words down to start of parabuf -- we use memmove because
810 the source and target may overlap. */
812 memmove (parabuf, split_point->text, wptr - split_point->text);
813 shift = split_point->text - parabuf;
816 /* Adjust text pointers. */
818 for (w = split_point; w <= word_limit; w++)
821 /* Copy words from split_point down to word -- we use memmove because
822 the source and target may overlap. */
824 memmove (word, split_point, (word_limit - split_point + 1) * sizeof *word);
825 word_limit -= split_point - word;
828 /* Compute the optimal formatting for the whole paragraph by computing
829 and remembering the optimal formatting for each suffix from the empty
830 one to the whole paragraph. */
840 word_limit->best_cost = 0;
841 saved_length = word_limit->length;
842 word_limit->length = max_width; /* sentinel */
844 for (start = word_limit - 1; start >= word; start--)
847 len = start == word ? first_indent : other_indent;
849 /* At least one word, however long, in the line. */
857 /* Consider breaking before w. */
859 wcost = line_cost (w, len) + w->best_cost;
860 if (start == word && last_line_length > 0)
861 wcost += RAGGED_COST (len - last_line_length);
865 start->next_break = w;
866 start->line_length = len;
869 /* This is a kludge to keep us from computing `len' as the
870 sum of the sentinel length and some non-zero number.
871 Since the sentinel w->length may be INT_MAX, adding
872 to that would give a negative result. */
876 len += (w - 1)->space + w->length; /* w > start >= word */
878 while (len < max_width);
879 start->best_cost = best + base_cost (start);
882 word_limit->length = saved_length;
885 /* Return the constant component of the cost of breaking before the
889 base_cost (WORD *this)
897 if ((this - 1)->period)
899 if ((this - 1)->final)
900 cost -= SENTENCE_BONUS;
902 cost += NOBREAK_COST;
904 else if ((this - 1)->punct)
906 else if (this > word + 1 && (this - 2)->final)
907 cost += WIDOW_COST ((this - 1)->length);
912 else if (this->final)
913 cost += ORPHAN_COST (this->length);
918 /* Return the component of the cost of breaking before word NEXT that
919 depends on LEN, the length of the line beginning there. */
922 line_cost (WORD *next, int len)
927 if (next == word_limit)
929 n = best_width - len;
930 cost = SHORT_COST (n);
931 if (next->next_break != word_limit)
933 n = len - next->line_length;
934 cost += RAGGED_COST (n);
939 /* Output to stdout a paragraph from word up to (but not including)
940 FINISH, which must be in the next_break chain from word. */
943 put_paragraph (WORD *finish)
947 put_line (word, first_indent);
948 for (w = word->next_break; w != finish; w = w->next_break)
949 put_line (w, other_indent);
952 /* Output to stdout the line beginning with word W, beginning in column
953 INDENT, including the prefix (if any). */
956 put_line (WORD *w, int indent)
961 put_space (prefix_indent);
962 fputs (prefix, stdout);
963 out_column += prefix_length;
964 put_space (indent - out_column);
966 endline = w->next_break - 1;
967 for (; w != endline; w++)
970 put_space (w->space);
973 last_line_length = out_column;
977 /* Output to stdout the word W. */
986 for (n = w->length; n != 0; n--)
988 out_column += w->length;
991 /* Output to stdout SPACE spaces, or equivalent tabs. */
994 put_space (int space)
996 int space_target, tab_target;
998 space_target = out_column + space;
1001 tab_target = space_target / TABWIDTH * TABWIDTH;
1002 if (out_column + 1 < tab_target)
1003 while (out_column < tab_target)
1006 out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
1009 while (out_column < space_target)