Most .c files (AUTHORS): Revert the WRITTEN_BY/AUTHORS change
[platform/upstream/coreutils.git] / src / ptx.c
1 /* Permuted index for GNU, with keywords in their context.
2    Copyright (C) 1990, 1991, 1993, 1998-2003 Free Software Foundation, Inc.
3    François Pinard <pinard@iro.umontreal.ca>, 1988.
4
5    This program is free software; you can redistribute it and/or modify
6    it under the terms of the GNU General Public License as published by
7    the Free Software Foundation; either version 2, or (at your option)
8    any later version.
9
10    This program is distributed in the hope that it will be useful, but
11    WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software Foundation,
17    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18
19    François Pinard <pinard@iro.umontreal.ca> */
20
21 #include <config.h>
22
23 #include <stdio.h>
24 #include <getopt.h>
25 #include <sys/types.h>
26 #include "system.h"
27 #include "argmatch.h"
28 #include "diacrit.h"
29 #include "error.h"
30 #include "regex.h"
31
32 /* The official name of this program (e.g., no `g' prefix).  */
33 #define PROGRAM_NAME "ptx"
34
35 /* Note to translator: Please translate "F. Pinard" to "François
36    Pinard" if "ç" (c-with-cedilla) is available in the
37    translation's character set and encoding.  */
38 #define AUTHORS _("F. Pinard")
39
40 /* Number of possible characters in a byte.  */
41 #define CHAR_SET_SIZE 256
42
43 #define ISODIGIT(C) ((C) >= '0' && (C) <= '7')
44 #define HEXTOBIN(C) ((C) >= 'a' && (C) <= 'f' ? (C)-'a'+10 \
45                      : (C) >= 'A' && (C) <= 'F' ? (C)-'A'+10 : (C)-'0')
46 #define OCTTOBIN(C) ((C) - '0')
47
48 /* Debugging the memory allocator.  */
49
50 #if WITH_DMALLOC
51 # define MALLOC_FUNC_CHECK 1
52 # include <dmalloc.h>
53 #endif
54 \f
55 /* Global definitions.  */
56
57 /* Reallocation step when swallowing non regular files.  The value is not
58    the actual reallocation step, but its base two logarithm.  */
59 #define SWALLOW_REALLOC_LOG 12
60
61 /* Imported from "regex.c".  */
62 #define Sword 1
63
64 /* The name this program was run with. */
65 char *program_name;
66
67 /* Program options.  */
68
69 enum Format
70 {
71   UNKNOWN_FORMAT,               /* output format still unknown */
72   DUMB_FORMAT,                  /* output for a dumb terminal */
73   ROFF_FORMAT,                  /* output for `troff' or `nroff' */
74   TEX_FORMAT                    /* output for `TeX' or `LaTeX' */
75 };
76
77 int gnu_extensions = 1;         /* trigger all GNU extensions */
78 int auto_reference = 0;         /* references are `file_name:line_number:' */
79 int input_reference = 0;        /* references at beginning of input lines */
80 int right_reference = 0;        /* output references after right context  */
81 int line_width = 72;            /* output line width in characters */
82 int gap_size = 3;               /* number of spaces between output fields */
83 const char *truncation_string = "/";
84                                 /* string used to mark line truncations */
85 const char *macro_name = "xx";  /* macro name for roff or TeX output */
86 enum Format output_format = UNKNOWN_FORMAT;
87                                 /* output format */
88
89 int ignore_case = 0;            /* fold lower to upper case for sorting */
90 const char *context_regex_string = NULL;
91                                 /* raw regex for end of context */
92 const char *word_regex_string = NULL;
93                                 /* raw regex for a keyword */
94 const char *break_file = NULL;  /* name of the `Break characters' file */
95 const char *only_file = NULL;   /* name of the `Only words' file */
96 const char *ignore_file = NULL; /* name of the `Ignore words' file */
97
98 /* A BLOCK delimit a region in memory of arbitrary size, like the copy of a
99    whole file.  A WORD is something smaller, its length should fit in a
100    short integer.  A WORD_TABLE may contain several WORDs.  */
101
102 typedef struct
103   {
104     char *start;                /* pointer to beginning of region */
105     char *end;                  /* pointer to end + 1 of region */
106   }
107 BLOCK;
108
109 typedef struct
110   {
111     char *start;                /* pointer to beginning of region */
112     short size;                 /* length of the region */
113   }
114 WORD;
115
116 typedef struct
117   {
118     WORD *start;                /* array of WORDs */
119     size_t alloc;               /* allocated length */
120     size_t length;              /* number of used entries */
121   }
122 WORD_TABLE;
123
124 /* Pattern description tables.  */
125
126 /* For each character, provide its folded equivalent.  */
127 unsigned char folded_chars[CHAR_SET_SIZE];
128
129 /* For each character, indicate if it is part of a word.  */
130 char syntax_table[CHAR_SET_SIZE];
131 char *re_syntax_table = syntax_table;
132
133 /* Compiled regex for end of context.  */
134 struct re_pattern_buffer *context_regex;
135
136 /* End of context pattern register indices.  */
137 struct re_registers context_regs;
138
139 /* Compiled regex for a keyword.  */
140 struct re_pattern_buffer *word_regex;
141
142 /* Keyword pattern register indices.  */
143 struct re_registers word_regs;
144
145 /* A word characters fastmap is used only when no word regexp has been
146    provided.  A word is then made up of a sequence of one or more characters
147    allowed by the fastmap.  Contains !0 if character allowed in word.  Not
148    only this is faster in most cases, but it simplifies the implementation
149    of the Break files.  */
150 char word_fastmap[CHAR_SET_SIZE];
151
152 /* Maximum length of any word read.  */
153 int maximum_word_length;
154
155 /* Maximum width of any reference used.  */
156 int reference_max_width;
157
158 /* Ignore and Only word tables.  */
159
160 WORD_TABLE ignore_table;        /* table of words to ignore */
161 WORD_TABLE only_table;          /* table of words to select */
162
163 /* Source text table, and scanning macros.  */
164
165 int number_input_files;         /* number of text input files */
166 int total_line_count;           /* total number of lines seen so far */
167 const char **input_file_name;   /* array of text input file names */
168 int *file_line_count;           /* array of `total_line_count' values at end */
169
170 BLOCK text_buffer;              /* file to study */
171 char *text_buffer_maxend;       /* allocated end of text_buffer */
172
173 /* SKIP_NON_WHITE used only for getting or skipping the reference.  */
174
175 #define SKIP_NON_WHITE(cursor, limit) \
176   while (cursor < limit && !ISSPACE(*cursor))                           \
177     cursor++
178
179 #define SKIP_WHITE(cursor, limit) \
180   while (cursor < limit && ISSPACE(*cursor))                            \
181     cursor++
182
183 #define SKIP_WHITE_BACKWARDS(cursor, start) \
184   while (cursor > start && ISSPACE(cursor[-1]))                         \
185     cursor--
186
187 #define SKIP_SOMETHING(cursor, limit) \
188   if (word_regex_string)                                                \
189     {                                                                   \
190       int count;                                                        \
191       count = re_match (word_regex, cursor, limit - cursor, 0, NULL);   \
192       cursor += count <= 0 ? 1 : count;                                 \
193     }                                                                   \
194   else if (word_fastmap[(unsigned char) *cursor])                       \
195     while (cursor < limit && word_fastmap[(unsigned char) *cursor])     \
196       cursor++;                                                         \
197   else                                                                  \
198     cursor++
199
200 /* Occurrences table.
201
202    The `keyword' pointer provides the central word, which is surrounded
203    by a left context and a right context.  The `keyword' and `length'
204    field allow full 8-bit characters keys, even including NULs.  At other
205    places in this program, the name `keyafter' refers to the keyword
206    followed by its right context.
207
208    The left context does not extend, towards the beginning of the file,
209    further than a distance given by the `left' value.  This value is
210    relative to the keyword beginning, it is usually negative.  This
211    insures that, except for white space, we will never have to backward
212    scan the source text, when it is time to generate the final output
213    lines.
214
215    The right context, indirectly attainable through the keyword end, does
216    not extend, towards the end of the file, further than a distance given
217    by the `right' value.  This value is relative to the keyword
218    beginning, it is usually positive.
219
220    When automatic references are used, the `reference' value is the
221    overall line number in all input files read so far, in this case, it
222    is of type (int).  When input references are used, the `reference'
223    value indicates the distance between the keyword beginning and the
224    start of the reference field, it is of type (DELTA) and usually
225    negative.  */
226
227 typedef short DELTA;            /* to hold displacement within one context */
228
229 typedef struct
230   {
231     WORD key;                   /* description of the keyword */
232     DELTA left;                 /* distance to left context start */
233     DELTA right;                /* distance to right context end */
234     int reference;              /* reference descriptor */
235   }
236 OCCURS;
237
238 /* The various OCCURS tables are indexed by the language.  But the time
239    being, there is no such multiple language support.  */
240
241 OCCURS *occurs_table[1];        /* all words retained from the read text */
242 size_t occurs_alloc[1];         /* allocated size of occurs_table */
243 size_t number_of_occurs[1];     /* number of used slots in occurs_table */
244
245
246 /* Communication among output routines.  */
247
248 /* Indicate if special output processing is requested for each character.  */
249 char edited_flag[CHAR_SET_SIZE];
250
251 int half_line_width;            /* half of line width, reference excluded */
252 int before_max_width;           /* maximum width of before field */
253 int keyafter_max_width;         /* maximum width of keyword-and-after field */
254 int truncation_string_length;   /* length of string used to flag truncation */
255
256 /* When context is limited by lines, wraparound may happen on final output:
257    the `head' pointer gives access to some supplementary left context which
258    will be seen at the end of the output line, the `tail' pointer gives
259    access to some supplementary right context which will be seen at the
260    beginning of the output line. */
261
262 BLOCK tail;                     /* tail field */
263 int tail_truncation;            /* flag truncation after the tail field */
264
265 BLOCK before;                   /* before field */
266 int before_truncation;          /* flag truncation before the before field */
267
268 BLOCK keyafter;                 /* keyword-and-after field */
269 int keyafter_truncation;        /* flag truncation after the keyafter field */
270
271 BLOCK head;                     /* head field */
272 int head_truncation;            /* flag truncation before the head field */
273
274 BLOCK reference;                /* reference field for input reference mode */
275 \f
276 /* Miscellaneous routines.  */
277
278 /*------------------------------------------------------.
279 | Duplicate string STRING, while evaluating \-escapes.  |
280 `------------------------------------------------------*/
281
282 /* Loosely adapted from GNU sh-utils printf.c code.  */
283
284 static char *
285 copy_unescaped_string (const char *string)
286 {
287   char *result;                 /* allocated result */
288   char *cursor;                 /* cursor in result */
289   int value;                    /* value of \nnn escape */
290   int length;                   /* length of \nnn escape */
291
292   result = xmalloc (strlen (string) + 1);
293   cursor = result;
294
295   while (*string)
296     if (*string == '\\')
297       {
298         string++;
299         switch (*string)
300           {
301           case 'x':             /* \xhhh escape, 3 chars maximum */
302             value = 0;
303             for (length = 0, string++;
304                  length < 3 && ISXDIGIT (*string);
305                  length++, string++)
306               value = value * 16 + HEXTOBIN (*string);
307             if (length == 0)
308               {
309                 *cursor++ = '\\';
310                 *cursor++ = 'x';
311               }
312             else
313               *cursor++ = value;
314             break;
315
316           case '0':             /* \0ooo escape, 3 chars maximum */
317             value = 0;
318             for (length = 0, string++;
319                  length < 3 && ISODIGIT (*string);
320                  length++, string++)
321               value = value * 8 + OCTTOBIN (*string);
322             *cursor++ = value;
323             break;
324
325           case 'a':             /* alert */
326 #if __STDC__
327             *cursor++ = '\a';
328 #else
329             *cursor++ = 7;
330 #endif
331             string++;
332             break;
333
334           case 'b':             /* backspace */
335             *cursor++ = '\b';
336             string++;
337             break;
338
339           case 'c':             /* cancel the rest of the output */
340             while (*string)
341               string++;
342             break;
343
344           case 'f':             /* form feed */
345             *cursor++ = '\f';
346             string++;
347             break;
348
349           case 'n':             /* new line */
350             *cursor++ = '\n';
351             string++;
352             break;
353
354           case 'r':             /* carriage return */
355             *cursor++ = '\r';
356             string++;
357             break;
358
359           case 't':             /* horizontal tab */
360             *cursor++ = '\t';
361             string++;
362             break;
363
364           case 'v':             /* vertical tab */
365 #if __STDC__
366             *cursor++ = '\v';
367 #else
368             *cursor++ = 11;
369 #endif
370             string++;
371             break;
372
373           default:
374             *cursor++ = '\\';
375             *cursor++ = *string++;
376             break;
377           }
378       }
379     else
380       *cursor++ = *string++;
381
382   *cursor = '\0';
383   return result;
384 }
385
386 /*-------------------------------------------------------------------.
387 | Compile the regex represented by STRING, diagnose and abort if any |
388 | error.  Returns the compiled regex structure.                      |
389 `-------------------------------------------------------------------*/
390
391 static struct re_pattern_buffer *
392 alloc_and_compile_regex (const char *string)
393 {
394   struct re_pattern_buffer *pattern; /* newly allocated structure */
395   const char *message;          /* error message returned by regex.c */
396
397   pattern = (struct re_pattern_buffer *)
398     xmalloc (sizeof (struct re_pattern_buffer));
399   memset (pattern, 0, sizeof (struct re_pattern_buffer));
400
401   pattern->buffer = NULL;
402   pattern->allocated = 0;
403   pattern->translate = ignore_case ? (char *) folded_chars : NULL;
404   pattern->fastmap = xmalloc ((size_t) CHAR_SET_SIZE);
405
406   message = re_compile_pattern (string, (int) strlen (string), pattern);
407   if (message)
408     error (EXIT_FAILURE, 0, _("%s (for regexp `%s')"), message, string);
409
410   /* The fastmap should be compiled before `re_match'.  The following
411      call is not mandatory, because `re_search' is always called sooner,
412      and it compiles the fastmap if this has not been done yet.  */
413
414   re_compile_fastmap (pattern);
415
416   /* Do not waste extra allocated space.  */
417
418   if (pattern->allocated > pattern->used)
419     {
420       pattern->buffer
421         = xrealloc (pattern->buffer, (size_t) pattern->used);
422       pattern->allocated = pattern->used;
423     }
424
425   return pattern;
426 }
427
428 /*------------------------------------------------------------------------.
429 | This will initialize various tables for pattern match and compiles some |
430 | regexps.                                                                |
431 `------------------------------------------------------------------------*/
432
433 static void
434 initialize_regex (void)
435 {
436   int character;                /* character value */
437
438   /* Initialize the regex syntax table.  */
439
440   for (character = 0; character < CHAR_SET_SIZE; character++)
441     syntax_table[character] = ISALPHA (character) ? Sword : 0;
442
443   /* Initialize the case folding table.  */
444
445   if (ignore_case)
446     for (character = 0; character < CHAR_SET_SIZE; character++)
447       folded_chars[character] = TOUPPER (character);
448
449   /* Unless the user already provided a description of the end of line or
450      end of sentence sequence, select an end of line sequence to compile.
451      If the user provided an empty definition, thus disabling end of line
452      or sentence feature, make it NULL to speed up tests.  If GNU
453      extensions are enabled, use end of sentence like in GNU emacs.  If
454      disabled, use end of lines.  */
455
456   if (context_regex_string)
457     {
458       if (!*context_regex_string)
459         context_regex_string = NULL;
460     }
461   else if (gnu_extensions && !input_reference)
462     context_regex_string = "[.?!][]\"')}]*\\($\\|\t\\|  \\)[ \t\n]*";
463   else
464     context_regex_string = "\n";
465
466   if (context_regex_string)
467     context_regex = alloc_and_compile_regex (context_regex_string);
468
469   /* If the user has already provided a non-empty regexp to describe
470      words, compile it.  Else, unless this has already been done through
471      a user provided Break character file, construct a fastmap of
472      characters that may appear in a word.  If GNU extensions enabled,
473      include only letters of the underlying character set.  If disabled,
474      include almost everything, even punctuations; stop only on white
475      space.  */
476
477   if (word_regex_string && *word_regex_string)
478     word_regex = alloc_and_compile_regex (word_regex_string);
479   else if (!break_file)
480     {
481       if (gnu_extensions)
482         {
483
484           /* Simulate \w+.  */
485
486           for (character = 0; character < CHAR_SET_SIZE; character++)
487             word_fastmap[character] = ISALPHA (character) ? 1 : 0;
488         }
489       else
490         {
491
492           /* Simulate [^ \t\n]+.  */
493
494           memset (word_fastmap, 1, CHAR_SET_SIZE);
495           word_fastmap[' '] = 0;
496           word_fastmap['\t'] = 0;
497           word_fastmap['\n'] = 0;
498         }
499     }
500 }
501
502 /*------------------------------------------------------------------------.
503 | This routine will attempt to swallow a whole file name FILE_NAME into a |
504 | contiguous region of memory and return a description of it into BLOCK.  |
505 | Standard input is assumed whenever FILE_NAME is NULL, empty or "-".     |
506 |                                                                         |
507 | Previously, in some cases, white space compression was attempted while  |
508 | inputting text.  This was defeating some regexps like default end of    |
509 | sentence, which checks for two consecutive spaces.  If white space      |
510 | compression is ever reinstated, it should be in output routines.        |
511 `------------------------------------------------------------------------*/
512
513 static void
514 swallow_file_in_memory (const char *file_name, BLOCK *block)
515 {
516   int file_handle;              /* file descriptor number */
517   struct stat stat_block;       /* stat block for file */
518   size_t allocated_length;      /* allocated length of memory buffer */
519   size_t used_length;           /* used length in memory buffer */
520   int read_length;              /* number of character gotten on last read */
521
522   /* As special cases, a file name which is NULL or "-" indicates standard
523      input, which is already opened.  In all other cases, open the file from
524      its name.  */
525   bool using_stdin = !file_name || !*file_name || strcmp (file_name, "-") == 0;
526   if (using_stdin)
527     file_handle = STDIN_FILENO;
528   else
529     if ((file_handle = open (file_name, O_RDONLY)) < 0)
530       error (EXIT_FAILURE, errno, "%s", file_name);
531
532   /* If the file is a plain, regular file, allocate the memory buffer all at
533      once and swallow the file in one blow.  In other cases, read the file
534      repeatedly in smaller chunks until we have it all, reallocating memory
535      once in a while, as we go.  */
536
537   if (fstat (file_handle, &stat_block) < 0)
538     error (EXIT_FAILURE, errno, "%s", file_name);
539
540   if (S_ISREG (stat_block.st_mode))
541     {
542       size_t in_memory_size;
543
544       block->start = xmalloc ((size_t) stat_block.st_size);
545
546       if ((in_memory_size = read (file_handle,
547                                   block->start, (size_t) stat_block.st_size))
548           != stat_block.st_size)
549         {
550 #if MSDOS
551           /* On MSDOS, in memory size may be smaller than the file
552              size, because of end of line conversions.  But it can
553              never be smaller than half the file size, because the
554              minimum is when all lines are empty and terminated by
555              CR+LF.  */
556           if (in_memory_size != (size_t)-1
557               && in_memory_size >= stat_block.st_size / 2)
558             block->start = xrealloc (block->start, in_memory_size);
559           else
560 #endif /* not MSDOS */
561
562             error (EXIT_FAILURE, errno, "%s", file_name);
563         }
564       block->end = block->start + in_memory_size;
565     }
566   else
567     {
568       block->start = xmalloc ((size_t) 1 << SWALLOW_REALLOC_LOG);
569       used_length = 0;
570       allocated_length = (1 << SWALLOW_REALLOC_LOG);
571
572       while (read_length = read (file_handle,
573                                  block->start + used_length,
574                                  allocated_length - used_length),
575              read_length > 0)
576         {
577           used_length += read_length;
578           if (used_length == allocated_length)
579             {
580               allocated_length += (1 << SWALLOW_REALLOC_LOG);
581               block->start
582                 = xrealloc (block->start, allocated_length);
583             }
584         }
585
586       if (read_length < 0)
587         error (EXIT_FAILURE, errno, "%s", file_name);
588
589       block->end = block->start + used_length;
590     }
591
592   /* Close the file, but only if it was not the standard input.  */
593
594   if (! using_stdin && close (file_handle) != 0)
595     error (EXIT_FAILURE, errno, "%s", file_name);
596 }
597 \f
598 /* Sort and search routines.  */
599
600 /*--------------------------------------------------------------------------.
601 | Compare two words, FIRST and SECOND, and return 0 if they are identical.  |
602 | Return less than 0 if the first word goes before the second; return       |
603 | greater than 0 if the first word goes after the second.                   |
604 |                                                                           |
605 | If a word is indeed a prefix of the other, the shorter should go first.   |
606 `--------------------------------------------------------------------------*/
607
608 static int
609 compare_words (const void *void_first, const void *void_second)
610 {
611 #define first ((const WORD *) void_first)
612 #define second ((const WORD *) void_second)
613   int length;                   /* minimum of two lengths */
614   int counter;                  /* cursor in words */
615   int value;                    /* value of comparison */
616
617   length = first->size < second->size ? first->size : second->size;
618
619   if (ignore_case)
620     {
621       for (counter = 0; counter < length; counter++)
622         {
623           value = (folded_chars [(unsigned char) (first->start[counter])]
624                    - folded_chars [(unsigned char) (second->start[counter])]);
625           if (value != 0)
626             return value;
627         }
628     }
629   else
630     {
631       for (counter = 0; counter < length; counter++)
632         {
633           value = ((unsigned char) first->start[counter]
634                    - (unsigned char) second->start[counter]);
635           if (value != 0)
636             return value;
637         }
638     }
639
640   return first->size - second->size;
641 #undef first
642 #undef second
643 }
644
645 /*-----------------------------------------------------------------------.
646 | Decides which of two OCCURS, FIRST or SECOND, should lexicographically |
647 | go first.  In case of a tie, preserve the original order through a     |
648 | pointer comparison.                                                    |
649 `-----------------------------------------------------------------------*/
650
651 static int
652 compare_occurs (const void *void_first, const void *void_second)
653 {
654 #define first ((const OCCURS *) void_first)
655 #define second ((const OCCURS *) void_second)
656   int value;
657
658   value = compare_words (&first->key, &second->key);
659   return value == 0 ? first->key.start - second->key.start : value;
660 #undef first
661 #undef second
662 }
663
664 /*------------------------------------------------------------.
665 | Return !0 if WORD appears in TABLE.  Uses a binary search.  |
666 `------------------------------------------------------------*/
667
668 static int
669 search_table (WORD *word, WORD_TABLE *table)
670 {
671   int lowest;                   /* current lowest possible index */
672   int highest;                  /* current highest possible index */
673   int middle;                   /* current middle index */
674   int value;                    /* value from last comparison */
675
676   lowest = 0;
677   highest = table->length - 1;
678   while (lowest <= highest)
679     {
680       middle = (lowest + highest) / 2;
681       value = compare_words (word, table->start + middle);
682       if (value < 0)
683         highest = middle - 1;
684       else if (value > 0)
685         lowest = middle + 1;
686       else
687         return 1;
688     }
689   return 0;
690 }
691
692 /*---------------------------------------------------------------------.
693 | Sort the whole occurs table in memory.  Presumably, `qsort' does not |
694 | take intermediate copies or table elements, so the sort will be      |
695 | stabilized throughout the comparison routine.                        |
696 `---------------------------------------------------------------------*/
697
698 static void
699 sort_found_occurs (void)
700 {
701
702   /* Only one language for the time being.  */
703
704   qsort (occurs_table[0], number_of_occurs[0], sizeof (OCCURS),
705          compare_occurs);
706 }
707 \f
708 /* Parameter files reading routines.  */
709
710 /*----------------------------------------------------------------------.
711 | Read a file named FILE_NAME, containing a set of break characters.    |
712 | Build a content to the array word_fastmap in which all characters are |
713 | allowed except those found in the file.  Characters may be repeated.  |
714 `----------------------------------------------------------------------*/
715
716 static void
717 digest_break_file (const char *file_name)
718 {
719   BLOCK file_contents;          /* to receive a copy of the file */
720   char *cursor;                 /* cursor in file copy */
721
722   swallow_file_in_memory (file_name, &file_contents);
723
724   /* Make the fastmap and record the file contents in it.  */
725
726   memset (word_fastmap, 1, CHAR_SET_SIZE);
727   for (cursor = file_contents.start; cursor < file_contents.end; cursor++)
728     word_fastmap[(unsigned char) *cursor] = 0;
729
730   if (!gnu_extensions)
731     {
732
733       /* If GNU extensions are enabled, the only way to avoid newline as
734          a break character is to write all the break characters in the
735          file with no newline at all, not even at the end of the file.
736          If disabled, spaces, tabs and newlines are always considered as
737          break characters even if not included in the break file.  */
738
739       word_fastmap[' '] = 0;
740       word_fastmap['\t'] = 0;
741       word_fastmap['\n'] = 0;
742     }
743
744   /* Return the space of the file, which is no more required.  */
745
746   free (file_contents.start);
747 }
748
749 /*-----------------------------------------------------------------------.
750 | Read a file named FILE_NAME, containing one word per line, then        |
751 | construct in TABLE a table of WORD descriptors for them.  The routine  |
752 | swallows the whole file in memory; this is at the expense of space     |
753 | needed for newlines, which are useless; however, the reading is fast.  |
754 `-----------------------------------------------------------------------*/
755
756 static void
757 digest_word_file (const char *file_name, WORD_TABLE *table)
758 {
759   BLOCK file_contents;          /* to receive a copy of the file */
760   char *cursor;                 /* cursor in file copy */
761   char *word_start;             /* start of the current word */
762
763   swallow_file_in_memory (file_name, &file_contents);
764
765   table->start = NULL;
766   table->alloc = 0;
767   table->length = 0;
768
769   /* Read the whole file.  */
770
771   cursor = file_contents.start;
772   while (cursor < file_contents.end)
773     {
774
775       /* Read one line, and save the word in contains.  */
776
777       word_start = cursor;
778       while (cursor < file_contents.end && *cursor != '\n')
779         cursor++;
780
781       /* Record the word in table if it is not empty.  */
782
783       if (cursor > word_start)
784         {
785           if (table->length == table->alloc)
786             {
787               if ((SIZE_MAX / sizeof *table->start - 1) / 2 < table->alloc)
788                 xalloc_die ();
789               table->alloc = table->alloc * 2 + 1;
790               table->start = xrealloc (table->start,
791                                        table->alloc * sizeof *table->start);
792             }
793
794           table->start[table->length].start = word_start;
795           table->start[table->length].size = cursor - word_start;
796           table->length++;
797         }
798
799       /* This test allows for an incomplete line at end of file.  */
800
801       if (cursor < file_contents.end)
802         cursor++;
803     }
804
805   /* Finally, sort all the words read.  */
806
807   qsort (table->start, table->length, (size_t) sizeof (WORD), compare_words);
808 }
809 \f
810 /* Keyword recognition and selection.  */
811
812 /*----------------------------------------------------------------------.
813 | For each keyword in the source text, constructs an OCCURS structure.  |
814 `----------------------------------------------------------------------*/
815
816 static void
817 find_occurs_in_text (void)
818 {
819   char *cursor;                 /* for scanning the source text */
820   char *scan;                   /* for scanning the source text also */
821   char *line_start;             /* start of the current input line */
822   char *line_scan;              /* newlines scanned until this point */
823   int reference_length;         /* length of reference in input mode */
824   WORD possible_key;            /* possible key, to ease searches */
825   OCCURS *occurs_cursor;        /* current OCCURS under construction */
826
827   char *context_start;          /* start of left context */
828   char *context_end;            /* end of right context */
829   char *word_start;             /* start of word */
830   char *word_end;               /* end of word */
831   char *next_context_start;     /* next start of left context */
832
833   /* reference_length is always used within `if (input_reference)'.
834      However, GNU C diagnoses that it may be used uninitialized.  The
835      following assignment is merely to shut it up.  */
836
837   reference_length = 0;
838
839   /* Tracking where lines start is helpful for reference processing.  In
840      auto reference mode, this allows counting lines.  In input reference
841      mode, this permits finding the beginning of the references.
842
843      The first line begins with the file, skip immediately this very first
844      reference in input reference mode, to help further rejection any word
845      found inside it.  Also, unconditionally assigning these variable has
846      the happy effect of shutting up lint.  */
847
848   line_start = text_buffer.start;
849   line_scan = line_start;
850   if (input_reference)
851     {
852       SKIP_NON_WHITE (line_scan, text_buffer.end);
853       reference_length = line_scan - line_start;
854       SKIP_WHITE (line_scan, text_buffer.end);
855     }
856
857   /* Process the whole buffer, one line or one sentence at a time.  */
858
859   for (cursor = text_buffer.start;
860        cursor < text_buffer.end;
861        cursor = next_context_start)
862     {
863
864       /* `context_start' gets initialized before the processing of each
865          line, or once for the whole buffer if no end of line or sentence
866          sequence separator.  */
867
868       context_start = cursor;
869
870       /* If a end of line or end of sentence sequence is defined and
871          non-empty, `next_context_start' will be recomputed to be the end of
872          each line or sentence, before each one is processed.  If no such
873          sequence, then `next_context_start' is set at the end of the whole
874          buffer, which is then considered to be a single line or sentence.
875          This test also accounts for the case of an incomplete line or
876          sentence at the end of the buffer.  */
877
878       if (context_regex_string
879           && (re_search (context_regex, cursor, text_buffer.end - cursor,
880                          0, text_buffer.end - cursor, &context_regs)
881               >= 0))
882         next_context_start = cursor + context_regs.end[0];
883
884       else
885         next_context_start = text_buffer.end;
886
887       /* Include the separator into the right context, but not any suffix
888          white space in this separator; this insures it will be seen in
889          output and will not take more space than necessary.  */
890
891       context_end = next_context_start;
892       SKIP_WHITE_BACKWARDS (context_end, context_start);
893
894       /* Read and process a single input line or sentence, one word at a
895          time.  */
896
897       while (1)
898         {
899           if (word_regex)
900
901             /* If a word regexp has been compiled, use it to skip at the
902                beginning of the next word.  If there is no such word, exit
903                the loop.  */
904
905             {
906               if (re_search (word_regex, cursor, context_end - cursor,
907                              0, context_end - cursor, &word_regs)
908                   < 0)
909                 break;
910               word_start = cursor + word_regs.start[0];
911               word_end = cursor + word_regs.end[0];
912             }
913           else
914
915             /* Avoid re_search and use the fastmap to skip to the
916                beginning of the next word.  If there is no more word in
917                the buffer, exit the loop.  */
918
919             {
920               scan = cursor;
921               while (scan < context_end
922                      && !word_fastmap[(unsigned char) *scan])
923                 scan++;
924
925               if (scan == context_end)
926                 break;
927
928               word_start = scan;
929
930               while (scan < context_end
931                      && word_fastmap[(unsigned char) *scan])
932                 scan++;
933
934               word_end = scan;
935             }
936
937           /* Skip right to the beginning of the found word.  */
938
939           cursor = word_start;
940
941           /* Skip any zero length word.  Just advance a single position,
942              then go fetch the next word.  */
943
944           if (word_end == word_start)
945             {
946               cursor++;
947               continue;
948             }
949
950           /* This is a genuine, non empty word, so save it as a possible
951              key.  Then skip over it.  Also, maintain the maximum length of
952              all words read so far.  It is mandatory to take the maximum
953              length of all words in the file, without considering if they
954              are actually kept or rejected, because backward jumps at output
955              generation time may fall in *any* word.  */
956
957           possible_key.start = cursor;
958           possible_key.size = word_end - word_start;
959           cursor += possible_key.size;
960
961           if (possible_key.size > maximum_word_length)
962             maximum_word_length = possible_key.size;
963
964           /* In input reference mode, update `line_start' from its previous
965              value.  Count the lines just in case auto reference mode is
966              also selected. If it happens that the word just matched is
967              indeed part of a reference; just ignore it.  */
968
969           if (input_reference)
970             {
971               while (line_scan < possible_key.start)
972                 if (*line_scan == '\n')
973                   {
974                     total_line_count++;
975                     line_scan++;
976                     line_start = line_scan;
977                     SKIP_NON_WHITE (line_scan, text_buffer.end);
978                     reference_length = line_scan - line_start;
979                   }
980                 else
981                   line_scan++;
982               if (line_scan > possible_key.start)
983                 continue;
984             }
985
986           /* Ignore the word if an `Ignore words' table exists and if it is
987              part of it.  Also ignore the word if an `Only words' table and
988              if it is *not* part of it.
989
990              It is allowed that both tables be used at once, even if this
991              may look strange for now.  Just ignore a word that would appear
992              in both.  If regexps are eventually implemented for these
993              tables, the Ignore table could then reject words that would
994              have been previously accepted by the Only table.  */
995
996           if (ignore_file && search_table (&possible_key, &ignore_table))
997             continue;
998           if (only_file && !search_table (&possible_key, &only_table))
999             continue;
1000
1001           /* A non-empty word has been found.  First of all, insure
1002              proper allocation of the next OCCURS, and make a pointer to
1003              where it will be constructed.  */
1004
1005           if (number_of_occurs[0] == occurs_alloc[0])
1006             {
1007               if ((SIZE_MAX / sizeof *occurs_table[0] - 1) / 2
1008                   < occurs_alloc[0])
1009                 xalloc_die ();
1010               occurs_alloc[0] = occurs_alloc[0] * 2 + 1;
1011               occurs_table[0] = xrealloc (occurs_table[0],
1012                                           occurs_alloc[0] * sizeof *occurs_table[0]);
1013             }
1014
1015           occurs_cursor = occurs_table[0] + number_of_occurs[0];
1016
1017           /* Define the refence field, if any.  */
1018
1019           if (auto_reference)
1020             {
1021
1022               /* While auto referencing, update `line_start' from its
1023                  previous value, counting lines as we go.  If input
1024                  referencing at the same time, `line_start' has been
1025                  advanced earlier, and the following loop is never really
1026                  executed.  */
1027
1028               while (line_scan < possible_key.start)
1029                 if (*line_scan == '\n')
1030                   {
1031                     total_line_count++;
1032                     line_scan++;
1033                     line_start = line_scan;
1034                     SKIP_NON_WHITE (line_scan, text_buffer.end);
1035                   }
1036                 else
1037                   line_scan++;
1038
1039               occurs_cursor->reference = total_line_count;
1040             }
1041           else if (input_reference)
1042             {
1043
1044               /* If only input referencing, `line_start' has been computed
1045                  earlier to detect the case the word matched would be part
1046                  of the reference.  The reference position is simply the
1047                  value of `line_start'.  */
1048
1049               occurs_cursor->reference
1050                 = (DELTA) (line_start - possible_key.start);
1051               if (reference_length > reference_max_width)
1052                 reference_max_width = reference_length;
1053             }
1054
1055           /* Exclude the reference from the context in simple cases.  */
1056
1057           if (input_reference && line_start == context_start)
1058             {
1059               SKIP_NON_WHITE (context_start, context_end);
1060               SKIP_WHITE (context_start, context_end);
1061             }
1062
1063           /* Completes the OCCURS structure.  */
1064
1065           occurs_cursor->key = possible_key;
1066           occurs_cursor->left = context_start - possible_key.start;
1067           occurs_cursor->right = context_end - possible_key.start;
1068
1069           number_of_occurs[0]++;
1070         }
1071     }
1072 }
1073 \f
1074 /* Formatting and actual output - service routines.  */
1075
1076 /*-----------------------------------------.
1077 | Prints some NUMBER of spaces on stdout.  |
1078 `-----------------------------------------*/
1079
1080 static void
1081 print_spaces (int number)
1082 {
1083   int counter;
1084
1085   for (counter = number; counter > 0; counter--)
1086     putchar (' ');
1087 }
1088
1089 /*-------------------------------------.
1090 | Prints the field provided by FIELD.  |
1091 `-------------------------------------*/
1092
1093 static void
1094 print_field (BLOCK field)
1095 {
1096   char *cursor;                 /* Cursor in field to print */
1097   int character;                /* Current character */
1098   int base;                     /* Base character, without diacritic */
1099   int diacritic;                /* Diacritic code for the character */
1100
1101   /* Whitespace is not really compressed.  Instead, each white space
1102      character (tab, vt, ht etc.) is printed as one single space.  */
1103
1104   for (cursor = field.start; cursor < field.end; cursor++)
1105     {
1106       character = (unsigned char) *cursor;
1107       if (edited_flag[character])
1108         {
1109
1110           /* First check if this is a diacriticized character.
1111
1112              This works only for TeX.  I do not know how diacriticized
1113              letters work with `roff'.  Please someone explain it to me!  */
1114
1115           diacritic = todiac (character);
1116           if (diacritic != 0 && output_format == TEX_FORMAT)
1117             {
1118               base = tobase (character);
1119               switch (diacritic)
1120                 {
1121
1122                 case 1:         /* Latin diphthongs */
1123                   switch (base)
1124                     {
1125                     case 'o':
1126                       fputs ("\\oe{}", stdout);
1127                       break;
1128
1129                     case 'O':
1130                       fputs ("\\OE{}", stdout);
1131                       break;
1132
1133                     case 'a':
1134                       fputs ("\\ae{}", stdout);
1135                       break;
1136
1137                     case 'A':
1138                       fputs ("\\AE{}", stdout);
1139                       break;
1140
1141                     default:
1142                       putchar (' ');
1143                     }
1144                   break;
1145
1146                 case 2:         /* Acute accent */
1147                   printf ("\\'%s%c", (base == 'i' ? "\\" : ""), base);
1148                   break;
1149
1150                 case 3:         /* Grave accent */
1151                   printf ("\\`%s%c", (base == 'i' ? "\\" : ""), base);
1152                   break;
1153
1154                 case 4:         /* Circumflex accent */
1155                   printf ("\\^%s%c", (base == 'i' ? "\\" : ""), base);
1156                   break;
1157
1158                 case 5:         /* Diaeresis */
1159                   printf ("\\\"%s%c", (base == 'i' ? "\\" : ""), base);
1160                   break;
1161
1162                 case 6:         /* Tilde accent */
1163                   printf ("\\~%s%c", (base == 'i' ? "\\" : ""), base);
1164                   break;
1165
1166                 case 7:         /* Cedilla */
1167                   printf ("\\c{%c}", base);
1168                   break;
1169
1170                 case 8:         /* Small circle beneath */
1171                   switch (base)
1172                     {
1173                     case 'a':
1174                       fputs ("\\aa{}", stdout);
1175                       break;
1176
1177                     case 'A':
1178                       fputs ("\\AA{}", stdout);
1179                       break;
1180
1181                     default:
1182                       putchar (' ');
1183                     }
1184                   break;
1185
1186                 case 9:         /* Strike through */
1187                   switch (base)
1188                     {
1189                     case 'o':
1190                       fputs ("\\o{}", stdout);
1191                       break;
1192
1193                     case 'O':
1194                       fputs ("\\O{}", stdout);
1195                       break;
1196
1197                     default:
1198                       putchar (' ');
1199                     }
1200                   break;
1201                 }
1202             }
1203           else
1204
1205             /* This is not a diacritic character, so handle cases which are
1206                really specific to `roff' or TeX.  All white space processing
1207                is done as the default case of this switch.  */
1208
1209             switch (character)
1210               {
1211               case '"':
1212                 /* In roff output format, double any quote.  */
1213                 putchar ('"');
1214                 putchar ('"');
1215                 break;
1216
1217               case '$':
1218               case '%':
1219               case '&':
1220               case '#':
1221               case '_':
1222                 /* In TeX output format, precede these with a backslash.  */
1223                 putchar ('\\');
1224                 putchar (character);
1225                 break;
1226
1227               case '{':
1228               case '}':
1229                 /* In TeX output format, precede these with a backslash and
1230                    force mathematical mode.  */
1231                 printf ("$\\%c$", character);
1232                 break;
1233
1234               case '\\':
1235                 /* In TeX output mode, request production of a backslash.  */
1236                 fputs ("\\backslash{}", stdout);
1237                 break;
1238
1239               default:
1240                 /* Any other flagged character produces a single space.  */
1241                 putchar (' ');
1242               }
1243         }
1244       else
1245         putchar (*cursor);
1246     }
1247 }
1248 \f
1249 /* Formatting and actual output - planning routines.  */
1250
1251 /*--------------------------------------------------------------------.
1252 | From information collected from command line options and input file |
1253 | readings, compute and fix some output parameter values.             |
1254 `--------------------------------------------------------------------*/
1255
1256 static void
1257 fix_output_parameters (void)
1258 {
1259   int file_index;               /* index in text input file arrays */
1260   int line_ordinal;             /* line ordinal value for reference */
1261   char ordinal_string[12];      /* edited line ordinal for reference */
1262   int reference_width;          /* width for the whole reference */
1263   int character;                /* character ordinal */
1264   const char *cursor;           /* cursor in some constant strings */
1265
1266   /* In auto reference mode, the maximum width of this field is
1267      precomputed and subtracted from the overall line width.  Add one for
1268      the column which separate the file name from the line number.  */
1269
1270   if (auto_reference)
1271     {
1272       reference_max_width = 0;
1273       for (file_index = 0; file_index < number_input_files; file_index++)
1274         {
1275           line_ordinal = file_line_count[file_index] + 1;
1276           if (file_index > 0)
1277             line_ordinal -= file_line_count[file_index - 1];
1278           sprintf (ordinal_string, "%d", line_ordinal);
1279           reference_width = strlen (ordinal_string);
1280           if (input_file_name[file_index])
1281             reference_width += strlen (input_file_name[file_index]);
1282           if (reference_width > reference_max_width)
1283             reference_max_width = reference_width;
1284         }
1285       reference_max_width++;
1286       reference.start = xmalloc ((size_t) reference_max_width + 1);
1287     }
1288
1289   /* If the reference appears to the left of the output line, reserve some
1290      space for it right away, including one gap size.  */
1291
1292   if ((auto_reference || input_reference) && !right_reference)
1293     line_width -= reference_max_width + gap_size;
1294
1295   /* The output lines, minimally, will contain from left to right a left
1296      context, a gap, and a keyword followed by the right context with no
1297      special intervening gap.  Half of the line width is dedicated to the
1298      left context and the gap, the other half is dedicated to the keyword
1299      and the right context; these values are computed once and for all here.
1300      There also are tail and head wrap around fields, used when the keyword
1301      is near the beginning or the end of the line, or when some long word
1302      cannot fit in, but leave place from wrapped around shorter words.  The
1303      maximum width of these fields are recomputed separately for each line,
1304      on a case by case basis.  It is worth noting that it cannot happen that
1305      both the tail and head fields are used at once.  */
1306
1307   half_line_width = line_width / 2;
1308   before_max_width = half_line_width - gap_size;
1309   keyafter_max_width = half_line_width;
1310
1311   /* If truncation_string is the empty string, make it NULL to speed up
1312      tests.  In this case, truncation_string_length will never get used, so
1313      there is no need to set it.  */
1314
1315   if (truncation_string && *truncation_string)
1316     truncation_string_length = strlen (truncation_string);
1317   else
1318     truncation_string = NULL;
1319
1320   if (gnu_extensions)
1321     {
1322
1323       /* When flagging truncation at the left of the keyword, the
1324          truncation mark goes at the beginning of the before field,
1325          unless there is a head field, in which case the mark goes at the
1326          left of the head field.  When flagging truncation at the right
1327          of the keyword, the mark goes at the end of the keyafter field,
1328          unless there is a tail field, in which case the mark goes at the
1329          end of the tail field.  Only eight combination cases could arise
1330          for truncation marks:
1331
1332          . None.
1333          . One beginning the before field.
1334          . One beginning the head field.
1335          . One ending the keyafter field.
1336          . One ending the tail field.
1337          . One beginning the before field, another ending the keyafter field.
1338          . One ending the tail field, another beginning the before field.
1339          . One ending the keyafter field, another beginning the head field.
1340
1341          So, there is at most two truncation marks, which could appear both
1342          on the left side of the center of the output line, both on the
1343          right side, or one on either side.  */
1344
1345       before_max_width -= 2 * truncation_string_length;
1346       keyafter_max_width -= 2 * truncation_string_length;
1347     }
1348   else
1349     {
1350
1351       /* I never figured out exactly how UNIX' ptx plans the output width
1352          of its various fields.  If GNU extensions are disabled, do not
1353          try computing the field widths correctly; instead, use the
1354          following formula, which does not completely imitate UNIX' ptx,
1355          but almost.  */
1356
1357       keyafter_max_width -= 2 * truncation_string_length + 1;
1358     }
1359
1360   /* Compute which characters need special output processing.  Initialize
1361      by flagging any white space character.  Some systems do not consider
1362      form feed as a space character, but we do.  */
1363
1364   for (character = 0; character < CHAR_SET_SIZE; character++)
1365     edited_flag[character] = ISSPACE (character) != 0;
1366   edited_flag['\f'] = 1;
1367
1368   /* Complete the special character flagging according to selected output
1369      format.  */
1370
1371   switch (output_format)
1372     {
1373     case UNKNOWN_FORMAT:
1374       /* Should never happen.  */
1375
1376     case DUMB_FORMAT:
1377       break;
1378
1379     case ROFF_FORMAT:
1380
1381       /* `Quote' characters should be doubled.  */
1382
1383       edited_flag['"'] = 1;
1384       break;
1385
1386     case TEX_FORMAT:
1387
1388       /* Various characters need special processing.  */
1389
1390       for (cursor = "$%&#_{}\\"; *cursor; cursor++)
1391         edited_flag[(unsigned char) *cursor] = 1;
1392
1393       /* Any character with 8th bit set will print to a single space, unless
1394          it is diacriticized.  */
1395
1396       for (character = 0200; character < CHAR_SET_SIZE; character++)
1397         edited_flag[character] = todiac (character) != 0;
1398       break;
1399     }
1400 }
1401
1402 /*------------------------------------------------------------------.
1403 | Compute the position and length of all the output fields, given a |
1404 | pointer to some OCCURS.                                           |
1405 `------------------------------------------------------------------*/
1406
1407 static void
1408 define_all_fields (OCCURS *occurs)
1409 {
1410   int tail_max_width;           /* allowable width of tail field */
1411   int head_max_width;           /* allowable width of head field */
1412   char *cursor;                 /* running cursor in source text */
1413   char *left_context_start;     /* start of left context */
1414   char *right_context_end;      /* end of right context */
1415   char *left_field_start;       /* conservative start for `head'/`before' */
1416   int file_index;               /* index in text input file arrays */
1417   const char *file_name;        /* file name for reference */
1418   int line_ordinal;             /* line ordinal for reference */
1419
1420   /* Define `keyafter', start of left context and end of right context.
1421      `keyafter' starts at the saved position for keyword and extend to the
1422      right from the end of the keyword, eating separators or full words, but
1423      not beyond maximum allowed width for `keyafter' field or limit for the
1424      right context.  Suffix spaces will be removed afterwards.  */
1425
1426   keyafter.start = occurs->key.start;
1427   keyafter.end = keyafter.start + occurs->key.size;
1428   left_context_start = keyafter.start + occurs->left;
1429   right_context_end = keyafter.start + occurs->right;
1430
1431   cursor = keyafter.end;
1432   while (cursor < right_context_end
1433          && cursor <= keyafter.start + keyafter_max_width)
1434     {
1435       keyafter.end = cursor;
1436       SKIP_SOMETHING (cursor, right_context_end);
1437     }
1438   if (cursor <= keyafter.start + keyafter_max_width)
1439     keyafter.end = cursor;
1440
1441   keyafter_truncation = truncation_string && keyafter.end < right_context_end;
1442
1443   SKIP_WHITE_BACKWARDS (keyafter.end, keyafter.start);
1444
1445   /* When the left context is wide, it might take some time to catch up from
1446      the left context boundary to the beginning of the `head' or `before'
1447      fields.  So, in this case, to speed the catchup, we jump back from the
1448      keyword, using some secure distance, possibly falling in the middle of
1449      a word.  A secure backward jump would be at least half the maximum
1450      width of a line, plus the size of the longest word met in the whole
1451      input.  We conclude this backward jump by a skip forward of at least
1452      one word.  In this manner, we should not inadvertently accept only part
1453      of a word.  From the reached point, when it will be time to fix the
1454      beginning of `head' or `before' fields, we will skip forward words or
1455      delimiters until we get sufficiently near.  */
1456
1457   if (-occurs->left > half_line_width + maximum_word_length)
1458     {
1459       left_field_start
1460         = keyafter.start - (half_line_width + maximum_word_length);
1461       SKIP_SOMETHING (left_field_start, keyafter.start);
1462     }
1463   else
1464     left_field_start = keyafter.start + occurs->left;
1465
1466   /* `before' certainly ends at the keyword, but not including separating
1467      spaces.  It starts after than the saved value for the left context, by
1468      advancing it until it falls inside the maximum allowed width for the
1469      before field.  There will be no prefix spaces either.  `before' only
1470      advances by skipping single separators or whole words. */
1471
1472   before.start = left_field_start;
1473   before.end = keyafter.start;
1474   SKIP_WHITE_BACKWARDS (before.end, before.start);
1475
1476   while (before.start + before_max_width < before.end)
1477     SKIP_SOMETHING (before.start, before.end);
1478
1479   if (truncation_string)
1480     {
1481       cursor = before.start;
1482       SKIP_WHITE_BACKWARDS (cursor, text_buffer.start);
1483       before_truncation = cursor > left_context_start;
1484     }
1485   else
1486     before_truncation = 0;
1487
1488   SKIP_WHITE (before.start, text_buffer.end);
1489
1490   /* The tail could not take more columns than what has been left in the
1491      left context field, and a gap is mandatory.  It starts after the
1492      right context, and does not contain prefixed spaces.  It ends at
1493      the end of line, the end of buffer or when the tail field is full,
1494      whichever comes first.  It cannot contain only part of a word, and
1495      has no suffixed spaces.  */
1496
1497   tail_max_width
1498     = before_max_width - (before.end - before.start) - gap_size;
1499
1500   if (tail_max_width > 0)
1501     {
1502       tail.start = keyafter.end;
1503       SKIP_WHITE (tail.start, text_buffer.end);
1504
1505       tail.end = tail.start;
1506       cursor = tail.end;
1507       while (cursor < right_context_end
1508              && cursor < tail.start + tail_max_width)
1509         {
1510           tail.end = cursor;
1511           SKIP_SOMETHING (cursor, right_context_end);
1512         }
1513
1514       if (cursor < tail.start + tail_max_width)
1515         tail.end = cursor;
1516
1517       if (tail.end > tail.start)
1518         {
1519           keyafter_truncation = 0;
1520           tail_truncation = truncation_string && tail.end < right_context_end;
1521         }
1522       else
1523         tail_truncation = 0;
1524
1525       SKIP_WHITE_BACKWARDS (tail.end, tail.start);
1526     }
1527   else
1528     {
1529
1530       /* No place left for a tail field.  */
1531
1532       tail.start = NULL;
1533       tail.end = NULL;
1534       tail_truncation = 0;
1535     }
1536
1537   /* `head' could not take more columns than what has been left in the right
1538      context field, and a gap is mandatory.  It ends before the left
1539      context, and does not contain suffixed spaces.  Its pointer is advanced
1540      until the head field has shrunk to its allowed width.  It cannot
1541      contain only part of a word, and has no suffixed spaces.  */
1542
1543   head_max_width
1544     = keyafter_max_width - (keyafter.end - keyafter.start) - gap_size;
1545
1546   if (head_max_width > 0)
1547     {
1548       head.end = before.start;
1549       SKIP_WHITE_BACKWARDS (head.end, text_buffer.start);
1550
1551       head.start = left_field_start;
1552       while (head.start + head_max_width < head.end)
1553         SKIP_SOMETHING (head.start, head.end);
1554
1555       if (head.end > head.start)
1556         {
1557           before_truncation = 0;
1558           head_truncation = (truncation_string
1559                              && head.start > left_context_start);
1560         }
1561       else
1562         head_truncation = 0;
1563
1564       SKIP_WHITE (head.start, head.end);
1565     }
1566   else
1567     {
1568
1569       /* No place left for a head field.  */
1570
1571       head.start = NULL;
1572       head.end = NULL;
1573       head_truncation = 0;
1574     }
1575
1576   if (auto_reference)
1577     {
1578
1579       /* Construct the reference text in preallocated space from the file
1580          name and the line number.  Find out in which file the reference
1581          occurred.  Standard input yields an empty file name.  Insure line
1582          numbers are one based, even if they are computed zero based.  */
1583
1584       file_index = 0;
1585       while (file_line_count[file_index] < occurs->reference)
1586         file_index++;
1587
1588       file_name = input_file_name[file_index];
1589       if (!file_name)
1590         file_name = "";
1591
1592       line_ordinal = occurs->reference + 1;
1593       if (file_index > 0)
1594         line_ordinal -= file_line_count[file_index - 1];
1595
1596       sprintf (reference.start, "%s:%d", file_name, line_ordinal);
1597       reference.end = reference.start + strlen (reference.start);
1598     }
1599   else if (input_reference)
1600     {
1601
1602       /* Reference starts at saved position for reference and extends right
1603          until some white space is met.  */
1604
1605       reference.start = keyafter.start + (DELTA) occurs->reference;
1606       reference.end = reference.start;
1607       SKIP_NON_WHITE (reference.end, right_context_end);
1608     }
1609 }
1610 \f
1611 /* Formatting and actual output - control routines.  */
1612
1613 /*----------------------------------------------------------------------.
1614 | Output the current output fields as one line for `troff' or `nroff'.  |
1615 `----------------------------------------------------------------------*/
1616
1617 static void
1618 output_one_roff_line (void)
1619 {
1620   /* Output the `tail' field.  */
1621
1622   printf (".%s \"", macro_name);
1623   print_field (tail);
1624   if (tail_truncation)
1625     fputs (truncation_string, stdout);
1626   putchar ('"');
1627
1628   /* Output the `before' field.  */
1629
1630   fputs (" \"", stdout);
1631   if (before_truncation)
1632     fputs (truncation_string, stdout);
1633   print_field (before);
1634   putchar ('"');
1635
1636   /* Output the `keyafter' field.  */
1637
1638   fputs (" \"", stdout);
1639   print_field (keyafter);
1640   if (keyafter_truncation)
1641     fputs (truncation_string, stdout);
1642   putchar ('"');
1643
1644   /* Output the `head' field.  */
1645
1646   fputs (" \"", stdout);
1647   if (head_truncation)
1648     fputs (truncation_string, stdout);
1649   print_field (head);
1650   putchar ('"');
1651
1652   /* Conditionally output the `reference' field.  */
1653
1654   if (auto_reference || input_reference)
1655     {
1656       fputs (" \"", stdout);
1657       print_field (reference);
1658       putchar ('"');
1659     }
1660
1661   putchar ('\n');
1662 }
1663
1664 /*---------------------------------------------------------.
1665 | Output the current output fields as one line for `TeX'.  |
1666 `---------------------------------------------------------*/
1667
1668 static void
1669 output_one_tex_line (void)
1670 {
1671   BLOCK key;                    /* key field, isolated */
1672   BLOCK after;                  /* after field, isolated */
1673   char *cursor;                 /* running cursor in source text */
1674
1675   printf ("\\%s ", macro_name);
1676   putchar ('{');
1677   print_field (tail);
1678   fputs ("}{", stdout);
1679   print_field (before);
1680   fputs ("}{", stdout);
1681   key.start = keyafter.start;
1682   after.end = keyafter.end;
1683   cursor = keyafter.start;
1684   SKIP_SOMETHING (cursor, keyafter.end);
1685   key.end = cursor;
1686   after.start = cursor;
1687   print_field (key);
1688   fputs ("}{", stdout);
1689   print_field (after);
1690   fputs ("}{", stdout);
1691   print_field (head);
1692   putchar ('}');
1693   if (auto_reference || input_reference)
1694     {
1695       putchar ('{');
1696       print_field (reference);
1697       putchar ('}');
1698     }
1699   putchar ('\n');
1700 }
1701
1702 /*-------------------------------------------------------------------.
1703 | Output the current output fields as one line for a dumb terminal.  |
1704 `-------------------------------------------------------------------*/
1705
1706 static void
1707 output_one_dumb_line (void)
1708 {
1709   if (!right_reference)
1710     {
1711       if (auto_reference)
1712         {
1713
1714           /* Output the `reference' field, in such a way that GNU emacs
1715              next-error will handle it.  The ending colon is taken from the
1716              gap which follows.  */
1717
1718           print_field (reference);
1719           putchar (':');
1720           print_spaces (reference_max_width
1721                         + gap_size
1722                         - (reference.end - reference.start)
1723                         - 1);
1724         }
1725       else
1726         {
1727
1728           /* Output the `reference' field and its following gap.  */
1729
1730           print_field (reference);
1731           print_spaces (reference_max_width
1732                         + gap_size
1733                         - (reference.end - reference.start));
1734         }
1735     }
1736
1737   if (tail.start < tail.end)
1738     {
1739       /* Output the `tail' field.  */
1740
1741       print_field (tail);
1742       if (tail_truncation)
1743         fputs (truncation_string, stdout);
1744
1745       print_spaces (half_line_width - gap_size
1746                     - (before.end - before.start)
1747                     - (before_truncation ? truncation_string_length : 0)
1748                     - (tail.end - tail.start)
1749                     - (tail_truncation ? truncation_string_length : 0));
1750     }
1751   else
1752     print_spaces (half_line_width - gap_size
1753                   - (before.end - before.start)
1754                   - (before_truncation ? truncation_string_length : 0));
1755
1756   /* Output the `before' field.  */
1757
1758   if (before_truncation)
1759     fputs (truncation_string, stdout);
1760   print_field (before);
1761
1762   print_spaces (gap_size);
1763
1764   /* Output the `keyafter' field.  */
1765
1766   print_field (keyafter);
1767   if (keyafter_truncation)
1768     fputs (truncation_string, stdout);
1769
1770   if (head.start < head.end)
1771     {
1772       /* Output the `head' field.  */
1773
1774       print_spaces (half_line_width
1775                     - (keyafter.end - keyafter.start)
1776                     - (keyafter_truncation ? truncation_string_length : 0)
1777                     - (head.end - head.start)
1778                     - (head_truncation ? truncation_string_length : 0));
1779       if (head_truncation)
1780         fputs (truncation_string, stdout);
1781       print_field (head);
1782     }
1783   else
1784
1785     if ((auto_reference || input_reference) && right_reference)
1786       print_spaces (half_line_width
1787                     - (keyafter.end - keyafter.start)
1788                     - (keyafter_truncation ? truncation_string_length : 0));
1789
1790   if ((auto_reference || input_reference) && right_reference)
1791     {
1792       /* Output the `reference' field.  */
1793
1794       print_spaces (gap_size);
1795       print_field (reference);
1796     }
1797
1798   putchar ('\n');
1799 }
1800
1801 /*------------------------------------------------------------------------.
1802 | Scan the whole occurs table and, for each entry, output one line in the |
1803 | appropriate format.                                                     |
1804 `------------------------------------------------------------------------*/
1805
1806 static void
1807 generate_all_output (void)
1808 {
1809   size_t occurs_index;          /* index of keyword entry being processed */
1810   OCCURS *occurs_cursor;        /* current keyword entry being processed */
1811
1812   /* The following assignments are useful to provide default values in case
1813      line contexts or references are not used, in which case these variables
1814      would never be computed.  */
1815
1816   tail.start = NULL;
1817   tail.end = NULL;
1818   tail_truncation = 0;
1819
1820   head.start = NULL;
1821   head.end = NULL;
1822   head_truncation = 0;
1823
1824   /* Loop over all keyword occurrences.  */
1825
1826   occurs_cursor = occurs_table[0];
1827
1828   for (occurs_index = 0; occurs_index < number_of_occurs[0]; occurs_index++)
1829     {
1830       /* Compute the exact size of every field and whenever truncation flags
1831          are present or not.  */
1832
1833       define_all_fields (occurs_cursor);
1834
1835       /* Produce one output line according to selected format.  */
1836
1837       switch (output_format)
1838         {
1839         case UNKNOWN_FORMAT:
1840           /* Should never happen.  */
1841
1842         case DUMB_FORMAT:
1843           output_one_dumb_line ();
1844           break;
1845
1846         case ROFF_FORMAT:
1847           output_one_roff_line ();
1848           break;
1849
1850         case TEX_FORMAT:
1851           output_one_tex_line ();
1852           break;
1853         }
1854
1855       /* Advance the cursor into the occurs table.  */
1856
1857       occurs_cursor++;
1858     }
1859 }
1860 \f
1861 /* Option decoding and main program.  */
1862
1863 /*------------------------------------------------------.
1864 | Print program identification and options, then exit.  |
1865 `------------------------------------------------------*/
1866
1867 void
1868 usage (int status)
1869 {
1870   if (status != EXIT_SUCCESS)
1871     fprintf (stderr, _("Try `%s --help' for more information.\n"),
1872              program_name);
1873   else
1874     {
1875       printf (_("\
1876 Usage: %s [OPTION]... [INPUT]...   (without -G)\n\
1877   or:  %s -G [OPTION]... [INPUT [OUTPUT]]\n"),
1878               program_name, program_name);
1879       fputs (_("\
1880 Output a permuted index, including context, of the words in the input files.\n\
1881 \n\
1882 "), stdout);
1883       fputs (_("\
1884 Mandatory arguments to long options are mandatory for short options too.\n\
1885 "), stdout);
1886       fputs (_("\
1887   -A, --auto-reference           output automatically generated references\n\
1888   -C, --copyright                display Copyright and copying conditions\n\
1889   -G, --traditional              behave more like System V `ptx'\n\
1890   -F, --flag-truncation=STRING   use STRING for flagging line truncations\n\
1891 "), stdout);
1892       fputs (_("\
1893   -M, --macro-name=STRING        macro name to use instead of `xx'\n\
1894   -O, --format=roff              generate output as roff directives\n\
1895   -R, --right-side-refs          put references at right, not counted in -w\n\
1896   -S, --sentence-regexp=REGEXP   for end of lines or end of sentences\n\
1897   -T, --format=tex               generate output as TeX directives\n\
1898 "), stdout);
1899       fputs (_("\
1900   -W, --word-regexp=REGEXP       use REGEXP to match each keyword\n\
1901   -b, --break-file=FILE          word break characters in this FILE\n\
1902   -f, --ignore-case              fold lower case to upper case for sorting\n\
1903   -g, --gap-size=NUMBER          gap size in columns between output fields\n\
1904   -i, --ignore-file=FILE         read ignore word list from FILE\n\
1905   -o, --only-file=FILE           read only word list from this FILE\n\
1906 "), stdout);
1907       fputs (_("\
1908   -r, --references               first field of each line is a reference\n\
1909   -t, --typeset-mode               - not implemented -\n\
1910   -w, --width=NUMBER             output width in columns, reference excluded\n\
1911 "), stdout);
1912       fputs (HELP_OPTION_DESCRIPTION, stdout);
1913       fputs (VERSION_OPTION_DESCRIPTION, stdout);
1914       fputs (_("\
1915 \n\
1916 With no FILE or if FILE is -, read Standard Input.  `-F /' by default.\n\
1917 "), stdout);
1918     }
1919   exit (status);
1920 }
1921
1922 /*----------------------------------------------------------------------.
1923 | Main program.  Decode ARGC arguments passed through the ARGV array of |
1924 | strings, then launch execution.                                       |
1925 `----------------------------------------------------------------------*/
1926
1927 /* Long options equivalences.  */
1928 static const struct option long_options[] =
1929 {
1930   {"auto-reference", no_argument, NULL, 'A'},
1931   {"break-file", required_argument, NULL, 'b'},
1932   {"copyright", no_argument, NULL, 'C'},
1933   {"flag-truncation", required_argument, NULL, 'F'},
1934   {"ignore-case", no_argument, NULL, 'f'},
1935   {"gap-size", required_argument, NULL, 'g'},
1936   {"ignore-file", required_argument, NULL, 'i'},
1937   {"macro-name", required_argument, NULL, 'M'},
1938   {"only-file", required_argument, NULL, 'o'},
1939   {"references", no_argument, NULL, 'r'},
1940   {"right-side-refs", no_argument, NULL, 'R'},
1941   {"format", required_argument, NULL, 10},
1942   {"sentence-regexp", required_argument, NULL, 'S'},
1943   {"traditional", no_argument, NULL, 'G'},
1944   {"typeset-mode", no_argument, NULL, 't'},
1945   {"width", required_argument, NULL, 'w'},
1946   {"word-regexp", required_argument, NULL, 'W'},
1947   {GETOPT_HELP_OPTION_DECL},
1948   {GETOPT_VERSION_OPTION_DECL},
1949   {0, 0, 0, 0},
1950 };
1951
1952 static char const* const format_args[] =
1953 {
1954   "roff", "tex", 0
1955 };
1956
1957 static enum Format const format_vals[] =
1958 {
1959   ROFF_FORMAT, TEX_FORMAT
1960 };
1961
1962 int
1963 main (int argc, char **argv)
1964 {
1965   int optchar;                  /* argument character */
1966   int file_index;               /* index in text input file arrays */
1967
1968   /* Decode program options.  */
1969
1970   initialize_main (&argc, &argv);
1971   program_name = argv[0];
1972   setlocale (LC_ALL, "");
1973   bindtextdomain (PACKAGE, LOCALEDIR);
1974   textdomain (PACKAGE);
1975
1976   atexit (close_stdout);
1977
1978 #if HAVE_SETCHRCLASS
1979   setchrclass (NULL);
1980 #endif
1981
1982   while (optchar = getopt_long (argc, argv, "ACF:GM:ORS:TW:b:i:fg:o:trw:",
1983                                 long_options, NULL),
1984          optchar != EOF)
1985     {
1986       switch (optchar)
1987         {
1988         default:
1989           usage (EXIT_FAILURE);
1990
1991         case 0:
1992           break;
1993
1994         case 'C':
1995           fputs (_("\
1996 This program is free software; you can redistribute it and/or modify\n\
1997 it under the terms of the GNU General Public License as published by\n\
1998 the Free Software Foundation; either version 2, or (at your option)\n\
1999 any later version.\n\
2000 \n\
2001 "), stdout);
2002           fputs (_("\
2003 This program is distributed in the hope that it will be useful,\n\
2004 but WITHOUT ANY WARRANTY; without even the implied warranty of\n\
2005 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n\
2006 GNU General Public License for more details.\n\
2007 \n\
2008 "), stdout);
2009           fputs (_("\
2010 You should have received a copy of the GNU General Public License\n\
2011 along with this program; if not, write to the Free Software Foundation,\n\
2012 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.\n"),
2013                  stdout);
2014
2015           exit (EXIT_SUCCESS);
2016
2017         case 'G':
2018           gnu_extensions = 0;
2019           break;
2020
2021         case 'b':
2022           break_file = optarg;
2023           break;
2024
2025         case 'f':
2026           ignore_case = 1;
2027           break;
2028
2029         case 'g':
2030           gap_size = atoi (optarg);
2031           break;
2032
2033         case 'i':
2034           ignore_file = optarg;
2035           break;
2036
2037         case 'o':
2038           only_file = optarg;
2039           break;
2040
2041         case 'r':
2042           input_reference = 1;
2043           break;
2044
2045         case 't':
2046           /* Yet to understand...  */
2047           break;
2048
2049         case 'w':
2050           line_width = atoi (optarg);
2051           break;
2052
2053         case 'A':
2054           auto_reference = 1;
2055           break;
2056
2057         case 'F':
2058           truncation_string = copy_unescaped_string (optarg);
2059           break;
2060
2061         case 'M':
2062           macro_name = optarg;
2063           break;
2064
2065         case 'O':
2066           output_format = ROFF_FORMAT;
2067           break;
2068
2069         case 'R':
2070           right_reference = 1;
2071           break;
2072
2073         case 'S':
2074           context_regex_string = copy_unescaped_string (optarg);
2075           break;
2076
2077         case 'T':
2078           output_format = TEX_FORMAT;
2079           break;
2080
2081         case 'W':
2082           word_regex_string = copy_unescaped_string (optarg);
2083           break;
2084
2085         case 10:
2086           output_format = XARGMATCH ("--format", optarg,
2087                                      format_args, format_vals);
2088         case_GETOPT_HELP_CHAR;
2089
2090         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
2091         }
2092     }
2093
2094   /* Change the default Ignore file if one is defined.  */
2095
2096 #ifdef DEFAULT_IGNORE_FILE
2097   if (!ignore_file)
2098     ignore_file = DEFAULT_IGNORE_FILE;
2099 #endif
2100
2101   /* Process remaining arguments.  If GNU extensions are enabled, process
2102      all arguments as input parameters.  If disabled, accept at most two
2103      arguments, the second of which is an output parameter.  */
2104
2105   if (optind == argc)
2106     {
2107
2108       /* No more argument simply means: read standard input.  */
2109
2110       input_file_name = xmalloc (sizeof (const char *));
2111       file_line_count = xmalloc (sizeof (int));
2112       number_input_files = 1;
2113       input_file_name[0] = NULL;
2114     }
2115   else if (gnu_extensions)
2116     {
2117       number_input_files = argc - optind;
2118       input_file_name
2119         = xmalloc (number_input_files * sizeof (const char *));
2120       file_line_count
2121         = xmalloc (number_input_files * sizeof (int));
2122
2123       for (file_index = 0; file_index < number_input_files; file_index++)
2124         {
2125           input_file_name[file_index] = argv[optind];
2126           if (!*argv[optind] || strcmp (argv[optind], "-") == 0)
2127             input_file_name[0] = NULL;
2128           else
2129             input_file_name[0] = argv[optind];
2130           optind++;
2131         }
2132     }
2133   else
2134     {
2135
2136       /* There is one necessary input file.  */
2137
2138       number_input_files = 1;
2139       input_file_name = xmalloc (sizeof (const char *));
2140       file_line_count = xmalloc (sizeof (int));
2141       if (!*argv[optind] || strcmp (argv[optind], "-") == 0)
2142         input_file_name[0] = NULL;
2143       else
2144         input_file_name[0] = argv[optind];
2145       optind++;
2146
2147       /* Redirect standard output, only if requested.  */
2148
2149       if (optind < argc)
2150         {
2151           /* FIXME: don't fclose here? */
2152           fclose (stdout);
2153           if (fopen (argv[optind], "w") == NULL)
2154             error (EXIT_FAILURE, errno, "%s", argv[optind]);
2155           optind++;
2156         }
2157
2158       /* Diagnose any other argument as an error.  */
2159
2160       if (optind < argc)
2161         usage (EXIT_FAILURE);
2162     }
2163
2164   /* If the output format has not been explicitly selected, choose dumb
2165      terminal format if GNU extensions are enabled, else `roff' format.  */
2166
2167   if (output_format == UNKNOWN_FORMAT)
2168     output_format = gnu_extensions ? DUMB_FORMAT : ROFF_FORMAT;
2169
2170   /* Initialize the main tables.  */
2171
2172   initialize_regex ();
2173
2174   /* Read `Break character' file, if any.  */
2175
2176   if (break_file)
2177     digest_break_file (break_file);
2178
2179   /* Read `Ignore words' file and `Only words' files, if any.  If any of
2180      these files is empty, reset the name of the file to NULL, to avoid
2181      unnecessary calls to search_table. */
2182
2183   if (ignore_file)
2184     {
2185       digest_word_file (ignore_file, &ignore_table);
2186       if (ignore_table.length == 0)
2187         ignore_file = NULL;
2188     }
2189
2190   if (only_file)
2191     {
2192       digest_word_file (only_file, &only_table);
2193       if (only_table.length == 0)
2194         only_file = NULL;
2195     }
2196
2197   /* Prepare to study all the input files.  */
2198
2199   number_of_occurs[0] = 0;
2200   total_line_count = 0;
2201   maximum_word_length = 0;
2202   reference_max_width = 0;
2203
2204   for (file_index = 0; file_index < number_input_files; file_index++)
2205     {
2206
2207       /* Read the file in core, than study it.  */
2208
2209       swallow_file_in_memory (input_file_name[file_index], &text_buffer);
2210       find_occurs_in_text ();
2211
2212       /* Maintain for each file how many lines has been read so far when its
2213          end is reached.  Incrementing the count first is a simple kludge to
2214          handle a possible incomplete line at end of file.  */
2215
2216       total_line_count++;
2217       file_line_count[file_index] = total_line_count;
2218     }
2219
2220   /* Do the output process phase.  */
2221
2222   sort_found_occurs ();
2223   fix_output_parameters ();
2224   generate_all_output ();
2225
2226   /* All done.  */
2227
2228   exit (EXIT_SUCCESS);
2229 }