package org.unicode.bidi; import java.util.Arrays; /* * Last Revised: 2013-09-02 * * Credits: * Originally written by Doug Felt * * Updated for Unicode 6.3 by Roozbeh Pournader, with feedback by Aharon Lanin * * Updated by Asmus Freytag to implement the Paired Bracket Algorithm (PBA) * * Disclaimer and legal rights: * (C) Copyright IBM Corp. 1999, All Rights Reserved * (C) Copyright Google Inc. 2013, All Rights Reserved * (C) Copyright ASMUS, Inc. 2013. All Rights Reserved * * Distributed under the Terms of Use in http://www.unicode.org/copyright.html. */ /* * Revision info (2013-09-16) * Changed MAX_DEPTH to 125 * * Revision info (2013-06-02): *
* The core part of the Unicode Paired Bracket Algorithm (PBA) * is implemented in a new BidiPBAReference class. *
* Changed convention for default paragraph embedding level from -1 to 2. */ /** * Reference implementation of the Unicode Bidirectional Algorithm (UAX #9). * *
* This implementation is not optimized for performance. It is intended as a * reference implementation that closely follows the specification of the * Bidirectional Algorithm in The Unicode Standard version 6.3. *
* Input:
* There are two levels of input to the algorithm, since clients may prefer to
* supply some information from out-of-band sources rather than relying on the
* default behavior.
*
* Output:
* Output is separated into several stages as well, to better enable clients to
* evaluate various aspects of implementation conformance.
*
* As the algorithm is defined to operate on a single paragraph at a time, this * implementation is written to handle single paragraphs. Thus rule P1 is * presumed by this implementation-- the data provided to the implementation is * assumed to be a single paragraph, and either contains no 'B' codes, or a * single 'B' code at the end of the input. 'B' is allowed as input to * illustrate how the algorithm assigns it a level. *
* Also note that rules L3 and L4 depend on the rendering engine that uses the * result of the bidi algorithm. This implementation assumes that the rendering * engine expects combining marks in visual order (e.g. to the left of their * base character in RTL runs) and that it adjusts the glyphs used to render * mirrored characters that are in RTL runs so that they render appropriately. * * @author Doug Felt * @author Roozbeh Pournader * @author Asmus Freytag */ public final class BidiReference { private final byte[] initialTypes; public final static byte implicitEmbeddingLevel = 2; // level will be determined implicitly private byte paragraphEmbeddingLevel = implicitEmbeddingLevel; private int textLength; // for convenience private byte[] resultTypes; // for paragraph, not lines private byte[] resultLevels; // for paragraph, not lines public byte [] getResultTypes() { return resultTypes.clone(); } // for display in test mode /* * Index of matching PDI for isolate initiator characters. For other * characters, the value of matchingPDI will be set to -1. For isolate * initiators with no matching PDI, matchingPDI will be set to the length of * the input string. */ private int[] matchingPDI; /* * Index of matching isolate initiator for PDI characters. For other * characters, and for PDIs with no matching isolate initiator, the value of * matchingIsolateInitiator will be set to -1. */ private int[] matchingIsolateInitiator; /* * Arrays of properties needed for paired bracket evaluation in N0 */ private final byte[] pairTypes; // paired Bracket types for paragraph private final int[] pairValues; // paired Bracket values for paragraph public BidiPBAReference pba; // to allow access to internal pba state for diagnostics // The bidi types /** Left-to-right */ public static final byte L = 0; /** Left-to-Right Embedding */ public static final byte LRE = 1; /** Left-to-Right Override */ public static final byte LRO = 2; /** Right-to-Left */ public static final byte R = 3; /** Right-to-Left Arabic */ public static final byte AL = 4; /** Right-to-Left Embedding */ public static final byte RLE = 5; /** Right-to-Left Override */ public static final byte RLO = 6; /** Pop Directional Format */ public static final byte PDF = 7; /** European Number */ public static final byte EN = 8; /** European Number Separator */ public static final byte ES = 9; /** European Number Terminator */ public static final byte ET = 10; /** Arabic Number */ public static final byte AN = 11; /** Common Number Separator */ public static final byte CS = 12; /** Non-Spacing Mark */ public static final byte NSM = 13; /** Boundary Neutral */ public static final byte BN = 14; /** Paragraph Separator */ public static final byte B = 15; /** Segment Separator */ public static final byte S = 16; /** Whitespace */ public static final byte WS = 17; /** Other Neutrals */ public static final byte ON = 18; /** Left-to-Right Isolate */ public static final byte LRI = 19; /** Right-to-Left Isolate */ public static final byte RLI = 20; /** First-Strong Isolate */ public static final byte FSI = 21; /** Pop Directional Isolate */ public static final byte PDI = 22; /** Minimum bidi type value. */ public static final byte TYPE_MIN = 0; /** Maximum bidi type value. */ public static final byte TYPE_MAX = 22; /** Shorthand names of bidi type values, for error reporting. */ public static final String[] typenames = { "L", "LRE", "LRO", "R", "AL", "RLE", "RLO", "PDF", "EN", "ES", "ET", "AN", "CS", "NSM", "BN", "B", "S", "WS", "ON", "LRI", "RLI", "FSI", "PDI" }; // // Input // /** * Initialize using several arrays, then run the algorithm * @param types * Array of types ranging from TYPE_MIN to TYPE_MAX inclusive * and representing the direction codes of the characters in the text. * @param pairTypes * Array of paired bracket types ranging from 0 (none) to 2 (closing) * of the characters * @param pairValues * Array identifying which set of matching bracket characters * as defined in BidiPBAReference (note, both opening and closing * bracket get the same value if they are part of the same canonical "set" * or pair) */ public BidiReference(byte[] types, byte [] pairTypes, int [] pairValues) { validateTypes(types); validatePbTypes(pairTypes); validatePbValues(pairValues, pairTypes); initialTypes = types.clone(); // client type array remains unchanged this.pairTypes = pairTypes; this.pairValues = pairValues; runAlgorithm(); } /** * Initialize using several arrays of direction and other types and an externally supplied * paragraph embedding level. The embedding level may be 0, 1 or 2. *
* 2 means to apply the default algorithm (rules P2 and P3), 0 is for LTR * paragraphs, and 1 is for RTL paragraphs. * * @param types * the types array * @param pairTypes * the paired bracket types array * @param pairValues * the paired bracket values array * @param paragraphEmbeddingLevel * the externally supplied paragraph embedding level. */ public BidiReference(byte[] types, byte [] pairTypes, int [] pairValues, byte paragraphEmbeddingLevel) { validateTypes(types); validatePbTypes(pairTypes); validatePbValues(pairValues, pairTypes); validateParagraphEmbeddingLevel(paragraphEmbeddingLevel); initialTypes = types.clone(); // client type array remains unchanged this.paragraphEmbeddingLevel = paragraphEmbeddingLevel; this.pairTypes = pairTypes; this.pairValues = pairValues; runAlgorithm(); } /** * The algorithm. Does not include line-based processing (Rules L1, L2). * These are applied later in the line-based phase of the algorithm. */ private void runAlgorithm() { textLength = initialTypes.length; // Initialize output types. // Result types initialized to input types. resultTypes = initialTypes.clone(); // Preprocessing to find the matching isolates determineMatchingIsolates(); // 1) determining the paragraph level // Rule P1 is the requirement for entering this algorithm. // Rules P2, P3. // If no externally supplied paragraph embedding level, use default. if (paragraphEmbeddingLevel == implicitEmbeddingLevel) { paragraphEmbeddingLevel = determineParagraphEmbeddingLevel(0, textLength); } // Initialize result levels to paragraph embedding level. resultLevels = new byte[textLength]; setLevels(resultLevels, 0, textLength, paragraphEmbeddingLevel); // 2) Explicit levels and directions // Rules X1-X8. determineExplicitEmbeddingLevels(); // Rule X9. // We do not remove the embeddings, the overrides, the PDFs, and the BNs // from the string explicitly. But they are not copied into isolating run // sequences when they are created, so they are removed for all // practical purposes. // Rule X10. // Run remainder of algorithm one isolating run sequence at a time IsolatingRunSequence[] sequences = determineIsolatingRunSequences(); for (int i = 0; i < sequences.length; ++i) { IsolatingRunSequence sequence = sequences[i]; // 3) resolving weak types // Rules W1-W7. sequence.resolveWeakTypes(); // 4a) resolving paired brackets // Rule N0 sequence.resolvePairedBrackets(); // 4b) resolving neutral types // Rules N1-N3. sequence.resolveNeutralTypes(); // 5) resolving implicit embedding levels // Rules I1, I2. sequence.resolveImplicitLevels(); // Apply the computed levels and types sequence.applyLevelsAndTypes(); } // Assign appropriate levels to 'hide' LREs, RLEs, LROs, RLOs, PDFs, and // BNs. This is for convenience, so the resulting level array will have // a value for every character. assignLevelsToCharactersRemovedByX9(); } /** * Determine the matching PDI for each isolate initiator and vice versa. *
* Definition BD9. *
* At the end of this function: *
* The returned levels array contains the resolved level for each bidi code * passed to the constructor. *
* The linebreaks array must include at least one value. The values must be * in strictly increasing order (no duplicates) between 1 and the length of * the text, inclusive. The last value must be the length of the text. * * @param linebreaks * the offsets at which to break the paragraph * @return the resolved levels of the text */ public byte[] getLevels(int[] linebreaks) { // Note that since the previous processing has removed all // P, S, and WS values from resultTypes, the values referred to // in these rules are the initial types, before any processing // has been applied (including processing of overrides). // // This example implementation has reinserted explicit format codes // and BN, in order that the levels array correspond to the // initial text. Their final placement is not normative. // These codes are treated like WS in this implementation, // so they don't interrupt sequences of WS. validateLineBreaks(linebreaks, textLength); byte[] result = resultLevels.clone(); // will be returned to // caller // don't worry about linebreaks since if there is a break within // a series of WS values preceding S, the linebreak itself // causes the reset. for (int i = 0; i < result.length; ++i) { byte t = initialTypes[i]; if (t == B || t == S) { // Rule L1, clauses one and two. result[i] = paragraphEmbeddingLevel; // Rule L1, clause three. for (int j = i - 1; j >= 0; --j) { if (isWhitespace(initialTypes[j])) { // including format // codes result[j] = paragraphEmbeddingLevel; } else { break; } } } } // Rule L1, clause four. int start = 0; for (int i = 0; i < linebreaks.length; ++i) { int limit = linebreaks[i]; for (int j = limit - 1; j >= start; --j) { if (isWhitespace(initialTypes[j])) { // including format codes result[j] = paragraphEmbeddingLevel; } else { break; } } start = limit; } return result; } /** * Return reordering array breaking lines at offsets in linebreaks. *
* The reordering array maps from a visual index to a logical index. Lines * are concatenated from left to right. So for example, the fifth character * from the left on the third line is * *
* getReordering(linebreaks)[linebreaks[1] + 4] ** * (linebreaks[1] is the position after the last character of the second * line, which is also the index of the first character on the third line, * and adding four gets the fifth character from the left). *
* The linebreaks array must include at least one value. The values must be * in strictly increasing order (no duplicates) between 1 and the length of * the text, inclusive. The last value must be the length of the text. * * @param linebreaks * the offsets at which to break the paragraph. */ public int[] getReordering(int[] linebreaks) { validateLineBreaks(linebreaks, textLength); byte[] levels = getLevels(linebreaks); return computeMultilineReordering(levels, linebreaks); } /** * Return multiline reordering array for a given level array. Reordering * does not occur across a line break. */ private static int[] computeMultilineReordering(byte[] levels, int[] linebreaks) { int[] result = new int[levels.length]; int start = 0; for (int i = 0; i < linebreaks.length; ++i) { int limit = linebreaks[i]; byte[] templevels = new byte[limit - start]; System.arraycopy(levels, start, templevels, 0, templevels.length); int[] temporder = computeReordering(templevels); for (int j = 0; j < temporder.length; ++j) { result[start + j] = temporder[j] + start; } start = limit; } return result; } /** * Return reordering array for a given level array. This reorders a single * line. The reordering is a visual to logical map. For example, the * leftmost char is string.charAt(order[0]). Rule L2. */ private static int[] computeReordering(byte[] levels) { int lineLength = levels.length; int[] result = new int[lineLength]; // initialize order for (int i = 0; i < lineLength; ++i) { result[i] = i; } // locate highest level found on line. // Note the rules say text, but no reordering across line bounds is // performed, so this is sufficient. byte highestLevel = 0; byte lowestOddLevel = MAX_DEPTH + 2; for (int i = 0; i < lineLength; ++i) { byte level = levels[i]; if (level > highestLevel) { highestLevel = level; } if (((level & 1) != 0) && level < lowestOddLevel) { lowestOddLevel = level; } } for (int level = highestLevel; level >= lowestOddLevel; --level) { for (int i = 0; i < lineLength; ++i) { if (levels[i] >= level) { // find range of text at or above this level int start = i; int limit = i + 1; while (limit < lineLength && levels[limit] >= level) { ++limit; } // reverse run for (int j = start, k = limit - 1; j < k; ++j, --k) { int temp = result[j]; result[j] = result[k]; result[k] = temp; } // skip to end of level run i = limit; } } } return result; } /** * Return the base level of the paragraph. */ public byte getBaseLevel() { return paragraphEmbeddingLevel; } // --- internal utilities ------------------------------------------------- /** * Return true if the type is considered a whitespace type for the line * break rules. */ private static boolean isWhitespace(byte biditype) { switch (biditype) { case LRE: case RLE: case LRO: case RLO: case PDF: case LRI: case RLI: case FSI: case PDI: case BN: case WS: return true; default: return false; } } /** * Return true if the type is one of the types removed in X9. * Made public so callers can duplicate the effect. */ public static boolean isRemovedByX9(byte biditype) { switch (biditype) { case LRE: case RLE: case LRO: case RLO: case PDF: case BN: return true; default: return false; } } /** * Return the strong type (L or R) corresponding to the level. */ private static byte typeForLevel(int level) { return ((level & 0x1) == 0) ? L : R; } /** * Set levels from start up to (but not including) limit to newLevel. */ private void setLevels(byte[] levels, int start, int limit, byte newLevel) { for (int i = start; i < limit; ++i) { levels[i] = newLevel; } } // --- input validation --------------------------------------------------- /** * Throw exception if type array is invalid. */ private static void validateTypes(byte[] types) { if (types == null) { throw new IllegalArgumentException("types is null"); } for (int i = 0; i < types.length; ++i) { if (types[i] < TYPE_MIN || types[i] > TYPE_MAX) { throw new IllegalArgumentException("illegal type value at " + i + ": " + types[i]); } } for (int i = 0; i < types.length - 1; ++i) { if (types[i] == B) { throw new IllegalArgumentException("B type before end of paragraph at index: " + i); } } } /** * Throw exception if paragraph embedding level is invalid. Special * allowance for implicitEmbeddinglevel so that default processing of the * paragraph embedding level as implicit can still be performed when * using this API. */ private static void validateParagraphEmbeddingLevel(byte paragraphEmbeddingLevel) { if (paragraphEmbeddingLevel != implicitEmbeddingLevel && paragraphEmbeddingLevel != 0 && paragraphEmbeddingLevel != 1) { throw new IllegalArgumentException("illegal paragraph embedding level: " + paragraphEmbeddingLevel); } } /** * Throw exception if line breaks array is invalid. */ private static void validateLineBreaks(int[] linebreaks, int textLength) { int prev = 0; for (int i = 0; i < linebreaks.length; ++i) { int next = linebreaks[i]; if (next <= prev) { throw new IllegalArgumentException("bad linebreak: " + next + " at index: " + i); } prev = next; } if (prev != textLength) { throw new IllegalArgumentException("last linebreak must be at " + textLength); } } /** * Throw exception if pairTypes array is invalid */ private static void validatePbTypes(byte[] pairTypes) { if (pairTypes == null) { throw new IllegalArgumentException("pairTypes is null"); } for (int i = 0; i < pairTypes.length; ++i) { if (pairTypes[i] < BidiPBAReference.n || pairTypes[i] > BidiPBAReference.c) { throw new IllegalArgumentException("illegal pairType value at " + i + ": " + pairTypes[i]); } } } /** * Throw exception if pairValues array is invalid or doesn't match pairTypes in length * Unfortunately there's little we can do in terms of validating the values themselves */ private static void validatePbValues(int[] pairValues, byte[] pairTypes) { if (pairValues == null) { throw new IllegalArgumentException("pairValues is null"); } if (pairTypes.length != pairValues.length) { throw new IllegalArgumentException("pairTypes is different length from pairValues"); } } /** * static entry point for testing using several arrays of direction and other types and an externally supplied * paragraph embedding level. The embedding level may be 0, 1 or 2. *
* 2 means to apply the default algorithm (rules P2 and P3), 0 is for LTR * paragraphs, and 1 is for RTL paragraphs. * * @param types * the directional types array * @param pairTypes * the paired bracket types array * @param pairValues * the paired bracket values array * @param paragraphEmbeddingLevel * the externally supplied paragraph embedding level. */ public static final BidiReference analyzeInput(byte[] types, byte [] pairTypes, int [] pairValues, byte paragraphEmbeddingLevel) { BidiReference bidi = new BidiReference(types, pairTypes, pairValues, paragraphEmbeddingLevel); return bidi; } }