package policy

import (
	"errors"
	"fmt"
	"io/fs"
	"os"
	"path"
	"path/filepath"
	"strings"
	"unicode"
)

// Rule paths are globs: "*" and "?" match within one path component,
// "[abc]" one of a set of characters, and a "**" component any number of
// directories, none included. Unlike in the shell, a leading "." is not
// special: "*" matches ".env". A path without wildcards names one path. A
// rule that matches a directory covers everything inside it, as a mount
// does. Paths are relative to the project unless they start with "/" or
// "~/". A path "$NAME" names the directories in an environment variable
// (see envPaths).

// ValidatePath rejects a rule path that is empty, climbs with "..", is a
// malformed glob, holds characters that could break out of a generated
// sandbox profile's string literal, or uses "$" other than as a whole
// "$NAME".
func ValidatePath(p string) error {
	if p == "" {
		return errors.New("empty path")
	}
	if IsVarPath(p) {
		return validateVarPath(p)
	}
	if name, ok := strings.CutPrefix(p, "$"); ok {
		if !validVarName(name) {
			return fmt.Errorf("%q: a variable must be the whole path, as $NAME", p)
		}
		if EnvFloored(name) {
			return fmt.Errorf("%q: %s is never available to commands", p, name)
		}
		return nil
	}
	if strings.Contains(p, "$") {
		return fmt.Errorf("%q: a variable must be the whole path, as $NAME", p)
	}
	for _, c := range p {
		// Control and format characters (bidi overrides, zero-width
		// spaces) would make a rule read as something it does not match.
		if unicode.IsControl(c) || unicode.Is(unicode.Cf, c) || c == '"' || c == '\\' {
			return fmt.Errorf("illegal character %U in path %q", c, p)
		}
	}
	// Policy files cannot hold one at either end (see field), so a rule
	// made in code must not either: it would read back as another path.
	if strings.TrimSpace(p) != p {
		return fmt.Errorf("%q: a path cannot start or end with a space", p)
	}
	if strings.HasPrefix(p, "~") && p != "~" && !strings.HasPrefix(p, "~/") {
		return fmt.Errorf("~user paths are not supported: %q", p)
	}
	for _, part := range strings.Split(p, "/") {
		if part == ".." {
			return fmt.Errorf(`".." is not allowed in paths: %q`, p)
		}
		if _, err := path.Match(part, ""); err != nil {
			return fmt.Errorf("bad glob %q: %w", p, err)
		}
	}
	return nil
}

// Expand turns a rule path into an absolute, cleaned one: "~" is home,
// and relative paths are under the project. Symlinks are not resolved.
func Expand(p, home, project string) string {
	switch {
	case p == "~":
		return home
	case strings.HasPrefix(p, "~/"):
		return filepath.Join(home, p[2:])
	case strings.HasPrefix(p, "/"):
		return filepath.Clean(p)
	}
	return filepath.Join(project, p)
}

// IsEnvPath reports whether a rule path is "$NAME".
func IsEnvPath(p string) bool { return strings.HasPrefix(p, "$") && !IsVarPath(p) }

// IsVarPath reports whether a rule path starts with "${NAME:-default}":
// the directory the variable names, or the default where it names none,
// and then the rest of the path. The default may be another such.
func IsVarPath(p string) bool { return strings.HasPrefix(p, "${") }

// splitVarPath splits "${NAME:-default}rest" into its parts.
func splitVarPath(p string) (name, def, rest string, err error) {
	body, ok := strings.CutPrefix(p, "${")
	if !ok {
		return "", "", "", fmt.Errorf("%q does not start with ${", p)
	}
	depth := 1
	for i := range len(body) {
		switch body[i] {
		case '{':
			depth++
		case '}':
			if depth--; depth == 0 {
				name, def, ok := strings.Cut(body[:i], ":-")
				if !ok {
					return "", "", "", fmt.Errorf("%q: write a variable as ${NAME:-default}", p)
				}
				return name, def, body[i+1:], nil
			}
		}
	}
	return "", "", "", fmt.Errorf("%q: no } closes the variable", p)
}

// validateVarPath checks a "${NAME:-default}rest" rule path: a variable's
// name, a default that is a plain path without wildcards or another such,
// and a rest that is empty or a path under it.
func validateVarPath(p string) error {
	name, def, rest, err := splitVarPath(p)
	if err != nil {
		return err
	}
	if !validVarName(name) {
		return fmt.Errorf("%q: bad variable name %q", p, name)
	}
	if IsVarPath(def) {
		if err := validateVarPath(def); err != nil {
			return err
		}
	} else if err := ValidatePath(def); err != nil || IsEnvPath(def) || IsGlob(def) || strings.ContainsAny(def, "{}") {
		return fmt.Errorf("%q: the default must be a plain path", p)
	}
	if rest != "" && !strings.HasPrefix(rest, "/") {
		return fmt.Errorf("%q: after the variable comes / and the rest of the path", p)
	}
	if strings.ContainsAny(rest, "{}") {
		return fmt.Errorf("%q: only the start of a path can be a variable", p)
	}
	if rest != "" {
		return ValidatePath("/x" + rest) // the rest, as a path's tail
	}
	return nil
}

