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 if (c != EOF && c != '\n')
616 put_space (in_column - out_column);
617 if (c == EOF && in_column >= next_prefix_indent + prefix_length)
620 while (c != '\n' && c != EOF)
628 /* Return true if a line whose first non-blank character after the
629 prefix (if any) is C could belong to the current paragraph,
635 return (next_prefix_indent == prefix_indent
636 && in_column >= next_prefix_indent + prefix_full_length
637 && c != '\n' && c != EOF);
640 /* Read a line from input file F, given first non-blank character C
641 after the prefix, and the following indent, and break it into words.
642 A word is a maximal non-empty string of non-white characters. A word
643 ending in [.?!]["')\]]* and followed by end-of-line or at least two
644 spaces ends a sentence, as in emacs.
646 Return the first non-blank character of the next line. */
649 get_line (FILE *f, int c)
652 char *end_of_parabuf;
655 end_of_parabuf = ¶buf[MAXCHARS];
656 end_of_word = &word[MAXWORDS - 2];
659 { /* for each word in a line */
663 word_limit->text = wptr;
666 if (wptr == end_of_parabuf)
668 set_other_indent (true);
674 while (c != EOF && !isspace (c));
675 in_column += word_limit->length = wptr - word_limit->text;
676 check_punctuation (word_limit);
678 /* Scan inter-word space. */
681 c = get_space (f, c);
682 word_limit->space = in_column - start;
683 word_limit->final = (c == EOF
684 || (word_limit->period
685 && (c == '\n' || word_limit->space > 1)));
686 if (c == '\n' || c == EOF || uniform)
687 word_limit->space = word_limit->final ? 2 : 1;
688 if (word_limit == end_of_word)
690 set_other_indent (true);
695 while (c != '\n' && c != EOF);
696 return get_prefix (f);
699 /* Read a prefix from input file F. Return either first non-matching
700 character, or first non-blank character after the prefix. */
708 c = get_space (f, getc (f));
709 if (prefix_length == 0)
710 next_prefix_indent = prefix_lead_space < in_column ?
711 prefix_lead_space : in_column;
715 next_prefix_indent = in_column;
716 for (p = prefix; *p != '\0'; p++)
718 unsigned char pc = *p;
724 c = get_space (f, c);
729 /* Read blank characters from input file F, starting with C, and keeping
730 in_column up-to-date. Return first non-blank character. */
733 get_space (FILE *f, int c)
742 in_column = (in_column / TABWIDTH + 1) * TABWIDTH;
750 /* Set extra fields in word W describing any attached punctuation. */
753 check_punctuation (WORD *w)
755 char const *start = w->text;
756 char const *finish = start + (w->length - 1);
757 unsigned char fin = *finish;
759 w->paren = isopen (*start);
760 w->punct = !! ispunct (fin);
761 while (start < finish && isclose (*finish))
763 w->period = isperiod (*finish);
766 /* Flush part of the paragraph to make room. This function is called on
767 hitting the limit on the number of words or characters. */
770 flush_paragraph (void)
777 /* In the special case where it's all one word, just flush it. */
779 if (word_limit == word)
781 fwrite (parabuf, sizeof *parabuf, wptr - parabuf, stdout);
787 - format what you have so far as a paragraph,
788 - find a low-cost line break near the end,
790 - make that the start of the paragraph. */
794 /* Choose a good split point. */
796 split_point = word_limit;
797 best_break = MAXCOST;
798 for (w = word->next_break; w != word_limit; w = w->next_break)
800 if (w->best_cost - w->next_break->best_cost < best_break)
803 best_break = w->best_cost - w->next_break->best_cost;
805 if (best_break <= MAXCOST - LINE_CREDIT)
806 best_break += LINE_CREDIT;
808 put_paragraph (split_point);
810 /* Copy text of words down to start of parabuf -- we use memmove because
811 the source and target may overlap. */
813 memmove (parabuf, split_point->text, wptr - split_point->text);
814 shift = split_point->text - parabuf;
817 /* Adjust text pointers. */
819 for (w = split_point; w <= word_limit; w++)
822 /* Copy words from split_point down to word -- we use memmove because
823 the source and target may overlap. */
825 memmove (word, split_point, (word_limit - split_point + 1) * sizeof *word);
826 word_limit -= split_point - word;
829 /* Compute the optimal formatting for the whole paragraph by computing
830 and remembering the optimal formatting for each suffix from the empty
831 one to the whole paragraph. */
841 word_limit->best_cost = 0;
842 saved_length = word_limit->length;
843 word_limit->length = max_width; /* sentinel */
845 for (start = word_limit - 1; start >= word; start--)
848 len = start == word ? first_indent : other_indent;
850 /* At least one word, however long, in the line. */
858 /* Consider breaking before w. */
860 wcost = line_cost (w, len) + w->best_cost;
861 if (start == word && last_line_length > 0)
862 wcost += RAGGED_COST (len - last_line_length);
866 start->next_break = w;
867 start->line_length = len;
870 /* This is a kludge to keep us from computing `len' as the
871 sum of the sentinel length and some non-zero number.
872 Since the sentinel w->length may be INT_MAX, adding
873 to that would give a negative result. */
877 len += (w - 1)->space + w->length; /* w > start >= word */
879 while (len < max_width);
880 start->best_cost = best + base_cost (start);
883 word_limit->length = saved_length;
886 /* Return the constant component of the cost of breaking before the
890 base_cost (WORD *this)
898 if ((this - 1)->period)
900 if ((this - 1)->final)
901 cost -= SENTENCE_BONUS;
903 cost += NOBREAK_COST;
905 else if ((this - 1)->punct)
907 else if (this > word + 1 && (this - 2)->final)
908 cost += WIDOW_COST ((this - 1)->length);
913 else if (this->final)
914 cost += ORPHAN_COST (this->length);
919 /* Return the component of the cost of breaking before word NEXT that
920 depends on LEN, the length of the line beginning there. */
923 line_cost (WORD *next, int len)
928 if (next == word_limit)
930 n = best_width - len;
931 cost = SHORT_COST (n);
932 if (next->next_break != word_limit)
934 n = len - next->line_length;
935 cost += RAGGED_COST (n);
940 /* Output to stdout a paragraph from word up to (but not including)
941 FINISH, which must be in the next_break chain from word. */
944 put_paragraph (WORD *finish)
948 put_line (word, first_indent);
949 for (w = word->next_break; w != finish; w = w->next_break)
950 put_line (w, other_indent);
953 /* Output to stdout the line beginning with word W, beginning in column
954 INDENT, including the prefix (if any). */
957 put_line (WORD *w, int indent)
962 put_space (prefix_indent);
963 fputs (prefix, stdout);
964 out_column += prefix_length;
965 put_space (indent - out_column);
967 endline = w->next_break - 1;
968 for (; w != endline; w++)
971 put_space (w->space);
974 last_line_length = out_column;
978 /* Output to stdout the word W. */
987 for (n = w->length; n != 0; n--)
989 out_column += w->length;
992 /* Output to stdout SPACE spaces, or equivalent tabs. */
995 put_space (int space)
997 int space_target, tab_target;
999 space_target = out_column + space;
1002 tab_target = space_target / TABWIDTH * TABWIDTH;
1003 if (out_column + 1 < tab_target)
1004 while (out_column < tab_target)
1007 out_column = (out_column / TABWIDTH + 1) * TABWIDTH;
1010 while (out_column < space_target)