--- /dev/null
+// Copyright 2015 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package bidi
+
+import "log"
+
+// This implementation is a port based on the reference implementation found at:
+// https://www.unicode.org/Public/PROGRAMS/BidiReferenceJava/
+//
+// described in Unicode Bidirectional Algorithm (UAX #9).
+//
+// 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.
+//
+// - Bidi class array
+// - Bidi class array, with externally supplied base line direction
+//
+// Output:
+// Output is separated into several stages:
+//
+// - levels array over entire paragraph
+// - reordering array over entire paragraph
+// - levels array over line
+// - reordering array over line
+//
+// Note that for conformance to the Unicode Bidirectional Algorithm,
+// implementations are only required to generate correct reordering and
+// character directionality (odd or even levels) over a line. Generating
+// identical level arrays over a line is not required. Bidi explicit format
+// codes (LRE, RLE, LRO, RLO, PDF) and BN can be assigned arbitrary levels and
+// positions as long as the rest of the input is properly reordered.
+//
+// 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.
+
+// level is the embedding level of a character. Even embedding levels indicate
+// left-to-right order and odd levels indicate right-to-left order. The special
+// level of -1 is reserved for undefined order.
+type level int8
+
+const implicitLevel level = -1
+
+// in returns if x is equal to any of the values in set.
+func (c Class) in(set ...Class) bool {
+ for _, s := range set {
+ if c == s {
+ return true
+ }
+ }
+ return false
+}
+
+// A paragraph contains the state of a paragraph.
+type paragraph struct {
+ initialTypes []Class
+
+ // Arrays of properties needed for paired bracket evaluation in N0
+ pairTypes []bracketType // paired Bracket types for paragraph
+ pairValues []rune // rune for opening bracket or pbOpen and pbClose; 0 for pbNone
+
+ embeddingLevel level // default: = implicitLevel;
+
+ // at the paragraph levels
+ resultTypes []Class
+ resultLevels []level
+
+ // 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.
+ matchingPDI []int
+
+ // 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.
+ matchingIsolateInitiator []int
+}
+
+// newParagraph initializes a paragraph. The user needs to supply a few arrays
+// corresponding to the preprocessed text input. The types correspond to the
+// Unicode BiDi classes for each rune. pairTypes indicates the bracket type for
+// each rune. pairValues provides a unique bracket class identifier for each
+// rune (suggested is the rune of the open bracket for opening and matching
+// close brackets, after normalization). The embedding levels are optional, but
+// may be supplied to encode embedding levels of styled text.
+//
+// TODO: return an error.
+func newParagraph(types []Class, pairTypes []bracketType, pairValues []rune, levels level) *paragraph {
+ validateTypes(types)
+ validatePbTypes(pairTypes)
+ validatePbValues(pairValues, pairTypes)
+ validateParagraphEmbeddingLevel(levels)
+
+ p := ¶graph{
+ initialTypes: append([]Class(nil), types...),
+ embeddingLevel: levels,
+
+ pairTypes: pairTypes,
+ pairValues: pairValues,
+
+ resultTypes: append([]Class(nil), types...),
+ }
+ p.run()
+ return p
+}
+
+func (p *paragraph) Len() int { return len(p.initialTypes) }
+
+// The algorithm. Does not include line-based processing (Rules L1, L2).
+// These are applied later in the line-based phase of the algorithm.
+func (p *paragraph) run() {
+ p.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 p.embeddingLevel == implicitLevel {
+ p.embeddingLevel = p.determineParagraphEmbeddingLevel(0, p.Len())
+ }
+
+ // Initialize result levels to paragraph embedding level.
+ p.resultLevels = make([]level, p.Len())
+ setLevels(p.resultLevels, p.embeddingLevel)
+
+ // 2) Explicit levels and directions
+ // Rules X1-X8.
+ p.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
+ for _, seq := range p.determineIsolatingRunSequences() {
+ // 3) resolving weak types
+ // Rules W1-W7.
+ seq.resolveWeakTypes()
+
+ // 4a) resolving paired brackets
+ // Rule N0
+ resolvePairedBrackets(seq)
+
+ // 4b) resolving neutral types
+ // Rules N1-N3.
+ seq.resolveNeutralTypes()
+
+ // 5) resolving implicit embedding levels
+ // Rules I1, I2.
+ seq.resolveImplicitLevels()
+
+ // Apply the computed levels and types
+ seq.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.
+ p.assignLevelsToCharactersRemovedByX9()
+}
+
+// determineMatchingIsolates determines the matching PDI for each isolate
+// initiator and vice versa.
+//
+// Definition BD9.
+//
+// At the end of this function:
+//
+// - The member variable matchingPDI is set to point to the index of the
+// matching PDI character for each isolate initiator character. If there is
+// no matching PDI, it is set to the length of the input text. For other
+// characters, it is set to -1.
+// - The member variable matchingIsolateInitiator is set to point to the
+// index of the matching isolate initiator character for each PDI character.
+// If there is no matching isolate initiator, or the character is not a PDI,
+// it is set to -1.
+func (p *paragraph) determineMatchingIsolates() {
+ p.matchingPDI = make([]int, p.Len())
+ p.matchingIsolateInitiator = make([]int, p.Len())
+
+ for i := range p.matchingIsolateInitiator {
+ p.matchingIsolateInitiator[i] = -1
+ }
+
+ for i := range p.matchingPDI {
+ p.matchingPDI[i] = -1
+
+ if t := p.resultTypes[i]; t.in(LRI, RLI, FSI) {
+ depthCounter := 1
+ for j := i + 1; j < p.Len(); j++ {
+ if u := p.resultTypes[j]; u.in(LRI, RLI, FSI) {
+ depthCounter++
+ } else if u == PDI {
+ if depthCounter--; depthCounter == 0 {
+ p.matchingPDI[i] = j
+ p.matchingIsolateInitiator[j] = i
+ break
+ }
+ }
+ }
+ if p.matchingPDI[i] == -1 {
+ p.matchingPDI[i] = p.Len()
+ }
+ }
+ }
+}
+
+// determineParagraphEmbeddingLevel reports the resolved paragraph direction of
+// the substring limited by the given range [start, end).
+//
+// Determines the paragraph level based on rules P2, P3. This is also used
+// in rule X5c to find if an FSI should resolve to LRI or RLI.
+func (p *paragraph) determineParagraphEmbeddingLevel(start, end int) level {
+ var strongType Class = unknownClass
+
+ // Rule P2.
+ for i := start; i < end; i++ {
+ if t := p.resultTypes[i]; t.in(L, AL, R) {
+ strongType = t
+ break
+ } else if t.in(FSI, LRI, RLI) {
+ i = p.matchingPDI[i] // skip over to the matching PDI
+ if i > end {
+ log.Panic("assert (i <= end)")
+ }
+ }
+ }
+ // Rule P3.
+ switch strongType {
+ case unknownClass: // none found
+ // default embedding level when no strong types found is 0.
+ return 0
+ case L:
+ return 0
+ default: // AL, R
+ return 1
+ }
+}
+
+const maxDepth = 125
+
+// This stack will store the embedding levels and override and isolated
+// statuses
+type directionalStatusStack struct {
+ stackCounter int
+ embeddingLevelStack [maxDepth + 1]level
+ overrideStatusStack [maxDepth + 1]Class
+ isolateStatusStack [maxDepth + 1]bool
+}
+
+func (s *directionalStatusStack) empty() { s.stackCounter = 0 }
+func (s *directionalStatusStack) pop() { s.stackCounter-- }
+func (s *directionalStatusStack) depth() int { return s.stackCounter }
+
+func (s *directionalStatusStack) push(level level, overrideStatus Class, isolateStatus bool) {
+ s.embeddingLevelStack[s.stackCounter] = level
+ s.overrideStatusStack[s.stackCounter] = overrideStatus
+ s.isolateStatusStack[s.stackCounter] = isolateStatus
+ s.stackCounter++
+}
+
+func (s *directionalStatusStack) lastEmbeddingLevel() level {
+ return s.embeddingLevelStack[s.stackCounter-1]
+}
+
+func (s *directionalStatusStack) lastDirectionalOverrideStatus() Class {
+ return s.overrideStatusStack[s.stackCounter-1]
+}
+
+func (s *directionalStatusStack) lastDirectionalIsolateStatus() bool {
+ return s.isolateStatusStack[s.stackCounter-1]
+}
+
+// Determine explicit levels using rules X1 - X8
+func (p *paragraph) determineExplicitEmbeddingLevels() {
+ var stack directionalStatusStack
+ var overflowIsolateCount, overflowEmbeddingCount, validIsolateCount int
+
+ // Rule X1.
+ stack.push(p.embeddingLevel, ON, false)
+
+ for i, t := range p.resultTypes {
+ // Rules X2, X3, X4, X5, X5a, X5b, X5c
+ switch t {
+ case RLE, LRE, RLO, LRO, RLI, LRI, FSI:
+ isIsolate := t.in(RLI, LRI, FSI)
+ isRTL := t.in(RLE, RLO, RLI)
+
+ // override if this is an FSI that resolves to RLI
+ if t == FSI {
+ isRTL = (p.determineParagraphEmbeddingLevel(i+1, p.matchingPDI[i]) == 1)
+ }
+ if isIsolate {
+ p.resultLevels[i] = stack.lastEmbeddingLevel()
+ if stack.lastDirectionalOverrideStatus() != ON {
+ p.resultTypes[i] = stack.lastDirectionalOverrideStatus()
+ }
+ }
+
+ var newLevel level
+ if isRTL {
+ // least greater odd
+ newLevel = (stack.lastEmbeddingLevel() + 1) | 1
+ } else {
+ // least greater even
+ newLevel = (stack.lastEmbeddingLevel() + 2) &^ 1
+ }
+
+ if newLevel <= maxDepth && overflowIsolateCount == 0 && overflowEmbeddingCount == 0 {
+ if isIsolate {
+ validIsolateCount++
+ }
+ // Push new embedding level, override status, and isolated
+ // status.
+ // No check for valid stack counter, since the level check
+ // suffices.
+ switch t {
+ case LRO:
+ stack.push(newLevel, L, isIsolate)
+ case RLO:
+ stack.push(newLevel, R, isIsolate)
+ default:
+ stack.push(newLevel, ON, isIsolate)
+ }
+ // Not really part of the spec
+ if !isIsolate {
+ p.resultLevels[i] = newLevel
+ }
+ } else {
+ // This is an invalid explicit formatting character,
+ // so apply the "Otherwise" part of rules X2-X5b.
+ if isIsolate {
+ overflowIsolateCount++
+ } else { // !isIsolate
+ if overflowIsolateCount == 0 {
+ overflowEmbeddingCount++
+ }
+ }
+ }
+
+ // Rule X6a
+ case PDI:
+ if overflowIsolateCount > 0 {
+ overflowIsolateCount--
+ } else if validIsolateCount == 0 {
+ // do nothing
+ } else {
+ overflowEmbeddingCount = 0
+ for !stack.lastDirectionalIsolateStatus() {
+ stack.pop()
+ }
+ stack.pop()
+ validIsolateCount--
+ }
+ p.resultLevels[i] = stack.lastEmbeddingLevel()
+
+ // Rule X7
+ case PDF:
+ // Not really part of the spec
+ p.resultLevels[i] = stack.lastEmbeddingLevel()
+
+ if overflowIsolateCount > 0 {
+ // do nothing
+ } else if overflowEmbeddingCount > 0 {
+ overflowEmbeddingCount--
+ } else if !stack.lastDirectionalIsolateStatus() && stack.depth() >= 2 {
+ stack.pop()
+ }
+
+ case B: // paragraph separator.
+ // Rule X8.
+
+ // These values are reset for clarity, in this implementation B
+ // can only occur as the last code in the array.
+ stack.empty()
+ overflowIsolateCount = 0
+ overflowEmbeddingCount = 0
+ validIsolateCount = 0
+ p.resultLevels[i] = p.embeddingLevel
+
+ default:
+ p.resultLevels[i] = stack.lastEmbeddingLevel()
+ if stack.lastDirectionalOverrideStatus() != ON {
+ p.resultTypes[i] = stack.lastDirectionalOverrideStatus()
+ }
+ }
+ }
+}
+
+type isolatingRunSequence struct {
+ p *paragraph
+
+ indexes []int // indexes to the original string
+
+ types []Class // type of each character using the index
+ resolvedLevels []level // resolved levels after application of rules
+ level level
+ sos, eos Class
+}
+
+func (i *isolatingRunSequence) Len() int { return len(i.indexes) }
+
+func maxLevel(a, b level) level {
+ if a > b {
+ return a
+ }
+ return b
+}
+
+// Rule X10, second bullet: Determine the start-of-sequence (sos) and end-of-sequence (eos) types,
+// either L or R, for each isolating run sequence.
+func (p *paragraph) isolatingRunSequence(indexes []int) *isolatingRunSequence {
+ length := len(indexes)
+ types := make([]Class, length)
+ for i, x := range indexes {
+ types[i] = p.resultTypes[x]
+ }
+
+ // assign level, sos and eos
+ prevChar := indexes[0] - 1
+ for prevChar >= 0 && isRemovedByX9(p.initialTypes[prevChar]) {
+ prevChar--
+ }
+ prevLevel := p.embeddingLevel
+ if prevChar >= 0 {
+ prevLevel = p.resultLevels[prevChar]
+ }
+
+ var succLevel level
+ lastType := types[length-1]
+ if lastType.in(LRI, RLI, FSI) {
+ succLevel = p.embeddingLevel
+ } else {
+ // the first character after the end of run sequence
+ limit := indexes[length-1] + 1
+ for ; limit < p.Len() && isRemovedByX9(p.initialTypes[limit]); limit++ {
+
+ }
+ succLevel = p.embeddingLevel
+ if limit < p.Len() {
+ succLevel = p.resultLevels[limit]
+ }
+ }
+ level := p.resultLevels[indexes[0]]
+ return &isolatingRunSequence{
+ p: p,
+ indexes: indexes,
+ types: types,
+ level: level,
+ sos: typeForLevel(maxLevel(prevLevel, level)),
+ eos: typeForLevel(maxLevel(succLevel, level)),
+ }
+}
+
+// Resolving weak types Rules W1-W7.
+//
+// Note that some weak types (EN, AN) remain after this processing is
+// complete.
+func (s *isolatingRunSequence) resolveWeakTypes() {
+
+ // on entry, only these types remain
+ s.assertOnly(L, R, AL, EN, ES, ET, AN, CS, B, S, WS, ON, NSM, LRI, RLI, FSI, PDI)
+
+ // Rule W1.
+ // Changes all NSMs.
+ preceedingCharacterType := s.sos
+ for i, t := range s.types {
+ if t == NSM {
+ s.types[i] = preceedingCharacterType
+ } else {
+ if t.in(LRI, RLI, FSI, PDI) {
+ preceedingCharacterType = ON
+ }
+ preceedingCharacterType = t
+ }
+ }
+
+ // Rule W2.
+ // EN does not change at the start of the run, because sos != AL.
+ for i, t := range s.types {
+ if t == EN {
+ for j := i - 1; j >= 0; j-- {
+ if t := s.types[j]; t.in(L, R, AL) {
+ if t == AL {
+ s.types[i] = AN
+ }
+ break
+ }
+ }
+ }
+ }
+
+ // Rule W3.
+ for i, t := range s.types {
+ if t == AL {
+ s.types[i] = R
+ }
+ }
+
+ // Rule W4.
+ // Since there must be values on both sides for this rule to have an
+ // effect, the scan skips the first and last value.
+ //
+ // Although the scan proceeds left to right, and changes the type
+ // values in a way that would appear to affect the computations
+ // later in the scan, there is actually no problem. A change in the
+ // current value can only affect the value to its immediate right,
+ // and only affect it if it is ES or CS. But the current value can
+ // only change if the value to its right is not ES or CS. Thus
+ // either the current value will not change, or its change will have
+ // no effect on the remainder of the analysis.
+
+ for i := 1; i < s.Len()-1; i++ {
+ t := s.types[i]
+ if t == ES || t == CS {
+ prevSepType := s.types[i-1]
+ succSepType := s.types[i+1]
+ if prevSepType == EN && succSepType == EN {
+ s.types[i] = EN
+ } else if s.types[i] == CS && prevSepType == AN && succSepType == AN {
+ s.types[i] = AN
+ }
+ }
+ }
+
+ // Rule W5.
+ for i, t := range s.types {
+ if t == ET {
+ // locate end of sequence
+ runStart := i
+ runEnd := s.findRunLimit(runStart, ET)
+
+ // check values at ends of sequence
+ t := s.sos
+ if runStart > 0 {
+ t = s.types[runStart-1]
+ }
+ if t != EN {
+ t = s.eos
+ if runEnd < len(s.types) {
+ t = s.types[runEnd]
+ }
+ }
+ if t == EN {
+ setTypes(s.types[runStart:runEnd], EN)
+ }
+ // continue at end of sequence
+ i = runEnd
+ }
+ }
+
+ // Rule W6.
+ for i, t := range s.types {
+ if t.in(ES, ET, CS) {
+ s.types[i] = ON
+ }
+ }
+
+ // Rule W7.
+ for i, t := range s.types {
+ if t == EN {
+ // set default if we reach start of run
+ prevStrongType := s.sos
+ for j := i - 1; j >= 0; j-- {
+ t = s.types[j]
+ if t == L || t == R { // AL's have been changed to R
+ prevStrongType = t
+ break
+ }
+ }
+ if prevStrongType == L {
+ s.types[i] = L
+ }
+ }
+ }
+}
+
+// 6) resolving neutral types Rules N1-N2.
+func (s *isolatingRunSequence) resolveNeutralTypes() {
+
+ // on entry, only these types can be in resultTypes
+ s.assertOnly(L, R, EN, AN, B, S, WS, ON, RLI, LRI, FSI, PDI)
+
+ for i, t := range s.types {
+ switch t {
+ case WS, ON, B, S, RLI, LRI, FSI, PDI:
+ // find bounds of run of neutrals
+ runStart := i
+ runEnd := s.findRunLimit(runStart, B, S, WS, ON, RLI, LRI, FSI, PDI)
+
+ // determine effective types at ends of run
+ var leadType, trailType Class
+
+ // Note that the character found can only be L, R, AN, or
+ // EN.
+ if runStart == 0 {
+ leadType = s.sos
+ } else {
+ leadType = s.types[runStart-1]
+ if leadType.in(AN, EN) {
+ leadType = R
+ }
+ }
+ if runEnd == len(s.types) {
+ trailType = s.eos
+ } else {
+ trailType = s.types[runEnd]
+ if trailType.in(AN, EN) {
+ trailType = R
+ }
+ }
+
+ var resolvedType Class
+ if leadType == trailType {
+ // Rule N1.
+ resolvedType = leadType
+ } else {
+ // Rule N2.
+ // Notice the embedding level of the run is used, not
+ // the paragraph embedding level.
+ resolvedType = typeForLevel(s.level)
+ }
+
+ setTypes(s.types[runStart:runEnd], resolvedType)
+
+ // skip over run of (former) neutrals
+ i = runEnd
+ }
+ }
+}
+
+func setLevels(levels []level, newLevel level) {
+ for i := range levels {
+ levels[i] = newLevel
+ }
+}
+
+func setTypes(types []Class, newType Class) {
+ for i := range types {
+ types[i] = newType
+ }
+}
+
+// 7) resolving implicit embedding levels Rules I1, I2.
+func (s *isolatingRunSequence) resolveImplicitLevels() {
+
+ // on entry, only these types can be in resultTypes
+ s.assertOnly(L, R, EN, AN)
+
+ s.resolvedLevels = make([]level, len(s.types))
+ setLevels(s.resolvedLevels, s.level)
+
+ if (s.level & 1) == 0 { // even level
+ for i, t := range s.types {
+ // Rule I1.
+ if t == L {
+ // no change
+ } else if t == R {
+ s.resolvedLevels[i] += 1
+ } else { // t == AN || t == EN
+ s.resolvedLevels[i] += 2
+ }
+ }
+ } else { // odd level
+ for i, t := range s.types {
+ // Rule I2.
+ if t == R {
+ // no change
+ } else { // t == L || t == AN || t == EN
+ s.resolvedLevels[i] += 1
+ }
+ }
+ }
+}
+
+// Applies the levels and types resolved in rules W1-I2 to the
+// resultLevels array.
+func (s *isolatingRunSequence) applyLevelsAndTypes() {
+ for i, x := range s.indexes {
+ s.p.resultTypes[x] = s.types[i]
+ s.p.resultLevels[x] = s.resolvedLevels[i]
+ }
+}
+
+// Return the limit of the run consisting only of the types in validSet
+// starting at index. This checks the value at index, and will return
+// index if that value is not in validSet.
+func (s *isolatingRunSequence) findRunLimit(index int, validSet ...Class) int {
+loop:
+ for ; index < len(s.types); index++ {
+ t := s.types[index]
+ for _, valid := range validSet {
+ if t == valid {
+ continue loop
+ }
+ }
+ return index // didn't find a match in validSet
+ }
+ return len(s.types)
+}
+
+// Algorithm validation. Assert that all values in types are in the
+// provided set.
+func (s *isolatingRunSequence) assertOnly(codes ...Class) {
+loop:
+ for i, t := range s.types {
+ for _, c := range codes {
+ if t == c {
+ continue loop
+ }
+ }
+ log.Panicf("invalid bidi code %v present in assertOnly at position %d", t, s.indexes[i])
+ }
+}
+
+// determineLevelRuns returns an array of level runs. Each level run is
+// described as an array of indexes into the input string.
+//
+// Determines the level runs. Rule X9 will be applied in determining the
+// runs, in the way that makes sure the characters that are supposed to be
+// removed are not included in the runs.
+func (p *paragraph) determineLevelRuns() [][]int {
+ run := []int{}
+ allRuns := [][]int{}
+ currentLevel := implicitLevel
+
+ for i := range p.initialTypes {
+ if !isRemovedByX9(p.initialTypes[i]) {
+ if p.resultLevels[i] != currentLevel {
+ // we just encountered a new run; wrap up last run
+ if currentLevel >= 0 { // only wrap it up if there was a run
+ allRuns = append(allRuns, run)
+ run = nil
+ }
+ // Start new run
+ currentLevel = p.resultLevels[i]
+ }
+ run = append(run, i)
+ }
+ }
+ // Wrap up the final run, if any
+ if len(run) > 0 {
+ allRuns = append(allRuns, run)
+ }
+ return allRuns
+}
+
+// Definition BD13. Determine isolating run sequences.
+func (p *paragraph) determineIsolatingRunSequences() []*isolatingRunSequence {
+ levelRuns := p.determineLevelRuns()
+
+ // Compute the run that each character belongs to
+ runForCharacter := make([]int, p.Len())
+ for i, run := range levelRuns {
+ for _, index := range run {
+ runForCharacter[index] = i
+ }
+ }
+
+ sequences := []*isolatingRunSequence{}
+
+ var currentRunSequence []int
+
+ for _, run := range levelRuns {
+ first := run[0]
+ if p.initialTypes[first] != PDI || p.matchingIsolateInitiator[first] == -1 {
+ currentRunSequence = nil
+ // int run = i;
+ for {
+ // Copy this level run into currentRunSequence
+ currentRunSequence = append(currentRunSequence, run...)
+
+ last := currentRunSequence[len(currentRunSequence)-1]
+ lastT := p.initialTypes[last]
+ if lastT.in(LRI, RLI, FSI) && p.matchingPDI[last] != p.Len() {
+ run = levelRuns[runForCharacter[p.matchingPDI[last]]]
+ } else {
+ break
+ }
+ }
+ sequences = append(sequences, p.isolatingRunSequence(currentRunSequence))
+ }
+ }
+ return sequences
+}
+
+// Assign level information to characters removed by rule X9. This is for
+// ease of relating the level information to the original input data. Note
+// that the levels assigned to these codes are arbitrary, they're chosen so
+// as to avoid breaking level runs.
+func (p *paragraph) assignLevelsToCharactersRemovedByX9() {
+ for i, t := range p.initialTypes {
+ if t.in(LRE, RLE, LRO, RLO, PDF, BN) {
+ p.resultTypes[i] = t
+ p.resultLevels[i] = -1
+ }
+ }
+ // now propagate forward the levels information (could have
+ // propagated backward, the main thing is not to introduce a level
+ // break where one doesn't already exist).
+
+ if p.resultLevels[0] == -1 {
+ p.resultLevels[0] = p.embeddingLevel
+ }
+ for i := 1; i < len(p.initialTypes); i++ {
+ if p.resultLevels[i] == -1 {
+ p.resultLevels[i] = p.resultLevels[i-1]
+ }
+ }
+ // Embedding information is for informational purposes only so need not be
+ // adjusted.
+}
+
+//
+// Output
+//
+
+// getLevels computes levels array breaking lines at offsets in linebreaks.
+// Rule L1.
+//
+// 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.
+func (p *paragraph) getLevels(linebreaks []int) []level {
+ // 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, p.Len())
+
+ result := append([]level(nil), p.resultLevels...)
+
+ // 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 i, t := range p.initialTypes {
+ if t.in(B, S) {
+ // Rule L1, clauses one and two.
+ result[i] = p.embeddingLevel
+
+ // Rule L1, clause three.
+ for j := i - 1; j >= 0; j-- {
+ if isWhitespace(p.initialTypes[j]) { // including format codes
+ result[j] = p.embeddingLevel
+ } else {
+ break
+ }
+ }
+ }
+ }
+
+ // Rule L1, clause four.
+ start := 0
+ for _, limit := range linebreaks {
+ for j := limit - 1; j >= start; j-- {
+ if isWhitespace(p.initialTypes[j]) { // including format codes
+ result[j] = p.embeddingLevel
+ } else {
+ break
+ }
+ }
+ start = limit
+ }
+
+ return result
+}
+
+// getReordering returns the reordering of lines from a visual index to a
+// logical index for line breaks at the given offsets.
+//
+// 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.
+func (p *paragraph) getReordering(linebreaks []int) []int {
+ validateLineBreaks(linebreaks, p.Len())
+
+ return computeMultilineReordering(p.getLevels(linebreaks), linebreaks)
+}
+
+// Return multiline reordering array for a given level array. Reordering
+// does not occur across a line break.
+func computeMultilineReordering(levels []level, linebreaks []int) []int {
+ result := make([]int, len(levels))
+
+ start := 0
+ for _, limit := range linebreaks {
+ tempLevels := make([]level, limit-start)
+ copy(tempLevels, levels[start:])
+
+ for j, order := range computeReordering(tempLevels) {
+ result[start+j] = order + 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.
+func computeReordering(levels []level) []int {
+ result := make([]int, len(levels))
+ // initialize order
+ for i := range result {
+ 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.
+ highestLevel := level(0)
+ lowestOddLevel := level(maxDepth + 2)
+ for _, level := range levels {
+ if level > highestLevel {
+ highestLevel = level
+ }
+ if level&1 != 0 && level < lowestOddLevel {
+ lowestOddLevel = level
+ }
+ }
+
+ for level := highestLevel; level >= lowestOddLevel; level-- {
+ for i := 0; i < len(levels); i++ {
+ if levels[i] >= level {
+ // find range of text at or above this level
+ start := i
+ limit := i + 1
+ for limit < len(levels) && levels[limit] >= level {
+ limit++
+ }
+
+ for j, k := start, limit-1; j < k; j, k = j+1, k-1 {
+ result[j], result[k] = result[k], result[j]
+ }
+ // skip to end of level run
+ i = limit
+ }
+ }
+ }
+
+ return result
+}
+
+// isWhitespace reports whether the type is considered a whitespace type for the
+// line break rules.
+func isWhitespace(c Class) bool {
+ switch c {
+ case LRE, RLE, LRO, RLO, PDF, LRI, RLI, FSI, PDI, BN, WS:
+ return true
+ }
+ return false
+}
+
+// isRemovedByX9 reports whether the type is one of the types removed in X9.
+func isRemovedByX9(c Class) bool {
+ switch c {
+ case LRE, RLE, LRO, RLO, PDF, BN:
+ return true
+ }
+ return false
+}
+
+// typeForLevel reports the strong type (L or R) corresponding to the level.
+func typeForLevel(level level) Class {
+ if (level & 0x1) == 0 {
+ return L
+ }
+ return R
+}
+
+// TODO: change validation to not panic
+
+func validateTypes(types []Class) {
+ if len(types) == 0 {
+ log.Panic("types is null")
+ }
+ for i, t := range types[:len(types)-1] {
+ if t == B {
+ log.Panicf("B type before end of paragraph at index: %d", i)
+ }
+ }
+}
+
+func validateParagraphEmbeddingLevel(embeddingLevel level) {
+ if embeddingLevel != implicitLevel &&
+ embeddingLevel != 0 &&
+ embeddingLevel != 1 {
+ log.Panicf("illegal paragraph embedding level: %d", embeddingLevel)
+ }
+}
+
+func validateLineBreaks(linebreaks []int, textLength int) {
+ prev := 0
+ for i, next := range linebreaks {
+ if next <= prev {
+ log.Panicf("bad linebreak: %d at index: %d", next, i)
+ }
+ prev = next
+ }
+ if prev != textLength {
+ log.Panicf("last linebreak was %d, want %d", prev, textLength)
+ }
+}
+
+func validatePbTypes(pairTypes []bracketType) {
+ if len(pairTypes) == 0 {
+ log.Panic("pairTypes is null")
+ }
+ for i, pt := range pairTypes {
+ switch pt {
+ case bpNone, bpOpen, bpClose:
+ default:
+ log.Panicf("illegal pairType value at %d: %v", i, pairTypes[i])
+ }
+ }
+}
+
+func validatePbValues(pairValues []rune, pairTypes []bracketType) {
+ if pairValues == nil {
+ log.Panic("pairValues is null")
+ }
+ if len(pairTypes) != len(pairValues) {
+ log.Panic("pairTypes is different length from pairValues")
+ }
+}
Code Review / barometer.git / blobdiff