compile.go

package dyfields

import (
	"fmt"
	"regexp"
	"strings"
)

// MaxDepth caps object_list nesting. A schema can come from an end user, so the
// depth needs an upper bound rather than trust.
const MaxDepth = 5

// Compiled is a validated schema, ready to check values against. It is
// read-only and safe for concurrent use: patterns are pre-compiled and the
// dependency graph is already built.
type Compiled struct {
	schema Schema
	root   *cscope
	groups []*cgroup

	// clientOnly holds the valid_when rules that read a transient field, and
	// so can only be answered where the transient value exists. See
	// markClientOnly.
	clientOnly map[*Rule]bool
}

type cscope struct {
	parent        *cscope
	depth         int
	fields        []*cfield
	byName        map[string]*cfield
	hasSecretDeep bool
}

func newScope(parent *cscope) *cscope {
	d := 0
	if parent != nil {
		d = parent.depth + 1
	}
	return &cscope{parent: parent, depth: d, byName: map[string]*cfield{}}
}

type cfield struct {
	f     *Field
	scope *cscope
	group string
	path  string // schema path, e.g. "sinks.mappings.secret_salt"

	isToggle    bool
	toggleGroup string

	pattern     *regexp.Regexp
	keyPattern  *regexp.Regexp
	itemPattern *regexp.Regexp

	child          *cscope
	requiresItemID bool
}

type cgroup struct {
	g      *Group
	toggle *cfield
	fields []*cfield
}

var tmplRe = regexp.MustCompile(`\{([A-Za-z0-9_]+)\}`)

// Compile checks that the schema is internally consistent: names unique,
// references resolvable and acyclic, containers well-formed. Errors are
// returned as SchemaErrors so a form builder can show them per field.
func Compile(s Schema) (*Compiled, error) {
	c := &Compiled{schema: s, root: newScope(nil)}
	var errs SchemaErrors

	seenGroup := map[string]bool{}
	for _, g := range s.Groups {
		if g == nil {
			continue
		}
		if g.Key == "" {
			errs = append(errs, SchemaError{Code: CodeBadType, Reason: "group key must not be empty"})
			continue
		}
		if seenGroup[g.Key] {
			errs = append(errs, SchemaError{Path: g.Key, Group: g.Key,
				Code: CodeDuplicateGroup, Reason: fmt.Sprintf("group key %q is declared twice", g.Key)})
			continue
		}
		seenGroup[g.Key] = true

		cg := &cgroup{g: g}
		switch g.Mode {
		case ModeAlways, ModeCollapsible:
		case ModeToggleable:
			if g.Toggle == nil || g.Toggle.Field == "" {
				errs = append(errs, SchemaError{Path: g.Key, Group: g.Key, Code: CodeMissingToggle,
					Reason: "toggleable group must declare a toggle"})
			}
		case "":
			g.Mode = ModeAlways
		default:
			errs = append(errs, SchemaError{Path: g.Key, Group: g.Key, Code: CodeBadType,
				Reason: fmt.Sprintf("unknown group mode %q", g.Mode)})
		}

		// A toggle implicitly declares its boolean field. It must not be
		// declared again anywhere, otherwise the UI would draw it twice.
		if g.Toggle != nil && g.Toggle.Field != "" {
			tf := &Field{
				Name:      g.Toggle.Field,
				Type:      TypeBoolean,
				Label:     g.Toggle.Label,
				LabelI18n: g.Toggle.I18n,
				Default:   g.Toggle.Default,
			}
			cf := &cfield{f: tf, scope: c.root, group: g.Key, path: tf.Name,
				isToggle: true, toggleGroup: g.Key}
			if _, dup := c.root.byName[tf.Name]; dup {
				errs = append(errs, SchemaError{Path: tf.Name, Group: g.Key, Code: CodeDuplicateName,
					Reason: fmt.Sprintf("toggle field %q collides with another field", tf.Name)})
			} else {
				c.root.byName[tf.Name] = cf
				c.root.fields = append(c.root.fields, cf)
				cg.toggle = cf
			}
		}

		for _, f := range g.Fields {
			cf, fe := c.buildField(f, c.root, g.Key, "")
			errs = append(errs, fe...)
			if cf != nil {
				cg.fields = append(cg.fields, cf)
			}
		}
		c.groups = append(c.groups, cg)
	}

	// References can only be checked once every scope exists.
	errs = append(errs, c.checkRefs()...)
	errs = append(errs, c.checkCycles()...)

	if len(errs) > 0 {
		return nil, errs
	}
	c.markClientOnly()
	return c, nil
}

