icuSources/common/edits.cpp

   1 // © 2017 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3
   4 // edits.cpp
   5 // created: 2017feb08 Markus W. Scherer
   6
   7 #include "unicode/edits.h"
   8 #include "unicode/unistr.h"
   9 #include "unicode/utypes.h"
  10 #include "cmemory.h"
  11 #include "uassert.h"
  12 #include "util.h"
  13
  14 U_NAMESPACE_BEGIN
  15
  16 namespace {
  17
  18 // 0000uuuuuuuuuuuu records u+1 unchanged text units.
  19 const int32_t MAX_UNCHANGED_LENGTH = 0x1000;
  20 const int32_t MAX_UNCHANGED = MAX_UNCHANGED_LENGTH - 1;
  21
  22 // 0mmmnnnccccccccc with m=1..6 records ccc+1 replacements of m:n text units.
  23 const int32_t MAX_SHORT_CHANGE_OLD_LENGTH = 6;
  24 const int32_t MAX_SHORT_CHANGE_NEW_LENGTH = 7;
  25 const int32_t SHORT_CHANGE_NUM_MASK = 0x1ff;
  26 const int32_t MAX_SHORT_CHANGE = 0x6fff;
  27
  28 // 0111mmmmmmnnnnnn records a replacement of m text units with n.
  29 // m or n = 61: actual length follows in the next edits array unit.
  30 // m or n = 62..63: actual length follows in the next two edits array units.
  31 // Bit 30 of the actual length is in the head unit.
  32 // Trailing units have bit 15 set.
  33 const int32_t LENGTH_IN_1TRAIL = 61;
  34 const int32_t LENGTH_IN_2TRAIL = 62;
  35
  36 }  // namespace
  37
  38 void Edits::releaseArray() U_NOEXCEPT {
  39     if (array != stackArray) {
  40         uprv_free(array);
  41     }
  42 }
  43
  44 Edits &Edits::copyArray(const Edits &other) {
  45     if (U_FAILURE(errorCode_)) {
  46         length = delta = numChanges = 0;
  47         return *this;
  48     }
  49     if (length > capacity) {
  50         uint16_t *newArray = (uint16_t *)uprv_malloc((size_t)length * 2);
  51         if (newArray == nullptr) {
  52             length = delta = numChanges = 0;
  53             errorCode_ = U_MEMORY_ALLOCATION_ERROR;
  54             return *this;
  55         }
  56         releaseArray();
  57         array = newArray;
  58         capacity = length;
  59     }
  60     if (length > 0) {
  61         uprv_memcpy(array, other.array, (size_t)length * 2);
  62     }
  63     return *this;
  64 }
  65
  66 Edits &Edits::moveArray(Edits &src) U_NOEXCEPT {
  67     if (U_FAILURE(errorCode_)) {
  68         length = delta = numChanges = 0;
  69         return *this;
  70     }
  71     releaseArray();
  72     if (length > STACK_CAPACITY) {
  73         array = src.array;
  74         capacity = src.capacity;
  75         src.array = src.stackArray;
  76         src.capacity = STACK_CAPACITY;
  77         src.reset();
  78         return *this;
  79     }
  80     array = stackArray;
  81     capacity = STACK_CAPACITY;
  82     if (length > 0) {
  83         uprv_memcpy(array, src.array, (size_t)length * 2);
  84     }
  85     return *this;
  86 }
  87
  88 Edits &Edits::operator=(const Edits &other) {
  89     length = other.length;
  90     delta = other.delta;
  91     numChanges = other.numChanges;
  92     errorCode_ = other.errorCode_;
  93     return copyArray(other);
  94 }
  95
  96 Edits &Edits::operator=(Edits &&src) U_NOEXCEPT {
  97     length = src.length;
  98     delta = src.delta;
  99     numChanges = src.numChanges;
 100     errorCode_ = src.errorCode_;
 101     return moveArray(src);
 102 }
 103
 104 Edits::~Edits() {
 105     releaseArray();
 106 }
 107
 108 void Edits::reset() U_NOEXCEPT {
 109     length = delta = numChanges = 0;
 110     errorCode_ = U_ZERO_ERROR;
 111 }
 112
 113 void Edits::addUnchanged(int32_t unchangedLength) {
 114     if(U_FAILURE(errorCode_) || unchangedLength == 0) { return; }
 115     if(unchangedLength < 0) {
 116         errorCode_ = U_ILLEGAL_ARGUMENT_ERROR;
 117         return;
 118     }
 119     // Merge into previous unchanged-text record, if any.
 120     int32_t last = lastUnit();
 121     if(last < MAX_UNCHANGED) {
 122         int32_t remaining = MAX_UNCHANGED - last;
 123         if (remaining >= unchangedLength) {
 124             setLastUnit(last + unchangedLength);
 125             return;
 126         }
 127         setLastUnit(MAX_UNCHANGED);
 128         unchangedLength -= remaining;
 129     }
 130     // Split large lengths into multiple units.
 131     while(unchangedLength >= MAX_UNCHANGED_LENGTH) {
 132         append(MAX_UNCHANGED);
 133         unchangedLength -= MAX_UNCHANGED_LENGTH;
 134     }
 135     // Write a small (remaining) length.
 136     if(unchangedLength > 0) {
 137         append(unchangedLength - 1);
 138     }
 139 }
 140
 141 void Edits::addReplace(int32_t oldLength, int32_t newLength) {
 142     if(U_FAILURE(errorCode_)) { return; }
 143     if(oldLength < 0 || newLength < 0) {
 144         errorCode_ = U_ILLEGAL_ARGUMENT_ERROR;
 145         return;
 146     }
 147     if (oldLength == 0 && newLength == 0) {
 148         return;
 149     }
 150     ++numChanges;
 151     int32_t newDelta = newLength - oldLength;
 152     if (newDelta != 0) {
 153         if ((newDelta > 0 && delta >= 0 && newDelta > (INT32_MAX - delta)) ||
 154                 (newDelta < 0 && delta < 0 && newDelta < (INT32_MIN - delta))) {
 155             // Integer overflow or underflow.
 156             errorCode_ = U_INDEX_OUTOFBOUNDS_ERROR;
 157             return;
 158         }
 159         delta += newDelta;
 160     }
 161
 162     if(0 < oldLength && oldLength <= MAX_SHORT_CHANGE_OLD_LENGTH &&
 163             newLength <= MAX_SHORT_CHANGE_NEW_LENGTH) {
 164         // Merge into previous same-lengths short-replacement record, if any.
 165         int32_t u = (oldLength << 12) | (newLength << 9);
 166         int32_t last = lastUnit();
 167         if(MAX_UNCHANGED < last && last < MAX_SHORT_CHANGE &&
 168                 (last & ~SHORT_CHANGE_NUM_MASK) == u &&
 169                 (last & SHORT_CHANGE_NUM_MASK) < SHORT_CHANGE_NUM_MASK) {
 170             setLastUnit(last + 1);
 171             return;
 172         }
 173         append(u);
 174         return;
 175     }
 176
 177     int32_t head = 0x7000;
 178     if (oldLength < LENGTH_IN_1TRAIL && newLength < LENGTH_IN_1TRAIL) {
 179         head |= oldLength << 6;
 180         head |= newLength;
 181         append(head);
 182     } else if ((capacity - length) >= 5 || growArray()) {
 183         int32_t limit = length + 1;
 184         if(oldLength < LENGTH_IN_1TRAIL) {
 185             head |= oldLength << 6;
 186         } else if(oldLength <= 0x7fff) {
 187             head |= LENGTH_IN_1TRAIL << 6;
 188             array[limit++] = (uint16_t)(0x8000 | oldLength);
 189         } else {
 190             head |= (LENGTH_IN_2TRAIL + (oldLength >> 30)) << 6;
 191             array[limit++] = (uint16_t)(0x8000 | (oldLength >> 15));
 192             array[limit++] = (uint16_t)(0x8000 | oldLength);
 193         }
 194         if(newLength < LENGTH_IN_1TRAIL) {
 195             head |= newLength;
 196         } else if(newLength <= 0x7fff) {
 197             head |= LENGTH_IN_1TRAIL;
 198             array[limit++] = (uint16_t)(0x8000 | newLength);
 199         } else {
 200             head |= LENGTH_IN_2TRAIL + (newLength >> 30);
 201             array[limit++] = (uint16_t)(0x8000 | (newLength >> 15));
 202             array[limit++] = (uint16_t)(0x8000 | newLength);
 203         }
 204         array[length] = (uint16_t)head;
 205         length = limit;
 206     }
 207 }
 208
 209 void Edits::append(int32_t r) {
 210     if(length < capacity || growArray()) {
 211         array[length++] = (uint16_t)r;
 212     }
 213 }
 214
 215 UBool Edits::growArray() {
 216     int32_t newCapacity;
 217     if (array == stackArray) {
 218         newCapacity = 2000;
 219     } else if (capacity == INT32_MAX) {
 220         // Not U_BUFFER_OVERFLOW_ERROR because that could be confused on a string transform API
 221         // with a result-string-buffer overflow.
 222         errorCode_ = U_INDEX_OUTOFBOUNDS_ERROR;
 223         return FALSE;
 224     } else if (capacity >= (INT32_MAX / 2)) {
 225         newCapacity = INT32_MAX;
 226     } else {
 227         newCapacity = 2 * capacity;
 228     }
 229     // Grow by at least 5 units so that a maximal change record will fit.
 230     if ((newCapacity - capacity) < 5) {
 231         errorCode_ = U_INDEX_OUTOFBOUNDS_ERROR;
 232         return FALSE;
 233     }
 234     uint16_t *newArray = (uint16_t *)uprv_malloc((size_t)newCapacity * 2);
 235     if (newArray == NULL) {
 236         errorCode_ = U_MEMORY_ALLOCATION_ERROR;
 237         return FALSE;
 238     }
 239     uprv_memcpy(newArray, array, (size_t)length * 2);
 240     releaseArray();
 241     array = newArray;
 242     capacity = newCapacity;
 243     return TRUE;
 244 }
 245
 246 UBool Edits::copyErrorTo(UErrorCode &outErrorCode) {
 247     if (U_FAILURE(outErrorCode)) { return TRUE; }
 248     if (U_SUCCESS(errorCode_)) { return FALSE; }
 249     outErrorCode = errorCode_;
 250     return TRUE;
 251 }
 252
 253 Edits &Edits::mergeAndAppend(const Edits &ab, const Edits &bc, UErrorCode &errorCode) {
 254     if (copyErrorTo(errorCode)) { return *this; }
 255     // Picture string a --(Edits ab)--> string b --(Edits bc)--> string c.
 256     // Parallel iteration over both Edits.
 257     Iterator abIter = ab.getFineIterator();
 258     Iterator bcIter = bc.getFineIterator();
 259     UBool abHasNext = TRUE, bcHasNext = TRUE;
 260     // Copy iterator state into local variables, so that we can modify and subdivide spans.
 261     // ab old & new length, bc old & new length
 262     int32_t aLength = 0, ab_bLength = 0, bc_bLength = 0, cLength = 0;
 263     // When we have different-intermediate-length changes, we accumulate a larger change.
 264     int32_t pending_aLength = 0, pending_cLength = 0;
 265     for (;;) {
 266         // At this point, for each of the two iterators:
 267         // Either we are done with the locally cached current edit,
 268         // and its intermediate-string length has been reset,
 269         // or we will continue to work with a truncated remainder of this edit.
 270         //
 271         // If the current edit is done, and the iterator has not yet reached the end,
 272         // then we fetch the next edit. This is true for at least one of the iterators.
 273         //
 274         // Normally it does not matter whether we fetch from ab and then bc or vice versa.
 275         // However, the result is observably different when
 276         // ab deletions meet bc insertions at the same intermediate-string index.
 277         // Some users expect the bc insertions to come first, so we fetch from bc first.
 278         if (bc_bLength == 0) {
 279             if (bcHasNext && (bcHasNext = bcIter.next(errorCode)) != 0) {
 280                 bc_bLength = bcIter.oldLength();
 281                 cLength = bcIter.newLength();
 282                 if (bc_bLength == 0) {
 283                     // insertion
 284                     if (ab_bLength == 0 || !abIter.hasChange()) {
 285                         addReplace(pending_aLength, pending_cLength + cLength);
 286                         pending_aLength = pending_cLength = 0;
 287                     } else {
 288                         pending_cLength += cLength;
 289                     }
 290                     continue;
 291                 }
 292             }
 293             // else see if the other iterator is done, too.
 294         }
 295         if (ab_bLength == 0) {
 296             if (abHasNext && (abHasNext = abIter.next(errorCode)) != 0) {
 297                 aLength = abIter.oldLength();
 298                 ab_bLength = abIter.newLength();
 299                 if (ab_bLength == 0) {
 300                     // deletion
 301                     if (bc_bLength == bcIter.oldLength() || !bcIter.hasChange()) {
 302                         addReplace(pending_aLength + aLength, pending_cLength);
 303                         pending_aLength = pending_cLength = 0;
 304                     } else {
 305                         pending_aLength += aLength;
 306                     }
 307                     continue;
 308                 }
 309             } else if (bc_bLength == 0) {
 310                 // Both iterators are done at the same time:
 311                 // The intermediate-string lengths match.
 312                 break;
 313             } else {
 314                 // The ab output string is shorter than the bc input string.
 315                 if (!copyErrorTo(errorCode)) {
 316                     errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 317                 }
 318                 return *this;
 319             }
 320         }
 321         if (bc_bLength == 0) {
 322             // The bc input string is shorter than the ab output string.
 323             if (!copyErrorTo(errorCode)) {
 324                 errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 325             }
 326             return *this;
 327         }
 328         //  Done fetching: ab_bLength > 0 && bc_bLength > 0
 329
 330         // The current state has two parts:
 331         // - Past: We accumulate a longer ac edit in the "pending" variables.
 332         // - Current: We have copies of the current ab/bc edits in local variables.
 333         //   At least one side is newly fetched.
 334         //   One side might be a truncated remainder of an edit we fetched earlier.
 335
 336         if (!abIter.hasChange() && !bcIter.hasChange()) {
 337             // An unchanged span all the way from string a to string c.
 338             if (pending_aLength != 0 || pending_cLength != 0) {
 339                 addReplace(pending_aLength, pending_cLength);
 340                 pending_aLength = pending_cLength = 0;
 341             }
 342             int32_t unchangedLength = aLength <= cLength ? aLength : cLength;
 343             addUnchanged(unchangedLength);
 344             ab_bLength = aLength -= unchangedLength;
 345             bc_bLength = cLength -= unchangedLength;
 346             // At least one of the unchanged spans is now empty.
 347             continue;
 348         }
 349         if (!abIter.hasChange() && bcIter.hasChange()) {
 350             // Unchanged a->b but changed b->c.
 351             if (ab_bLength >= bc_bLength) {
 352                 // Split the longer unchanged span into change + remainder.
 353                 addReplace(pending_aLength + bc_bLength, pending_cLength + cLength);
 354                 pending_aLength = pending_cLength = 0;
 355                 aLength = ab_bLength -= bc_bLength;
 356                 bc_bLength = 0;
 357                 continue;
 358             }
 359             // Handle the shorter unchanged span below like a change.
 360         } else if (abIter.hasChange() && !bcIter.hasChange()) {
 361             // Changed a->b and then unchanged b->c.
 362             if (ab_bLength <= bc_bLength) {
 363                 // Split the longer unchanged span into change + remainder.
 364                 addReplace(pending_aLength + aLength, pending_cLength + ab_bLength);
 365                 pending_aLength = pending_cLength = 0;
 366                 cLength = bc_bLength -= ab_bLength;
 367                 ab_bLength = 0;
 368                 continue;
 369             }
 370             // Handle the shorter unchanged span below like a change.
 371         } else {  // both abIter.hasChange() && bcIter.hasChange()
 372             if (ab_bLength == bc_bLength) {
 373                 // Changes on both sides up to the same position. Emit & reset.
 374                 addReplace(pending_aLength + aLength, pending_cLength + cLength);
 375                 pending_aLength = pending_cLength = 0;
 376                 ab_bLength = bc_bLength = 0;
 377                 continue;
 378             }
 379         }
 380         // Accumulate the a->c change, reset the shorter side,
 381         // keep a remainder of the longer one.
 382         pending_aLength += aLength;
 383         pending_cLength += cLength;
 384         if (ab_bLength < bc_bLength) {
 385             bc_bLength -= ab_bLength;
 386             cLength = ab_bLength = 0;
 387         } else {  // ab_bLength > bc_bLength
 388             ab_bLength -= bc_bLength;
 389             aLength = bc_bLength = 0;
 390         }
 391     }
 392     if (pending_aLength != 0 || pending_cLength != 0) {
 393         addReplace(pending_aLength, pending_cLength);
 394     }
 395     copyErrorTo(errorCode);
 396     return *this;
 397 }
 398
 399 Edits::Iterator::Iterator(const uint16_t *a, int32_t len, UBool oc, UBool crs) :
 400         array(a), index(0), length(len), remaining(0),
 401         onlyChanges_(oc), coarse(crs),
 402         dir(0), changed(FALSE), oldLength_(0), newLength_(0),
 403         srcIndex(0), replIndex(0), destIndex(0) {}
 404
 405 int32_t Edits::Iterator::readLength(int32_t head) {
 406     if (head < LENGTH_IN_1TRAIL) {
 407         return head;
 408     } else if (head < LENGTH_IN_2TRAIL) {
 409         U_ASSERT(index < length);
 410         U_ASSERT(array[index] >= 0x8000);
 411         return array[index++] & 0x7fff;
 412     } else {
 413         U_ASSERT((index + 2) <= length);
 414         U_ASSERT(array[index] >= 0x8000);
 415         U_ASSERT(array[index + 1] >= 0x8000);
 416         int32_t len = ((head & 1) << 30) |
 417                 ((int32_t)(array[index] & 0x7fff) << 15) |
 418                 (array[index + 1] & 0x7fff);
 419         index += 2;
 420         return len;
 421     }
 422 }
 423
 424 void Edits::Iterator::updateNextIndexes() {
 425     srcIndex += oldLength_;
 426     if (changed) {
 427         replIndex += newLength_;
 428     }
 429     destIndex += newLength_;
 430 }
 431
 432 void Edits::Iterator::updatePreviousIndexes() {
 433     srcIndex -= oldLength_;
 434     if (changed) {
 435         replIndex -= newLength_;
 436     }
 437     destIndex -= newLength_;
 438 }
 439
 440 UBool Edits::Iterator::noNext() {
 441     // No change before or beyond the string.
 442     dir = 0;
 443     changed = FALSE;
 444     oldLength_ = newLength_ = 0;
 445     return FALSE;
 446 }
 447
 448 UBool Edits::Iterator::next(UBool onlyChanges, UErrorCode &errorCode) {
 449     // Forward iteration: Update the string indexes to the limit of the current span,
 450     // and post-increment-read array units to assemble a new span.
 451     // Leaves the array index one after the last unit of that span.
 452     if (U_FAILURE(errorCode)) { return FALSE; }
 453     // We have an errorCode in case we need to start guarding against integer overflows.
 454     // It is also convenient for caller loops if we bail out when an error was set elsewhere.
 455     if (dir > 0) {
 456         updateNextIndexes();
 457     } else {
 458         if (dir < 0) {
 459             // Turn around from previous() to next().
 460             // Post-increment-read the same span again.
 461             if (remaining > 0) {
 462                 // Fine-grained iterator:
 463                 // Stay on the current one of a sequence of compressed changes.
 464                 ++index;  // next() rests on the index after the sequence unit.
 465                 dir = 1;
 466                 return TRUE;
 467             }
 468         }
 469         dir = 1;
 470     }
 471     if (remaining >= 1) {
 472         // Fine-grained iterator: Continue a sequence of compressed changes.
 473         if (remaining > 1) {
 474             --remaining;
 475             return TRUE;
 476         }
 477         remaining = 0;
 478     }
 479     if (index >= length) {
 480         return noNext();
 481     }
 482     int32_t u = array[index++];
 483     if (u <= MAX_UNCHANGED) {
 484         // Combine adjacent unchanged ranges.
 485         changed = FALSE;
 486         oldLength_ = u + 1;
 487         while (index < length && (u = array[index]) <= MAX_UNCHANGED) {
 488             ++index;
 489             oldLength_ += u + 1;
 490         }
 491         newLength_ = oldLength_;
 492         if (onlyChanges) {
 493             updateNextIndexes();
 494             if (index >= length) {
 495                 return noNext();
 496             }
 497             // already fetched u > MAX_UNCHANGED at index
 498             ++index;
 499         } else {
 500             return TRUE;
 501         }
 502     }
 503     changed = TRUE;
 504     if (u <= MAX_SHORT_CHANGE) {
 505         int32_t oldLen = u >> 12;
 506         int32_t newLen = (u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH;
 507         int32_t num = (u & SHORT_CHANGE_NUM_MASK) + 1;
 508         if (coarse) {
 509             oldLength_ = num * oldLen;
 510             newLength_ = num * newLen;
 511         } else {
 512             // Split a sequence of changes that was compressed into one unit.
 513             oldLength_ = oldLen;
 514             newLength_ = newLen;
 515             if (num > 1) {
 516                 remaining = num;  // This is the first of two or more changes.
 517             }
 518             return TRUE;
 519         }
 520     } else {
 521         U_ASSERT(u <= 0x7fff);
 522         oldLength_ = readLength((u >> 6) & 0x3f);
 523         newLength_ = readLength(u & 0x3f);
 524         if (!coarse) {
 525             return TRUE;
 526         }
 527     }
 528     // Combine adjacent changes.
 529     while (index < length && (u = array[index]) > MAX_UNCHANGED) {
 530         ++index;
 531         if (u <= MAX_SHORT_CHANGE) {
 532             int32_t num = (u & SHORT_CHANGE_NUM_MASK) + 1;
 533             oldLength_ += (u >> 12) * num;
 534             newLength_ += ((u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH) * num;
 535         } else {
 536             U_ASSERT(u <= 0x7fff);
 537             oldLength_ += readLength((u >> 6) & 0x3f);
 538             newLength_ += readLength(u & 0x3f);
 539         }
 540     }
 541     return TRUE;
 542 }
 543
 544 UBool Edits::Iterator::previous(UErrorCode &errorCode) {
 545     // Backward iteration: Pre-decrement-read array units to assemble a new span,
 546     // then update the string indexes to the start of that span.
 547     // Leaves the array index on the head unit of that span.
 548     if (U_FAILURE(errorCode)) { return FALSE; }
 549     // We have an errorCode in case we need to start guarding against integer overflows.
 550     // It is also convenient for caller loops if we bail out when an error was set elsewhere.
 551     if (dir >= 0) {
 552         if (dir > 0) {
 553             // Turn around from next() to previous().
 554             // Set the string indexes to the span limit and
 555             // pre-decrement-read the same span again.
 556             if (remaining > 0) {
 557                 // Fine-grained iterator:
 558                 // Stay on the current one of a sequence of compressed changes.
 559                 --index;  // previous() rests on the sequence unit.
 560                 dir = -1;
 561                 return TRUE;
 562             }
 563             updateNextIndexes();
 564         }
 565         dir = -1;
 566     }
 567     if (remaining > 0) {
 568         // Fine-grained iterator: Continue a sequence of compressed changes.
 569         int32_t u = array[index];
 570         U_ASSERT(MAX_UNCHANGED < u && u <= MAX_SHORT_CHANGE);
 571         if (remaining <= (u & SHORT_CHANGE_NUM_MASK)) {
 572             ++remaining;
 573             updatePreviousIndexes();
 574             return TRUE;
 575         }
 576         remaining = 0;
 577     }
 578     if (index <= 0) {
 579         return noNext();
 580     }
 581     int32_t u = array[--index];
 582     if (u <= MAX_UNCHANGED) {
 583         // Combine adjacent unchanged ranges.
 584         changed = FALSE;
 585         oldLength_ = u + 1;
 586         while (index > 0 && (u = array[index - 1]) <= MAX_UNCHANGED) {
 587             --index;
 588             oldLength_ += u + 1;
 589         }
 590         newLength_ = oldLength_;
 591         // No need to handle onlyChanges as long as previous() is called only from findIndex().
 592         updatePreviousIndexes();
 593         return TRUE;
 594     }
 595     changed = TRUE;
 596     if (u <= MAX_SHORT_CHANGE) {
 597         int32_t oldLen = u >> 12;
 598         int32_t newLen = (u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH;
 599         int32_t num = (u & SHORT_CHANGE_NUM_MASK) + 1;
 600         if (coarse) {
 601             oldLength_ = num * oldLen;
 602             newLength_ = num * newLen;
 603         } else {
 604             // Split a sequence of changes that was compressed into one unit.
 605             oldLength_ = oldLen;
 606             newLength_ = newLen;
 607             if (num > 1) {
 608                 remaining = 1;  // This is the last of two or more changes.
 609             }
 610             updatePreviousIndexes();
 611             return TRUE;
 612         }
 613     } else {
 614         if (u <= 0x7fff) {
 615             // The change is encoded in u alone.
 616             oldLength_ = readLength((u >> 6) & 0x3f);
 617             newLength_ = readLength(u & 0x3f);
 618         } else {
 619             // Back up to the head of the change, read the lengths,
 620             // and reset the index to the head again.
 621             U_ASSERT(index > 0);
 622             while ((u = array[--index]) > 0x7fff) {}
 623             U_ASSERT(u > MAX_SHORT_CHANGE);
 624             int32_t headIndex = index++;
 625             oldLength_ = readLength((u >> 6) & 0x3f);
 626             newLength_ = readLength(u & 0x3f);
 627             index = headIndex;
 628         }
 629         if (!coarse) {
 630             updatePreviousIndexes();
 631             return TRUE;
 632         }
 633     }
 634     // Combine adjacent changes.
 635     while (index > 0 && (u = array[index - 1]) > MAX_UNCHANGED) {
 636         --index;
 637         if (u <= MAX_SHORT_CHANGE) {
 638             int32_t num = (u & SHORT_CHANGE_NUM_MASK) + 1;
 639             oldLength_ += (u >> 12) * num;
 640             newLength_ += ((u >> 9) & MAX_SHORT_CHANGE_NEW_LENGTH) * num;
 641         } else if (u <= 0x7fff) {
 642             // Read the lengths, and reset the index to the head again.
 643             int32_t headIndex = index++;
 644             oldLength_ += readLength((u >> 6) & 0x3f);
 645             newLength_ += readLength(u & 0x3f);
 646             index = headIndex;
 647         }
 648     }
 649     updatePreviousIndexes();
 650     return TRUE;
 651 }
 652
 653 int32_t Edits::Iterator::findIndex(int32_t i, UBool findSource, UErrorCode &errorCode) {
 654     if (U_FAILURE(errorCode) || i < 0) { return -1; }
 655     int32_t spanStart, spanLength;
 656     if (findSource) {  // find source index
 657         spanStart = srcIndex;
 658         spanLength = oldLength_;
 659     } else {  // find destination index
 660         spanStart = destIndex;
 661         spanLength = newLength_;
 662     }
 663     if (i < spanStart) {
 664         if (i >= (spanStart / 2)) {
 665             // Search backwards.
 666             for (;;) {
 667                 UBool hasPrevious = previous(errorCode);
 668                 U_ASSERT(hasPrevious);  // because i>=0 and the first span starts at 0
 669                 (void)hasPrevious;  // avoid unused-variable warning
 670                 spanStart = findSource ? srcIndex : destIndex;
 671                 if (i >= spanStart) {
 672                     // The index is in the current span.
 673                     return 0;
 674                 }
 675                 if (remaining > 0) {
 676                     // Is the index in one of the remaining compressed edits?
 677                     // spanStart is the start of the current span, first of the remaining ones.
 678                     spanLength = findSource ? oldLength_ : newLength_;
 679                     int32_t u = array[index];
 680                     U_ASSERT(MAX_UNCHANGED < u && u <= MAX_SHORT_CHANGE);
 681                     int32_t num = (u & SHORT_CHANGE_NUM_MASK) + 1 - remaining;
 682                     int32_t len = num * spanLength;
 683                     if (i >= (spanStart - len)) {
 684                         int32_t n = ((spanStart - i - 1) / spanLength) + 1;
 685                         // 1 <= n <= num
 686                         srcIndex -= n * oldLength_;
 687                         replIndex -= n * newLength_;
 688                         destIndex -= n * newLength_;
 689                         remaining += n;
 690                         return 0;
 691                     }
 692                     // Skip all of these edits at once.
 693                     srcIndex -= num * oldLength_;
 694                     replIndex -= num * newLength_;
 695                     destIndex -= num * newLength_;
 696                     remaining = 0;
 697                 }
 698             }
 699         }
 700         // Reset the iterator to the start.
 701         dir = 0;
 702         index = remaining = oldLength_ = newLength_ = srcIndex = replIndex = destIndex = 0;
 703     } else if (i < (spanStart + spanLength)) {
 704         // The index is in the current span.
 705         return 0;
 706     }
 707     while (next(FALSE, errorCode)) {
 708         if (findSource) {
 709             spanStart = srcIndex;
 710             spanLength = oldLength_;
 711         } else {
 712             spanStart = destIndex;
 713             spanLength = newLength_;
 714         }
 715         if (i < (spanStart + spanLength)) {
 716             // The index is in the current span.
 717             return 0;
 718         }
 719         if (remaining > 1) {
 720             // Is the index in one of the remaining compressed edits?
 721             // spanStart is the start of the current span, first of the remaining ones.
 722             int32_t len = remaining * spanLength;
 723             if (i < (spanStart + len)) {
 724                 int32_t n = (i - spanStart) / spanLength;  // 1 <= n <= remaining - 1
 725                 srcIndex += n * oldLength_;
 726                 replIndex += n * newLength_;
 727                 destIndex += n * newLength_;
 728                 remaining -= n;
 729                 return 0;
 730             }
 731             // Make next() skip all of these edits at once.
 732             oldLength_ *= remaining;
 733             newLength_ *= remaining;
 734             remaining = 0;
 735         }
 736     }
 737     return 1;
 738 }
 739
 740 int32_t Edits::Iterator::destinationIndexFromSourceIndex(int32_t i, UErrorCode &errorCode) {
 741     int32_t where = findIndex(i, TRUE, errorCode);
 742     if (where < 0) {
 743         // Error or before the string.
 744         return 0;
 745     }
 746     if (where > 0 || i == srcIndex) {
 747         // At or after string length, or at start of the found span.
 748         return destIndex;
 749     }
 750     if (changed) {
 751         // In a change span, map to its end.
 752         return destIndex + newLength_;
 753     } else {
 754         // In an unchanged span, offset 1:1 within it.
 755         return destIndex + (i - srcIndex);
 756     }
 757 }
 758
 759 int32_t Edits::Iterator::sourceIndexFromDestinationIndex(int32_t i, UErrorCode &errorCode) {
 760     int32_t where = findIndex(i, FALSE, errorCode);
 761     if (where < 0) {
 762         // Error or before the string.
 763         return 0;
 764     }
 765     if (where > 0 || i == destIndex) {
 766         // At or after string length, or at start of the found span.
 767         return srcIndex;
 768     }
 769     if (changed) {
 770         // In a change span, map to its end.
 771         return srcIndex + oldLength_;
 772     } else {
 773         // In an unchanged span, offset within it.
 774         return srcIndex + (i - destIndex);
 775     }
 776 }
 777
 778 UnicodeString& Edits::Iterator::toString(UnicodeString& sb) const {
 779     sb.append(u"{ src[", -1);
 780     ICU_Utility::appendNumber(sb, srcIndex);
 781     sb.append(u"..", -1);
 782     ICU_Utility::appendNumber(sb, srcIndex + oldLength_);
 783     if (changed) {
 784         sb.append(u"] ⇝ dest[", -1);
 785     } else {
 786         sb.append(u"] ≡ dest[", -1);
 787     }
 788     ICU_Utility::appendNumber(sb, destIndex);
 789     sb.append(u"..", -1);
 790     ICU_Utility::appendNumber(sb, destIndex + newLength_);
 791     if (changed) {
 792         sb.append(u"], repl[", -1);
 793         ICU_Utility::appendNumber(sb, replIndex);
 794         sb.append(u"..", -1);
 795         ICU_Utility::appendNumber(sb, replIndex + newLength_);
 796         sb.append(u"] }", -1);
 797     } else {
 798         sb.append(u"] (no-change) }", -1);
 799     }
 800     return sb;
 801 }
 802
 803 U_NAMESPACE_END