path.go

package xmlpath

import (
	"fmt"
	"strconv"
	"unicode/utf8"
)

// Path is a compiled path that can be applied to a context
// node to obtain a matching node set.
// A single Path can be applied concurrently to any number
// of context nodes.
type Path struct {
	path  string
	steps []pathStep
}

// Iter returns an iterator that goes over the list of nodes
// that p matches on the given context.
func (p *Path) Iter(context *Node) *Iter {
	iter := Iter{
		make([]pathStepState, len(p.steps)),
		make([]bool, len(context.nodes)),
	}
	for i := range p.steps {
		iter.state[i].step = &p.steps[i]
	}
	iter.state[0].init(context)
	return &iter
}

// Exists returns whether any nodes match p on the given context.
func (p *Path) Exists(context *Node) bool {
	return p.Iter(context).Next()
}

// String returns the string value of the first node matched
// by p on the given context.
//
// See the documentation of Node.String.
func (p *Path) String(context *Node) (s string, ok bool) {
	iter := p.Iter(context)
	if iter.Next() {
		return iter.Node().String(), true
	}
	return "", false
}

// Bytes returns as a byte slice the string value of the first
// node matched by p on the given context.
//
// See the documentation of Node.String.
func (p *Path) Bytes(node *Node) (b []byte, ok bool) {
	iter := p.Iter(node)
	if iter.Next() {
		return iter.Node().Bytes(), true
	}
	return nil, false
}

// Iter iterates over node sets.
type Iter struct {
	state []pathStepState
	seen  []bool
}

// Node returns the current node.
// Must only be called after Iter.Next returns true.
func (iter *Iter) Node() *Node {
	state := iter.state[len(iter.state)-1]
	if state.pos == 0 {
		panic("Iter.Node called before Iter.Next")
	}
	if state.node == nil {
		panic("Iter.Node called after Iter.Next false")
	}
	return state.node
}

// Next iterates to the next node in the set, if any, and
// returns whether there is a node available.
func (iter *Iter) Next() bool {
	tip := len(iter.state) - 1
outer:
	for {
		for !iter.state[tip].next() {
			tip--
			if tip == -1 {
				return false
			}
		}
		for tip < len(iter.state)-1 {
			tip++
			iter.state[tip].init(iter.state[tip-1].node)
			if !iter.state[tip].next() {
				tip--
				continue outer
			}
		}
		if iter.seen[iter.state[tip].node.pos] {
			continue
		}
		iter.seen[iter.state[tip].node.pos] = true
		return true
	}
	panic("unreachable")
}

type pathStepState struct {
	step *pathStep
	node *Node
	pos  int
	idx  int
	aux  int
}

func (s *pathStepState) init(node *Node) {
	s.node = node
	s.pos = 0
	s.idx = 0
	s.aux = 0
}

func (s *pathStepState) next() bool {
	for s._next() {
		s.pos++
		if s.step.pred == nil || s.test(s.step.pred) {
			return true
		}
	}
	return false
}

func (s *pathStepState) test(pred predicate) bool {
	switch pred := pred.(type) {
	case positionPredicate:
		if pred.operator(pred.pos, s.pos) {
			return true
		}
	case existsPredicate:
		if pred.path.Exists(s.node) {
			return true
		}
	case equalsPredicate:
		iter := pred.path.Iter(s.node)
		for iter.Next() {
			if iter.Node().equals(pred.value) {
				return true
			}
		}
	case notequalsPredicate:
		iter := pred.path.Iter(s.node)
		for iter.Next() {
			if !iter.Node().equals(pred.value) {
				return true
			}
		}
	case containsPredicate:
		iter := pred.path.Iter(s.node)
		for iter.Next() {
			if iter.Node().contains(pred.value) {
				return true
			}
		}
	case startsWithPredicate:
		iter := pred.path.Iter(s.node)
		for iter.Next() {
			if iter.Node().startsWith(pred.value) {
				return true
			}
		}
	case notPredicate:
		return !s.test(pred.uniSub)
	case andPredicate:
		for _, sub := range pred.sub {
			if !s.test(sub) {
				return false
			}
		}
		return true
	case orPredicate:
		for _, sub := range pred.sub {
			if s.test(sub) {
				return true
			}
		}
	default:
		panic(fmt.Sprintf("internal error: unknown predicate type: %#v", s.step.pred))
	}
	return false
}

