OCaml Cyclical Build Dependencies

OCaml Cyclical Build Dependencies

This page provides some suggestions for how to resolve cyclic build dependencies.

Symptom

OMake gives an error like the following:

*** omake: deadlock on a.cmx
*** omake: is a dependency of b.cmx
*** omake: is a dependency of a.cmx

Problem

You have a cyclic dependency between your modules, so OMake cannot find a linear order of compilation.

For example, the following set of modules exhibits this problem:

                         a.ml
let bar () = ()
let foo () = B.bar ()
let gip () = bar ()

                         b.ml
let bar () = A.bar ()

The edges in the call graph are:

A -> B

B -> A

which is cyclic.

Possible Solutions

Here are some potential ways around the problem.

Avoid the situation by careful design

Design the interfaces between modules such that there is a directed, acyclic flow in the graph of modules where edges are function calls. In the example above, the call back from module B to module A would be disallowed.

For example, in our codebase, we have ocaml/xapi/xapi.ml as the "main" module, calling functions in other modules: those modules should never contain functions which call functions back in ocaml/xapi/xapi.ml.

However, sometimes this approach is not possible if you are adding extra functionality to existing code.

Move a function into a new file

A potential solution is to move a function into a separate module to break the cyclic dependency. The fix to the example above would be:

                              a_bar.ml
let bar () = ()a.ml
let foo () = B.bar ()
let gip () = A_bar.bar ()

                              b.ml
let bar () = A_bar.bar ()

The edges in the call graph are now

A -> B

A -> A_bar

B -> A_bar

which is acyclic.

Pass the function in as a parameter

By passing the "callback" function as a parameter, there is no need for the reverse link in the call graph, breaking the cyclic dependency. The fix to the example above would be:

                         a.ml
let bar () = ()
let foo () = B.bar bar
let gip () = bar ()

                         b.ml
let bar f = f ()

The edges in the call graph are now

A -> B

which is acyclic.

Using functors

In some situations, you need to pass a lot of "callback" functions and maybe also type declarations. In this case, it could be useful to use functors.

                         a.ml
let bar () = ()
let gip () = bar ()

module type B_sig = sig val bar : unit -> unit end
module A (B : B_sig) = struct
let foo () = B.bar ()
end

                          b.ml
module B = struct let bar () = A.bar () end
module A = A(B)
let bar = B.bar

The edges in the call graph are now

B -> A

which is acyclic.

However, in this very simple example, it is not really a good idea to use functors

Using global references

Warning: this is a very ugly solution, try to not use it, but sometimes there are no other ways, so .... (and it is used inside the source code of xapi).

                      a.ml
let bar () = ()
let _ = B.bar := bar
let foo () = !B.bar ()
let gip () = bar ()

                      b.ml
let bar = ref (fun () -> ())

The edges in the call graph are now

A -> B

which is acyclic.