+++ /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:
-// http://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")
- }
-}
OSDN Git Service
