Swift solution to Kata18: Transitive Dependencies

Dave’s 18th kata asks us to build a simple transitive dependency analyzer. Code download and my solutions to other katas in this series.

One of the insidious things about dependencies is that they are transitive — if A depends on B and B depends on C, then A also depends on C. So, let’s write some code that calculates the full set of dependencies for a group of items. The code takes as input a set of lines where the first token is the name of an item. The remaining tokens are the names of things that this first item depends on.

For the first part of the kata, the data structure can best be visualized as a tree

…more helpfully…

Tree diagram showing class relationships

In the diagram, A is dependent on B, C, D, and E.

To make the code domain specific, I create a typealias for Node and DirectDependencies. This makes it easier to visualize what we’re referring to while working with the code.

typealias Node = String
typealias DirectDependencies = [Node : [Node]]

The add method is used to load the nodes and their dependencies and store them in an allDirectDependencies dictionary.

When findAllDependencies(node:, directDependencies:) is called we recursively “walk down the tree”, starting with the node that was passed in and keep track of all the direct dependencies.

This works fine until we hit the case of a circular dependency. Where

A’s dependent on B

B’s dependent on C

C’s dependent on A

There’s two ways to handle this case, the first is detect it, but only evaluate each node once to avoid the infinite loop. The second (and what I went with) is to say that a circular dependency is an invalid state and to throw an exception.

I create an allDependencies property that I add the initial node to when the findAllDependencies method is called. Each time through the recursive loop, I check if any of the indirectDependencies found are already in allDependencies. If not, I add them to the set. If they are, I break out of the loop and return an error of type DependencyError.Circular.

For a polished functional implementation of this Kata, check out Josh Smith’s solution.