Deep End

Incrementally merges and linearizes ordered dependency trees.

The deepend module exports a Dependency constructor. The constructor in turn accepts an array of ordered dependencies and an optional payload value. The order of the dependencies is significant and preserved in all subsequent dependees, but subsequent dependees may interleave aditional dependencies. This produces a strong foundation for a variety of mixin patterns.

The dependency instance carries the payload as value, shallow dependencies, and an incrementally computed deepDependencies array.

var A = Dependency([], 'A');
assert.strictEqual(A.value, 'A');
assert.deepEqual(A.dependencies, []);
assert.deepEqual(A.deepDependencies, [A]);

The deep dependencies are defined as the dependency itself, followed by its transitive dependencies ordered such that the relative order of all individual dependency lists are preserved. The formal term for this kind of ordering is "monotonically increasing dependence", meaning that each successive dependency in the deep dependencies is at least as dependent as the previous, and only increasing otherwise.

var A = Dependency([], 'A');
var Z = Dependency([], 'Z');
var AZ = Dependency([A, Z], 'AZ');
assert.deepEquals(AZ.deepDependencies, [AZ, A, Z]);

Using this technique, we can introduce a dependency that must interpolate a dependency between the dependencies of one of its children. In this case, we introduce an "M" dependency between "A" and "Z". Since "M" depends upon "Z", it must be shifted into a position that preceds it.

var M = Dependency([Z]);
var AMZ = Dependency([AZ, M]);
expect(AMZ.deepDependencies).toEqual([AMZ, AZ, A, M, Z]);

If you attempt to construct a dependency with its own dependencies ordered in such a way as that a monotonic order is not possible, the constructor will throw an "Can't construct Dependency because Ambiguous dependency order" error, which will have an ambiguousDependencyOrder flag set.

var A = Dependency([], 'A');
var Z = Dependency([], 'Z');
var AZ = Dependency([A, Z], 'AZ');
var ZA = Dependency([Z, A], 'ZA');
 
assert.throws(function () {
    new Dependency([AZ, ZA], '?!');
});

Dependencies use the C3 superclass linearization algorithm, best known because it is used for determining the method resolution order in Python classes starting with version 2.3. The algorithm is more broadly applicable for a variety of problems. The motivation for creating this library was to create a system for linearizing adapters or decorators in a way that allows individual adapters to express a dependency order on other adapters.

Installation

npm install deepend

Contributors

• Kris Kowal, @kriskowal, [e-mail]

Copyright and License

This library is © Copyright Uber Technologies, Inc. 2014. All rights reserved.