func (s *pathStepState) _next() bool {
	if s.node == nil {
		return false
	}
	if s.step.root && s.idx == 0 {
		for s.node.up != nil {
			s.node = s.node.up
		}
	}

	switch s.step.axis {

	case "self":
		if s.idx == 0 && s.step.match(s.node) {
			s.idx++
			return true
		}

	case "parent":
		if s.idx == 0 && s.node.up != nil && s.step.match(s.node.up) {
			s.idx++
			s.node = s.node.up
			return true
		}

	case "ancestor", "ancestor-or-self":
		if s.idx == 0 && s.step.axis == "ancestor-or-self" {
			s.idx++
			if s.step.match(s.node) {
				return true
			}
		}
		for s.node.up != nil {
			s.node = s.node.up
			s.idx++
			if s.step.match(s.node) {
				return true
			}
		}

	case "child":
		var down []*Node
		if s.idx == 0 {
			down = s.node.down
		} else {
			down = s.node.up.down
		}
		for s.idx < len(down) {
			node := down[s.idx]
			s.idx++
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	case "descendant", "descendant-or-self":
		if s.idx == 0 {
			s.idx = s.node.pos
			s.aux = s.node.end
			if s.step.axis == "descendant" {
				s.idx++
			}
		}
		for s.idx < s.aux {
			node := &s.node.nodes[s.idx]
			s.idx++
			if node.kind == AttrNode {
				continue
			}
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	case "following":
		if s.idx == 0 {
			s.idx = s.node.end
		}
		for s.idx < len(s.node.nodes) {
			node := &s.node.nodes[s.idx]
			s.idx++
			if node.kind == AttrNode {
				continue
			}
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	case "following-sibling":
		var down []*Node
		if s.node.up != nil {
			down = s.node.up.down
			if s.idx == 0 {
				for s.idx < len(down) {
					node := down[s.idx]
					s.idx++
					if node == s.node {
						break
					}
				}
			}
		}
		for s.idx < len(down) {
			node := down[s.idx]
			s.idx++
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	case "preceding":
		if s.idx == 0 {
			s.aux = s.node.pos // Detect ancestors.
			s.idx = s.node.pos - 1
		}
		for s.idx >= 0 {
			node := &s.node.nodes[s.idx]
			s.idx--
			if node.kind == AttrNode {
				continue
			}
			if node == s.node.nodes[s.aux].up {
				s.aux = s.node.nodes[s.aux].up.pos
				continue
			}
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	case "preceding-sibling":
		var down []*Node
		if s.node.up != nil {
			down = s.node.up.down
			if s.aux == 0 {
				s.aux = 1
				for s.idx < len(down) {
					node := down[s.idx]
					s.idx++
					if node == s.node {
						s.idx--
						break
					}
				}
			}
		}
		for s.idx >= 0 {
			node := down[s.idx]
			s.idx--
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	case "attribute":
		if s.idx == 0 {
			s.idx = s.node.pos + 1
			s.aux = s.node.end
		}
		for s.idx < s.aux {
			node := &s.node.nodes[s.idx]
			s.idx++
			if node.kind != AttrNode {
				break
			}
			if s.step.match(node) {
				s.node = node
				return true
			}
		}

	}

	s.node = nil
	return false
}

type positionPredicate struct {
	pos      int
	operator positionFunc
}

type existsPredicate struct {
	path *Path
}

type equalsPredicate struct {
	path  *Path
	value string
}
type notequalsPredicate struct {
	path  *Path
	value string
}

type containsPredicate struct {
	path  *Path
	value string
}

type startsWithPredicate struct {
	path  *Path
	value string
}

type notPredicate struct {
	uniSub predicate
}

type andPredicate struct {
	sub []predicate
}

type orPredicate struct {
	sub []predicate
}

// predicate is a marker interface for predicate types.
type predicate interface {
	predicate()
}

func (positionPredicate) predicate()   {}
func (existsPredicate) predicate()     {}
func (equalsPredicate) predicate()     {}
func (notequalsPredicate) predicate()  {}
func (containsPredicate) predicate()   {}
func (startsWithPredicate) predicate() {}
func (notPredicate) predicate()        {}
func (andPredicate) predicate()        {}
func (orPredicate) predicate()         {}

// positionFunc is a type interface for all position comparison operators
type positionFunc func(wanted, current int) bool

func equalPosition(wanted, current int) bool        { return wanted == current }
func notequalPosition(wanted, current int) bool     { return wanted != current }
func largerPosition(wanted, current int) bool       { return current > wanted }
func smallerPosition(wanted, current int) bool      { return current < wanted }
func largerequalPosition(wanted, current int) bool  { return current >= wanted }
func smallerequalPosition(wanted, current int) bool { return current <= wanted }

type pathStep struct {
	root bool
	axis string
	name string
	kind NodeKind
	pred predicate
}

func (step *pathStep) match(node *Node) bool {
	return node.kind != EndNode &&
		(step.kind == AnyNode || step.kind == node.kind) &&
		(step.name == "*" || node.name.Local == step.name)
}

// MustCompile returns the compiled path, and panics if
// there are any errors.
func MustCompile(path string) *Path {
	e, err := Compile(path)
	if err != nil {
		panic(err)
	}
	return e
}

// Compile returns the compiled path.
func Compile(path string) (*Path, error) {
	c := pathCompiler{path, 0}
	if path == "" {
		return nil, c.errorf("empty path")
	}
	p, err := c.parsePath()
	if err != nil {
		return nil, err
	}
	return p, nil
}

type pathCompiler struct {
	path string
	i    int
}

func (c *pathCompiler) errorf(format string, args ...interface{}) error {
	return fmt.Errorf("compiling xml path %q:%d: %s", c.path, c.i, fmt.Sprintf(format, args...))
}

func (c *pathCompiler) parsePath() (path *Path, err error) {
	var steps []pathStep
	var start = c.i
	for {
		step := pathStep{axis: "child"}

		c.skipSpaces()
		if c.i == 0 && c.skipByte('/') {
			c.skipSpaces()
			step.root = true
			if len(c.path) == 1 {
				step.name = "*"
			}
		}
		if c.peekByte('/') {
			step.axis = "descendant-or-self"
			step.name = "*"
		} else if c.skipByte('@') {
			mark := c.i
			if !c.skipName() {
				return nil, c.errorf("missing name after @")
			}
			step.axis = "attribute"
			step.name = c.path[mark:c.i]
			step.kind = AttrNode
		} else {
			mark := c.i
			if c.skipName() {
				step.name = c.path[mark:c.i]
				c.skipSpaces()
			}
			if step.name == "" {
				return nil, c.errorf("missing name")
			} else if step.name == "*" {
				step.kind = StartNode
			} else if step.name == "." {
				step.axis = "self"
				step.name = "*"
			} else if step.name == ".." {
				step.axis = "parent"
				step.name = "*"
			} else {
				if c.skipByte(':') {
					if !c.skipByte(':') {
						return nil, c.errorf("missing ':'")
					}
					c.skipSpaces()
					switch step.name {
					case "attribute":
						step.kind = AttrNode
					case "self", "child", "parent":
					case "descendant", "descendant-or-self":
					case "ancestor", "ancestor-or-self":
					case "following", "following-sibling":
					case "preceding", "preceding-sibling":
					default:
						return nil, c.errorf("unsupported axis: %q", step.name)
					}
					step.axis = step.name

					mark = c.i
					if !c.skipName() {
						return nil, c.errorf("missing name")
					}
					step.name = c.path[mark:c.i]

					c.skipSpaces()
				}
				if c.skipByte('(') {
					c.skipSpaces()
					conflict := step.kind != AnyNode
					switch step.name {
					case "node":
						// must be anyNode
					case "text":
						step.kind = TextNode
					case "comment":
						step.kind = CommentNode
					case "processing-instruction":
						step.kind = ProcInstNode
					default:
						return nil, c.errorf("unsupported expression: %s()", step.name)
					}
					if conflict {
						return nil, c.errorf("%s() cannot succeed on axis %q", step.name, step.axis)
					}

					name := step.name
					literal, err := c.parseLiteral()
					if err == errNoLiteral {
						step.name = "*"
					} else if err != nil {
						return nil, c.errorf("%v", err)
					} else if step.kind == ProcInstNode {
						c.skipSpaces()
						step.name = literal
					} else {
						return nil, c.errorf("%s() has no arguments", name)
					}
					if !c.skipByte(')') {
						return nil, c.errorf("%s() missing ')'", name)
					}
					c.skipSpaces()
				} else if step.name == "*" && step.kind == AnyNode {
					step.kind = StartNode
				}
			}
		}
		if c.skipByte('[') {
			c.skipSpaces()
			type state struct {
				sub []predicate
				and bool
				not bool
			}
			var stack []state
			var sub []predicate
			var and bool
		NextPred:
			if c.skipByte('(') {
				stack = append(stack, state{sub: sub, and: and})
				sub = nil
				and = false
			}
			var next predicate
			if pos, ok := c.parseInt(); ok {
				if pos == 0 {
					return nil, c.errorf("positions start at 1")
				}
				next = positionPredicate{pos: pos, operator: equalPosition}
			} else if c.skipString("position()") {
				c.skipSpaces()
				if operator, ok := c.parseOperator(); !ok {
					return nil, c.errorf("position() not followed by operator")
				} else {
					var operatorFunc positionFunc
					switch operator {
					case "=":
						operatorFunc = equalPosition
					case "!=":
						operatorFunc = notequalPosition
					case "<=":
						operatorFunc = smallerequalPosition
					case ">=":
						operatorFunc = largerequalPosition
					case "<":
						operatorFunc = smallerPosition
					case ">":
						operatorFunc = largerPosition
					}

					c.skipSpaces()
					if pos, ok := c.parseInt(); !ok {
						return nil, c.errorf("position() not followed by number")
					} else {
						if pos == 0 {
							return nil, c.errorf("positions start at 1")
						}
						next = positionPredicate{pos: pos, operator: operatorFunc}
					}
				}
			} else if c.skipString("contains(") {
				path, err := c.parsePath()
				if err != nil {
					return nil, err
				}
				c.skipSpaces()
				if !c.skipByte(',') {
					return nil, c.errorf("contains() expected ',' followed by a literal string")
				}
				c.skipSpaces()
				value, err := c.parseLiteral()
				if err != nil {
					return nil, err
				}
				c.skipSpaces()
				if !c.skipByte(')') {
					return nil, c.errorf("contains() missing ')'")
				}
				next = containsPredicate{path, value}
			} else if c.skipString("starts-with(") {
				path, err := c.parsePath()
				if err != nil {
					return nil, err
				}
				c.skipSpaces()
				if !c.skipByte(',') {
					return nil, c.errorf("starts-with() expected ',' followed by a literal string")
				}
				c.skipSpaces()
				value, err := c.parseLiteral()
				if err != nil {
					return nil, err
				}
				c.skipSpaces()
				if !c.skipByte(')') {
					return nil, c.errorf("starts-with() missing ')'")
				}
				next = startsWithPredicate{path, value}
			} else if c.skipString("not(") {
				stack = append(stack, state{sub: sub, and: and, not: true})
				sub = nil
				and = false
				goto NextPred
			} else {
				path, err := c.parsePath()
				if err != nil {
					return nil, err
				}
				if path.path[0] == '-' {
					if _, err = strconv.Atoi(path.path); err == nil {
						return nil, c.errorf("positions must be positive")
					}
				}
				c.skipSpaces()
				if c.skipByte('=') {
					c.skipSpaces()
					value, err := c.parseLiteral()
					if err != nil {
						return nil, c.errorf("%v", err)
					}
					next = equalsPredicate{path, value}
				} else if c.skipString("!=") {
					c.skipSpaces()
					value, err := c.parseLiteral()
					if err != nil {
						return nil, c.errorf("%v", err)
					}
					next = notequalsPredicate{path, value}
				} else {
					next = existsPredicate{path}
				}
			}
		HandleNext:
			if and {
				p := sub[len(sub)-1].(andPredicate)
				p.sub = append(p.sub, next)
				sub[len(sub)-1] = p
			} else {
				sub = append(sub, next)
			}
			if c.skipSpaces() {
				mark := c.i
				if c.skipString("and") && c.skipSpaces() {
					if !and {
						and = true
						sub[len(sub)-1] = andPredicate{[]predicate{sub[len(sub)-1]}}
					}
					goto NextPred
				} else if c.skipString("or") && c.skipSpaces() {
					and = false
					goto NextPred
				} else {
					c.i = mark
				}
			}
			if c.skipByte(')') {
				if len(stack) == 0 {
					return nil, c.errorf("unexpected ')'")
				}
				if len(sub) == 1 {
					next = sub[0]
				} else {
					next = orPredicate{sub}
				}
				s := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				sub = s.sub
				and = s.and
				if s.not {
					next = notPredicate{next}
				}
				goto HandleNext
			}
			if len(stack) > 0 {
				return nil, c.errorf("expected ')'")
			}
			if len(sub) == 1 {
				step.pred = sub[0]
			} else {
				step.pred = orPredicate{sub}
			}
			if !c.skipByte(']') {
				return nil, c.errorf("expected ']'")
			}
			c.skipSpaces()
		}
		steps = append(steps, step)
		//fmt.Printf("step: %#v\n", step)
		if !c.skipByte('/') {
			if (start == 0 || start == c.i) && c.i < len(c.path) {
				return nil, c.errorf("unexpected %q", c.path[c.i])
			}
			return &Path{steps: steps, path: c.path[start:c.i]}, nil
		}
	}
	panic("unreachable")
}

var errNoLiteral = fmt.Errorf("expected a literal string")

func (c *pathCompiler) parseLiteral() (string, error) {
	if c.skipByte('"') {
		mark := c.i
		if !c.skipByteFind('"') {
			return "", fmt.Errorf(`missing '"'`)
		}
		return c.path[mark : c.i-1], nil
	}
	if c.skipByte('\'') {
		mark := c.i
		if !c.skipByteFind('\'') {
			return "", fmt.Errorf(`missing "'"`)
		}
		return c.path[mark : c.i-1], nil
	}
	return "", errNoLiteral
}

func (c *pathCompiler) parseInt() (v int, ok bool) {
	mark := c.i
	for c.i < len(c.path) && c.path[c.i] >= '0' && c.path[c.i] <= '9' {
		v *= 10
		v += int(c.path[c.i]) - '0'
		c.i++
	}
	if c.i == mark {
		return 0, false
	}
	return v, true
}

func (c *pathCompiler) parseOperator() (v string, ok bool) {
	if c.skipString("=") {
		return "=", true
	}
	if c.skipString("!=") {
		return "!=", true
	}
	if c.skipString(">=") {
		return ">=", true
	}
	if c.skipString(">") {
		return ">", true
	}
	if c.skipString("<=") {
		return "<=", true
	}
	if c.skipString("<") {
		return "<", true
	}
	return "", false
}

func (c *pathCompiler) skipByte(b byte) bool {
	if c.i < len(c.path) && c.path[c.i] == b {
		c.i++
		return true
	}
	return false
}

func (c *pathCompiler) skipByteFind(b byte) bool {
	for i := c.i; i < len(c.path); i++ {
		if c.path[i] == b {
			c.i = i + 1
			return true
		}
	}
	return false
}

func (c *pathCompiler) peekByte(b byte) bool {
	return c.i < len(c.path) && c.path[c.i] == b
}

func (c *pathCompiler) skipSpaces() bool {
	mark := c.i
	for c.i < len(c.path) {
		if c.path[c.i] != ' ' {
			break
		}
		c.i++
	}
	return c.i != mark
}

func (c *pathCompiler) skipString(s string) bool {
	if c.i+len(s) <= len(c.path) && c.path[c.i:c.i+len(s)] == s {
		c.i += len(s)
		return true
	}
	return false
}

func (c *pathCompiler) skipName() bool {
	if c.i >= len(c.path) {
		return false
	}
	if c.path[c.i] == '*' {
		c.i++
		return true
	}
	start := c.i
	for c.i < len(c.path) && (c.path[c.i] >= utf8.RuneSelf || isNameByte(c.path[c.i])) {
		c.i++
	}
	return c.i > start
}

func isNameByte(c byte) bool {
	return 'A' <= c && c <= 'Z' || 'a' <= c && c <= 'z' || '0' <= c && c <= '9' || c == '_' || c == '.' || c == '-'
}