1package xpath 2 3import ( 4 "bytes" 5 "errors" 6 "fmt" 7 "strconv" 8 "unicode" 9) 10 11// A XPath expression token type. 12type itemType int 13 14const ( 15 itemComma itemType = iota // ',' 16 itemSlash // '/' 17 itemAt // '@' 18 itemDot // '.' 19 itemLParens // '(' 20 itemRParens // ')' 21 itemLBracket // '[' 22 itemRBracket // ']' 23 itemStar // '*' 24 itemPlus // '+' 25 itemMinus // '-' 26 itemEq // '=' 27 itemLt // '<' 28 itemGt // '>' 29 itemBang // '!' 30 itemDollar // '$' 31 itemApos // '\'' 32 itemQuote // '"' 33 itemUnion // '|' 34 itemNe // '!=' 35 itemLe // '<=' 36 itemGe // '>=' 37 itemAnd // '&&' 38 itemOr // '||' 39 itemDotDot // '..' 40 itemSlashSlash // '//' 41 itemName // XML Name 42 itemString // Quoted string constant 43 itemNumber // Number constant 44 itemAxe // Axe (like child::) 45 itemEof // END 46) 47 48// A node is an XPath node in the parse tree. 49type node interface { 50 Type() nodeType 51} 52 53// nodeType identifies the type of a parse tree node. 54type nodeType int 55 56func (t nodeType) Type() nodeType { 57 return t 58} 59 60const ( 61 nodeRoot nodeType = iota 62 nodeAxis 63 nodeFilter 64 nodeFunction 65 nodeOperator 66 nodeVariable 67 nodeConstantOperand 68) 69 70type parser struct { 71 r *scanner 72 d int 73} 74 75// newOperatorNode returns new operator node OperatorNode. 76func newOperatorNode(op string, left, right node) node { 77 return &operatorNode{nodeType: nodeOperator, Op: op, Left: left, Right: right} 78} 79 80// newOperand returns new constant operand node OperandNode. 81func newOperandNode(v interface{}) node { 82 return &operandNode{nodeType: nodeConstantOperand, Val: v} 83} 84 85// newAxisNode returns new axis node AxisNode. 86func newAxisNode(axeTyp, localName, prefix, prop string, n node) node { 87 return &axisNode{ 88 nodeType: nodeAxis, 89 LocalName: localName, 90 Prefix: prefix, 91 AxeType: axeTyp, 92 Prop: prop, 93 Input: n, 94 } 95} 96 97// newVariableNode returns new variable node VariableNode. 98func newVariableNode(prefix, name string) node { 99 return &variableNode{nodeType: nodeVariable, Name: name, Prefix: prefix} 100} 101 102// newFilterNode returns a new filter node FilterNode. 103func newFilterNode(n, m node) node { 104 return &filterNode{nodeType: nodeFilter, Input: n, Condition: m} 105} 106 107// newRootNode returns a root node. 108func newRootNode(s string) node { 109 return &rootNode{nodeType: nodeRoot, slash: s} 110} 111 112// newFunctionNode returns function call node. 113func newFunctionNode(name, prefix string, args []node) node { 114 return &functionNode{nodeType: nodeFunction, Prefix: prefix, FuncName: name, Args: args} 115} 116 117// testOp reports whether current item name is an operand op. 118func testOp(r *scanner, op string) bool { 119 return r.typ == itemName && r.prefix == "" && r.name == op 120} 121 122func isPrimaryExpr(r *scanner) bool { 123 switch r.typ { 124 case itemString, itemNumber, itemDollar, itemLParens: 125 return true 126 case itemName: 127 return r.canBeFunc && !isNodeType(r) 128 } 129 return false 130} 131 132func isNodeType(r *scanner) bool { 133 switch r.name { 134 case "node", "text", "processing-instruction", "comment": 135 return r.prefix == "" 136 } 137 return false 138} 139 140func isStep(item itemType) bool { 141 switch item { 142 case itemDot, itemDotDot, itemAt, itemAxe, itemStar, itemName: 143 return true 144 } 145 return false 146} 147 148func checkItem(r *scanner, typ itemType) { 149 if r.typ != typ { 150 panic(fmt.Sprintf("%s has an invalid token", r.text)) 151 } 152} 153 154// parseExpression parsing the expression with input node n. 155func (p *parser) parseExpression(n node) node { 156 if p.d = p.d + 1; p.d > 200 { 157 panic("the xpath query is too complex(depth > 200)") 158 } 159 n = p.parseOrExpr(n) 160 p.d-- 161 return n 162} 163 164// next scanning next item on forward. 165func (p *parser) next() bool { 166 return p.r.nextItem() 167} 168 169func (p *parser) skipItem(typ itemType) { 170 checkItem(p.r, typ) 171 p.next() 172} 173 174// OrExpr ::= AndExpr | OrExpr 'or' AndExpr 175func (p *parser) parseOrExpr(n node) node { 176 opnd := p.parseAndExpr(n) 177 for { 178 if !testOp(p.r, "or") { 179 break 180 } 181 p.next() 182 opnd = newOperatorNode("or", opnd, p.parseAndExpr(n)) 183 } 184 return opnd 185} 186 187// AndExpr ::= EqualityExpr | AndExpr 'and' EqualityExpr 188func (p *parser) parseAndExpr(n node) node { 189 opnd := p.parseEqualityExpr(n) 190 for { 191 if !testOp(p.r, "and") { 192 break 193 } 194 p.next() 195 opnd = newOperatorNode("and", opnd, p.parseEqualityExpr(n)) 196 } 197 return opnd 198} 199 200// EqualityExpr ::= RelationalExpr | EqualityExpr '=' RelationalExpr | EqualityExpr '!=' RelationalExpr 201func (p *parser) parseEqualityExpr(n node) node { 202 opnd := p.parseRelationalExpr(n) 203Loop: 204 for { 205 var op string 206 switch p.r.typ { 207 case itemEq: 208 op = "=" 209 case itemNe: 210 op = "!=" 211 default: 212 break Loop 213 } 214 p.next() 215 opnd = newOperatorNode(op, opnd, p.parseRelationalExpr(n)) 216 } 217 return opnd 218} 219 220// RelationalExpr ::= AdditiveExpr | RelationalExpr '<' AdditiveExpr | RelationalExpr '>' AdditiveExpr 221// | RelationalExpr '<=' AdditiveExpr 222// | RelationalExpr '>=' AdditiveExpr 223func (p *parser) parseRelationalExpr(n node) node { 224 opnd := p.parseAdditiveExpr(n) 225Loop: 226 for { 227 var op string 228 switch p.r.typ { 229 case itemLt: 230 op = "<" 231 case itemGt: 232 op = ">" 233 case itemLe: 234 op = "<=" 235 case itemGe: 236 op = ">=" 237 default: 238 break Loop 239 } 240 p.next() 241 opnd = newOperatorNode(op, opnd, p.parseAdditiveExpr(n)) 242 } 243 return opnd 244} 245 246// AdditiveExpr ::= MultiplicativeExpr | AdditiveExpr '+' MultiplicativeExpr | AdditiveExpr '-' MultiplicativeExpr 247func (p *parser) parseAdditiveExpr(n node) node { 248 opnd := p.parseMultiplicativeExpr(n) 249Loop: 250 for { 251 var op string 252 switch p.r.typ { 253 case itemPlus: 254 op = "+" 255 case itemMinus: 256 op = "-" 257 default: 258 break Loop 259 } 260 p.next() 261 opnd = newOperatorNode(op, opnd, p.parseMultiplicativeExpr(n)) 262 } 263 return opnd 264} 265 266// MultiplicativeExpr ::= UnaryExpr | MultiplicativeExpr MultiplyOperator(*) UnaryExpr 267// | MultiplicativeExpr 'div' UnaryExpr | MultiplicativeExpr 'mod' UnaryExpr 268func (p *parser) parseMultiplicativeExpr(n node) node { 269 opnd := p.parseUnaryExpr(n) 270Loop: 271 for { 272 var op string 273 if p.r.typ == itemStar { 274 op = "*" 275 } else if testOp(p.r, "div") || testOp(p.r, "mod") { 276 op = p.r.name 277 } else { 278 break Loop 279 } 280 p.next() 281 opnd = newOperatorNode(op, opnd, p.parseUnaryExpr(n)) 282 } 283 return opnd 284} 285 286// UnaryExpr ::= UnionExpr | '-' UnaryExpr 287func (p *parser) parseUnaryExpr(n node) node { 288 minus := false 289 // ignore '-' sequence 290 for p.r.typ == itemMinus { 291 p.next() 292 minus = !minus 293 } 294 opnd := p.parseUnionExpr(n) 295 if minus { 296 opnd = newOperatorNode("*", opnd, newOperandNode(float64(-1))) 297 } 298 return opnd 299} 300 301// UnionExpr ::= PathExpr | UnionExpr '|' PathExpr 302func (p *parser) parseUnionExpr(n node) node { 303 opnd := p.parsePathExpr(n) 304Loop: 305 for { 306 if p.r.typ != itemUnion { 307 break Loop 308 } 309 p.next() 310 opnd2 := p.parsePathExpr(n) 311 // Checking the node type that must be is node set type? 312 opnd = newOperatorNode("|", opnd, opnd2) 313 } 314 return opnd 315} 316 317// PathExpr ::= LocationPath | FilterExpr | FilterExpr '/' RelativeLocationPath | FilterExpr '//' RelativeLocationPath 318func (p *parser) parsePathExpr(n node) node { 319 var opnd node 320 if isPrimaryExpr(p.r) { 321 opnd = p.parseFilterExpr(n) 322 switch p.r.typ { 323 case itemSlash: 324 p.next() 325 opnd = p.parseRelativeLocationPath(opnd) 326 case itemSlashSlash: 327 p.next() 328 opnd = p.parseRelativeLocationPath(newAxisNode("descendant-or-self", "", "", "", opnd)) 329 } 330 } else { 331 opnd = p.parseLocationPath(nil) 332 } 333 return opnd 334} 335 336// FilterExpr ::= PrimaryExpr | FilterExpr Predicate 337func (p *parser) parseFilterExpr(n node) node { 338 opnd := p.parsePrimaryExpr(n) 339 if p.r.typ == itemLBracket { 340 opnd = newFilterNode(opnd, p.parsePredicate(opnd)) 341 } 342 return opnd 343} 344 345// Predicate ::= '[' PredicateExpr ']' 346func (p *parser) parsePredicate(n node) node { 347 p.skipItem(itemLBracket) 348 opnd := p.parseExpression(n) 349 p.skipItem(itemRBracket) 350 return opnd 351} 352 353// LocationPath ::= RelativeLocationPath | AbsoluteLocationPath 354func (p *parser) parseLocationPath(n node) (opnd node) { 355 switch p.r.typ { 356 case itemSlash: 357 p.next() 358 opnd = newRootNode("/") 359 if isStep(p.r.typ) { 360 opnd = p.parseRelativeLocationPath(opnd) // ?? child:: or self ?? 361 } 362 case itemSlashSlash: 363 p.next() 364 opnd = newRootNode("//") 365 opnd = p.parseRelativeLocationPath(newAxisNode("descendant-or-self", "", "", "", opnd)) 366 default: 367 opnd = p.parseRelativeLocationPath(n) 368 } 369 return opnd 370} 371 372// RelativeLocationPath ::= Step | RelativeLocationPath '/' Step | AbbreviatedRelativeLocationPath 373func (p *parser) parseRelativeLocationPath(n node) node { 374 opnd := n 375Loop: 376 for { 377 opnd = p.parseStep(opnd) 378 switch p.r.typ { 379 case itemSlashSlash: 380 p.next() 381 opnd = newAxisNode("descendant-or-self", "", "", "", opnd) 382 case itemSlash: 383 p.next() 384 default: 385 break Loop 386 } 387 } 388 return opnd 389} 390 391// Step ::= AxisSpecifier NodeTest Predicate* | AbbreviatedStep 392func (p *parser) parseStep(n node) node { 393 axeTyp := "child" // default axes value. 394 if p.r.typ == itemDot || p.r.typ == itemDotDot { 395 if p.r.typ == itemDot { 396 axeTyp = "self" 397 } else { 398 axeTyp = "parent" 399 } 400 p.next() 401 return newAxisNode(axeTyp, "", "", "", n) 402 } 403 switch p.r.typ { 404 case itemAt: 405 p.next() 406 axeTyp = "attribute" 407 case itemAxe: 408 axeTyp = p.r.name 409 p.next() 410 } 411 opnd := p.parseNodeTest(n, axeTyp) 412 for p.r.typ == itemLBracket { 413 opnd = newFilterNode(opnd, p.parsePredicate(opnd)) 414 } 415 return opnd 416} 417 418// NodeTest ::= NameTest | nodeType '(' ')' | 'processing-instruction' '(' Literal ')' 419func (p *parser) parseNodeTest(n node, axeTyp string) (opnd node) { 420 switch p.r.typ { 421 case itemName: 422 if p.r.canBeFunc && isNodeType(p.r) { 423 var prop string 424 switch p.r.name { 425 case "comment", "text", "processing-instruction", "node": 426 prop = p.r.name 427 } 428 var name string 429 p.next() 430 p.skipItem(itemLParens) 431 if prop == "processing-instruction" && p.r.typ != itemRParens { 432 checkItem(p.r, itemString) 433 name = p.r.strval 434 p.next() 435 } 436 p.skipItem(itemRParens) 437 opnd = newAxisNode(axeTyp, name, "", prop, n) 438 } else { 439 prefix := p.r.prefix 440 name := p.r.name 441 p.next() 442 if p.r.name == "*" { 443 name = "" 444 } 445 opnd = newAxisNode(axeTyp, name, prefix, "", n) 446 } 447 case itemStar: 448 opnd = newAxisNode(axeTyp, "", "", "", n) 449 p.next() 450 default: 451 panic("expression must evaluate to a node-set") 452 } 453 return opnd 454} 455 456// PrimaryExpr ::= VariableReference | '(' Expr ')' | Literal | Number | FunctionCall 457func (p *parser) parsePrimaryExpr(n node) (opnd node) { 458 switch p.r.typ { 459 case itemString: 460 opnd = newOperandNode(p.r.strval) 461 p.next() 462 case itemNumber: 463 opnd = newOperandNode(p.r.numval) 464 p.next() 465 case itemDollar: 466 p.next() 467 checkItem(p.r, itemName) 468 opnd = newVariableNode(p.r.prefix, p.r.name) 469 p.next() 470 case itemLParens: 471 p.next() 472 opnd = p.parseExpression(n) 473 p.skipItem(itemRParens) 474 case itemName: 475 if p.r.canBeFunc && !isNodeType(p.r) { 476 opnd = p.parseMethod(nil) 477 } 478 } 479 return opnd 480} 481 482// FunctionCall ::= FunctionName '(' ( Argument ( ',' Argument )* )? ')' 483func (p *parser) parseMethod(n node) node { 484 var args []node 485 name := p.r.name 486 prefix := p.r.prefix 487 488 p.skipItem(itemName) 489 p.skipItem(itemLParens) 490 if p.r.typ != itemRParens { 491 for { 492 args = append(args, p.parseExpression(n)) 493 if p.r.typ == itemRParens { 494 break 495 } 496 p.skipItem(itemComma) 497 } 498 } 499 p.skipItem(itemRParens) 500 return newFunctionNode(name, prefix, args) 501} 502 503// Parse parsing the XPath express string expr and returns a tree node. 504func parse(expr string) node { 505 r := &scanner{text: expr} 506 r.nextChar() 507 r.nextItem() 508 p := &parser{r: r} 509 return p.parseExpression(nil) 510} 511 512// rootNode holds a top-level node of tree. 513type rootNode struct { 514 nodeType 515 slash string 516} 517 518func (r *rootNode) String() string { 519 return r.slash 520} 521 522// operatorNode holds two Nodes operator. 523type operatorNode struct { 524 nodeType 525 Op string 526 Left, Right node 527} 528 529func (o *operatorNode) String() string { 530 return fmt.Sprintf("%v%s%v", o.Left, o.Op, o.Right) 531} 532 533// axisNode holds a location step. 534type axisNode struct { 535 nodeType 536 Input node 537 Prop string // node-test name.[comment|text|processing-instruction|node] 538 AxeType string // name of the axes.[attribute|ancestor|child|....] 539 LocalName string // local part name of node. 540 Prefix string // prefix name of node. 541} 542 543func (a *axisNode) String() string { 544 var b bytes.Buffer 545 if a.AxeType != "" { 546 b.Write([]byte(a.AxeType + "::")) 547 } 548 if a.Prefix != "" { 549 b.Write([]byte(a.Prefix + ":")) 550 } 551 b.Write([]byte(a.LocalName)) 552 if a.Prop != "" { 553 b.Write([]byte("/" + a.Prop + "()")) 554 } 555 return b.String() 556} 557 558// operandNode holds a constant operand. 559type operandNode struct { 560 nodeType 561 Val interface{} 562} 563 564func (o *operandNode) String() string { 565 return fmt.Sprintf("%v", o.Val) 566} 567 568// filterNode holds a condition filter. 569type filterNode struct { 570 nodeType 571 Input, Condition node 572} 573 574func (f *filterNode) String() string { 575 return fmt.Sprintf("%s[%s]", f.Input, f.Condition) 576} 577 578// variableNode holds a variable. 579type variableNode struct { 580 nodeType 581 Name, Prefix string 582} 583 584func (v *variableNode) String() string { 585 if v.Prefix == "" { 586 return v.Name 587 } 588 return fmt.Sprintf("%s:%s", v.Prefix, v.Name) 589} 590 591// functionNode holds a function call. 592type functionNode struct { 593 nodeType 594 Args []node 595 Prefix string 596 FuncName string // function name 597} 598 599func (f *functionNode) String() string { 600 var b bytes.Buffer 601 // fun(arg1, ..., argn) 602 b.Write([]byte(f.FuncName)) 603 b.Write([]byte("(")) 604 for i, arg := range f.Args { 605 if i > 0 { 606 b.Write([]byte(",")) 607 } 608 b.Write([]byte(fmt.Sprintf("%s", arg))) 609 } 610 b.Write([]byte(")")) 611 return b.String() 612} 613 614type scanner struct { 615 text, name, prefix string 616 617 pos int 618 curr rune 619 typ itemType 620 strval string // text value at current pos 621 numval float64 // number value at current pos 622 canBeFunc bool 623} 624 625func (s *scanner) nextChar() bool { 626 if s.pos >= len(s.text) { 627 s.curr = rune(0) 628 return false 629 } 630 s.curr = rune(s.text[s.pos]) 631 s.pos += 1 632 return true 633} 634 635func (s *scanner) nextItem() bool { 636 s.skipSpace() 637 switch s.curr { 638 case 0: 639 s.typ = itemEof 640 return false 641 case ',', '@', '(', ')', '|', '*', '[', ']', '+', '-', '=', '#', '$': 642 s.typ = asItemType(s.curr) 643 s.nextChar() 644 case '<': 645 s.typ = itemLt 646 s.nextChar() 647 if s.curr == '=' { 648 s.typ = itemLe 649 s.nextChar() 650 } 651 case '>': 652 s.typ = itemGt 653 s.nextChar() 654 if s.curr == '=' { 655 s.typ = itemGe 656 s.nextChar() 657 } 658 case '!': 659 s.typ = itemBang 660 s.nextChar() 661 if s.curr == '=' { 662 s.typ = itemNe 663 s.nextChar() 664 } 665 case '.': 666 s.typ = itemDot 667 s.nextChar() 668 if s.curr == '.' { 669 s.typ = itemDotDot 670 s.nextChar() 671 } else if isDigit(s.curr) { 672 s.typ = itemNumber 673 s.numval = s.scanFraction() 674 } 675 case '/': 676 s.typ = itemSlash 677 s.nextChar() 678 if s.curr == '/' { 679 s.typ = itemSlashSlash 680 s.nextChar() 681 } 682 case '"', '\'': 683 s.typ = itemString 684 s.strval = s.scanString() 685 default: 686 if isDigit(s.curr) { 687 s.typ = itemNumber 688 s.numval = s.scanNumber() 689 } else if isName(s.curr) { 690 s.typ = itemName 691 s.name = s.scanName() 692 s.prefix = "" 693 // "foo:bar" is one itemem not three because it doesn't allow spaces in between 694 // We should distinct it from "foo::" and need process "foo ::" as well 695 if s.curr == ':' { 696 s.nextChar() 697 // can be "foo:bar" or "foo::" 698 if s.curr == ':' { 699 // "foo::" 700 s.nextChar() 701 s.typ = itemAxe 702 } else { // "foo:*", "foo:bar" or "foo: " 703 s.prefix = s.name 704 if s.curr == '*' { 705 s.nextChar() 706 s.name = "*" 707 } else if isName(s.curr) { 708 s.name = s.scanName() 709 } else { 710 panic(fmt.Sprintf("%s has an invalid qualified name.", s.text)) 711 } 712 } 713 } else { 714 s.skipSpace() 715 if s.curr == ':' { 716 s.nextChar() 717 // it can be "foo ::" or just "foo :" 718 if s.curr == ':' { 719 s.nextChar() 720 s.typ = itemAxe 721 } else { 722 panic(fmt.Sprintf("%s has an invalid qualified name.", s.text)) 723 } 724 } 725 } 726 s.skipSpace() 727 s.canBeFunc = s.curr == '(' 728 } else { 729 panic(fmt.Sprintf("%s has an invalid token.", s.text)) 730 } 731 } 732 return true 733} 734 735func (s *scanner) skipSpace() { 736Loop: 737 for { 738 if !unicode.IsSpace(s.curr) || !s.nextChar() { 739 break Loop 740 } 741 } 742} 743 744func (s *scanner) scanFraction() float64 { 745 var ( 746 i = s.pos - 2 747 c = 1 // '.' 748 ) 749 for isDigit(s.curr) { 750 s.nextChar() 751 c++ 752 } 753 v, err := strconv.ParseFloat(s.text[i:i+c], 64) 754 if err != nil { 755 panic(fmt.Errorf("xpath: scanFraction parse float got error: %v", err)) 756 } 757 return v 758} 759 760func (s *scanner) scanNumber() float64 { 761 var ( 762 c int 763 i = s.pos - 1 764 ) 765 for isDigit(s.curr) { 766 s.nextChar() 767 c++ 768 } 769 if s.curr == '.' { 770 s.nextChar() 771 c++ 772 for isDigit(s.curr) { 773 s.nextChar() 774 c++ 775 } 776 } 777 v, err := strconv.ParseFloat(s.text[i:i+c], 64) 778 if err != nil { 779 panic(fmt.Errorf("xpath: scanNumber parse float got error: %v", err)) 780 } 781 return v 782} 783 784func (s *scanner) scanString() string { 785 var ( 786 c = 0 787 end = s.curr 788 ) 789 s.nextChar() 790 i := s.pos - 1 791 for s.curr != end { 792 if !s.nextChar() { 793 panic(errors.New("xpath: scanString got unclosed string")) 794 } 795 c++ 796 } 797 s.nextChar() 798 return s.text[i : i+c] 799} 800 801func (s *scanner) scanName() string { 802 var ( 803 c int 804 i = s.pos - 1 805 ) 806 for isName(s.curr) { 807 c++ 808 if !s.nextChar() { 809 break 810 } 811 } 812 return s.text[i : i+c] 813} 814 815func isName(r rune) bool { 816 return string(r) != ":" && string(r) != "/" && 817 (unicode.Is(first, r) || unicode.Is(second, r) || string(r) == "*") 818} 819 820func isDigit(r rune) bool { 821 return unicode.IsDigit(r) 822} 823 824func asItemType(r rune) itemType { 825 switch r { 826 case ',': 827 return itemComma 828 case '@': 829 return itemAt 830 case '(': 831 return itemLParens 832 case ')': 833 return itemRParens 834 case '|': 835 return itemUnion 836 case '*': 837 return itemStar 838 case '[': 839 return itemLBracket 840 case ']': 841 return itemRBracket 842 case '+': 843 return itemPlus 844 case '-': 845 return itemMinus 846 case '=': 847 return itemEq 848 case '$': 849 return itemDollar 850 } 851 panic(fmt.Errorf("unknown item: %v", r)) 852} 853 854var first = &unicode.RangeTable{ 855 R16: []unicode.Range16{ 856 {0x003A, 0x003A, 1}, 857 {0x0041, 0x005A, 1}, 858 {0x005F, 0x005F, 1}, 859 {0x0061, 0x007A, 1}, 860 {0x00C0, 0x00D6, 1}, 861 {0x00D8, 0x00F6, 1}, 862 {0x00F8, 0x00FF, 1}, 863 {0x0100, 0x0131, 1}, 864 {0x0134, 0x013E, 1}, 865 {0x0141, 0x0148, 1}, 866 {0x014A, 0x017E, 1}, 867 {0x0180, 0x01C3, 1}, 868 {0x01CD, 0x01F0, 1}, 869 {0x01F4, 0x01F5, 1}, 870 {0x01FA, 0x0217, 1}, 871 {0x0250, 0x02A8, 1}, 872 {0x02BB, 0x02C1, 1}, 873 {0x0386, 0x0386, 1}, 874 {0x0388, 0x038A, 1}, 875 {0x038C, 0x038C, 1}, 876 {0x038E, 0x03A1, 1}, 877 {0x03A3, 0x03CE, 1}, 878 {0x03D0, 0x03D6, 1}, 879 {0x03DA, 0x03E0, 2}, 880 {0x03E2, 0x03F3, 1}, 881 {0x0401, 0x040C, 1}, 882 {0x040E, 0x044F, 1}, 883 {0x0451, 0x045C, 1}, 884 {0x045E, 0x0481, 1}, 885 {0x0490, 0x04C4, 1}, 886 {0x04C7, 0x04C8, 1}, 887 {0x04CB, 0x04CC, 1}, 888 {0x04D0, 0x04EB, 1}, 889 {0x04EE, 0x04F5, 1}, 890 {0x04F8, 0x04F9, 1}, 891 {0x0531, 0x0556, 1}, 892 {0x0559, 0x0559, 1}, 893 {0x0561, 0x0586, 1}, 894 {0x05D0, 0x05EA, 1}, 895 {0x05F0, 0x05F2, 1}, 896 {0x0621, 0x063A, 1}, 897 {0x0641, 0x064A, 1}, 898 {0x0671, 0x06B7, 1}, 899 {0x06BA, 0x06BE, 1}, 900 {0x06C0, 0x06CE, 1}, 901 {0x06D0, 0x06D3, 1}, 902 {0x06D5, 0x06D5, 1}, 903 {0x06E5, 0x06E6, 1}, 904 {0x0905, 0x0939, 1}, 905 {0x093D, 0x093D, 1}, 906 {0x0958, 0x0961, 1}, 907 {0x0985, 0x098C, 1}, 908 {0x098F, 0x0990, 1}, 909 {0x0993, 0x09A8, 1}, 910 {0x09AA, 0x09B0, 1}, 911 {0x09B2, 0x09B2, 1}, 912 {0x09B6, 0x09B9, 1}, 913 {0x09DC, 0x09DD, 1}, 914 {0x09DF, 0x09E1, 1}, 915 {0x09F0, 0x09F1, 1}, 916 {0x0A05, 0x0A0A, 1}, 917 {0x0A0F, 0x0A10, 1}, 918 {0x0A13, 0x0A28, 1}, 919 {0x0A2A, 0x0A30, 1}, 920 {0x0A32, 0x0A33, 1}, 921 {0x0A35, 0x0A36, 1}, 922 {0x0A38, 0x0A39, 1}, 923 {0x0A59, 0x0A5C, 1}, 924 {0x0A5E, 0x0A5E, 1}, 925 {0x0A72, 0x0A74, 1}, 926 {0x0A85, 0x0A8B, 1}, 927 {0x0A8D, 0x0A8D, 1}, 928 {0x0A8F, 0x0A91, 1}, 929 {0x0A93, 0x0AA8, 1}, 930 {0x0AAA, 0x0AB0, 1}, 931 {0x0AB2, 0x0AB3, 1}, 932 {0x0AB5, 0x0AB9, 1}, 933 {0x0ABD, 0x0AE0, 0x23}, 934 {0x0B05, 0x0B0C, 1}, 935 {0x0B0F, 0x0B10, 1}, 936 {0x0B13, 0x0B28, 1}, 937 {0x0B2A, 0x0B30, 1}, 938 {0x0B32, 0x0B33, 1}, 939 {0x0B36, 0x0B39, 1}, 940 {0x0B3D, 0x0B3D, 1}, 941 {0x0B5C, 0x0B5D, 1}, 942 {0x0B5F, 0x0B61, 1}, 943 {0x0B85, 0x0B8A, 1}, 944 {0x0B8E, 0x0B90, 1}, 945 {0x0B92, 0x0B95, 1}, 946 {0x0B99, 0x0B9A, 1}, 947 {0x0B9C, 0x0B9C, 1}, 948 {0x0B9E, 0x0B9F, 1}, 949 {0x0BA3, 0x0BA4, 1}, 950 {0x0BA8, 0x0BAA, 1}, 951 {0x0BAE, 0x0BB5, 1}, 952 {0x0BB7, 0x0BB9, 1}, 953 {0x0C05, 0x0C0C, 1}, 954 {0x0C0E, 0x0C10, 1}, 955 {0x0C12, 0x0C28, 1}, 956 {0x0C2A, 0x0C33, 1}, 957 {0x0C35, 0x0C39, 1}, 958 {0x0C60, 0x0C61, 1}, 959 {0x0C85, 0x0C8C, 1}, 960 {0x0C8E, 0x0C90, 1}, 961 {0x0C92, 0x0CA8, 1}, 962 {0x0CAA, 0x0CB3, 1}, 963 {0x0CB5, 0x0CB9, 1}, 964 {0x0CDE, 0x0CDE, 1}, 965 {0x0CE0, 0x0CE1, 1}, 966 {0x0D05, 0x0D0C, 1}, 967 {0x0D0E, 0x0D10, 1}, 968 {0x0D12, 0x0D28, 1}, 969 {0x0D2A, 0x0D39, 1}, 970 {0x0D60, 0x0D61, 1}, 971 {0x0E01, 0x0E2E, 1}, 972 {0x0E30, 0x0E30, 1}, 973 {0x0E32, 0x0E33, 1}, 974 {0x0E40, 0x0E45, 1}, 975 {0x0E81, 0x0E82, 1}, 976 {0x0E84, 0x0E84, 1}, 977 {0x0E87, 0x0E88, 1}, 978 {0x0E8A, 0x0E8D, 3}, 979 {0x0E94, 0x0E97, 1}, 980 {0x0E99, 0x0E9F, 1}, 981 {0x0EA1, 0x0EA3, 1}, 982 {0x0EA5, 0x0EA7, 2}, 983 {0x0EAA, 0x0EAB, 1}, 984 {0x0EAD, 0x0EAE, 1}, 985 {0x0EB0, 0x0EB0, 1}, 986 {0x0EB2, 0x0EB3, 1}, 987 {0x0EBD, 0x0EBD, 1}, 988 {0x0EC0, 0x0EC4, 1}, 989 {0x0F40, 0x0F47, 1}, 990 {0x0F49, 0x0F69, 1}, 991 {0x10A0, 0x10C5, 1}, 992 {0x10D0, 0x10F6, 1}, 993 {0x1100, 0x1100, 1}, 994 {0x1102, 0x1103, 1}, 995 {0x1105, 0x1107, 1}, 996 {0x1109, 0x1109, 1}, 997 {0x110B, 0x110C, 1}, 998 {0x110E, 0x1112, 1}, 999 {0x113C, 0x1140, 2}, 1000 {0x114C, 0x1150, 2}, 1001 {0x1154, 0x1155, 1}, 1002 {0x1159, 0x1159, 1}, 1003 {0x115F, 0x1161, 1}, 1004 {0x1163, 0x1169, 2}, 1005 {0x116D, 0x116E, 1}, 1006 {0x1172, 0x1173, 1}, 1007 {0x1175, 0x119E, 0x119E - 0x1175}, 1008 {0x11A8, 0x11AB, 0x11AB - 0x11A8}, 1009 {0x11AE, 0x11AF, 1}, 1010 {0x11B7, 0x11B8, 1}, 1011 {0x11BA, 0x11BA, 1}, 1012 {0x11BC, 0x11C2, 1}, 1013 {0x11EB, 0x11F0, 0x11F0 - 0x11EB}, 1014 {0x11F9, 0x11F9, 1}, 1015 {0x1E00, 0x1E9B, 1}, 1016 {0x1EA0, 0x1EF9, 1}, 1017 {0x1F00, 0x1F15, 1}, 1018 {0x1F18, 0x1F1D, 1}, 1019 {0x1F20, 0x1F45, 1}, 1020 {0x1F48, 0x1F4D, 1}, 1021 {0x1F50, 0x1F57, 1}, 1022 {0x1F59, 0x1F5B, 0x1F5B - 0x1F59}, 1023 {0x1F5D, 0x1F5D, 1}, 1024 {0x1F5F, 0x1F7D, 1}, 1025 {0x1F80, 0x1FB4, 1}, 1026 {0x1FB6, 0x1FBC, 1}, 1027 {0x1FBE, 0x1FBE, 1}, 1028 {0x1FC2, 0x1FC4, 1}, 1029 {0x1FC6, 0x1FCC, 1}, 1030 {0x1FD0, 0x1FD3, 1}, 1031 {0x1FD6, 0x1FDB, 1}, 1032 {0x1FE0, 0x1FEC, 1}, 1033 {0x1FF2, 0x1FF4, 1}, 1034 {0x1FF6, 0x1FFC, 1}, 1035 {0x2126, 0x2126, 1}, 1036 {0x212A, 0x212B, 1}, 1037 {0x212E, 0x212E, 1}, 1038 {0x2180, 0x2182, 1}, 1039 {0x3007, 0x3007, 1}, 1040 {0x3021, 0x3029, 1}, 1041 {0x3041, 0x3094, 1}, 1042 {0x30A1, 0x30FA, 1}, 1043 {0x3105, 0x312C, 1}, 1044 {0x4E00, 0x9FA5, 1}, 1045 {0xAC00, 0xD7A3, 1}, 1046 }, 1047} 1048 1049var second = &unicode.RangeTable{ 1050 R16: []unicode.Range16{ 1051 {0x002D, 0x002E, 1}, 1052 {0x0030, 0x0039, 1}, 1053 {0x00B7, 0x00B7, 1}, 1054 {0x02D0, 0x02D1, 1}, 1055 {0x0300, 0x0345, 1}, 1056 {0x0360, 0x0361, 1}, 1057 {0x0387, 0x0387, 1}, 1058 {0x0483, 0x0486, 1}, 1059 {0x0591, 0x05A1, 1}, 1060 {0x05A3, 0x05B9, 1}, 1061 {0x05BB, 0x05BD, 1}, 1062 {0x05BF, 0x05BF, 1}, 1063 {0x05C1, 0x05C2, 1}, 1064 {0x05C4, 0x0640, 0x0640 - 0x05C4}, 1065 {0x064B, 0x0652, 1}, 1066 {0x0660, 0x0669, 1}, 1067 {0x0670, 0x0670, 1}, 1068 {0x06D6, 0x06DC, 1}, 1069 {0x06DD, 0x06DF, 1}, 1070 {0x06E0, 0x06E4, 1}, 1071 {0x06E7, 0x06E8, 1}, 1072 {0x06EA, 0x06ED, 1}, 1073 {0x06F0, 0x06F9, 1}, 1074 {0x0901, 0x0903, 1}, 1075 {0x093C, 0x093C, 1}, 1076 {0x093E, 0x094C, 1}, 1077 {0x094D, 0x094D, 1}, 1078 {0x0951, 0x0954, 1}, 1079 {0x0962, 0x0963, 1}, 1080 {0x0966, 0x096F, 1}, 1081 {0x0981, 0x0983, 1}, 1082 {0x09BC, 0x09BC, 1}, 1083 {0x09BE, 0x09BF, 1}, 1084 {0x09C0, 0x09C4, 1}, 1085 {0x09C7, 0x09C8, 1}, 1086 {0x09CB, 0x09CD, 1}, 1087 {0x09D7, 0x09D7, 1}, 1088 {0x09E2, 0x09E3, 1}, 1089 {0x09E6, 0x09EF, 1}, 1090 {0x0A02, 0x0A3C, 0x3A}, 1091 {0x0A3E, 0x0A3F, 1}, 1092 {0x0A40, 0x0A42, 1}, 1093 {0x0A47, 0x0A48, 1}, 1094 {0x0A4B, 0x0A4D, 1}, 1095 {0x0A66, 0x0A6F, 1}, 1096 {0x0A70, 0x0A71, 1}, 1097 {0x0A81, 0x0A83, 1}, 1098 {0x0ABC, 0x0ABC, 1}, 1099 {0x0ABE, 0x0AC5, 1}, 1100 {0x0AC7, 0x0AC9, 1}, 1101 {0x0ACB, 0x0ACD, 1}, 1102 {0x0AE6, 0x0AEF, 1}, 1103 {0x0B01, 0x0B03, 1}, 1104 {0x0B3C, 0x0B3C, 1}, 1105 {0x0B3E, 0x0B43, 1}, 1106 {0x0B47, 0x0B48, 1}, 1107 {0x0B4B, 0x0B4D, 1}, 1108 {0x0B56, 0x0B57, 1}, 1109 {0x0B66, 0x0B6F, 1}, 1110 {0x0B82, 0x0B83, 1}, 1111 {0x0BBE, 0x0BC2, 1}, 1112 {0x0BC6, 0x0BC8, 1}, 1113 {0x0BCA, 0x0BCD, 1}, 1114 {0x0BD7, 0x0BD7, 1}, 1115 {0x0BE7, 0x0BEF, 1}, 1116 {0x0C01, 0x0C03, 1}, 1117 {0x0C3E, 0x0C44, 1}, 1118 {0x0C46, 0x0C48, 1}, 1119 {0x0C4A, 0x0C4D, 1}, 1120 {0x0C55, 0x0C56, 1}, 1121 {0x0C66, 0x0C6F, 1}, 1122 {0x0C82, 0x0C83, 1}, 1123 {0x0CBE, 0x0CC4, 1}, 1124 {0x0CC6, 0x0CC8, 1}, 1125 {0x0CCA, 0x0CCD, 1}, 1126 {0x0CD5, 0x0CD6, 1}, 1127 {0x0CE6, 0x0CEF, 1}, 1128 {0x0D02, 0x0D03, 1}, 1129 {0x0D3E, 0x0D43, 1}, 1130 {0x0D46, 0x0D48, 1}, 1131 {0x0D4A, 0x0D4D, 1}, 1132 {0x0D57, 0x0D57, 1}, 1133 {0x0D66, 0x0D6F, 1}, 1134 {0x0E31, 0x0E31, 1}, 1135 {0x0E34, 0x0E3A, 1}, 1136 {0x0E46, 0x0E46, 1}, 1137 {0x0E47, 0x0E4E, 1}, 1138 {0x0E50, 0x0E59, 1}, 1139 {0x0EB1, 0x0EB1, 1}, 1140 {0x0EB4, 0x0EB9, 1}, 1141 {0x0EBB, 0x0EBC, 1}, 1142 {0x0EC6, 0x0EC6, 1}, 1143 {0x0EC8, 0x0ECD, 1}, 1144 {0x0ED0, 0x0ED9, 1}, 1145 {0x0F18, 0x0F19, 1}, 1146 {0x0F20, 0x0F29, 1}, 1147 {0x0F35, 0x0F39, 2}, 1148 {0x0F3E, 0x0F3F, 1}, 1149 {0x0F71, 0x0F84, 1}, 1150 {0x0F86, 0x0F8B, 1}, 1151 {0x0F90, 0x0F95, 1}, 1152 {0x0F97, 0x0F97, 1}, 1153 {0x0F99, 0x0FAD, 1}, 1154 {0x0FB1, 0x0FB7, 1}, 1155 {0x0FB9, 0x0FB9, 1}, 1156 {0x20D0, 0x20DC, 1}, 1157 {0x20E1, 0x3005, 0x3005 - 0x20E1}, 1158 {0x302A, 0x302F, 1}, 1159 {0x3031, 0x3035, 1}, 1160 {0x3099, 0x309A, 1}, 1161 {0x309D, 0x309E, 1}, 1162 {0x30FC, 0x30FE, 1}, 1163 }, 1164} 1165