1package xpath 2 3import ( 4 "bytes" 5 "fmt" 6 "hash/fnv" 7 "reflect" 8) 9 10type iterator interface { 11 Current() NodeNavigator 12} 13 14// An XPath query interface. 15type query interface { 16 // Select traversing iterator returns a query matched node NodeNavigator. 17 Select(iterator) NodeNavigator 18 19 // Evaluate evaluates query and returns values of the current query. 20 Evaluate(iterator) interface{} 21 22 Clone() query 23} 24 25// contextQuery is returns current node on the iterator object query. 26type contextQuery struct { 27 count int 28 Root bool // Moving to root-level node in the current context iterator. 29} 30 31func (c *contextQuery) Select(t iterator) (n NodeNavigator) { 32 if c.count == 0 { 33 c.count++ 34 n = t.Current().Copy() 35 if c.Root { 36 n.MoveToRoot() 37 } 38 } 39 return n 40} 41 42func (c *contextQuery) Evaluate(iterator) interface{} { 43 c.count = 0 44 return c 45} 46 47func (c *contextQuery) Clone() query { 48 return &contextQuery{count: 0, Root: c.Root} 49} 50 51// ancestorQuery is an XPath ancestor node query.(ancestor::*|ancestor-self::*) 52type ancestorQuery struct { 53 iterator func() NodeNavigator 54 55 Self bool 56 Input query 57 Predicate func(NodeNavigator) bool 58} 59 60func (a *ancestorQuery) Select(t iterator) NodeNavigator { 61 for { 62 if a.iterator == nil { 63 node := a.Input.Select(t) 64 if node == nil { 65 return nil 66 } 67 first := true 68 a.iterator = func() NodeNavigator { 69 if first && a.Self { 70 first = false 71 if a.Predicate(node) { 72 return node 73 } 74 } 75 for node.MoveToParent() { 76 if !a.Predicate(node) { 77 continue 78 } 79 return node 80 } 81 return nil 82 } 83 } 84 85 if node := a.iterator(); node != nil { 86 return node 87 } 88 a.iterator = nil 89 } 90} 91 92func (a *ancestorQuery) Evaluate(t iterator) interface{} { 93 a.Input.Evaluate(t) 94 a.iterator = nil 95 return a 96} 97 98func (a *ancestorQuery) Test(n NodeNavigator) bool { 99 return a.Predicate(n) 100} 101 102func (a *ancestorQuery) Clone() query { 103 return &ancestorQuery{Self: a.Self, Input: a.Input.Clone(), Predicate: a.Predicate} 104} 105 106// attributeQuery is an XPath attribute node query.(@*) 107type attributeQuery struct { 108 iterator func() NodeNavigator 109 110 Input query 111 Predicate func(NodeNavigator) bool 112} 113 114func (a *attributeQuery) Select(t iterator) NodeNavigator { 115 for { 116 if a.iterator == nil { 117 node := a.Input.Select(t) 118 if node == nil { 119 return nil 120 } 121 node = node.Copy() 122 a.iterator = func() NodeNavigator { 123 for { 124 onAttr := node.MoveToNextAttribute() 125 if !onAttr { 126 return nil 127 } 128 if a.Predicate(node) { 129 return node 130 } 131 } 132 } 133 } 134 135 if node := a.iterator(); node != nil { 136 return node 137 } 138 a.iterator = nil 139 } 140} 141 142func (a *attributeQuery) Evaluate(t iterator) interface{} { 143 a.Input.Evaluate(t) 144 a.iterator = nil 145 return a 146} 147 148func (a *attributeQuery) Test(n NodeNavigator) bool { 149 return a.Predicate(n) 150} 151 152func (a *attributeQuery) Clone() query { 153 return &attributeQuery{Input: a.Input.Clone(), Predicate: a.Predicate} 154} 155 156// childQuery is an XPath child node query.(child::*) 157type childQuery struct { 158 posit int 159 iterator func() NodeNavigator 160 161 Input query 162 Predicate func(NodeNavigator) bool 163} 164 165func (c *childQuery) Select(t iterator) NodeNavigator { 166 for { 167 if c.iterator == nil { 168 c.posit = 0 169 node := c.Input.Select(t) 170 if node == nil { 171 return nil 172 } 173 node = node.Copy() 174 first := true 175 c.iterator = func() NodeNavigator { 176 for { 177 if (first && !node.MoveToChild()) || (!first && !node.MoveToNext()) { 178 return nil 179 } 180 first = false 181 if c.Predicate(node) { 182 return node 183 } 184 } 185 } 186 } 187 188 if node := c.iterator(); node != nil { 189 c.posit++ 190 return node 191 } 192 c.iterator = nil 193 } 194} 195 196func (c *childQuery) Evaluate(t iterator) interface{} { 197 c.Input.Evaluate(t) 198 c.iterator = nil 199 return c 200} 201 202func (c *childQuery) Test(n NodeNavigator) bool { 203 return c.Predicate(n) 204} 205 206func (c *childQuery) Clone() query { 207 return &childQuery{Input: c.Input.Clone(), Predicate: c.Predicate} 208} 209 210// position returns a position of current NodeNavigator. 211func (c *childQuery) position() int { 212 return c.posit 213} 214 215// descendantQuery is an XPath descendant node query.(descendant::* | descendant-or-self::*) 216type descendantQuery struct { 217 iterator func() NodeNavigator 218 posit int 219 220 Self bool 221 Input query 222 Predicate func(NodeNavigator) bool 223} 224 225func (d *descendantQuery) Select(t iterator) NodeNavigator { 226 for { 227 if d.iterator == nil { 228 d.posit = 0 229 node := d.Input.Select(t) 230 if node == nil { 231 return nil 232 } 233 node = node.Copy() 234 level := 0 235 first := true 236 d.iterator = func() NodeNavigator { 237 if first && d.Self { 238 first = false 239 if d.Predicate(node) { 240 return node 241 } 242 } 243 244 for { 245 if node.MoveToChild() { 246 level++ 247 } else { 248 for { 249 if level == 0 { 250 return nil 251 } 252 if node.MoveToNext() { 253 break 254 } 255 node.MoveToParent() 256 level-- 257 } 258 } 259 if d.Predicate(node) { 260 return node 261 } 262 } 263 } 264 } 265 266 if node := d.iterator(); node != nil { 267 d.posit++ 268 return node 269 } 270 d.iterator = nil 271 } 272} 273 274func (d *descendantQuery) Evaluate(t iterator) interface{} { 275 d.Input.Evaluate(t) 276 d.iterator = nil 277 return d 278} 279 280func (d *descendantQuery) Test(n NodeNavigator) bool { 281 return d.Predicate(n) 282} 283 284// position returns a position of current NodeNavigator. 285func (d *descendantQuery) position() int { 286 return d.posit 287} 288 289func (d *descendantQuery) Clone() query { 290 return &descendantQuery{Self: d.Self, Input: d.Input.Clone(), Predicate: d.Predicate} 291} 292 293// followingQuery is an XPath following node query.(following::*|following-sibling::*) 294type followingQuery struct { 295 iterator func() NodeNavigator 296 297 Input query 298 Sibling bool // The matching sibling node of current node. 299 Predicate func(NodeNavigator) bool 300} 301 302func (f *followingQuery) Select(t iterator) NodeNavigator { 303 for { 304 if f.iterator == nil { 305 node := f.Input.Select(t) 306 if node == nil { 307 return nil 308 } 309 node = node.Copy() 310 if f.Sibling { 311 f.iterator = func() NodeNavigator { 312 for { 313 if !node.MoveToNext() { 314 return nil 315 } 316 if f.Predicate(node) { 317 return node 318 } 319 } 320 } 321 } else { 322 var q query // descendant query 323 f.iterator = func() NodeNavigator { 324 for { 325 if q == nil { 326 for !node.MoveToNext() { 327 if !node.MoveToParent() { 328 return nil 329 } 330 } 331 q = &descendantQuery{ 332 Self: true, 333 Input: &contextQuery{}, 334 Predicate: f.Predicate, 335 } 336 t.Current().MoveTo(node) 337 } 338 if node := q.Select(t); node != nil { 339 return node 340 } 341 q = nil 342 } 343 } 344 } 345 } 346 347 if node := f.iterator(); node != nil { 348 return node 349 } 350 f.iterator = nil 351 } 352} 353 354func (f *followingQuery) Evaluate(t iterator) interface{} { 355 f.Input.Evaluate(t) 356 return f 357} 358 359func (f *followingQuery) Test(n NodeNavigator) bool { 360 return f.Predicate(n) 361} 362 363func (f *followingQuery) Clone() query { 364 return &followingQuery{Input: f.Input.Clone(), Sibling: f.Sibling, Predicate: f.Predicate} 365} 366 367// precedingQuery is an XPath preceding node query.(preceding::*) 368type precedingQuery struct { 369 iterator func() NodeNavigator 370 Input query 371 Sibling bool // The matching sibling node of current node. 372 Predicate func(NodeNavigator) bool 373} 374 375func (p *precedingQuery) Select(t iterator) NodeNavigator { 376 for { 377 if p.iterator == nil { 378 node := p.Input.Select(t) 379 if node == nil { 380 return nil 381 } 382 node = node.Copy() 383 if p.Sibling { 384 p.iterator = func() NodeNavigator { 385 for { 386 for !node.MoveToPrevious() { 387 return nil 388 } 389 if p.Predicate(node) { 390 return node 391 } 392 } 393 } 394 } else { 395 var q query 396 p.iterator = func() NodeNavigator { 397 for { 398 if q == nil { 399 for !node.MoveToPrevious() { 400 if !node.MoveToParent() { 401 return nil 402 } 403 } 404 q = &descendantQuery{ 405 Self: true, 406 Input: &contextQuery{}, 407 Predicate: p.Predicate, 408 } 409 t.Current().MoveTo(node) 410 } 411 if node := q.Select(t); node != nil { 412 return node 413 } 414 q = nil 415 } 416 } 417 } 418 } 419 if node := p.iterator(); node != nil { 420 return node 421 } 422 p.iterator = nil 423 } 424} 425 426func (p *precedingQuery) Evaluate(t iterator) interface{} { 427 p.Input.Evaluate(t) 428 return p 429} 430 431func (p *precedingQuery) Test(n NodeNavigator) bool { 432 return p.Predicate(n) 433} 434 435func (p *precedingQuery) Clone() query { 436 return &precedingQuery{Input: p.Input.Clone(), Sibling: p.Sibling, Predicate: p.Predicate} 437} 438 439// parentQuery is an XPath parent node query.(parent::*) 440type parentQuery struct { 441 Input query 442 Predicate func(NodeNavigator) bool 443} 444 445func (p *parentQuery) Select(t iterator) NodeNavigator { 446 for { 447 node := p.Input.Select(t) 448 if node == nil { 449 return nil 450 } 451 node = node.Copy() 452 if node.MoveToParent() && p.Predicate(node) { 453 return node 454 } 455 } 456} 457 458func (p *parentQuery) Evaluate(t iterator) interface{} { 459 p.Input.Evaluate(t) 460 return p 461} 462 463func (p *parentQuery) Clone() query { 464 return &parentQuery{Input: p.Input.Clone(), Predicate: p.Predicate} 465} 466 467func (p *parentQuery) Test(n NodeNavigator) bool { 468 return p.Predicate(n) 469} 470 471// selfQuery is an Self node query.(self::*) 472type selfQuery struct { 473 Input query 474 Predicate func(NodeNavigator) bool 475} 476 477func (s *selfQuery) Select(t iterator) NodeNavigator { 478 for { 479 node := s.Input.Select(t) 480 if node == nil { 481 return nil 482 } 483 484 if s.Predicate(node) { 485 return node 486 } 487 } 488} 489 490func (s *selfQuery) Evaluate(t iterator) interface{} { 491 s.Input.Evaluate(t) 492 return s 493} 494 495func (s *selfQuery) Test(n NodeNavigator) bool { 496 return s.Predicate(n) 497} 498 499func (s *selfQuery) Clone() query { 500 return &selfQuery{Input: s.Input.Clone(), Predicate: s.Predicate} 501} 502 503// filterQuery is an XPath query for predicate filter. 504type filterQuery struct { 505 Input query 506 Predicate query 507} 508 509func (f *filterQuery) do(t iterator) bool { 510 val := reflect.ValueOf(f.Predicate.Evaluate(t)) 511 switch val.Kind() { 512 case reflect.Bool: 513 return val.Bool() 514 case reflect.String: 515 return len(val.String()) > 0 516 case reflect.Float64: 517 pt := float64(getNodePosition(f.Input)) 518 return int(val.Float()) == int(pt) 519 default: 520 if q, ok := f.Predicate.(query); ok { 521 return q.Select(t) != nil 522 } 523 } 524 return false 525} 526 527func (f *filterQuery) Select(t iterator) NodeNavigator { 528 for { 529 node := f.Input.Select(t) 530 if node == nil { 531 return node 532 } 533 node = node.Copy() 534 //fmt.Println(node.LocalName()) 535 536 t.Current().MoveTo(node) 537 if f.do(t) { 538 return node 539 } 540 } 541} 542 543func (f *filterQuery) Evaluate(t iterator) interface{} { 544 f.Input.Evaluate(t) 545 return f 546} 547 548func (f *filterQuery) Clone() query { 549 return &filterQuery{Input: f.Input.Clone(), Predicate: f.Predicate.Clone()} 550} 551 552// functionQuery is an XPath function that call a function to returns 553// value of current NodeNavigator node. 554type functionQuery struct { 555 Input query // Node Set 556 Func func(query, iterator) interface{} // The xpath function. 557} 558 559func (f *functionQuery) Select(t iterator) NodeNavigator { 560 return nil 561} 562 563// Evaluate call a specified function that will returns the 564// following value type: number,string,boolean. 565func (f *functionQuery) Evaluate(t iterator) interface{} { 566 return f.Func(f.Input, t) 567} 568 569func (f *functionQuery) Clone() query { 570 return &functionQuery{Input: f.Input.Clone(), Func: f.Func} 571} 572 573// constantQuery is an XPath constant operand. 574type constantQuery struct { 575 Val interface{} 576} 577 578func (c *constantQuery) Select(t iterator) NodeNavigator { 579 return nil 580} 581 582func (c *constantQuery) Evaluate(t iterator) interface{} { 583 return c.Val 584} 585 586func (c *constantQuery) Clone() query { 587 return c 588} 589 590// logicalQuery is an XPath logical expression. 591type logicalQuery struct { 592 Left, Right query 593 594 Do func(iterator, interface{}, interface{}) interface{} 595} 596 597func (l *logicalQuery) Select(t iterator) NodeNavigator { 598 // When a XPath expr is logical expression. 599 node := t.Current().Copy() 600 val := l.Evaluate(t) 601 switch val.(type) { 602 case bool: 603 if val.(bool) == true { 604 return node 605 } 606 } 607 return nil 608} 609 610func (l *logicalQuery) Evaluate(t iterator) interface{} { 611 m := l.Left.Evaluate(t) 612 n := l.Right.Evaluate(t) 613 return l.Do(t, m, n) 614} 615 616func (l *logicalQuery) Clone() query { 617 return &logicalQuery{Left: l.Left.Clone(), Right: l.Right.Clone(), Do: l.Do} 618} 619 620// numericQuery is an XPath numeric operator expression. 621type numericQuery struct { 622 Left, Right query 623 624 Do func(interface{}, interface{}) interface{} 625} 626 627func (n *numericQuery) Select(t iterator) NodeNavigator { 628 return nil 629} 630 631func (n *numericQuery) Evaluate(t iterator) interface{} { 632 m := n.Left.Evaluate(t) 633 k := n.Right.Evaluate(t) 634 return n.Do(m, k) 635} 636 637func (n *numericQuery) Clone() query { 638 return &numericQuery{Left: n.Left.Clone(), Right: n.Right.Clone(), Do: n.Do} 639} 640 641type booleanQuery struct { 642 IsOr bool 643 Left, Right query 644 iterator func() NodeNavigator 645} 646 647func (b *booleanQuery) Select(t iterator) NodeNavigator { 648 if b.iterator == nil { 649 var list []NodeNavigator 650 i := 0 651 root := t.Current().Copy() 652 if b.IsOr { 653 for { 654 node := b.Left.Select(t) 655 if node == nil { 656 break 657 } 658 node = node.Copy() 659 list = append(list, node) 660 } 661 t.Current().MoveTo(root) 662 for { 663 node := b.Right.Select(t) 664 if node == nil { 665 break 666 } 667 node = node.Copy() 668 list = append(list, node) 669 } 670 } else { 671 var m []NodeNavigator 672 var n []NodeNavigator 673 for { 674 node := b.Left.Select(t) 675 if node == nil { 676 break 677 } 678 node = node.Copy() 679 list = append(m, node) 680 } 681 t.Current().MoveTo(root) 682 for { 683 node := b.Right.Select(t) 684 if node == nil { 685 break 686 } 687 node = node.Copy() 688 list = append(n, node) 689 } 690 for _, k := range m { 691 for _, j := range n { 692 if k == j { 693 list = append(list, k) 694 } 695 } 696 } 697 } 698 699 b.iterator = func() NodeNavigator { 700 if i >= len(list) { 701 return nil 702 } 703 node := list[i] 704 i++ 705 return node 706 } 707 } 708 return b.iterator() 709} 710 711func (b *booleanQuery) Evaluate(t iterator) interface{} { 712 m := b.Left.Evaluate(t) 713 left := asBool(t, m) 714 if b.IsOr && left { 715 return true 716 } else if !b.IsOr && !left { 717 return false 718 } 719 m = b.Right.Evaluate(t) 720 return asBool(t, m) 721} 722 723func (b *booleanQuery) Clone() query { 724 return &booleanQuery{IsOr: b.IsOr, Left: b.Left.Clone(), Right: b.Right.Clone()} 725} 726 727type unionQuery struct { 728 Left, Right query 729 iterator func() NodeNavigator 730} 731 732func (u *unionQuery) Select(t iterator) NodeNavigator { 733 if u.iterator == nil { 734 var m = make(map[uint64]NodeNavigator) 735 root := t.Current().Copy() 736 for { 737 node := u.Left.Select(t) 738 if node == nil { 739 break 740 } 741 code := getHashCode(node.Copy()) 742 if _, ok := m[code]; !ok { 743 m[code] = node.Copy() 744 } 745 } 746 t.Current().MoveTo(root) 747 for { 748 node := u.Right.Select(t) 749 if node == nil { 750 break 751 } 752 code := getHashCode(node.Copy()) 753 if _, ok := m[code]; !ok { 754 m[code] = node.Copy() 755 } 756 } 757 list := make([]NodeNavigator, len(m)) 758 var i int 759 for _, v := range m { 760 list[i] = v 761 i++ 762 } 763 i = 0 764 u.iterator = func() NodeNavigator { 765 if i >= len(list) { 766 return nil 767 } 768 node := list[i] 769 i++ 770 return node 771 } 772 } 773 return u.iterator() 774} 775 776func (u *unionQuery) Evaluate(t iterator) interface{} { 777 u.iterator = nil 778 u.Left.Evaluate(t) 779 u.Right.Evaluate(t) 780 return u 781} 782 783func (u *unionQuery) Clone() query { 784 return &unionQuery{Left: u.Left.Clone(), Right: u.Right.Clone()} 785} 786 787func getHashCode(n NodeNavigator) uint64 { 788 var sb bytes.Buffer 789 switch n.NodeType() { 790 case AttributeNode, TextNode, CommentNode: 791 sb.WriteString(fmt.Sprintf("%s=%s", n.LocalName(), n.Value())) 792 if n.MoveToParent() { 793 sb.WriteString(n.LocalName()) 794 } 795 case ElementNode: 796 sb.WriteString(n.Prefix() + n.LocalName()) 797 d := 1 798 for n.MoveToPrevious() { 799 d++ 800 } 801 sb.WriteString(fmt.Sprintf("-%d", d)) 802 803 for n.MoveToParent() { 804 d = 1 805 for n.MoveToPrevious() { 806 d++ 807 } 808 sb.WriteString(fmt.Sprintf("-%d", d)) 809 } 810 } 811 h := fnv.New64a() 812 h.Write([]byte(sb.String())) 813 return h.Sum64() 814} 815 816func getNodePosition(q query) int { 817 type Position interface { 818 position() int 819 } 820 if count, ok := q.(Position); ok { 821 return count.position() 822 } 823 return 1 824} 825