// markClientOnly records which valid_when rules read a transient field.
//
// A transient value is dropped from Validate's own output, so it is never in a
// payload, never in a patch, and never in the document a server stores. A rule
// that reads one therefore has exactly one place it can be answered: the form
// that holds the value. Asked anywhere else it does not merely lack an answer,
// it produces a wrong one -- "confirm your password" against a document that
// structurally cannot contain a confirmation reads as a failure every time.
//
// Apply is the "anywhere else". It skips these; see Compiled.Apply.
func (c *Compiled) markClientOnly() {
	c.clientOnly = map[*Rule]bool{}

	reads := func(cond *Condition, sc *cscope) bool {
		for _, r := range cond.refs() {
			if t := resolveRef(sc, r); t != nil && t.f.Transient {
				return true
			}
		}
		return false
	}
	for _, g := range c.groups {
		for _, r := range g.g.ValidWhen {
			if r != nil && reads(r.When, c.root) {
				c.clientOnly[r] = true
			}
		}
	}
	c.walk(func(cf *cfield) {
		for _, r := range cf.f.ValidWhen {
			// A rule hung on a transient field belongs to it whether or not it
			// names it, so both ways of writing the same rule behave alike.
			if r != nil && (cf.f.Transient || reads(r.When, cf.scope)) {
				c.clientOnly[r] = true
			}
		}
	})
}

