// Redirect and rewrite rules for static sites: a `_redirects` file at the root
// of a shipped tree, in the format Netlify introduced and Cloudflare Pages
// adopted. One rule per line, "source destination [status]":
//
//	/old            /new                301
//	/blog/*         /posts/:splat
//	/docs/:slug     /guide/:slug        302
//	/app/*          /app/index.html     200
//	https://www.example.com/*  https://example.com/:splat  301!
//
// The subset served here:
//
//   - A source is a path, or an http(s) URL whose host must match the
//     request's (the scheme is not compared: the edge serves https only).
//     A segment ":name" captures one path segment; a final "*" captures the
//     rest of the path, "" included, so "/blog/*" also matches "/blog"; a
//     non-empty splat keeps the request's trailing slash.
//     Matching is case-sensitive and ignores a trailing slash.
//   - A destination is a path, or for a redirect an http(s) URL. ":name" and
//     ":splat" are replaced with what the source captured; placeholders in a
//     URL's scheme or host are not. A request's query string is carried over
//     when the destination names none of its own.
//   - The status is 301 (the default), 302, 303, 307 or 308 for a redirect;
//     200 serves the destination's file at the request's URL (a rewrite) and
//     404 serves it with a 404 (a custom not-found page). A rewrite's
//     destination is always a file in the same tree, never another host.
//   - A file at the request path wins over every rule (Netlify's
//     "shadowing"), unless the status carries a trailing "!".
//   - The first matching rule applies. A line whose first field starts with
//     "#" is a comment, and so is everything from a field starting with "#".
//
// Netlify's conditions (Country=, Language=, Role=...), proxying to another
// host and the netlify.toml form are not supported. `carlos ship` refuses a
// tree whose _redirects has a line it cannot use (PackDir), so a site never
// ships rules the edge would ignore; the edge itself skips such a line and
// logs it, which only a tree packed by something else can reach.
package edge

import (
	"errors"
	"fmt"
	"net/url"
	"path"
	"strconv"
	"strings"
)

// redirectsFile is the rules file's name at the root of a static tree. The
// file is configuration, not content: the edge never serves it.
const redirectsFile = "_redirects"

// Limits on one _redirects file. Matching is a scan of every rule on each
// request the tree cannot answer, so the count is bounded the way Cloudflare
// Pages bounds it.
const (
	redirectsMaxBytes = 256 << 10
	redirectsMaxRules = 2000
	redirectsMaxLine  = 2048
)

// redirectRule is one parsed line of a _redirects file.
type redirectRule struct {
	line   int      // 1-based line number, for logs
	host   string   // lowercased; "" matches any host
	segs   []string // source path segments; ":name" captures one
	splat  bool     // the source ends in "*"
	prefix string   // a URL destination's "scheme://host", never substituted
	to     string   // the destination template after prefix
	status int
	force  bool // "!": applies even when a file exists at the request path
}

// redirectRules is a parsed _redirects file, immutable once built.
type redirectRules struct {
	rules []redirectRule
}

// isRedirect reports whether status is one a redirect rule may answer with.
func isRedirect(status int) bool {
	switch status {
	case 301, 302, 303, 307, 308:
		return true
	}
	return false
}

// parseRedirects parses a _redirects file. It returns the rules it could use
// and an error naming every line it could not; callers decide which matters.
// Ship refuses on any error, and the edge serves the usable rules.
func parseRedirects(data []byte) (*redirectRules, error) {
	if len(data) > redirectsMaxBytes {
		return nil, fmt.Errorf("%s is %d bytes; the limit is %d", redirectsFile, len(data), redirectsMaxBytes)
	}
	rs := &redirectRules{}
	var errs []error
	// A byte-order mark is what some editors save at the front; it is not
	// part of the first rule.
	text := strings.TrimPrefix(string(data), "\ufeff")
	for i, line := range strings.Split(text, "\n") {
		n := i + 1
		line = strings.TrimSpace(strings.TrimSuffix(line, "\r"))
		if line == "" || strings.HasPrefix(line, "#") {
			continue
		}
		if len(line) > redirectsMaxLine {
			errs = append(errs, fmt.Errorf("line %d: longer than %d characters", n, redirectsMaxLine))
			continue
		}
		rule, err := parseRedirectLine(line)
		if err != nil {
			errs = append(errs, fmt.Errorf("line %d: %v", n, err))
			continue
		}
		if len(rs.rules) == redirectsMaxRules {
			errs = append(errs, fmt.Errorf("line %d: more than %d rules", n, redirectsMaxRules))
			continue
		}
		rule.line = n
		rs.rules = append(rs.rules, rule)
	}
	return rs, errors.Join(errs...)
}

