package di

// Registration: what a binding is, the methods that make one, and the typed
// handle that refines it. Nothing here builds anything; a binding's build
// func is called by the resolution in resolve.go.

import (
        "context"
        "fmt"
        "reflect"
        "runtime"
        "slices"
        "sync/atomic"
)

// binding is one registration: its key, lifetime, hooks and build func.
type binding struct {
        key      key
        site     string
        module   string // the Module this was registered from, or ""
        group    bool
        scoped   bool
        eager    bool
        override bool  // declared to replace an earlier registration of the key
        isValue  bool  // registered with Value: lifetimes do not apply
        wants    []key // the parameter types of a Wire constructor; nil for a Provide closure
        build    func(*Scope) any

        // inner is the registration a Wrap composes over, bound when Wrap is
        // called, and innerAt the scope that registered it; both nil for any
        // other binding. wrappedBy is set on a binding a Wrap has bound to: an
        // Override that replaced it would leave the wrapper composing over a
        // registration that no longer serves the key.
        inner     *binding
        innerAt   *state
        wrappedBy atomic.Pointer[binding]
        onStart   func(context.Context, any) error
        onDrain   func(context.Context, any) error
        onStop    func(context.Context, any) error
        worker    func(context.Context, any) error

        // used is set once this binding has served a value. From then on the
        // registration cannot be overridden, since that would leave two live
        // instances of one service. A failed resolution built nothing and leaves
        // the key re-registerable; that is how a key whose constructor failed is
        // recovered.
        used atomic.Bool

        // resolving counts the resolutions of this binding that have not served
        // a value yet, the window used cannot cover: a constructor that registers
        // over its own key and resolves the replacement would otherwise hand the
        // nested call the new value and the outer call the old one. It is read
        // only until the first value is served; after that used says the same.
        resolving atomic.Int32

        single *instance // the singleton; scoped bindings keep one instance per state
}

// where names the registration for a message: its site, and the module it was
// registered from when there is one, as in "storage (wire.go:12)".
func (b *binding) where() string {
        if b.module == "" {
                return b.site
        }
        return b.module + " (" + b.site + ")"
}

// validate rejects lifetime and hook combinations that cannot be honoured.
// It runs at freeze, so the order the builder methods were called in does
// not matter.
func (b *binding) validate() {
        bad := func(what, why string) {
                panic(fmt.Sprintf("di: %s (provided at %s): %s %s", b.key, b.where(), what, why))
        }
        switch {
        case b.eager && b.scoped:
                // Rejected even if a later registration overrides it. Whether an
                // override inherits eagerness is decided in deriveEager.
                bad("Eager", "does not apply to a Scoped binding: it is not built once")
        case b.isValue && b.scoped:
                bad("Scoped", "is meaningless for a Value binding: the instance already exists")
        case b.group && b.override:
                bad("Override", "does not apply to a group member: members accumulate rather than replace one another")
        case b.inner != nil && b.group:
                bad("Group", "does not apply to a wrapper: it serves the key it wraps")
        case b.inner != nil && b.override:
                bad("Override", "does not apply to a wrapper: it composes over the registration it wraps rather than replacing it")
        }
}

// Binding is the typed handle returned by Provide, Value, Wire and Wrap. Its
// methods refine the registration; they must be called before the first
// resolution from this scope.
type Binding[T any] struct {
        s *Scope
        b *binding
}

func (s *Scope) register(k key, build func(*Scope) any) *binding {
        b := &binding{key: k, site: callsite(), module: s.module, build: build}
        b.single = &instance{b: b}
        s.mu.Lock()
        s.pending = append(s.pending, b)
        s.mu.Unlock()
        return b
}

// Provide registers a lazily built singleton. T is inferred from the
// constructor's return type; dependencies are pulled with s.Get[...]().
func (s *Scope) Provide[T any](ctor func(*Scope) T) Binding[T] {
        return Binding[T]{s, s.register(key{t: reflect.TypeFor[T]()}, func(s *Scope) any { return ctor(s) })}
}

// Value registers an already-built instance.
func (s *Scope) Value[T any](v T) Binding[T] {
        b := s.register(key{t: reflect.TypeFor[T]()}, func(*Scope) any { return v })
        b.isValue = true
        return Binding[T]{s, b}
}

func callsite() string {
        _, file, line, _ := runtime.Caller(3)
        return fmt.Sprintf("%s:%d", file, line)
}

// Wire registers a lazily built singleton from a constructor of any arity,
// whose parameters are its dependencies:
//
//        s.Wire[*Server](NewServer) // func NewServer(cfg Config, repo *Repo) *Server
//
// ctor must be a non-variadic function returning T, or T and an error, and is
// read with reflection once, here. Each parameter type is resolved from the
// same scope view a Provide closure would see, so lifetimes, cycles, hooks and
// error paths are unchanged; what Wire adds is that the dependencies are known
// at registration, before anything is built. A non-nil error from ctor aborts
// the build exactly as s.Must does.
//
// T cannot be inferred from an untyped argument, so it is spelled out, and a
// constructor whose result is not assignable to T is rejected here, with the
// other configuration errors. A concrete constructor may therefore serve an
// interface key directly: s.Wire[Repository](NewPGRepo). The build calls ctor
// through reflect, which costs about 150ns and two allocations per build over
// a Provide closure; a warm Get is the same code for both.
func (s *Scope) Wire[T any](ctor any) Binding[T] {
        want := reflect.TypeFor[T]()
        fv, ft, fails := function("Wire["+typeName(want)+"]", "constructor", ctor, want)
        wants := params(ft, 0)
        b := s.register(key{t: want}, func(s *Scope) any {
                args := make([]reflect.Value, len(wants))
                s.arguments(wants, args)
                return call(fv, args, fails, want)
        })
        b.wants = wants
        return Binding[T]{s, b}
}

// Wrap registers a wrapper over the registration that serves T when Wrap is
// called: the latest one in this scope, or the one an ancestor provides. fn
// takes the value being wrapped first and its other dependencies after it,
// read with reflection as Wire reads a constructor, and returns T, or T and
// an error:
//
//        s.Wrap[Store](func(next Store, c *Cache) Store { return &caching{next, c} })
//
// What is wrapped keeps its registration, hooks and lifetime: it is built
// first, as the wrapper's dependency, and so stopped after it. The wrapper
// serves T from this scope down. In a child scope it wraps the parent's value
// for that child and its descendants and leaves the parent and its other
// children as they were, which is what uber/fx calls Decorate. Wrappers
// chain in registration order, and a wrapper takes the lifetime of what it
// wraps; Scoped() on the wrapper makes it one per resolving scope over a
// shared inner value. An Override registered afterwards replaces the wrapper
// and everything it wrapped. Nothing to wrap is rejected here, and a group
// cannot be wrapped: its members are read with All. A key this scope has
// already resolved is rejected at the next resolution, as an Override is,
// since callers already hold the unwrapped value.
func (s *Scope) Wrap[T any](fn any) Binding[T] {
        want := reflect.TypeFor[T]()
        name := "Wrap[" + typeName(want) + "]"
        fv, ft, fails := function(name, "wrapper", fn, want)
        if ft.NumIn() == 0 || !want.AssignableTo(ft.In(0)) {
                panic(fmt.Sprintf("di: %s: wrapper %s must take the %s it wraps as its first parameter", name, ft, typeName(want)))
        }
        k := key{t: want}
        // This scope is read as it is, pending batch included, because committing
        // the batch here would end it for every registration made so far.
        // Ancestors are looked up as a resolution would look them up.
        inner, at := s.current(k)
        if inner == nil && s.parent != nil {
                inner, at = (&Scope{state: s.parent}).lookup(k)
        }
        if inner == nil {
                panic(fmt.Sprintf("di: %s: nothing provides %s in scope %s or above; a group is read with All and cannot be wrapped", name, k, s.name))
        }
        wants := params(ft, 1)
        b := s.register(k, func(s *Scope) any {
                args := make([]reflect.Value, len(wants)+1)
                // The wrapped value is resolved as a dependency, which records the
                // edge, keeps build order and catches a wrapper that reaches back
                // into itself; served is marked as get would mark it.
                args[0] = argument(s.resolve(inner, at), ft.In(0))
                s.markServed(at, k)
                s.arguments(wants, args[1:])
                return call(fv, args, fails, want)
        })
        b.inner, b.innerAt, b.wants, b.scoped = inner, at, wants, inner.scoped
        inner.wrappedBy.Store(b)
        return Binding[T]{s, b}
}

var errorType = reflect.TypeFor[error]()

// function checks that fn is a non-variadic function returning want, or want
// and an error, and returns it with its type and whether it declares the
// error. name and role label the message: "di: Wire[*app.Server]: constructor
// must be a function".
func function(name, role string, fn any, want reflect.Type) (fv reflect.Value, ft reflect.Type, fails bool) {
        fv = reflect.ValueOf(fn)
        if !fv.IsValid() || fv.Kind() != reflect.Func {
                panic(fmt.Sprintf("di: %s: %s must be a function, got %T", name, role, fn))
        }
        ft = fv.Type()
        switch {
        case ft.IsVariadic():
                panic(fmt.Sprintf("di: %s: %s %s is variadic", name, role, ft))
        case ft.NumOut() == 0 || ft.NumOut() > 2:
                panic(fmt.Sprintf("di: %s: %s %s must return T or (T, error)", name, role, ft))
        case !ft.Out(0).AssignableTo(want):
                panic(fmt.Sprintf("di: %s: %s %s returns %s", name, role, ft, typeName(ft.Out(0))))
        case ft.NumOut() == 2 && ft.Out(1) != errorType:
                panic(fmt.Sprintf("di: %s: %s %s must return T or (T, error)", name, role, ft))
        }
        return fv, ft, ft.NumOut() == 2
}

// params lists the parameter types of ft from index from on, as keys.
func params(ft reflect.Type, from int) []key {
        wants := make([]key, ft.NumIn()-from)
        for i := range wants {
                wants[i] = key{t: ft.In(i + from)}
        }
        return wants
}

// arguments resolves each of wants from s into the corresponding slot of
// args.
func (s *Scope) arguments(wants []key, args []reflect.Value) {
        for i, k := range wants {
                args[i] = argument(s.get(k), k.t)
        }
}

// current is the registration serving k in this scope as of now, pending or
// committed, read without committing anything.
func (st *state) current(k key) (*binding, *state) {
        st.mu.Lock()
        defer st.mu.Unlock()
        for _, b := range slices.Backward(st.pending) {
                if b.key == k && !b.group {
                        return b, st
                }
        }
        if b, ok := st.index[k]; ok {
                return b, st
        }
        return nil, nil
}

// argument makes a stored value into an argument of type t. A nil interface
// is a legitimate service, and reflect.ValueOf(nil) is not a value of any
// type; see as.
func argument(v any, t reflect.Type) reflect.Value {
        if v == nil {
                return reflect.Zero(t)
        }
        return reflect.ValueOf(v)
}

// call runs a constructor through reflect and turns its error, if it
// declared one and returned it, into the abort that s.Must would raise. The
// value is stored as the registered type, not the constructor's result type:
// registration accepted any result assignable to the key, and a chan int
// stored for a <-chan int key would pass every check until Get asserted it.
// An interface key needs no conversion, since the assertion to an interface
// is what accepts the concrete value.
func call(fv reflect.Value, args []reflect.Value, fails bool, want reflect.Type) any {
        out := fv.Call(args)
        if fails && !out[1].IsNil() {
                panic(abort{out[1].Interface().(error)})
        }
        v := out[0]
        if v.Type() != want && want.Kind() != reflect.Interface {
                v = v.Convert(want)
        }
        return v.Interface()
}

// edit applies a builder method to the binding, rejecting one made after the
// scope committed the registration.
func (b Binding[T]) edit(f func(*binding)) Binding[T] {
        b.s.mu.Lock()
        defer b.s.mu.Unlock()
        if b.s.frozen && !slices.Contains(b.s.pending, b.b) {
                panic(fmt.Sprintf("di: %s (provided at %s) modified after the scope was first resolved", b.b.key, b.b.where()))
        }
        f(b.b)
        return b
}

// Group makes the binding a member of the multi-binding group for T instead
// of the binding for T: it neither shadows nor is shadowed by another
// registration of T, and the members are read back together with s.All[T]().
// A member keeps its own lifetime and hooks.
func (b Binding[T]) Group() Binding[T] {
        return b.edit(func(b *binding) { b.group = true })
}

// Override declares that this registration replaces an earlier one of the same
// key in the same scope. Without it a second registration of a key is rejected
// at the next resolution, naming both sites, because a duplicate that wins
// silently is how one module reroutes another module's wiring without anyone
// noticing. With it the later registration serves the key, and inherits its
// eagerness, which is the test seam:
//
//        s := di.Test(t, app.Production)
//        s.Value(&DB{DSN: "sqlite://memory"}).Override()
//
// There must be something to override in this scope, or that is rejected too:
// a fake for a service that has since been renamed would otherwise be a
// registration nobody resolves, and the test would pass against production
// wiring. A child scope shadows its parent without Override, since that is a
// different registry rather than a replacement. A key that has already served
// a value cannot be overridden at all.
func (b Binding[T]) Override() Binding[T] {
        return b.edit(func(b *binding) { b.override = true })
}

// Scoped makes the binding one-per-scope: each scope that resolves it gets
// its own instance, built in that scope (so it can see that scope's
// values) and stopped with it. Declare request-scoped services once in the
// root and resolve them through the request scope.
func (b Binding[T]) Scoped() Binding[T] {
        return b.edit(func(b *binding) { b.scoped = true })
}

// Eager builds the service during Start rather than on first use.
//
// Eagerness belongs to the key, not the registration: it means the service
// exists by the time Start returns. Overriding an eager binding therefore
// keeps the key eager and builds the replacement; a replacement with a
// per-scope lifetime, which cannot be built once at Start, is rejected.
func (b Binding[T]) Eager() Binding[T] { return b.edit(func(b *binding) { b.eager = true }) }

// OnStart runs once the service is built, and only a hook that returns
// normally starts it: one that panics fails the start step, like a panicking
// constructor, and the service is never served. The hooks are typed: no
// interface sniffing, no reflection.
func (b Binding[T]) OnStart(f func(context.Context, T) error) Binding[T] {
        return b.edit(func(b *binding) { b.onStart = func(ctx context.Context, v any) error { return f(ctx, as[T](v)) } })
}

// OnDrain runs before anything is stopped: Stop drains the whole tree, from
// the innermost scope outwards and in reverse build order, while every scope
// still resolves normally. It is where a service stops accepting new work and
// waits for the work it already has, such as an HTTP server that must finish
// in-flight requests whose handlers still need their request scope. Anything
// those handlers build, including a request scope of their own, is drained
// before the phase ends. Use OnStop for the release that follows.
func (b Binding[T]) OnDrain(f func(context.Context, T) error) Binding[T] {
        return b.edit(func(b *binding) { b.onDrain = func(ctx context.Context, v any) error { return f(ctx, as[T](v)) } })
}