// buildField validates one field and, for object_list, recurses into its scope.
func (c *Compiled) buildField(f *Field, sc *cscope, group, prefix string) (*cfield, SchemaErrors) {
	var errs SchemaErrors
	if f == nil {
		return nil, errs
	}
	path := f.Name
	if prefix != "" {
		path = prefix + "." + f.Name
	}
	bad := func(code, format string, args ...any) {
		errs = append(errs, SchemaError{Path: path, Group: group, Code: code,
			Reason: fmt.Sprintf(format, args...)})
	}

	if f.Name == "" {
		bad(CodeBadType, "field name must not be empty")
		return nil, errs
	}
	if strings.HasPrefix(f.Name, "$") {
		bad(CodeBadType, "field name %q must not start with $, which is reserved", f.Name)
	}
	// Names are joined with dots to form secrets keys and with brackets to
	// form error paths. A name carrying either character makes both ambiguous
	// -- "a.b.token" could be two different fields -- which is the same reason
	// $id has a restricted charset.
	if i := strings.IndexAny(f.Name, ".[]"); i >= 0 {
		bad(CodeBadType, "field name %q must not contain %q; names are joined into paths",
			f.Name, f.Name[i:i+1])
	}
	if !f.Type.valid() {
		bad(CodeBadType, "unknown field type %q", f.Type)
		return nil, errs
	}
	if _, dup := sc.byName[f.Name]; dup {
		bad(CodeDuplicateName, "field name %q is declared twice in the same scope", f.Name)
		return nil, errs
	}

	cf := &cfield{f: f, scope: sc, group: group, path: path}

	// Shape rules: each modifier belongs to exactly one family of types.
	if f.Type == TypeEnum {
		if len(f.Options) == 0 {
			bad(CodeBadOptions, "enum must declare options")
		}
		seen := map[string]bool{}
		for _, o := range f.Options {
			k := fmt.Sprintf("%v", o.Value)
			if seen[k] {
				bad(CodeBadOptions, "option value %v is declared twice", o.Value)
			}
			seen[k] = true
		}
	} else if len(f.Options) > 0 {
		bad(CodeBadOptions, "only enum may declare options")
	}
	if f.Multiple && f.Type != TypeEnum {
		bad(CodeBadType, "only enum may set multiple")
	}

	switch f.Type {
	case TypeList, TypeMap:
		switch {
		case f.Items == nil:
			bad(CodeMissingItems, "%s must declare items", f.Type)
		case f.Items.Type == TypeSecret:
			// A container lives in values, and secrets never do. Allowing this
			// would put secret values in the one place the design guarantees
			// they cannot be.
			bad(CodeBadType, "items type must not be secret; a container's values live in the values document")
		case f.Items.Type == TypeEnum:
			if len(f.Items.Options) == 0 {
				bad(CodeBadOptions, "enum items must declare options")
			}
		case !f.Items.Type.IsScalar():
			bad(CodeBadType, "items type %q must be scalar", f.Items.Type)
		}
		if f.Items != nil && f.Items.Type != TypeEnum && len(f.Items.Options) > 0 {
			bad(CodeBadOptions, "only enum items may declare options")
		}
		if len(f.Fields) > 0 {
			bad(CodeBadType, "only object_list may declare fields")
		}
	case TypeObjectList:
		if len(f.Fields) == 0 {
			bad(CodeMissingFields, "object_list must declare fields")
		}
		if f.Items != nil {
			bad(CodeBadType, "object_list uses fields, not items")
		}
	default:
		if f.Items != nil {
			bad(CodeBadType, "only list and map may declare items")
		}
		if len(f.Fields) > 0 {
			bad(CodeBadType, "only object_list may declare fields")
		}
	}

	if f.KeyPattern != "" {
		if f.Type != TypeMap {
			bad(CodeBadType, "only map may declare key_pattern")
		} else if re, err := regexp.Compile(f.KeyPattern); err != nil {
			bad(CodeBadPattern, "key_pattern does not compile: %v", err)
		} else {
			cf.keyPattern = re
		}
	}
	if f.Type.IsContainer() {
		// required and min_items would say the same thing; two mechanisms for
		// one meaning is how callers end up guessing which wins.
		if f.Required {
			bad(CodeContainerReq, "container fields use min_items, not required")
		}
	} else {
		if f.MinItems != nil || f.MaxItems != nil {
			bad(CodeBadType, "only container fields may declare min_items/max_items")
		}
	}
	if f.Type != TypeObjectList && (len(f.Unique) > 0 || f.ItemLabel != "" || f.Layout != "") {
		bad(CodeBadType, "only object_list may declare unique/item_label/layout")
	}

	// A constraint on a type that cannot honour it is a silent no-op, and a
	// validation rule that quietly does nothing is the failure this whole
	// design keeps guarding against. Say so instead.
	textual := f.Type == TypeString || f.Type == TypeSecret || f.Type == TypeFile
	numeric := f.Type == TypeInteger || f.Type == TypeNumber || f.Type == TypeDecimal
	if !textual && (f.Pattern != "" || f.MinLength != nil || f.MaxLength != nil) {
		bad(CodeBadType, "pattern and length bounds apply to string, secret and file, not %s", f.Type)
	}
	if !numeric && (f.Min != nil || f.Max != nil) {
		bad(CodeBadType, "min and max apply to integer, number and decimal, not %s", f.Type)
	}
	if f.Format != "" && !textual && f.Type != TypeDatetime {
		bad(CodeBadType, "format applies to string, secret, file and datetime, not %s", f.Type)
	}

	// A mask that cannot fire is worse than no mask: it reads, in the schema,
	// as a promise that the value is kept out of the logs.
	if f.Mask != nil {
		switch {
		case f.Mask.Check() != "":
			bad(CodeBadMask, "%s", f.Mask.Check())
		case f.Type == TypeSecret:
			bad(CodeBadMask, "secret values never reach a redacted document, so they cannot be masked")
		case !f.Type.IsScalar():
			bad(CodeBadMask, "mask applies to scalar fields, not %s; mask the fields inside it instead", f.Type)
		}
	}

	if f.Pattern != "" {
		if re, err := regexp.Compile(f.Pattern); err != nil {
			bad(CodeBadPattern, "pattern does not compile: %v", err)
		} else {
			cf.pattern = re
		}
	}
	if f.Items != nil && f.Items.Pattern != "" {
		if re, err := regexp.Compile(f.Items.Pattern); err != nil {
			bad(CodeBadPattern, "items.pattern does not compile: %v", err)
		} else {
			cf.itemPattern = re
		}
	}
	if f.Min != nil && f.Max != nil && *f.Min > *f.Max {
		bad(CodeBadRange, "min %v is greater than max %v", *f.Min, *f.Max)
	}
	if f.MinLength != nil && f.MaxLength != nil && *f.MinLength > *f.MaxLength {
		bad(CodeBadRange, "min_length %d is greater than max_length %d", *f.MinLength, *f.MaxLength)
	}
	if f.MinItems != nil && f.MaxItems != nil && *f.MinItems > *f.MaxItems {
		bad(CodeBadRange, "min_items %d is greater than max_items %d", *f.MinItems, *f.MaxItems)
	}

	if f.Default != nil {
		if reason, ok := c.checkDefault(f); !ok {
			bad(CodeBadDefault, "default %v is invalid: %s", f.Default, reason)
		}
	}

	// Register before recursing so a nested condition can refer to siblings.
	sc.byName[f.Name] = cf
	sc.fields = append(sc.fields, cf)
	if f.Type == TypeSecret {
		markSecret(sc)
	}

	if f.Type == TypeObjectList {
		if sc.depth+1 > MaxDepth {
			bad(CodeDepthExceeded, "object_list nesting exceeds MaxDepth (%d)", MaxDepth)
			return cf, errs
		}
		child := newScope(sc)
		cf.child = child
		for _, sub := range f.Fields {
			_, se := c.buildField(sub, child, group, path)
			errs = append(errs, se...)
		}
		cf.requiresItemID = child.hasSecretDeep

		for _, u := range f.Unique {
			t, ok := child.byName[u]
			if !ok {
				bad(CodeBadUnique, "unique references unknown field %q", u)
				continue
			}
			if !t.f.Type.IsScalar() && t.f.Type != TypeEnum {
				bad(CodeBadUnique, "unique field %q must be scalar", u)
			}
		}
		for _, m := range tmplRe.FindAllStringSubmatch(f.ItemLabel, -1) {
			if _, ok := child.byName[m[1]]; !ok {
				bad(CodeBadItemLabel, "item_label references unknown field %q", m[1])
			}
		}
	}
	return cf, errs
}

