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