// OnStop releases the service, in reverse build order, once its drain step
// and its child scopes are done. It runs when OnStart succeeded, or when
// there is no OnStart to pair with, in which case it is a plain destructor;
// a service whose start step failed is not stopped.
func (b Binding[T]) OnStop(f func(context.Context, T) error) Binding[T] {
        return b.edit(func(b *binding) { b.onStop = func(ctx context.Context, v any) error { return f(ctx, as[T](v)) } })
}

// Worker registers a long-running function for T, such as a consumer loop. It is
// started in its own goroutine once the service starts and its context is
// cancelled when the service stops; Stop waits for it to return, bounded by
// its own context. A hook that outlasts that deadline is reported by Stop,
// and OnStop then waits for it rather than releasing the value underneath a
// worker still reading it.
//
// Returning a non-nil error calls Shutdown with it, stopping the application,
// even if the scope was already stopping: a worker may fail, flush while the
// scope winds down, and only then report. The exception is context.Canceled
// from a hook that was already cancelled, which is a worker reporting the
// cancellation and nothing else. A hook that wants to stay quiet during
// shutdown should return nil.
func (b Binding[T]) Worker(f func(context.Context, T) error) Binding[T] {
        return b.edit(func(b *binding) { b.worker = func(ctx context.Context, v any) error { return f(ctx, as[T](v)) } })
}

// Package di is a dependency-injection container for Go 1.27+ built on
// generic methods.
//
// Services are registered on a [Scope] and resolved from it by type:
//
//        app := di.New()
//        app.Value(Config{DSN: "postgres://localhost/app"})
//        app.Provide(func(s *di.Scope) *DB { return s.Must(sql.Open("postgres", s.Get[Config]().DSN)) }).
//                OnStop(func(ctx context.Context, db *DB) error { return db.Close() })
//        app.Provide(func(s *di.Scope) *Repo { return &Repo{db: s.Get[*DB]()} })
//
//        repo, err := app.Resolve[*Repo]()
//
// Keys are Go types, so there is no naming scheme and no collisions between
// packages. Constructors return T rather than (T, error): inside a
// constructor, [Scope.Get] and [Scope.Must] abort on failure and the error
// surfaces from the enclosing [Scope.Resolve], [Scope.Start] or [Scope.Run]
// with the dependency path and the registration site.
//
// # Lifetimes
//
// A binding is a singleton by default, cached in the scope that registered
// it. [Binding.Scoped] makes it one instance per resolving scope, built
// there so it can see that scope's values, which is how request-scoped
// services are declared once in the root. [Binding.Group] and [Scope.All]
// handle groups, and [Scope.Maybe] resolves optional dependencies. An
// interface is served by a constructor that returns the implementation:
// s.Provide(func(s *Scope) Reader { return s.Get[*Repo]() }).
//
// # Scopes
//
// [Scope.Child] creates a scope that resolves through its parent, reuses
// the parent's singletons and owns the lifecycle of what it builds. A child
// may shadow a key its parent provides; within one scope, a second
// registration of a key must be marked [Binding.Override], or the next
// resolution rejects it naming both sites. That marker is the test seam: wire
// the production graph into a fresh scope, then override what you want faked
// before anything is resolved ([Test] does the bookkeeping). For HTTP,
// [github.com/floatdrop/di/dihttp.Middleware] gives each request a child
// scope holding the *http.Request, reachable through [FromContext].
//
// # Modules
//
// A [Module] is a function that registers into a scope, and [Scope.Use]
// applies modules in order. Registrations are attributed to the module that
// made them, so a collision between two modules is reported as one: "*app.DB
// is provided at storage (wire.go:12) and again at caching (cache.go:8)".
//
// # Lifecycle
//
// [Binding.OnStart], [Binding.OnDrain] and [Binding.OnStop] are typed hooks.
// [Scope.Start] builds [Binding.Eager] bindings and runs start hooks in build
// order, rolling back on failure; services built later start as part of being
// built. [Scope.Stop] first drains, which lets work already in flight finish
// while the scope still resolves, then stops child scopes, then services in
// reverse build order, and afterwards the scope refuses to resolve anything.
// [Binding.Worker] runs a long-lived function that is cancelled on stop.
// [Scope.Run] ties it together
// for a main function: start, wait for a signal or [Scope.Shutdown], stop
// with a deadline. [Scope.Observe] reports every step for logging and
// metrics.
//
// # Inspecting the graph
//
// A constructor's dependencies are recorded as it resolves them, so the
// graph is known for whatever has been built. [Scope.Explain] renders one
// service's dependency tree, with the registration site, lifetime and scope
// of each node, and what needed it. [Scope.Graph] renders everything built
// in a scope and its descendants as Graphviz DOT.
//
// # Concurrency
//
// A [Scope] is safe to use from many goroutines, including from goroutines a
// constructor starts for itself: the resolution path is immutable, so
// branches that run in parallel share nothing. A constructor may also keep
// the Scope it was handed and resolve through it later, once its own service
// is built; the finished part of that path is no longer a dependency, so such
// a resolution is not a cycle. A service is built once however many
// resolutions race for it, and a resolution of a running scope returns only a
// service whose start step has finished. A cycle is reported as [ErrCycle]
// even when the two halves are being built concurrently.
//
// Three re-entrancy limits apply. A goroutine started by a constructor must
// use [Scope.Resolve] rather than [Scope.Get], because Get reports failure by
// panicking and that panic cannot unwind to the enclosing call from another
// goroutine. An [Binding.OnStart] hook must not resolve a service that
// depends on the one being started: the hook already holds the value, and
// waiting for itself cannot make progress. And no hook may call [Scope.Stop]
// on its own scope or an ancestor, because Stop waits for the very step the
// hook is running; call [Scope.Shutdown], which never blocks.
package di

import (
        "context"
        "errors"
        "reflect"
        "runtime"
        "slices"
        "strings"
        "time"
)

// key identifies a service: its Go type. Keys compare by reflect.Type
// identity, so same-named types in different packages never collide (unlike
// fmt.Sprintf("%T")-derived names). There is no name alongside the type: a
// second binding of one type is declared as a distinct type instead, which
// makes a mistaken reference a compile error rather than a missing key.
type key struct{ t reflect.Type }

func (k key) String() string { return typeName(k.t) }

// pkgPath is the import path of the named type k stands for, walking through
// pointers as typeName does, since a pointer type is unnamed and carries no
// path of its own. It is empty for a type that has no path to report, which
// is exactly the set typeName writes with reflect's own short spelling.
func (k key) pkgPath() string {
        t := k.t
        for t.Kind() == reflect.Pointer {
                t = t.Elem()
        }
        return t.PkgPath()
}

func typeName(t reflect.Type) string {
        if t.Kind() == reflect.Pointer {
                return "*" + typeName(t.Elem())
        }
        if t.PkgPath() != "" {
                return t.PkgPath() + "." + t.Name()
        }
        return t.String()
}

var (
        ErrNotProvided = errors.New("not provided")
        ErrCycle       = errors.New("dependency cycle")
        ErrStopped     = errors.New("scope stopped")
)

// EventKind classifies an Event.
type EventKind string

const (
        EventBuild    EventKind = "build"    // a constructor ran
        EventStart    EventKind = "start"    // an OnStart hook ran
        EventDrain    EventKind = "drain"    // an OnDrain hook ran
        EventStop     EventKind = "stop"     // a Worker hook was cancelled and/or an OnStop hook ran
        EventShutdown EventKind = "shutdown" // Shutdown was called
)

// Event describes one lifecycle step. Observers receive it after the step
// completes, with its duration and error if any.
type Event struct {
        Kind    EventKind
        Service string // the service, e.g. "*github.com/acme/app.DB"; empty for shutdown
        // Package is the import path of the type Service names, e.g.
        // "github.com/acme/app", so an observer can shorten or group by it
        // without parsing Service. It is empty for a shutdown, and for a key
        // whose type is unnamed -- a []byte, a map[string]int -- since reflect
        // already writes those with a short package name.
        Package  string
        Scope    string // name of the scope that owns the instance
        Site     string // file:line of the registration; empty for shutdown
        Module   string // the Module the service was registered from; empty when none
        Duration time.Duration
        Err      error
}

// Scope is a container. A Scope value handed to a constructor is a view over
// the same state that carries the current resolution path.
type Scope struct {
        *state
        r      *resolver
        module string // the Module registering through this handle, or ""
}

// New creates a root scope: a container with no parent.
func New() *Scope { return &Scope{state: newState("root", nil)} }

func newState(name string, parent *state) *state {
        st := &state{
                name:       name,
                parent:     parent,
                index:      map[key]*binding{},
                groups:     map[key][]*binding{},
                scoped:     map[*binding]*instance{},
                shutdownCh: make(chan struct{}),
        }
        // One graph per container, shared by every scope under the root.
        if parent != nil {
                st.graph = parent.graph
        } else {
                st.graph = &graph{blockedFor: map[*resolver]*instance{}}
        }
        return st
}

// Child creates a scope that resolves through s. Stopping s stops its
// children first.
//
// A child made inside a constructor carries that constructor's resolution
// path, so a cycle through it is reported rather than deadlocking. The path
// goes inert when the constructor returns (see resolver.done), so a child kept
// for later, such as a request scope, resolves as an independent branch.
func (s *Scope) Child(name string) *Scope {
        st := newState(name, s.state)
        s.mu.Lock()
        s.children = append(s.children, st)
        s.mu.Unlock()
        return &Scope{state: st, r: s.r, module: s.module}
}

func (s *Scope) view(r *resolver) *Scope { return &Scope{state: s.state, r: r, module: s.module} }

// A Module is a unit of wiring: a function that registers into a scope.
// Modules compose by ordinary function composition, and [Scope.Use] applies
// them in order. Every registration a module makes is attributed to it, so a
// collision between two modules is reported as one.
type Module func(*Scope)

// Use applies each module to this scope. A registration made while a module
// runs -- directly, or from a child the module opens, or later from a
// constructor the module registered -- carries that module's name, which is
// the name of the function: register modules as named functions rather than
// closures, or the name is the enclosing function's.
func (s *Scope) Use(mods ...Module) {
        for _, m := range mods {
                m(&Scope{state: s.state, r: s.r, module: moduleName(m)})
        }
}

// moduleName is the function's name, package-qualified and without the import
// path: "app.Storage" for a function Storage in package app.
func moduleName(m Module) string {
        if m == nil {
                return ""
        }
        fn := runtime.FuncForPC(reflect.ValueOf(m).Pointer())
        if fn == nil {
                return ""
        }
        name := fn.Name()
        if i := strings.LastIndex(name, "/"); i >= 0 {
                name = name[i+1:]
        }
        return name
}

// Observe registers fn to receive lifecycle events from this scope and every
// scope under it. Use it for logging and metrics.
func (s *Scope) Observe(fn func(Event)) {
        s.mu.Lock()
        s.observers = append(s.observers, fn)
        s.mu.Unlock()
}

// emit delivers ev to the observers of st and its ancestors.
func (st *state) emit(ev Event) {
        for ; st != nil; st = st.parent {
                st.mu.Lock()
                obs := slices.Clone(st.observers)
                st.mu.Unlock()
                for _, fn := range obs {
                        fn(ev)
                }
        }
}

// report emits the event for one lifecycle step of b, owned by this scope,
// that began at t0 and ended with err.
func (st *state) report(kind EventKind, b *binding, t0 time.Time, err error) {
        st.emit(Event{
                Kind: kind, Service: b.key.String(), Package: b.key.pkgPath(),
                Scope: st.name, Site: b.site, Module: b.module,
                Duration: time.Since(t0), Err: err,
        })
}

// TB is the subset of testing.TB that Test needs.
type TB interface {
        Helper()
        Cleanup(func())
        Errorf(format string, args ...any)
}

// Test returns a scope for a test: the modules register the graph under test,
// and the scope is stopped when the test ends, failing it if a stop hook
// errors. Override what you need faked after wiring and before resolving,
// saying so:
//
//        s := di.Test(t, app.Production)
//        s.Value(&DB{DSN: "sqlite://memory"}).Override()
//        repo := s.Get[*Repo]()
func Test(tb TB, wire ...Module) *Scope {
        tb.Helper()
        s := New()
        s.Use(wire...)
        tb.Cleanup(func() {
                if err := s.Stop(context.Background()); err != nil {
                        tb.Errorf("di: stopping test scope: %v", err)
                }
        })
        return s
}

type ctxKey struct{}

// WithScope attaches s to ctx so handlers and their callees can reach it
// with FromContext.
func WithScope(ctx context.Context, s *Scope) context.Context {
        return context.WithValue(ctx, ctxKey{}, s)
}

// FromContext returns the scope attached with WithScope, if any.
func FromContext(ctx context.Context) (*Scope, bool) {
        s, ok := ctx.Value(ctxKey{}).(*Scope)
        return s, ok
}

// Package dihttp connects a di.Scope to net/http.
//
// A [Middleware] gives every request its own child scope holding the
// *http.Request, so services that depend on the request are declared once in
// the application scope as Scoped and built per request. Handlers reach the
// scope through [di.FromContext], or are made with [Handle], which resolves a
// handler type from that scope and calls one of its methods. [Module]
// registers the middleware as a service, so a server's constructor takes it
// as a parameter; [NewMiddleware] makes one directly.
package dihttp

import (
        "context"
        "net/http"

        "github.com/floatdrop/di"
)

// Middleware gives every request its own child scope of the application
// scope: the *http.Request is registered in it, the scope is attached to the
// request context, and it is stopped (and detached) when the handler returns.
// Stop failures reach the application scope's observers as EventStop with Err
// set.
//
// It has the usual middleware shape, so it wraps a handler directly or goes
// into a router's Use. Take it as a dependency after Module has registered
// it, or make one with NewMiddleware.
type Middleware func(http.Handler) http.Handler

// Module registers a Middleware over the scope it is applied to, so that a
// constructor wired into that scope can take one as a parameter:
//
//        app.Use(dihttp.Module, api.Module)
//
//        func NewServer(cfg Config, mw dihttp.Middleware) *http.Server {
//                return &http.Server{Addr: cfg.Addr, Handler: mw(mux)}
//        }
//
// The middleware needs the scope itself, to open a child per request, which
// is why this is the one closure in the package rather than a wired
// constructor.
func Module(s *di.Scope) {
        s.Provide(func(s *di.Scope) Middleware { return NewMiddleware(s) })
}

// NewMiddleware makes a Middleware whose request scopes are children of s.
func NewMiddleware(s *di.Scope) Middleware {
        return func(next http.Handler) http.Handler {
                return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
                        req := s.Child("request")
                        // Attach the scope, then register that same request and hand it
                        // on. The handler and the constructors must see one
                        // *http.Request: routers write path values and the matched
                        // pattern into the request they are given, so a copy registered
                        // here would miss them.
                        r = r.WithContext(di.WithScope(r.Context(), req))
                        req.Value(r)
                        defer func() { _ = req.Stop(context.WithoutCancel(r.Context())) }()
                        next.ServeHTTP(w, r)
                })
        }
}

