contrib/diffutils/src/context.c

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