Implement a Dependency Injection Container

package com.androidinterview.di;

// One entry in the registry. It knows how to build the thing, whether the
// result is kept, holds the instance once there is one, and carries its own
// lock.
//
// The lock is per binding on purpose. A single lock over the container would
// serialise every construction in the app behind whichever provider is
// slowest, and it would be held while arbitrary user code runs inside that
// provider, which is how a container deadlocks.
final class Binding<T> {

    private final Lifetime lifetime;
    private final Provider<T> provider;
    private final Object lock = new Object();

    private volatile T instance;

    Binding(Lifetime lifetime, Provider<T> provider) {
        this.lifetime = lifetime;
        this.provider = provider;
    }

    Lifetime lifetime() {
        return lifetime;
    }

    // Checked twice, and the field is volatile, which is the half people
    // forget. Without volatile a second thread can see a non null reference
    // to an object whose constructor has not finished running.
    T get(Resolver resolver) {
        if (lifetime == Lifetime.FACTORY) {
            return provider.provide(resolver);
        }
        T local = instance;
        if (local == null) {
            synchronized (lock) {
                local = instance;
                if (local == null) {
                    local = provider.provide(resolver);
                    instance = local;
                }
            }
        }
        return local;
    }

    // Called when the owning container is closed. A singleton holding a
    // socket or a thread pool gets told to let go of it. Best effort, because
    // one noisy dependency must not stop a screen scope being released.
    void release() {
        T local = instance;
        instance = null;
        if (local instanceof AutoCloseable closeable) {
            try {
                closeable.close();
            } catch (Exception ignored) {
                // Nothing useful to do here, and nothing to gain by stopping.
            }
        }
    }
}

package com.androidinterview.di;

final class Binding<T> {

    private final Lifetime lifetime;
    private final Provider<T> provider;
    private final Object lock = new Object();

    private volatile T instance;

    Binding(Lifetime lifetime, Provider<T> provider) {
        this.lifetime = lifetime;
        this.provider = provider;
    }

    Lifetime lifetime() {
        return lifetime;
    }

    T get(Resolver resolver) {
        if (lifetime == Lifetime.FACTORY) {
            return provider.provide(resolver);
        }
        T local = instance;
        if (local == null) {
            synchronized (lock) {
                local = instance;
                if (local == null) {
                    local = provider.provide(resolver);
                    instance = local;
                }
            }
        }
        return local;
    }

    void release() {
        T local = instance;
        instance = null;
        if (local instanceof AutoCloseable closeable) {
            try {
                closeable.close();
            } catch (Exception ignored) {
            }
        }
    }
}

package com.androidinterview.di;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

// The graph. A container holds its own bindings and a link to its parent, so
// a screen container can see the application container and the application
// container can never see the screen. That one direction is the whole scoping
// story. A long lived singleton has no way to reach a short lived object, so
// the classic leak, an application singleton still holding something owned by
// a screen that closed twenty minutes ago, is not a bug to be careful about.
// It is unreachable.
public final class Container implements Resolver, AutoCloseable {

    private final String name;
    private final Container parent;
    private final Map<Key, Binding<?>> bindings;

    private volatile boolean closed;

    Container(String name, Container parent, Map<Key, Binding<?>> bindings) {
        this.name = name;
        this.parent = parent;
        this.bindings = new LinkedHashMap<>(bindings);
    }

    // A child scope. It can see this container, and this container is never
    // told the child exists, which is the point.
    public ContainerBuilder child(String childName) {
        return new ContainerBuilder(childName, this);
    }

    @Override
    public <T> T get(Key key) {
        if (closed) {
            throw new DiException("container " + name + " is closed, so " + key
                + " cannot be resolved. Something outlived the scope that owns it.");
        }
        Container owner = ownerOf(key);
        if (owner == null) {
            throw new DiException.MissingBindingException(key, chain());
        }
        ResolutionStack.enter(key);
        try {
            @SuppressWarnings("unchecked")
            Binding<T> binding = (Binding<T>) owner.bindings.get(key);
            // The owner resolves, not the caller. A binding registered on the
            // application container is always built against the application
            // container, even when the request arrived through a screen, so
            // an application singleton cannot capture a screen object.
            return binding.get(owner);
        } finally {
            ResolutionStack.exit();
        }
    }

    // Resolve every binding once, so a wiring mistake fails at launch and not
    // on screen twelve on a customer's phone. Failures are collected and
    // reported together, because fixing six of these one build at a time is a
    // slow afternoon. The cost is that this warms every singleton, so on a
    // graph with something genuinely expensive in it, validate in debug only.
    public void validate() {
        List<String> failures = new ArrayList<>();
        for (Key key : bindings.keySet()) {
            try {
                get(key);
            } catch (DiException failure) {
                failures.add("  " + failure.getMessage());
            }
        }
        if (!failures.isEmpty()) {
            throw new DiException("container " + name + " has " + failures.size()
                + " broken binding(s):\n" + String.join("\n", failures));
        }
    }

    // Releasing a scope. Drop this container's singletons, close anything
    // closeable, refuse every later resolution. The parent is untouched.
    @Override
    public void close() {
        if (closed) {
            return;
        }
        closed = true;
        for (Binding<?> binding : bindings.values()) {
            binding.release();
        }
    }

    private Container ownerOf(Key key) {
        for (Container container = this; container != null; container = container.parent) {
            if (container.bindings.containsKey(key)) {
                return container;
            }
        }
        return null;
    }

