lib/diffseq.h

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