Dependency Injection algorithm idea

resolve.test.ts

import {resolve, Service, ResolvedService} from './resolve';

describe('resolve', () => {
    it('resolves a single service graph', () => {
        const input: Service[] = [
            {
                name: 'a',
                requires: []
            }
        ];
        const expected: ResolvedService[] = [
            {
                name: 'a',
                requires: []
            }
        ];
        expect(resolve('a', input)).toEqual(expected);
    });
    it('resolves service with one dependency', () => {
        const input: Service[] = [
            {
                name: 'a',
                requires: ['b']
            },
            {
                name: 'b',
                requires: []
            }
        ];
        const expected: ResolvedService[] = [
            {
                name: 'a',
                requires: ['b']
            },
            {
                name: 'b',
                requires: []
            }
        ];
        expect(resolve('a', input)).toEqual(expected);
    });
    it('resolves service with one interface dependency', () => {
        const input: Service[] = [
            {
                name: 'a',
                requires: ['interface-y']
            },
            {
                name: 'b',
                implements: ['interface-y'],
                requires: []
            }
        ];
        const expected: ResolvedService[] = [
            {
                name: 'a',
                requires: ['b']
            },
            {
                name: 'b',
                requires: []
            }
        ];
        expect(resolve('a', input)).toEqual(expected);
    });
    it('resolves service with one interface dependency, with two implementations', () => {
        const input: Service[] = [
            {
                name: 'a',
                requires: ['interface-y', 'c']
            },
            {
                name: 'b',
                implements: ['interface-y'],
                requires: []
            },
            {
                name: 'c',
                implements: ['interface-y'],
                requires: []
            }
        ];
        const expected: ResolvedService[] = [
            {
                name: 'a',
                requires: ['c', 'c']
            },
            {
                name: 'c',
                requires: []
            }
        ];
        expect(resolve('a', input)).toEqual(expected);
    });
    it('resolves interface implementation by picking the one with valid requirements', () => {
        const input: Service[] = [
            {
                name: 'a',
                requires: ['interface-y', 'd']
            },
            {
                name: 'b',
                implements: ['interface-y'],
                requires: ['d']
            },
            {
                name: 'c',
                implements: ['interface-y'],
                requires: ['e']
            },
            {
                name: 'd',
                requires: []
            },
            {
                name: 'e',
                requires: []
            }
        ];
        const expected: ResolvedService[] = [
            {
                name: 'a',
                requires: ['b', 'd']
            },
            {
                name: 'b',
                requires: ['d']
            },
            {
                name: 'd',
                requires: []
            }
        ];
        expect(resolve('a', input)).toEqual(expected);
    });
    it('resolves interface implementation by picking the one with deeply valid requirements', () => {
        const input: Service[] = [
            {
                name: 'a',
                requires: ['interface-y', 'g']
            },
            {
                name: 'b',
                implements: ['interface-y'],
                requires: ['d']
            },
            {
                name: 'c',
                implements: ['interface-y'],
                requires: ['e']
            },
            {
                name: 'd',
                requires: ['f']
            },
            {
                name: 'e',
                requires: ['g']
            },
            {
                name: 'f',
                requires: []
            },
            {
                name: 'g',
                requires: []
            }
        ];
        const expected: ResolvedService[] = [
            {
                name: 'a',
                requires: ['c', 'g']
            },
            {
                name: 'c',
                requires: ['e']
            },
            {
                name: 'e',
                requires: ['g']
            },
            {
                name: 'g',
                requires: []
            }
        ];
        expect(resolve('a', input)).toEqual(expected);
    });
});

resolve.ts

function assert(condition: boolean) {
    if (!condition) throw new Error();
}

type ServiceName = string;
type InterfaceName = string;

export interface Service {
    readonly name: ServiceName;
    readonly implements?: InterfaceName[];
    readonly requires: (ServiceName | InterfaceName)[];
}

export interface ResolvedService {
    readonly name: ServiceName;
    readonly requires: ServiceName[];
}

interface Edge {
    readonly service: Node;
    readonly dependency: Node;
}

class Node {
    status: 'required' | 'problem' | 'maybe' | 'possible' = 'maybe';

    constructor(
        private readonly g: Graph,
        readonly name: ServiceName | InterfaceName,
        readonly type: 'service' | 'interface'
    ) {}

    getDependencies(): Node[] {
        return this.g.getEdgesWhereServiceIs(this.name).map(edge => edge.dependency);
    }
    getDependants(): Node[] {
        return this.g.getEdgesWhereDependencyIs(this.name).map(edge => edge.service);
    }
    addDependency(n: Node): void {
        this.g.addEdge(this, n);
    }
}

class Graph {
    private readonly nodes = new Map<ServiceName | InterfaceName, Node>();
    private readonly edges: Edge[] = [];

    public getNode(name: ServiceName): Node {
        return this.nodes.get(name);
    }

    __debug() {
        console.log(Array.from(this.nodes.values()).map(s => ({name: s.name, status: s.status})));
    }

    public getOrCreateNode(name: ServiceName, type: 'service' | 'interface'): Node {
        let node = this.nodes.get(name);
        if (node) {
            if (node.type !== type) {
                throw new Error(`${name} can not be a service and an interface`);
            }
            return node;
        }
        node = new Node(this, name, type);
        this.nodes.set(name, node);
        return node;
    }