    private String chain() {
        StringBuilder text = new StringBuilder();
        for (Container container = this; container != null; container = container.parent) {
            if (text.length() > 0) {
                text.append(" -> ");
            }
            text.append(container.name);
        }
        return text.toString();
    }
}

package com.androidinterview.di;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public final class Container implements Resolver, AutoCloseable {

    private final String name;
    private final Container parent;
    private final Map<Key, Binding<?>> bindings;

    private volatile boolean closed;

    Container(String name, Container parent, Map<Key, Binding<?>> bindings) {
        this.name = name;
        this.parent = parent;
        this.bindings = new LinkedHashMap<>(bindings);
    }

    public ContainerBuilder child(String childName) {
        return new ContainerBuilder(childName, this);
    }

    @Override
    public <T> T get(Key key) {
        if (closed) {
            throw new DiException("container " + name + " is closed, so " + key
                + " cannot be resolved. Something outlived the scope that owns it.");
        }
        Container owner = ownerOf(key);
        if (owner == null) {
            throw new DiException.MissingBindingException(key, chain());
        }
        ResolutionStack.enter(key);
        try {
            @SuppressWarnings("unchecked")
            Binding<T> binding = (Binding<T>) owner.bindings.get(key);
            return binding.get(owner);
        } finally {
            ResolutionStack.exit();
        }
    }

    public void validate() {
        List<String> failures = new ArrayList<>();
        for (Key key : bindings.keySet()) {
            try {
                get(key);
            } catch (DiException failure) {
                failures.add("  " + failure.getMessage());
            }
        }
        if (!failures.isEmpty()) {
            throw new DiException("container " + name + " has " + failures.size()
                + " broken binding(s):\n" + String.join("\n", failures));
        }
    }

    @Override
    public void close() {
        if (closed) {
            return;
        }
        closed = true;
        for (Binding<?> binding : bindings.values()) {
            binding.release();
        }
    }

    private Container ownerOf(Key key) {
        for (Container container = this; container != null; container = container.parent) {
            if (container.bindings.containsKey(key)) {
                return container;
            }
        }
        return null;
    }

    private String chain() {
        StringBuilder text = new StringBuilder();
        for (Container container = this; container != null; container = container.parent) {
            if (text.length() > 0) {
                text.append(" -> ");
            }
            text.append(container.name);
        }
        return text.toString();
    }
}

package com.androidinterview.di;

import java.util.LinkedHashMap;
import java.util.Map;

// The write side. Registration is explicit, it happens once, and it happens
// through an object that is thrown away when the graph goes live, so nothing
// can add a binding to a running container.
public final class ContainerBuilder {

    private final String name;
    private final Container parent;
    private final Map<Key, Binding<?>> bindings = new LinkedHashMap<>();

    public ContainerBuilder(String name) {
        this(name, null);
    }

    ContainerBuilder(String name, Container parent) {
        this.name = name;
        this.parent = parent;
    }

    public <T> ContainerBuilder singleton(Class<T> type, Provider<T> provider) {
        return bind(Key.of(type), Lifetime.SINGLETON, provider);
    }

    public <T> ContainerBuilder singleton(Class<T> type, String qualifier, Provider<T> provider) {
        return bind(Key.of(type, qualifier), Lifetime.SINGLETON, provider);
    }

    public <T> ContainerBuilder factory(Class<T> type, Provider<T> provider) {
        return bind(Key.of(type), Lifetime.FACTORY, provider);
    }

    // Something already built, usually a value from outside the graph.
    public <T> ContainerBuilder instance(Class<T> type, String qualifier, T value) {
        return bind(Key.of(type, qualifier), Lifetime.SINGLETON, resolver -> value);
    }

    // The test seam. Registering the same key twice by accident is a bug and
    // doing it on purpose is a test, so they are two method names rather than
    // one method with a flag. The lifetime comes from the binding being
    // replaced, so a fake cannot quietly turn a singleton into a factory.
    public <T> ContainerBuilder override(Class<T> type, Provider<T> provider) {
        Key key = Key.of(type);
        Binding<?> existing = bindings.get(key);
        if (existing == null) {
            throw new DiException("nothing to override for " + key + " in container " + name);
        }
        bindings.put(key, new Binding<>(existing.lifetime(), provider));
        return this;
    }

    public Container build() {
        return new Container(name, parent, bindings);
    }

    private <T> ContainerBuilder bind(Key key, Lifetime lifetime, Provider<T> provider) {
        if (bindings.containsKey(key)) {
            throw new DiException("duplicate binding for " + key + " in container " + name
                + ". Use override if that was deliberate.");
        }
        bindings.put(key, new Binding<>(lifetime, provider));
        return this;
    }
}

package com.androidinterview.di;

import java.util.LinkedHashMap;
import java.util.Map;

public final class ContainerBuilder {

    private final String name;
    private final Container parent;
    private final Map<Key, Binding<?>> bindings = new LinkedHashMap<>();

    public ContainerBuilder(String name) {
        this(name, null);
    }

    ContainerBuilder(String name, Container parent) {
        this.name = name;
        this.parent = parent;
    }

    public <T> ContainerBuilder singleton(Class<T> type, Provider<T> provider) {
        return bind(Key.of(type), Lifetime.SINGLETON, provider);
    }

    public <T> ContainerBuilder singleton(Class<T> type, String qualifier, Provider<T> provider) {
        return bind(Key.of(type, qualifier), Lifetime.SINGLETON, provider);
    }

    public <T> ContainerBuilder factory(Class<T> type, Provider<T> provider) {
        return bind(Key.of(type), Lifetime.FACTORY, provider);
    }