// markSecret propagates "this subtree holds a secret" outwards: an outer list
// needs a stable $id as soon as anything below it has a secret, because the
// secret's key is built from the whole $id path.
func markSecret(sc *cscope) {
	for s := sc; s != nil; s = s.parent {
		s.hasSecretDeep = true
	}
}

func (c *Compiled) checkDefault(f *Field) (string, bool) {
	switch {
	case f.Type == TypeEnum:
		if f.Multiple {
			arr, ok := f.Default.([]any)
			if !ok {
				return "must be an array for a multiple enum", false
			}
			for _, v := range arr {
				if !c.inOptions(f, v) {
					return "not among options", false
				}
			}
			return "", true
		}
		if !c.inOptions(f, f.Default) {
			return "not among options", false
		}
	case f.Type == TypeObjectList || f.Type == TypeList:
		if _, ok := f.Default.([]any); !ok {
			return "must be an array", false
		}
	case f.Type == TypeMap:
		if _, ok := f.Default.(map[string]any); !ok {
			return "must be an object", false
		}
	case f.Type == TypeJSON:
		return "", true
	default:
		if reason, ok := checkScalarType(f.Default, f.Type); !ok {
			return reason, false
		}
	}
	return "", true
}

func (c *Compiled) inOptions(f *Field, v any) bool {
	for _, o := range f.Options {
		if equalValues(o.Value, v) {
			return true
		}
	}
	return false
}

