package httpd

import (
	"strings"
	"testing"
)

// The cases here follow patterns(7), which httpd.conf(5) names for
// `location match`; where it leaves something undefined, they follow
// patterns.c, which httpd links.

// classMembers is each class of patterns(7) in the C locale, listed by
// hand so that it checks class, where computing it would only restate it.
var classMembers = map[byte]string{
	'a': "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
	'c': "\x00\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\r\x0e\x0f" +
		"\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x7f",
	'd': "0123456789",
	'g': "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
	'l': "abcdefghijklmnopqrstuvwxyz",
	'p': "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~",
	's': " \t\n\v\f\r",
	'u': "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
	'w': "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz",
	'x': "0123456789ABCDEFabcdef",
}

// TestClass checks every class letter against every byte: "the
// corresponding uppercase letter represents the complement of the class",
// and %x for any other x "represents the character x" (patterns(7)).
// Bytes past ASCII are in no class, as in the C locale. Lua 5.1's %z is
// gone from patterns.c, so it is a plain z.
func TestClass(t *testing.T) {
	for cl := 0; cl < 256; cl++ {
		members, isClass := classMembers[byte(cl)|0x20]
		isClass = isClass && ('a' <= cl|0x20 && cl|0x20 <= 'z')
		for c := 0; c < 256; c++ {
			want := byte(c) == byte(cl)
			if isClass {
				want = strings.IndexByte(members, byte(c)) >= 0
				if 'A' <= cl && cl <= 'Z' {
					want = !want
				}
			}
			if got := class(byte(c), byte(cl)); got != want {
				t.Errorf("class(%q, %q) = %v, want %v", byte(c), byte(cl), got, want)
			}
		}
	}
}

// TestClassInPattern checks that a class means the same alone, in a set
// and in a complemented set.
func TestClassInPattern(t *testing.T) {
	for l, members := range classMembers {
		for _, cl := range []byte{l, l - 'a' + 'A'} {
			for c := 1; c < 256; c++ {
				in := strings.IndexByte(members, byte(c)) >= 0
				if cl != l {
					in = !in
				}
				s := string([]byte{byte(c)})
				for pat, want := range map[string]bool{
					"%" + string(cl):         in,
					"[%" + string(cl) + "]":  in,
					"[^%" + string(cl) + "]": !in,
				} {
					if _, got := PatternLocation("^" + pat + "$").Match(s); got != want {
						t.Errorf("%q on %q = %v, want %v", pat, s, got, want)
					}
				}
			}
		}
	}
}

// match runs pat on s and joins what it captured, or "-" for no match.
func match(pat, s string) string {
	caps, ok := PatternLocation(pat).Match(s)
	if !ok {
		return "-"
	}
	return strings.Join(caps, "|")
}

func testMatches(t *testing.T, cases []struct{ pat, s, want string }) {
	t.Helper()
	for _, c := range cases {
		if err := PatternLocation(c.pat).Check(); err != nil {
			t.Errorf("Check: %v", err)
		}
		if got := match(c.pat, c.s); got != c.want {
			t.Errorf("%q on %q = %q, want %q", c.pat, c.s, got, c.want)
		}
	}
}

// TestSingle covers the single character classes outside sets: ".", "%x"
// and a plain character, which "represents the character x itself"
// unless it is one of ^$()%.[]*+-? (patterns(7)).
func TestSingle(t *testing.T) {
	testMatches(t, []struct{ pat, s, want string }{
		{"^.$", "x", "x"},
		{"^.$", "/", "/"},
		{"^.$", "", "-"},
		{"^.$", "xy", "-"},
		{"^a.c$", "a/c", "a/c"},
		{"^%.$", ".", "."},
		{"^%.$", "x", "-"},
		{"^%%$", "%", "%"},
		{"^%[%]$", "[]", "[]"},
		{"^%^%$$", "^$", "^$"},
		{"^%*%+%-%?$", "*+-?", "*+-?"},
		{"^%/$", "/", "/"},
		{"^%B$", "B", "B"}, // not a class: an escaped B
		{"^%z$", "z", "z"},
		{"^%z$", "\x00", "-"},
		{"%d%d", "/a1b23", "23"},
		{"%u%l", "/aBcD", "Bc"},
		{"%S+", "  ab c", "ab"},
		{"%W", "ab/c", "/"},
	})
}