    public <T> ContainerBuilder instance(Class<T> type, String qualifier, T value) {
        return bind(Key.of(type, qualifier), Lifetime.SINGLETON, resolver -> value);
    }

    public <T> ContainerBuilder override(Class<T> type, Provider<T> provider) {
        Key key = Key.of(type);
        Binding<?> existing = bindings.get(key);
        if (existing == null) {
            throw new DiException("nothing to override for " + key + " in container " + name);
        }
        bindings.put(key, new Binding<>(existing.lifetime(), provider));
        return this;
    }

    public Container build() {
        return new Container(name, parent, bindings);
    }

    private <T> ContainerBuilder bind(Key key, Lifetime lifetime, Provider<T> provider) {
        if (bindings.containsKey(key)) {
            throw new DiException("duplicate binding for " + key + " in container " + name
                + ". Use override if that was deliberate.");
        }
        bindings.put(key, new Binding<>(lifetime, provider));
        return this;
    }
}

package com.androidinterview.di;

import java.util.List;
import java.util.stream.Collectors;

// One family, so a caller can catch every wiring failure with one clause.
public class DiException extends RuntimeException {

    public DiException(String message) {
        super(message);
    }

    // Reported at resolution, with the full type name and the chain of
    // container names that was searched, so the message contains the fix.
    public static final class MissingBindingException extends DiException {

        public MissingBindingException(Key key, String chain) {
            super("no binding for " + key + ". Searched " + chain);
        }
    }

    // Reported the moment a key is asked for while it is already being built.
    // The path is the cycle itself, from the repeated key back round to it.
    public static final class CycleException extends DiException {

        public CycleException(List<Key> path) {
            super("dependency cycle "
                + path.stream().map(Key::toString).collect(Collectors.joining(" -> ")));
        }
    }
}

package com.androidinterview.di;

import java.util.List;
import java.util.stream.Collectors;

public class DiException extends RuntimeException {

    public DiException(String message) {
        super(message);
    }

    public static final class MissingBindingException extends DiException {

        public MissingBindingException(Key key, String chain) {
            super("no binding for " + key + ". Searched " + chain);
        }
    }

    public static final class CycleException extends DiException {

        public CycleException(List<Key> path) {
            super("dependency cycle "
                + path.stream().map(Key::toString).collect(Collectors.joining(" -> ")));
        }
    }
}

package com.androidinterview.di;

import java.util.Objects;

// What a binding is looked up by. A type on its own is not enough, because a
// real graph has two Strings and two clients in it, so an optional qualifier
// rides along and the pair is the key.
//
// The type is held as a Class only to be compared and printed. Nothing here
// ever asks it for its constructors, which is the line between this container
// and a reflective one.
public record Key(Class<?> type, String qualifier) {

    public Key {
        Objects.requireNonNull(type, "type");
    }

    public static Key of(Class<?> type) {
        return new Key(type, null);
    }

    public static Key of(Class<?> type, String qualifier) {
        return new Key(type, qualifier);
    }

    // The full name, always. "No binding for String" is useless and "no
    // binding for java.lang.String named baseUrl" is a fix.
    @Override
    public String toString() {
        return qualifier == null ? type.getName() : type.getName() + " named " + qualifier;
    }
}

package com.androidinterview.di;

import java.util.Objects;

public record Key(Class<?> type, String qualifier) {

    public Key {
        Objects.requireNonNull(type, "type");
    }

    public static Key of(Class<?> type) {
        return new Key(type, null);
    }

    public static Key of(Class<?> type, String qualifier) {
        return new Key(type, qualifier);
    }

    @Override
    public String toString() {
        return qualifier == null ? type.getName() : type.getName() + " named " + qualifier;
    }
}

package com.androidinterview.di;

// A dependency resolved on first use rather than at construction. Two reasons
// to want one. A screen that declares ten dependencies and touches two of
// them on a normal visit pays for two. And a pair of classes that genuinely
// need each other stops being a cycle, because the second half is resolved
// after the first is already built and cached.
public final class Lazy<T> {

    private final Resolver resolver;
    private final Key key;
    private volatile T value;

    Lazy(Resolver resolver, Key key) {
        this.resolver = resolver;
        this.key = key;
    }

    public T get() {
        T local = value;
        if (local == null) {
            synchronized (this) {
                local = value;
                if (local == null) {
                    local = resolver.get(key);
                    value = local;
                }
            }
        }
        return local;
    }
}

package com.androidinterview.di;

public final class Lazy<T> {

    private final Resolver resolver;
    private final Key key;
    private volatile T value;

    Lazy(Resolver resolver, Key key) {
        this.resolver = resolver;
        this.key = key;
    }

    public T get() {
        T local = value;
        if (local == null) {
            synchronized (this) {
                local = value;
                if (local == null) {
                    local = resolver.get(key);
                    value = local;
                }
            }
        }
        return local;
    }
}

package com.androidinterview.di;

// Two lifetimes, and there is no third one worth having. Everything people
// call a scope is a container, not a lifetime.
public enum Lifetime {

    // Built once by the container that owns the binding, then cached there.
    SINGLETON,

    // Built again on every request. Nothing is cached, so nothing is retained
    // and a screen object cannot outlive the screen by accident.
    FACTORY
}

package com.androidinterview.di;

public enum Lifetime {

    SINGLETON,

    FACTORY
}

package com.androidinterview.di;

