lib/diffseq.h

   1 /* Analyze differences between two vectors.
   2
   3    Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2008 Free
   4    Software 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 #ifndef IF_LINT
  73 # ifdef lint
  74 #  define IF_LINT(Code) Code
  75 # else
  76 #  define IF_LINT(Code) /* empty */
  77 # endif
  78 #endif
  79
  80 /*
  81  * Context of comparison operation.
  82  */
  83 struct context
  84 {
  85   /* Vectors being compared.  */
  86   ELEMENT const *xvec;
  87   ELEMENT const *yvec;
  88
  89   /* Extra fields.  */
  90   EXTRA_CONTEXT_FIELDS
  91
  92   /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
  93      furthest along the given diagonal in the forward search of the edit
  94      matrix.  */
  95   OFFSET *fdiag;
  96
  97   /* Vector, indexed by diagonal, containing the X coordinate of the point
  98      furthest along the given diagonal in the backward search of the edit
  99      matrix.  */
 100   OFFSET *bdiag;
 101
 102   #ifdef USE_HEURISTIC
 103   /* This corresponds to the diff -H flag.  With this heuristic, for
 104      vectors with a constant small density of changes, the algorithm is
 105      linear in the vectors size.  */
 106   bool heuristic;
 107   #endif
 108
 109   /* Edit scripts longer than this are too expensive to compute.  */
 110   OFFSET too_expensive;
 111
 112   /* Snakes bigger than this are considered `big'.  */
 113   #define SNAKE_LIMIT 20
 114 };
 115
 116 struct partition
 117 {
 118   /* Midpoints of this partition.  */
 119   OFFSET xmid;
 120   OFFSET ymid;
 121
 122   /* True if low half will be analyzed minimally.  */
 123   bool lo_minimal;
 124
 125   /* Likewise for high half.  */
 126   bool hi_minimal;
 127 };
 128
 129
 130 /* Find the midpoint of the shortest edit script for a specified portion
 131    of the two vectors.
 132
 133    Scan from the beginnings of the vectors, and simultaneously from the ends,
 134    doing a breadth-first search through the space of edit-sequence.
 135    When the two searches meet, we have found the midpoint of the shortest
 136    edit sequence.
 137
 138    If FIND_MINIMAL is true, find the minimal edit script regardless of
 139    expense.  Otherwise, if the search is too expensive, use heuristics to
 140    stop the search and report a suboptimal answer.
 141
 142    Set PART->(xmid,ymid) to the midpoint (XMID,YMID).  The diagonal number
 143    XMID - YMID equals the number of inserted elements minus the number
 144    of deleted elements (counting only elements before the midpoint).
 145
 146    Set PART->lo_minimal to true iff the minimal edit script for the
 147    left half of the partition is known; similarly for PART->hi_minimal.
 148
 149    This function assumes that the first elements of the specified portions
 150    of the two vectors do not match, and likewise that the last elements do not
 151    match.  The caller must trim matching elements from the beginning and end
 152    of the portions it is going to specify.
 153
 154    If we return the "wrong" partitions, the worst this can do is cause
 155    suboptimal diff output.  It cannot cause incorrect diff output.  */
 156
 157 static void
 158 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
 159       struct partition *part, struct context *ctxt)
 160 {
 161   OFFSET *const fd = ctxt->fdiag;       /* Give the compiler a chance. */
 162   OFFSET *const bd = ctxt->bdiag;       /* Additional help for the compiler. */
 163   ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
 164   ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
 165   const OFFSET dmin = xoff - ylim;      /* Minimum valid diagonal. */
 166   const OFFSET dmax = xlim - yoff;      /* Maximum valid diagonal. */
 167   const OFFSET fmid = xoff - yoff;      /* Center diagonal of top-down search. */
 168   const OFFSET bmid = xlim - ylim;      /* Center diagonal of bottom-up search. */
 169   OFFSET fmin = fmid;
 170   OFFSET fmax = fmid;           /* Limits of top-down search. */
 171   OFFSET bmin = bmid;
 172   OFFSET bmax = bmid;           /* Limits of bottom-up search. */
 173   OFFSET c;                     /* Cost. */
 174   bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
 175                                    diagonal with respect to the northwest. */
 176
 177   fd[fmid] = xoff;
 178   bd[bmid] = xlim;
 179
 180   for (c = 1;; ++c)
 181     {
 182       OFFSET d;                 /* Active diagonal. */
 183       bool big_snake = false;
 184
 185       /* Extend the top-down search by an edit step in each diagonal. */
 186       if (fmin > dmin)
 187         fd[--fmin - 1] = -1;
 188       else
 189         ++fmin;
 190       if (fmax < dmax)
 191         fd[++fmax + 1] = -1;
 192       else
 193         --fmax;
 194       for (d = fmax; d >= fmin; d -= 2)
 195         {
 196           OFFSET x;
 197           OFFSET y;
 198           OFFSET tlo = fd[d - 1];
 199           OFFSET thi = fd[d + 1];
 200           OFFSET x0 = tlo < thi ? thi : tlo + 1;
 201
 202           for (x = x0, y = x0 - d;
 203                x < xlim && y < ylim && EQUAL (xv[x], yv[y]);
 204                x++, y++)
 205             continue;
 206           if (x - x0 > SNAKE_LIMIT)
 207             big_snake = true;
 208           fd[d] = x;
 209           if (odd && bmin <= d && d <= bmax && bd[d] <= x)
 210             {
 211               part->xmid = x;
 212               part->ymid = y;
 213               part->lo_minimal = part->hi_minimal = true;
 214               return;
 215             }
 216         }
 217
 218       /* Similarly extend the bottom-up search.  */
 219       if (bmin > dmin)
 220         bd[--bmin - 1] = OFFSET_MAX;
 221       else
 222         ++bmin;
 223       if (bmax < dmax)
 224         bd[++bmax + 1] = OFFSET_MAX;
 225       else
 226         --bmax;
 227       for (d = bmax; d >= bmin; d -= 2)
 228         {
 229           OFFSET x;
 230           OFFSET y;
 231           OFFSET tlo = bd[d - 1];
 232           OFFSET thi = bd[d + 1];
 233           OFFSET x0 = tlo < thi ? tlo : thi - 1;
 234
 235           for (x = x0, y = x0 - d;
 236                xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]);
 237                x--, y--)
 238             continue;
 239           if (x0 - x > SNAKE_LIMIT)
 240             big_snake = true;
 241           bd[d] = x;
 242           if (!odd && fmin <= d && d <= fmax && x <= fd[d])
 243             {
 244               part->xmid = x;
 245               part->ymid = y;
 246               part->lo_minimal = part->hi_minimal = true;
 247               return;
 248             }
 249         }
 250
 251       if (find_minimal)
 252         continue;
 253
 254 #ifdef USE_HEURISTIC
 255       /* Heuristic: check occasionally for a diagonal that has made lots
 256          of progress compared with the edit distance.  If we have any
 257          such, find the one that has made the most progress and return it
 258          as if it had succeeded.
 259
 260          With this heuristic, for vectors with a constant small density
 261          of changes, the algorithm is linear in the vector size.  */
 262
 263       if (200 < c && big_snake && ctxt->heuristic)
 264         {
 265           OFFSET best = 0;
 266
 267           for (d = fmax; d >= fmin; d -= 2)
 268             {
 269               OFFSET dd = d - fmid;
 270               OFFSET x = fd[d];
 271               OFFSET y = x - d;
 272               OFFSET v = (x - xoff) * 2 - dd;
 273
 274               if (v > 12 * (c + (dd < 0 ? -dd : dd)))
 275                 {
 276                   if (v > best
 277                       && xoff + SNAKE_LIMIT <= x && x < xlim
 278                       && yoff + SNAKE_LIMIT <= y && y < ylim)
 279                     {
 280                       /* We have a good enough best diagonal; now insist
 281                          that it end with a significant snake.  */
 282                       int k;
 283
 284                       for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++)
 285                         if (k == SNAKE_LIMIT)
 286                           {
 287                             best = v;
 288                             part->xmid = x;
 289                             part->ymid = y;
 290                             break;
 291                           }
 292                     }
 293                 }
 294             }
 295           if (best > 0)
 296             {
 297               part->lo_minimal = true;
 298               part->hi_minimal = false;
 299               return;
 300             }
 301
 302           for (d = bmax; d >= bmin; d -= 2)
 303             {
 304               OFFSET dd = d - bmid;
 305               OFFSET x = bd[d];
 306               OFFSET y = x - d;
 307               OFFSET v = (xlim - x) * 2 + dd;
 308
 309               if (v > 12 * (c + (dd < 0 ? -dd : dd)))
 310                 {
 311                   if (v > best
 312                       && xoff < x && x <= xlim - SNAKE_LIMIT
 313                       && yoff < y && y <= ylim - SNAKE_LIMIT)
 314                     {
 315                       /* We have a good enough best diagonal; now insist
 316                          that it end with a significant snake.  */
 317                       int k;
 318
 319                       for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++)
 320                         if (k == SNAKE_LIMIT - 1)
 321                           {
 322                             best = v;
 323                             part->xmid = x;
 324                             part->ymid = y;
 325                             break;
 326                           }
 327                     }
 328                 }
 329             }
 330           if (best > 0)
 331             {
 332               part->lo_minimal = false;
 333               part->hi_minimal = true;
 334               return;
 335             }
 336         }
 337 #endif /* USE_HEURISTIC */
 338
 339       /* Heuristic: if we've gone well beyond the call of duty, give up
 340          and report halfway between our best results so far.  */
 341       if (c >= ctxt->too_expensive)
 342         {
 343           OFFSET fxybest;
 344           OFFSET fxbest IF_LINT (= 0);
 345           OFFSET bxybest;
 346           OFFSET bxbest IF_LINT (= 0);
 347
 348           /* Find forward diagonal that maximizes X + Y.  */
 349           fxybest = -1;
 350           for (d = fmax; d >= fmin; d -= 2)
 351             {
 352               OFFSET x = MIN (fd[d], xlim);
 353               OFFSET y = x - d;
 354               if (ylim < y)
 355                 {
 356                   x = ylim + d;
 357                   y = ylim;
 358                 }
 359               if (fxybest < x + y)
 360                 {
 361                   fxybest = x + y;
 362                   fxbest = x;
 363                 }
 364             }
 365
 366           /* Find backward diagonal that minimizes X + Y.  */
 367           bxybest = OFFSET_MAX;
 368           for (d = bmax; d >= bmin; d -= 2)
 369             {
 370               OFFSET x = MAX (xoff, bd[d]);
 371               OFFSET y = x - d;
 372               if (y < yoff)
 373                 {
 374                   x = yoff + d;
 375                   y = yoff;
 376                 }
 377               if (x + y < bxybest)
 378                 {
 379                   bxybest = x + y;
 380                   bxbest = x;
 381                 }
 382             }
 383
 384           /* Use the better of the two diagonals.  */
 385           if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
 386             {
 387               part->xmid = fxbest;
 388               part->ymid = fxybest - fxbest;
 389               part->lo_minimal = true;
 390               part->hi_minimal = false;
 391             }
 392           else
 393             {
 394               part->xmid = bxbest;
 395               part->ymid = bxybest - bxbest;
 396               part->lo_minimal = false;
 397               part->hi_minimal = true;
 398             }
 399           return;
 400         }
 401     }
 402 }
 403
 404
 405 /* Compare in detail contiguous subsequences of the two vectors
 406    which are known, as a whole, to match each other.
 407
 408    The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1.
 409
 410    Note that XLIM, YLIM are exclusive bounds.  All indices into the vectors
 411    are origin-0.
 412
 413    If FIND_MINIMAL, find a minimal difference no matter how
 414    expensive it is.
 415
 416    The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
 417
 418    Return false if terminated normally, or true if terminated through early
 419    abort.  */
 420
 421 static bool
 422 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
 423             bool find_minimal, struct context *ctxt)
 424 {
 425   ELEMENT const *xv = ctxt->xvec; /* Help the compiler.  */
 426   ELEMENT const *yv = ctxt->yvec;
 427
 428   /* Slide down the bottom initial diagonal.  */
 429   while (xoff < xlim && yoff < ylim && EQUAL (xv[xoff], yv[yoff]))
 430     {
 431       xoff++;
 432       yoff++;
 433     }
 434
 435   /* Slide up the top initial diagonal. */
 436   while (xoff < xlim && yoff < ylim && EQUAL (xv[xlim - 1], yv[ylim - 1]))
 437     {
 438       xlim--;
 439       ylim--;
 440     }
 441
 442   /* Handle simple cases. */
 443   if (xoff == xlim)
 444     while (yoff < ylim)
 445       {
 446         NOTE_INSERT (ctxt, yoff);
 447         if (EARLY_ABORT (ctxt))
 448           return true;
 449         yoff++;
 450       }
 451   else if (yoff == ylim)
 452     while (xoff < xlim)
 453       {
 454         NOTE_DELETE (ctxt, xoff);
 455         if (EARLY_ABORT (ctxt))
 456           return true;
 457         xoff++;
 458       }
 459   else
 460     {
 461       struct partition part;
 462
 463       /* Find a point of correspondence in the middle of the vectors.  */
 464       diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
 465
 466       /* Use the partitions to split this problem into subproblems.  */
 467       if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
 468         return true;
 469       if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
 470         return true;
 471     }
 472
 473   return false;
 474 }
 475
 476 #undef ELEMENT
 477 #undef EQUAL
 478 #undef OFFSET
 479 #undef EXTRA_CONTEXT_FIELDS
 480 #undef NOTE_DELETE
 481 #undef NOTE_INSERT
 482 #undef EARLY_ABORT
 483 #undef USE_HEURISTIC
 484 #undef OFFSET_MAX