Playing with llbuild core in swift!


Swift Package Manager uses llbuild to build the packages. llbuild is a complex build system like make/ninja etc built on a layered architecture. The bottom most layer is called Core, a buildengine responsible for managing and performing the computations. It is completely written in C++ but I got swift bindings to build …after some fighting with cmake otherwise this post would have been in C++ 😄. Lets use the buildengine to do some computation.


Problem statement: Find sum of square roots of numbers upto N.

So basically we need to calculate sqrt(1) + sqrt(2) + sqrt(3) + sqrt(4) + ... + sqrt(N)

Before jumping into code, lets describe the solution in simpler terms.

To find the solution for N = 5, all we need is sqrt(5) + sqrtsum(4).

So basically the solution is sqrt(N) + sqrtsum(N-1).

Rule

A Rule is an individual element of computation that can be performed by the build engine. A Rule is identified by a unique Key which is basically a string (atleast for now). Rules are responsible for creating Task objects which “represents an abstract in-progress computation in the buildengine”. To understand this more lets just start with the example:

class SumSquareRootRule: Rule {
  let input: Key
  init(_ input: Key) {
    self.input = input
  } 
  func createTask() -> Task {
    return SumSquareRootTask(input)
  }
}

Rule is a protocol which requires us to implement the createTask() method which returns the Task object for that rule. Our Rule is simple, all we need to do is store the key and create the Task object using the Key. Here Key will be the limit N.

BuildEngineDelegate

Whenever buildengine is asked to build a Key, it asks the BuildEngineDelegate to provide the Rule for that key. Our delegate will also be very simple:

class SumSquareRootTaskDelegate: BuildEngineDelegate {
  func lookupRule(key: Key) -> Rule {
    return SumSquareRootRule(key)
  }
}

Task

Now here things get interesting. We need to create a task which will take an input N and ask the buildengine to do the computation of N-1. Once we have N-1 we can find the sqrt of N and add it with result of computation of N-1.

class SumSquareRootTask: Task {
  let input: Int
  var prev = 0.0
  
  init(_ input: Key) {
    self.input = Int(input.toString())!
  }
}

The input Key is converted into an Int (which is our N) and we keep another variable prev which will hold the result of computation of N-1 once buildengine provides it.

Task provides 3 methods for managing the computation:

  • func start(engine: TaskBuildEngine)

This is called when build engine starts this task. In our case we need to tell buildengine to provide us computation of N-1:

func start(engine: TaskBuildEngine) {
  if input > 0 {
    engine.taskNeedsInput(Key("\(input - 1)"), inputID: input - 1)
  }
}
  • func provideValue(engine: TaskBuildEngine, inputID: Int, value: Value)

Once buildengine has a value for a input we requested, it’ll call this method with the value of the requested input. It is allowed to ask for additional inputs here. We store the result in the variable prev.

func provideValue(engine: TaskBuildEngine, inputID: Int, value: Value) {
  let theValue = Double(value.toString())!
  prev = theValue
}
  • func inputsAvailable(engine: TaskBuildEngine)

When all of the request inputs are statisfied buildengine will call this method.

We find the sqrt of our N and add it with prev.

func inputsAvailable(engine: TaskBuildEngine) {
  let result = sqrt(Double(input)) + prev
  print("Computing sqrt for \(input)")
  engine.taskIsComplete(Value("\(result)"), forceChange: false)
}

BuildEngine

Now all that is left is creating the delegate and engine object and calling the build method to get the output.

let delegate = SumSquareRootTaskDelegate()
var engine = BuildEngine(delegate: delegate)

var result = engine.build(Key("5"))
print("\(result.toString())")

Output:

Computing sqrt for 0
Computing sqrt for 1
Computing sqrt for 2
Computing sqrt for 3
Computing sqrt for 4
Computing sqrt for 5
8.38233234744176

As expected, buildengine went on and calcuated the sqrt of all the numbers upto N and provided us with the final value.

Suppose we now need to know value of N=6

result = engine.build(Key("6"))
print("\(result.toString())")

Output:

Computing sqrt for 6
10.8318220902249

Since buildengine had already computed the values till N=5, it did not recalcuate them and only computed for N=6. Similarly if we ask for N=4, there will be no computation and we’ll directly have the result.

result = engine.build(Key("4"))
print("\(result.toString())")
6.14626436994197

This was a very simple example of what buildengine can do. Here is another example converted from C++ core unit tests to swift :

Here we have 3 rules A, B and C where C depends on A and B. Buildengine first calcuates A and B and then starts computing C.

A’s computation returns 2, B’s computation returns 3 and C is expected to multiply the result of A and B.

typealias Compute = [Int] -> Int

class SimpleTask: Task {
  let inputs: [Key]
  var values: [Int]
  let compute: Compute
	
  init(_ inputs: [Key], compute: Compute) {
    self.inputs = inputs
    values = [Int](count: inputs.count, repeatedValue: 0)
    self.compute = compute
  }
	
  func start(engine: TaskBuildEngine) {
    for (idx, input) in inputs.enumerate() {
      engine.taskNeedsInput(input, inputID: idx)
    }
  }
  
  func provideValue(engine: TaskBuildEngine, inputID: Int, value: Value) {
    values[inputID] = Int(value.toString())!
  }
  
  func inputsAvailable(engine: TaskBuildEngine) {
    let result = compute(values)
    engine.taskIsComplete(Value("\(result)"), forceChange: false)
  }
}

class SimpleBuildEngineDelegate: BuildEngineDelegate {
  var builtKeys = [Key]()
	
  func lookupRule(key: Key) -> Rule {
    switch key.toString() {
    case "A":
      return SimpleRule([]) { arr in
        precondition(self.builtKeys.isEmpty)
        self.builtKeys.append(key)
        return 2
      }
    case "B":
      return SimpleRule([]) { arr in
        precondition(self.builtKeys.count == 1)
        self.builtKeys.append(key)
        return 3
      }
    case "C":
      return SimpleRule([Key("A"), Key("B")]) { arr in 
        precondition(self.builtKeys.count == 2)
        precondition(self.builtKeys[0].toString() == "A")
        precondition(self.builtKeys[1].toString() == "B")
        self.builtKeys.append(key)
        return arr[0] * arr[1]
      }
      default: fatalError("Unexpected key \(key) lookup")
    }
  }
}

class SimpleRule: Rule {
  let inputs: [Key]
  let compute: Compute
  init(_ inputs: [Key], compute: Compute) { 
    self.inputs = inputs 
    self.compute = compute
  } 
  func createTask() -> Task {
    return SimpleTask(inputs, compute: compute)
  }
}

let delegate = SimpleBuildEngineDelegate()
var engine = BuildEngine(delegate: delegate)

// C depends on A and B
var result = engine.build(Key("C"))
print("\(result.toString())")

precondition(result.toString() == "6")

// Make sure building already built keys do not re-compute.
delegate.builtKeys.removeAll()
precondition(delegate.builtKeys.isEmpty)

result = engine.build(Key("A"))
precondition(result.toString() == "2")
precondition(delegate.builtKeys.isEmpty)

result = engine.build(Key("B"))
precondition(result.toString() == "3")
precondition(delegate.builtKeys.isEmpty)