// How one type gets built. A lambda, not an annotation, and it is handed the
// resolver so that its own arguments come out of the graph. That makes
// constructor injection an ordinary constructor call,
//
//   b.singleton(UserApi.class, r -> new UserApi(r.get(HttpClient.class)))
//
// which is exactly what Dagger generates for you at compile time.
@FunctionalInterface
public interface Provider<T> {
    T provide(Resolver resolver);
}

package com.androidinterview.di;

@FunctionalInterface
public interface Provider<T> {
    T provide(Resolver resolver);
}

package com.androidinterview.di;

import java.util.ArrayList;
import java.util.List;

// Cycle detection, and it is short because the data structure is right. The
// keys currently being built, per thread, since two threads building two
// graphs are not a cycle and a shared list would report one.
//
// A key asked for while it is already on the stack can only be a cycle, and
// the stack from that key onwards is the cycle, so the message writes itself
// instead of saying stack overflow from a recursion two hundred frames deep.
final class ResolutionStack {

    private static final ThreadLocal<List<Key>> ACTIVE = ThreadLocal.withInitial(ArrayList::new);

    private ResolutionStack() {
    }

    static void enter(Key key) {
        List<Key> active = ACTIVE.get();
        int start = active.indexOf(key);
        if (start >= 0) {
            List<Key> cycle = new ArrayList<>(active.subList(start, active.size()));
            cycle.add(key);
            throw new DiException.CycleException(cycle);
        }
        active.add(key);
    }

    static void exit() {
        List<Key> active = ACTIVE.get();
        active.remove(active.size() - 1);
        if (active.isEmpty()) {
            // Never leave an empty list bolted to a pooled thread.
            ACTIVE.remove();
        }
    }
}

package com.androidinterview.di;

import java.util.ArrayList;
import java.util.List;

final class ResolutionStack {

    private static final ThreadLocal<List<Key>> ACTIVE = ThreadLocal.withInitial(ArrayList::new);

    private ResolutionStack() {
    }

    static void enter(Key key) {
        List<Key> active = ACTIVE.get();
        int start = active.indexOf(key);
        if (start >= 0) {
            List<Key> cycle = new ArrayList<>(active.subList(start, active.size()));
            cycle.add(key);
            throw new DiException.CycleException(cycle);
        }
        active.add(key);
    }

    static void exit() {
        List<Key> active = ACTIVE.get();
        active.remove(active.size() - 1);
        if (active.isEmpty()) {
            ACTIVE.remove();
        }
    }
}

package com.androidinterview.di;

// The read side of the graph, and the only thing a provider is ever handed.
// Keeping it apart from the builder means a provider cannot register a
// binding halfway through a resolution, which is how a graph turns into a
// puzzle that only works if you call things in the right order.
public interface Resolver {

    <T> T get(Key key);

    default <T> T get(Class<T> type) {
        return get(Key.of(type));
    }

    default <T> T get(Class<T> type, String qualifier) {
        return get(Key.of(type, qualifier));
    }

    // A handle to something that has not been built yet.
    default <T> Lazy<T> lazy(Class<T> type) {
        return new Lazy<>(this, Key.of(type));
    }
}

package com.androidinterview.di;

public interface Resolver {

    <T> T get(Key key);

    default <T> T get(Class<T> type) {
        return get(Key.of(type));
    }

    default <T> T get(Class<T> type, String qualifier) {
        return get(Key.of(type, qualifier));
    }

    default <T> Lazy<T> lazy(Class<T> type) {
        return new Lazy<>(this, Key.of(type));
    }
}

package com.androidinterview.di.sample;

import com.androidinterview.di.Container;
import com.androidinterview.di.ContainerBuilder;

// The wiring, and the only place in the codebase that knows how anything is
// built. Every provider is a lambda that pulls its own arguments out of the
// resolver, which is constructor injection written by hand.
public final class AppGraph {

    private AppGraph() {
    }

    // One reusable block of registrations, the equivalent of a Koin module.
    // It takes the builder so a test can register the same graph and then
    // replace one binding in it.
    public static void appModule(ContainerBuilder builder) {
        builder
            .singleton(HttpClient.class, r -> new HttpClient(r.get(String.class, "baseUrl")))
            .singleton(UserRepository.class, r -> new UserRepository(r.get(HttpClient.class)));
    }

    public static Container application(String baseUrl) {
        ContainerBuilder builder = new ContainerBuilder("application")
            .instance(String.class, "baseUrl", baseUrl);
        appModule(builder);
        Container application = builder.build();
        // Fail at launch, not on screen twelve.
        application.validate();
        return application;
    }

    // A screen scope. It can see the application container, the application
    // container cannot see it, and closing it releases only what it owns. The
    // presenter is a factory, so two visits never share one.
    public static Container profileScreen(Container application, String userId) {
        return application.child("profile-screen")
            .instance(String.class, "userId", userId)
            .factory(ProfilePresenter.class, r -> new ProfilePresenter(
                r.lazy(UserRepository.class), r.get(String.class, "userId")))
            .build();
    }

    // The test seam. The same module, one binding replaced, and everything
    // downstream of it is still the real class.
    public static Container underTest(HttpClient fake) {
        ContainerBuilder builder = new ContainerBuilder("test")
            .instance(String.class, "baseUrl", "http://fake");
        appModule(builder);
        builder.override(HttpClient.class, r -> fake);
        return builder.build();
    }
}

package com.androidinterview.di.sample;

import com.androidinterview.di.Container;
import com.androidinterview.di.ContainerBuilder;

public final class AppGraph {

    private AppGraph() {
    }