// resolveVarPath turns a "${NAME:-default}rest" rule path into the path it
// names now. The variable counts only if it holds one directory that
// varDir accepts; otherwise the default does, as the XDG spec says of a
// relative path and the tools themselves do. The value is returned as
// written, so the symlinks in it are followed, and checked, as any rule's
// are. The default is left as written (~/x, or relative to the project).
func resolveVarPath(p, home, project string) (string, error) {
	name, def, rest, err := splitVarPath(p)
	if err != nil {
		return "", err
	}
	base := def
	if IsVarPath(def) {
		if base, err = resolveVarPath(def, home, project); err != nil {
			return "", err
		}
	}
	if v := os.Getenv(name); !strings.Contains(v, ":") { // one path, not a list
		if _, _, ok := varDir(v, home, project); ok {
			base = filepath.Clean(v)
		}
	}
	return base + rest, nil
}

// IsGlob reports whether a path holds glob characters.
func IsGlob(p string) bool { return strings.ContainsAny(p, "*?[") }

// parts splits a clean absolute path into its components: it takes ".."
// for a name like any other.
func parts(p string) []string {
	if p == "/" {
		return nil
	}
	return strings.Split(strings.TrimPrefix(p, "/"), "/")
}

// matchParts reports whether a path's components match a glob's.
func matchParts(glob, elems []string) bool {
	for len(glob) > 0 {
		if glob[0] == "**" {
			if len(glob) == 2 && glob[1] != "**" {
				// Only the last component can match what follows, so
				// trying every split, as below, would answer the same.
				return len(elems) > 0 && matchParts(glob[1:], elems[len(elems)-1:])
			}
			for i := 0; i <= len(elems); i++ {
				if matchParts(glob[1:], elems[i:]) {
					return true
				}
			}
			return false
		}
		if len(elems) == 0 {
			return false
		}
		if strings.ContainsAny(glob[0], `*?[\`) {
			if ok, err := path.Match(glob[0], elems[0]); err != nil || !ok {
				return false
			}
		} else if glob[0] != elems[0] {
			return false // what path.Match does with no special characters
		}
		glob, elems = glob[1:], elems[1:]
	}
	return len(elems) == 0
}

// Matcher matches the paths a rule path names.
type Matcher struct {
	// Path is absolute. For a glob, it is the expanded pattern, and
	// Prefix is the directory above its first wildcard.
	Path   string
	Prefix string
	// Dir is set when the rule path ends in "/": it names a directory,
	// which the sandbox makes (or blocks) as one if it is missing.
	Dir  bool
	glob []string // a glob's components; nil for a plain path
}

// NewMatcher prepares a rule path. A trailing "/**" adds nothing, since a
// rule covers what is inside the directories it matches, so "dir/**" is
// the plain path "dir", which needs no search of the filesystem.
//
// A path outside the project names a place the user chose (~/.vimrc, a
// link into a dotfiles repo), so the symlinks in its part before any
// wildcard are resolved now, as the kernel will see them (Compile refuses
// one that commands could change; see resolveLinks). A path in the
// project (whose real path is fixed for the session) keeps the rest as
// written: what is in it is not the user's choice, and a symlink planted
// there cannot redirect a rule.
func NewMatcher(rulePath, home, project string) (Matcher, error) {
	m, _, err := newMatcher(rulePath, home, project)
	return m, err
}

// newMatcher is NewMatcher, also returning the symlinks it followed.
func newMatcher(rulePath, home, project string) (Matcher, []string, error) {
	if err := ValidatePath(rulePath); err != nil {
		return Matcher{}, nil, err
	}
	if IsEnvPath(rulePath) {
		return Matcher{}, nil, fmt.Errorf("%q names a variable's directories, not one path", rulePath)
	}
	if IsVarPath(rulePath) {
		var err error
		if rulePath, err = resolveVarPath(rulePath, home, project); err != nil {
			return Matcher{}, nil, err
		}
	}
	p := Expand(rulePath, home, project)
	for strings.HasSuffix(p, "/**") {
		p = strings.TrimSuffix(p, "/**")
	}
	if p == "" {
		p = "/"
	}
	var links []string
	if !Under(p, project) {
		// Only the part before the first wildcard: a file named "*" is no
		// wildcard's to follow.
		lit, rest := parts(p), []string(nil)
		for i, part := range lit {
			if IsGlob(part) {
				lit, rest = lit[:i], lit[i:]
				break
			}
		}
		var real string
		real, links = resolveLinks("/" + strings.Join(lit, "/"))
		p = filepath.Join(append([]string{real}, rest...)...)
	}
	dir := strings.HasSuffix(rulePath, "/")
	if !IsGlob(p) {
		return Matcher{Path: p, Dir: dir}, links, nil
	}
	glob := parts(p)
	prefix := "/"
	for i, part := range glob {
		if IsGlob(part) {
			prefix = "/" + strings.Join(glob[:i], "/")
			break
		}
	}
	return Matcher{Path: p, Prefix: prefix, Dir: dir, glob: glob}, links, nil
}

// IsGlob reports whether the matcher needs the filesystem searched to find
// what it matches.
func (m Matcher) IsGlob() bool { return m.glob != nil }

// Match reports whether the matcher covers path: path is a match, or
// inside one.
func (m Matcher) Match(p string) bool {
	if m.glob == nil {
		return Under(p, m.Path)
	}
	if !Under(p, m.Prefix) {
		return false
	}
	elems := parts(p)
	for i := len(elems); i >= 0; i-- {
		if matchParts(m.glob, elems[:i]) {
			return true
		}
	}
	return false
}

// MatchAnyExact reports whether one of ms matches p itself, rather than
// something p is inside, splitting p into its components once for all of
// them.
func MatchAnyExact(ms []Matcher, p string) bool {
	var elems []string
	for _, m := range ms {
		switch {
		case m.glob == nil:
			if p == m.Path {
				return true
			}
		case Under(p, m.Prefix):
			if elems == nil {
				elems = parts(p)
			}
			if matchParts(m.glob, elems) {
				return true
			}
		}
	}
	return false
}

// Covers reports whether every path o matches, m matches too, so a later
// rule m leaves an earlier rule o nothing to decide. It only answers yes
// when that is certain.
func (m Matcher) Covers(o Matcher) bool {
	if m.Path == o.Path {
		return true
	}
	if o.glob == nil {
		return m.Match(o.Path)
	}
	// Everything a glob matches is under its prefix.
	return m.glob == nil && Under(o.Prefix, m.Path)
}

// Under reports whether path is dir or inside it. An empty dir (such as an
// Env without a scratch dir) contains nothing. It compares the strings, so
// both must be clean absolute paths (see filepath.Clean): "/p/../etc" is
// under "/p" here.
func Under(path, dir string) bool {
	if dir == "" {
		return false
	}
	// As strings.HasPrefix(path, dir+"/"), without making that string.
	return path == dir || dir == "/" || len(path) > len(dir) && path[len(dir)] == '/' && strings.HasPrefix(path, dir)
}

// ResolveExisting resolves the symlinks in the longest existing prefix of
// p, keeping the rest as written.
func ResolveExisting(p string) string {
	var tail []string
	cur := p
	for {
		if r, err := filepath.EvalSymlinks(cur); err == nil {
			return filepath.Join(append([]string{r}, tail...)...)
		}
		parent := filepath.Dir(cur)
		if parent == cur {
			return p
		}
		tail = append([]string{filepath.Base(cur)}, tail...)
		cur = parent
	}
}

// resolveLinks resolves the symlinks in an absolute path as the kernel
// would, a dangling last one included, keeping what does not exist as
// written, and lists each symlink it followed, links within links too.
func resolveLinks(p string) (string, []string) {
	var links []string
	todo, cur := parts(filepath.Clean(p)), "/"
	for hops := 0; len(todo) > 0; {
		next := filepath.Join(cur, todo[0])
		fi, err := os.Lstat(next)
		if err != nil {
			return filepath.Join(append([]string{cur}, todo...)...), links
		}
		if fi.Mode()&fs.ModeSymlink == 0 {
			cur, todo = next, todo[1:]
			continue
		}
		target, err := os.Readlink(next)
		if hops++; err != nil || hops > 40 {
			return filepath.Clean(p), links // a loop: as written, which matches nothing real
		}
		links = append(links, next)
		if !filepath.IsAbs(target) {
			target = filepath.Join(cur, target) // cur holds no symlinks, so ".." is plain
		}
		todo, cur = append(parts(filepath.Clean(target)), todo[1:]...), "/"
	}
	return cur, links
}

// RealPath resolves where an operation on p lands: the symlinks of its
// existing prefix, and a final symlink even if it dangles (writing through
// it creates its target).
func RealPath(p string) string {
	for range 40 {
		fi, err := os.Lstat(p)
		if err != nil || fi.Mode()&fs.ModeSymlink == 0 {
			break
		}
		if r, err := filepath.EvalSymlinks(p); err == nil {
			return r
		}
		target, err := os.Readlink(p)
		if err != nil {
			break
		}
		if !filepath.IsAbs(target) {
			target = filepath.Join(filepath.Dir(p), target)
		}
		p = filepath.Clean(target)
	}
	return ResolveExisting(p)
}