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