Source: core.go in package vendor/golang.org/x/text/unicode/bidi


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 := &paragraph{
		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

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 {

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)

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

least greater odd

				newLevel = (stack.lastEmbeddingLevel() + 1) | 1

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
				}

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--

do nothing

			} else {
				overflowEmbeddingCount = 0
				for !stack.lastDirectionalIsolateStatus() {
					stack.pop()
				}
				stack.pop()
				validIsolateCount--
			}
			p.resultLevels[i] = stack.lastEmbeddingLevel()

Rule X7

Not really part of the spec

			p.resultLevels[i] = stack.lastEmbeddingLevel()

do nothing

			} else if overflowEmbeddingCount > 0 {
				overflowEmbeddingCount--
			} else if !stack.lastDirectionalIsolateStatus() && stack.depth() >= 2 {
				stack.pop()
			}

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

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.

	precedingCharacterType := s.sos
	for i, t := range s.types {
		if t == NSM {
			s.types[i] = precedingCharacterType
		} else {
			if t.in(LRI, RLI, FSI, PDI) {
				precedingCharacterType = ON
			}
			precedingCharacterType = 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 {

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 {

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 {

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

Rule N1.

				resolvedType = leadType

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

Rule I1.

no change

			} else if t == R {
				s.resolvedLevels[i] += 1
			} else { // t == AN || t == EN
				s.resolvedLevels[i] += 2
			}
		}
	} else { // odd level

Rule I2.

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]) {

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 {

int run = i;

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.

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 {

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 {

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++ {

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")
	}