func parseRedirectLine(line string) (redirectRule, error) {
	var fields []string
	for _, f := range strings.Fields(line) {
		if strings.HasPrefix(f, "#") {
			break // the rest of the line is a comment
		}
		fields = append(fields, f)
	}
	var rule redirectRule
	switch {
	case len(fields) < 2:
		return rule, errors.New("want a source and a destination")
	case len(fields) > 3:
		if strings.Contains(fields[3], "=") {
			return rule, fmt.Errorf("conditions such as %q are not supported", fields[3])
		}
		return rule, fmt.Errorf("unexpected %q after the status", fields[3])
	}

	rule.status = 301
	if len(fields) == 3 {
		st := fields[2]
		if s, ok := strings.CutSuffix(st, "!"); ok {
			rule.force, st = true, s
		}
		code, err := strconv.Atoi(st)
		if err != nil || !(isRedirect(code) || code == 200 || code == 404) {
			return rule, fmt.Errorf("status %q: want 301, 302, 303, 307, 308, 200 or 404, optionally followed by !", fields[2])
		}
		rule.status = code
	}

	src := fields[0]
	if strings.HasPrefix(src, "http://") || strings.HasPrefix(src, "https://") {
		u, err := url.Parse(src)
		if err != nil || u.Host == "" || u.User != nil || u.Port() != "" || u.RawQuery != "" || u.Fragment != "" {
			return rule, fmt.Errorf("source %q: want a URL with only a host and a path", src)
		}
		rule.host = serverName(u.Hostname()) // as requestHost normalizes the request's
		src = u.Path
		if src == "" {
			src = "/"
		}
	}
	if !strings.HasPrefix(src, "/") {
		return rule, fmt.Errorf("source %q: want a path starting with / or an http(s) URL", fields[0])
	}
	if strings.ContainsAny(src, "?#") {
		return rule, fmt.Errorf("source %q: query strings and fragments are not matched", fields[0])
	}
	names := map[string]bool{}
	trimmed := strings.Trim(src, "/")
	for _, seg := range strings.Split(trimmed, "/") {
		switch {
		case seg == "":
			if trimmed != "" {
				return rule, fmt.Errorf("source %q: empty path segment", fields[0])
			}
		case rule.splat:
			return rule, fmt.Errorf("source %q: * must be the last segment", fields[0])
		case seg == "*":
			rule.splat = true
		case strings.Contains(seg, "*"):
			return rule, fmt.Errorf("source %q: * must be a whole segment", fields[0])
		case strings.HasPrefix(seg, ":"):
			name := seg[1:]
			if !validPlaceholder(name) || name == "splat" {
				return rule, fmt.Errorf("source %q: bad placeholder %q", fields[0], seg)
			}
			if names[name] {
				return rule, fmt.Errorf("source %q: placeholder %q appears twice", fields[0], seg)
			}
			names[name] = true
			rule.segs = append(rule.segs, seg)
		default:
			// Requests match decoded, as files are found, so a literal
			// segment is decoded here to meet them: "/caf%C3%A9" matches a
			// request for /café. A decoded "/" would be two segments, and
			// no request path has one inside a segment.
			dec, err := url.PathUnescape(seg)
			if err != nil || strings.Contains(dec, "/") {
				return rule, fmt.Errorf("source %q: bad percent-encoding in %q", fields[0], seg)
			}
			if strings.HasPrefix(dec, ":") {
				return rule, fmt.Errorf("source %q: %q would read as a placeholder", fields[0], seg)
			}
			if dec == "." || dec == ".." {
				return rule, fmt.Errorf("source %q: dot segments never match", fields[0])
			}
			rule.segs = append(rule.segs, dec)
		}
	}

	dst := fields[1]
	switch {
	case strings.HasPrefix(dst, "http://") || strings.HasPrefix(dst, "https://"):
		if !isRedirect(rule.status) {
			return rule, fmt.Errorf("destination %q: a %d serves a file from this site, so it takes a path, not a URL", dst, rule.status)
		}
		u, err := url.Parse(dst)
		if err != nil || u.Host == "" || u.User != nil {
			return rule, fmt.Errorf("destination %q: not a usable URL", dst)
		}
		i := len(u.Scheme) + len("://") + len(u.Host)
		if !strings.EqualFold(dst[:i], u.Scheme+"://"+u.Host) {
			return rule, fmt.Errorf("destination %q: not a usable URL", dst)
		}
		rule.prefix, rule.to = dst[:i], dst[i:]
		if rule.to != "" && !strings.ContainsAny(rule.to[:1], "/?#") {
			return rule, fmt.Errorf("destination %q: not a usable URL", dst)
		}
	case strings.HasPrefix(dst, "//") || strings.HasPrefix(dst, "/\\"):
		return rule, fmt.Errorf("destination %q: name another host with https://", dst)
	case strings.HasPrefix(dst, "/"):
		rule.to = dst
	default:
		return rule, fmt.Errorf("destination %q: want a path starting with / or an http(s) URL", dst)
	}
	return rule, nil
}

// validPlaceholder: a placeholder name is letters, digits and underscores.
func validPlaceholder(name string) bool {
	if name == "" {
		return false
	}
	for _, c := range name {
		if !(c == '_' || c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
			return false
		}
	}
	return true
}

