1// Copyright 2015 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bidi
6
7import (
8 "fmt"
9)
10
11// This implementation is a port based on the reference implementation found at:
12// https://www.unicode.org/Public/PROGRAMS/BidiReferenceJava/
13//
14// described in Unicode Bidirectional Algorithm (UAX #9).
15//
16// Input:
17// There are two levels of input to the algorithm, since clients may prefer to
18// supply some information from out-of-band sources rather than relying on the
19// default behavior.
20//
21// - Bidi class array
22// - Bidi class array, with externally supplied base line direction
23//
24// Output:
25// Output is separated into several stages:
26//
27// - levels array over entire paragraph
28// - reordering array over entire paragraph
29// - levels array over line
30// - reordering array over line
31//
32// Note that for conformance to the Unicode Bidirectional Algorithm,
33// implementations are only required to generate correct reordering and
34// character directionality (odd or even levels) over a line. Generating
35// identical level arrays over a line is not required. Bidi explicit format
36// codes (LRE, RLE, LRO, RLO, PDF) and BN can be assigned arbitrary levels and
37// positions as long as the rest of the input is properly reordered.
38//
39// As the algorithm is defined to operate on a single paragraph at a time, this
40// implementation is written to handle single paragraphs. Thus rule P1 is
41// presumed by this implementation-- the data provided to the implementation is
42// assumed to be a single paragraph, and either contains no 'B' codes, or a
43// single 'B' code at the end of the input. 'B' is allowed as input to
44// illustrate how the algorithm assigns it a level.
45//
46// Also note that rules L3 and L4 depend on the rendering engine that uses the
47// result of the bidi algorithm. This implementation assumes that the rendering
48// engine expects combining marks in visual order (e.g. to the left of their
49// base character in RTL runs) and that it adjusts the glyphs used to render
50// mirrored characters that are in RTL runs so that they render appropriately.
51
52// level is the embedding level of a character. Even embedding levels indicate
53// left-to-right order and odd levels indicate right-to-left order. The special
54// level of -1 is reserved for undefined order.
55type level int8
56
57const implicitLevel level = -1
58
59// in returns if x is equal to any of the values in set.
60func (c Class) in(set ...Class) bool {
61 for _, s := range set {
62 if c == s {
63 return true
64 }
65 }
66 return false
67}
68
69// A paragraph contains the state of a paragraph.
70type paragraph struct {
71 initialTypes []Class
72
73 // Arrays of properties needed for paired bracket evaluation in N0
74 pairTypes []bracketType // paired Bracket types for paragraph
75 pairValues []rune // rune for opening bracket or pbOpen and pbClose; 0 for pbNone
76
77 embeddingLevel level // default: = implicitLevel;
78
79 // at the paragraph levels
80 resultTypes []Class
81 resultLevels []level
82
83 // Index of matching PDI for isolate initiator characters. For other
84 // characters, the value of matchingPDI will be set to -1. For isolate
85 // initiators with no matching PDI, matchingPDI will be set to the length of
86 // the input string.
87 matchingPDI []int
88
89 // Index of matching isolate initiator for PDI characters. For other
90 // characters, and for PDIs with no matching isolate initiator, the value of
91 // matchingIsolateInitiator will be set to -1.
92 matchingIsolateInitiator []int
93}
94
95// newParagraph initializes a paragraph. The user needs to supply a few arrays
96// corresponding to the preprocessed text input. The types correspond to the
97// Unicode BiDi classes for each rune. pairTypes indicates the bracket type for
98// each rune. pairValues provides a unique bracket class identifier for each
99// rune (suggested is the rune of the open bracket for opening and matching
100// close brackets, after normalization). The embedding levels are optional, but
101// may be supplied to encode embedding levels of styled text.
102func newParagraph(types []Class, pairTypes []bracketType, pairValues []rune, levels level) (*paragraph, error) {
103 var err error
104 if err = validateTypes(types); err != nil {
105 return nil, err
106 }
107 if err = validatePbTypes(pairTypes); err != nil {
108 return nil, err
109 }
110 if err = validatePbValues(pairValues, pairTypes); err != nil {
111 return nil, err
112 }
113 if err = validateParagraphEmbeddingLevel(levels); err != nil {
114 return nil, err
115 }
116
117 p := ¶graph{
118 initialTypes: append([]Class(nil), types...),
119 embeddingLevel: levels,
120
121 pairTypes: pairTypes,
122 pairValues: pairValues,
123
124 resultTypes: append([]Class(nil), types...),
125 }
126 p.run()
127 return p, nil
128}
129
130func (p *paragraph) Len() int { return len(p.initialTypes) }
131
132// The algorithm. Does not include line-based processing (Rules L1, L2).
133// These are applied later in the line-based phase of the algorithm.
134func (p *paragraph) run() {
135 p.determineMatchingIsolates()
136
137 // 1) determining the paragraph level
138 // Rule P1 is the requirement for entering this algorithm.
139 // Rules P2, P3.
140 // If no externally supplied paragraph embedding level, use default.
141 if p.embeddingLevel == implicitLevel {
142 p.embeddingLevel = p.determineParagraphEmbeddingLevel(0, p.Len())
143 }
144
145 // Initialize result levels to paragraph embedding level.
146 p.resultLevels = make([]level, p.Len())
147 setLevels(p.resultLevels, p.embeddingLevel)
148
149 // 2) Explicit levels and directions
150 // Rules X1-X8.
151 p.determineExplicitEmbeddingLevels()
152
153 // Rule X9.
154 // We do not remove the embeddings, the overrides, the PDFs, and the BNs
155 // from the string explicitly. But they are not copied into isolating run
156 // sequences when they are created, so they are removed for all
157 // practical purposes.
158
159 // Rule X10.
160 // Run remainder of algorithm one isolating run sequence at a time
161 for _, seq := range p.determineIsolatingRunSequences() {
162 // 3) resolving weak types
163 // Rules W1-W7.
164 seq.resolveWeakTypes()
165
166 // 4a) resolving paired brackets
167 // Rule N0
168 resolvePairedBrackets(seq)
169
170 // 4b) resolving neutral types
171 // Rules N1-N3.
172 seq.resolveNeutralTypes()
173
174 // 5) resolving implicit embedding levels
175 // Rules I1, I2.
176 seq.resolveImplicitLevels()
177
178 // Apply the computed levels and types
179 seq.applyLevelsAndTypes()
180 }
181
182 // Assign appropriate levels to 'hide' LREs, RLEs, LROs, RLOs, PDFs, and
183 // BNs. This is for convenience, so the resulting level array will have
184 // a value for every character.
185 p.assignLevelsToCharactersRemovedByX9()
186}
187
188// determineMatchingIsolates determines the matching PDI for each isolate
189// initiator and vice versa.
190//
191// Definition BD9.
192//
193// At the end of this function:
194//
195// - The member variable matchingPDI is set to point to the index of the
196// matching PDI character for each isolate initiator character. If there is
197// no matching PDI, it is set to the length of the input text. For other
198// characters, it is set to -1.
199// - The member variable matchingIsolateInitiator is set to point to the
200// index of the matching isolate initiator character for each PDI character.
201// If there is no matching isolate initiator, or the character is not a PDI,
202// it is set to -1.
203func (p *paragraph) determineMatchingIsolates() {
204 p.matchingPDI = make([]int, p.Len())
205 p.matchingIsolateInitiator = make([]int, p.Len())
206
207 for i := range p.matchingIsolateInitiator {
208 p.matchingIsolateInitiator[i] = -1
209 }
210
211 for i := range p.matchingPDI {
212 p.matchingPDI[i] = -1
213
214 if t := p.resultTypes[i]; t.in(LRI, RLI, FSI) {
215 depthCounter := 1
216 for j := i + 1; j < p.Len(); j++ {
217 if u := p.resultTypes[j]; u.in(LRI, RLI, FSI) {
218 depthCounter++
219 } else if u == PDI {
220 if depthCounter--; depthCounter == 0 {
221 p.matchingPDI[i] = j
222 p.matchingIsolateInitiator[j] = i
223 break
224 }
225 }
226 }
227 if p.matchingPDI[i] == -1 {
228 p.matchingPDI[i] = p.Len()
229 }
230 }
231 }
232}
233
234// determineParagraphEmbeddingLevel reports the resolved paragraph direction of
235// the substring limited by the given range [start, end).
236//
237// Determines the paragraph level based on rules P2, P3. This is also used
238// in rule X5c to find if an FSI should resolve to LRI or RLI.
239func (p *paragraph) determineParagraphEmbeddingLevel(start, end int) level {
240 var strongType Class = unknownClass
241
242 // Rule P2.
243 for i := start; i < end; i++ {
244 if t := p.resultTypes[i]; t.in(L, AL, R) {
245 strongType = t
246 break
247 } else if t.in(FSI, LRI, RLI) {
248 i = p.matchingPDI[i] // skip over to the matching PDI
249 if i > end {
250 panic("assert (i <= end)")
251 }
252 }
253 }
254 // Rule P3.
255 switch strongType {
256 case unknownClass: // none found
257 // default embedding level when no strong types found is 0.
258 return 0
259 case L:
260 return 0
261 default: // AL, R
262 return 1
263 }
264}
265
266const maxDepth = 125
267
268// This stack will store the embedding levels and override and isolated
269// statuses
270type directionalStatusStack struct {
271 stackCounter int
272 embeddingLevelStack [maxDepth + 1]level
273 overrideStatusStack [maxDepth + 1]Class
274 isolateStatusStack [maxDepth + 1]bool
275}
276
277func (s *directionalStatusStack) empty() { s.stackCounter = 0 }
278func (s *directionalStatusStack) pop() { s.stackCounter-- }
279func (s *directionalStatusStack) depth() int { return s.stackCounter }
280
281func (s *directionalStatusStack) push(level level, overrideStatus Class, isolateStatus bool) {
282 s.embeddingLevelStack[s.stackCounter] = level
283 s.overrideStatusStack[s.stackCounter] = overrideStatus
284 s.isolateStatusStack[s.stackCounter] = isolateStatus
285 s.stackCounter++
286}
287
288func (s *directionalStatusStack) lastEmbeddingLevel() level {
289 return s.embeddingLevelStack[s.stackCounter-1]
290}
291
292func (s *directionalStatusStack) lastDirectionalOverrideStatus() Class {
293 return s.overrideStatusStack[s.stackCounter-1]
294}
295
296func (s *directionalStatusStack) lastDirectionalIsolateStatus() bool {
297 return s.isolateStatusStack[s.stackCounter-1]
298}
299
300// Determine explicit levels using rules X1 - X8
301func (p *paragraph) determineExplicitEmbeddingLevels() {
302 var stack directionalStatusStack
303 var overflowIsolateCount, overflowEmbeddingCount, validIsolateCount int
304
305 // Rule X1.
306 stack.push(p.embeddingLevel, ON, false)
307
308 for i, t := range p.resultTypes {
309 // Rules X2, X3, X4, X5, X5a, X5b, X5c
310 switch t {
311 case RLE, LRE, RLO, LRO, RLI, LRI, FSI:
312 isIsolate := t.in(RLI, LRI, FSI)
313 isRTL := t.in(RLE, RLO, RLI)
314
315 // override if this is an FSI that resolves to RLI
316 if t == FSI {
317 isRTL = (p.determineParagraphEmbeddingLevel(i+1, p.matchingPDI[i]) == 1)
318 }
319 if isIsolate {
320 p.resultLevels[i] = stack.lastEmbeddingLevel()
321 if stack.lastDirectionalOverrideStatus() != ON {
322 p.resultTypes[i] = stack.lastDirectionalOverrideStatus()
323 }
324 }
325
326 var newLevel level
327 if isRTL {
328 // least greater odd
329 newLevel = (stack.lastEmbeddingLevel() + 1) | 1
330 } else {
331 // least greater even
332 newLevel = (stack.lastEmbeddingLevel() + 2) &^ 1
333 }
334
335 if newLevel <= maxDepth && overflowIsolateCount == 0 && overflowEmbeddingCount == 0 {
336 if isIsolate {
337 validIsolateCount++
338 }
339 // Push new embedding level, override status, and isolated
340 // status.
341 // No check for valid stack counter, since the level check
342 // suffices.
343 switch t {
344 case LRO:
345 stack.push(newLevel, L, isIsolate)
346 case RLO:
347 stack.push(newLevel, R, isIsolate)
348 default:
349 stack.push(newLevel, ON, isIsolate)
350 }
351 // Not really part of the spec
352 if !isIsolate {
353 p.resultLevels[i] = newLevel
354 }
355 } else {
356 // This is an invalid explicit formatting character,
357 // so apply the "Otherwise" part of rules X2-X5b.
358 if isIsolate {
359 overflowIsolateCount++
360 } else { // !isIsolate
361 if overflowIsolateCount == 0 {
362 overflowEmbeddingCount++
363 }
364 }
365 }
366
367 // Rule X6a
368 case PDI:
369 if overflowIsolateCount > 0 {
370 overflowIsolateCount--
371 } else if validIsolateCount == 0 {
372 // do nothing
373 } else {
374 overflowEmbeddingCount = 0
375 for !stack.lastDirectionalIsolateStatus() {
376 stack.pop()
377 }
378 stack.pop()
379 validIsolateCount--
380 }
381 p.resultLevels[i] = stack.lastEmbeddingLevel()
382
383 // Rule X7
384 case PDF:
385 // Not really part of the spec
386 p.resultLevels[i] = stack.lastEmbeddingLevel()
387
388 if overflowIsolateCount > 0 {
389 // do nothing
390 } else if overflowEmbeddingCount > 0 {
391 overflowEmbeddingCount--
392 } else if !stack.lastDirectionalIsolateStatus() && stack.depth() >= 2 {
393 stack.pop()
394 }
395
396 case B: // paragraph separator.
397 // Rule X8.
398
399 // These values are reset for clarity, in this implementation B
400 // can only occur as the last code in the array.
401 stack.empty()
402 overflowIsolateCount = 0
403 overflowEmbeddingCount = 0
404 validIsolateCount = 0
405 p.resultLevels[i] = p.embeddingLevel
406
407 default:
408 p.resultLevels[i] = stack.lastEmbeddingLevel()
409 if stack.lastDirectionalOverrideStatus() != ON {
410 p.resultTypes[i] = stack.lastDirectionalOverrideStatus()
411 }
412 }
413 }
414}
415
416type isolatingRunSequence struct {
417 p *paragraph
418
419 indexes []int // indexes to the original string
420
421 types []Class // type of each character using the index
422 resolvedLevels []level // resolved levels after application of rules
423 level level
424 sos, eos Class
425}
426
427func (i *isolatingRunSequence) Len() int { return len(i.indexes) }
428
429// Rule X10, second bullet: Determine the start-of-sequence (sos) and end-of-sequence (eos) types,
430// either L or R, for each isolating run sequence.
431func (p *paragraph) isolatingRunSequence(indexes []int) *isolatingRunSequence {
432 length := len(indexes)
433 types := make([]Class, length)
434 for i, x := range indexes {
435 types[i] = p.resultTypes[x]
436 }
437
438 // assign level, sos and eos
439 prevChar := indexes[0] - 1
440 for prevChar >= 0 && isRemovedByX9(p.initialTypes[prevChar]) {
441 prevChar--
442 }
443 prevLevel := p.embeddingLevel
444 if prevChar >= 0 {
445 prevLevel = p.resultLevels[prevChar]
446 }
447
448 var succLevel level
449 lastType := types[length-1]
450 if lastType.in(LRI, RLI, FSI) {
451 succLevel = p.embeddingLevel
452 } else {
453 // the first character after the end of run sequence
454 limit := indexes[length-1] + 1
455 for ; limit < p.Len() && isRemovedByX9(p.initialTypes[limit]); limit++ {
456
457 }
458 succLevel = p.embeddingLevel
459 if limit < p.Len() {
460 succLevel = p.resultLevels[limit]
461 }
462 }
463 level := p.resultLevels[indexes[0]]
464 return &isolatingRunSequence{
465 p: p,
466 indexes: indexes,
467 types: types,
468 level: level,
469 sos: typeForLevel(max(prevLevel, level)),
470 eos: typeForLevel(max(succLevel, level)),
471 }
472}
473
474// Resolving weak types Rules W1-W7.
475//
476// Note that some weak types (EN, AN) remain after this processing is
477// complete.
478func (s *isolatingRunSequence) resolveWeakTypes() {
479
480 // on entry, only these types remain
481 s.assertOnly(L, R, AL, EN, ES, ET, AN, CS, B, S, WS, ON, NSM, LRI, RLI, FSI, PDI)
482
483 // Rule W1.
484 // Changes all NSMs.
485 precedingCharacterType := s.sos
486 for i, t := range s.types {
487 if t == NSM {
488 s.types[i] = precedingCharacterType
489 } else {
490 // if t.in(LRI, RLI, FSI, PDI) {
491 // precedingCharacterType = ON
492 // }
493 precedingCharacterType = t
494 }
495 }
496
497 // Rule W2.
498 // EN does not change at the start of the run, because sos != AL.
499 for i, t := range s.types {
500 if t == EN {
501 for j := i - 1; j >= 0; j-- {
502 if t := s.types[j]; t.in(L, R, AL) {
503 if t == AL {
504 s.types[i] = AN
505 }
506 break
507 }
508 }
509 }
510 }
511
512 // Rule W3.
513 for i, t := range s.types {
514 if t == AL {
515 s.types[i] = R
516 }
517 }
518
519 // Rule W4.
520 // Since there must be values on both sides for this rule to have an
521 // effect, the scan skips the first and last value.
522 //
523 // Although the scan proceeds left to right, and changes the type
524 // values in a way that would appear to affect the computations
525 // later in the scan, there is actually no problem. A change in the
526 // current value can only affect the value to its immediate right,
527 // and only affect it if it is ES or CS. But the current value can
528 // only change if the value to its right is not ES or CS. Thus
529 // either the current value will not change, or its change will have
530 // no effect on the remainder of the analysis.
531
532 for i := 1; i < s.Len()-1; i++ {
533 t := s.types[i]
534 if t == ES || t == CS {
535 prevSepType := s.types[i-1]
536 succSepType := s.types[i+1]
537 if prevSepType == EN && succSepType == EN {
538 s.types[i] = EN
539 } else if s.types[i] == CS && prevSepType == AN && succSepType == AN {
540 s.types[i] = AN
541 }
542 }
543 }
544
545 // Rule W5.
546 for i, t := range s.types {
547 if t == ET {
548 // locate end of sequence
549 runStart := i
550 runEnd := s.findRunLimit(runStart, ET)
551
552 // check values at ends of sequence
553 t := s.sos
554 if runStart > 0 {
555 t = s.types[runStart-1]
556 }
557 if t != EN {
558 t = s.eos
559 if runEnd < len(s.types) {
560 t = s.types[runEnd]
561 }
562 }
563 if t == EN {
564 setTypes(s.types[runStart:runEnd], EN)
565 }
566 // continue at end of sequence
567 i = runEnd
568 }
569 }
570
571 // Rule W6.
572 for i, t := range s.types {
573 if t.in(ES, ET, CS) {
574 s.types[i] = ON
575 }
576 }
577
578 // Rule W7.
579 for i, t := range s.types {
580 if t == EN {
581 // set default if we reach start of run
582 prevStrongType := s.sos
583 for j := i - 1; j >= 0; j-- {
584 t = s.types[j]
585 if t == L || t == R { // AL's have been changed to R
586 prevStrongType = t
587 break
588 }
589 }
590 if prevStrongType == L {
591 s.types[i] = L
592 }
593 }
594 }
595}
596
597// 6) resolving neutral types Rules N1-N2.
598func (s *isolatingRunSequence) resolveNeutralTypes() {
599
600 // on entry, only these types can be in resultTypes
601 s.assertOnly(L, R, EN, AN, B, S, WS, ON, RLI, LRI, FSI, PDI)
602
603 for i, t := range s.types {
604 switch t {
605 case WS, ON, B, S, RLI, LRI, FSI, PDI:
606 // find bounds of run of neutrals
607 runStart := i
608 runEnd := s.findRunLimit(runStart, B, S, WS, ON, RLI, LRI, FSI, PDI)
609
610 // determine effective types at ends of run
611 var leadType, trailType Class
612
613 // Note that the character found can only be L, R, AN, or
614 // EN.
615 if runStart == 0 {
616 leadType = s.sos
617 } else {
618 leadType = s.types[runStart-1]
619 if leadType.in(AN, EN) {
620 leadType = R
621 }
622 }
623 if runEnd == len(s.types) {
624 trailType = s.eos
625 } else {
626 trailType = s.types[runEnd]
627 if trailType.in(AN, EN) {
628 trailType = R
629 }
630 }
631
632 var resolvedType Class
633 if leadType == trailType {
634 // Rule N1.
635 resolvedType = leadType
636 } else {
637 // Rule N2.
638 // Notice the embedding level of the run is used, not
639 // the paragraph embedding level.
640 resolvedType = typeForLevel(s.level)
641 }
642
643 setTypes(s.types[runStart:runEnd], resolvedType)
644
645 // skip over run of (former) neutrals
646 i = runEnd
647 }
648 }
649}
650
651func setLevels(levels []level, newLevel level) {
652 for i := range levels {
653 levels[i] = newLevel
654 }
655}
656
657func setTypes(types []Class, newType Class) {
658 for i := range types {
659 types[i] = newType
660 }
661}
662
663// 7) resolving implicit embedding levels Rules I1, I2.
664func (s *isolatingRunSequence) resolveImplicitLevels() {
665
666 // on entry, only these types can be in resultTypes
667 s.assertOnly(L, R, EN, AN)
668
669 s.resolvedLevels = make([]level, len(s.types))
670 setLevels(s.resolvedLevels, s.level)
671
672 if (s.level & 1) == 0 { // even level
673 for i, t := range s.types {
674 // Rule I1.
675 if t == L {
676 // no change
677 } else if t == R {
678 s.resolvedLevels[i] += 1
679 } else { // t == AN || t == EN
680 s.resolvedLevels[i] += 2
681 }
682 }
683 } else { // odd level
684 for i, t := range s.types {
685 // Rule I2.
686 if t == R {
687 // no change
688 } else { // t == L || t == AN || t == EN
689 s.resolvedLevels[i] += 1
690 }
691 }
692 }
693}
694
695// Applies the levels and types resolved in rules W1-I2 to the
696// resultLevels array.
697func (s *isolatingRunSequence) applyLevelsAndTypes() {
698 for i, x := range s.indexes {
699 s.p.resultTypes[x] = s.types[i]
700 s.p.resultLevels[x] = s.resolvedLevels[i]
701 }
702}
703
704// Return the limit of the run consisting only of the types in validSet
705// starting at index. This checks the value at index, and will return
706// index if that value is not in validSet.
707func (s *isolatingRunSequence) findRunLimit(index int, validSet ...Class) int {
708loop:
709 for ; index < len(s.types); index++ {
710 t := s.types[index]
711 for _, valid := range validSet {
712 if t == valid {
713 continue loop
714 }
715 }
716 return index // didn't find a match in validSet
717 }
718 return len(s.types)
719}
720
721// Algorithm validation. Assert that all values in types are in the
722// provided set.
723func (s *isolatingRunSequence) assertOnly(codes ...Class) {
724loop:
725 for i, t := range s.types {
726 for _, c := range codes {
727 if t == c {
728 continue loop
729 }
730 }
731 panic(fmt.Errorf("invalid bidi code %v present in assertOnly at position %d", t, s.indexes[i]))
732 }
733}
734
735// determineLevelRuns returns an array of level runs. Each level run is
736// described as an array of indexes into the input string.
737//
738// Determines the level runs. Rule X9 will be applied in determining the
739// runs, in the way that makes sure the characters that are supposed to be
740// removed are not included in the runs.
741func (p *paragraph) determineLevelRuns() [][]int {
742 run := []int{}
743 allRuns := [][]int{}
744 currentLevel := implicitLevel
745
746 for i := range p.initialTypes {
747 if !isRemovedByX9(p.initialTypes[i]) {
748 if p.resultLevels[i] != currentLevel {
749 // we just encountered a new run; wrap up last run
750 if currentLevel >= 0 { // only wrap it up if there was a run
751 allRuns = append(allRuns, run)
752 run = nil
753 }
754 // Start new run
755 currentLevel = p.resultLevels[i]
756 }
757 run = append(run, i)
758 }
759 }
760 // Wrap up the final run, if any
761 if len(run) > 0 {
762 allRuns = append(allRuns, run)
763 }
764 return allRuns
765}
766
767// Definition BD13. Determine isolating run sequences.
768func (p *paragraph) determineIsolatingRunSequences() []*isolatingRunSequence {
769 levelRuns := p.determineLevelRuns()
770
771 // Compute the run that each character belongs to
772 runForCharacter := make([]int, p.Len())
773 for i, run := range levelRuns {
774 for _, index := range run {
775 runForCharacter[index] = i
776 }
777 }
778
779 sequences := []*isolatingRunSequence{}
780
781 var currentRunSequence []int
782
783 for _, run := range levelRuns {
784 first := run[0]
785 if p.initialTypes[first] != PDI || p.matchingIsolateInitiator[first] == -1 {
786 currentRunSequence = nil
787 // int run = i;
788 for {
789 // Copy this level run into currentRunSequence
790 currentRunSequence = append(currentRunSequence, run...)
791
792 last := currentRunSequence[len(currentRunSequence)-1]
793 lastT := p.initialTypes[last]
794 if lastT.in(LRI, RLI, FSI) && p.matchingPDI[last] != p.Len() {
795 run = levelRuns[runForCharacter[p.matchingPDI[last]]]
796 } else {
797 break
798 }
799 }
800 sequences = append(sequences, p.isolatingRunSequence(currentRunSequence))
801 }
802 }
803 return sequences
804}
805
806// Assign level information to characters removed by rule X9. This is for
807// ease of relating the level information to the original input data. Note
808// that the levels assigned to these codes are arbitrary, they're chosen so
809// as to avoid breaking level runs.
810func (p *paragraph) assignLevelsToCharactersRemovedByX9() {
811 for i, t := range p.initialTypes {
812 if t.in(LRE, RLE, LRO, RLO, PDF, BN) {
813 p.resultTypes[i] = t
814 p.resultLevels[i] = -1
815 }
816 }
817 // now propagate forward the levels information (could have
818 // propagated backward, the main thing is not to introduce a level
819 // break where one doesn't already exist).
820
821 if p.resultLevels[0] == -1 {
822 p.resultLevels[0] = p.embeddingLevel
823 }
824 for i := 1; i < len(p.initialTypes); i++ {
825 if p.resultLevels[i] == -1 {
826 p.resultLevels[i] = p.resultLevels[i-1]
827 }
828 }
829 // Embedding information is for informational purposes only so need not be
830 // adjusted.
831}
832
833//
834// Output
835//
836
837// getLevels computes levels array breaking lines at offsets in linebreaks.
838// Rule L1.
839//
840// The linebreaks array must include at least one value. The values must be
841// in strictly increasing order (no duplicates) between 1 and the length of
842// the text, inclusive. The last value must be the length of the text.
843func (p *paragraph) getLevels(linebreaks []int) []level {
844 // Note that since the previous processing has removed all
845 // P, S, and WS values from resultTypes, the values referred to
846 // in these rules are the initial types, before any processing
847 // has been applied (including processing of overrides).
848 //
849 // This example implementation has reinserted explicit format codes
850 // and BN, in order that the levels array correspond to the
851 // initial text. Their final placement is not normative.
852 // These codes are treated like WS in this implementation,
853 // so they don't interrupt sequences of WS.
854
855 validateLineBreaks(linebreaks, p.Len())
856
857 result := append([]level(nil), p.resultLevels...)
858
859 // don't worry about linebreaks since if there is a break within
860 // a series of WS values preceding S, the linebreak itself
861 // causes the reset.
862 for i, t := range p.initialTypes {
863 if t.in(B, S) {
864 // Rule L1, clauses one and two.
865 result[i] = p.embeddingLevel
866
867 // Rule L1, clause three.
868 for j := i - 1; j >= 0; j-- {
869 if isWhitespace(p.initialTypes[j]) { // including format codes
870 result[j] = p.embeddingLevel
871 } else {
872 break
873 }
874 }
875 }
876 }
877
878 // Rule L1, clause four.
879 start := 0
880 for _, limit := range linebreaks {
881 for j := limit - 1; j >= start; j-- {
882 if isWhitespace(p.initialTypes[j]) { // including format codes
883 result[j] = p.embeddingLevel
884 } else {
885 break
886 }
887 }
888 start = limit
889 }
890
891 return result
892}
893
894// getReordering returns the reordering of lines from a visual index to a
895// logical index for line breaks at the given offsets.
896//
897// Lines are concatenated from left to right. So for example, the fifth
898// character from the left on the third line is
899//
900// getReordering(linebreaks)[linebreaks[1] + 4]
901//
902// (linebreaks[1] is the position after the last character of the second
903// line, which is also the index of the first character on the third line,
904// and adding four gets the fifth character from the left).
905//
906// The linebreaks array must include at least one value. The values must be
907// in strictly increasing order (no duplicates) between 1 and the length of
908// the text, inclusive. The last value must be the length of the text.
909// nefergui: retain upstream L2 helper for differential conformance checks.
910func (p *paragraph) getReordering(linebreaks []int) []int {
911 validateLineBreaks(linebreaks, p.Len())
912
913 return computeMultilineReordering(p.getLevels(linebreaks), linebreaks)
914}
915
916// Return multiline reordering array for a given level array. Reordering
917// does not occur across a line break.
918func computeMultilineReordering(levels []level, linebreaks []int) []int {
919 result := make([]int, len(levels))
920
921 start := 0
922 for _, limit := range linebreaks {
923 tempLevels := make([]level, limit-start)
924 copy(tempLevels, levels[start:])
925
926 for j, order := range computeReordering(tempLevels) {
927 result[start+j] = order + start
928 }
929 start = limit
930 }
931 return result
932}
933
934// Return reordering array for a given level array. This reorders a single
935// line. The reordering is a visual to logical map. For example, the
936// leftmost char is string.charAt(order[0]). Rule L2.
937func computeReordering(levels []level) []int {
938 result := make([]int, len(levels))
939 // initialize order
940 for i := range result {
941 result[i] = i
942 }
943
944 // locate highest level found on line.
945 // Note the rules say text, but no reordering across line bounds is
946 // performed, so this is sufficient.
947 highestLevel := level(0)
948 lowestOddLevel := level(maxDepth + 2)
949 for _, level := range levels {
950 if level > highestLevel {
951 highestLevel = level
952 }
953 if level&1 != 0 && level < lowestOddLevel {
954 lowestOddLevel = level
955 }
956 }
957
958 for level := highestLevel; level >= lowestOddLevel; level-- {
959 for i := 0; i < len(levels); i++ {
960 if levels[i] >= level {
961 // find range of text at or above this level
962 start := i
963 limit := i + 1
964 for limit < len(levels) && levels[limit] >= level {
965 limit++
966 }
967
968 for j, k := start, limit-1; j < k; j, k = j+1, k-1 {
969 result[j], result[k] = result[k], result[j]
970 }
971 // skip to end of level run
972 i = limit
973 }
974 }
975 }
976
977 return result
978}
979
980// isWhitespace reports whether the type is considered a whitespace type for the
981// line break rules.
982func isWhitespace(c Class) bool {
983 switch c {
984 case LRE, RLE, LRO, RLO, PDF, LRI, RLI, FSI, PDI, BN, WS:
985 return true
986 }
987 return false
988}
989
990// isRemovedByX9 reports whether the type is one of the types removed in X9.
991func isRemovedByX9(c Class) bool {
992 switch c {
993 case LRE, RLE, LRO, RLO, PDF, BN:
994 return true
995 }
996 return false
997}
998
999// typeForLevel reports the strong type (L or R) corresponding to the level.
1000func typeForLevel(level level) Class {
1001 if (level & 0x1) == 0 {
1002 return L
1003 }
1004 return R
1005}
1006
1007func validateTypes(types []Class) error {
1008 if len(types) == 0 {
1009 return fmt.Errorf("types is null")
1010 }
1011 for i, t := range types[:len(types)-1] {
1012 if t == B {
1013 // nefergui: staticcheck ST1005 requires lowercase error strings.
1014 return fmt.Errorf("b type before end of paragraph at index: %d", i)
1015 }
1016 }
1017 return nil
1018}
1019
1020func validateParagraphEmbeddingLevel(embeddingLevel level) error {
1021 if embeddingLevel != implicitLevel &&
1022 embeddingLevel != 0 &&
1023 embeddingLevel != 1 {
1024 return fmt.Errorf("illegal paragraph embedding level: %d", embeddingLevel)
1025 }
1026 return nil
1027}
1028
1029func validateLineBreaks(linebreaks []int, textLength int) error {
1030 prev := 0
1031 for i, next := range linebreaks {
1032 if next <= prev {
1033 return fmt.Errorf("bad linebreak: %d at index: %d", next, i)
1034 }
1035 prev = next
1036 }
1037 if prev != textLength {
1038 return fmt.Errorf("last linebreak was %d, want %d", prev, textLength)
1039 }
1040 return nil
1041}
1042
1043func validatePbTypes(pairTypes []bracketType) error {
1044 if len(pairTypes) == 0 {
1045 return fmt.Errorf("pairTypes is null")
1046 }
1047 for i, pt := range pairTypes {
1048 switch pt {
1049 case bpNone, bpOpen, bpClose:
1050 default:
1051 return fmt.Errorf("illegal pairType value at %d: %v", i, pairTypes[i])
1052 }
1053 }
1054 return nil
1055}
1056
1057func validatePbValues(pairValues []rune, pairTypes []bracketType) error {
1058 if pairValues == nil {
1059 return fmt.Errorf("pairValues is null")
1060 }
1061 if len(pairTypes) != len(pairValues) {
1062 return fmt.Errorf("pairTypes is different length from pairValues")
1063 }
1064 return nil
1065}