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