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