fmt.c revision 99112
1/*	$OpenBSD: fmt.c,v 1.16 2000/06/25 15:35:42 pjanzen Exp $	*/
2
3/* Sensible version of fmt
4 *
5 * Syntax: fmt [ options ] [ goal [ max ] ] [ filename ... ]
6 *
7 * Since the documentation for the original fmt is so poor, here
8 * is an accurate description of what this one does. It's usually
9 * the same. The *mechanism* used may differ from that suggested
10 * here. Note that we are *not* entirely compatible with fmt,
11 * because fmt gets so many things wrong.
12 *
13 * 1. Tabs are expanded, assuming 8-space tab stops.
14 *    If the `-t <n>' option is given, we assume <n>-space
15 *    tab stops instead.
16 *    Trailing blanks are removed from all lines.
17 *    x\b == nothing, for any x other than \b.
18 *    Other control characters are simply stripped. This
19 *    includes \r.
20 * 2. Each line is split into leading whitespace and
21 *    everything else. Maximal consecutive sequences of
22 *    lines with the same leading whitespace are considered
23 *    to form paragraphs, except that a blank line is always
24 *    a paragraph to itself.
25 *    If the `-p' option is given then the first line of a
26 *    paragraph is permitted to have indentation different
27 *    from that of the other lines.
28 *    If the `-m' option is given then a line that looks
29 *    like a mail message header, if it is not immediately
30 *    preceded by a non-blank non-message-header line, is
31 *    taken to start a new paragraph, which also contains
32 *    any subsequent lines with non-empty leading whitespace.
33 *    Unless the `-n' option is given, lines beginning with
34 *    a . (dot) are not formatted.
35 * 3. The "everything else" is split into words; a word
36 *    includes its trailing whitespace, and a word at the
37 *    end of a line is deemed to be followed by a single
38 *    space, or two spaces if it ends with a sentence-end
39 *    character. (See the `-d' option for how to change that.)
40 *    If the `-s' option has been given, then a word's trailing
41 *    whitespace is replaced by what it would have had if it
42 *    had occurred at end of line.
43 * 4. Each paragraph is sent to standard output as follows.
44 *    We output the leading whitespace, and then enough words
45 *    to make the line length as near as possible to the goal
46 *    without exceeding the maximum. (If a single word would
47 *    exceed the maximum, we output that anyway.) Of course
48 *    the trailing whitespace of the last word is ignored.
49 *    We then emit a newline and start again if there are any
50 *    words left.
51 *    Note that for a blank line this translates as "We emit
52 *    a newline".
53 *    If the `-l <n>' option is given, then leading whitespace
54 *    is modified slightly: <n> spaces are replaced by a tab.
55 *    Indented paragraphs (see above under `-p') make matters
56 *    more complicated than this suggests. Actually every paragraph
57 *    has two `leading whitespace' values; the value for the first
58 *    line, and the value for the most recent line. (While processing
59 *    the first line, the two are equal. When `-p' has not been
60 *    given, they are always equal.) The leading whitespace
61 *    actually output is that of the first line (for the first
62 *    line of *output*) or that of the most recent line (for
63 *    all other lines of output).
64 *    When `-m' has been given, message header paragraphs are
65 *    taken as having first-leading-whitespace empty and
66 *    subsequent-leading-whitespace two spaces.
67 *
68 * Multiple input files are formatted one at a time, so that a file
69 * never ends in the middle of a line.
70 *
71 * There's an alternative mode of operation, invoked by giving
72 * the `-c' option. In that case we just center every line,
73 * and most of the other options are ignored. This should
74 * really be in a separate program, but we must stay compatible
75 * with old `fmt'.
76 *
77 * QUERY: Should `-m' also try to do the right thing with quoted text?
78 * QUERY: `-b' to treat backslashed whitespace as old `fmt' does?
79 * QUERY: Option meaning `never join lines'?
80 * QUERY: Option meaning `split in mid-word to avoid overlong lines'?
81 * (Those last two might not be useful, since we have `fold'.)
82 *
83 * Differences from old `fmt':
84 *
85 *   - We have many more options. Options that aren't understood
86 *     generate a lengthy usage message, rather than being
87 *     treated as filenames.
88 *   - Even with `-m', our handling of message headers is
89 *     significantly different. (And much better.)
90 *   - We don't treat `\ ' as non-word-breaking.
91 *   - Downward changes of indentation start new paragraphs
92 *     for us, as well as upward. (I think old `fmt' behaves
93 *     in the way it does in order to allow indented paragraphs,
94 *     but this is a broken way of making indented paragraphs
95 *     behave right.)
96 *   - Given the choice of going over or under |goal_length|
97 *     by the same amount, we go over; old `fmt' goes under.
98 *   - We treat `?' as ending a sentence, and not `:'. Old `fmt'
99 *     does the reverse.
100 *   - We return approved return codes. Old `fmt' returns
101 *     1 for some errors, and *the number of unopenable files*
102 *     when that was all that went wrong.
103 *   - We have fewer crashes and more helpful error messages.
104 *   - We don't turn spaces into tabs at starts of lines unless
105 *     specifically requested.
106 *   - New `fmt' is somewhat smaller and slightly faster than
107 *     old `fmt'.
108 *
109 * Bugs:
110 *
111 *   None known. There probably are some, though.
112 *
113 * Portability:
114 *
115 *   I believe this code to be pretty portable. It does require
116 *   that you have `getopt'. If you need to include "getopt.h"
117 *   for this (e.g., if your system didn't come with `getopt'
118 *   and you installed it yourself) then you should arrange for
119 *   NEED_getopt_h to be #defined.
120 *
121 *   Everything here should work OK even on nasty 16-bit
122 *   machines and nice 64-bit ones. However, it's only really
123 *   been tested on my FreeBSD machine. Your mileage may vary.
124 */
125
126/* Copyright (c) 1997 Gareth McCaughan. All rights reserved.
127 *
128 * Redistribution and use of this code, in source or binary forms,
129 * with or without modification, are permitted subject to the following
130 * conditions:
131 *
132 *  - Redistribution of source code must retain the above copyright
133 *    notice, this list of conditions and the following disclaimer.
134 *
135 *  - If you distribute modified source code it must also include
136 *    a notice saying that it has been modified, and giving a brief
137 *    description of what changes have been made.
138 *
139 * Disclaimer: I am not responsible for the results of using this code.
140 *             If it formats your hard disc, sends obscene messages to
141 *             your boss and kills your children then that's your problem
142 *             not mine. I give absolutely no warranty of any sort as to
143 *             what the program will do, and absolutely refuse to be held
144 *             liable for any consequences of your using it.
145 *             Thank you. Have a nice day.
146 */
147
148/* RCS change log:
149 * Revision 1.5  1998/03/02 18:02:21  gjm11
150 * Minor changes for portability.
151 *
152 * Revision 1.4  1997/10/01 11:51:28  gjm11
153 * Repair broken indented-paragraph handling.
154 * Add mail message header stuff.
155 * Improve comments and layout.
156 * Make usable with non-BSD systems.
157 * Add revision display to usage message.
158 *
159 * Revision 1.3  1997/09/30 16:24:47  gjm11
160 * Add copyright notice, rcsid string and log message.
161 *
162 * Revision 1.2  1997/09/30 16:13:39  gjm11
163 * Add options: -d <chars>, -l <width>, -p, -s, -t <width>, -h .
164 * Parse options with `getopt'. Clean up code generally.
165 * Make comments more accurate.
166 *
167 * Revision 1.1  1997/09/30 11:29:57  gjm11
168 * Initial revision
169 */
170
171#ifndef lint
172static const char copyright[] =
173  "Copyright (c) 1997 Gareth McCaughan. All rights reserved.\n";
174#endif /* not lint */
175#include <sys/cdefs.h>
176__FBSDID("$FreeBSD: head/usr.bin/fmt/fmt.c 99112 2002-06-30 05:25:07Z obrien $");
177
178#include <ctype.h>
179#include <err.h>
180#include <locale.h>
181#include <stdio.h>
182#include <stdlib.h>
183#include <string.h>
184#include <sysexits.h>
185#include <unistd.h>
186
187/* Something that, we hope, will never be a genuine line length,
188 * indentation etc.
189 */
190#define SILLY ((size_t)-1)
191
192/* I used to use |strtoul| for this, but (1) not all systems have it
193 * and (2) it's probably better to use |strtol| to detect negative
194 * numbers better.
195 * If |fussyp==0| then we don't complain about non-numbers
196 * (returning 0 instead), but we do complain about bad numbers.
197 */
198static size_t
199get_positive(const char *s, const char *err_mess, int fussyP) {
200  char *t;
201  long result = strtol(s,&t,0);
202  if (*t) { if (fussyP) goto Lose; else return 0; }
203  if (result<=0) { Lose: errx(EX_USAGE, "%s", err_mess); }
204  return (size_t) result;
205}
206
207static size_t
208get_nonnegative(const char *s, const char *err_mess, int fussyP) {
209  char *t;
210  long result = strtol(s,&t,0);
211  if (*t) { if (fussyP) goto Lose; else return 0; }
212  if (result<0) { Lose: errx(EX_USAGE, "%s", err_mess); }
213  return (size_t) result;
214}
215
216/* Global variables */
217
218static int centerP=0;		/* Try to center lines? */
219static size_t goal_length=0;	/* Target length for output lines */
220static size_t max_length=0;	/* Maximum length for output lines */
221static int coalesce_spaces_P=0;	/* Coalesce multiple whitespace -> ' ' ? */
222static int allow_indented_paragraphs=0;	/* Can first line have diff. ind.? */
223static int tab_width=8;		/* Number of spaces per tab stop */
224static size_t output_tab_width=8;	/* Ditto, when squashing leading spaces */
225static const char *sentence_enders=".?!";	/* Double-space after these */
226static int grok_mail_headers=0;	/* treat embedded mail headers magically? */
227static int format_troff=0;	/* Format troff? */
228
229static int n_errors=0;		/* Number of failed files. Return on exit. */
230static char *output_buffer=0;	/* Output line will be built here */
231static size_t x;		/* Horizontal position in output line */
232static size_t x0;		/* Ditto, ignoring leading whitespace */
233static size_t pending_spaces;	/* Spaces to add before next word */
234static int output_in_paragraph=0;	/* Any of current para written out yet? */
235
236/* Prototypes */
237
238static void process_named_file (const char *);
239static void     process_stream (FILE *, const char *);
240static size_t    indent_length (const char *, size_t);
241static int     might_be_header (const unsigned char *);
242static void      new_paragraph (size_t, size_t);
243static void        output_word (size_t, size_t, const char *, size_t, size_t);
244static void      output_indent (size_t);
245static void      center_stream (FILE *, const char *);
246static char *         get_line (FILE *, size_t *);
247static void *         xrealloc (void *, size_t);
248
249#define XMALLOC(x) xrealloc(0,x)
250
251/* Here is perhaps the right place to mention that this code is
252 * all in top-down order. Hence, |main| comes first.
253 */
254int
255main(int argc, char *argv[]) {
256  int ch;			/* used for |getopt| processing */
257
258
259  (void) setlocale(LC_CTYPE, "");
260
261  /* 1. Grok parameters. */
262
263  while ((ch = getopt(argc, argv, "0123456789cd:hl:mnpst:w:")) != -1)
264  switch(ch) {
265    case 'c':
266      centerP = 1;
267      format_troff = 1;
268      continue;
269    case 'd':
270      sentence_enders = optarg;
271      continue;
272    case 'l':
273      output_tab_width
274        = get_nonnegative(optarg, "output tab width must be non-negative", 1);
275      continue;
276    case 'm':
277      grok_mail_headers = 1;
278      continue;
279    case 'n':
280      format_troff = 1;
281      continue;
282    case 'p':
283      allow_indented_paragraphs = 1;
284      continue;
285    case 's':
286      coalesce_spaces_P = 1;
287      continue;
288    case 't':
289      tab_width = get_positive(optarg, "tab width must be positive", 1);
290      continue;
291    case 'w':
292      goal_length = get_positive(optarg, "width must be positive", 1);
293      max_length = goal_length;
294      continue;
295    case '0': case '1': case '2': case '3': case '4': case '5':
296    case '6': case '7': case '8': case '9':
297    /* XXX  this is not a stylistically approved use of getopt() */
298      if (goal_length==0) {
299        char *p;
300        p = argv[optind - 1];
301        if (p[0] == '-' && p[1] == ch && !p[2])
302             goal_length = get_positive(++p, "width must be nonzero", 1);
303        else
304             goal_length = get_positive(argv[optind]+1,
305                 "width must be nonzero", 1);
306        max_length = goal_length;
307      }
308      continue;
309    case 'h': default:
310      fprintf(stderr,
311"usage:   fmt [-cmps] [-d chars] [-l num] [-t num]\n"
312"             [-w width | -width | goal [maximum]] [file ...]\n"
313"Options: -c     center each line instead of formatting\n"
314"         -d <chars> double-space after <chars> at line end\n"
315"         -l <n> turn each <n> spaces at start of line into a tab\n"
316"         -m     try to make sure mail header lines stay separate\n"
317"         -n     format lines beginning with a dot\n"
318"         -p     allow indented paragraphs\n"
319"         -s     coalesce whitespace inside lines\n"
320"         -t <n> have tabs every <n> columns\n"
321"         -w <n> set maximum width to <n>\n"
322"         goal   set target width to goal\n");
323      exit(ch=='h' ? 0 : EX_USAGE);
324  }
325  argc -= optind; argv += optind;
326
327  /* [ goal [ maximum ] ] */
328
329  if (argc>0 && goal_length==0
330      && (goal_length=get_positive(*argv,"goal length must be positive", 0))
331         != 0) {
332    --argc; ++argv;
333    if (argc>0
334        && (max_length=get_positive(*argv,"max length must be positive", 0))
335           != 0) {
336      --argc; ++argv;
337      if (max_length<goal_length)
338        errx(EX_USAGE, "max length must be >= goal length");
339    }
340  }
341  if (goal_length==0) goal_length = 65;
342  if (max_length==0) max_length = goal_length+10;
343  output_buffer = XMALLOC(max_length+1);	/* really needn't be longer */
344
345  /* 2. Process files. */
346
347  if (argc>0) {
348    while (argc-->0) process_named_file(*argv++);
349  }
350  else {
351    process_stream(stdin, "standard input");
352  }
353
354  /* We're done. */
355
356  return n_errors ? EX_NOINPUT : 0;
357
358}
359
360/* Process a single file, given its name.
361 */
362static void
363process_named_file(const char *name) {
364  FILE *f=fopen(name, "r");
365  if (!f) { perror(name); ++n_errors; }
366  else {
367    process_stream(f, name);
368    fclose(f);
369  }
370}
371
372/* Types of mail header continuation lines:
373 */
374typedef enum {
375  hdr_ParagraphStart = -1,
376  hdr_NonHeader      = 0,
377  hdr_Header         = 1,
378  hdr_Continuation   = 2
379} HdrType;
380
381/* Process a stream. This is where the real work happens,
382 * except that centering is handled separately.
383 */
384static void
385process_stream(FILE *stream, const char *name) {
386  size_t last_indent=SILLY;	/* how many spaces in last indent? */
387  size_t para_line_number=0;	/* how many lines already read in this para? */
388  size_t first_indent=SILLY;	/* indentation of line 0 of paragraph */
389  HdrType prev_header_type=hdr_ParagraphStart;
390	/* ^-- header_type of previous line; -1 at para start */
391  char *line;
392  size_t length;
393
394  if (centerP) { center_stream(stream, name); return; }
395  while ((line=get_line(stream,&length)) != NULL) {
396    size_t np=indent_length(line, length);
397    { HdrType header_type=hdr_NonHeader;
398      if (grok_mail_headers && prev_header_type!=hdr_NonHeader) {
399        if (np==0 && might_be_header(line))
400          header_type = hdr_Header;
401        else if (np>0 && prev_header_type>hdr_NonHeader)
402          header_type = hdr_Continuation;
403      }
404      /* We need a new paragraph if and only if:
405       *   this line is blank,
406       *   OR it's a troff request (and we don't format troff),
407       *   OR it's a mail header,
408       *   OR it's not a mail header AND the last line was one,
409       *   OR the indentation has changed
410       *      AND the line isn't a mail header continuation line
411       *      AND this isn't the second line of an indented paragraph.
412       */
413      if ( length==0
414           || (line[0]=='.' && !format_troff)
415           || header_type==hdr_Header
416           || (header_type==hdr_NonHeader && prev_header_type>hdr_NonHeader)
417           || (np!=last_indent
418               && header_type != hdr_Continuation
419               && (!allow_indented_paragraphs || para_line_number != 1)) ) {
420        new_paragraph(output_in_paragraph ? last_indent : first_indent, np);
421        para_line_number = 0;
422        first_indent = np;
423        last_indent = np;
424        if (header_type==hdr_Header) last_indent=2;	/* for cont. lines */
425        if (length==0 || (line[0]=='.' && !format_troff)) {
426          if (length==0)
427            putchar('\n');
428          else
429            printf("%.*s\n", (int)length, line);
430          prev_header_type=hdr_ParagraphStart;
431          continue;
432        }
433      }
434      else {
435        /* If this is an indented paragraph other than a mail header
436         * continuation, set |last_indent|.
437         */
438        if (np != last_indent && header_type != hdr_Continuation)
439          last_indent=np;
440      }
441      prev_header_type = header_type;
442    }
443
444    { size_t n=np;
445      while (n<length) {
446        /* Find word end and count spaces after it */
447        size_t word_length=0, space_length=0;
448        while (n+word_length < length && line[n+word_length] != ' ')
449          ++word_length;
450        space_length = word_length;
451        while (n+space_length < length && line[n+space_length] == ' ')
452          ++space_length;
453        /* Send the word to the output machinery. */
454        output_word(first_indent, last_indent,
455                    line+n, word_length, space_length-word_length);
456        n += space_length;
457      }
458    }
459    ++para_line_number;
460  }
461  new_paragraph(output_in_paragraph ? last_indent : first_indent, 0);
462  if (ferror(stream)) { perror(name); ++n_errors; }
463}
464
465/* How long is the indent on this line?
466 */
467static size_t
468indent_length(const char *line, size_t length) {
469  size_t n=0;
470  while (n<length && *line++ == ' ') ++n;
471  return n;
472}
473
474/* Might this line be a mail header?
475 * We deem a line to be a possible header if it matches the
476 * Perl regexp /^[A-Z][-A-Za-z0-9]*:\s/. This is *not* the same
477 * as in RFC whatever-number-it-is; we want to be gratuitously
478 * conservative to avoid mangling ordinary civilised text.
479 */
480static int
481might_be_header(const unsigned char *line) {
482  if (!isupper(*line++)) return 0;
483  while (*line && (isalnum(*line) || *line=='-')) ++line;
484  return (*line==':' && isspace(line[1]));
485}
486
487/* Begin a new paragraph with an indent of |indent| spaces.
488 */
489static void
490new_paragraph(size_t old_indent, size_t indent) {
491  if (x0) {
492    if (old_indent>0) output_indent(old_indent);
493    fwrite(output_buffer, 1, x0, stdout);
494    putchar('\n');
495  }
496  x=indent; x0=0; pending_spaces=0;
497  output_in_paragraph = 0;
498}
499
500/* Output spaces or tabs for leading indentation.
501 */
502static void
503output_indent(size_t n_spaces) {
504  if (output_tab_width) {
505    while (n_spaces >= output_tab_width) {
506      putchar('\t');
507      n_spaces -= output_tab_width;
508    }
509  }
510  while (n_spaces-- > 0) putchar(' ');
511}
512
513/* Output a single word, or add it to the buffer.
514 * indent0 and indent1 are the indents to use on the first and subsequent
515 * lines of a paragraph. They'll often be the same, of course.
516 */
517static void
518output_word(size_t indent0, size_t indent1, const char *word, size_t length, size_t spaces) {
519  size_t new_x = x+pending_spaces+length;
520  size_t indent = output_in_paragraph ? indent1 : indent0;
521
522  /* If either |spaces==0| (at end of line) or |coalesce_spaces_P|
523   * (squashing internal whitespace), then add just one space;
524   * except that if the last character was a sentence-ender we
525   * actually add two spaces.
526   */
527  if (coalesce_spaces_P || spaces==0)
528    spaces = strchr(sentence_enders, word[length-1]) ? 2 : 1;
529
530  if (new_x<=goal_length) {
531    /* After adding the word we still aren't at the goal length,
532     * so clearly we add it to the buffer rather than outputing it.
533     */
534    memset(output_buffer+x0, ' ', pending_spaces);
535    x0 += pending_spaces; x += pending_spaces;
536    memcpy(output_buffer+x0, word, length);
537    x0 += length; x += length;
538    pending_spaces = spaces;
539  }
540  else {
541    /* Adding the word takes us past the goal. Print the line-so-far,
542     * and the word too iff either (1) the lsf is empty or (2) that
543     * makes us nearer the goal but doesn't take us over the limit,
544     * or (3) the word on its own takes us over the limit.
545     * In case (3) we put a newline in between.
546     */
547    if (indent>0) output_indent(indent);
548    fwrite(output_buffer, 1, x0, stdout);
549    if (x0==0 || (new_x <= max_length && new_x-goal_length <= goal_length-x)) {
550      printf("%*s", (int)pending_spaces, "");
551      goto write_out_word;
552    }
553    else {
554      /* If the word takes us over the limit on its own, just
555       * spit it out and don't bother buffering it.
556       */
557      if (indent+length > max_length) {
558        putchar('\n');
559        if (indent>0) output_indent(indent);
560write_out_word:
561        fwrite(word, 1, length, stdout);
562        x0 = 0; x = indent1; pending_spaces = 0;
563      }
564      else {
565        memcpy(output_buffer, word, length);
566        x0 = length; x = length+indent1; pending_spaces = spaces;
567      }
568    }
569    putchar('\n');
570    output_in_paragraph = 1;
571  }
572}
573
574/* Process a stream, but just center its lines rather than trying to
575 * format them neatly.
576 */
577static void
578center_stream(FILE *stream, const char *name) {
579  char *line;
580  size_t length;
581  while ((line=get_line(stream, &length)) != 0) {
582    size_t l=length;
583    while (l>0 && isspace(*line)) { ++line; --l; }
584    length=l;
585    while (l<goal_length) { putchar(' '); l+=2; }
586    fwrite(line, 1, length, stdout);
587    putchar('\n');
588  }
589  if (ferror(stream)) { perror(name); ++n_errors; }
590}
591
592/* Get a single line from a stream. Expand tabs, strip control
593 * characters and trailing whitespace, and handle backspaces.
594 * Return the address of the buffer containing the line, and
595 * put the length of the line in |lengthp|.
596 * This can cope with arbitrarily long lines, and with lines
597 * without terminating \n.
598 * If there are no characters left or an error happens, we
599 * return 0.
600 * Don't confuse |spaces_pending| here with the global
601 * |pending_spaces|.
602 */
603static char *
604get_line(FILE *stream, size_t *lengthp) {
605  static char *buf=NULL;
606  static size_t length=0;
607  size_t len=0;
608  int ch;
609  size_t spaces_pending=0;
610  int troff=0;
611
612  if (buf==NULL) { length=100; buf=XMALLOC(length); }
613  while ((ch=getc(stream)) != '\n' && ch != EOF) {
614    if (len+spaces_pending==0 && ch=='.' && !format_troff) troff=1;
615    if (ch==' ') ++spaces_pending;
616    else if (troff || isprint(ch)) {
617      while (len+spaces_pending >= length) {
618        length*=2; buf=xrealloc(buf, length);
619      }
620      while (spaces_pending > 0) { --spaces_pending; buf[len++]=' '; }
621      buf[len++] = ch;
622    }
623    else if (ch=='\t')
624      spaces_pending += tab_width - (len+spaces_pending)%tab_width;
625    else if (ch=='\b') { if (len) --len; }
626  }
627  *lengthp=len;
628  return (len>0 || ch!=EOF) ? buf : 0;
629}
630
631/* (Re)allocate some memory, exiting with an error if we can't.
632 */
633static void *
634xrealloc(void *ptr, size_t nbytes) {
635  void *p = realloc(ptr, nbytes);
636  if (p == NULL) errx(EX_OSERR, "out of memory");
637  return p;
638}
639