package httproute

import (
	"net/url"
	"strings"

	"github.com/pkg/errors"
)

// isMatch returns whether the provided URI path matches this template.
func (t *Template) isMatch(path string) bool {
	return t.traverse(path, func(_ string) {})
}

// traverse matches the provided URI path against this template, calling the
// eachSegment function with individual path segments as they're matched
// against the template. It returns whether the URI path matches the template.
func (t *Template) traverse(path string, eachSegment func(value string)) bool {
	if !strings.HasPrefix(path, "/") {
		return false
	}

	var verb string
	if i := strings.Index(path, ":"); i != -1 {
		verb = path[i+len(":"):]
		path = path[:i]
	}
	if verb != string(t.verb) {
		return false
	}

	path = strings.TrimPrefix(path, "/")

	for _, tmplSeg := range t.pathSegments() {
		if tmplSeg == "**" {
			// The ** segment matches zero or more path segments. Here it consumes
			// the entire remaining path and marks the end of the traversal.
			eachSegment(path)
			return true
		}
		var seg string
		seg, path = split2(path, "/")
		if len(seg) == 0 {
			// The pattern calls for more path, but we've run out.
			return false
		}
		if tmplSeg != "*" && seg != tmplSeg {
			// The * segment matches any input, otherwise we'll need an exact
			// string match of this segment.
			return false
		}
		eachSegment(seg)
	}

	if path == "" {
		// No path segments remain. This is a match.
		return true
	}
	return false
}

// split2 partitions the string s on either side of the first occurrence of
// sep.
func split2(s, sep string) (string, string) {
	if i := strings.Index(s, sep); i >= 0 {
		return s[:i], s[i+len(sep):]
	}
	return s, ""
}

// NewPathMatcher creates a PathMatcher for the provided patterns.
func NewPathMatcher(patterns []string) (*PathMatcher, error) {
	return newPathMatcher(patterns, ParseTemplate)
}

func newPathMatcher(patterns []string, parseTemplate func(string) (*Template, error)) (*PathMatcher, error) {
	var pm PathMatcher

	for _, pattern := range patterns {
		tmpl, err := parseTemplate(pattern)
		if err != nil {
			return nil, errors.Wrapf(err, "invalid template %q", pattern)
		}
		pm.templates = append(pm.templates, tmpl)
		if out := tmpl.String(); out != pattern {
			// Check the round-trip invariant. The presence of templates for
			// which this doesn't work indicates a bug in the parser (it
			// should return an error on invalid templates). Allowing errors
			// to be injected here means we can get to 100% test coverage even
			// when the invariant holds :)
			return nil, errors.Errorf(
				"template did not successfully round-trip after parsing, suspect parser bug (given %q, returned %q)",
				pattern, out)
		}
	}

	return &pm, nil
}

// A PathMatcher allows URI paths to be compared against a set of templates,
// and any bound variables to be extracted from those URI paths.
type PathMatcher struct {
	templates []*Template
}

// Match determines which template matches the provided URI path, returning
// the text format of the selected template along with any values that were
// bound to path segments. If no matching template is found, Match returns the
// empty string and a nil values map.
//
// Its behavior in the case of degenerate templates (where more than one
// matches the provided URI path) is undefined.
func (pm *PathMatcher) Match(path string) (template string, values url.Values) {
	for _, tmpl := range pm.templates {
		if tmpl.isMatch(path) {
			if template == "" {
				t := tmpl.String()
				v, err := tmpl.capturePathParams(path)
				if err == nil {
					template, values = t, v
				}
			} else {
				// TODO: precompute whether this is possible within
				// NewPathMatcher.

				// TODO: break the degeneracy by calculating a score for each
				// template. When matching the URI "/a/b/c", we'd use the following
				// sorts of tiebreakers:
				//
				//     "/a/b/c"    > "/a/b/*"
				//     "/a/b/c"    > "/a/*/c"
				//     "/a/b/c"    > "/*/b/c"
				//     "/a/b/*"    > "/a/*/*"
				//     "/a/*/*"    > "/*/*/*"
				//     "/a/b/c"    > "/a/b/c/**"
				//     "/a/b/c/**" > "/a/b/**"
				//     "/a/b/**"   > "/a/**"
				//     "/a/**"     > "/**"
				//
				// But which of the following should win? We'd need to precisely
				// define the expectations here.
				//
				//     "/a/*/c"     ? "/*/b/c"
				//     "/a/*/*"     ? "/*/b/c"
				//     "/a/b/*"     ? "/a/b/c/**"
			}
		}
	}
	return template, values
}
