xref: /freebsd/contrib/diff/src/context.c (revision 30d239bc4c510432e65a84fa1c14ed67a3ab1c92)
1 /* Context-format output routines for GNU DIFF.
2 
3    Copyright (C) 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1998, 2001,
4    2002, 2004 Free Software Foundation, Inc.
5 
6    This file is part of GNU DIFF.
7 
8    GNU DIFF is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2, or (at your option)
11    any later version.
12 
13    GNU DIFF is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17 
18    You should have received a copy of the GNU General Public License
19    along with this program; see the file COPYING.
20    If not, write to the Free Software Foundation,
21    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
22 
23 #include "diff.h"
24 #include <inttostr.h>
25 
26 #ifdef ST_MTIM_NSEC
27 # define TIMESPEC_NS(timespec) ((timespec).ST_MTIM_NSEC)
28 #else
29 # define TIMESPEC_NS(timespec) 0
30 #endif
31 
32 size_t nstrftime (char *, size_t, char const *, struct tm const *, int, int);
33 
34 static char const *find_function (char const * const *, lin);
35 static struct change *find_hunk (struct change *);
36 static void mark_ignorable (struct change *);
37 static void pr_context_hunk (struct change *);
38 static void pr_unidiff_hunk (struct change *);
39 
40 /* Last place find_function started searching from.  */
41 static lin find_function_last_search;
42 
43 /* The value find_function returned when it started searching there.  */
44 static lin find_function_last_match;
45 
46 /* Print a label for a context diff, with a file name and date or a label.  */
47 
48 static void
49 print_context_label (char const *mark,
50 		     struct file_data *inf,
51 		     char const *label)
52 {
53   if (label)
54     fprintf (outfile, "%s %s\n", mark, label);
55   else
56     {
57       char buf[MAX (INT_STRLEN_BOUND (int) + 32,
58 		    INT_STRLEN_BOUND (time_t) + 11)];
59       struct tm const *tm = localtime (&inf->stat.st_mtime);
60       int nsec = TIMESPEC_NS (inf->stat.st_mtim);
61       if (! (tm && nstrftime (buf, sizeof buf, time_format, tm, 0, nsec)))
62 	{
63 	  long int sec = inf->stat.st_mtime;
64 	  verify (info_preserved, sizeof inf->stat.st_mtime <= sizeof sec);
65 	  sprintf (buf, "%ld.%.9d", sec, nsec);
66 	}
67       fprintf (outfile, "%s %s\t%s\n", mark, inf->name, buf);
68     }
69 }
70 
71 /* Print a header for a context diff, with the file names and dates.  */
72 
73 void
74 print_context_header (struct file_data inf[], bool unidiff)
75 {
76   if (unidiff)
77     {
78       print_context_label ("---", &inf[0], file_label[0]);
79       print_context_label ("+++", &inf[1], file_label[1]);
80     }
81   else
82     {
83       print_context_label ("***", &inf[0], file_label[0]);
84       print_context_label ("---", &inf[1], file_label[1]);
85     }
86 }
87 
88 /* Print an edit script in context format.  */
89 
90 void
91 print_context_script (struct change *script, bool unidiff)
92 {
93   if (ignore_blank_lines || ignore_regexp.fastmap)
94     mark_ignorable (script);
95   else
96     {
97       struct change *e;
98       for (e = script; e; e = e->link)
99 	e->ignore = false;
100     }
101 
102   find_function_last_search = - files[0].prefix_lines;
103   find_function_last_match = LIN_MAX;
104 
105   if (unidiff)
106     print_script (script, find_hunk, pr_unidiff_hunk);
107   else
108     print_script (script, find_hunk, pr_context_hunk);
109 }
110 
111 /* Print a pair of line numbers with a comma, translated for file FILE.
112    If the second number is not greater, use the first in place of it.
113 
114    Args A and B are internal line numbers.
115    We print the translated (real) line numbers.  */
116 
117 static void
118 print_context_number_range (struct file_data const *file, lin a, lin b)
119 {
120   long int trans_a, trans_b;
121   translate_range (file, a, b, &trans_a, &trans_b);
122 
123   /* We can have B <= A in the case of a range of no lines.
124      In this case, we should print the line number before the range,
125      which is B.
126 
127      POSIX 1003.1-2001 requires two line numbers separated by a comma
128      even if the line numbers are the same.  However, this does not
129      match existing practice and is surely an error in the
130      specification.  */
131 
132   if (trans_b <= trans_a)
133     fprintf (outfile, "%ld", trans_b);
134   else
135     fprintf (outfile, "%ld,%ld", trans_a, trans_b);
136 }
137 
138 /* Print FUNCTION in a context header.  */
139 static void
140 print_context_function (FILE *out, char const *function)
141 {
142   int i;
143   putc (' ', out);
144   for (i = 0; i < 40 && function[i] != '\n'; i++)
145     continue;
146   fwrite (function, sizeof (char), i, out);
147 }
148 
149 /* Print a portion of an edit script in context format.
150    HUNK is the beginning of the portion to be printed.
151    The end is marked by a `link' that has been nulled out.
152 
153    Prints out lines from both files, and precedes each
154    line with the appropriate flag-character.  */
155 
156 static void
157 pr_context_hunk (struct change *hunk)
158 {
159   lin first0, last0, first1, last1, i;
160   char const *prefix;
161   char const *function;
162   FILE *out;
163 
164   /* Determine range of line numbers involved in each file.  */
165 
166   enum changes changes = analyze_hunk (hunk, &first0, &last0, &first1, &last1);
167   if (! changes)
168     return;
169 
170   /* Include a context's width before and after.  */
171 
172   i = - files[0].prefix_lines;
173   first0 = MAX (first0 - context, i);
174   first1 = MAX (first1 - context, i);
175   if (last0 < files[0].valid_lines - context)
176     last0 += context;
177   else
178     last0 = files[0].valid_lines - 1;
179   if (last1 < files[1].valid_lines - context)
180     last1 += context;
181   else
182     last1 = files[1].valid_lines - 1;
183 
184   /* If desired, find the preceding function definition line in file 0.  */
185   function = 0;
186   if (function_regexp.fastmap)
187     function = find_function (files[0].linbuf, first0);
188 
189   begin_output ();
190   out = outfile;
191 
192   fprintf (out, "***************");
193 
194   if (function)
195     print_context_function (out, function);
196 
197   fprintf (out, "\n*** ");
198   print_context_number_range (&files[0], first0, last0);
199   fprintf (out, " ****\n");
200 
201   if (changes & OLD)
202     {
203       struct change *next = hunk;
204 
205       for (i = first0; i <= last0; i++)
206 	{
207 	  /* Skip past changes that apply (in file 0)
208 	     only to lines before line I.  */
209 
210 	  while (next && next->line0 + next->deleted <= i)
211 	    next = next->link;
212 
213 	  /* Compute the marking for line I.  */
214 
215 	  prefix = " ";
216 	  if (next && next->line0 <= i)
217 	    /* The change NEXT covers this line.
218 	       If lines were inserted here in file 1, this is "changed".
219 	       Otherwise it is "deleted".  */
220 	    prefix = (next->inserted > 0 ? "!" : "-");
221 
222 	  print_1_line (prefix, &files[0].linbuf[i]);
223 	}
224     }
225 
226   fprintf (out, "--- ");
227   print_context_number_range (&files[1], first1, last1);
228   fprintf (out, " ----\n");
229 
230   if (changes & NEW)
231     {
232       struct change *next = hunk;
233 
234       for (i = first1; i <= last1; i++)
235 	{
236 	  /* Skip past changes that apply (in file 1)
237 	     only to lines before line I.  */
238 
239 	  while (next && next->line1 + next->inserted <= i)
240 	    next = next->link;
241 
242 	  /* Compute the marking for line I.  */
243 
244 	  prefix = " ";
245 	  if (next && next->line1 <= i)
246 	    /* The change NEXT covers this line.
247 	       If lines were deleted here in file 0, this is "changed".
248 	       Otherwise it is "inserted".  */
249 	    prefix = (next->deleted > 0 ? "!" : "+");
250 
251 	  print_1_line (prefix, &files[1].linbuf[i]);
252 	}
253     }
254 }
255 
256 /* Print a pair of line numbers with a comma, translated for file FILE.
257    If the second number is smaller, use the first in place of it.
258    If the numbers are equal, print just one number.
259 
260    Args A and B are internal line numbers.
261    We print the translated (real) line numbers.  */
262 
263 static void
264 print_unidiff_number_range (struct file_data const *file, lin a, lin b)
265 {
266   long int trans_a, trans_b;
267   translate_range (file, a, b, &trans_a, &trans_b);
268 
269   /* We can have B < A in the case of a range of no lines.
270      In this case, we print the line number before the range,
271      which is B.  It would be more logical to print A, but
272      'patch' expects B in order to detect diffs against empty files.  */
273   if (trans_b <= trans_a)
274     fprintf (outfile, trans_b < trans_a ? "%ld,0" : "%ld", trans_b);
275   else
276     fprintf (outfile, "%ld,%ld", trans_a, trans_b - trans_a + 1);
277 }
278 
279 /* Print a portion of an edit script in unidiff format.
280    HUNK is the beginning of the portion to be printed.
281    The end is marked by a `link' that has been nulled out.
282 
283    Prints out lines from both files, and precedes each
284    line with the appropriate flag-character.  */
285 
286 static void
287 pr_unidiff_hunk (struct change *hunk)
288 {
289   lin first0, last0, first1, last1;
290   lin i, j, k;
291   struct change *next;
292   char const *function;
293   FILE *out;
294 
295   /* Determine range of line numbers involved in each file.  */
296 
297   if (! analyze_hunk (hunk, &first0, &last0, &first1, &last1))
298     return;
299 
300   /* Include a context's width before and after.  */
301 
302   i = - files[0].prefix_lines;
303   first0 = MAX (first0 - context, i);
304   first1 = MAX (first1 - context, i);
305   if (last0 < files[0].valid_lines - context)
306     last0 += context;
307   else
308     last0 = files[0].valid_lines - 1;
309   if (last1 < files[1].valid_lines - context)
310     last1 += context;
311   else
312     last1 = files[1].valid_lines - 1;
313 
314   /* If desired, find the preceding function definition line in file 0.  */
315   function = 0;
316   if (function_regexp.fastmap)
317     function = find_function (files[0].linbuf, first0);
318 
319   begin_output ();
320   out = outfile;
321 
322   fprintf (out, "@@ -");
323   print_unidiff_number_range (&files[0], first0, last0);
324   fprintf (out, " +");
325   print_unidiff_number_range (&files[1], first1, last1);
326   fprintf (out, " @@");
327 
328   if (function)
329     print_context_function (out, function);
330 
331   putc ('\n', out);
332 
333   next = hunk;
334   i = first0;
335   j = first1;
336 
337   while (i <= last0 || j <= last1)
338     {
339 
340       /* If the line isn't a difference, output the context from file 0. */
341 
342       if (!next || i < next->line0)
343 	{
344 	  putc (initial_tab ? '\t' : ' ', out);
345 	  print_1_line (0, &files[0].linbuf[i++]);
346 	  j++;
347 	}
348       else
349 	{
350 	  /* For each difference, first output the deleted part. */
351 
352 	  k = next->deleted;
353 	  while (k--)
354 	    {
355 	      putc ('-', out);
356 	      if (initial_tab)
357 		putc ('\t', out);
358 	      print_1_line (0, &files[0].linbuf[i++]);
359 	    }
360 
361 	  /* Then output the inserted part. */
362 
363 	  k = next->inserted;
364 	  while (k--)
365 	    {
366 	      putc ('+', out);
367 	      if (initial_tab)
368 		putc ('\t', out);
369 	      print_1_line (0, &files[1].linbuf[j++]);
370 	    }
371 
372 	  /* We're done with this hunk, so on to the next! */
373 
374 	  next = next->link;
375 	}
376     }
377 }
378 
379 /* Scan a (forward-ordered) edit script for the first place that more than
380    2*CONTEXT unchanged lines appear, and return a pointer
381    to the `struct change' for the last change before those lines.  */
382 
383 static struct change *
384 find_hunk (struct change *start)
385 {
386   struct change *prev;
387   lin top0, top1;
388   lin thresh;
389 
390   /* Threshold distance is 2 * CONTEXT + 1 between two non-ignorable
391      changes, but only CONTEXT if one is ignorable.  Watch out for
392      integer overflow, though.  */
393   lin non_ignorable_threshold =
394     (LIN_MAX - 1) / 2 < context ? LIN_MAX : 2 * context + 1;
395   lin ignorable_threshold = context;
396 
397   do
398     {
399       /* Compute number of first line in each file beyond this changed.  */
400       top0 = start->line0 + start->deleted;
401       top1 = start->line1 + start->inserted;
402       prev = start;
403       start = start->link;
404       thresh = (prev->ignore || (start && start->ignore)
405 		? ignorable_threshold
406 		: non_ignorable_threshold);
407       /* It is not supposed to matter which file we check in the end-test.
408 	 If it would matter, crash.  */
409       if (start && start->line0 - top0 != start->line1 - top1)
410 	abort ();
411     } while (start
412 	     /* Keep going if less than THRESH lines
413 		elapse before the affected line.  */
414 	     && start->line0 - top0 < thresh);
415 
416   return prev;
417 }
418 
419 /* Set the `ignore' flag properly in each change in SCRIPT.
420    It should be 1 if all the lines inserted or deleted in that change
421    are ignorable lines.  */
422 
423 static void
424 mark_ignorable (struct change *script)
425 {
426   while (script)
427     {
428       struct change *next = script->link;
429       lin first0, last0, first1, last1;
430 
431       /* Turn this change into a hunk: detach it from the others.  */
432       script->link = 0;
433 
434       /* Determine whether this change is ignorable.  */
435       script->ignore = ! analyze_hunk (script,
436 				       &first0, &last0, &first1, &last1);
437 
438       /* Reconnect the chain as before.  */
439       script->link = next;
440 
441       /* Advance to the following change.  */
442       script = next;
443     }
444 }
445 
446 /* Find the last function-header line in LINBUF prior to line number LINENUM.
447    This is a line containing a match for the regexp in `function_regexp'.
448    Return the address of the text, or 0 if no function-header is found.  */
449 
450 static char const *
451 find_function (char const * const *linbuf, lin linenum)
452 {
453   lin i = linenum;
454   lin last = find_function_last_search;
455   find_function_last_search = i;
456 
457   while (last <= --i)
458     {
459       /* See if this line is what we want.  */
460       char const *line = linbuf[i];
461       size_t linelen = linbuf[i + 1] - line - 1;
462 
463       /* FIXME: re_search's size args should be size_t, not int.  */
464       int len = MIN (linelen, INT_MAX);
465 
466       if (0 <= re_search (&function_regexp, line, len, 0, len, 0))
467 	{
468 	  find_function_last_match = i;
469 	  return line;
470 	}
471     }
472   /* If we search back to where we started searching the previous time,
473      find the line we found last time.  */
474   if (find_function_last_match != LIN_MAX)
475     return linbuf[find_function_last_match];
476 
477   return 0;
478 }
479