iamdiff

// Evaluate applies AWS's own precedence rules and returns a flat,
// provider-neutral effective set.
//
// AWS composition, in order:
//  1. identity allows are unioned
//  2. the permissions boundary intersects -- it never adds access
//  3. guardrails intersect, one layer per organisation level, because
//     an action must be allowed at every level from the root down
//  4. any explicit deny anywhere wins outright
//
// Steps 2 to 4 are what distinguish this from a policy linter, and are
// the reason the answer cannot be derived from one document alone.
//
// Conditions stay opaque throughout. A conditional allow in a layer, a
// conditional deny, or a deny that removes only part of a grant's
// resources all become clauses of the grant's condition rather than a
// guess about whether access exists: the diff then reports a change to
// any of them as "condition changed", never as silence.
func (p *Provider) Evaluate(ctx context.Context, raw *provider.RawSet) (*model.EffectiveSet, error) {
	return p.evaluate(raw, nil)
}

func (p *Provider) evaluate(raw *provider.RawSet, obs observer) (*model.EffectiveSet, error) {
	out := model.NewEffectiveSet(raw.Principal)
	out.Catalogue = p.cat.Version()
	for _, g := range raw.Gaps {
		out.MarkGap(g)
	}

	set, err := p.compile(raw)
	if err != nil {
		return nil, err
	}
	for _, g := range set.gaps {
		out.MarkGap(g)
	}

	seen := map[string]bool{}
	for _, g := range set.identity {
		grants, gaps := set.resolve(g, obs)
		for _, gap := range gaps {
			if !seen[gap] {
				seen[gap] = true
				out.MarkGap(gap)
			}
		}
		for _, final := range grants {
			out.Add(final)
		}
	}
	return out, nil
}

// resolve pushes one identity grant through every layer and then the
// denies, returning what survives. A layer may narrow the grant to the
// resources it actually permits, so one grant in can be several out.
func (set *ruleset) resolve(g model.Grant, obs observer) (out []model.Grant, gaps []string) {
	lower := strings.ToLower(g.Action)
	type candidate struct {
		resource string
		parts    []model.ConditionPart
	}
	current := []candidate{{resource: g.Resource, parts: []model.ConditionPart{model.Part(model.RoleRequire, g.Condition, "")}}}
	// …
	denies := set.denies.for_(lower)
	for _, c := range current {
		parts := c.parts
		denied := false
		for _, r := range denies {
			rel := r.relate(c.resource)
			switch {
			case rel.full && r.cond.Empty():
				observe(obs, &layer{kind: r.origin.SourceKind, name: r.origin.SourceName}, "Deny", fmt.Sprintf("%s denies %s", describe(r), c.resource))
				denied = true
			case rel.full:
				observe(obs, &layer{kind: r.origin.SourceKind, name: r.origin.SourceName}, "Deny (conditional)", fmt.Sprintf("%s denies %s under a condition", describe(r), c.resource))
				parts = append(clone(parts), model.Part(model.RoleUnless, r.cond, ""))
			case len(rel.narrow) > 0 || rel.partial:
				observe(obs, &layer{kind: r.origin.SourceKind, name: r.origin.SourceName}, "Deny (partial)", fmt.Sprintf("%s denies part of %s", describe(r), c.resource))
				parts = append(clone(parts), model.Part(model.RoleUnless, r.cond, "except "+r.resourceSummary()))
			}
			if denied {
				break
			}
		}
		if denied {
			continue
		}
		out = append(out, model.Grant{
			Action:    g.Action,
			Resource:  c.resource,
			Effect:    model.Allow,
			Condition: model.ComposeCondition(parts...),
			Origin:    g.Origin,
		})
	}
	return out, gaps
}

// Package glob matches the wildcard language of IAM policy documents:
// '*' for any run of characters and '?' for exactly one. It is not a
// shell glob; '[', ']' and '\' are ordinary characters.
//
// The one subtlety is where '*' may roam. The IAM documentation states
// that a '*' which ends a colon-separated ARN segment, or ends the
// pattern, expands beyond the colon boundaries, while a '*' followed by
// anything else stays inside its segment. Action names carry a single
// ':' before the name, so for them the rule changes nothing.
package glob
// …
// Match reports whether s is in the language of pattern. With fold set,
// matching ignores ASCII case, as IAM does for action names.
func Match(pattern, s string, fold bool) bool {
	if fold {
		pattern, s = strings.ToLower(pattern), strings.ToLower(s)
	}
	return match(pattern, s)
}