    public static void appModule(ContainerBuilder builder) {
        builder
            .singleton(HttpClient.class, r -> new HttpClient(r.get(String.class, "baseUrl")))
            .singleton(UserRepository.class, r -> new UserRepository(r.get(HttpClient.class)));
    }

    public static Container application(String baseUrl) {
        ContainerBuilder builder = new ContainerBuilder("application")
            .instance(String.class, "baseUrl", baseUrl);
        appModule(builder);
        Container application = builder.build();
        application.validate();
        return application;
    }

    public static Container profileScreen(Container application, String userId) {
        return application.child("profile-screen")
            .instance(String.class, "userId", userId)
            .factory(ProfilePresenter.class, r -> new ProfilePresenter(
                r.lazy(UserRepository.class), r.get(String.class, "userId")))
            .build();
    }

    public static Container underTest(HttpClient fake) {
        ContainerBuilder builder = new ContainerBuilder("test")
            .instance(String.class, "baseUrl", "http://fake");
        appModule(builder);
        builder.override(HttpClient.class, r -> fake);
        return builder.build();
    }
}

package com.androidinterview.di.sample;

// Stands in for the network stack. It is AutoCloseable so that releasing a
// scope has something real to release.
public final class HttpClient implements AutoCloseable {

    private final String baseUrl;
    private boolean open = true;

    public HttpClient(String baseUrl) {
        this.baseUrl = baseUrl;
    }

    public String fetch(String path) {
        if (!open) {
            throw new IllegalStateException("client is closed");
        }
        return baseUrl + path;
    }

    @Override
    public void close() {
        open = false;
    }
}

package com.androidinterview.di.sample;

public final class HttpClient implements AutoCloseable {

    private final String baseUrl;
    private boolean open = true;

    public HttpClient(String baseUrl) {
        this.baseUrl = baseUrl;
    }

    public String fetch(String path) {
        if (!open) {
            throw new IllegalStateException("client is closed");
        }
        return baseUrl + path;
    }

    @Override
    public void close() {
        open = false;
    }
}

package com.androidinterview.di.sample;

import com.androidinterview.di.Lazy;

// Screen scoped, and built with the id of the screen it belongs to, which is
// the reason a screen container exists at all. That id is a binding in the
// child container and nothing above it can see it. The repository arrives
// lazily, so a screen opened and closed without anyone looking at a profile
// builds nothing at all.
public final class ProfilePresenter {

    private final Lazy<UserRepository> repository;
    private final String userId;

    public ProfilePresenter(Lazy<UserRepository> repository, String userId) {
        this.repository = repository;
        this.userId = userId;
    }

    public String title() {
        return repository.get().load(userId);
    }
}

package com.androidinterview.di.sample;

import com.androidinterview.di.Lazy;

public final class ProfilePresenter {

    private final Lazy<UserRepository> repository;
    private final String userId;

    public ProfilePresenter(Lazy<UserRepository> repository, String userId) {
        this.repository = repository;
        this.userId = userId;
    }

    public String title() {
        return repository.get().load(userId);
    }
}

package com.androidinterview.di.sample;

public final class UserRepository {

    private final HttpClient client;

    public UserRepository(HttpClient client) {
        this.client = client;
    }

    public String load(String id) {
        return client.fetch("/users/" + id);
    }
}

package com.androidinterview.di.sample;

public final class UserRepository {

    private final HttpClient client;

    public UserRepository(HttpClient client) {
        this.client = client;
    }

    public String load(String id) {
        return client.fetch("/users/" + id);
    }
}

package com.androidinterview.di

// One entry in the registry. It knows how to build the thing, whether the
// result is kept, holds the instance once there is one, and carries its own
// lock.
//
// The lock is per binding on purpose. A single lock over the container would
// serialise every construction in the app behind whichever provider is
// slowest, and it would be held while arbitrary user code runs inside that
// provider, which is how a container deadlocks.
class Binding<T : Any> internal constructor(
    val lifetime: Lifetime,
    private val provider: Provider<T>,
) {
    private val lock = Any()

    @Volatile
    private var instance: T? = null

    fun get(resolver: Resolver): T {
        if (lifetime == Lifetime.FACTORY) return resolver.provider()
        instance?.let { return it }
        // Checked twice, and the field is volatile, which is the half people
        // forget. Without volatile a second thread can see a non null
        // reference to an object whose constructor has not finished running.
        return synchronized(lock) {
            instance ?: resolver.provider().also { instance = it }
        }
    }

    // Called when the owning container is closed. A singleton holding a socket
    // or a thread pool gets told to let go of it. Best effort, because one
    // noisy dependency must not stop a screen scope being released.
    internal fun release() {
        val held = instance
        instance = null
        (held as? AutoCloseable)?.let { runCatching { it.close() } }
    }
}

// Cycle detection, and it is short because the data structure is right. The
// keys currently being built, per thread, since two threads building two
// graphs are not a cycle and a shared list would report one.
//
// A key asked for while it is already on the stack can only be a cycle, and
// the stack from that key onwards is the cycle, so the message writes itself
// instead of saying stack overflow from a recursion two hundred frames deep.
internal object ResolutionStack {

    private val active = ThreadLocal.withInitial { ArrayDeque<Key>() }

    fun <T> guard(key: Key, resolve: () -> T): T {
        val stack = active.get()
        val start = stack.indexOf(key)
        if (start >= 0) throw DiException.Cycle(stack.drop(start) + key)
        stack.addLast(key)
        try {
            return resolve()
        } finally {
            stack.removeLast()
            // Never leave an empty deque bolted to a pooled thread.
            if (stack.isEmpty()) active.remove()
        }
    }
}