// checkRefs resolves every condition reference. References may point sideways
// (same scope) or outwards; there is no syntax pointing inwards, so "outer
// refers to inner" surfaces naturally as an unknown reference.
func (c *Compiled) checkRefs() SchemaErrors {
	var errs SchemaErrors

	check := func(cond *Condition, sc *cscope, path, group, slot string) {
		if cond == nil {
			return
		}
		if !cond.hasOp() {
			errs = append(errs, SchemaError{Path: path, Group: group, Code: CodeBadCondition,
				Reason: fmt.Sprintf("%s is empty", slot)})
			return
		}
		for _, r := range cond.refs() {
			if resolveRef(sc, r) == nil {
				errs = append(errs, SchemaError{Path: path, Group: group, Code: CodeUnknownRef,
					Reason: fmt.Sprintf("%s references unknown field %q", slot, r.raw)})
			}
		}
		for _, pair := range cond.ordRefs() {
			a, b := resolveRef(sc, pair[0]), resolveRef(sc, pair[1])
			if a == nil || b == nil {
				continue
			}
			if !isOrderable(a.f.Type) || !isOrderable(b.f.Type) {
				errs = append(errs, SchemaError{Path: path, Group: group, Code: CodeNotComparable,
					Reason: fmt.Sprintf("%s compares %q (%s) with %q (%s), which has no order",
						slot, pair[0].raw, a.f.Type, pair[1].raw, b.f.Type)})
			} else if a.f.Type != b.f.Type {
				errs = append(errs, SchemaError{Path: path, Group: group, Code: CodeNotComparable,
					Reason: fmt.Sprintf("%s compares %q (%s) with %q (%s) of a different type",
						slot, pair[0].raw, a.f.Type, pair[1].raw, b.f.Type)})
			}
		}
	}

	// A transient value is dropped from Validate's own output, so it is never
	// in a patch and never in the document a server stores. A rule that only
	// reports a problem can be left to the client (see markClientOnly), but a
	// condition that decides the shape of the document cannot: the two sides
	// would answer it differently, and the server's answer is the one that
	// gets persisted -- a visible_when reading a transient field deletes, on
	// every unrelated update, the values it decides the visibility of. There
	// is no evaluation order that fixes that, so it is refused at compile
	// time instead.
	structural := func(cond *Condition, sc *cscope, path, group, slot string) {
		if cond == nil {
			return
		}
		for _, r := range cond.refs() {
			if t := resolveRef(sc, r); t != nil && t.f.Transient {
				errs = append(errs, SchemaError{Path: path, Group: group, Code: CodeTransientRef,
					Reason: fmt.Sprintf(
						"%s reads %q, which is transient and never reaches the stored document; "+
							"only valid_when may read a transient field", slot, r.raw)})
			}
		}
	}

	for _, g := range c.groups {
		check(g.g.VisibleWhen, c.root, g.g.Key, g.g.Key, "group visible_when")
		structural(g.g.VisibleWhen, c.root, g.g.Key, g.g.Key, "group visible_when")
		for i, r := range g.g.ValidWhen {
			if r == nil {
				continue
			}
			check(r.When, c.root, g.g.Key, g.g.Key, fmt.Sprintf("group valid_when[%d]", i))
		}
	}
	c.walk(func(cf *cfield) {
		check(cf.f.VisibleWhen, cf.scope, cf.path, cf.group, "visible_when")
		check(cf.f.RequiredWhen, cf.scope, cf.path, cf.group, "required_when")
		check(cf.f.ReadOnlyWhen, cf.scope, cf.path, cf.group, "readonly_when")
		structural(cf.f.VisibleWhen, cf.scope, cf.path, cf.group, "visible_when")
		structural(cf.f.RequiredWhen, cf.scope, cf.path, cf.group, "required_when")
		structural(cf.f.ReadOnlyWhen, cf.scope, cf.path, cf.group, "readonly_when")
		for i, r := range cf.f.ValidWhen {
			if r == nil {
				continue
			}
			check(r.When, cf.scope, cf.path, cf.group, fmt.Sprintf("valid_when[%d]", i))
		}
	})
	return errs
}