// crosses reports whether the star at p[i] may match ':'.
func crosses(p string, i int) bool {
	return i+1 == len(p) || p[i+1] == ':'
}

func match(p, s string) bool {
	n, m := len(p), len(s)
	prev := make([]bool, m+1) // prev[j]: p[i+1:] matches s[j:]
	cur := make([]bool, m+1)
	prev[m] = true
	for i := n - 1; i >= 0; i-- {
		switch c := p[i]; c {
		case '*':
			free := crosses(p, i)
			cur[m] = prev[m]
			for j := m - 1; j >= 0; j-- {
				cur[j] = prev[j] || ((free || s[j] != ':') && cur[j+1])
			}
		case '?':
			cur[m] = false
			for j := m - 1; j >= 0; j-- {
				cur[j] = prev[j+1]
			}
		default:
			cur[m] = false
			for j := m - 1; j >= 0; j-- {
				cur[j] = s[j] == c && prev[j+1]
			}
		}
		prev, cur = cur, prev
	}
	return prev[0]
}

// ComposeCondition folds several clauses into one opaque condition.
//
// Conditions stay opaque (ADR-0002): composition never reasons about
// what a clause means, only about which clauses are present. The result
// is canonical, so the same clauses in any order produce the same
// fingerprint, and a change to any clause changes it. A lone "require"
// clause with no note is returned unchanged, so a grant carrying only
// its own statement's condition keeps that condition's fingerprint.
func ComposeCondition(parts ...ConditionPart) Condition {
	var kept []ConditionPart
	for _, p := range parts {
		if p.Fingerprint == "" && p.Note == "" {
			continue
		}
		kept = append(kept, p)
	}
	if len(kept) == 0 {
		return Condition{}
	}
	if len(kept) == 1 && kept[0].Role == RoleRequire && kept[0].Note == "" {
		return Condition{Fingerprint: kept[0].Fingerprint, Summary: kept[0].Summary, Raw: nil}
	}
	sort.Slice(kept, func(i, j int) bool {
		if kept[i].Role != kept[j].Role {
			return kept[i].Role < kept[j].Role
		}
		if kept[i].Fingerprint != kept[j].Fingerprint {
			return kept[i].Fingerprint < kept[j].Fingerprint
		}
		return kept[i].Note < kept[j].Note
	})
	canon, _ := json.Marshal(kept)
	var summary []string
	for _, p := range kept {
		switch {
		case p.Note != "" && p.Summary != "":
			summary = append(summary, p.Role+" "+p.Summary+" ("+p.Note+")")
		case p.Note != "":
			summary = append(summary, p.Role+" "+p.Note)
		default:
			summary = append(summary, p.Role+" "+p.Summary)
		}
	}
	return Condition{
		Raw:         canon,
		Fingerprint: hash(canon),
		Summary:     strings.Join(summary, "; "),
		Parts:       kept,
	}
}

// EffectiveSet is the fully resolved permission set for one principal.
//
// Partial must be set whenever any policy source could not be reached.
// Reporting an incomplete result as though it were complete is the one
// failure mode that would make the whole tool untrustworthy.
type EffectiveSet struct {
	Principal Principal          `json:"principal"`
	Grants    map[GrantKey]Grant `json:"-"`
	Partial   bool               `json:"partial"`
	Gaps      []string           `json:"gaps,omitempty"`
	Catalogue string             `json:"catalogue_version,omitempty"`
}

func NewEffectiveSet(p Principal) *EffectiveSet {
	return &EffectiveSet{Principal: p, Grants: map[GrantKey]Grant{}}
}

// Add inserts a grant, honouring universal deny precedence: an explicit
// deny on a key is never overwritten by a later allow. Every cloud
// examined shares this rule, so it belongs in the core rather than in
// each provider.
//
// Two allows on the same key merge to the broader one: an unconditional
// allow beats a conditional allow whatever order they arrive in, and two
// different conditions compose as "any", since the grant holds under
// either. Letting the later statement win would let a conditional grant
// hide an unconditional one behind a condition-changed verdict.
func (s *EffectiveSet) Add(g Grant) {
	k := g.Key()
	existing, ok := s.Grants[k]
	if !ok || existing.Effect == Deny {
		if !ok {
			s.Grants[k] = g
		}
		return
	}
	if g.Effect == Deny {
		s.Grants[k] = g
		return
	}
	switch {
	case existing.Condition.Empty():
		return
	case g.Condition.Empty():
		s.Grants[k] = g
	case existing.Condition.Fingerprint == g.Condition.Fingerprint:
		return
	default:
		merged := existing
		merged.Condition = Any(existing.Condition, g.Condition)
		s.Grants[k] = merged
	}
}