package com.androidinterview.di

class Binding<T : Any> internal constructor(
    val lifetime: Lifetime,
    private val provider: Provider<T>,
) {
    private val lock = Any()

    @Volatile
    private var instance: T? = null

    fun get(resolver: Resolver): T {
        if (lifetime == Lifetime.FACTORY) return resolver.provider()
        instance?.let { return it }
        return synchronized(lock) {
            instance ?: resolver.provider().also { instance = it }
        }
    }

    internal fun release() {
        val held = instance
        instance = null
        (held as? AutoCloseable)?.let { runCatching { it.close() } }
    }
}

internal object ResolutionStack {

    private val active = ThreadLocal.withInitial { ArrayDeque<Key>() }

    fun <T> guard(key: Key, resolve: () -> T): T {
        val stack = active.get()
        val start = stack.indexOf(key)
        if (start >= 0) throw DiException.Cycle(stack.drop(start) + key)
        stack.addLast(key)
        try {
            return resolve()
        } finally {
            stack.removeLast()
            if (stack.isEmpty()) active.remove()
        }
    }
}

package com.androidinterview.di

// The graph. A container holds its own bindings and a link to its parent, so
// a screen container can see the application container and the application
// container can never see the screen. That one direction is the whole scoping
// story. A long lived singleton has no way to reach a short lived object, so
// the classic leak, an application singleton still holding something owned by
// a screen that closed twenty minutes ago, is not a bug to be careful about.
// It is unreachable.
class Container internal constructor(
    private val name: String,
    private val parent: Container?,
    private val bindings: Map<Key, Binding<*>>,
) : Resolver, AutoCloseable {

    @Volatile
    private var closed = false

    override fun <T : Any> get(key: Key): T {
        if (closed) {
            throw DiException("container $name is closed, so $key cannot be resolved. " +
                "Something outlived the scope that owns it.")
        }
        val owner = ownerOf(key) ?: throw DiException.MissingBinding(key, chain())
        return ResolutionStack.guard(key) {
            @Suppress("UNCHECKED_CAST")
            val binding = owner.bindings.getValue(key) as Binding<T>
            // The owner resolves, not the caller. A binding registered on the
            // application container is always built against the application
            // container, even when the request arrived through a screen, so an
            // application singleton cannot capture a screen object.
            binding.get(owner)
        }
    }

    // A child scope. It can see this container, and this container is never
    // told the child exists, which is the point.
    fun child(name: String, block: ContainerBuilder.() -> Unit): Container =
        container(name, this, block)

    // Resolve every binding once, so a wiring mistake fails at launch and not
    // on screen twelve on a customer's phone. Failures are collected and
    // reported together, because fixing six of these one build at a time is a
    // slow afternoon. The cost is that this warms every singleton, so on a
    // graph with something genuinely expensive in it, validate in debug only.
    fun validate() {
        val failures = bindings.keys.mapNotNull { key ->
            try {
                get<Any>(key)
                null
            } catch (failure: DiException) {
                "  ${failure.message}"
            }
        }
        if (failures.isNotEmpty()) {
            throw DiException("container $name has ${failures.size} broken binding(s):\n" +
                failures.joinToString("\n"))
        }
    }

    // Releasing a scope. Drop this container's singletons, close anything
    // closeable, refuse every later resolution. The parent is untouched.
    override fun close() {
        if (closed) return
        closed = true
        bindings.values.forEach { it.release() }
    }

    private fun ownerOf(key: Key): Container? =
        generateSequence(this) { it.parent }.firstOrNull { key in it.bindings }

    private fun chain(): String =
        generateSequence(this) { it.parent }.joinToString(" -> ") { it.name }
}

// The write side. Registration is explicit, it happens once, and it happens
// inside a lambda whose receiver is thrown away when the graph goes live, so
// nothing can add a binding to a running container.
class ContainerBuilder internal constructor(private val name: String) {

    internal val bindings = LinkedHashMap<Key, Binding<*>>()

    inline fun <reified T : Any> single(qualifier: String? = null, noinline provider: Provider<T>) {
        bind(Key(T::class, qualifier), Lifetime.SINGLETON, provider)
    }

    inline fun <reified T : Any> factory(qualifier: String? = null, noinline provider: Provider<T>) {
        bind(Key(T::class, qualifier), Lifetime.FACTORY, provider)
    }

    // Something already built, usually a value from outside the graph.
    inline fun <reified T : Any> instance(value: T, qualifier: String? = null) {
        bind(Key(T::class, qualifier), Lifetime.SINGLETON) { value }
    }

    // The test seam. Registering the same key twice by accident is a bug and
    // doing it on purpose is a test, so they are two words rather than one
    // word with a flag. The lifetime comes from the binding being replaced, so
    // a fake cannot quietly turn a singleton into a factory.
    inline fun <reified T : Any> override(qualifier: String? = null, noinline provider: Provider<T>) {
        replace(Key(T::class, qualifier), provider)
    }

    fun <T : Any> bind(key: Key, lifetime: Lifetime, provider: Provider<T>) {
        if (key in bindings) {
            throw DiException("duplicate binding for $key in container $name. " +
                "Use override if that was deliberate.")
        }
        bindings[key] = Binding(lifetime, provider)
    }

    fun <T : Any> replace(key: Key, provider: Provider<T>) {
        val existing = bindings[key]
            ?: throw DiException("nothing to override for $key in container $name")
        bindings[key] = Binding(existing.lifetime, provider)
    }
}