// Handle serves each request with a method of H, resolved from the request's
// scope. A method expression names both, so no type argument is needed:
//
//        mux.Handle("GET /users/{id}", dihttp.Handle((*Users).Show))
//
// H is a service like any other: declared Scoped when it needs the request,
// and once for the application when it does not; one type per resource, with
// a method per route, keeps the dependencies in one place. Resolution follows
// the lifetime either way. A wiring failure at request time panics with the
// error, which net/http recovers and logs with the request; checking the
// graph with Validate at startup is what keeps that from happening.
func Handle[H any](method func(H, http.ResponseWriter, *http.Request)) http.Handler {
        return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
                req, ok := di.FromContext(r.Context())
                if !ok {
                        panic("dihttp: no request scope on the context; is the Middleware above this handler?")
                }
                method(req.Get[H](), w, r)
        })
}

// Package dislog logs a di.Scope's lifecycle events through log/slog.
//
// [New] turns a *slog.Logger into the function [di.Scope.Observe] takes,
// so an application says what it is doing as it builds, starts, drains and
// stops:
//
//        app.Observe(dislog.New(slog.Default()))
//
// It imports nothing outside the standard library, so any slog handler will
// do, including one that colours its output. Events arrive on the goroutine
// that did the work, one per constructor and per hook, so a slow handler slows
// the application down; a *slog.Logger is safe to share, and events do arrive
// from several goroutines at once.
package dislog

import (
        "context"
        "log/slog"
        "path"
        "strings"

        "github.com/floatdrop/di"
)

// New returns a function for [di.Scope.Observe] that logs each event
// through l. The message is the event's kind -- "build", "start", "drain",
// "stop" or "shutdown" -- and the attributes are the service, its scope, the
// module it was registered from when there is one, and how long the step took.
//
// A service is named the way it is written in Go rather than the way an event
// carries it: "service=*mail.Mailer" with the import path alongside as
// "pkg=github.com/acme/app/internal/mail", since the path is most of the
// length and none of the meaning. The two come from [di.Event.Service] and
// [di.Event.Package], so nothing is parsed; a key whose type is unnamed
// reports no package and keeps its whole name.
//
// An event carrying an error is logged at [slog.LevelError] with an "err"
// attribute and the registration site, since that is what a failure is read
// with; anything else is logged at [slog.LevelInfo], or at the level [Level]
// sets. Pass [Site] to log the site every time.
func New(l *slog.Logger, opts ...Option) func(di.Event) {
        cfg := options{level: slog.LevelInfo}
        for _, o := range opts {
                o(&cfg)
        }
        return func(ev di.Event) {
                level := cfg.level
                if ev.Err != nil {
                        level = slog.LevelError
                }
                if !l.Enabled(context.Background(), level) {
                        return
                }
                attrs := make([]slog.Attr, 0, 7)
                if ev.Service != "" { // a shutdown names no service
                        attrs = append(attrs, slog.String("service", short(ev.Service, ev.Package)))
                        if ev.Package != "" {
                                attrs = append(attrs, slog.String("pkg", ev.Package))
                        }
                }
                attrs = append(attrs, slog.String("scope", ev.Scope))
                if ev.Module != "" {
                        attrs = append(attrs, slog.String("module", ev.Module))
                }
                if ev.Kind != di.EventShutdown {
                        attrs = append(attrs, slog.Duration("duration", ev.Duration))
                }
                if ev.Site != "" && (cfg.site || ev.Err != nil) {
                        attrs = append(attrs, slog.String("site", ev.Site))
                }
                if ev.Err != nil {
                        attrs = append(attrs, slog.Any("err", ev.Err))
                }
                l.LogAttrs(context.Background(), level, string(ev.Kind), attrs...)
        }
}

// short is the service name with its import path taken off:
// "*github.com/acme/app.DB" and "github.com/acme/app" become "*app.DB".
//
// The event carries both, so there is nothing to guess. An empty pkg is a
// type with no path to take off -- an unnamed type, which reflect already
// writes short, or a shutdown, which names no service -- and its name is
// returned as it came. A generic instantiation keeps its type arguments,
// because what is trimmed is the prefix rather than everything after a dot.
func short(service, pkg string) string {
        if pkg == "" {
                return service
        }
        stars := 0
        for stars < len(service) && service[stars] == '*' {
                stars++
        }
        name, ok := strings.CutPrefix(service[stars:], pkg+".")
        if !ok {
                return service // not the shape the pair promises; report it whole
        }
        return service[:stars] + path.Base(pkg) + "." + name
}

// Option configures the observer New returns.
type Option func(*options)

type options struct {
        level slog.Level
        site  bool
}

// Level sets the level an event that succeeded is logged at. Building every
// service is worth a line while an application is being wired and noise once
// it works, so [slog.LevelDebug] is the usual second choice. A failure is
// logged at [slog.LevelError] whatever this says.
func Level(lv slog.Level) Option { return func(o *options) { o.level = lv } }

// Site includes the registration site -- the file:line the service was
// registered at -- on every event, rather than only on the ones that failed.
func Site() Option { return func(o *options) { o.site = true } }

package di

// Rendering the graph. Nothing here participates in resolution or teardown:
// it reads the edges resolve.go records while constructors run, under the same
// mutex that guards every other field of an instance, and never holds two of
// those at once, and it reads the dependency lists Wire declares, which never
// change after registration. It is also the only part of the package that
// builds strings for a person rather than for an error.

import (
        "fmt"
        "reflect"
        "slices"
        "strings"
)

// Explain renders what T resolves to and what it was built from: the
// dependency tree, each node with its lifetime, its scope, the state of its
// lifecycle and where it was registered, followed by what needed it.
//
// What has been built has a recorded tree, because a constructor's
// dependencies are recorded as it resolves them. A service that has not been
// built is reported as such, with its registration; if it was registered
// with Wire, the dependencies it declares are drawn under it with dashed
// edges, each continuing as a recorded tree where it has been built and as a
// declared one where it has not, and "declared by" lists the unbuilt
// services that declare it. A closure that has not run ends its branch,
// since nothing is known about it yet, and so does a key nothing provides.
// Explain resolves nothing and builds nothing; it commits pending
// registrations the way a resolution from this scope would, so a
// configuration this scope would reject is reported here by the same panic.
//
// A key served by a group is explained member by member. A dependency reached
// twice, as in a diamond, is expanded once and named on later visits, so the
// tree stays finite and the repeat is visibly the same instance.
func (s *Scope) Explain[T any]() string {
        k := key{t: reflect.TypeFor[T]()}
        b, owner := s.lookup(k)
        members := s.groupMembers(k)
        if b == nil && len(members) == 0 {
                return fmt.Sprintf("%s: not provided\n", k)
        }

        var sb strings.Builder
        seen := map[*instance]bool{}
        if b != nil {
                s.explainOne(&sb, b, owner, seen)
        }
        for _, m := range members {
                if sb.Len() > 0 {
                        sb.WriteString("\n")
                }
                s.explainOne(&sb, m.b, m.owner, seen)
        }
        return sb.String()
}

// found is a binding and the scope that registered it, which is what group
// lookup has to carry and single-key lookup returns as a pair.
type found struct {
        b     *binding
        owner *state
}

// groupMembers lists the group registered for k across the scope chain, in
// the order All resolves them.
func (s *Scope) groupMembers(k key) []found {
        var out []found
        for st := s.state; st != nil; st = st.parent {
                st.freeze()
                st.mu.Lock()
                bs := slices.Clone(st.groups[k])
                st.mu.Unlock()
                for _, b := range bs {
                        out = append(out, found{b: b, owner: st})
                }
        }
        return out
}

// explainOne renders one binding's tree, and the instances that needed it.
func (s *Scope) explainOne(sb *strings.Builder, b *binding, owner *state, seen map[*instance]bool) {
        holder := owner
        if b.scoped {
                holder = s.state
        }
        holder.mu.Lock()
        in := holder.instanceAt(b)
        holder.mu.Unlock()
        // A Scoped binding this scope has never resolved has no instance; a
        // singleton always has one, built or not. Either way an unbuilt service
        // has no recorded tree, only what Wire declared.
        phase, deps, fresh := "not built", []dep(nil), true
        if in != nil {
                phase, deps, fresh = dep{in: in, holder: holder}.inspect()
        }
        sb.WriteString(describe(b, holder, phase) + "\n")

        var by []dep
        if fresh {
                s.declaredInto(sb, b, holder, "", seen, map[*binding]bool{b: true})
        } else {
                seen[in] = true
                explainInto(sb, deps, "", seen)
                by = dependentsOf(s.root(), in)
        }
        if len(by) > 0 {
                names := make([]string, len(by))
                for i, d := range by {
                        names[i] = d.in.b.key.String() + " in " + d.holder.name
                }
                sb.WriteString("needed by: " + strings.Join(names, ", ") + "\n")
        }
        if declared := s.declaredBy(b, by); len(declared) > 0 {
                sb.WriteString("declared by: " + strings.Join(declared, ", ") + "\n")
        }
}

// declaredInto draws the dependencies b declares under a node that has not
// been built, with dashed edges, looking each up from holder as the build
// would. One that has been built continues as its recorded tree; one that has
// not continues as its own declaration, or ends the branch if it is a closure,
// which declares nothing. drawn keeps a declared binding from being expanded
// twice, which is what a diamond needs and what a cycle needs more.
func (s *Scope) declaredInto(sb *strings.Builder, b *binding, holder *state, prefix string, seen map[*instance]bool, drawn map[*binding]bool) {
        edges := declared(b, holder)
        for i, e := range edges {
                branch, pad := "├╌╌ ", "│   "
                if i == len(edges)-1 {
                        branch, pad = "└╌╌ ", "    "
                }
                sb.WriteString(prefix + branch)
                target, owner := e.b, e.owner
                if target == nil {
                        sb.WriteString(e.k.String() + ": not provided\n")
                        continue
                }
                th := owner
                if target.scoped {
                        th = holder
                }
                th.mu.Lock()
                in := th.instanceAt(target)
                th.mu.Unlock()
                if in != nil {
                        if seen[in] {
                                sb.WriteString(target.key.String() + ": see above\n")
                                continue
                        }
                        if phase, next, fresh := (dep{in: in, holder: th}).inspect(); !fresh {
                                seen[in] = true
                                sb.WriteString(describe(target, th, phase) + "\n")
                                explainInto(sb, next, prefix+pad, seen)
                                continue
                        }
                }
                if drawn[target] {
                        sb.WriteString(target.key.String() + ": see above\n")
                        continue
                }
                drawn[target] = true
                sb.WriteString(describe(target, th, "not built") + "\n")
                s.declaredInto(sb, target, th, prefix+pad, seen, drawn)
        }
}

// declaredBy lists the Wire bindings, in any scope of the container, that
// declare b's key and would resolve it to b from the scope that registered
// them, leaving out the instances already named as having needed it. A
// Scoped one is named by the scope declaring it, since the scopes that will
// resolve it do not exist yet. It reads what is committed and commits
// nothing, so a descendant's pending registrations neither appear nor get
// the chance to be rejected here.
func (s *Scope) declaredBy(b *binding, except []dep) []string {
        var out []string
        for _, st := range walkScopes(s.root()) {
                for _, d := range st.live() {
                        if d == b || slices.ContainsFunc(except, func(e dep) bool { return e.in.b == d }) {
                                continue
                        }
                        if d.inner != b && (!slices.Contains(d.wants, b.key) || peek(st, b.key) != b) {
                                continue
                        }
                        out = append(out, d.key.String()+" in "+st.name)
                }
        }
        return out
}

// peek is lookup without the freeze: the binding k resolves to from st among
// the registrations already committed.
func peek(st *state, k key) *binding {
        for ; st != nil; st = st.parent {
                st.mu.Lock()
                b, ok := st.index[k]
                st.mu.Unlock()
                if ok {
                        return b
                }
        }
        return nil
}

// explainInto writes one level of the tree and recurses, drawing the spine
// with the usual box characters.
func explainInto(sb *strings.Builder, deps []dep, prefix string, seen map[*instance]bool) {
        for i, d := range deps {
                branch, pad := "├── ", "│   "
                if i == len(deps)-1 {
                        branch, pad = "└── ", "    "
                }
                sb.WriteString(prefix + branch)
                if seen[d.in] {
                        // The same instance by another route. Naming it without its
                        // subtree keeps a diamond from being drawn twice, and says that
                        // it is one value rather than two of a type.
                        sb.WriteString(d.in.b.key.String() + ": see above\n")
                        continue
                }
                seen[d.in] = true
                phase, next, _ := d.inspect()
                sb.WriteString(describe(d.in.b, d.holder, phase) + "\n")
                explainInto(sb, next, prefix+pad, seen)
        }
}

// Graph renders everything built in this scope and its descendants as
// Graphviz DOT: one box per instance, one cluster per scope that holds any,
// and an arrow from each instance to what its constructor resolved.
//
// It reads the graph and changes nothing, not even the pending registrations,
// so it is safe to call from a handler or a hook. Nodes are numbered in the
// order the scopes were created and the instances were built, so the same run
// of the same program renders the same document. A scope that has been
// stopped no longer holds its instances and contributes nothing.
//
// The detail is deliberately thin -- a registration site would not fit in a
// box. Use Explain for one service in full.
func (s *Scope) Graph() string {
        scopes := walkScopes(s.state)
        type node struct {
                d     dep
                id    int
                phase string
        }
        ids := map[*instance]int{}
        byScope := make([][]node, len(scopes))
        var all []node
        for i, st := range scopes {
                st.mu.Lock()
                built := slices.Clone(st.started)
                st.mu.Unlock()
                for _, in := range built {
                        d := dep{in: in, holder: st}
                        phase, _, _ := d.inspect()
                        n := node{d: d, id: len(all), phase: phase}
                        ids[in] = n.id
                        all = append(all, n)
                        byScope[i] = append(byScope[i], n)
                }
        }

        var sb strings.Builder
        sb.WriteString("digraph di {\n")
        sb.WriteString("  rankdir=LR;\n")
        sb.WriteString("  node [shape=box, fontname=\"monospace\"];\n")
        for i, st := range scopes {
                if len(byScope[i]) == 0 {
                        continue
                }
                fmt.Fprintf(&sb, "  subgraph cluster%d {\n", i)
                fmt.Fprintf(&sb, "    label=%s;\n", dotLabel(scopePath(st, s.state)))
                for _, n := range byScope[i] {
                        fmt.Fprintf(&sb, "    n%d [label=%s];\n", n.id,
                                dotLabel(n.d.in.b.key.String(), lifetime(n.d.in.b)+", "+n.phase))
                }
                sb.WriteString("  }\n")
        }
        // Edges last and outside every cluster: one that crosses a cluster
        // boundary is drawn wrong if it is declared inside one.
        for _, n := range all {
                _, deps, _ := n.d.inspect()
                for _, d := range deps {
                        if to, ok := ids[d.in]; ok {
                                fmt.Fprintf(&sb, "  n%d -> n%d;\n", n.id, to)
                        }
                        // An edge to something outside this walk is dropped rather than
                        // given a node of its own: it points into a scope that has been
                        // stopped, or one above the scope Graph was called on.
                }
        }
        sb.WriteString("}\n")
        return sb.String()
}

