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