fun container(
    name: String,
    parent: Container? = null,
    block: ContainerBuilder.() -> Unit,
): Container = Container(name, parent, ContainerBuilder(name).apply(block).bindings)

package com.androidinterview.di

class Container internal constructor(
    private val name: String,
    private val parent: Container?,
    private val bindings: Map<Key, Binding<*>>,
) : Resolver, AutoCloseable {

    @Volatile
    private var closed = false

    override fun <T : Any> get(key: Key): T {
        if (closed) {
            throw DiException("container $name is closed, so $key cannot be resolved. " +
                "Something outlived the scope that owns it.")
        }
        val owner = ownerOf(key) ?: throw DiException.MissingBinding(key, chain())
        return ResolutionStack.guard(key) {
            @Suppress("UNCHECKED_CAST")
            val binding = owner.bindings.getValue(key) as Binding<T>
            binding.get(owner)
        }
    }

    fun child(name: String, block: ContainerBuilder.() -> Unit): Container =
        container(name, this, block)

    fun validate() {
        val failures = bindings.keys.mapNotNull { key ->
            try {
                get<Any>(key)
                null
            } catch (failure: DiException) {
                "  ${failure.message}"
            }
        }
        if (failures.isNotEmpty()) {
            throw DiException("container $name has ${failures.size} broken binding(s):\n" +
                failures.joinToString("\n"))
        }
    }

    override fun close() {
        if (closed) return
        closed = true
        bindings.values.forEach { it.release() }
    }

    private fun ownerOf(key: Key): Container? =
        generateSequence(this) { it.parent }.firstOrNull { key in it.bindings }

    private fun chain(): String =
        generateSequence(this) { it.parent }.joinToString(" -> ") { it.name }
}

class ContainerBuilder internal constructor(private val name: String) {

    internal val bindings = LinkedHashMap<Key, Binding<*>>()

    inline fun <reified T : Any> single(qualifier: String? = null, noinline provider: Provider<T>) {
        bind(Key(T::class, qualifier), Lifetime.SINGLETON, provider)
    }

    inline fun <reified T : Any> factory(qualifier: String? = null, noinline provider: Provider<T>) {
        bind(Key(T::class, qualifier), Lifetime.FACTORY, provider)
    }

    inline fun <reified T : Any> instance(value: T, qualifier: String? = null) {
        bind(Key(T::class, qualifier), Lifetime.SINGLETON) { value }
    }

    inline fun <reified T : Any> override(qualifier: String? = null, noinline provider: Provider<T>) {
        replace(Key(T::class, qualifier), provider)
    }

    fun <T : Any> bind(key: Key, lifetime: Lifetime, provider: Provider<T>) {
        if (key in bindings) {
            throw DiException("duplicate binding for $key in container $name. " +
                "Use override if that was deliberate.")
        }
        bindings[key] = Binding(lifetime, provider)
    }

    fun <T : Any> replace(key: Key, provider: Provider<T>) {
        val existing = bindings[key]
            ?: throw DiException("nothing to override for $key in container $name")
        bindings[key] = Binding(existing.lifetime, provider)
    }
}

fun container(
    name: String,
    parent: Container? = null,
    block: ContainerBuilder.() -> Unit,
): Container = Container(name, parent, ContainerBuilder(name).apply(block).bindings)

package com.androidinterview.di

import kotlin.reflect.KClass

// What a binding is looked up by. A type on its own is not enough, because a
// real graph has two Strings and two clients in it, so an optional qualifier
// rides along and the pair is the key.
//
// The KClass is only ever compared and printed. Nothing here asks it for its
// constructors, which is the line between this container and a reflective one.
data class Key(val type: KClass<*>, val qualifier: String? = null) {

    // The full name, always. "No binding for String" is useless and "no
    // binding for kotlin.String named baseUrl" is a fix.
    override fun toString(): String {
        val name = type.qualifiedName ?: type.toString()
        return if (qualifier == null) name else "$name named $qualifier"
    }
}

// Two lifetimes, and there is no third one worth having. Everything people
// call a scope is a container, not a lifetime.
enum class Lifetime {
    // Built once by the container that owns the binding, then cached there.
    SINGLETON,

    // Built again on every request, so nothing is cached and nothing retained.
    FACTORY,
}

// One family, so a caller can catch every wiring failure with one clause.
open class DiException(message: String) : RuntimeException(message) {

    // Reported at resolution, with the full type name and the chain of
    // container names that was searched, so the message contains the fix.
    class MissingBinding(key: Key, chain: String) :
        DiException("no binding for $key. Searched $chain")

    // Reported the moment a key is asked for while it is already being built.
    // The path is the cycle itself, from the repeated key back round to it.
    class Cycle(path: List<Key>) :
        DiException("dependency cycle ${path.joinToString(" -> ")}")
}

package com.androidinterview.di

import kotlin.reflect.KClass

data class Key(val type: KClass<*>, val qualifier: String? = null) {

    override fun toString(): String {
        val name = type.qualifiedName ?: type.toString()
        return if (qualifier == null) name else "$name named $qualifier"
    }
}

enum class Lifetime {
    SINGLETON,

    FACTORY,
}

open class DiException(message: String) : RuntimeException(message) {

    class MissingBinding(key: Key, chain: String) :
        DiException("no binding for $key. Searched $chain")

    class Cycle(path: List<Key>) :
        DiException("dependency cycle ${path.joinToString(" -> ")}")
}

package com.androidinterview.di

