lib/diffseq.h

   1 /* Analyze differences between two vectors.
   2
   3    Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2010 Free Software
   4    Foundation, Inc.
   5
   6    This program 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 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program 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    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  18
  19
  20 /* The basic idea is to consider two vectors as similar if, when
  21    transforming the first vector into the second vector through a
  22    sequence of edits (inserts and deletes of one element each),
  23    this sequence is short - or equivalently, if the ordered list
  24    of elements that are untouched by these edits is long.  For a
  25    good introduction to the subject, read about the "Levenshtein
  26    distance" in Wikipedia.
  27
  28    The basic algorithm is described in:
  29    "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
  30    Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
  31    see especially section 4.2, which describes the variation used below.
  32
  33    The basic algorithm was independently discovered as described in:
  34    "Algorithms for Approximate String Matching", E. Ukkonen,
  35    Information and Control Vol. 64, 1985, pp. 100-118.
  36
  37    Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
  38    heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
  39    at the price of producing suboptimal output for large inputs with
  40    many differences.  */
  41
  42 /* Before including this file, you need to define:
  43      ELEMENT                 The element type of the vectors being compared.
  44      EQUAL                   A two-argument macro that tests two elements for
  45                              equality.
  46      OFFSET                  A signed integer type sufficient to hold the
  47                              difference between two indices. Usually
  48                              something like ssize_t.
  49      EXTRA_CONTEXT_FIELDS    Declarations of fields for 'struct context'.
  50      NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
  51      NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
  52      EARLY_ABORT(ctxt)       (Optional) A boolean expression that triggers an
  53                              early abort of the computation.
  54      USE_HEURISTIC           (Optional) Define if you want to support the
  55                              heuristic for large vectors.
  56    Before including this file, you also need to include:
  57      #include <limits.h>
  58      #include <stdbool.h>
  59      #include "minmax.h"
  60  */
  61
  62 /* Maximum value of type OFFSET.  */
  63 #define OFFSET_MAX \
  64   ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
  65
  66 /* Default to no early abort.  */
  67 #ifndef EARLY_ABORT
  68 # define EARLY_ABORT(ctxt) false
  69 #endif
  70
  71 /* Use this to suppress gcc's `...may be used before initialized' warnings.
  72    Beware: The Code argument must not contain commas.  */
  73 #ifndef IF_LINT
  74 # ifdef lint
  75 #  define IF_LINT(Code) Code
  76 # else
  77 #  define IF_LINT(Code) /* empty */
  78 # endif
  79 #endif
  80
  81 /* As above, but when Code must contain one comma. */
  82 #ifndef IF_LINT2
  83 # ifdef lint
  84 #  define IF_LINT2(Code1, Code2) Code1, Code2
  85 # else
  86 #  define IF_LINT2(Code1, Code2) /* empty */
  87 # endif
  88 #endif
  89
  90 /*
  91  * Context of comparison operation.
  92  */
  93 struct context
  94 {
  95   /* Vectors being compared.  */
  96   ELEMENT const *xvec;
  97   ELEMENT const *yvec;
  98
  99   /* Extra fields.  */
 100   EXTRA_CONTEXT_FIELDS
 101
 102   /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
 103      furthest along the given diagonal in the forward search of the edit
 104      matrix.  */
 105   OFFSET *fdiag;
 106
 107   /* Vector, indexed by diagonal, containing the X coordinate of the point
 108      furthest along the given diagonal in the backward search of the edit
 109      matrix.  */
 110   OFFSET *bdiag;
 111
 112   #ifdef USE_HEURISTIC
 113   /* This corresponds to the diff -H flag.  With this heuristic, for
 114      vectors with a constant small density of changes, the algorithm is
 115      linear in the vectors size.  */
 116   bool heuristic;
 117   #endif
 118
 119   /* Edit scripts longer than this are too expensive to compute.  */
 120   OFFSET too_expensive;
 121
 122   /* Snakes bigger than this are considered `big'.  */
 123   #define SNAKE_LIMIT 20
 124 };
 125
 126 struct partition
 127 {
 128   /* Midpoints of this partition.  */
 129   OFFSET xmid;
 130   OFFSET ymid;
 131
 132   /* True if low half will be analyzed minimally.  */
 133   bool lo_minimal;
 134
 135   /* Likewise for high half.  */
 136   bool hi_minimal;
 137 };
 138
 139
 140 /* Find the midpoint of the shortest edit script for a specified portion
 141    of the two vectors.
 142
 143    Scan from the beginnings of the vectors, and simultaneously from the ends,
 144    doing a breadth-first search through the space of edit-sequence.
 145    When the two searches meet, we have found the midpoint of the shortest
 146    edit sequence.
 147
 148    If FIND_MINIMAL is true, find the minimal edit script regardless of
 149    expense.  Otherwise, if the search is too expensive, use heuristics to
 150    stop the search and report a suboptimal answer.
 151
 152    Set PART->(xmid,ymid) to the midpoint (XMID,YMID).  The diagonal number
 153    XMID - YMID equals the number of inserted elements minus the number
 154    of deleted elements (counting only elements before the midpoint).
 155
 156    Set PART->lo_minimal to true iff the minimal edit script for the
 157    left half of the partition is known; similarly for PART->hi_minimal.
 158
 159    This function assumes that the first elements of the specified portions
 160    of the two vectors do not match, and likewise that the last elements do not
 161    match.  The caller must trim matching elements from the beginning and end
 162    of the portions it is going to specify.
 163
 164    If we return the "wrong" partitions, the worst this can do is cause
 165    suboptimal diff output.  It cannot cause incorrect diff output.  */
 166
 167 static void
 168 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
 169       struct partition *part, struct context *ctxt)
 170 {
 171   OFFSET *const fd = ctxt->fdiag;       /* Give the compiler a chance. */
 172   OFFSET *const bd = ctxt->bdiag;       /* Additional help for the compiler. */
 173   ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
 174   ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
 175   const OFFSET dmin = xoff - ylim;      /* Minimum valid diagonal. */
 176   const OFFSET dmax = xlim - yoff;      /* Maximum valid diagonal. */
 177   const OFFSET fmid = xoff - yoff;      /* Center diagonal of top-down search. */
 178   const OFFSET bmid = xlim - ylim;      /* Center diagonal of bottom-up search. */
 179   OFFSET fmin = fmid;
 180   OFFSET fmax = fmid;           /* Limits of top-down search. */
 181   OFFSET bmin = bmid;
 182   OFFSET bmax = bmid;           /* Limits of bottom-up search. */
 183   OFFSET c;                     /* Cost. */
 184   bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
 185                                    diagonal with respect to the northwest. */
 186
 187   fd[fmid] = xoff;
 188   bd[bmid] = xlim;
 189
 190   for (c = 1;; ++c)
 191     {
 192       OFFSET d;                 /* Active diagonal. */
 193       bool big_snake = false;
 194
 195       /* Extend the top-down search by an edit step in each diagonal. */
 196       if (fmin > dmin)
 197         fd[--fmin - 1] = -1;
 198       else
 199         ++fmin;
 200       if (fmax < dmax)
 201         fd[++fmax + 1] = -1;
 202       else
 203         --fmax;
 204       for (d = fmax; d >= fmin; d -= 2)
 205         {
 206           OFFSET x;
 207           OFFSET y;
 208           OFFSET tlo = fd[d - 1];
 209           OFFSET thi = fd[d + 1];
 210           OFFSET x0 = tlo < thi ? thi : tlo + 1;
 211
 212           for (x = x0, y = x0 - d;
 213                x < xlim && y < ylim && EQUAL (xv[x], yv[y]);
 214                x++, y++)
 215             continue;
 216           if (x - x0 > SNAKE_LIMIT)
 217             big_snake = true;
 218           fd[d] = x;
 219           if (odd && bmin <= d && d <= bmax && bd[d] <= x)
 220             {
 221               part->xmid = x;
 222               part->ymid = y;
 223               part->lo_minimal = part->hi_minimal = true;
 224               return;
 225             }
 226         }
 227
 228       /* Similarly extend the bottom-up search.  */
 229       if (bmin > dmin)
 230         bd[--bmin - 1] = OFFSET_MAX;
 231       else
 232         ++bmin;
 233       if (bmax < dmax)
 234         bd[++bmax + 1] = OFFSET_MAX;
 235       else
 236         --bmax;
 237       for (d = bmax; d >= bmin; d -= 2)
 238         {
 239           OFFSET x;
 240           OFFSET y;
 241           OFFSET tlo = bd[d - 1];
 242           OFFSET thi = bd[d + 1];
 243           OFFSET x0 = tlo < thi ? tlo : thi - 1;
 244
 245           for (x = x0, y = x0 - d;
 246                xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]);
 247                x--, y--)
 248             continue;
 249           if (x0 - x > SNAKE_LIMIT)
 250             big_snake = true;
 251           bd[d] = x;
 252           if (!odd && fmin <= d && d <= fmax && x <= fd[d])
 253             {
 254               part->xmid = x;
 255               part->ymid = y;
 256               part->lo_minimal = part->hi_minimal = true;
 257               return;
 258             }
 259         }
 260
 261       if (find_minimal)
 262         continue;
 263
 264 #ifdef USE_HEURISTIC
 265       /* Heuristic: check occasionally for a diagonal that has made lots
 266          of progress compared with the edit distance.  If we have any
 267          such, find the one that has made the most progress and return it
 268          as if it had succeeded.
 269
 270          With this heuristic, for vectors with a constant small density
 271          of changes, the algorithm is linear in the vector size.  */
 272
 273       if (200 < c && big_snake && ctxt->heuristic)
 274         {
 275           {
 276             OFFSET best = 0;
 277
 278             for (d = fmax; d >= fmin; d -= 2)
 279               {
 280                 OFFSET dd = d - fmid;
 281                 OFFSET x = fd[d];
 282                 OFFSET y = x - d;
 283                 OFFSET v = (x - xoff) * 2 - dd;
 284
 285                 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
 286                   {
 287                     if (v > best
 288                         && xoff + SNAKE_LIMIT <= x && x < xlim
 289                         && yoff + SNAKE_LIMIT <= y && y < ylim)
 290                       {
 291                         /* We have a good enough best diagonal; now insist
 292                            that it end with a significant snake.  */
 293                         int k;
 294
 295                         for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++)
 296                           if (k == SNAKE_LIMIT)
 297                             {
 298                               best = v;
 299                               part->xmid = x;
 300                               part->ymid = y;
 301                               break;
 302                             }
 303                       }
 304                   }
 305               }
 306             if (best > 0)
 307               {
 308                 part->lo_minimal = true;
 309                 part->hi_minimal = false;
 310                 return;
 311               }
 312           }
 313
 314           {
 315             OFFSET best = 0;
 316
 317             for (d = bmax; d >= bmin; d -= 2)
 318               {
 319                 OFFSET dd = d - bmid;
 320                 OFFSET x = bd[d];
 321                 OFFSET y = x - d;
 322                 OFFSET v = (xlim - x) * 2 + dd;
 323
 324                 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
 325                   {
 326                     if (v > best
 327                         && xoff < x && x <= xlim - SNAKE_LIMIT
 328                         && yoff < y && y <= ylim - SNAKE_LIMIT)
 329                       {
 330                         /* We have a good enough best diagonal; now insist
 331                            that it end with a significant snake.  */
 332                         int k;
 333
 334                         for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++)
 335                           if (k == SNAKE_LIMIT - 1)
 336                             {
 337                               best = v;
 338                               part->xmid = x;
 339                               part->ymid = y;
 340                               break;
 341                             }
 342                       }
 343                   }
 344               }
 345             if (best > 0)
 346               {
 347                 part->lo_minimal = false;
 348                 part->hi_minimal = true;
 349                 return;
 350               }
 351           }
 352         }
 353 #endif /* USE_HEURISTIC */
 354
 355       /* Heuristic: if we've gone well beyond the call of duty, give up
 356          and report halfway between our best results so far.  */
 357       if (c >= ctxt->too_expensive)
 358         {
 359           OFFSET fxybest;
 360           OFFSET fxbest IF_LINT (= 0);
 361           OFFSET bxybest;
 362           OFFSET bxbest IF_LINT (= 0);
 363
 364           /* Find forward diagonal that maximizes X + Y.  */
 365           fxybest = -1;
 366           for (d = fmax; d >= fmin; d -= 2)
 367             {
 368               OFFSET x = MIN (fd[d], xlim);
 369               OFFSET y = x - d;
 370               if (ylim < y)
 371                 {
 372                   x = ylim + d;
 373                   y = ylim;
 374                 }
 375               if (fxybest < x + y)
 376                 {
 377                   fxybest = x + y;
 378                   fxbest = x;
 379                 }
 380             }
 381
 382           /* Find backward diagonal that minimizes X + Y.  */
 383           bxybest = OFFSET_MAX;
 384           for (d = bmax; d >= bmin; d -= 2)
 385             {
 386               OFFSET x = MAX (xoff, bd[d]);
 387               OFFSET y = x - d;
 388               if (y < yoff)
 389                 {
 390                   x = yoff + d;
 391                   y = yoff;
 392                 }
 393               if (x + y < bxybest)
 394                 {
 395                   bxybest = x + y;
 396                   bxbest = x;
 397                 }
 398             }
 399
 400           /* Use the better of the two diagonals.  */
 401           if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
 402             {
 403               part->xmid = fxbest;
 404               part->ymid = fxybest - fxbest;
 405               part->lo_minimal = true;
 406               part->hi_minimal = false;
 407             }
 408           else
 409             {
 410               part->xmid = bxbest;
 411               part->ymid = bxybest - bxbest;
 412               part->lo_minimal = false;
 413               part->hi_minimal = true;
 414             }
 415           return;
 416         }
 417     }
 418 }
 419
 420
 421 /* Compare in detail contiguous subsequences of the two vectors
 422    which are known, as a whole, to match each other.
 423
 424    The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1.
 425
 426    Note that XLIM, YLIM are exclusive bounds.  All indices into the vectors
 427    are origin-0.
 428
 429    If FIND_MINIMAL, find a minimal difference no matter how
 430    expensive it is.
 431
 432    The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
 433
 434    Return false if terminated normally, or true if terminated through early
 435    abort.  */
 436
 437 static bool
 438 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
 439             bool find_minimal, struct context *ctxt)
 440 {
 441   ELEMENT const *xv = ctxt->xvec; /* Help the compiler.  */
 442   ELEMENT const *yv = ctxt->yvec;
 443
 444   /* Slide down the bottom initial diagonal.  */
 445   while (xoff < xlim && yoff < ylim && EQUAL (xv[xoff], yv[yoff]))
 446     {
 447       xoff++;
 448       yoff++;
 449     }
 450
 451   /* Slide up the top initial diagonal. */
 452   while (xoff < xlim && yoff < ylim && EQUAL (xv[xlim - 1], yv[ylim - 1]))
 453     {
 454       xlim--;
 455       ylim--;
 456     }
 457
 458   /* Handle simple cases. */
 459   if (xoff == xlim)
 460     while (yoff < ylim)
 461       {
 462         NOTE_INSERT (ctxt, yoff);
 463         if (EARLY_ABORT (ctxt))
 464           return true;
 465         yoff++;
 466       }
 467   else if (yoff == ylim)
 468     while (xoff < xlim)
 469       {
 470         NOTE_DELETE (ctxt, xoff);
 471         if (EARLY_ABORT (ctxt))
 472           return true;
 473         xoff++;
 474       }
 475   else
 476     {
 477       struct partition part IF_LINT2 (= { .xmid = 0, .ymid = 0 });
 478
 479       /* Find a point of correspondence in the middle of the vectors.  */
 480       diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
 481
 482       /* Use the partitions to split this problem into subproblems.  */
 483       if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
 484         return true;
 485       if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
 486         return true;
 487     }
 488
 489   return false;
 490 }
 491
 492 #undef ELEMENT
 493 #undef EQUAL
 494 #undef OFFSET
 495 #undef EXTRA_CONTEXT_FIELDS
 496 #undef NOTE_DELETE
 497 #undef NOTE_INSERT
 498 #undef EARLY_ABORT
 499 #undef USE_HEURISTIC
 500 #undef OFFSET_MAX