/usr/share/gocode/src/golang.org/x/text/unicode/bidi/core.go is in golang-golang-x-text-dev 0.0~git20170627.0.6353ef0-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 | // 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")
}
}
|