// How one type gets built. A function with the resolver as its receiver, so a
// provider body reads as an ordinary constructor call whose arguments come
// out of the graph, `UserRepository(get())`. No interface, no annotation, no
// annotation processor.
typealias Provider<T> = Resolver.() -> T

// The read side of the graph, and the only thing a provider is ever handed.
// Keeping it apart from the registry means a provider cannot register a
// binding halfway through a resolution.
interface Resolver {
    fun <T : Any> get(key: Key): T
}

// The API a caller actually uses. Reified, so the type is written once and
// there is no class literal anywhere in the wiring.
inline fun <reified T : Any> Resolver.get(qualifier: String? = null): T =
    get(Key(T::class, qualifier))

// Lazy resolution, and in Kotlin it is the standard library's Lazy rather
// than a class of our own, so it works as a property delegate and its
// double checked locking is already written and already correct.
//
//   private val repository: UserRepository by resolver.inject()
//
// Two reasons to want it. A screen that declares ten dependencies and touches
// two of them pays for two. And a pair of classes that genuinely need each
// other stops being a cycle, because the second half resolves after the first
// is already built and cached.
inline fun <reified T : Any> Resolver.inject(qualifier: String? = null): Lazy<T> =
    lazy { get<T>(qualifier) }

package com.androidinterview.di

typealias Provider<T> = Resolver.() -> T

interface Resolver {
    fun <T : Any> get(key: Key): T
}

inline fun <reified T : Any> Resolver.get(qualifier: String? = null): T =
    get(Key(T::class, qualifier))

inline fun <reified T : Any> Resolver.inject(qualifier: String? = null): Lazy<T> =
    lazy { get<T>(qualifier) }

package com.androidinterview.di.sample

import com.androidinterview.di.Container
import com.androidinterview.di.ContainerBuilder
import com.androidinterview.di.container
import com.androidinterview.di.get
import com.androidinterview.di.inject

// Stands in for the network stack. It is AutoCloseable so that releasing a
// scope has something real to release.
class HttpClient(private val baseUrl: String) : AutoCloseable {

    private var open = true

    fun fetch(path: String): String {
        check(open) { "client is closed" }
        return baseUrl + path
    }

    override fun close() {
        open = false
    }
}

class UserRepository(private val client: HttpClient) {
    fun load(id: String): String = client.fetch("/users/$id")
}

// Screen scoped, and built with the id of the screen it belongs to, which is
// the reason a screen container exists at all. That id is a binding in the
// child container and nothing above it can see it. The repository arrives as
// a Lazy and is used as a delegate, so a screen opened and closed without
// anyone looking at a profile builds nothing at all.
class ProfilePresenter(lazyRepository: Lazy<UserRepository>, private val userId: String) {

    private val repository by lazyRepository

    fun title(): String = repository.load(userId)
}

// One reusable block of registrations, the equivalent of a Koin module. It is
// an extension on the builder, so a test can register the same graph and then
// replace one binding in it.
fun ContainerBuilder.appModule() {
    single { HttpClient(get(qualifier = "baseUrl")) }
    single { UserRepository(get()) }
}

// The wiring, and the only place in the codebase that knows how anything is
// built. Every provider is a lambda that pulls its own arguments out of the
// graph, which is constructor injection written by hand.
object AppGraph {

    fun application(baseUrl: String): Container = container("application") {
        instance(baseUrl, qualifier = "baseUrl")
        appModule()
    }.also {
        // Fail at launch, not on screen twelve.
        it.validate()
    }

    // A screen scope. It can see the application container, the application
    // container cannot see it, and closing it releases only what it owns. The
    // presenter is a factory, so two visits never share one.
    fun profileScreen(application: Container, userId: String): Container =
        application.child("profile-screen") {
            instance(userId, qualifier = "userId")
            factory { ProfilePresenter(inject(), get(qualifier = "userId")) }
        }

    // The test seam. The same module, one binding replaced, and everything
    // downstream of it is still the real class.
    fun underTest(fake: HttpClient): Container = container("test") {
        instance("http://fake", qualifier = "baseUrl")
        appModule()
        override<HttpClient> { fake }
    }
}

package com.androidinterview.di.sample

import com.androidinterview.di.Container
import com.androidinterview.di.ContainerBuilder
import com.androidinterview.di.container
import com.androidinterview.di.get
import com.androidinterview.di.inject

class HttpClient(private val baseUrl: String) : AutoCloseable {

    private var open = true

    fun fetch(path: String): String {
        check(open) { "client is closed" }
        return baseUrl + path
    }

    override fun close() {
        open = false
    }
}

class UserRepository(private val client: HttpClient) {
    fun load(id: String): String = client.fetch("/users/$id")
}

class ProfilePresenter(lazyRepository: Lazy<UserRepository>, private val userId: String) {

    private val repository by lazyRepository

    fun title(): String = repository.load(userId)
}

fun ContainerBuilder.appModule() {
    single { HttpClient(get(qualifier = "baseUrl")) }
    single { UserRepository(get()) }
}

object AppGraph {

    fun application(baseUrl: String): Container = container("application") {
        instance(baseUrl, qualifier = "baseUrl")
        appModule()
    }.also {
        it.validate()
    }

    fun profileScreen(application: Container, userId: String): Container =
        application.child("profile-screen") {
            instance(userId, qualifier = "userId")
            factory { ProfilePresenter(inject(), get(qualifier = "userId")) }
        }

    fun underTest(fake: HttpClient): Container = container("test") {
        instance("http://fake", qualifier = "baseUrl")
        appModule()
        override<HttpClient> { fake }
    }
}