lib/diffseq.h

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