package sandbox

import (
	"cmp"
	"errors"
	"fmt"
	"io/fs"
	"os"
	"path/filepath"
	"slices"
	"strings"

	"blinker/internal/policy"
)

// Both backends build the same thing from a policy: a list of paths, each
// with the access a mode has to it and everything under it, applied
// ancestors first so deeper paths override shallower ones. The paths are
// every place access can change: the rules' and the floor's literal paths,
// and what their globs match on disk right now. Under any path, access is
// that of its deepest listed ancestor, so evaluating each listed path with
// policy.Compiled.Access gives the kernel exactly the evaluator's answers.

type state int

const (
	none state = iota // neither readable nor writable
	ro
	rw
)

func stateOf(a policy.Access) state {
	switch {
	case a.Write:
		return rw
	case a.Read:
		return ro
	}
	return none
}

type mount struct {
	path   string
	state  state
	exists bool // on the host
	// dir is set when the host path is a directory, or, missing, would be
	// one: a rule names it as one, or something is to go inside it.
	dir bool
	// pin and block are set by guard, for bubblewrap.
	pin   bool // mount even if it changes nothing, so it cannot be renamed
	block bool // a missing path to keep from being created
}

// walkLimit caps the entries one command's glob expansion may visit. A
// command whose globs cannot be expanded fully does not run: a rule
// applied to only some of its matches would fail open.
var walkLimit = 500_000 // a variable for tests

var errTooManyFiles = errors.New("too many files")

// walk calls fn for root and every entry under it, without following
// symlinks, spending from budget.
func walk(root string, budget *int, fn func(string)) error {
	return filepath.WalkDir(root, func(p string, d fs.DirEntry, err error) error {
		if err != nil {
			// Unreadable to blinker means unreadable in the sandbox too:
			// nothing there to hide.
			return nil
		}
		if *budget <= 0 {
			return errTooManyFiles
		}
		*budget--
		fn(p)
		return nil
	})
}

// hasSymlink reports whether any component of p is a symlink. A rule's path
// is taken as written below its anchor, so a symlink there (perhaps planted
// by the agent) must not redirect the rule: such paths are left out, and
// the kernel judges whatever they point to by its own path.
func hasSymlink(p string) bool {
	cur := "/"
	for _, part := range strings.Split(strings.TrimPrefix(p, "/"), "/") {
		if part == "" {
			continue
		}
		cur = filepath.Join(cur, part)
		fi, err := os.Lstat(cur)
		if err != nil {
			return false // the rest does not exist
		}
		if fi.Mode()&fs.ModeSymlink != 0 {
			return true
		}
	}
	return false
}

// plan lists the mounts for a mode.
func plan(c *policy.Compiled) ([]mount, error) {
	paths := map[string]bool{}
	for _, p := range c.Literals() {
		paths[p] = true
	}
	// Walk only where a glob could match something the mode can see: a
	// glob's prefix, cut down to the readable trees inside it.
	var roots []string
	addRoots := func(globs []policy.Matcher, trees []string) {
		for _, g := range globs {
			for _, r := range trees {
				switch {
				case policy.Under(g.Prefix, r):
					roots = append(roots, g.Prefix)
				case policy.Under(r, g.Prefix):
					roots = append(roots, r)
				}
			}
		}
	}
	readable := append([]string{c.Env.Scratch}, c.Env.SystemRead...)
	for _, p := range c.Literals() {
		if c.Access(p).Read {
			readable = append(readable, p)
		}
	}
	ruleGlobs, floorGlobs := c.RuleGlobs(), c.FloorGlobs()
	addRoots(ruleGlobs, readable)
	// A glob that grants reading may match outside every readable tree,
	// so all of its prefix is searched (within walkLimit).
	for _, g := range c.GrantGlobs() {
		roots = append(roots, g.Prefix)
	}
	// The floor's globs (*.pem, id_rsa*, ...) catch keys lying around where
	// the agent works: the project. Walking every readable toolchain cache
	// for them on each command would be slow, and the floor's literal paths
	// already cover the usual credential stores.
	// The trees there to search are those the mode can read: the project,
	// or (if not) any readable inside it, such as a rule's .git.
	var inProject []string
	for _, r := range readable {
		if policy.Under(r, c.Env.Project) {
			inProject = append(inProject, r)
		}
	}
	if c.Access(c.Env.Project).Read {
		inProject = append(inProject, c.Env.Project)
	}
	addRoots(floorGlobs, inProject)
	globs := slices.Concat(ruleGlobs, floorGlobs)
	budget := walkLimit
	for _, root := range outermost(roots) {
		err := walk(root, &budget, func(p string) {
			if policy.MatchAnyExact(globs, p) {
				paths[p] = true
			}
		})
		if errors.Is(err, errTooManyFiles) {
			return nil, fmt.Errorf("the policy's glob rules cover more than %d files (under %s), too many to apply them; narrow the globs", walkLimit, root)
		}
		if err != nil {
			return nil, err
		}
	}

	var mounts []mount
	for p := range paths {
		fi, err := os.Lstat(p)
		exists := err == nil
		if exists && hasSymlink(p) {
			continue
		}
		dir := exists && fi.IsDir() || !exists && c.NamedDir(p)
		mounts = append(mounts, mount{path: p, state: stateOf(c.Access(p)), exists: exists, dir: dir})
	}
	sortMounts(mounts)
	return mounts, nil
}

// shownLinks lists the symlinks the policy's rules followed (see
// policy.Compiled.Links) whose real paths the mode may read, so a command
// can reach the file through the link as it would outside (~/.vimrc to a
// dotfiles repo). Rules only follow links no command can replace.
func shownLinks(c *policy.Compiled) []string {
	var out []string
	for _, l := range c.Links() {
		if c.Access(policy.RealPath(l)).Read {
			out = append(out, l)
		}
	}
	return out
}