// match reports whether the rule applies to a request for host whose cleaned
// path splits into reqSegs, and returns what the source captured.
func (rule *redirectRule) match(host string, reqSegs []string) (map[string]string, bool) {
	if rule.host != "" && rule.host != host {
		return nil, false
	}
	if len(reqSegs) < len(rule.segs) || !rule.splat && len(reqSegs) != len(rule.segs) {
		return nil, false
	}
	var caps map[string]string
	for i, seg := range rule.segs {
		if strings.HasPrefix(seg, ":") {
			if caps == nil {
				caps = map[string]string{}
			}
			caps[seg[1:]] = reqSegs[i]
		} else if seg != reqSegs[i] {
			return nil, false
		}
	}
	if rule.splat {
		if caps == nil {
			caps = map[string]string{}
		}
		caps["splat"] = strings.Join(reqSegs[len(rule.segs):], "/")
	}
	return caps, true
}

// expand substitutes the captures into the destination template. With escape
// set, values are percent-encoded for a Location header: per segment in the
// path, as a query value after "?". Without it they go in raw, for a rewrite's
// file lookup. A ":name" the source did not capture stays as written.
func expand(t string, caps map[string]string, escape bool) string {
	var b strings.Builder
	inQuery := false
	for i := 0; i < len(t); {
		c := t[i]
		if c == '?' || c == '#' {
			inQuery = true
		}
		if c != ':' {
			b.WriteByte(c)
			i++
			continue
		}
		j := i + 1
		for j < len(t) && validPlaceholder(t[j:j+1]) {
			j++
		}
		v, ok := caps[t[i+1:j]]
		if !ok {
			b.WriteString(t[i:j])
			i = j
			continue
		}
		switch {
		case !escape:
			b.WriteString(v)
		case inQuery:
			b.WriteString(url.QueryEscape(v))
		default:
			parts := strings.Split(v, "/")
			for k, p := range parts {
				parts[k] = url.PathEscape(p)
			}
			b.WriteString(strings.Join(parts, "/"))
		}
		i = j
	}
	return b.String()
}

// redirectAction is what a matched rule asks the handler to do.
type redirectAction struct {
	status   int
	location string // a redirect's Location
	file     string // a rewrite's cleaned, rooted path within the tree
}

// resolve finds the first rule that applies to r's host and the cleaned path
// p. exists is whether the tree has a file at p, which shadows every rule not
// forced. rawPath and rawQuery are the request's own, used to refuse a
// redirect to the URL being requested, which would loop.
func (rs *redirectRules) resolve(host, p, rawPath, rawQuery string, exists bool) (redirectAction, bool) {
	if rs == nil || len(rs.rules) == 0 {
		return redirectAction{}, false
	}
	var reqSegs []string
	if p != "/" {
		reqSegs = strings.Split(p[1:], "/")
	}
	for i := range rs.rules {
		rule := &rs.rules[i]
		if exists && !rule.force {
			continue
		}
		caps, ok := rule.match(host, reqSegs)
		if !ok {
			continue
		}
		if sp := caps["splat"]; sp != "" && strings.HasSuffix(rawPath, "/") {
			// The cleaned path lost it, and a page moved from /about/ to
			// /about resolves its relative links against the wrong directory.
			caps["splat"] = sp + "/"
		}
		if !isRedirect(rule.status) {
			// The template's own query and fragment are cut BEFORE the
			// captures go in: a decoded capture can hold "?" or "#", and it
			// is part of the file's name, not the end of it.
			to := rule.to
			if k := strings.IndexAny(to, "?#"); k >= 0 {
				to = to[:k]
			}
			return redirectAction{status: rule.status, file: path.Clean("/" + expand(to, caps, false))}, true
		}
		// loc is the destination after any scheme://host: path, query.
		loc := expand(rule.to, caps, true)
		frag := ""
		if k := strings.IndexByte(loc, '#'); k >= 0 {
			loc, frag = loc[:k], loc[k:]
		}
		if rule.prefix == "" {
			// Cleaned here, as http.Redirect would clean it, so the loop
			// check below sees the Location that is actually sent. Clean
			// also folds the "//" an empty capture can leave at the front,
			// which a browser would read as another host.
			pth, q, hasQ := strings.Cut(loc, "?")
			trailing := strings.HasSuffix(pth, "/")
			pth = path.Clean("/" + pth)
			if trailing && pth != "/" {
				pth += "/"
			}
			loc = pth
			if hasQ {
				loc += "?" + q
			}
		}
		if !strings.Contains(loc, "?") && rawQuery != "" {
			loc += "?" + rawQuery
		}
		if rule.prefix == "" || hostOf(rule.prefix) == host {
			pth, q, _ := strings.Cut(loc, "?")
			if pth == "" {
				pth = "/"
			}
			if u, err := url.Parse(pth); err == nil && u.Path == rawPath && q == rawQuery {
				continue // a redirect to this very URL
			}
		}
		return redirectAction{status: rule.status, location: rule.prefix + loc + frag}, true
	}
	return redirectAction{}, false
}

// hostOf is the host of a "scheme://host[:port]" prefix, normalized as
// requestHost normalizes a request's.
func hostOf(prefix string) string {
	_, h, _ := strings.Cut(prefix, "://")
	return requestHost(h)
}