Renaming Dependencies

OCaml has a rich and expressive module system, which makes renaming a particularly complex task. Types for modules may be independently declared, bound to (module type) identifiers, modified by various kinds of constraints, and used as annotations that trigger compiler checks. The use of functors introduces further coupling between the modules and module types declared in a program. Declarations in both modules and module types may be shadowed, and duplicated through the use of include statements.

Some of the issues are illustrated by the following example.

  module type Stringable = sig
    type t
    val to_string : t -> string
  end

  module Pair(X : Stringable)(Y : Stringable) = struct
    type t = X.t * Y.t
    let to_string (x, y) = (X.to_string x) ˆ " " ˆ (Y.to_string y)
  end

  module Int = struct
    type t = int
    let to_string i = int_to_string i
  end

  module String = struct
    type t = string
    let to_string s = s
  end

  module P = Pair(Int)(String) ;;

  print_endline (P.to_string (5, "Gold Rings") ;;

This program defines a functor Pair that takes two modules as arguments, which must conform to the Stringable module type. It also defines two structures Int and String, using them as arguments in an application of Pair and binding the result to the module P. Suppose we wanted to rename the to_string function in the Int module. To do so correctly, we must take the following into account:

  • Since Int is used as the first argument to an application of Pair, the to_string member of Pair’s first parameter must be renamed.
  • The first parameter of Pair is declared to be of module type Stringable, so to_string in Stringable must be renamed.
  • The second parameter of Pair is also declared to be of module type Stringable, so its to_string member must be renamed.
  • The String module is used as the second argument to an application of Pair, and so its to_string member must also be renamed.

Although we could correctly rename the to_string function in the String module by carrying out a global find-and-replace, this would result in renaming too many things. In particular, we do not need to rename the to_string function declared in the body of the Pair functor.

The declarations of to_string in the modules Int and String and the module type Stringable are all related. Renaming the binding to_string in the Int module actually depends on renaming other bindings in the program: failing to rename any one of them would result in the program being rejected by the compiler. Moreover, these bindings are all mutually dependent on each other.

For a given value binding, ROTOR computes its set of renaming dependencies using a worklist algorithm, starting with a working set consisting of the primary binding to be renamed. To process each dependency in the worklist, ROTOR analyses each source file that depends on the module containing the binding. ROTOR then generates dependencies based on identifying the following syntactic patterns, with each newly generated dependency that has not already been processed being added to the worklist.

In the following, ROTOR’s identifier syntax is used.

Module and Signature Includes

In renaming a binding .A:foo, if module A is included in another module B, e.g.

  module B = struct include A end

then a dependency .B:foo is generated. Analogously,

  module type T = sig include S end

would generate the dependency %T:foo for the binding %S:foo. The reverse is also true.

Module and Module Type Aliases

Dependencies are generated similarly when module or module types are aliased.

  module B = A
  module type S = T

Here, the dependencies .B:foo and %S:foo would be generated for bindings .A:foo and %T:foo, respectively, and vice versa.

Module Type Annotations

In renaming %S:foo, dependencies are generated by module type annotations, e.g.

  module A : S = ...

Here the dependency .A:foo is generated. In the opposite direction, the dependency %S:foo is only generated for renaming .A:foo when the module type S actually contains a declaration of foo ( N.B. it need not: module types can be used to hide sub-components of modules). Module type annotations on functor parameters also generate dependencies, e.g.

  module F (X : S) = ...

generates #F[1]:foo for %S:foo, and vice versa.

Functor Applications

In renaming in functor parameters, e.g. #F[1]:foo, the application

  module M = F (N)

generates the dependency .N:foo. In the reverse direction, .N:foo would only generate #F[1]:foo if the declared type of F’s first parameter contains a declaration for foo.

Module Type Constraints

In renaming .M:foo, a module type constraint, e.g.

  S with module N = M

results in a dependency %S.N:foo, but only if N contains a declaration of foo (the type of module N is only required to be a supertype of that of module M). A dependency is also generated in the reverse direction.