lib/diffseq.h

   1 /* Analyze differences between two vectors.
   2
   3    Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2024 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 <https://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 W. Myers,
  30    Algorithmica Vol. 1, 1986, pp. 251-266,
  31    <https://doi.org/10.1007/BF01840446>.
  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", Esko Ukkonen,
  36    Information and Control Vol. 64, 1985, pp. 100-118,
  37    <https://doi.org/10.1016/S0019-9958(85)80046-2>.
  38
  39    Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
  40    heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
  41    at the price of producing suboptimal output for large inputs with
  42    many differences.  */
  43
  44 /* Before including this file, you need to define:
  45      ELEMENT                 The element type of the vectors being compared.
  46      EQUAL                   A two-argument macro that tests two elements for
  47                              equality.
  48      OFFSET                  A signed integer type sufficient to hold the
  49                              difference between two indices.  Usually
  50                              something like ptrdiff_t.
  51      OFFSET_MAX              (Optional) The maximum value of OFFSET (e.g.,
  52                              PTRDIFF_MAX).  If omitted, it is inferred in a
  53                              way portable to the vast majority of C platforms,
  54                              as they lack padding bits.
  55      EXTRA_CONTEXT_FIELDS    Declarations of fields for 'struct context'.
  56      NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
  57      NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
  58      NOTE_ORDERED            (Optional) A boolean expression saying that
  59                              NOTE_DELETE and NOTE_INSERT calls must be
  60                              issued in offset order.
  61      EARLY_ABORT(ctxt)       (Optional) A boolean expression that triggers an
  62                              early abort of the computation.
  63      USE_HEURISTIC           (Optional) Define if you want to support the
  64                              heuristic for large vectors.
  65
  66    It is also possible to use this file with abstract arrays.  In this case,
  67    xvec and yvec are not represented in memory.  They only exist conceptually.
  68    In this case, the list of defines above is amended as follows:
  69      ELEMENT                 Undefined.
  70      EQUAL                   Undefined.
  71      XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff)
  72                              A three-argument macro: References xvec[xoff] and
  73                              yvec[yoff] and tests these elements for equality.
  74
  75    Before including this file, you also need to include:
  76      #include <limits.h>
  77      #include "minmax.h"
  78  */
  79
  80 /* Maximum value of type OFFSET.  */
  81 #ifndef OFFSET_MAX
  82 # define OFFSET_MAX \
  83    ((((OFFSET) 1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
  84 #endif
  85
  86 /* Default to no early abort.  */
  87 #ifndef EARLY_ABORT
  88 # define EARLY_ABORT(ctxt) false
  89 #endif
  90
  91 #ifndef NOTE_ORDERED
  92 # define NOTE_ORDERED false
  93 #endif
  94
  95 /* Suppress gcc's "...may be used before initialized" warnings,
  96    generated by GCC versions up to at least GCC 13.2.  */
  97 #if __GNUC__ + (__GNUC_MINOR__ >= 7) > 4
  98 # pragma GCC diagnostic push
  99 # pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
 100 #endif
 101
 102 /*
 103  * Context of comparison operation.
 104  */
 105 struct context
 106 {
 107   #ifdef ELEMENT
 108   /* Vectors being compared.  */
 109   ELEMENT const *xvec;
 110   ELEMENT const *yvec;
 111   #endif
 112
 113   /* Extra fields.  */
 114   EXTRA_CONTEXT_FIELDS
 115
 116   /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
 117      furthest along the given diagonal in the forward search of the edit
 118      matrix.  */
 119   OFFSET *fdiag;
 120
 121   /* Vector, indexed by diagonal, containing the X coordinate of the point
 122      furthest along the given diagonal in the backward search of the edit
 123      matrix.  */
 124   OFFSET *bdiag;
 125
 126   #ifdef USE_HEURISTIC
 127   /* This corresponds to the diff --speed-large-files flag.  With this
 128      heuristic, for vectors with a constant small density of changes,
 129      the algorithm is linear in the vector size.  */
 130   bool heuristic;
 131   #endif
 132
 133   /* Edit scripts longer than this are too expensive to compute.  */
 134   OFFSET too_expensive;
 135
 136   /* Snakes bigger than this are considered "big".  */
 137   #define SNAKE_LIMIT 20
 138 };
 139
 140 struct partition
 141 {
 142   /* Midpoints of this partition.  */
 143   OFFSET xmid;
 144   OFFSET ymid;
 145
 146   /* True if low half will be analyzed minimally.  */
 147   bool lo_minimal;
 148
 149   /* Likewise for high half.  */
 150   bool hi_minimal;
 151 };
 152
 153
 154 /* Find the midpoint of the shortest edit script for a specified portion
 155    of the two vectors.
 156
 157    Scan from the beginnings of the vectors, and simultaneously from the ends,
 158    doing a breadth-first search through the space of edit-sequence.
 159    When the two searches meet, we have found the midpoint of the shortest
 160    edit sequence.
 161
 162    If FIND_MINIMAL is true, find the minimal edit script regardless of
 163    expense.  Otherwise, if the search is too expensive, use heuristics to
 164    stop the search and report a suboptimal answer.
 165
 166    Set PART->(xmid,ymid) to the midpoint (XMID,YMID).  The diagonal number
 167    XMID - YMID equals the number of inserted elements minus the number
 168    of deleted elements (counting only elements before the midpoint).
 169
 170    Set PART->lo_minimal to true iff the minimal edit script for the
 171    left half of the partition is known; similarly for PART->hi_minimal.
 172
 173    This function assumes that the first elements of the specified portions
 174    of the two vectors do not match, and likewise that the last elements do not
 175    match.  The caller must trim matching elements from the beginning and end
 176    of the portions it is going to specify.
 177
 178    If we return the "wrong" partitions, the worst this can do is cause
 179    suboptimal diff output.  It cannot cause incorrect diff output.  */
 180
 181 static void
 182 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
 183       struct partition *part, struct context *ctxt)
 184 {
 185   OFFSET *const fd = ctxt->fdiag;       /* Give the compiler a chance. */
 186   OFFSET *const bd = ctxt->bdiag;       /* Additional help for the compiler. */
 187 #ifdef ELEMENT
 188   ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
 189   ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
 190   #define XREF_YREF_EQUAL(x,y)  EQUAL (xv[x], yv[y])
 191 #else
 192   #define XREF_YREF_EQUAL(x,y)  XVECREF_YVECREF_EQUAL (ctxt, x, y)
 193 #endif
 194   const OFFSET dmin = xoff - ylim;      /* Minimum valid diagonal. */
 195   const OFFSET dmax = xlim - yoff;      /* Maximum valid diagonal. */
 196   const OFFSET fmid = xoff - yoff;      /* Center diagonal of top-down search. */
 197   const OFFSET bmid = xlim - ylim;      /* Center diagonal of bottom-up search. */
 198   OFFSET fmin = fmid;
 199   OFFSET fmax = fmid;           /* Limits of top-down search. */
 200   OFFSET bmin = bmid;
 201   OFFSET bmax = bmid;           /* Limits of bottom-up search. */
 202   OFFSET c;                     /* Cost. */
 203   bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
 204                                    diagonal with respect to the northwest. */
 205
 206   fd[fmid] = xoff;
 207   bd[bmid] = xlim;
 208
 209   for (c = 1;; ++c)
 210     {
 211       OFFSET d;                 /* Active diagonal. */
 212       bool big_snake = false;
 213
 214       /* Extend the top-down search by an edit step in each diagonal. */
 215       if (fmin > dmin)
 216         fd[--fmin - 1] = -1;
 217       else
 218         ++fmin;
 219       if (fmax < dmax)
 220         fd[++fmax + 1] = -1;
 221       else
 222         --fmax;
 223       for (d = fmax; d >= fmin; d -= 2)
 224         {
 225           OFFSET x;
 226           OFFSET y;
 227           OFFSET tlo = fd[d - 1];
 228           OFFSET thi = fd[d + 1];
 229           OFFSET x0 = tlo < thi ? thi : tlo + 1;
 230
 231           for (x = x0, y = x0 - d;
 232                x < xlim && y < ylim && XREF_YREF_EQUAL (x, y);
 233                x++, y++)
 234             continue;
 235           if (x - x0 > SNAKE_LIMIT)
 236             big_snake = true;
 237           fd[d] = x;
 238           if (odd && bmin <= d && d <= bmax && bd[d] <= x)
 239             {
 240               part->xmid = x;
 241               part->ymid = y;
 242               part->lo_minimal = part->hi_minimal = true;
 243               return;
 244             }
 245         }
 246
 247       /* Similarly extend the bottom-up search.  */
 248       if (bmin > dmin)
 249         bd[--bmin - 1] = OFFSET_MAX;
 250       else
 251         ++bmin;
 252       if (bmax < dmax)
 253         bd[++bmax + 1] = OFFSET_MAX;
 254       else
 255         --bmax;
 256       for (d = bmax; d >= bmin; d -= 2)
 257         {
 258           OFFSET x;
 259           OFFSET y;
 260           OFFSET tlo = bd[d - 1];
 261           OFFSET thi = bd[d + 1];
 262           OFFSET x0 = tlo < thi ? tlo : thi - 1;
 263
 264           for (x = x0, y = x0 - d;
 265                xoff < x && yoff < y && XREF_YREF_EQUAL (x - 1, y - 1);
 266                x--, y--)
 267             continue;
 268           if (x0 - x > SNAKE_LIMIT)
 269             big_snake = true;
 270           bd[d] = x;
 271           if (!odd && fmin <= d && d <= fmax && x <= fd[d])
 272             {
 273               part->xmid = x;
 274               part->ymid = y;
 275               part->lo_minimal = part->hi_minimal = true;
 276               return;
 277             }
 278         }
 279
 280       if (find_minimal)
 281         continue;
 282
 283 #ifdef USE_HEURISTIC
 284       bool heuristic = ctxt->heuristic;
 285 #else
 286       bool heuristic = false;
 287 #endif
 288
 289       /* Heuristic: check occasionally for a diagonal that has made lots
 290          of progress compared with the edit distance.  If we have any
 291          such, find the one that has made the most progress and return it
 292          as if it had succeeded.
 293
 294          With this heuristic, for vectors with a constant small density
 295          of changes, the algorithm is linear in the vector size.  */
 296
 297       if (200 < c && big_snake && heuristic)
 298         {
 299           {
 300             OFFSET best = 0;
 301
 302             for (d = fmax; d >= fmin; d -= 2)
 303               {
 304                 OFFSET dd = d - fmid;
 305                 OFFSET x = fd[d];
 306                 OFFSET y = x - d;
 307                 OFFSET v = (x - xoff) * 2 - dd;
 308
 309                 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
 310                   {
 311                     if (v > best
 312                         && xoff + SNAKE_LIMIT <= x && x < xlim
 313                         && yoff + SNAKE_LIMIT <= y && y < ylim)
 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 = 1; XREF_YREF_EQUAL (x - k, y - k); k++)
 320                           if (k == SNAKE_LIMIT)
 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 = true;
 333                 part->hi_minimal = false;
 334                 return;
 335               }
 336           }
 337
 338           {
 339             OFFSET best = 0;
 340
 341             for (d = bmax; d >= bmin; d -= 2)
 342               {
 343                 OFFSET dd = d - bmid;
 344                 OFFSET x = bd[d];
 345                 OFFSET y = x - d;
 346                 OFFSET v = (xlim - x) * 2 + dd;
 347
 348                 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
 349                   {
 350                     if (v > best
 351                         && xoff < x && x <= xlim - SNAKE_LIMIT
 352                         && yoff < y && y <= ylim - SNAKE_LIMIT)
 353                       {
 354                         /* We have a good enough best diagonal; now insist
 355                            that it end with a significant snake.  */
 356                         int k;
 357
 358                         for (k = 0; XREF_YREF_EQUAL (x + k, y + k); k++)
 359                           if (k == SNAKE_LIMIT - 1)
 360                             {
 361                               best = v;
 362                               part->xmid = x;
 363                               part->ymid = y;
 364                               break;
 365                             }
 366                       }
 367                   }
 368               }
 369             if (best > 0)
 370               {
 371                 part->lo_minimal = false;
 372                 part->hi_minimal = true;
 373                 return;
 374               }
 375           }
 376         }
 377
 378       /* Heuristic: if we've gone well beyond the call of duty, give up
 379          and report halfway between our best results so far.  */
 380       if (c >= ctxt->too_expensive)
 381         {
 382           /* Find forward diagonal that maximizes X + Y.  */
 383           OFFSET fxybest = -1, fxbest;
 384           for (d = fmax; d >= fmin; d -= 2)
 385             {
 386               OFFSET x = MIN (fd[d], xlim);
 387               OFFSET y = x - d;
 388               if (ylim < y)
 389                 {
 390                   x = ylim + d;
 391                   y = ylim;
 392                 }
 393               if (fxybest < x + y)
 394                 {
 395                   fxybest = x + y;
 396                   fxbest = x;
 397                 }
 398             }
 399
 400           /* Find backward diagonal that minimizes X + Y.  */
 401           OFFSET bxybest = OFFSET_MAX, bxbest;
 402           for (d = bmax; d >= bmin; d -= 2)
 403             {
 404               OFFSET x = MAX (xoff, bd[d]);
 405               OFFSET y = x - d;
 406               if (y < yoff)
 407                 {
 408                   x = yoff + d;
 409                   y = yoff;
 410                 }
 411               if (x + y < bxybest)
 412                 {
 413                   bxybest = x + y;
 414                   bxbest = x;
 415                 }
 416             }
 417
 418           /* Use the better of the two diagonals.  */
 419           if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
 420             {
 421               part->xmid = fxbest;
 422               part->ymid = fxybest - fxbest;
 423               part->lo_minimal = true;
 424               part->hi_minimal = false;
 425             }
 426           else
 427             {
 428               part->xmid = bxbest;
 429               part->ymid = bxybest - bxbest;
 430               part->lo_minimal = false;
 431               part->hi_minimal = true;
 432             }
 433           return;
 434         }
 435     }
 436   #undef XREF_YREF_EQUAL
 437 }
 438
 439
 440 /* Compare in detail contiguous subsequences of the two vectors
 441    which are known, as a whole, to match each other.
 442
 443    The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1.
 444
 445    Note that XLIM, YLIM are exclusive bounds.  All indices into the vectors
 446    are origin-0.
 447
 448    If FIND_MINIMAL, find a minimal difference no matter how
 449    expensive it is.
 450
 451    The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
 452
 453    Return false if terminated normally, or true if terminated through early
 454    abort.  */
 455
 456 static bool
 457 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
 458             bool find_minimal, struct context *ctxt)
 459 {
 460 #ifdef ELEMENT
 461   ELEMENT const *xv = ctxt->xvec; /* Help the compiler.  */
 462   ELEMENT const *yv = ctxt->yvec;
 463   #define XREF_YREF_EQUAL(x,y)  EQUAL (xv[x], yv[y])
 464 #else
 465   #define XREF_YREF_EQUAL(x,y)  XVECREF_YVECREF_EQUAL (ctxt, x, y)
 466 #endif
 467
 468   while (true)
 469     {
 470       /* Slide down the bottom initial diagonal.  */
 471       while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
 472         {
 473           xoff++;
 474           yoff++;
 475         }
 476
 477       /* Slide up the top initial diagonal. */
 478       while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
 479         {
 480           xlim--;
 481           ylim--;
 482         }
 483
 484       /* Handle simple cases. */
 485       if (xoff == xlim)
 486         {
 487           while (yoff < ylim)
 488             {
 489               NOTE_INSERT (ctxt, yoff);
 490               if (EARLY_ABORT (ctxt))
 491                 return true;
 492               yoff++;
 493             }
 494           break;
 495         }
 496       if (yoff == ylim)
 497         {
 498           while (xoff < xlim)
 499             {
 500               NOTE_DELETE (ctxt, xoff);
 501               if (EARLY_ABORT (ctxt))
 502                 return true;
 503               xoff++;
 504             }
 505           break;
 506         }
 507
 508       struct partition part;
 509
 510       /* Find a point of correspondence in the middle of the vectors.  */
 511       diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
 512
 513       /* Use the partitions to split this problem into subproblems.  */
 514       OFFSET xoff1, xlim1, yoff1, ylim1, xoff2, xlim2, yoff2, ylim2;
 515       bool find_minimal1, find_minimal2;
 516       if (!NOTE_ORDERED
 517           && ((xlim + ylim) - (part.xmid + part.ymid)
 518               < (part.xmid + part.ymid) - (xoff + yoff)))
 519         {
 520           /* The second problem is smaller and the caller doesn't
 521              care about order, so do the second problem first to
 522              lessen recursion.  */
 523           xoff1 = part.xmid; xlim1 = xlim;
 524           yoff1 = part.ymid; ylim1 = ylim;
 525           find_minimal1 = part.hi_minimal;
 526
 527           xoff2 = xoff; xlim2 = part.xmid;
 528           yoff2 = yoff; ylim2 = part.ymid;
 529           find_minimal2 = part.lo_minimal;
 530         }
 531       else
 532         {
 533           xoff1 = xoff; xlim1 = part.xmid;
 534           yoff1 = yoff; ylim1 = part.ymid;
 535           find_minimal1 = part.lo_minimal;
 536
 537           xoff2 = part.xmid; xlim2 = xlim;
 538           yoff2 = part.ymid; ylim2 = ylim;
 539           find_minimal2 = part.hi_minimal;
 540         }
 541
 542       /* Recurse to do one subproblem.  */
 543       bool early = compareseq (xoff1, xlim1, yoff1, ylim1, find_minimal1, ctxt);
 544       if (early)
 545         return early;
 546
 547       /* Iterate to do the other subproblem.  */
 548       xoff = xoff2; xlim = xlim2;
 549       yoff = yoff2; ylim = ylim2;
 550       find_minimal = find_minimal2;
 551     }
 552
 553   return false;
 554   #undef XREF_YREF_EQUAL
 555 }
 556
 557 #if __GNUC__ + (__GNUC_MINOR__ >= 7) > 4
 558 # pragma GCC diagnostic pop
 559 #endif
 560
 561 #undef ELEMENT
 562 #undef EQUAL
 563 #undef OFFSET
 564 #undef EXTRA_CONTEXT_FIELDS
 565 #undef NOTE_DELETE
 566 #undef NOTE_INSERT
 567 #undef EARLY_ABORT
 568 #undef USE_HEURISTIC
 569 #undef XVECREF_YVECREF_EQUAL
 570 #undef OFFSET_MAX