package httpd

import "errors"

// Lua patterns, as patterns(7) describes them: a port of the matcher in
// OpenBSD's patterns.c, which httpd uses, itself Lua 5.3's lstrlib.c.

// Limits of patterns.c.
const (
	maxCaptures = 32  // MAXCAPTURES
	maxCalls    = 200 // MAXCCALLS: how deep a match may recurse
)

// checkPattern reports why patterns.c would refuse pat, or why find would
// not match it as patterns.c does, and otherwise how many captures it
// has.
func checkPattern(pat string) (int, error) {
	caps, open := 0, 0
	for p := 0; p < len(pat); {
		switch pat[p] {
		case '(':
			if p+1 < len(pat) && pat[p+1] == ')' {
				return 0, errors.New("position captures are not supported")
			}
			if caps++; caps > maxCaptures {
				return 0, errors.New("too many captures")
			}
			open++
			p++
			continue
		case ')':
			if open == 0 {
				return 0, errors.New("invalid pattern capture")
			}
			open--
			p++
			continue
		case '%':
			if p+1 == len(pat) {
				return 0, errors.New("malformed pattern (ends with '%')")
			}
			switch c := pat[p+1]; {
			case c == 'b' || c == 'f':
				return 0, errors.New("%" + string(c) + " is not supported")
			case '0' <= c && c <= '9':
				return 0, errors.New("back references are not supported")
			}
		}
		if p = classEnd(pat, p); p < 0 {
			return 0, errors.New("malformed pattern (missing ']')")
		}
	}
	if open > 0 {
		return 0, errors.New("unfinished capture")
	}
	return caps, nil
}

// find is str_find_aux: the first match of pat in s, and then each
// capture. A pattern too complex to match within maxCalls finds nothing,
// as httpd has it. pat must pass checkPattern.
func find(s, pat string) ([]string, bool) {
	m := &matcher{src: s, pat: pat}
	p0, anchor := 0, len(pat) > 0 && pat[0] == '^'
	if anchor {
		p0 = 1
	}
	for start := 0; start <= len(s) && !m.tooComplex; start++ {
		m.caps = m.caps[:0]
		if end := m.match(start, p0); end >= 0 {
			caps := []string{s[start:end]}
			for _, c := range m.caps {
				caps = append(caps, s[c.start:c.start+c.len])
			}
			return caps, true
		}
		if anchor {
			break
		}
	}
	return nil, false
}

type capture struct{ start, len int } // len -1 while open

type matcher struct {
	src, pat   string
	caps       []capture
	depth      int
	tooComplex bool
}

// match is do_match: the end of the match of pat[p:] at src[s:], or -1.
func (m *matcher) match(s, p int) int {
	if m.tooComplex || m.depth == maxCalls {
		m.tooComplex = true
		return -1
	}
	m.depth++
	defer func() { m.depth-- }()
	for {
		if p == len(m.pat) {
			return s
		}
		switch m.pat[p] {
		case '(':
			m.caps = append(m.caps, capture{s, -1})
			r := m.match(s, p+1)
			if r < 0 {
				m.caps = m.caps[:len(m.caps)-1]
			}
			return r
		case ')':
			l := len(m.caps) - 1
			for l >= 0 && m.caps[l].len != -1 {
				l--
			}
			m.caps[l].len = s - m.caps[l].start
			r := m.match(s, p+1)
			if r < 0 {
				m.caps[l].len = -1
			}
			return r
		case '$':
			if p+1 == len(m.pat) {
				if s == len(m.src) {
					return s
				}
				return -1
			}
		}
		ep := classEnd(m.pat, p)
		ok := s < len(m.src) && m.single(m.src[s], p, ep)
		if ep < len(m.pat) {
			switch m.pat[ep] {
			case '?':
				if ok {
					if r := m.match(s+1, ep+1); r >= 0 {
						return r
					}
				}
				p = ep + 1
				continue
			case '+':
				if !ok {
					return -1
				}
				return m.maxExpand(s+1, p, ep)
			case '*':
				return m.maxExpand(s, p, ep)
			case '-':
				for {
					if r := m.match(s, ep+1); r >= 0 {
						return r
					}
					if s < len(m.src) && m.single(m.src[s], p, ep) {
						s++
					} else {
						return -1
					}
				}
			}
		}
		if !ok {
			return -1
		}
		s, p = s+1, ep
	}
}

func (m *matcher) maxExpand(s, p, ep int) int {
	i := 0
	for s+i < len(m.src) && m.single(m.src[s+i], p, ep) {
		i++
	}
	for ; i >= 0; i-- {
		if r := m.match(s+i, ep+1); r >= 0 {
			return r
		}
	}
	return -1
}

// classEnd is the end of the single-character class at pat[p], or -1 if
// it is malformed.
func classEnd(pat string, p int) int {
	c := pat[p]
	p++
	switch c {
	case '%':
		if p == len(pat) {
			return -1
		}
		return p + 1
	case '[':
		if p < len(pat) && pat[p] == '^' {
			p++
		}
		// The first character is never the closing ], so []] is a set.
		for {
			if p >= len(pat) {
				return -1
			}
			c := pat[p]
			p++
			if c == '%' && p < len(pat) {
				p++
			}
			if p >= len(pat) {
				return -1
			}
			if pat[p] == ']' {
				return p + 1
			}
		}
	}
	return p
}

func (m *matcher) single(c byte, p, ep int) bool {
	switch m.pat[p] {
	case '.':
		return true
	case '%':
		return class(c, m.pat[p+1])
	case '[':
		return m.bracket(c, p, ep-1)
	}
	return m.pat[p] == c
}

func (m *matcher) bracket(c byte, p, ec int) bool {
	sig := true
	p++
	if m.pat[p] == '^' {
		sig = false
		p++
	}
	for ; p < ec; p++ {
		switch {
		case m.pat[p] == '%':
			p++
			if class(c, m.pat[p]) {
				return sig
			}
		case m.pat[p+1] == '-' && p+2 < ec:
			if m.pat[p] <= c && c <= m.pat[p+2] {
				return sig
			}
			p += 2
		case m.pat[p] == c:
			return sig
		}
	}
	return !sig
}

// class is match_class: whether c is in the class %cl, in the C locale.
func class(c, cl byte) bool {
	var ok bool
	switch cl | 0x20 {
	case 'a':
		ok = 'a' <= c|0x20 && c|0x20 <= 'z'
	case 'c':
		ok = c < ' ' || c == 0x7f
	case 'd':
		ok = '0' <= c && c <= '9'
	case 'g':
		ok = c > ' ' && c < 0x7f
	case 'l':
		ok = 'a' <= c && c <= 'z'
	case 'p':
		ok = c > ' ' && c < 0x7f && !class(c, 'w')
	case 's':
		ok = c == ' ' || ('\t' <= c && c <= '\r')
	case 'u':
		ok = 'A' <= c && c <= 'Z'
	case 'w':
		ok = class(c, 'a') || class(c, 'd')
	case 'x':
		ok = class(c, 'd') || ('a' <= c|0x20 && c|0x20 <= 'f')
	default:
		return cl == c
	}
	if 'A' <= cl && cl <= 'Z' {
		return !ok
	}
	return ok
}