// makeDirs makes the missing directories a rule names as directories
// (see policy.Matcher.Dir) and the mode may write, outside the project:
// a tool's cache, say, in a home the command cannot write, so cannot make
// it in. They stay, as caches do.
func makeDirs(c *policy.Compiled) error {
	for _, p := range c.Literals() {
		if !c.NamedDir(p) || policy.Under(p, c.Env.Project) || !c.Access(p).Write {
			continue
		}
		if err := mkdirNoFollow(p); err != nil {
			return fmt.Errorf("making %s: %w", p, err)
		}
	}
	return nil
}

// mkdirNoFollow makes p and the missing directories above it, unless p
// exists already. It makes them in the nearest directory above that
// exists, through an os.Root, which follows no symlink out of it: one put
// in place of a directory it has just made cannot send the rest
// elsewhere.
func mkdirNoFollow(p string) error {
	if _, err := os.Lstat(p); !errors.Is(err, fs.ErrNotExist) {
		return err // nil if there already, whatever it is
	}
	top, parent, err := missingTop(p)
	if err != nil {
		return err
	}
	dir := filepath.Dir(top)
	if !parent.IsDir() {
		return fmt.Errorf("%s is not a directory", dir)
	}
	root, err := os.OpenRoot(dir)
	if err != nil {
		return err
	}
	defer root.Close()
	rel, err := filepath.Rel(dir, p)
	if err != nil {
		return err
	}
	return root.MkdirAll(rel, 0o700)
}

// missingTop returns the highest of p and the directories above it whose
// parent exists, and what that parent is: p is missing from top down, if
// p itself is (which it does not look at). An error other than not
// existing stops it: what blinker cannot see is not taken for missing.
func missingTop(p string) (top string, parent fs.FileInfo, err error) {
	for top = p; ; top = filepath.Dir(top) {
		dir := filepath.Dir(top)
		fi, err := os.Lstat(dir)
		if err == nil {
			return top, fi, nil
		}
		if !errors.Is(err, fs.ErrNotExist) || dir == top {
			return "", nil, err
		}
	}
}

// sortMounts puts ancestors first.
func sortMounts(mounts []mount) {
	slices.SortFunc(mounts, func(a, b mount) int {
		return cmp.Or(
			cmp.Compare(strings.Count(a.path, "/"), strings.Count(b.path, "/")),
			cmp.Compare(a.path, b.path),
		)
	})
}

// guard adds what bubblewrap needs to keep the mounts' paths protected
// beyond what they show. A mount judges whatever sits at its mount point,
// not a name, so:
//
//   - A directory above a mount that gives less than writing is pinned:
//     mounted over itself, as a mount point cannot be renamed. Otherwise a
//     command could move the directory aside, and the next command, whose
//     mounts follow the names, would find the protected path unprotected
//     under its new name.
//   - A path that gives less than writing and does not exist would be
//     created freely inside a writable directory (a missing ~/.bashrc, or
//     .git/hooks). It is blocked instead, by a read-only empty file in its
//     place, or an empty directory where a directory is meant. Missing directories above it are made, and pinned. bubblewrap
//     makes these on the host, and Run removes the ones left empty.
//
// bwrapArgs mounts each only where the directory holding it is writable,
// the only place it matters. Seatbelt judges paths by name, so it needs no
// blocks, but a rename is judged by the names it changes, not the paths
// under them: seatbeltProfile pins too.
func guard(c *policy.Compiled, mounts []mount) []mount {
	index := map[string]int{}
	for i, m := range mounts {
		index[m.path] = i
	}
	at := func(p string) *mount {
		if i, ok := index[p]; ok {
			return &mounts[i]
		}
		fi, err := os.Lstat(p)
		index[p] = len(mounts)
		mounts = append(mounts, mount{path: p, state: stateOf(c.Access(p)), exists: err == nil, dir: err == nil && fi.IsDir()})
		return &mounts[len(mounts)-1]
	}
	for i := 0; i < len(mounts); i++ { // at grows mounts as this goes
		m := mounts[i]
		if m.state == rw || m.block || m.pin {
			continue
		}
		if !m.exists {
			// The highest missing directory above it, or itself.
			top, parent, err := missingTop(m.path)
			if err != nil || !parent.IsDir() {
				// Under a file (a worktree's .git, say): nothing can be
				// created there, and nothing can be mounted either. Nor
				// under what blinker cannot see, as commands cannot.
				continue
			}
			if hasSymlink(filepath.Dir(top)) {
				continue // judged by where the link leads, as plan does
			}
			// From the top down, the missing directories that may be
			// written are made, and the first that may not is blocked:
			// nothing below it can be created then.
			var missing []string
			for p := m.path; p != filepath.Dir(top); p = filepath.Dir(p) {
				missing = append([]string{p}, missing...)
			}
			for _, p := range missing {
				if e := at(p); e.state != rw || p == m.path {
					e.block = true
					e.dir = e.dir || p != m.path
					break
				}
			}
		}
		for a := filepath.Dir(m.path); a != "/"; a = filepath.Dir(a) {
			if e := at(a); !e.block {
				e.pin = true
			}
		}
	}
	sortMounts(mounts)
	return mounts
}

// outermost drops paths inside other paths of the list, and duplicates.
func outermost(paths []string) []string {
	slices.SortFunc(paths, func(a, b string) int { return cmp.Compare(len(a), len(b)) })
	var out []string
next:
	for _, p := range paths {
		for _, o := range out {
			if policy.Under(p, o) {
				continue next
			}
		}
		out = append(out, p)
	}
	return out
}