// ---- rendering helpers -----------------------------------------------------

// inspect reads the one instance's phase and edges together, which is the
// only critical section a rendering takes, and says whether the instance is
// still unbuilt, in which case the edges are not there to read and what the
// binding declares stands in. Nothing is held across the recursion, so two
// scopes' mutexes are never held at once.
func (d dep) inspect() (phase string, deps []dep, fresh bool) {
        d.holder.mu.Lock()
        defer d.holder.mu.Unlock()
        return phaseWord(d.in), slices.Clone(d.in.deps), d.in.ph == phaseNew
}

// phaseWord names where an instance is in its lifecycle. Called with the
// owning state's mutex held, like every other read of ph and err.
func phaseWord(in *instance) string {
        switch in.ph {
        case phaseNew:
                return "not built"
        case phaseBuilding:
                return "building"
        case phaseBuilt:
                return "built"
        case phaseStarting:
                return "starting"
        case phaseStarted:
                return "started"
        case phaseStopped:
                return "stopped"
        case phaseFailed:
                if in.err != nil {
                        return "failed: " + in.err.Error()
                }
                return "failed"
        }
        return "unknown"
}

// lifetime names how a binding is kept, in the words the API uses.
func lifetime(b *binding) string {
        life := "singleton"
        switch {
        case b.isValue:
                life = "value"
        case b.scoped:
                life = "scoped"
        }
        if b.group {
                life += " group member"
        }
        if b.inner != nil {
                life += " wrapper"
        }
        return life
}

// describe is one line of a tree: what the service is, where it lives, how
// far through its lifecycle it is, and where it was registered.
func describe(b *binding, holder *state, phase string) string {
        attrs := []string{lifetime(b) + " in " + holder.name}
        if b.eager {
                attrs = append(attrs, "eager")
        }
        attrs = append(attrs, phase)
        return fmt.Sprintf("%s: %s (provided at %s)", b.key, strings.Join(attrs, ", "), b.site)
}

// dependentsOf finds the built instances whose constructors resolved target.
// It searches from the container root, because a dependent lives in the
// scope that holds it or below, never above what it depends on.
func dependentsOf(from *state, target *instance) []dep {
        var out []dep
        for _, st := range walkScopes(from) {
                st.mu.Lock()
                for _, in := range st.started {
                        if slices.ContainsFunc(in.deps, func(d dep) bool { return d.in == target }) {
                                out = append(out, dep{in: in, holder: st})
                        }
                }
                st.mu.Unlock()
        }
        return out
}

// walkScopes lists st and every scope under it, parents before children and
// in creation order, so a rendering is stable across runs.
func walkScopes(st *state) []*state {
        st.mu.Lock()
        children := slices.Clone(st.children)
        st.mu.Unlock()
        out := []*state{st}
        for _, c := range children {
                out = append(out, walkScopes(c)...)
        }
        return out
}

// root returns the topmost scope of this container.
func (st *state) root() *state {
        for st.parent != nil {
                st = st.parent
        }
        return st
}

// scopePath names st relative to from, so two scopes with the same name are
// told apart by where they hang.
func scopePath(st, from *state) string {
        var parts []string
        for ; st != nil; st = st.parent {
                parts = append(parts, st.name)
                if st == from {
                        break
                }
        }
        slices.Reverse(parts)
        return strings.Join(parts, "/")
}