    public addEdge(from: Node, to: Node) {
        let edge = this.edges.find(
            e => e.service.name === from.name && e.dependency.name === to.name
        );
        if (!edge) {
            edge = {service: from, dependency: to};
            this.edges.push(edge);
        }
    }

    public getEdgesWhereServiceIs(service: ServiceName): Edge[] {
        return this.edges.filter(e => e.service.name === service);
    }

    public getEdgesWhereDependencyIs(dependency: ServiceName): Edge[] {
        return this.edges.filter(e => e.dependency.name === dependency);
    }

    public setServiceStatus(nameOrNode: ServiceName | Node, newStatus: Node['status']) {
        const node = typeof nameOrNode === 'string' ? this.nodes.get(nameOrNode) : nameOrNode;
        if (node.status === newStatus) {
            return;
        }
        node.status = newStatus;
        node.getDependants().forEach(dep => {
            this.updateService(dep);
        });
        node.getDependencies().forEach(dep => {
            this.updateService(dep);
        });
    }

    private updateService(node: Node) {
        let newStatus: Node['status'] = node.status;
        if (node.type === 'service') {
            if (node.status !== 'required') {
                if (node.getDependants().some(d => d.status === 'required')) {
                    newStatus = 'required';
                } else {
                    if (
                        node
                            .getDependencies()
                            .every(({status}) => status === 'required' || status === 'possible')
                    ) {
                        newStatus = 'possible';
                    }
                }
            }
        } else if (node.type === 'interface') {
            const possibleImplementations = node
                .getDependencies()
                .map(dep => dep.status)
                .filter(status => status === 'required' || status === 'possible');
            if (possibleImplementations.length === 1) {
                newStatus = 'possible';
            } else if (
                possibleImplementations.filter(status => status === 'required').length === 1
            ) {
                newStatus = 'possible';
            } else {
                newStatus = 'problem';
            }
        } else {
            assert(false);
        }
        if (node.status !== newStatus) {
            this.setServiceStatus(node, newStatus);
        }
    }
}

export function resolve(rootService: ServiceName, availableServices: Service[]): ResolvedService[] {
    // Create Maps for fast look-ups
    const interfaces = new Map<InterfaceName, ServiceName[]>();
    const services = new Map<ServiceName, Service>();

    for (const service of availableServices) {
        (service.implements || []).forEach(interfaceName => {
            const arr = interfaces.get(interfaceName) || [];
            arr.push(service.name);
            interfaces.set(interfaceName, arr);
        });
        services.set(service.name, service);
    }

    const g = new Graph();

    // Traverse services creating the graph structure
    const alreadyTraversed = new Set<ServiceName>();
    (function traverse(service: ServiceName) {
        if (alreadyTraversed.has(service)) return;
        alreadyTraversed.add(service);

        const serviceNode = g.getOrCreateNode(service, 'service');

        services.get(service).requires.forEach(serviceDependency => {
            if (services.has(serviceDependency)) {
                serviceNode.addDependency(g.getOrCreateNode(serviceDependency, 'service'));
                traverse(serviceDependency);
                return;
            }
            const possibleImplementations = interfaces.get(serviceDependency) || [];
            if (possibleImplementations.length === 0) {
                throw new Error('Unable to find any implementations of interface');
            }
            const interfaceNode = g.getOrCreateNode(serviceDependency, 'interface');
            serviceNode.addDependency(interfaceNode);

            possibleImplementations.forEach(possibleImpl => {
                interfaceNode.addDependency(g.getOrCreateNode(possibleImpl, 'service'));
                traverse(possibleImpl);
            });
        });
    })(rootService);

    g.setServiceStatus(rootService, 'required');

    // now should be able to walk graph and encounter no 'problems' if all is well

    const resolvedServices = new Map<ServiceName, ResolvedService>();

    (function traverse(serviceName: ServiceName): void {
        if (resolvedServices.has(serviceName)) {
            return;
        }
        const resolvedService: ResolvedService = {
            name: serviceName,
            requires: []
        };
        resolvedServices.set(serviceName, resolvedService);
        const serviceReqs = services.get(serviceName).requires;
        serviceReqs.forEach(depName => {
            const node = g.getNode(depName);
            if (node.type === 'service') {
                assert(node.status !== 'problem');
                resolvedService.requires.push(node.name);
                traverse(node.name);
            } else if (node.type === 'interface') {
                assert(node.status !== 'problem');
                const implementations = node
                    .getDependencies()
                    .filter(({status}) => status === 'required' || status === 'possible');
                assert(implementations.length > 0);
                if (implementations.length === 1) {
                    resolvedService.requires.push(implementations[0].name);
                    traverse(implementations[0].name);
                } else {
                    const solved = implementations.filter(n => n.status === 'required');
                    assert(solved.length === 1);
                    resolvedService.requires.push(solved[0].name);
                    traverse(solved[0].name);
                }
            } else {
                assert(false);
            }
        });
        assert(resolvedService.requires.length === serviceReqs.length);
    })(rootService);

    return Array.from(resolvedServices.values()).sort((a, b) => a.name.localeCompare(b.name));
}