// MarkGap records an unreachable source and flags the set as partial.
func (s *EffectiveSet) MarkGap(reason string) {
	s.Partial = true
	s.Gaps = append(s.Gaps, reason)
}

type Verdict string

const (
	VerdictUnchanged     Verdict = "unchanged"
	VerdictNarrowed      Verdict = "narrowed"
	VerdictWidened       Verdict = "widened"
	VerdictIndeterminate Verdict = "indeterminate"
	VerdictIncomplete    Verdict = "incomplete"
)

// Exit codes are part of the tool's public contract. Changing them is a
// breaking change for every pipeline that consumes the tool.
const (
	ExitUnchanged     = 0
	ExitNarrowed      = 1
	ExitWidened       = 2
	ExitIndeterminate = 3
	ExitIncomplete    = 4
)
// …
// Verdict collapses the result into a single judgement.
//
// Precedence is deliberate: incompleteness outranks everything, because
// a partial evaluation cannot honestly claim that access did not widen.
func (r Result) Verdict() Verdict {
	switch {
	case r.Partial:
		return VerdictIncomplete
	case len(r.Added) > 0:
		return VerdictWidened
	case len(r.Changed) > 0:
		return VerdictIndeterminate
	case len(r.Removed) > 0:
		return VerdictNarrowed
	default:
		return VerdictUnchanged
	}
}

// Package severity ranks a permission change.
//
// Most of the signal comes free from the catalogue's own access levels.
// The curated high-risk list is the small opinionated part that gives
// the tool a point of view: roughly fifty actions per cloud where the
// access level understates the blast radius.
package severity
// …
// HighRisk is hand-curated. Each entry is an action whose catalogue
// access level does not convey how dangerous it is.
var HighRisk = []string{
	"iam:*",
	"sts:AssumeRole",
	"kms:ScheduleKeyDeletion",
	"kms:DisableKey",
	"organizations:LeaveOrganization",
	"ec2:TerminateInstances",
	"s3:PutBucketPolicy",
}

// Classify ranks an action using the curated list first, then the
// catalogue's access level.
func Classify(c catalogue.Catalogue, action string, extra []string) Rank {
	for _, p := range append(append([]string{}, HighRisk...), extra...) {
		if matches(p, action) {
			return High
		}
	}
	if c == nil {
		return Low
	}
	switch c.AccessLevel(action) {
	case catalogue.LevelPermissionsMgmt:
		return High
	case catalogue.LevelWrite:
		return Medium
	default:
		return Low
	}
}

// Document is an opaque policy payload. Only the owning provider knows
// how to parse Body; the envelope exists so collection and evaluation
// can be tested independently of each other.
//
// Target names the point a guardrail is attached to (an organisation
// root, unit or account). Guardrails attached to different targets
// intersect, because every level must permit an action; guardrails that
// share a target union. Inherited is provenance only: the path of
// targets between the organisation root and the principal.
type Document struct {
	Kind      model.SourceKind `json:"kind"`
	Name      string           `json:"name"`
	Body      json.RawMessage  `json:"body"`
	Target    string           `json:"target,omitempty"`
	Inherited []string         `json:"inherited,omitempty"`
}

// RawSet is everything collected for one principal, before evaluation.
type RawSet struct {
	Principal model.Principal `json:"principal"`
	Documents []Document      `json:"documents"`
	Gaps      []string        `json:"gaps,omitempty"`
}

// Provider is the contract every cloud plug-in implements.
type Provider interface {
	Name() string
	Collect(ctx context.Context, sel Selector) (*RawSet, error)
	Evaluate(ctx context.Context, raw *RawSet) (*model.EffectiveSet, error)
}
// …
// OfflineLoader is implemented by providers that can build a RawSet from
// local documents with no credentials. This powers `iamdiff policy`,
// which is the fastest path to a useful first release.
type OfflineLoader interface {
	FromDocuments(p model.Principal, docs []Document) (*RawSet, error)
}