// dotEscape is what a DOT quoted string needs escaped inside it.
var dotEscape = strings.NewReplacer(`\`, `\\`, `"`, `\"`)

// dotLabel quotes the parts as one DOT label, one per line. Scope names come
// from the caller, so they are escaped rather than trusted.
func dotLabel(parts ...string) string {
        esc := make([]string, len(parts))
        for i, p := range parts {
                esc[i] = dotEscape.Replace(p)
        }
        return `"` + strings.Join(esc, `\n`) + `"`
}

// Modules renders the modules registered into this scope and its ancestors:
// what each provides, what it needs and which module serves it, what it
// wraps, and which of its constructors are closures whose needs are unknown
// until they run. A need only a resolving scope can provide, as a request
// scope provides the request, is reported as owed, the way Validate reports
// it. A dependency a module serves for itself is not a module dependency and
// is left out. Registrations made outside any module are grouped as
// "registered directly".
//
// Like Explain, it builds nothing and commits pending registrations the way
// a resolution would, so a configuration this scope would reject is reported
// by the same panic.
func (s *Scope) Modules() string {
        var chain []*state
        for st := s.state; st != nil; st = st.parent {
                st.freeze()
                chain = append(chain, st)
        }
        type module struct {
                name                              string
                provides, needs, wraps, unchecked []string
                seen                              map[string]bool
        }
        var order []*module
        byName := map[string]*module{}
        get := func(name string) *module {
                if m := byName[name]; m != nil {
                        return m
                }
                m := &module{name: name, seen: map[string]bool{}}
                byName[name] = m
                order = append(order, m)
                return m
        }
        // One set per module, keyed by section as well as line: a key is listed
        // under provides and then again under unchecked, and both lines stay.
        add := func(m *module, list *[]string, line string) {
                id := fmt.Sprintf("%p:%s", list, line)
                if !m.seen[id] {
                        m.seen[id] = true
                        *list = append(*list, line)
                }
        }
        // Ancestors first, so the report reads top-down like the scope tree and
        // a module is listed where it was first used.
        for _, st := range slices.Backward(chain) {
                for _, b := range st.live() {
                        m := get(moduleLabel(b))
                        if b.inner != nil {
                                add(m, &m.wraps, shortName(b.key.t)+" ← "+moduleLabel(b.inner))
                        } else {
                                add(m, &m.provides, shortName(b.key.t))
                        }
                        switch {
                        case b.isValue:
                                continue
                        case b.wants == nil:
                                add(m, &m.unchecked, shortName(b.key.t))
                                continue
                        }
                        holder := st
                        if b.scoped {
                                holder = s.state
                        }
                        for _, k := range b.wants {
                                dep, _ := (&Scope{state: holder}).lookup(k)
                                var from string
                                switch {
                                case dep == nil && b.scoped:
                                        from = "owed to a resolving scope"
                                case dep == nil:
                                        from = "not provided"
                                case moduleLabel(dep) == m.name:
                                        continue // the module's own business
                                default:
                                        from = moduleLabel(dep)
                                }
                                add(m, &m.needs, shortName(k.t)+" ← "+from)
                        }
                }
        }

        var sb strings.Builder
        for _, m := range order {
                sb.WriteString(m.name + "\n")
                section := func(label string, lines []string) {
                        for i, l := range lines {
                                if i == 0 {
                                        fmt.Fprintf(&sb, "  %-10s %s\n", label, l)
                                } else {
                                        fmt.Fprintf(&sb, "  %-10s %s\n", "", l)
                                }
                        }
                }
                if len(m.provides) > 0 {
                        section("provides", []string{strings.Join(m.provides, ", ")})
                }
                section("wraps", m.wraps)
                section("needs", m.needs)
                if len(m.unchecked) > 0 {
                        section("unchecked", []string{strings.Join(m.unchecked, ", ") + " (closures: needs known when they run)"})
                }
        }
        return sb.String()
}

// moduleLabel names the module a binding was registered from, or says that
// there was none.
func moduleLabel(b *binding) string {
        if b.module == "" {
                return "registered directly"
        }
        return b.module
}

// shortName is a key with its package named the way code names it,
// storage.Store rather than the import path, to match the module labels
// beside it. Explain keeps the full path, since an error message must not
// confuse two packages of one name; a module report is read by a person
// who knows their packages.
func shortName(t reflect.Type) string {
        if t.Kind() == reflect.Pointer {
                return "*" + shortName(t.Elem())
        }
        if t.PkgPath() != "" {
                return t.PkgPath()[strings.LastIndex(t.PkgPath(), "/")+1:] + "." + t.Name()
        }
        return t.String()
}

package di

// The lifecycle: an instance's phase machine, the hooks that move it through
// its start, drain and stop steps, and Start and Stop, which drive that
// machine for a whole scope tree. Every phase is read and written under the
// owning state's mutex, and every user hook is called through callHook.

import (
        "context"
        "errors"
        "fmt"
        "slices"
        "time"
)

// phase is an instance's position in the build/start/stop sequence. It is
// read and written only under the owning state's mutex, so deciding who
// starts or stops an instance never spans two critical sections.
type phase int8

const (
        phaseNew      phase = iota // no value yet
        phaseBuilding              // a resolution has claimed the build step
        phaseBuilt                 // constructor ran; the start step has not
        phaseStarting              // a goroutine has claimed the start step
        phaseStarted               // the start step succeeded
        phaseFailed                // the build or the start step failed
        phaseStopped               // the stop step ran, or was skipped for good
)

// drainPhase tracks OnDrain the way phase tracks the build and start steps:
// a drain in progress is waited for, so a waiter has to tell it from one that
// has finished.
type drainPhase int8

const (
        drainNone drainPhase = iota // OnDrain has not been considered
        draining                    // a Stop is running OnDrain now
        drained                     // OnDrain ran, or was skipped for good
)

// dep is one recorded dependency edge: an instance a constructor resolved,
// and the scope holding it, which is what names it in a rendering. The
// holder is carried rather than looked up because an instance does not know
// its own scope, and the scope it was resolved from may be gone by the time
// anything reads the edge.
type dep struct {
        in     *instance
        holder *state
}

// instance is one built value of a binding, owned by the state that stops it.
type instance struct {
        b     *binding
        ph    phase // guarded by the owning state's mutex
        value any
        err   error // guarded by the owning state's mutex
        // settled is set when the build step has finished and value and err are
        // final.
        settled bool       // guarded by the owning state's mutex
        dr      drainPhase // guarded by the owning state's mutex

        // deps are the services this instance's constructor resolved, in the
        // order it asked for them, each recorded once however many times it
        // asked. Guarded by the owning state's mutex, because a constructor may
        // resolve from several goroutines at once and they share the Scope it
        // was handed. Only Explain and Graph read them; nothing in the
        // build/start/stop machine does.
        deps []dep

        // Each step another goroutine may have to wait for has a channel that is
        // closed when the step is done, so a waiter blocks on that step alone.
        // The first goroutine that has to wait makes the channel (waitOn); the
        // owner of the step closes it if it exists (wake). Both happen under the
        // owning state's mutex, in the same critical section as the phase change,
        // so either order is safe: a waiter that arrives first is released by the
        // close, and an owner that finishes first leaves nil behind, in which case
        // the phase already says the step is done and the waiter never blocks.
        //
        // Nil is the normal state. An uncontended build, an unraced start step
        // and an undisputed drain allocate nothing. Never block on one of these
        // fields directly, since a receive from a nil channel blocks for ever;
        // go through waitOn.
        settledCh  chan struct{} // closed by settle: value and err are final
        startingCh chan struct{} // closed when the start step is no longer in flight
        drainedCh  chan struct{} // closed when OnDrain has finished

        // builder is the resolution running the build step, guarded by the
        // container graph's mutex. It is the edge that makes a cycle between
        // concurrent builds visible.
        builder *resolver

        // Worker hook bookkeeping, guarded by the phase machine rather than a mutex.
        // cancel and runDone are written by start, on the goroutine that owns the
        // start step, and read by stop, which stopIfNeeded reaches only after
        // startClaimed has moved the phase past phaseStarting under the owning
        // state's mutex; that lock handoff is the happens-before. runErr is written
        // by the worker goroutine before it closes runDone and read only after a
        // receive from runDone.
        cancel  context.CancelFunc
        runDone chan struct{}
        runErr  error
}

// wake closes a step's channel if a waiter made one.
func wake(ch chan struct{}) {
        if ch != nil {
                close(ch)
        }
}

// waitOn returns a step's channel, making it on first use. Called under the
// owning state's mutex, in the critical section that read the phase.
func waitOn(ch *chan struct{}) chan struct{} {
        if *ch == nil {
                *ch = make(chan struct{})
        }
        return *ch
}

// once is a teardown phase that runs at most once per scope: the first caller
// runs it, and every later or concurrent caller waits for that run, bounded by
// its own context. Stop and the scope-wide drain are both this shape.
//
// Its fields are guarded by the state's mutex, so claiming the phase and
// recording what the claim decided are one critical section, and no third
// lock joins the ordering rules.
type once struct {
        done chan struct{} // made by the claimer, closed once its run has finished
        err  error         // that run's result
}

// claim reports whether this caller owns the run. The owner must call settle
// exactly once; everyone else calls wait. claimed, if non-nil, runs under the
// mutex in the same critical section that picks the winner, for state a waiter
// must see as soon as it sees the phase claimed.
func (o *once) claim(st *state, claimed func()) bool {
        st.mu.Lock()
        defer st.mu.Unlock()
        if o.done != nil {
                return false
        }
        o.done = make(chan struct{})
        if claimed != nil {
                claimed()
        }
        return true
}

// settle publishes the run's result and releases the waiters.
func (o *once) settle(st *state, err error) {
        st.mu.Lock()
        o.err = err
        st.mu.Unlock()
        close(o.done)
}

// wait blocks until the owning run has finished and reports its error, or
// reports false if the caller's context expires first. Only a caller whose
// claim returned false may wait: an unclaimed phase has no channel and would
// block until ctx expires.
func (o *once) wait(st *state, ctx context.Context) (finished bool, err error) {
        st.mu.Lock()
        done := o.done
        st.mu.Unlock()
        select {
        case <-done:
        case <-ctx.Done():
                return false, nil
        }
        st.mu.Lock()
        defer st.mu.Unlock()
        return true, o.err
}

// hookKey marks a context as belonging to a lifecycle hook.
type hookKey struct{}

// inHook tags the context a hook is called with, so a Stop made with that
// context can name the misuse instead of waiting for a step the caller is
// itself running. A hook that passes a context of its own is not seen.
func inHook(ctx context.Context, st *state) context.Context {
        return context.WithValue(ctx, hookKey{}, st)
}

// hookOwner returns the scope whose hook ctx belongs to, or nil.
func hookOwner(ctx context.Context) *state {
        st, _ := ctx.Value(hookKey{}).(*state)
        return st
}

// callHook runs a lifecycle hook and reports what it did as an error, a panic
// included. A hook that panics -- or resolves something whose registration is
// rejected, which reaches it as a panic -- must not take the teardown down
// with it: stopOnce would be claimed and never settled, every later Stop
// would wait for it, and every instance behind it would never be released.
func callHook(hook func(context.Context, any) error, ctx context.Context, v any) (err error) {
        defer func() {
                if rec := recover(); rec != nil {
                        if a, ok := rec.(abort); ok {
                                err = a.err // a nested resolution failed; report that cause
                        } else {
                                err = fmt.Errorf("panic: %v", rec)
                        }
                }
        }()
        return hook(ctx, v)
}

// start runs OnStart and launches the Worker hook. The worker's context is
// detached from ctx so the worker is cancelled by Stop, in dependency order,
// rather than the moment the application context is cancelled.
func (in *instance) start(ctx context.Context, owner *state) error {
        b := in.b
        if b.onStart != nil {
                t0 := time.Now()
                err := callHook(b.onStart, inHook(ctx, owner), in.value)
                owner.report(EventStart, b, t0, err)
                if err != nil {
                        return err
                }
        }
        if b.worker != nil {
                rctx, cancel := context.WithCancel(context.WithoutCancel(ctx))
                in.cancel, in.runDone = cancel, make(chan struct{})
                hctx := inHook(rctx, owner)
                go func() {
                        defer close(in.runDone)
                        err := b.worker(hctx, in.value)
                        if err == nil {
                                return
                        }
                        if rctx.Err() != nil && onlyCancellation(err) {
                                return // we cancelled it and it reported just that
                        }
                        // Any other error is the worker's own failure and goes to
                        // Shutdown, whether or not the scope had begun stopping:
                        // rctx.Err() says whether we cancelled, not why the worker
                        // failed. It is wrapped once and kept, so that Stop, which
                        // reports it, and Run, which receives it, recognise one failure
                        // rather than listing it twice.
                        in.runErr = fmt.Errorf("di: %s: %w", b.key, err)
                        (&Scope{state: owner}).Shutdown(in.runErr)
                }()
        }
        return nil
}

// claim takes the start step for this goroutine, returning false if another
// one already has it or the instance is past starting.
func (in *instance) claim(owner *state) bool {
        owner.mu.Lock()
        defer owner.mu.Unlock()
        if in.ph != phaseBuilt {
                return false
        }
        in.ph = phaseStarting
        return true
}

// startClaimed runs the start step of an instance already in phaseStarting
// and settles the phase, which releases a Stop or a resolution waiting for
// the step. Only a hook that returned has started its service: a panic is a
// failed start, as it is for a constructor, or a caller that recovered it
// would be served a half-initialised service and Stop would pair an OnStop
// with an OnStart that never finished. The failure is recorded on the
// instance as well as returned, so a resolution that waited reports it too.
func (in *instance) startClaimed(ctx context.Context, owner *state) error {
        err := in.start(ctx, owner)
        owner.mu.Lock()
        if err == nil {
                in.ph = phaseStarted
        } else {
                in.ph = phaseFailed
                if in.err == nil {
                        in.err = fmt.Errorf("di: starting %s (provided at %s): %w", in.b.key, in.b.where(), err)
                }
        }
        wake(in.startingCh)
        owner.mu.Unlock()
        return err
}

// paired reports whether the instance's OnStop has an OnStart to pair with:
// the binding declares one and the scope has been started. It walks the
// parent chain, so it is answered before the owning state's mutex is taken.
func (in *instance) paired(owner *state) bool {
        return in.b.onStart != nil && owner.everStarted()
}

// owes reports whether the instance owes its drain and stop steps: it
// started, or it was built and has no start step to pair with, so OnStop is
// a plain destructor. An instance whose OnStart failed or was skipped by a
// rollback owes nothing. Called with the owning state's mutex held.
func (in *instance) owes(paired bool) bool {
        return in.ph == phaseStarted || (in.ph == phaseBuilt && !paired)
}

// stopIfNeeded runs the stop step once, if it is owed. It first waits out
// whichever step another goroutine is still running for this instance -- a
// start step, then a drain hook -- so the release never runs against a value
// one of them holds. That wait is what makes Stop synchronous, and it is safe
// because a hook may not call Stop on its own scope or an ancestor.
//
// If ctx expires first the release is still owed, and this is the only caller
// that can make it happen: Stop took the instance off its scope's list before
// the walk began. So the deadline ends the caller's wait, not the teardown,
// which finishes on a goroutine of its own once the step returns, with the
// spent deadline dropped so that it waits properly.
func (in *instance) stopIfNeeded(ctx context.Context, owner *state) error {
        paired := in.paired(owner)
        for {
                owner.mu.Lock()
                step, what := in.outstanding()
                if step == nil {
                        owed := in.owes(paired)
                        in.ph = phaseStopped
                        owner.mu.Unlock()
                        if !owed {
                                return nil
                        }
                        return in.stop(ctx, owner)
                }
                owner.mu.Unlock()
                select {
                case <-step:
                case <-ctx.Done():
                        go func() { _ = in.stopIfNeeded(context.WithoutCancel(ctx), owner) }()
                        return fmt.Errorf("di: stopping %s: %s did not return: %w", in.b.key, what, ctx.Err())
                }
        }
}

// outstanding names the step another goroutine is running for this instance,
// with the channel that goroutine will close, or nil if the instance is
// nobody else's business. Called with the owning state's mutex held, so the
// phase and the channel are read in one critical section.
func (in *instance) outstanding() (chan struct{}, string) {
        switch {
        case in.ph == phaseStarting:
                return waitOn(&in.startingCh), "OnStart"
        case in.dr == draining:
                return waitOn(&in.drainedCh), "OnDrain"
        }
        return nil, ""
}

// drainIfNeeded runs OnDrain once, if it is owed: a service that will not be
// stopped has nothing to wind down. It reports whether this call ran or waited
// for the hook, so a drain pass can tell that it did work.
//
// A drain another Stop has begun is waited for, not skipped, or this Stop
// would go on to run OnStop while that hook still holds the value. A start
// step in flight is waited for as well: a service that is starting owes a
// drain as soon as it has started.
func (in *instance) drainIfNeeded(ctx context.Context, owner *state) (bool, error) {
        b := in.b
        if b.onDrain == nil {
                return false, nil
        }
        paired := in.paired(owner)
        for {
                owner.mu.Lock()
                if in.dr == drained {
                        owner.mu.Unlock()
                        return false, nil
                }
                if in.dr == draining {
                        done := waitOn(&in.drainedCh)
                        owner.mu.Unlock()
                        select {
                        case <-done:
                                return true, nil
                        case <-ctx.Done():
                                return true, fmt.Errorf("di: draining %s: another Stop did not finish OnDrain: %w", b.key, ctx.Err())
                        }
                }
                if in.ph == phaseStarting {
                        starting := waitOn(&in.startingCh)
                        owner.mu.Unlock()
                        select {
                        case <-starting:
                                continue
                        case <-ctx.Done():
                                return false, fmt.Errorf("di: draining %s: OnStart did not return: %w", b.key, ctx.Err())
                        }
                }
                if owner.isStopped() || !in.owes(paired) {
                        // Not owed, or the scope's own Stop has moved past draining and a
                        // sweep still running in an ancestor reached an instance built
                        // into it: winding it down for work it can no longer take on is
                        // the opposite of what the hook is for. Straight to drained, so
                        // no waiter can arrive and no channel is needed.
                        in.dr = drained
                        owner.mu.Unlock()
                        return false, nil
                }
                in.dr = draining
                owner.mu.Unlock()
                break
        }

        t0 := time.Now()
        err := callHook(b.onDrain, inHook(ctx, owner), in.value)
        owner.report(EventDrain, b, t0, err)

        owner.mu.Lock()
        in.dr = drained
        wake(in.drainedCh)
        owner.mu.Unlock()

        if err != nil {
                return true, fmt.Errorf("di: draining %s: %w", b.key, err)
        }
        return true, nil
}

// stop cancels the Worker hook, waits for it within ctx, then runs OnStop.
//
// A Worker hook that outlasts ctx still holds the value, so OnStop cannot run yet
// without racing the worker. The missed deadline is reported to the caller and
// the release is finished when the worker returns, as Stop does for a start
// step in flight.
func (in *instance) stop(ctx context.Context, owner *state) error {
        b := in.b
        if in.cancel == nil && b.onStop == nil {
                return nil
        }
        t0 := time.Now()
        var errs []error
        if in.cancel != nil {
                in.cancel()
                select {
                case <-in.runDone:
                        if in.runErr != nil {
                                errs = append(errs, in.runErr)
                        }
                case <-ctx.Done():
                        err := fmt.Errorf("di: stopping %s: Worker hook did not return: %w", b.key, ctx.Err())
                        if b.onStop == nil {
                                owner.report(EventStop, b, t0, err)
                                return err
                        }
                        go in.releaseAfterWorker(context.WithoutCancel(ctx), owner, err)
                        return err
                }
        }
        if b.onStop != nil {
                if err := callHook(b.onStop, inHook(ctx, owner), in.value); err != nil {
                        errs = append(errs, fmt.Errorf("di: stopping %s: %w", b.key, err))
                }
        }
        err := errors.Join(errs...)
        owner.report(EventStop, b, t0, err)
        return err
}

// releaseAfterWorker finishes a stop step whose Worker hook outlasted Stop's
// context, once the hook returns. missed is what Stop returned to its caller;
// the instance's single EventStop is emitted here and carries it along with
// the release's own result, so no observer sees a service stopped twice.
func (in *instance) releaseAfterWorker(ctx context.Context, owner *state, missed error) {
        <-in.runDone
        b := in.b
        t0 := time.Now()
        errs := []error{missed}
        if in.runErr != nil {
                errs = append(errs, in.runErr)
        }
        if err := callHook(b.onStop, inHook(ctx, owner), in.value); err != nil {
                errs = append(errs, fmt.Errorf("di: stopping %s: %w", b.key, err))
        }
        owner.report(EventStop, b, t0, errors.Join(errs...))
}

// onlyCancellation reports whether err says nothing beyond context.Canceled:
// the cancellation itself, or wrappings of it. A worker that returns
// errors.Join(ctx.Err(), failure) after being cancelled is reporting the
// failure, and errors.Is would have called the whole thing a cancellation.
func onlyCancellation(err error) bool {
        if err == context.Canceled {
                return true
        }
        switch u := err.(type) {
        case interface{ Unwrap() []error }:
                errs := u.Unwrap()
                if len(errs) == 0 {
                        return false
                }
                for _, e := range errs {
                        if !onlyCancellation(e) {
                                return false
                        }
                }
                return true
        case interface{ Unwrap() error }:
                inner := u.Unwrap()
                return inner != nil && onlyCancellation(inner)
        }
        return false
}

// Start builds every Eager binding in registration order, then runs the
// start step of everything built so far, in build order. If a constructor
// or a start step fails, the scope is stopped, which rolls back exactly the
// services that did start, child scopes included. A service that was built
// but never started is not stopped, so acquire resources in OnStart rather
// than in the constructor when the binding declares one.
//
// After Start returns, a service built later runs its start step as part of
// being built, so lazily resolved services start too. Start may be called
// once, and builds only this scope's own Eager bindings: a child scope's are
// built by that child's Start.
func (s *Scope) Start(ctx context.Context) error {
        // Start has no deadline of its own for the rollback, so it detaches the
        // caller's context: an already-cancelled ctx must not skip the teardown.
        return s.start(ctx, func() (context.Context, func()) {
                return context.WithoutCancel(ctx), func() {}
        })
}

// start is Start with the rollback context supplied by the caller: Start
// detaches the caller's context, Run applies its StopTimeout and signal
// handling.
func (s *Scope) start(ctx context.Context, rollbackCtx func() (context.Context, func())) (err error) {
        defer recoverAbort(&err)
        s.freeze()
        s.mu.Lock()
        if s.startCtx != nil {
                s.mu.Unlock()
                return errors.New("di: Start called twice")
        }
        s.startCtx = ctx
        eager := slices.Clone(s.eager) // derived at freeze; clone so a later freeze cannot truncate it
        s.mu.Unlock()

        // A failing eager constructor must roll back like a failing hook.
        if err := s.buildEager(eager); err != nil {
                return errors.Join(err, s.rollback(rollbackCtx))
        }

        s.mu.Lock()
        s.running = true
        s.mu.Unlock()

        // Drain: anything built before the flag was set is still waiting here,
        // and starting one service may build more.
        for {
                in, owner := s.claimNext()
                if in == nil {
                        if s.isStopped() {
                                // A start hook stopped the scope; nothing is running.
                                return fmt.Errorf("di: Start: %w", ErrStopped)
                        }
                        return nil
                }
                if err := in.startClaimed(ctx, owner); err != nil {
                        err = fmt.Errorf("di: starting %s: %w", in.b.key, err)
                        return errors.Join(err, s.rollback(rollbackCtx))
                }
        }
}

func (s *Scope) rollback(mk func() (context.Context, func())) error {
        ctx, cancel := mk()
        defer cancel()
        return s.Stop(ctx)
}

// buildEager builds the eager bindings, turning a constructor failure into
// an error rather than letting it unwind past Start's rollback.
func (s *Scope) buildEager(eager []*binding) (err error) {
        defer recoverAbort(&err)
        for _, b := range eager {
                if b.group {
                        // A group member is not reachable by key: resolve it directly.
                        s.enter().resolve(b, s.state)
                        continue
                }
                // By key, so whichever registration owns the key is what gets built;
                // deriveEager has already checked that it can honour eagerness.
                s.enter().get(b.key)
        }
        return nil
}

// claimNext claims the start step of the next built-but-unstarted instance
// in this scope or a descendant, in build order.
func (st *state) claimNext() (*instance, *state) {
        st.mu.Lock()
        for _, in := range st.started {
                if in.ph == phaseBuilt {
                        in.ph = phaseStarting
                        st.mu.Unlock()
                        return in, st
                }
        }
        children := slices.Clone(st.children)
        st.mu.Unlock()
        for _, c := range children {
                if in, owner := c.claimNext(); in != nil {
                        return in, owner
                }
        }
        return nil, nil
}

// Context returns the context passed to Start (or Run) on this scope or the
// nearest started ancestor, so constructors can dial with a deadline. Before
// Start it returns context.Background().
func (s *Scope) Context() context.Context {
        if ctx, _ := s.runContext(); ctx != nil {
                return ctx
        }
        return context.Background()
}

// Stop winds the scope down in three phases. First it drains: OnDrain hooks
// run from the innermost scope outwards, in reverse build order, while every
// scope still resolves, so work already in flight can finish and still reach
// its dependencies. A service or child scope that phase brings into being is
// drained too, before anything is marked stopped. Then the scope is marked
// stopped and child scopes are stopped. Then OnStop hooks run in reverse
// build order (dependents first).
//
// A service is stopped only if it started, or if it declares no OnStart, in
// which case OnStop is a plain destructor. Every failure is reported.
//
// Stop is synchronous. It waits out whatever another goroutine is still
// running for a service it is tearing down -- a start step in flight, a drain
// hook another Stop began, a Worker hook being cancelled -- so when it returns,
// the teardown has happened and its failures are in the error. A teardown
// outlives the call only when ctx expires first: the missed deadline is
// reported here, and the release is finished once the outstanding step
// returns, on a goroutine of its own, reaching observers rather than this
// caller.
//
// Afterwards the scope and its descendants refuse to resolve anything, with
// ErrStopped; that includes a resolution that was already waiting when the
// scope stopped, so a closed service is never handed out. Stopping a child
// scope also detaches it from its parent, so per-request scopes are released
// once stopped.
//
// Stop is idempotent, and concurrent calls are safe: only the first tears the
// scope down, and the others wait for it and report its result, bounded by
// their own context. Two Stop calls that meet at one scope, as a child and
// its parent do, wait for each other phase by phase, so neither starts
// releasing what the other's hooks are still using.
//
// Because Stop waits, a hook must not call Stop on its own scope or an
// ancestor: it would be waiting for the step it is itself running. Stopping a
// sibling, or a scope below the hook's own, is allowed. A hook that passes on
// the context it was given gets an error saying so; one that passes a context
// of its own is not recognised, and waits until that context expires. Call
// Shutdown, which never blocks.
func (s *Scope) Stop(ctx context.Context) error {
        if h := hookOwner(ctx); h != nil && h.descendsFrom(s.state) {
                return fmt.Errorf("di: a lifecycle hook of scope %s called Stop on scope %s, which it is inside: call Shutdown instead", h.name, s.name)
        }
        if !s.stopOnce.claim(s.state, func() {
                if s.stopCtx == nil {
                        s.stopCtx = ctx // the first Stop owns it; a later call must not clobber it
                }
        }) {
                finished, err := s.stopOnce.wait(s.state, ctx)
                if !finished {
                        return fmt.Errorf("di: waiting for scope %s to stop: %w", s.name, ctx.Err())
                }
                return err
        }
        err := s.teardown(ctx)
        s.stopOnce.settle(s.state, err)
        return err
}

// teardown is the body of the first Stop.
func (s *Scope) teardown(ctx context.Context) error {
        errs := []error{s.drain(ctx)}

        s.mu.Lock()
        children := slices.Clone(s.children)
        started := s.started
        s.started = nil
        s.stopped.Store(true)
        s.mu.Unlock()

        for _, c := range children {
                errs = append(errs, (&Scope{state: c}).Stop(ctx))
        }
        errs = append(errs, stopAll(ctx, s.state, started))

        if p := s.parent; p != nil {
                p.mu.Lock()
                p.children = slices.DeleteFunc(p.children, func(c *state) bool { return c == s.state })
                p.mu.Unlock()
        }
        return errors.Join(errs...)
}

// drain runs the OnDrain hooks of this scope's subtree before anything is
// marked stopped, innermost first and in reverse build order, the order Stop
// uses. Nothing here changes an instance's phase.
//
// Only the first drain of a scope runs; a Stop that reaches the scope by
// another route waits for it. Without that wait, when a child and its parent
// are stopped at once, the second Stop would walk past a drain still in
// flight and start releasing what its hooks are using.
func (s *Scope) drain(ctx context.Context) error {
        if !s.drainOnce.claim(s.state, nil) {
                // The owner settles the phase with what this scope's own hooks
                // reported, and a Stop reports that whether it ran the hooks or
                // waited for someone else to.
                finished, err := s.drainOnce.wait(s.state, ctx)
                if !finished {
                        return fmt.Errorf("di: waiting for scope %s to drain: %w", s.name, ctx.Err())
                }
                return err
        }
        root := &drainScope{st: s.state, ours: true}
        r := drainRun{root: root, seen: map[*state]*drainScope{s.state: root}}
        err := r.sweepAll(ctx)
        s.drainOnce.settle(s.state, err) // this scope's phase is the last to end
        return err
}

// drainRun is the bookkeeping of one drain phase: the scopes it has reached,
// whether it owns each one's phase, and whether that phase has ended.
type drainRun struct {
        root *drainScope
        seen map[*state]*drainScope
}

type drainScope struct {
        st      *state
        ours    bool // this run claimed the phase; otherwise another Stop owns it
        settled bool // its phase has ended; for a descendant, when its own sweep does
}

// sweepAll is the body of the first drain. It sweeps the subtree until a pass
// finds no new work, because the scope still resolves during this phase: a
// hook finishing in-flight work may build a service or open a child scope,
// and those owe a drain too, before anything is marked stopped. ctx bounds
// the sweep as well as the hooks, so a hook that keeps building cannot hold
// the phase open for ever.
func (r *drainRun) sweepAll(ctx context.Context) error {
        var errs []error
        for {
                progress := false
                errs = append(errs, r.visit(ctx, r.root, &progress)...)
                if !progress || ctx.Err() != nil {
                        return errors.Join(errs...)
                }
        }
}

// visit sweeps one scope this run owns and everything below it, innermost
// first and in reverse creation order, the order Stop uses. Every owned scope
// is swept on every pass, not only the ones that appeared in it, because a
// hook may build into a scope already visited.
//
// It returns the errors that belong to *this* scope's Stop. A descendant's are
// settled into that descendant's phase instead, so its own Stop reports them,
// and they reach this caller through teardown, which stops its children and
// joins what their Stop returns; that is what keeps one failure to one place
// in the aggregate. Errors found in a descendant after its phase has ended
// have nowhere to be settled, so those bubble up here.
//
// A descendant's phase is claimed just before its subtree is swept and ended
// as soon as that sweep finishes, so while a hook runs the only unended phases
// this run holds are the scope being swept and its ancestors, which a hook may
// not Stop anyway. Claiming the whole subtree up front would deadlock a hook
// that stops a scope the walk has claimed but not yet reached, such as a
// server draining in one child and stopping a request scope in another.
//
// A scope another Stop already owns is waited for and then left alone,
// subtree included; that Stop's run drains it.
func (r *drainRun) visit(ctx context.Context, ds *drainScope, progress *bool) []error {
        var errs []error
        ds.st.mu.Lock()
        children := slices.Clone(ds.st.children)
        ds.st.mu.Unlock()
        for _, c := range slices.Backward(children) {
                cs := r.seen[c]
                if cs == nil {
                        *progress = true
                        cs = &drainScope{st: c}
                        r.seen[c] = cs
                        if c.drainOnce.claim(c, nil) {
                                cs.ours = true
                        } else if finished, _ := c.drainOnce.wait(c, ctx); !finished {
                                errs = append(errs, fmt.Errorf("di: waiting for scope %s to drain: %w", c.name, ctx.Err()))
                        }
                }
                if cs.ours {
                        errs = append(errs, r.visit(ctx, cs, progress)...)
                }
        }
        ds.st.mu.Lock()
        started := slices.Clone(ds.st.started)
        ds.st.mu.Unlock()
        for _, in := range slices.Backward(started) {
                ran, err := in.drainIfNeeded(ctx, ds.st)
                *progress = *progress || ran
                errs = append(errs, err)
        }
        if ds != r.root && !ds.settled {
                ds.st.drainOnce.settle(ds.st, errors.Join(errs...))
                ds.settled = true
                return nil // reported by this scope's own Stop, not by its parent's
        }
        return errs
}

func stopAll(ctx context.Context, owner *state, started []*instance) error {
        var errs []error
        for _, in := range slices.Backward(started) {
                errs = append(errs, in.stopIfNeeded(ctx, owner))
        }
        return errors.Join(errs...)
}

package di

// Resolution: the path a resolution walks, the two cycle detectors, the
// build step of an instance, and the entry points that resolve by type.

import (
        "errors"
        "fmt"
        "reflect"
        "slices"
        "sync"
        "sync/atomic"
        "time"
)

// abort is the panic a wiring failure unwinds with. It reaches the nearest
// Resolve, Start or Run and becomes that call's error; a top-level Get panics
// with the plain error instead.
type abort struct{ err error }

// resolver is one node of a resolution path: what is being resolved and the
// node that needed it. The path is a linked list, not a slice, because a
// constructor may resolve from several goroutines at once; a node is never
// mutated after it is made (except done), so branches share nothing and each
// carries the whole path for cycle detection and error messages.
//
// A node is identified by binding and holder, not by key: a group member and
// a plain registration of the same type are different bindings, and one
// Scoped binding is a different node in each scope that holds an instance of
// it.
type resolver struct {
        parent *resolver
        b      *binding // nil on the root node, which resolves nothing itself
        holder *state

        // done marks a node whose resolution has returned. The path stays whole
        // for error messages, but a finished node is no longer a dependency: a
        // constructor may keep the Scope it was handed and resolve through it
        // later, and that resolution must not meet its own finished frame and be
        // called a cycle. Written once by the resolution that owns the node, read
        // from any branch.
        done atomic.Bool
}

func (r *resolver) child(b *binding, holder *state) *resolver {
        return &resolver{parent: r, b: b, holder: holder}
}

// onPath reports whether this exact binding is still being resolved further
// up the path, which is a dependency cycle within one branch.
//
// The walk stops at the first finished node rather than skipping it. Only a
// constructor that kept its Scope can put one on a live path, and a
// resolution made through that Scope afterwards is a new branch: what is
// above the finished node may still be building, but not for it, so it has
// only to wait. The one shape this cannot tell apart without goroutine-local
// state deadlocks instead of being reported: a constructor that blocks on a
// resolution made through a finished descendant's Scope that leads back to
// itself.
func (r *resolver) onPath(b *binding, holder *state) bool {
        for n := r; n != nil; n = n.parent {
                if n.done.Load() {
                        return false
                }
                if n.b == b && n.holder == holder {
                        return true
                }
        }
        return false
}

func (r *resolver) path() string {
        if r == nil || r.b == nil {
                return ""
        }
        return " (needed by " + r.pathStr() + ")"
}

func (r *resolver) pathStr() string {
        var parts []string
        for n := r; n != nil; n = n.parent {
                if n.b != nil {
                        parts = append(parts, n.b.key.String())
                }
        }
        slices.Reverse(parts)
        return fmt.Sprint(parts)
}

// graph is one container's wait-for graph, with two kinds of edge: an
// instance points at the resolution building it (instance.builder), and a
// blocked resolution points at the instance it waits for (blockedFor). Its
// mutex is the innermost lock: a state's mutex may be held while taking it,
// never the reverse, so the graph can be read across scopes without ordering
// state mutexes against each other.
//
// New makes one graph per container and every scope under that root shares
// it. That is as far as a cycle can reach: a resolution follows the parent
// chain, so a wait can cross scopes, but nothing joins two containers.
type graph struct {
        mu         sync.Mutex
        blockedFor map[*resolver]*instance
}

// descends reports whether n is anc or was created below it. A branch blocks
// at a leaf of its path, several nodes below the one that claimed the build it
// is holding up, so both directions of the graph are matched against whole
// paths rather than single nodes.
//
// The walk stops at a node whose resolution has returned, for the same reason
// onPath does: nothing above a finished node is waiting for what is opened
// below it later.
func descends(n, anc *resolver) bool {
        for ; n != nil; n = n.parent {
                if n == anc {
                        return true
                }
                if n.done.Load() {
                        return false
                }
        }
        return false
}

// wait records that r is about to wait for in, unless that would close a
// wait-for cycle by reaching, through builds that are themselves blocked, a
// build this branch is responsible for finishing. Called with the holder's
// mutex held; the check and the new edge are one critical section, so two
// branches closing a cycle at once cannot both decide to wait.
func (r *resolver) wait(g *graph, in *instance) bool {
        g.mu.Lock()
        defer g.mu.Unlock()

        seen := map[*instance]bool{in: true}
        for stack := []*instance{in}; len(stack) > 0; {
                cur := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                builder := cur.builder
                if builder == nil {
                        continue // nobody is building it: whoever holds it will settle it
                }
                if descends(r, builder) {
                        return false // waiting on our own branch's work
                }
                for n, j := range g.blockedFor {
                        if descends(n, builder) && !seen[j] {
                                seen[j] = true
                                stack = append(stack, j)
                        }
                }
        }
        g.blockedFor[r] = in
        return true
}

func (r *resolver) unwait(g *graph) {
        g.mu.Lock()
        delete(g.blockedFor, r)
        g.mu.Unlock()
}

// as unwraps a stored value. A nil interface is a legitimate service, and a
// nil any cannot be asserted back to the interface type it was stored as, so
// it becomes T's zero value rather than a panic. Every hand-back of a stored
// value goes through here.
func as[T any](v any) T {
        if v == nil {
                var zero T
                return zero
        }
        return v.(T)
}

// lookup finds the binding registered for k in this scope or an ancestor,
// and the scope that owns it. A nil binding means nothing is registered for
// k anywhere in the chain.
func (s *Scope) lookup(k key) (*binding, *state) {
        for st := s.state; st != nil; st = st.parent {
                st.freeze()
                st.mu.Lock()
                b, ok := st.index[k]
                st.mu.Unlock()
                if ok {
                        return b, st
                }
        }
        return nil, nil
}

// inFlight reports whether this Scope is a live view of a resolution: it
// carries a path whose last node has not returned. A Scope kept past that
// point, by a constructor or by a Child made in one, is not in flight, and
// calls through it are top-level calls.
func (s *Scope) inFlight() bool { return s.r != nil && !s.r.done.Load() }

// enter returns a view carrying a resolver, starting a new resolution unless
// one is in flight.
func (s *Scope) enter() *Scope {
        if s.inFlight() {
                return s
        }
        return s.view(&resolver{})
}

// get resolves k. Outside a constructor the internal abort is converted into
// a panic carrying the plain error; inside one it unwinds to the enclosing
// Resolve/Start call.
func (s *Scope) get(k key) any {
        if !s.inFlight() {
                defer unwrapAbort()
                return s.enter().get(k)
        }
        b, owner := s.lookup(k)
        if b == nil {
                panic(abort{fmt.Errorf("di: %s: %w%s", k, ErrNotProvided, s.r.path())})
        }
        v := s.resolve(b, owner)
        s.markServed(owner, k)
        return v
}

// markServed records that k was served to this scope from owner, in every
// scope between the two. binding.used protects the owner; the scopes in
// between each handed out a value for k as well, and registering k in one of
// them afterwards would give the key two live values there.
func (s *Scope) markServed(owner *state, k key) {
        for st := s.state; st != nil && st != owner; st = st.parent {
                st.mu.Lock()
                if st.served == nil {
                        st.served = make(map[key]bool, 4)
                }
                st.served[k] = true
                st.mu.Unlock()
        }
}

// resolve produces b's value for the resolving scope s, honouring the
// binding's lifetime and starting the instance when the scope is running.
func (s *Scope) resolve(b *binding, owner *state) any {
        if s.isStopped() {
                panic(abort{fmt.Errorf("di: %s: %w%s", b.key, ErrStopped, s.r.path())})
        }
        // The holder owns the instance's lifecycle: a singleton lives in the
        // scope that registered the binding, a scoped one in the scope that
        // resolves it, so it can see that scope's values.
        holder := owner
        if b.scoped {
                holder = s.state
        }
        if s.r.onPath(b, holder) {
                panic(abort{fmt.Errorf("di: %w: %s -> %s", ErrCycle, s.r.pathStr(), b.key)})
        }
        if !b.used.Load() {
                // Hold the key against an override for as long as this resolution
                // runs, so a constructor cannot replace the registration it is
                // itself being built from. used is set before this is dropped, so
                // the two guards never leave a gap between them.
                b.resolving.Add(1)
                defer b.resolving.Add(-1)
        }
        sc := s.view(s.r.child(b, holder))
        // The node stops being a dependency when this resolution returns, however
        // it returns. See resolver.done.
        defer sc.r.done.Store(true)

        in := holder.instanceFor(b)
        v, err := sc.await(in, holder)
        if err != nil {
                panic(abort{err})
        }
        b.used.Store(true)
        // The edge belongs to the node that asked, and only a node with a binding
        // has an instance to record it on: a top-level Get starts a path whose
        // first node has none, and so does a Scope kept past its resolution. The
        // test is here rather than in dependOn so that the warm path pays a
        // pointer comparison instead of a call. A failed resolution records
        // nothing; the path it failed on is in the error.
        if s.r.b != nil {
                s.r.dependOn(in, holder)
        }
        return v
}

// dependOn records that the resolution at this node needed in, once per
// distinct dependency: a constructor that asks for the same service twice
// gets one edge. The scan is over one constructor's own dependencies and runs
// only while it is building.
func (r *resolver) dependOn(in *instance, holder *state) {
        r.holder.mu.Lock()
        defer r.holder.mu.Unlock()
        // resolve made the asking instance before running its constructor, so
        // the nil check is a guard on the recording only: a mistake here must
        // not break resolution.
        asker := r.holder.instanceAt(r.b)
        if asker == nil || slices.ContainsFunc(asker.deps, func(d dep) bool { return d.in == in }) {
                return
        }
        asker.deps = append(asker.deps, dep{in: in, holder: holder})
}

// await returns the instance's value: this branch builds it if it gets there
// first, and otherwise waits for whoever did. It waits for the start step as
// well, so a resolution of a running scope never hands out a service whose
// OnStart is still in flight. A wait that would close a cycle between two
// concurrent builds is reported as ErrCycle rather than deadlocking.
func (s *Scope) await(in *instance, holder *state) (any, error) {
        holder.mu.Lock()
        for in.ph == phaseNew || !in.settled || in.ph == phaseStarting {
                if in.ph == phaseNew {
                        in.claimBuild(holder, s.r)
                        holder.mu.Unlock()
                        s.materialise(in, holder)
                        holder.mu.Lock()
                        continue
                }
                // The phase says which step is outstanding and so which channel to
                // block on. Both are read in this critical section, and the owner
                // closes the channel under the same mutex, so it cannot be closed
                // between the choice and the block.
                var ready chan struct{}
                if in.settled {
                        ready = waitOn(&in.startingCh) // settled, so OnStart is outstanding
                } else {
                        ready = waitOn(&in.settledCh)
                }
                if !s.r.wait(holder.graph, in) {
                        holder.mu.Unlock()
                        return nil, fmt.Errorf("di: %w: %s -> %s", ErrCycle, s.r.parent.pathStr(), in.b.key)
                }
                holder.mu.Unlock()
                <-ready
                s.r.unwait(holder.graph)
                holder.mu.Lock()
        }
        value, err := in.value, in.err
        if err == nil && s.isStopped() {
                // The scope stopped while this branch was building or waiting;
                // resolve's check was before the wait. The check is on the resolving
                // scope, which covers the holder (always that scope or an ancestor):
                // a stopped scope must refuse the request whether or not the value is
                // still alive above it.
                value, err = nil, fmt.Errorf("di: %s: %w", in.b.key, ErrStopped)
        }
        holder.mu.Unlock()
        return value, err
}

// claimBuild takes the build step for this resolution. Called with the
// holder's mutex held.
func (in *instance) claimBuild(holder *state, r *resolver) {
        in.ph = phaseBuilding
        g := holder.graph
        g.mu.Lock()
        in.builder = r
        g.mu.Unlock()
}

// settle publishes the outcome of the build step and wakes every resolution
// waiting for this instance.
func (in *instance) settle(holder *state) {
        holder.mu.Lock()
        in.settled = true
        g := holder.graph
        g.mu.Lock()
        in.builder = nil
        g.mu.Unlock()
        wake(in.settledCh)
        holder.mu.Unlock()
}

// fail records a build failure, which is terminal for the instance.
func (in *instance) fail(holder *state, err error) {
        holder.mu.Lock()
        in.ph, in.err = phaseFailed, err
        holder.mu.Unlock()
}

// materialise builds an instance, once. A failure is recorded on the instance
// rather than unwound, so every later resolution reports it identically, and
// the instance is settled on the way out so waiters are released whatever
// happened.
func (s *Scope) materialise(in *instance, holder *state) {
        defer in.settle(holder)
        if err := s.construct(in, holder); err != nil {
                in.fail(holder, err)
                return
        }
        if !in.publish(holder) {
                return
        }
        in.startIfRunning(holder)
}

// construct runs the constructor, turning a panic or an abort from a nested
// resolution into an error, and reports the attempt to observers either way.
func (s *Scope) construct(in *instance, holder *state) (err error) {
        b := in.b
        t0 := time.Now()
        defer func() {
                if rec := recover(); rec != nil {
                        if a, ok := rec.(abort); ok {
                                err = fmt.Errorf("di: building %s (provided at %s): %w", b.key, b.where(), a.err)
                        } else {
                                err = fmt.Errorf("di: building %s (provided at %s): panic: %v", b.key, b.where(), rec)
                        }
                }
                holder.report(EventBuild, b, t0, err)
        }()
        in.value = b.build(&Scope{state: holder, r: s.r, module: b.module})
        return nil
}

// publish adds the instance to its owner's stop list so it will be torn
// down. If Stop ran while the constructor was in flight its snapshot did not
// include this instance, so undo it here and report ErrStopped instead.
func (in *instance) publish(owner *state) bool {
        owner.mu.Lock()
        stopped := owner.isStopped()
        in.ph = phaseBuilt
        if !stopped {
                owner.started = append(owner.started, in)
        }
        owner.mu.Unlock()
        if !stopped {
                return true
        }
        err := errors.Join(fmt.Errorf("di: %s: %w", in.b.key, ErrStopped), in.stopIfNeeded(owner.stopContext(), owner))
        owner.mu.Lock()
        in.err = err
        owner.mu.Unlock()
        return false
}

// startIfRunning runs the start step when the scope is already running.
// publish strictly precedes the read below, and Start sets running before it
// drains, so either this starts the instance or Start's drain finds it.
// startClaimed records its failure on the instance, so a resolution that
// waited for the step reports it too.
func (in *instance) startIfRunning(owner *state) {
        if sctx, running := owner.runContext(); running && in.claim(owner) {
                _ = in.startClaimed(sctx, owner)
        }
        stopped := owner.isStopped()
        owner.mu.Lock()
        if in.err == nil && stopped {
                // Stop ran while we were starting and waited for the step, so the
                // instance is torn down: do not hand it out.
                in.err = fmt.Errorf("di: %s: %w", in.b.key, ErrStopped)
        }
        owner.mu.Unlock()
}

// Get resolves T. Inside a constructor, failure unwinds to the enclosing
// Resolve/Start call and becomes an error; at top level it panics. In a
// goroutine a constructor started, use Resolve instead: that panic has no
// enclosing call to unwind to and would take the process down.
func (s *Scope) Get[T any]() T { return as[T](s.get(key{t: reflect.TypeFor[T]()})) }

// Maybe resolves T if it is provided anywhere in the scope chain.
func (s *Scope) Maybe[T any]() (T, bool) {
        if b, _ := s.lookup(key{t: reflect.TypeFor[T]()}); b == nil {
                var zero T
                return zero, false
        }
        return s.Get[T](), true
}

// All resolves the multi-binding group for T across the scope chain. Members
// are singletons (or Scoped if so marked) with the same lifecycle
// as any other binding.
func (s *Scope) All[T any]() []T {
        if !s.inFlight() {
                defer unwrapAbort()
                return s.enter().All[T]()
        }
        k := key{t: reflect.TypeFor[T]()}
        var out []T
        for st := s.state; st != nil; st = st.parent {
                st.freeze()
                st.mu.Lock()
                bs := slices.Clone(st.groups[k])
                st.mu.Unlock()
                for _, b := range bs {
                        out = append(out, as[T](s.resolve(b, st)))
                }
        }
        return out
}

// Must unwraps a (value, error) pair inside a constructor:
//
//        db := s.Must(sql.Open("postgres", dsn))
//
// A non-nil error aborts the constructor and surfaces from the enclosing
// Resolve, Start or Run. Outside a constructor it panics with the error.
func (s *Scope) Must[T any](v T, err error) T {
        if err == nil {
                return v
        }
        if s.inFlight() {
                panic(abort{err})
        }
        panic(err)
}

// Resolve resolves T, reporting a wiring failure as an error rather than a
// panic. It is the entry point for a goroutine a constructor started.
func (s *Scope) Resolve[T any]() (v T, err error) {
        defer recoverAbort(&err)
        return as[T](s.enter().get(key{t: reflect.TypeFor[T]()})), nil
}

// unwrapAbort turns an abort into a panic carrying the plain error, which is
// what a top-level Get or All reports. Deferred only by an entry point that
// is not already inside a resolution.
func unwrapAbort() {
        if rec := recover(); rec != nil {
                if a, ok := rec.(abort); ok {
                        panic(a.err)
                }
                panic(rec)
        }
}

// recoverAbort turns an abort into *err and re-panics anything else.
func recoverAbort(err *error) {
        if rec := recover(); rec != nil {
                if a, ok := rec.(abort); ok {
                        *err = a.err
                        return
                }
                panic(rec)
        }
}

package di

// Run and Shutdown: the main-function loop over Start and Stop, and the
// signal handling around it.

import (
        "context"
        "errors"
        "os"
        "os/signal"
        "syscall"
        "time"
)

// Shutdown asks a running Run to stop and records the cause it should return.
// It never blocks, may be called from any goroutine, and the first call wins.
// It propagates to ancestor scopes, so a service in a child scope can stop the
// application.
func (s *Scope) Shutdown(cause error) {
        first := false
        for st := s.state; st != nil; st = st.parent {
                st.shutdownOnce.Do(func() {
                        st.shutdownErr = cause
                        close(st.shutdownCh)
                        first = first || st == s.state
                })
        }
        if first {
                s.emit(Event{Kind: EventShutdown, Scope: s.name, Err: cause})
        }
}

// RunOption configures Run.
type RunOption func(*runConfig)

type runConfig struct{ stopTimeout time.Duration }

// exitSignals are what make Run exit: an interrupt or a termination request.
var exitSignals = []os.Signal{os.Interrupt, syscall.SIGTERM}

// StopTimeout bounds how long Stop may take once Run decides to exit.
// The default is 15 seconds.
func StopTimeout(d time.Duration) RunOption { return func(c *runConfig) { c.stopTimeout = d } }

// stopContext builds the context Run stops with: detached from the caller's,
// bounded by StopTimeout, and cancelled by a second signal so a hung hook
// cannot keep the process alive. A rollback from a failed Start gets the same
// context.
func (c runConfig) stopContext(ctx context.Context) (context.Context, func()) {
        stopCtx, cancelStop := context.WithTimeout(context.WithoutCancel(ctx), c.stopTimeout)
        forceCtx, cancelForce := signal.NotifyContext(stopCtx, exitSignals...)
        return forceCtx, func() { cancelForce(); cancelStop() }
}

// Run starts the scope and blocks until ctx is cancelled, a termination
// signal arrives, or Shutdown is called. It then stops the scope with a
// bounded context; a second signal during the stop cancels that context so
// a hung hook cannot keep the process alive. Run returns the Start error, the
// error passed to Shutdown, and any Stop errors, joined. A worker that died
// on its own is reported once, whether it reached Run as the cause or as a
// Stop error.
func (s *Scope) Run(ctx context.Context, opts ...RunOption) error {
        cfg := runConfig{stopTimeout: 15 * time.Second}
        for _, o := range opts {
                o(&cfg)
        }

        // Register before Start so a signal during a slow start is not lost.
        sigCtx, cancelSig := signal.NotifyContext(ctx, exitSignals...)
        defer cancelSig()

        if err := s.start(ctx, func() (context.Context, func()) { return cfg.stopContext(ctx) }); err != nil {
                // A failed Start rolls back through Stop, which runs the drain and
                // stop hooks, so a worker can die and publish its failure here
                // exactly as it can during an ordinary shutdown.
                return joinCause(err, s.publishedCause())
        }

        var cause error
        select {
        case <-sigCtx.Done():
        case <-s.shutdownCh:
                cause = s.shutdownErr
        }

        stopCtx, cancel := cfg.stopContext(ctx)
        defer cancel()

        stopErr := s.Stop(stopCtx)
        if cause == nil {
                // A worker that died during the stop published its failure through
                // Shutdown after the select above had woken for a signal or a
                // cancelled ctx. Read it again: the Stop that saw the failure may have
                // been a child's, called from a drain hook that handled the error
                // itself.
                cause = s.publishedCause()
        }
        return joinCause(stopErr, cause)
}

// publishedCause reports the failure Shutdown recorded, without waiting for
// one. Run reads it on both ways out, because a worker dies when it dies:
// during the stop that follows a signal, or during the rollback of a Start
// that never finished.
func (s *Scope) publishedCause() error {
        select {
        case <-s.shutdownCh:
                return s.shutdownErr
        default:
                return nil
        }
}

// joinCause adds a published cause to what Run is already returning, unless
// that failure is in there already: a worker's error reaches Run by two
// routes, as the cause and through the Stop that cancelled it, and it is one
// failure either way.
func joinCause(err, cause error) error {
        if cause == nil {
                return err
        }
        if errors.Is(err, cause) {
                return err // one failure, reached by both routes
        }
        return errors.Join(err, cause)
}

package di

// A scope's state: its registry, the freeze that commits registrations into
// it, and the readers that walk the parent chain. No two state mutexes are
// ever ordered against each other; a walk takes and releases each in turn.

import (
        "context"
        "fmt"
        "maps"
        "slices"
        "sync"
        "sync/atomic"
)

// state is a scope's registry and lifecycle bookkeeping. A Scope is a handle
// over it.
type state struct {
        name   string
        parent *state
        graph  *graph // the container's wait-for graph, shared with every other scope under the root

        mu        sync.Mutex
        pending   []*binding // registrations not yet indexed
        index     map[key]*binding
        groups    map[key][]*binding
        frozen    bool
        all       []*binding             // every binding, in registration order
        eager     []*binding             // derived by deriveEager: what Start builds
        started   []*instance            // build order; stopped in reverse
        scoped    map[*binding]*instance // per-scope instances of Scoped bindings
        served    map[key]bool           // keys this scope resolved from an outer scope; lazily made
        children  []*state
        observers []func(Event)

        stopped  atomic.Bool     // set by Stop or a failed Start; resolution then fails with ErrStopped
        stopCtx  context.Context // the context Stop was called with
        stopOnce once            // this scope's teardown; later Stop calls wait for it
        startCtx context.Context // set by Start; read by Context()
        running  bool            // set once Start reaches the hook phase; enables late OnStart

        // drainOnce is the scope-wide drain phase, once-with-wait like stopOnce:
        // a second Stop reaching this scope waits for the first drain instead of
        // running its own or skipping past it.
        drainOnce once

        shutdownOnce sync.Once
        shutdownCh   chan struct{}
        shutdownErr  error
}

// freeze commits the pending registrations. The batch is validated against a
// copy of the registry and committed only if it passes, so a rejected
// registration leaves the scope as it was and is rejected identically on
// every later attempt.
func (st *state) freeze() {
        st.mu.Lock()
        defer st.mu.Unlock()
        if len(st.pending) == 0 {
                return
        }

        index := maps.Clone(st.index)
        groups := maps.Clone(st.groups)
        all := slices.Clone(st.all)
        for _, b := range st.pending {
                // A wrapper is built where what it wraps is built, so it takes that
                // lifetime, read here rather than at registration because the
                // wrapped binding's own Scoped() may come later in the batch.
                if b.inner != nil && b.inner.scoped {
                        b.scoped = true
                }
                b.validate()
                if b.group {
                        groups[b.key] = append(slices.Clone(groups[b.key]), b)
                } else {
                        prev, ok := index[b.key]
                        act := "overridden"
                        if b.inner != nil {
                                act = "wrapped"
                        }
                        switch {
                        case ok && !b.override && b.inner == nil:
                                // A replacement is a thing a caller declares; a later
                                // registration winning silently would let one module reroute
                                // another's wiring.
                                panic(fmt.Sprintf("di: %s is provided at %s and again at %s: a second registration of a key must be marked Override() to replace the first",
                                        b.key, prev.where(), b.where()))
                        case !ok && b.override:
                                // Nearly always a fake for a service that was renamed, which
                                // would otherwise be a registration nobody resolves. A child
                                // shadows its parent without Override: that is a different
                                // registry, not a replacement.
                                panic(fmt.Sprintf("di: %s (provided at %s) is marked Override() but nothing in scope %s provides it; a child scope shadows its parent without Override",
                                        b.key, b.where(), st.name))
                        case ok && prev.used.Load():
                                // Replacing or wrapping a key that has served a value would
                                // leave two live instances of one service.
                                panic(fmt.Sprintf("di: %s (provided at %s) cannot be %s at %s: it has already been resolved",
                                        b.key, prev.where(), act, b.where()))
                        case ok && prev.resolving.Load() > 0:
                                // The same defect from the other side: the resolution in
                                // flight would return the old value while the replacement
                                // served everything it goes on to build.
                                panic(fmt.Sprintf("di: %s (provided at %s) cannot be %s at %s: it is being resolved",
                                        b.key, prev.where(), act, b.where()))
                        case ok && b.inner == nil && prev.wrappedBy.Load() != nil:
                                // A wrapper, here or in a descendant, composes over prev;
                                // replacing prev would leave it serving a value built from a
                                // registration nothing else can reach.
                                panic(fmt.Sprintf("di: %s (provided at %s) cannot be overridden at %s: it is wrapped at %s",
                                        b.key, prev.where(), b.where(), prev.wrappedBy.Load().where()))
                        }
                        if st.served[b.key] {
                                // This scope already handed the key down from an outer scope;
                                // shadowing it now would give the key two live values here.
                                panic(fmt.Sprintf("di: %s cannot be registered at %s: this scope has already resolved it from an outer scope",
                                        b.key, b.where()))
                        }
                        index[b.key] = b
                }
                all = append(all, b)
        }
        eager := deriveEager(all, index)

        st.index, st.groups, st.all, st.eager = index, groups, all, eager
        st.pending, st.frozen = nil, true
}

// deriveEager returns the ordered set of bindings Start builds, and is the
// one place that decides what Eager means. For every key with an Eager
// registration, the set holds the binding that serves that key, once, at the
// position of the first such registration. A group member is its own entry. A
// binding with a per-scope lifetime cannot honour eagerness and is rejected
// here, whether declared so directly or arriving through an override.
func deriveEager(all []*binding, index map[key]*binding) []*binding {
        var eager []*binding
        seen := make(map[*binding]bool, len(all))
        for _, b := range all {
                if !b.eager {
                        continue
                }
                w := b
                if !b.group {
                        w = index[b.key] // whichever registration owns the key by now
                }
                if seen[w] {
                        continue
                }
                if w.scoped {
                        // b itself is caught by validate, so w is an override here.
                        panic(fmt.Sprintf("di: %s is Eager (provided at %s), but the Scoped registration at %s owns the key: eagerness cannot transfer to a per-scope lifetime",
                                b.key, b.where(), w.where()))
                }
                seen[w] = true
                eager = append(eager, w)
        }
        return eager
}

// descendsFrom reports whether st is anc or a scope under it.
func (st *state) descendsFrom(anc *state) bool {
        for ; st != nil; st = st.parent {
                if st == anc {
                        return true
                }
        }
        return false
}

// isStopped reports whether this scope or an ancestor has stopped.
func (st *state) isStopped() bool {
        for ; st != nil; st = st.parent {
                if st.stopped.Load() {
                        return true
                }
        }
        return false
}

// runContext walks up the scope chain to the nearest state that Start was
// called on. running reports whether that Start has passed its hook phase,
// which is when bindings built later must start themselves; it is never true
// with a nil ctx, since start records the context before setting the flag.
func (st *state) runContext() (ctx context.Context, running bool) {
        for ; st != nil; st = st.parent {
                st.mu.Lock()
                ctx, running = st.startCtx, st.running
                st.mu.Unlock()
                if ctx != nil {
                        return ctx, running
                }
        }
        return nil, false
}

// everStarted reports whether Start was called on this scope or an ancestor.
func (st *state) everStarted() bool {
        ctx, _ := st.runContext()
        return ctx != nil
}

// stopContext returns the context Stop was called with, or a background one
// if the scope was stopped without recording it.
func (st *state) stopContext() context.Context {
        for ; st != nil; st = st.parent {
                st.mu.Lock()
                ctx := st.stopCtx
                st.mu.Unlock()
                if ctx != nil {
                        return ctx
                }
        }
        return context.Background()
}

// instanceFor picks the instance a resolution uses. A singleton has one for
// the whole binding; a Scoped binding has one per scope that holds it.
func (st *state) instanceFor(b *binding) *instance {
        if !b.scoped {
                return b.single
        }
        st.mu.Lock()
        defer st.mu.Unlock()
        in := st.scoped[b]
        if in == nil {
                in = &instance{b: b}
                st.scoped[b] = in
        }
        return in
}

// instanceAt is instanceFor without the making: the instance b already has
// in st, or nil. Called with st's mutex held, by the callers that must not
// bring one into being -- a recorded edge, and the inspection API.
func (st *state) instanceAt(b *binding) *instance {
        if !b.scoped {
                return b.single
        }
        return st.scoped[b]
}

package di

// Checking the declared graph. Only a constructor registered with Wire
// declares its dependencies; a Provide closure reveals them as it runs, and is
// reported here as unchecked. Nothing in this file resolves or builds: it
// reads bindings and their declared dependency lists after committing pending
// registrations, exactly as a lookup would.

import (
        "errors"
        "fmt"
        "reflect"
        "slices"
)

// Validation is what Validate found.
type Validation struct {
        // Errors are the failures the declared graph proves: a dependency nothing
        // provides, a cycle among Wire constructors, or a singleton that would
        // build a Scoped service in its own scope, where that service's
        // dependencies are not provided. Each wraps ErrNotProvided or ErrCycle.
        Errors []error
        // Owed lists the dependencies of Scoped bindings that this scope does not
        // provide. A Scoped service is built in the scope that resolves it, so
        // these are left to that scope: call Validate from there, or say what it
        // will hold with Provided stubs, and they are checked as errors instead.
        Owed []string
        // Unchecked lists the Provide constructors in the chain, whose
        // dependencies are known only once they run.
        Unchecked []string
}

// Err joins Errors, or is nil when the declared graph proves no failure.
func (v Validation) Err() error { return errors.Join(v.Errors...) }

// Validate checks the wiring visible from this scope without building
// anything. A singleton is checked against the scope that registered it,
// since that is where it is built. A Scoped binding is checked as if resolved
// from this scope, and what this scope does not provide for it is reported as
// Owed rather than as an error, because a descendant may:
//
//        v := app.Validate() // *http.Request is owed to a request scope
//
// The stubs say what such a descendant will hold, so that the check can be
// made from the application scope as that descendant would make it. With
// stubs the caller has described the resolving scope, and a dependency neither
// this scope nor the stubs provide is an error:
//
//        err := app.Validate(di.Provided[*http.Request]()).Err()
//
// Like Explain, Validate commits pending registrations the way a resolution
// would, so a configuration this scope would reject is reported by the same
// panic.
func (s *Scope) Validate(stubs ...Stub) Validation {
        var chain []*state
        for st := s.state; st != nil; st = st.parent {
                st.freeze()
                chain = append(chain, st)
        }
        v := &validator{seen: map[string]bool{}, done: map[visit]bool{}, stubs: map[key]bool{}, leaf: len(stubs) > 0}
        for _, st := range stubs {
                v.stubs[st.k] = true
        }
        // Ancestors first, so a report reads top-down like the scope tree.
        for _, st := range slices.Backward(chain) {
                for _, b := range st.live() {
                        switch {
                        case b.isValue:
                        case b.wants == nil:
                                v.out.Unchecked = append(v.out.Unchecked, fmt.Sprintf("%s (provided at %s)", b.key, b.where()))
                        case b.scoped:
                                v.walk(b, s.state, lenient, nil)
                        default:
                                v.walk(b, st, strict, nil)
                        }
                }
        }
        return v.out
}

// live returns the bindings that can serve a key from this scope, in
// registration order: what index and groups hold, without the registrations
// an Override replaced.
func (st *state) live() []*binding {
        st.mu.Lock()
        defer st.mu.Unlock()
        serving := map[*binding]bool{}
        // A wrapper serves the key and what it wraps is built underneath it,
        // so the whole chain is live; a chain an Override replaced is not.
        chain := func(b *binding) {
                for ; b != nil && !serving[b]; b = b.inner {
                        serving[b] = true
                }
        }
        for _, b := range st.index {
                chain(b)
        }
        for _, bs := range st.groups {
                for _, b := range bs {
                        chain(b)
                }
        }
        var out []*binding
        for _, b := range st.all {
                if serving[b] {
                        out = append(out, b)
                }
        }
        return out
}

type validator struct {
        out   Validation
        seen  map[string]bool // lines already reported, and cycles by their members
        done  map[visit]bool  // nodes fully explored, so a diamond is walked once
        stubs map[key]bool    // what the resolving scope will hold, by the caller's word
        leaf  bool            // stubs were given: the resolving scope is described, so nothing is owed
}

// Stub names a key the scope resolving a Scoped binding will provide, for
// Validate to take as given. Make one with Provided.
type Stub struct{ k key }

// Provided is a Stub for T: the resolving scope will hold a T, as a request
// scope holds an *http.Request.
func Provided[T any]() Stub { return Stub{k: key{t: reflect.TypeFor[T]()}} }

// A node of the declared graph is a binding in the scope it would be built
// in. The same binding is a different node under a different holder, since a
// Scoped binding built in one scope looks its dependencies up from there.
type visit struct {
        b      *binding
        holder *state
        mode   mode
}

// mode says what a missing dependency means on the current walk.
type mode uint8

const (
        strict     mode = iota // a singleton's own graph: missing is an error
        lenient                // a Scoped binding as this scope would resolve it: missing is owed to a descendant
        cyclesOnly             // a singleton reached from elsewhere: its own turn reports what it misses
)

// step is one node on a walk's path: a binding in the scope it would be
// built in. The holder is part of the identity, as it is on a resolution
// path at run time: a Scoped binding reached again under another holder is
// another instance, not a cycle, and a valid graph can visit one twice.
type step struct {
        b      *binding
        holder *state
}

// walk follows b's declared dependencies from holder, the scope b would be
// built in. A Scoped dependency is built in the same holder and walked in the
// same mode. A singleton dependency is built in its own scope, and its
// missing dependencies are that scope's report on its own turn, so it is
// walked only for cycles. Cycles are reported once, by their members.
func (v *validator) walk(b *binding, holder *state, md mode, path []step) {
        node := visit{b, holder, md}
        if v.done[node] {
                return
        }
        path = append(path, step{b, holder})
        for _, e := range declared(b, holder) {
                k, dep, owner := e.k, e.b, e.owner
                next := step{dep, owner}
                if dep != nil && dep.scoped {
                        next.holder = holder
                }
                switch {
                case dep == nil && md == lenient && v.stubs[k]:
                        // The resolving scope will hold it, the caller says, and a value
                        // declares nothing further. Only on the Scoped path: a singleton
                        // builds in its own scope, where that scope's values are not.
                case dep == nil:
                        v.missing(k, b, holder, md, path)
                case slices.Contains(path, next):
                        v.cycle(path[slices.Index(path, next):], k)
                case dep.wants == nil:
                        // A Provide closure or a Value: nothing declared to follow.
                case dep.scoped:
                        v.walk(dep, holder, md, path)
                default:
                        v.walk(dep, owner, cyclesOnly, path)
                }
        }
        v.done[node] = true
}

func (v *validator) missing(k key, b *binding, holder *state, md mode, path []step) {
        switch {
        case md == cyclesOnly:
        case md == lenient && v.leaf:
                v.err(fmt.Errorf("di: %s: %w by this scope or the stubs (needed by %s; scoped, provided at %s)", k, ErrNotProvided, keysOf(path), b.site))
        case md == lenient:
                v.owed(fmt.Sprintf("%s: needed by %s (scoped, provided at %s)", k, b.key, b.site))
        case len(path) > 1:
                v.err(fmt.Errorf("di: %s: %w in scope %s (needed by %s; %s is Scoped, so the singleton %s would build it there)",
                        k, ErrNotProvided, holder.name, keysOf(path), b.key, path[0].b.key))
        default:
                v.err(fmt.Errorf("di: %s: %w (needed by %s, provided at %s)", k, ErrNotProvided, keysOf(path), b.where()))
        }
}

// cycle reports the members once however many turns reach them, so a cycle
// of two is one line rather than one per participant.
func (v *validator) cycle(members []step, closing key) {
        names := make([]string, len(members))
        for i, m := range members {
                names[i] = m.b.key.String()
        }
        slices.Sort(names)
        id := "cycle " + fmt.Sprint(names)
        if !v.seen[id] {
                v.seen[id] = true
                v.err(fmt.Errorf("di: %w: %s -> %s", ErrCycle, keysOf(members), closing))
        }
}

func (v *validator) err(e error) {
        if !v.seen[e.Error()] {
                v.seen[e.Error()] = true
                v.out.Errors = append(v.out.Errors, e)
        }
}

func (v *validator) owed(line string) {
        if !v.seen[line] {
                v.seen[line] = true
                v.out.Owed = append(v.out.Owed, line)
        }
}

// edge is one declared dependency: the key, and the binding it resolves to
// from the holder with the scope that registered it, or nil.
type edge struct {
        k     key
        b     *binding
        owner *state
}

// declared lists what b declares, in build order: the registration a wrapper
// composes over, which is bound rather than looked up, and then the
// parameter types, each looked up from holder as the build would.
func declared(b *binding, holder *state) []edge {
        out := make([]edge, 0, len(b.wants)+1)
        if b.inner != nil {
                out = append(out, edge{b.key, b.inner, b.innerAt})
        }
        for _, k := range b.wants {
                dep, owner := (&Scope{state: holder}).lookup(k)
                out = append(out, edge{k, dep, owner})
        }
        return out
}

// keysOf renders a path the way a resolution error does.
func keysOf(path []step) string {
        keys := make([]string, len(path))
        for i, s := range path {
                keys[i] = s.b.key.String()
        }
        return fmt.Sprint(keys)
}