icuSources/common/unicode/edits.h

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3
   4 // edits.h
   5 // created: 2016dec30 Markus W. Scherer
   6
   7 #ifndef __EDITS_H__
   8 #define __EDITS_H__
   9
  10 #include "unicode/utypes.h"
  11 #include "unicode/uobject.h"
  12
  13 /**
  14  * \file
  15  * \brief C++ API: C++ class Edits for low-level string transformations on styled text.
  16  */
  17
  18 #if U_SHOW_CPLUSPLUS_API
  19 U_NAMESPACE_BEGIN
  20
  21 class UnicodeString;
  22
  23 /**
  24  * Records lengths of string edits but not replacement text. Supports replacements, insertions, deletions
  25  * in linear progression. Does not support moving/reordering of text.
  26  *
  27  * There are two types of edits: <em>change edits</em> and <em>no-change edits</em>. Add edits to
  28  * instances of this class using {@link #addReplace(int32_t, int32_t)} (for change edits) and
  29  * {@link #addUnchanged(int32_t)} (for no-change edits). Change edits are retained with full granularity,
  30  * whereas adjacent no-change edits are always merged together. In no-change edits, there is a one-to-one
  31  * mapping between code points in the source and destination strings.
  32  *
  33  * After all edits have been added, instances of this class should be considered immutable, and an
  34  * {@link Edits::Iterator} can be used for queries.
  35  *
  36  * There are four flavors of Edits::Iterator:
  37  *
  38  * <ul>
  39  * <li>{@link #getFineIterator()} retains full granularity of change edits.
  40  * <li>{@link #getFineChangesIterator()} retains full granularity of change edits, and when calling
  41  * next() on the iterator, skips over no-change edits (unchanged regions).
  42  * <li>{@link #getCoarseIterator()} treats adjacent change edits as a single edit. (Adjacent no-change
  43  * edits are automatically merged during the construction phase.)
  44  * <li>{@link #getCoarseChangesIterator()} treats adjacent change edits as a single edit, and when
  45  * calling next() on the iterator, skips over no-change edits (unchanged regions).
  46  * </ul>
  47  *
  48  * For example, consider the string "abcßDeF", which case-folds to "abcssdef". This string has the
  49  * following fine edits:
  50  * <ul>
  51  * <li>abc ⇨ abc (no-change)
  52  * <li>ß ⇨ ss (change)
  53  * <li>D ⇨ d (change)
  54  * <li>e ⇨ e (no-change)
  55  * <li>F ⇨ f (change)
  56  * </ul>
  57  * and the following coarse edits (note how adjacent change edits get merged together):
  58  * <ul>
  59  * <li>abc ⇨ abc (no-change)
  60  * <li>ßD ⇨ ssd (change)
  61  * <li>e ⇨ e (no-change)
  62  * <li>F ⇨ f (change)
  63  * </ul>
  64  *
  65  * The "fine changes" and "coarse changes" iterators will step through only the change edits when their
  66  * `Edits::Iterator::next()` methods are called. They are identical to the non-change iterators when
  67  * their `Edits::Iterator::findSourceIndex()` or `Edits::Iterator::findDestinationIndex()`
  68  * methods are used to walk through the string.
  69  *
  70  * For examples of how to use this class, see the test `TestCaseMapEditsIteratorDocs` in
  71  * UCharacterCaseTest.java.
  72  *
  73  * An Edits object tracks a separate UErrorCode, but ICU string transformation functions
  74  * (e.g., case mapping functions) merge any such errors into their API's UErrorCode.
  75  *
  76  * @stable ICU 59
  77  */
  78 class U_COMMON_API Edits U_FINAL : public UMemory {
  79 public:
  80     /**
  81      * Constructs an empty object.
  82      * @stable ICU 59
  83      */
  84     Edits() :
  85             array(stackArray), capacity(STACK_CAPACITY), length(0), delta(0), numChanges(0),
  86             errorCode_(U_ZERO_ERROR) {}
  87     /**
  88      * Copy constructor.
  89      * @param other source edits
  90      * @stable ICU 60
  91      */
  92     Edits(const Edits &other) :
  93             array(stackArray), capacity(STACK_CAPACITY), length(other.length),
  94             delta(other.delta), numChanges(other.numChanges),
  95             errorCode_(other.errorCode_) {
  96         copyArray(other);
  97     }
  98     /**
  99      * Move constructor, might leave src empty.
 100      * This object will have the same contents that the source object had.
 101      * @param src source edits
 102      * @stable ICU 60
 103      */
 104     Edits(Edits &&src) U_NOEXCEPT :
 105             array(stackArray), capacity(STACK_CAPACITY), length(src.length),
 106             delta(src.delta), numChanges(src.numChanges),
 107             errorCode_(src.errorCode_) {
 108         moveArray(src);
 109     }
 110
 111     /**
 112      * Destructor.
 113      * @stable ICU 59
 114      */
 115     ~Edits();
 116
 117     /**
 118      * Assignment operator.
 119      * @param other source edits
 120      * @return *this
 121      * @stable ICU 60
 122      */
 123     Edits &operator=(const Edits &other);
 124
 125     /**
 126      * Move assignment operator, might leave src empty.
 127      * This object will have the same contents that the source object had.
 128      * The behavior is undefined if *this and src are the same object.
 129      * @param src source edits
 130      * @return *this
 131      * @stable ICU 60
 132      */
 133     Edits &operator=(Edits &&src) U_NOEXCEPT;
 134
 135     /**
 136      * Resets the data but may not release memory.
 137      * @stable ICU 59
 138      */
 139     void reset() U_NOEXCEPT;
 140
 141     /**
 142      * Adds a no-change edit: a record for an unchanged segment of text.
 143      * Normally called from inside ICU string transformation functions, not user code.
 144      * @stable ICU 59
 145      */
 146     void addUnchanged(int32_t unchangedLength);
 147     /**
 148      * Adds a change edit: a record for a text replacement/insertion/deletion.
 149      * Normally called from inside ICU string transformation functions, not user code.
 150      * @stable ICU 59
 151      */
 152     void addReplace(int32_t oldLength, int32_t newLength);
 153     /**
 154      * Sets the UErrorCode if an error occurred while recording edits.
 155      * Preserves older error codes in the outErrorCode.
 156      * Normally called from inside ICU string transformation functions, not user code.
 157      * @param outErrorCode Set to an error code if it does not contain one already
 158      *                  and an error occurred while recording edits.
 159      *                  Otherwise unchanged.
 160      * @return TRUE if U_FAILURE(outErrorCode)
 161      * @stable ICU 59
 162      */
 163     UBool copyErrorTo(UErrorCode &outErrorCode);
 164
 165     /**
 166      * How much longer is the new text compared with the old text?
 167      * @return new length minus old length
 168      * @stable ICU 59
 169      */
 170     int32_t lengthDelta() const { return delta; }
 171     /**
 172      * @return TRUE if there are any change edits
 173      * @stable ICU 59
 174      */
 175     UBool hasChanges() const { return numChanges != 0; }
 176
 177     /**
 178      * @return the number of change edits
 179      * @stable ICU 60
 180      */
 181     int32_t numberOfChanges() const { return numChanges; }
 182
 183     /**
 184      * Access to the list of edits.
 185      *
 186      * At any moment in time, an instance of this class points to a single edit: a "window" into a span
 187      * of the source string and the corresponding span of the destination string. The source string span
 188      * starts at {@link #sourceIndex()} and runs for {@link #oldLength()} chars; the destination string
 189      * span starts at {@link #destinationIndex()} and runs for {@link #newLength()} chars.
 190      *
 191      * The iterator can be moved between edits using the `next()`, `findSourceIndex(int32_t, UErrorCode &)`,
 192      * and `findDestinationIndex(int32_t, UErrorCode &)` methods.
 193      * Calling any of these methods mutates the iterator to make it point to the corresponding edit.
 194      *
 195      * For more information, see the documentation for {@link Edits}.
 196      *
 197      * @see getCoarseIterator
 198      * @see getFineIterator
 199      * @stable ICU 59
 200      */
 201     struct U_COMMON_API Iterator U_FINAL : public UMemory {
 202         /**
 203          * Default constructor, empty iterator.
 204          * @stable ICU 60
 205          */
 206         Iterator() :
 207                 array(nullptr), index(0), length(0),
 208                 remaining(0), onlyChanges_(FALSE), coarse(FALSE),
 209                 dir(0), changed(FALSE), oldLength_(0), newLength_(0),
 210                 srcIndex(0), replIndex(0), destIndex(0) {}
 211         /**
 212          * Copy constructor.
 213          * @stable ICU 59
 214          */
 215         Iterator(const Iterator &other) = default;
 216         /**
 217          * Assignment operator.
 218          * @stable ICU 59
 219          */
 220         Iterator &operator=(const Iterator &other) = default;
 221
 222         /**
 223          * Advances the iterator to the next edit.
 224          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
 225          *                  or else the function returns immediately. Check for U_FAILURE()
 226          *                  on output or use with function chaining. (See User Guide for details.)
 227          * @return TRUE if there is another edit
 228          * @stable ICU 59
 229          */
 230         UBool next(UErrorCode &errorCode) { return next(onlyChanges_, errorCode); }
 231
 232         /**
 233          * Moves the iterator to the edit that contains the source index.
 234          * The source index may be found in a no-change edit
 235          * even if normal iteration would skip no-change edits.
 236          * Normal iteration can continue from a found edit.
 237          *
 238          * The iterator state before this search logically does not matter.
 239          * (It may affect the performance of the search.)
 240          *
 241          * The iterator state after this search is undefined
 242          * if the source index is out of bounds for the source string.
 243          *
 244          * @param i source index
 245          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
 246          *                  or else the function returns immediately. Check for U_FAILURE()
 247          *                  on output or use with function chaining. (See User Guide for details.)
 248          * @return TRUE if the edit for the source index was found
 249          * @stable ICU 59
 250          */
 251         UBool findSourceIndex(int32_t i, UErrorCode &errorCode) {
 252             return findIndex(i, TRUE, errorCode) == 0;
 253         }
 254
 255         /**
 256          * Moves the iterator to the edit that contains the destination index.
 257          * The destination index may be found in a no-change edit
 258          * even if normal iteration would skip no-change edits.
 259          * Normal iteration can continue from a found edit.
 260          *
 261          * The iterator state before this search logically does not matter.
 262          * (It may affect the performance of the search.)
 263          *
 264          * The iterator state after this search is undefined
 265          * if the source index is out of bounds for the source string.
 266          *
 267          * @param i destination index
 268          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
 269          *                  or else the function returns immediately. Check for U_FAILURE()
 270          *                  on output or use with function chaining. (See User Guide for details.)
 271          * @return TRUE if the edit for the destination index was found
 272          * @stable ICU 60
 273          */
 274         UBool findDestinationIndex(int32_t i, UErrorCode &errorCode) {
 275             return findIndex(i, FALSE, errorCode) == 0;
 276         }
 277
 278         /**
 279          * Computes the destination index corresponding to the given source index.
 280          * If the source index is inside a change edit (not at its start),
 281          * then the destination index at the end of that edit is returned,
 282          * since there is no information about index mapping inside a change edit.
 283          *
 284          * (This means that indexes to the start and middle of an edit,
 285          * for example around a grapheme cluster, are mapped to indexes
 286          * encompassing the entire edit.
 287          * The alternative, mapping an interior index to the start,
 288          * would map such an interval to an empty one.)
 289          *
 290          * This operation will usually but not always modify this object.
 291          * The iterator state after this search is undefined.
 292          *
 293          * @param i source index
 294          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
 295          *                  or else the function returns immediately. Check for U_FAILURE()
 296          *                  on output or use with function chaining. (See User Guide for details.)
 297          * @return destination index; undefined if i is not 0..string length
 298          * @stable ICU 60
 299          */
 300         int32_t destinationIndexFromSourceIndex(int32_t i, UErrorCode &errorCode);
 301
 302         /**
 303          * Computes the source index corresponding to the given destination index.
 304          * If the destination index is inside a change edit (not at its start),
 305          * then the source index at the end of that edit is returned,
 306          * since there is no information about index mapping inside a change edit.
 307          *
 308          * (This means that indexes to the start and middle of an edit,
 309          * for example around a grapheme cluster, are mapped to indexes
 310          * encompassing the entire edit.
 311          * The alternative, mapping an interior index to the start,
 312          * would map such an interval to an empty one.)
 313          *
 314          * This operation will usually but not always modify this object.
 315          * The iterator state after this search is undefined.
 316          *
 317          * @param i destination index
 318          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
 319          *                  or else the function returns immediately. Check for U_FAILURE()
 320          *                  on output or use with function chaining. (See User Guide for details.)
 321          * @return source index; undefined if i is not 0..string length
 322          * @stable ICU 60
 323          */
 324         int32_t sourceIndexFromDestinationIndex(int32_t i, UErrorCode &errorCode);
 325
 326         /**
 327          * Returns whether the edit currently represented by the iterator is a change edit.
 328          *
 329          * @return TRUE if this edit replaces oldLength() units with newLength() different ones.
 330          *         FALSE if oldLength units remain unchanged.
 331          * @stable ICU 59
 332          */
 333         UBool hasChange() const { return changed; }
 334
 335         /**
 336          * The length of the current span in the source string, which starts at {@link #sourceIndex}.
 337          *
 338          * @return the number of units in the original string which are replaced or remain unchanged.
 339          * @stable ICU 59
 340          */
 341         int32_t oldLength() const { return oldLength_; }
 342
 343         /**
 344          * The length of the current span in the destination string, which starts at
 345          * {@link #destinationIndex}, or in the replacement string, which starts at
 346          * {@link #replacementIndex}.
 347          *
 348          * @return the number of units in the modified string, if hasChange() is TRUE.
 349          *         Same as oldLength if hasChange() is FALSE.
 350          * @stable ICU 59
 351          */
 352         int32_t newLength() const { return newLength_; }
 353
 354         /**
 355          * The start index of the current span in the source string; the span has length
 356          * {@link #oldLength}.
 357          *
 358          * @return the current index into the source string
 359          * @stable ICU 59
 360          */
 361         int32_t sourceIndex() const { return srcIndex; }
 362
 363         /**
 364          * The start index of the current span in the replacement string; the span has length
 365          * {@link #newLength}. Well-defined only if the current edit is a change edit.
 366          *
 367          * The *replacement string* is the concatenation of all substrings of the destination
 368          * string corresponding to change edits.
 369          *
 370          * This method is intended to be used together with operations that write only replacement
 371          * characters (e.g. operations specifying the \ref U_OMIT_UNCHANGED_TEXT option).
 372          * The source string can then be modified in-place.
 373          *
 374          * @return the current index into the replacement-characters-only string,
 375          *         not counting unchanged spans
 376          * @stable ICU 59
 377          */
 378         int32_t replacementIndex() const {
 379             // TODO: Throw an exception if we aren't in a change edit?
 380             return replIndex;
 381         }
 382
 383         /**
 384          * The start index of the current span in the destination string; the span has length
 385          * {@link #newLength}.
 386          *
 387          * @return the current index into the full destination string
 388          * @stable ICU 59
 389          */
 390         int32_t destinationIndex() const { return destIndex; }
 391
 392 #ifndef U_HIDE_INTERNAL_API
 393         /**
 394          * A string representation of the current edit represented by the iterator for debugging. You
 395          * should not depend on the contents of the return string.
 396          * @internal
 397          */
 398         UnicodeString& toString(UnicodeString& appendTo) const;
 399 #endif  // U_HIDE_INTERNAL_API
 400
 401     private:
 402         friend class Edits;
 403
 404         Iterator(const uint16_t *a, int32_t len, UBool oc, UBool crs);
 405
 406         int32_t readLength(int32_t head);
 407         void updateNextIndexes();
 408         void updatePreviousIndexes();
 409         UBool noNext();
 410         UBool next(UBool onlyChanges, UErrorCode &errorCode);
 411         UBool previous(UErrorCode &errorCode);
 412         /** @return -1: error or i<0; 0: found; 1: i>=string length */
 413         int32_t findIndex(int32_t i, UBool findSource, UErrorCode &errorCode);
 414
 415         const uint16_t *array;
 416         int32_t index, length;
 417         // 0 if we are not within compressed equal-length changes.
 418         // Otherwise the number of remaining changes, including the current one.
 419         int32_t remaining;
 420         UBool onlyChanges_, coarse;
 421
 422         int8_t dir;  // iteration direction: back(<0), initial(0), forward(>0)
 423         UBool changed;
 424         int32_t oldLength_, newLength_;
 425         int32_t srcIndex, replIndex, destIndex;
 426     };
 427
 428     /**
 429      * Returns an Iterator for coarse-grained change edits
 430      * (adjacent change edits are treated as one).
 431      * Can be used to perform simple string updates.
 432      * Skips no-change edits.
 433      * @return an Iterator that merges adjacent changes.
 434      * @stable ICU 59
 435      */
 436     Iterator getCoarseChangesIterator() const {
 437         return Iterator(array, length, TRUE, TRUE);
 438     }
 439
 440     /**
 441      * Returns an Iterator for coarse-grained change and no-change edits
 442      * (adjacent change edits are treated as one).
 443      * Can be used to perform simple string updates.
 444      * Adjacent change edits are treated as one edit.
 445      * @return an Iterator that merges adjacent changes.
 446      * @stable ICU 59
 447      */
 448     Iterator getCoarseIterator() const {
 449         return Iterator(array, length, FALSE, TRUE);
 450     }
 451
 452     /**
 453      * Returns an Iterator for fine-grained change edits
 454      * (full granularity of change edits is retained).
 455      * Can be used for modifying styled text.
 456      * Skips no-change edits.
 457      * @return an Iterator that separates adjacent changes.
 458      * @stable ICU 59
 459      */
 460     Iterator getFineChangesIterator() const {
 461         return Iterator(array, length, TRUE, FALSE);
 462     }
 463
 464     /**
 465      * Returns an Iterator for fine-grained change and no-change edits
 466      * (full granularity of change edits is retained).
 467      * Can be used for modifying styled text.
 468      * @return an Iterator that separates adjacent changes.
 469      * @stable ICU 59
 470      */
 471     Iterator getFineIterator() const {
 472         return Iterator(array, length, FALSE, FALSE);
 473     }
 474
 475     /**
 476      * Merges the two input Edits and appends the result to this object.
 477      *
 478      * Consider two string transformations (for example, normalization and case mapping)
 479      * where each records Edits in addition to writing an output string.<br>
 480      * Edits ab reflect how substrings of input string a
 481      * map to substrings of intermediate string b.<br>
 482      * Edits bc reflect how substrings of intermediate string b
 483      * map to substrings of output string c.<br>
 484      * This function merges ab and bc such that the additional edits
 485      * recorded in this object reflect how substrings of input string a
 486      * map to substrings of output string c.
 487      *
 488      * If unrelated Edits are passed in where the output string of the first
 489      * has a different length than the input string of the second,
 490      * then a U_ILLEGAL_ARGUMENT_ERROR is reported.
 491      *
 492      * @param ab reflects how substrings of input string a
 493      *     map to substrings of intermediate string b.
 494      * @param bc reflects how substrings of intermediate string b
 495      *     map to substrings of output string c.
 496      * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
 497      *                  or else the function returns immediately. Check for U_FAILURE()
 498      *                  on output or use with function chaining. (See User Guide for details.)
 499      * @return *this, with the merged edits appended
 500      * @stable ICU 60
 501      */
 502     Edits &mergeAndAppend(const Edits &ab, const Edits &bc, UErrorCode &errorCode);
 503
 504 private:
 505     void releaseArray() U_NOEXCEPT;
 506     Edits &copyArray(const Edits &other);
 507     Edits &moveArray(Edits &src) U_NOEXCEPT;
 508
 509     void setLastUnit(int32_t last) { array[length - 1] = (uint16_t)last; }
 510     int32_t lastUnit() const { return length > 0 ? array[length - 1] : 0xffff; }
 511
 512     void append(int32_t r);
 513     UBool growArray();
 514
 515     static const int32_t STACK_CAPACITY = 100;
 516     uint16_t *array;
 517     int32_t capacity;
 518     int32_t length;
 519     int32_t delta;
 520     int32_t numChanges;
 521     UErrorCode errorCode_;
 522     uint16_t stackArray[STACK_CAPACITY];
 523 };
 524
 525 U_NAMESPACE_END
 526 #endif // U_SHOW_CPLUSPLUS_API
 527
 528 #endif  // __EDITS_H__