// TestSet covers [set] and [^set]: "a range ... the end characters
// separated by '-'", "%x" classes inside, "a closing square bracket in a
// set by positioning it as the first character" and "a hyphen in a set by
// positioning it either as the first or the last character" (patterns(7)).
func TestSet(t *testing.T) {
	testMatches(t, []struct{ pat, s, want string }{
		{"[abc]", "/xbx", "b"},
		{"[abc]", "/xyz", "-"},
		{"[^abc]", "abcd", "d"},
		{"[^abc]", "abca", "-"},
		{"^[a-c]+$", "abcba", "abcba"},
		{"[a-c]", "d-`", "-"},
		{"[^a-c]", "abc-", "-"},
		{"^[0-9a-f]+$", "09af", "09af"},
		{"^[0-9a-f]+$", "09ag", "-"},
		{"[z-a]", "amz-", "-"}, // an empty range
		{"[a-]", "x-", "-"},    // - last is literal
		{"[a-]", "xa", "a"},
		{"[-a]", "x-", "-"},
		{"[-a]", "xb", "-"},
		{"[%-]", "x-", "-"},
		{"[]]", "x]", "]"},
		{"[^]]", "]]x", "x"},
		{"[^]]", "]]", "-"},
		{"[]-a]", "^", "^"}, // ] first can start a range
		{"[%]]", "x]", "]"},
		{"[%a%]]", "1]", "]"},
		{"[%a%]]", "1b", "b"},
		{"[.]", "x.", "."},
		{"[.]", "x", "-"},
		{"[%.]", "x.", "."},
		{"[(]", "x(", "("}, // no capture inside a set
		{"[)]", "x)", ")"},
		{"[%d_]", "a_", "_"},
		{"[^%d_]", "1_a", "a"},
		// "The interaction between ranges and classes is not defined"
		// (patterns(7)). patterns.c takes a class then - as the class and
		// plain characters, and a range ending in % as a range to %, so
		// that [a-%d] is the empty range a-% and d.
		{"^[%a-z]+$", "a-z", "a-z"},
		{"^[%a-z]+$", "a1", "-"},
		{"^[a-%d]+$", "d", "d"},
		{"^[a-%d]+$", "a", "-"},
		{"^[a-%d]+$", "%", "-"},
		{"^[ab]*$", "abba", "abba"},
		{"^[ab]*$", "abca", "-"},
	})
}

// TestAnchors: "A '^' at the beginning of a pattern anchors the match at
// the beginning of the subject string. A '$' at the end of a pattern
// anchors the match at the end of the subject string. At other positions,
// '^' and '$' have no special meaning and represent themselves"
// (patterns(7)). Unanchored, the first match from the left wins.
func TestAnchors(t *testing.T) {
	testMatches(t, []struct{ pat, s, want string }{
		{"", "abc", ""},
		{"", "", ""},
		{"^", "abc", ""},
		{"$", "abc", ""},
		{"^$", "", ""},
		{"^$", "a", "-"},
		{"^a", "ba", "-"},
		{"^a", "ab", "a"},
		{"a$", "ab", "-"},
		{"a$", "aba", "a"},
		{"b", "abcb", "b"},
		{"b.", "abcbd", "bc"},
		{"^^a", "^a", "^a"},
		{"^^a", "a", "-"},
		{"a$$", "a$", "a$"},
		{"a$$", "a", "-"},
		{"$a", "x$a", "$a"},
		{"a^", "a^", "a^"},
		{"^a$", "aa", "-"},
	})
}

// TestQuantifiers covers "*" and "+", which match "the longest possible
// sequence", "-", which matches "the shortest possible sequence", and
// "?", "0 or 1 occurrence" (patterns(7)), each backtracking when what
// follows fails. A quantifier where no single character class precedes
// it is a plain character.
func TestQuantifiers(t *testing.T) {
	testMatches(t, []struct{ pat, s, want string }{
		{"^(a*)(a*)$", "aaa", "aaa|aaa|"},
		{"^(a-)(a*)$", "aaa", "aaa||aaa"},
		{"^(a+)(a*)$", "aaa", "aaa|aaa|"},
		{"^(a?)(a*)$", "aaa", "aaa|a|aa"},
		{"^a*$", "", ""},
		{"^a+$", "", "-"},
		{"^a-$", "", ""},
		{"^a?$", "", ""},
		{"^a*ab$", "aaab", "aaab"},
		{"^a+ab$", "aab", "aab"},
		{"^a+ab$", "ab", "-"},
		{"^a?a$", "a", "a"},
		{"^a?b$", "c", "-"},
		{"^a-b", "aabb", "aab"},
		{"^a-$", "aab", "-"},
		{"^a-b$", "aa", "-"},
		{"^%d+", "123x", "123"},
		{"^%d-x", "123x", "123x"},
		{"^[ab]+", "abc", "ab"},
		{".-/", "a/b/c", "a/"},
		{".*/", "a/b/c", "a/b/"},
		{"^*a$", "*a", "*a"},
		{"^+$", "+", "+"},
		{"^a**$", "aa*", "aa*"},
		{"^a**$", "aa", "-"},
		{"^%**$", "**", "**"},
	})
}

