Update lintian overrides
[alioth/cvs.git] / diff / io.c
1 /* File I/O for GNU DIFF.
2    Copyright (C) 1988, 1989, 1992, 1993, 1994 Free Software Foundation, Inc.
3
4 This file is part of GNU DIFF.
5
6 GNU DIFF is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GNU DIFF is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 */
17
18 #include "diff.h"
19
20 /* Rotate a value n bits to the left. */
21 #define UINT_BIT (sizeof (unsigned) * CHAR_BIT)
22 #define ROL(v, n) ((v) << (n) | (v) >> (UINT_BIT - (n)))
23
24 /* Given a hash value and a new character, return a new hash value. */
25 #define HASH(h, c) ((c) + ROL (h, 7))
26
27 /* Guess remaining number of lines from number N of lines so far,
28    size S so far, and total size T.  */
29 #define GUESS_LINES(n,s,t) (((t) - (s)) / ((n) < 10 ? 32 : (s) / ((n)-1)) + 5)
30
31 /* Type used for fast prefix comparison in find_identical_ends.  */
32 #ifndef word
33 #define word int
34 #endif
35 \f
36 /* Lines are put into equivalence classes (of lines that match in line_cmp).
37    Each equivalence class is represented by one of these structures,
38    but only while the classes are being computed.
39    Afterward, each class is represented by a number.  */
40 struct equivclass
41 {
42   int next;     /* Next item in this bucket. */
43   unsigned hash;        /* Hash of lines in this class.  */
44   char const *line;     /* A line that fits this class. */
45   size_t length;        /* That line's length, not counting its newline.  */
46 };
47
48 /* Hash-table: array of buckets, each being a chain of equivalence classes.
49    buckets[-1] is reserved for incomplete lines.  */
50 static int *buckets;
51
52 /* Number of buckets in the hash table array, not counting buckets[-1]. */
53 static int nbuckets;
54
55 /* Array in which the equivalence classes are allocated.
56    The bucket-chains go through the elements in this array.
57    The number of an equivalence class is its index in this array.  */
58 static struct equivclass *equivs;
59
60 /* Index of first free element in the array `equivs'.  */
61 static int equivs_index;
62
63 /* Number of elements allocated in the array `equivs'.  */
64 static int equivs_alloc;
65
66 static void find_and_hash_each_line PARAMS((struct file_data *));
67 static void find_identical_ends PARAMS((struct file_data[]));
68 static void prepare_text_end PARAMS((struct file_data *));
69 \f
70 /* Check for binary files and compare them for exact identity.  */
71
72 /* Return 1 if BUF contains a non text character.
73    SIZE is the number of characters in BUF.  */
74
75 #define binary_file_p(buf, size) (memchr (buf, '\0', size) != 0)
76
77 /* Get ready to read the current file.
78    Return nonzero if SKIP_TEST is zero,
79    and if it appears to be a binary file.  */
80
81 int
82 sip (current, skip_test)
83      struct file_data *current;
84      int skip_test;
85 {
86   /* If we have a nonexistent file at this stage, treat it as empty.  */
87   if (current->desc < 0)
88     {
89       /* Leave room for a sentinel.  */
90       current->bufsize = sizeof (word);
91       current->buffer = xmalloc (current->bufsize);
92     }
93   else
94     {
95       current->bufsize = STAT_BLOCKSIZE (current->stat);
96       current->buffer = xmalloc (current->bufsize);
97
98       if (! skip_test)
99         {
100           /* Check first part of file to see if it's a binary file.  */
101 #if HAVE_SETMODE
102           int oldmode = setmode (current->desc, O_BINARY);
103 #endif
104           ssize_t n = read (current->desc, current->buffer, current->bufsize);
105           if (n == -1)
106             pfatal_with_name (current->name);
107           current->buffered_chars = n;
108 #if HAVE_SETMODE
109           if (oldmode != O_BINARY)
110             {
111               if (lseek (current->desc, - (off_t) n, SEEK_CUR) == -1)
112                 pfatal_with_name (current->name);
113               setmode (current->desc, oldmode);
114               current->buffered_chars = 0;
115             }
116 #endif
117           return binary_file_p (current->buffer, n);
118         }
119     }
120
121   current->buffered_chars = 0;
122   return 0;
123 }
124
125 /* Slurp the rest of the current file completely into memory.  */
126
127 void
128 slurp (current)
129      struct file_data *current;
130 {
131   ssize_t cc;
132
133   if (current->desc < 0)
134     /* The file is nonexistent.  */
135     ;
136   else if (S_ISREG (current->stat.st_mode))
137     {
138       /* It's a regular file; slurp in the rest all at once.  */
139
140       /* Get the size out of the stat block.
141          Allocate enough room for appended newline and sentinel.  */
142       cc = current->stat.st_size + 1 + sizeof (word);
143       if (current->bufsize < cc)
144         {
145           current->bufsize = cc;
146           current->buffer = xrealloc (current->buffer, cc);
147         }
148
149       if (current->buffered_chars < current->stat.st_size)
150         {
151           cc = read (current->desc,
152                      current->buffer + current->buffered_chars,
153                      current->stat.st_size - current->buffered_chars);
154           if (cc == -1)
155             pfatal_with_name (current->name);
156           current->buffered_chars += cc;
157         }
158     }
159   /* It's not a regular file; read it, growing the buffer as needed.  */
160   else if (always_text_flag || current->buffered_chars != 0)
161     {
162       for (;;)
163         {
164           if (current->buffered_chars == current->bufsize)
165             {
166               current->bufsize = current->bufsize * 2;
167               current->buffer = xrealloc (current->buffer, current->bufsize);
168             }
169           cc = read (current->desc,
170                      current->buffer + current->buffered_chars,
171                      current->bufsize - current->buffered_chars);
172           if (cc == 0)
173             break;
174           if (cc == -1)
175             pfatal_with_name (current->name);
176           current->buffered_chars += cc;
177         }
178       /* Allocate just enough room for appended newline and sentinel.  */
179       current->bufsize = current->buffered_chars + 1 + sizeof (word);
180       current->buffer = xrealloc (current->buffer, current->bufsize);
181     }
182 }
183 \f
184 /* Split the file into lines, simultaneously computing the equivalence class for
185    each line. */
186
187 static void
188 find_and_hash_each_line (current)
189      struct file_data *current;
190 {
191   unsigned h;
192   unsigned char const *p = (unsigned char const *) current->prefix_end;
193   unsigned char c;
194   int i, *bucket;
195   size_t length;
196
197   /* Cache often-used quantities in local variables to help the compiler.  */
198   char const **linbuf = current->linbuf;
199   int alloc_lines = current->alloc_lines;
200   int line = 0;
201   int linbuf_base = current->linbuf_base;
202   int *cureqs = (int *) xmalloc (alloc_lines * sizeof (int));
203   struct equivclass *eqs = equivs;
204   int eqs_index = equivs_index;
205   int eqs_alloc = equivs_alloc;
206   char const *suffix_begin = current->suffix_begin;
207   char const *bufend = current->buffer + current->buffered_chars;
208   int use_line_cmp = ignore_some_line_changes;
209
210   while ((char const *) p < suffix_begin)
211     {
212       char const *ip = (char const *) p;
213
214       /* Compute the equivalence class for this line.  */
215
216       h = 0;
217
218       /* Hash this line until we find a newline. */
219       if (ignore_case_flag)
220         {
221           if (ignore_all_space_flag)
222             while ((c = *p++) != '\n')
223               {
224                 if (! ISSPACE (c))
225                   h = HASH (h, ISUPPER (c) ? tolower (c) : c);
226               }
227           else if (ignore_space_change_flag)
228             while ((c = *p++) != '\n')
229               {
230                 if (ISSPACE (c))
231                   {
232                     for (;;)
233                       {
234                         c = *p++;
235                         if (!ISSPACE (c))
236                           break;
237                         if (c == '\n')
238                           goto hashing_done;
239                       }
240                     h = HASH (h, ' ');
241                   }
242                 /* C is now the first non-space.  */
243                 h = HASH (h, ISUPPER (c) ? tolower (c) : c);
244               }
245           else
246             while ((c = *p++) != '\n')
247               h = HASH (h, ISUPPER (c) ? tolower (c) : c);
248         }
249       else
250         {
251           if (ignore_all_space_flag)
252             while ((c = *p++) != '\n')
253               {
254                 if (! ISSPACE (c))
255                   h = HASH (h, c);
256               }
257           else if (ignore_space_change_flag)
258             while ((c = *p++) != '\n')
259               {
260                 if (ISSPACE (c))
261                   {
262                     for (;;)
263                       {
264                         c = *p++;
265                         if (!ISSPACE (c))
266                           break;
267                         if (c == '\n')
268                           goto hashing_done;
269                       }
270                     h = HASH (h, ' ');
271                   }
272                 /* C is now the first non-space.  */
273                 h = HASH (h, c);
274               }
275           else
276             while ((c = *p++) != '\n')
277               h = HASH (h, c);
278         }
279    hashing_done:;
280
281       bucket = &buckets[h % nbuckets];
282       length = (char const *) p - ip - 1;
283
284       if ((char const *) p == bufend
285           && current->missing_newline
286           && ROBUST_OUTPUT_STYLE (output_style))
287         {
288           /* This line is incomplete.  If this is significant,
289              put the line into bucket[-1].  */
290           if (! (ignore_space_change_flag | ignore_all_space_flag))
291             bucket = &buckets[-1];
292
293           /* Omit the inserted newline when computing linbuf later.  */
294           p--;
295           bufend = suffix_begin = (char const *) p;
296         }
297
298       for (i = *bucket;  ;  i = eqs[i].next)
299         if (!i)
300           {
301             /* Create a new equivalence class in this bucket. */
302             i = eqs_index++;
303             if (i == eqs_alloc)
304               eqs = (struct equivclass *)
305                       xrealloc (eqs, (eqs_alloc*=2) * sizeof(*eqs));
306             eqs[i].next = *bucket;
307             eqs[i].hash = h;
308             eqs[i].line = ip;
309             eqs[i].length = length;
310             *bucket = i;
311             break;
312           }
313         else if (eqs[i].hash == h)
314           {
315             char const *eqline = eqs[i].line;
316
317             /* Reuse existing equivalence class if the lines are identical.
318                This detects the common case of exact identity
319                faster than complete comparison would.  */
320             if (eqs[i].length == length && memcmp (eqline, ip, length) == 0)
321               break;
322
323             /* Reuse existing class if line_cmp reports the lines equal.  */
324             if (use_line_cmp && line_cmp (eqline, ip) == 0)
325               break;
326           }
327
328       /* Maybe increase the size of the line table. */
329       if (line == alloc_lines)
330         {
331           /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */
332           alloc_lines = 2 * alloc_lines - linbuf_base;
333           cureqs = (int *) xrealloc (cureqs, alloc_lines * sizeof (*cureqs));
334           linbuf = (char const **) xrealloc (linbuf + linbuf_base,
335                                              (alloc_lines - linbuf_base)
336                                              * sizeof (*linbuf))
337                    - linbuf_base;
338         }
339       linbuf[line] = ip;
340       cureqs[line] = i;
341       ++line;
342     }
343
344   current->buffered_lines = line;
345
346   for (i = 0;  ;  i++)
347     {
348       /* Record the line start for lines in the suffix that we care about.
349          Record one more line start than lines,
350          so that we can compute the length of any buffered line.  */
351       if (line == alloc_lines)
352         {
353           /* Double (alloc_lines - linbuf_base) by adding to alloc_lines.  */
354           alloc_lines = 2 * alloc_lines - linbuf_base;
355           linbuf = (char const **) xrealloc (linbuf + linbuf_base,
356                                              (alloc_lines - linbuf_base)
357                                              * sizeof (*linbuf))
358                    - linbuf_base;
359         }
360       linbuf[line] = (char const *) p;
361
362       if ((char const *) p == bufend)
363         break;
364
365       if (context <= i && no_diff_means_no_output)
366         break;
367
368       line++;
369
370       while (*p++ != '\n')
371         ;
372     }
373
374   /* Done with cache in local variables.  */
375   current->linbuf = linbuf;
376   current->valid_lines = line;
377   current->alloc_lines = alloc_lines;
378   current->equivs = cureqs;
379   equivs = eqs;
380   equivs_alloc = eqs_alloc;
381   equivs_index = eqs_index;
382 }
383 \f
384 /* Prepare the end of the text.  Make sure it's initialized.
385    Make sure text ends in a newline,
386    but remember that we had to add one.  */
387
388 static void
389 prepare_text_end (current)
390      struct file_data *current;
391 {
392   size_t buffered_chars = current->buffered_chars;
393   char *p = current->buffer;
394
395   if (buffered_chars == 0 || p[buffered_chars - 1] == '\n')
396     current->missing_newline = 0;
397   else
398     {
399       p[buffered_chars++] = '\n';
400       current->buffered_chars = buffered_chars;
401       current->missing_newline = 1;
402     }
403
404   /* Don't use uninitialized storage when planting or using sentinels.  */
405   if (p)
406     bzero (p + buffered_chars, sizeof (word));
407 }
408 \f
409 /* Given a vector of two file_data objects, find the identical
410    prefixes and suffixes of each object. */
411
412 static void
413 find_identical_ends (filevec)
414      struct file_data filevec[];
415 {
416   word *w0, *w1;
417   char *p0, *p1, *buffer0, *buffer1;
418   char const *end0, *beg0;
419   char const **linbuf0, **linbuf1;
420   int i, lines;
421   size_t n0, n1, tem;
422   int alloc_lines0, alloc_lines1;
423   int buffered_prefix, prefix_count, prefix_mask;
424
425   slurp (&filevec[0]);
426   if (filevec[0].desc != filevec[1].desc)
427     slurp (&filevec[1]);
428   else
429     {
430       filevec[1].buffer = filevec[0].buffer;
431       filevec[1].bufsize = filevec[0].bufsize;
432       filevec[1].buffered_chars = filevec[0].buffered_chars;
433     }
434   for (i = 0; i < 2; i++)
435     prepare_text_end (&filevec[i]);
436
437   /* Find identical prefix.  */
438
439   p0 = buffer0 = filevec[0].buffer;
440   p1 = buffer1 = filevec[1].buffer;
441
442   n0 = filevec[0].buffered_chars;
443   n1 = filevec[1].buffered_chars;
444
445   if (p0 == p1)
446     /* The buffers are the same; sentinels won't work.  */
447     p0 = p1 += n1;
448   else
449     {
450       /* Insert end sentinels, in this case characters that are guaranteed
451          to make the equality test false, and thus terminate the loop.  */
452
453       if (n0 < n1)
454         p0[n0] = ~p1[n0];
455       else
456         p1[n1] = ~p0[n1];
457
458       /* Loop until first mismatch, or to the sentinel characters.  */
459
460       /* Compare a word at a time for speed.  */
461       w0 = (word *) p0;
462       w1 = (word *) p1;
463       while (*w0++ == *w1++)
464         ;
465       --w0, --w1;
466
467       /* Do the last few bytes of comparison a byte at a time.  */
468       p0 = (char *) w0;
469       p1 = (char *) w1;
470       while (*p0++ == *p1++)
471         ;
472       --p0, --p1;
473
474       /* Don't mistakenly count missing newline as part of prefix. */
475       if (ROBUST_OUTPUT_STYLE (output_style)
476           && (buffer0 + n0 - filevec[0].missing_newline < p0)
477              !=
478              (buffer1 + n1 - filevec[1].missing_newline < p1))
479         --p0, --p1;
480     }
481
482   /* Now P0 and P1 point at the first nonmatching characters.  */
483
484   /* Skip back to last line-beginning in the prefix,
485      and then discard up to HORIZON_LINES lines from the prefix.  */
486   i = horizon_lines;
487   while (p0 != buffer0 && (p0[-1] != '\n' || i--))
488     --p0, --p1;
489
490   /* Record the prefix.  */
491   filevec[0].prefix_end = p0;
492   filevec[1].prefix_end = p1;
493
494   /* Find identical suffix.  */
495
496   /* P0 and P1 point beyond the last chars not yet compared.  */
497   p0 = buffer0 + n0;
498   p1 = buffer1 + n1;
499
500   if (! ROBUST_OUTPUT_STYLE (output_style)
501       || filevec[0].missing_newline == filevec[1].missing_newline)
502     {
503       end0 = p0;        /* Addr of last char in file 0.  */
504
505       /* Get value of P0 at which we should stop scanning backward:
506          this is when either P0 or P1 points just past the last char
507          of the identical prefix.  */
508       beg0 = filevec[0].prefix_end + (n0 < n1 ? 0 : n0 - n1);
509
510       /* Scan back until chars don't match or we reach that point.  */
511       for (; p0 != beg0; p0--, p1--)
512         if (*p0 != *p1)
513           {
514             /* Point at the first char of the matching suffix.  */
515             beg0 = p0;
516             break;
517           }
518
519       /* Are we at a line-beginning in both files?  If not, add the rest of
520          this line to the main body.  Discard up to HORIZON_LINES lines from
521          the identical suffix.  Also, discard one extra line,
522          because shift_boundaries may need it.  */
523       i = horizon_lines + !((buffer0 == p0 || p0[-1] == '\n')
524                             &&
525                             (buffer1 == p1 || p1[-1] == '\n'));
526       while (i-- && p0 != end0)
527         while (*p0++ != '\n')
528           ;
529
530       p1 += p0 - beg0;
531     }
532
533   /* Record the suffix.  */
534   filevec[0].suffix_begin = p0;
535   filevec[1].suffix_begin = p1;
536
537   /* Calculate number of lines of prefix to save.
538
539      prefix_count == 0 means save the whole prefix;
540      we need this with for options like -D that output the whole file.
541      We also need it for options like -F that output some preceding line;
542      at least we will need to find the last few lines,
543      but since we don't know how many, it's easiest to find them all.
544
545      Otherwise, prefix_count != 0.  Save just prefix_count lines at start
546      of the line buffer; they'll be moved to the proper location later.
547      Handle 1 more line than the context says (because we count 1 too many),
548      rounded up to the next power of 2 to speed index computation.  */
549
550   if (no_diff_means_no_output && ! function_regexp_list)
551     {
552       for (prefix_count = 1;  prefix_count < context + 1;  prefix_count *= 2)
553         ;
554       prefix_mask = prefix_count - 1;
555       alloc_lines0
556         = prefix_count
557           + GUESS_LINES (0, 0, p0 - filevec[0].prefix_end)
558           + context;
559     }
560   else
561     {
562       prefix_count = 0;
563       prefix_mask = ~0;
564       alloc_lines0 = GUESS_LINES (0, 0, n0);
565     }
566
567   lines = 0;
568   linbuf0 = (char const **) xmalloc (alloc_lines0 * sizeof (*linbuf0));
569
570   /* If the prefix is needed, find the prefix lines.  */
571   if (! (no_diff_means_no_output
572          && filevec[0].prefix_end == p0
573          && filevec[1].prefix_end == p1))
574     {
575       p0 = buffer0;
576       end0 = filevec[0].prefix_end;
577       while (p0 != end0)
578         {
579           int l = lines++ & prefix_mask;
580           if (l == alloc_lines0)
581             linbuf0 = (char const **) xrealloc (linbuf0, (alloc_lines0 *= 2)
582                                                          * sizeof(*linbuf0));
583           linbuf0[l] = p0;
584           while (*p0++ != '\n')
585             ;
586         }
587     }
588   buffered_prefix = prefix_count && context < lines ? context : lines;
589
590   /* Allocate line buffer 1.  */
591   tem = prefix_count ? filevec[1].suffix_begin - buffer1 : n1;
592
593   alloc_lines1
594     = (buffered_prefix
595        + GUESS_LINES (lines, filevec[1].prefix_end - buffer1, tem)
596        + context);
597   linbuf1 = (char const **) xmalloc (alloc_lines1 * sizeof (*linbuf1));
598
599   if (buffered_prefix != lines)
600     {
601       /* Rotate prefix lines to proper location.  */
602       for (i = 0;  i < buffered_prefix;  i++)
603         linbuf1[i] = linbuf0[(lines - context + i) & prefix_mask];
604       for (i = 0;  i < buffered_prefix;  i++)
605         linbuf0[i] = linbuf1[i];
606     }
607
608   /* Initialize line buffer 1 from line buffer 0.  */
609   for (i = 0; i < buffered_prefix; i++)
610     linbuf1[i] = linbuf0[i] - buffer0 + buffer1;
611
612   /* Record the line buffer, adjusted so that
613      linbuf*[0] points at the first differing line.  */
614   filevec[0].linbuf = linbuf0 + buffered_prefix;
615   filevec[1].linbuf = linbuf1 + buffered_prefix;
616   filevec[0].linbuf_base = filevec[1].linbuf_base = - buffered_prefix;
617   filevec[0].alloc_lines = alloc_lines0 - buffered_prefix;
618   filevec[1].alloc_lines = alloc_lines1 - buffered_prefix;
619   filevec[0].prefix_lines = filevec[1].prefix_lines = lines;
620 }
621 \f
622 /* Largest primes less than some power of two, for nbuckets.  Values range
623    from useful to preposterous.  If one of these numbers isn't prime
624    after all, don't blame it on me, blame it on primes (6) . . . */
625 static int const primes[] =
626 {
627   509,
628   1021,
629   2039,
630   4093,
631   8191,
632   16381,
633   32749,
634 #if 32767 < INT_MAX
635   65521,
636   131071,
637   262139,
638   524287,
639   1048573,
640   2097143,
641   4194301,
642   8388593,
643   16777213,
644   33554393,
645   67108859,                     /* Preposterously large . . . */
646   134217689,
647   268435399,
648   536870909,
649   1073741789,
650   2147483647,
651 #endif
652   0
653 };
654
655 /* Given a vector of two file_data objects, read the file associated
656    with each one, and build the table of equivalence classes.
657    Return 1 if either file appears to be a binary file.
658    If PRETEND_BINARY is nonzero, pretend they are binary regardless.  */
659
660 int
661 read_files (filevec, pretend_binary)
662      struct file_data filevec[];
663      int pretend_binary;
664 {
665   int i;
666   int skip_test = always_text_flag | pretend_binary;
667   int appears_binary = pretend_binary | sip (&filevec[0], skip_test);
668
669   if (filevec[0].desc != filevec[1].desc)
670     appears_binary |= sip (&filevec[1], skip_test | appears_binary);
671   else
672     {
673       filevec[1].buffer = filevec[0].buffer;
674       filevec[1].bufsize = filevec[0].bufsize;
675       filevec[1].buffered_chars = filevec[0].buffered_chars;
676     }
677   if (appears_binary)
678     {
679 #if HAVE_SETMODE
680       setmode (filevec[0].desc, O_BINARY);
681       setmode (filevec[1].desc, O_BINARY);
682 #endif
683       return 1;
684     }
685
686   find_identical_ends (filevec);
687
688   equivs_alloc = filevec[0].alloc_lines + filevec[1].alloc_lines + 1;
689   equivs = (struct equivclass *) xmalloc (equivs_alloc * sizeof (struct equivclass));
690   /* Equivalence class 0 is permanently safe for lines that were not
691      hashed.  Real equivalence classes start at 1. */
692   equivs_index = 1;
693
694   for (i = 0;  primes[i] < equivs_alloc / 3;  i++)
695     if (! primes[i])
696       abort ();
697   nbuckets = primes[i];
698
699   buckets = (int *) xmalloc ((nbuckets + 1) * sizeof (*buckets));
700   bzero (buckets++, (nbuckets + 1) * sizeof (*buckets));
701
702   for (i = 0; i < 2; i++)
703     find_and_hash_each_line (&filevec[i]);
704
705   filevec[0].equiv_max = filevec[1].equiv_max = equivs_index;
706
707   free (equivs);
708   free (buckets - 1);
709
710   return 0;
711 }