// resolveRef walks out of the current scope as the reference asks.
func resolveRef(sc *cscope, r ref) *cfield {
	target := sc
	if r.root {
		for target.parent != nil {
			target = target.parent
		}
	} else {
		for i := 0; i < r.up; i++ {
			if target.parent == nil {
				return nil
			}
			target = target.parent
		}
	}
	return target.byName[r.name]
}

// checkCycles rejects visible_when cycles. Only visible_when needs this: the
// other slots are terminal consumers and cannot loop. Cross-scope references
// always point outwards, so only same-scope edges can form a cycle.
func (c *Compiled) checkCycles() SchemaErrors {
	var errs SchemaErrors
	var scopes []*cscope
	collect := func(sc *cscope) { scopes = append(scopes, sc) }
	collect(c.root)
	c.walk(func(cf *cfield) {
		if cf.child != nil {
			collect(cf.child)
		}
	})

	// A group's visibility gates its fields, so it is an extra dependency edge.
	groupDeps := map[string][]string{}
	for _, g := range c.groups {
		if g.g.VisibleWhen != nil {
			groupDeps[g.g.Key] = g.g.VisibleWhen.sameScopeRefs()
		}
	}

	for _, sc := range scopes {
		state := map[string]int{} // 0 unvisited, 1 in stack, 2 done
		var dfs func(name string, stack []string) bool
		dfs = func(name string, stack []string) bool {
			switch state[name] {
			case 1:
				at := 0
				for i, s := range stack {
					if s == name {
						at = i
						break
					}
				}
				errs = append(errs, SchemaError{Path: name, Code: CodeCycle,
					Reason: "visible_when forms a cycle: " + strings.Join(append(stack[at:], name), " -> ")})
				return true
			case 2:
				return false
			}
			state[name] = 1
			cf := sc.byName[name]
			if cf != nil {
				var deps []string
				if cf.f.VisibleWhen != nil {
					deps = append(deps, cf.f.VisibleWhen.sameScopeRefs()...)
				}
				if sc == c.root {
					deps = append(deps, groupDeps[cf.group]...)
				}
				for _, d := range deps {
					if _, ok := sc.byName[d]; !ok {
						continue
					}
					if dfs(d, append(stack, name)) {
						state[name] = 2
						return true
					}
				}
			}
			state[name] = 2
			return false
		}
		for _, cf := range sc.fields {
			if state[cf.f.Name] == 0 {
				dfs(cf.f.Name, nil)
			}
		}
	}
	return errs
}

// walk visits every field in the schema, depth first.
func (c *Compiled) walk(fn func(*cfield)) {
	var rec func(sc *cscope)
	rec = func(sc *cscope) {
		for _, cf := range sc.fields {
			fn(cf)
			if cf.child != nil {
				rec(cf.child)
			}
		}
	}
	rec(c.root)
}

// Schema returns the schema this was compiled from.
func (c *Compiled) Schema() Schema { return c.schema }

// RequiresItemID reports whether an object_list at the given schema path needs
// every item to carry a client-generated $id, which is the case as soon as the
// item subtree holds a secret.
func (c *Compiled) RequiresItemID(path string) bool {
	var found bool
	c.walk(func(cf *cfield) {
		if cf.path == path {
			found = cf.requiresItemID
		}
	})
	return found
}