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
14U_NAMESPACE_BEGIN
15
16namespace {
17
18// 0000uuuuuuuuuuuu records u+1 unchanged text units.
19const int32_t MAX_UNCHANGED_LENGTH = 0x1000;
20const int32_t MAX_UNCHANGED = MAX_UNCHANGED_LENGTH - 1;
21
22// 0mmmnnnccccccccc with m=1..6 records ccc+1 replacements of m:n text units.
23const int32_t MAX_SHORT_CHANGE_OLD_LENGTH = 6;
24const int32_t MAX_SHORT_CHANGE_NEW_LENGTH = 7;
25const int32_t SHORT_CHANGE_NUM_MASK = 0x1ff;
26const 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.
33const int32_t LENGTH_IN_1TRAIL = 61;
34const int32_t LENGTH_IN_2TRAIL = 62;
35
36} // namespace
37
38void Edits::releaseArray() U_NOEXCEPT {
39 if (array != stackArray) {
40 uprv_free(array);
41 }
42}
43
44Edits &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
66Edits &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
88Edits &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
96Edits &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
104Edits::~Edits() {
105 releaseArray();
106}
107
108void Edits::reset() U_NOEXCEPT {
109 length = delta = numChanges = 0;
110 errorCode_ = U_ZERO_ERROR;
111}
112
113void 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
141void 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
209void Edits::append(int32_t r) {
210 if(length < capacity || growArray()) {
211 array[length++] = (uint16_t)r;
212 }
213}
214
215UBool 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
246UBool Edits::copyErrorTo(UErrorCode &outErrorCode) const {
247 if (U_FAILURE(outErrorCode)) { return TRUE; }
248 if (U_SUCCESS(errorCode_)) { return FALSE; }
249 outErrorCode = errorCode_;
250 return TRUE;
251}
252
253Edits &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
399Edits::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
405int32_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
424void Edits::Iterator::updateNextIndexes() {
425 srcIndex += oldLength_;
426 if (changed) {
427 replIndex += newLength_;
428 }
429 destIndex += newLength_;
430}
431
432void Edits::Iterator::updatePreviousIndexes() {
433 srcIndex -= oldLength_;
434 if (changed) {
435 replIndex -= newLength_;
436 }
437 destIndex -= newLength_;
438}
439
440UBool 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
448UBool 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
544UBool 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
653int32_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
740int32_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
759int32_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
778UnicodeString& 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
803U_NAMESPACE_END
804