// TestCaptures: "A pattern can contain sub-patterns enclosed in
// parentheses; they describe captures", numbered by their left
// parentheses (patterns(7)). A capture is undone when what follows it
// fails, so the match that succeeds has only its own.
func TestCaptures(t *testing.T) {
	testMatches(t, []struct{ pat, s, want string }{
		{"((a)b)", "xab", "ab|ab|a"},
		{"(a)(b)", "xab", "ab|a|b"},
		{"^(a*(.)%w(%s*))", "aaa yz", "aaa y|aaa y| |"},
		{"(a*(.)%w(%s*))", "xaaa yz", "xa|xa|x|"},
		{"^(a?)a$", "a", "a|"},
		{"^a?(a)$", "a", "a|a"},
		{"^(a*)(a)$", "aaa", "aaa|aa|a"},
		{"(a+)b", "aac aab", "aab|aa"},
		{"%((a)%)", "(a)", "(a)|a"},
	})
}

// TestTooComplex: patterns.c gives up past MAXCCALLS (200) levels of
// recursion, and httpd then takes the location as not matching; below it
// the same pattern matches.
func TestTooComplex(t *testing.T) {
	short := "^" + strings.Repeat("a?", 150) + "$"
	if got := match(short, strings.Repeat("a", 150)); got == "-" {
		t.Errorf("150 a? on 150 a: no match")
	}
	long := "^" + strings.Repeat("a?", 250) + "$"
	if got := match(long, strings.Repeat("a", 250)); got != "-" {
		t.Errorf("250 a? on 250 a: matched")
	}
}

// TestCheckPatternCaptures checks the count of captures checkPattern
// gives CheckRewrite, and what it refuses: patterns(7)'s malformed
// patterns, and %b, %f, back references and position captures, which
// find does not support.
func TestCheckPatternCaptures(t *testing.T) {
	for pat, want := range map[string]int{
		"":                        0,
		"a":                       0,
		"(a)":                     1,
		"(a)(b)":                  2,
		"((a)b)":                  2,
		"%(a%)":                   0,
		"[(]":                     0,
		"[)]":                     0,
		"[(](a)":                  1,
		"%B":                      0,
		"%F":                      0,
		strings.Repeat("(a)", 32): 32,
		"[%(](a)[^)]":             1,
		"([]])":                   1,
		"^/code/(..-)/?$":         1,
		"%d+%.(%w*)[%-_]?$":       1,
		"[%]]":                    0,
		"[a-z](%%)":               1,
		"a(b(c(d)e)f)g":           3,
	} {
		n, err := checkPattern(pat)
		if err != nil || n != want {
			t.Errorf("checkPattern(%q) = %d, %v; want %d", pat, n, err, want)
		}
	}
	for pat, why := range map[string]string{
		"%":                       "ends with '%'",
		"a%":                      "ends with '%'",
		"[":                       "missing ']'",
		"[a":                      "missing ']'",
		"[]":                      "missing ']'",
		"[^]":                     "missing ']'",
		"[^":                      "missing ']'",
		"[%":                      "missing ']'",
		"[%]":                     "missing ']'",
		"[a%]":                    "missing ']'",
		"(a":                      "unfinished capture",
		"((a)":                    "unfinished capture",
		"a)":                      "invalid pattern capture",
		"(a))":                    "invalid pattern capture",
		")(":                      "invalid pattern capture",
		"()":                      "position captures",
		"a()":                     "position captures",
		"%b()":                    "%b is not supported",
		"%f[a]":                   "%f is not supported",
		"(a)%1":                   "back references",
		"%0":                      "back references",
		"%9":                      "back references",
		strings.Repeat("(a)", 33): "too many captures",
	} {
		if _, err := checkPattern(pat); err == nil || !strings.Contains(err.Error(), why) {
			t.Errorf("checkPattern(%q) = %v, want %q", pat, err, why)
		}
	}
}