Resolution#

Resolution is the process by which we take a value of type Lang.t and look up details of the internal cross references and make sure we know exactly which component is being referred to. Much of the work has been done by the compiler but we need to do a little more. For example, given

module M : sig
  type t
end
type u = M.t 

in the definition of u, the compiler tells us precisely which M is on the right hand side but doesn't say to which t it is referring to; the representation of this is simply the string "t". Resolution is the process of finding precise identifiers that will allow us to construct links.

We'll start with a little preamble, constructing the execution environment in which we can run through some tests and describe the resolution process.

(* Prelude *)
#require "odoc.xref_test";;
open Odoc_xref2;;
open Odoc_xref_test;;
open Odoc_model.Names;;
#install_printer Common.root_pp;;
#install_printer Odoc_model.Names.ValueName.fmt;;
#install_printer Odoc_model.Names.ModuleName.fmt;;
#install_printer Odoc_model.Names.ModuleTypeName.fmt;;
#install_printer Odoc_model.Names.TypeName.fmt;;
#install_printer Odoc_model.Names.ExceptionName.fmt;;
#install_printer Odoc_model.Names.FieldName.fmt;;
#install_printer Odoc_model.Names.PageName.fmt;;
#print_length 65536;;
Odoc_xref2.Component.Delayed.eager := true;;
Odoc_xref2.Tools.disable_all_caches ();;
let id = Common.id;;
let _ = Odoc_model.Names.set_unique_ident "XXXX";;

Simple resolution#

We'll start by examining the simple case - how we deal with module hierarchies, and build up later to the more advanced uses of the module system.

No modules at all#

The simplest possible resolution it simply checking that a resolved path exists. We'll use a helper function Common.signature_of_mli_string to go straight from a text representation of an mli file to the type we would ordinarily read from a compiled cmti file.

let test_data = {|
  type x
  type u = x
|};;
let sg = Common.signature_of_mli_string test_data;;

The type of sg is:

# #show_val sg;;
val sg : Odoc_model.Lang.Signature.t

This Signature.t is a representation of the entire cmti file, and resolution essentially proceeds as map function over this data type: Signature.t -> Signature.t, with the end result having precise identifiers for all elements in the signature.

The first thing we do is to construct an environment from the signature. The environment is simply a mapping from identifiers to items representing each element in the signature. The representations are types declared in the module Component, and follow quite closely those in module Lang, the main difference being in the types of paths. The environment constructed from the above signature is as follows:

# Env.open_signature sg Env.empty;;
- : Env.t = <abstr>

here we can see there are two types in the environment and nothing else. u has identifier `Type (`Root (Common.root, "Root"), "u"), and has an internal identifier of ("u",17). t is abstract and therefore has no manifest, but u has a manifest that points to the `Identifier path that has already been `Resolved to `Identifier `Type (`Root (Common.root, "Root"), "u"). So there won't be much for us to do.

The resolution process proceeds starting from the Lang.Signature.t going down until it finds values that are subtypes of Path.t - for example, a Module.decl is defined as

type decl =
  | Alias of Path.Module.t
  | ModuleType of ModuleType.expr

This type Path.Module.t is a polymorphic variant:

type any = [
  | `Resolved of Resolved_path.module_
  | `Root of string
  | `Forward of string
  | `Dot of module_ * string
  | `Apply of module_ * module_
]

and Resolved_path.module_ is:

type module_ = [
  | `Identifier of Identifier.path_module
  | `Subst of module_type * module_
  | `Alias of module_ * module_
  | `Hidden of module_
  | `Module of module_ * ModuleName.t
  | `Canonical of module_ * Path.module_
  | `Apply of module_ * Path.module_
  | `Alias of module_ * module_
  ]

Once it gets to a Path.t (or a Path.Module.t, Path.Type.t etc.), and looks down the path to find the element. The aim is to have every path start with `Resolved.

In our example above, the first instance of a Path.t is the right hand side of the type u. For the purposes of examining that value, we can define a Lens that extracts just that out of the Signature.t:

let type_manifest name =
  let open Common.LangUtils.Lens in
  Signature.type_ name |-- TypeDecl.equation |-- TypeDecl.Equation.manifest
let u_manifest = type_manifest "u"
let t_manifest = type_manifest "t"
let s_manifest = type_manifest "s"

and using this lens on our original signature we obtain:

# Common.LangUtils.Lens.get u_manifest sg ;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Identifier
      ({Odoc_model__Paths_types.iv =
         `Type
           ({Odoc_model__Paths_types.iv =
              `Root
                (Some
                  {Odoc_model__Paths_types.iv = `Page (None, None);
                   ihash = 236059787; ikey = "p_None"},
                 Root);
             ihash = 818126955; ikey = "r_Root.p_None"},
            x);
        ihash = 622581103; ikey = "t_x.r_Root.p_None"},
       false),
   []))

This path clearly already begins with `Resolved, so we don't expect to change it, but we are going to check it exists. We convert the path into a Cpath.t and call Tools.resolve_type. This function starts approximately:

    | `Resolved r as unresolved ->
        of_result ~unresolved (lookup_type env r) >>=
        fun t -> return (r, t)

and lookup_type starts:

    | `Identifier (`Type _ as i) ->
        of_option ~error:(`Lookup_failure i) (Env.lookup_type i env)
        >>= fun t -> Ok (Find.Found (`T t))

and so we simply look up the type in the environment, giving a Component.Type.t that represents the type.

# Common.compile_signature sg;;
- : Odoc_model.Lang.Signature.t =
{Odoc_model.Lang.Signature.items =
  [Odoc_model.Lang.Signature.Type (Odoc_model.Lang.Signature.Ordinary,
    {Odoc_model.Lang.TypeDecl.id =
      {Odoc_model__Paths_types.iv =
        `Type
          ({Odoc_model__Paths_types.iv =
             `Root
               (Some
                 {Odoc_model__Paths_types.iv = `Page (None, None);
                  ihash = 236059787; ikey = "p_None"},
                Root);
            ihash = 818126955; ikey = "r_Root.p_None"},
           x);
       ihash = 622581103; ikey = "t_x.r_Root.p_None"};
     source_loc = None;
     doc = {Odoc_model__.Comment.elements = []; warnings_tag = None};
     canonical = None;
     equation =
      {Odoc_model.Lang.TypeDecl.Equation.params = []; private_ = false;
       manifest = None; constraints = []};
     representation = None});
   Odoc_model.Lang.Signature.Type (Odoc_model.Lang.Signature.Ordinary,
    {Odoc_model.Lang.TypeDecl.id =
      {Odoc_model__Paths_types.iv =
        `Type
          ({Odoc_model__Paths_types.iv =
             `Root
               (Some
                 {Odoc_model__Paths_types.iv = `Page (None, None);
                  ihash = 236059787; ikey = "p_None"},
                Root);
            ihash = 818126955; ikey = "r_Root.p_None"},
           u);
       ihash = 15973539; ikey = "t_u.r_Root.p_None"};
     source_loc = None;
     doc = {Odoc_model__.Comment.elements = []; warnings_tag = None};
     canonical = None;
     equation =
      {Odoc_model.Lang.TypeDecl.Equation.params = []; private_ = false;
       manifest =
        Some
         (Odoc_model.Lang.TypeExpr.Constr
           (`Resolved
              (`Identifier
                 {Odoc_model__Paths_types.iv =
                   `Type
                     ({Odoc_model__Paths_types.iv =
                        `Root
                          (Some
                            {Odoc_model__Paths_types.iv = `Page (None, None);
                             ihash = 236059787; ikey = "p_None"},
                           Root);
                       ihash = 818126955; ikey = "r_Root.p_None"},
                      x);
                  ihash = 622581103; ikey = "t_x.r_Root.p_None"}),
           []));
       constraints = []};
     representation = None})];
 compiled = true; removed = [];
 doc = {Odoc_model__.Comment.elements = []; warnings_tag = None}}

One module#

Now let's look at a marginally more complicated example. In this case, our type [t] is now inside a module:

let test_data = {|
module M : sig
    type t
end
type u = M.t
|};;
let sg = Common.signature_of_mli_string test_data;;
let env = Env.open_signature sg Env.empty;;

The OCaml compiler find the module M exactly, but everything after that is left to us to identify precisely. So the manifest of u is now:

# Common.LangUtils.Lens.get u_manifest sg ;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`DotT
      (`Identifier
         ({Odoc_model__Paths_types.iv =
            `Module
              ({Odoc_model__Paths_types.iv =
                 `Root
                   (Some
                     {Odoc_model__Paths_types.iv = `Page (None, None);
                      ihash = 236059787; ikey = "p_None"},
                    Root);
                ihash = 818126955; ikey = "r_Root.p_None"},
               M);
           ihash = 716453475; ikey = "m_M.r_Root.p_None"},
          false),
       t),
   []))

Here we can see that the path is not completely resolved. The M bit is resolved, but the t bit is not. So we have to do a bit more work when we look up the type in Tools.resolve_type.

Let's look in more detail at that process. The first thing that happens is that the path is matched the [`Dot] is found:

   | `Dot (parent, id) ->
        resolve_module env parent
        >>= fun (p, m) ->

This implies that the thing before the dot is a module, so we call Tools.resolve_module. This is a resolved identifier so we can simply look this up from the environment. This gets us back the path and a Component.Module.t representing the module M, which are:

# let get_ok = function
    | Ok x -> x
    | Error _ -> failwith "Found error";;
val get_ok : ('a, 'b) result -> 'a = <fun>
# let (path, module_) = get_ok @@ Tools.resolve_module env (`Resolved (`Gpath (`Identifier (Common.root_module "M"))));;
val path : Cpath.Resolved.module_ =
  `Gpath
    (`Identifier
       {Odoc_model__Paths_types.iv =
         `Module
           ({Odoc_model__Paths_types.iv =
              `Root
                (Some
                  {Odoc_model__Paths_types.iv = `Page (None, None);
                   ihash = 236059787; ikey = "p_None"},
                 Root);
             ihash = 818126955; ikey = "r_Root.p_None"},
            M);
        ihash = 716453475; ikey = "m_M.r_Root.p_None"})
val module_ : Component.Module.t Component.Delayed.t =
  {Odoc_xref2.Component.Delayed.v =
    Some
     {Odoc_xref2.Component.Module.source_loc = None;
      doc =
       {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
      type_ =
       Odoc_xref2.Component.Module.ModuleType
        (Odoc_xref2.Component.ModuleType.Signature
          {Odoc_xref2.Component.Signature.items =
            [Odoc_xref2.Component.Signature.Type (`LType (t, 0),
              Odoc_model.Lang.Signature.Ordinary,
              {Odoc_xref2.Component.Delayed.v =
                Some
                 {Odoc_xref2.Component.TypeDecl.source_loc = None;
                  doc =
                   {Odoc_xref2.Component.CComment.elements = [];
                    warnings_tag = None};
                  canonical = None;
                  equation =
                   {Odoc_xref2.Component.TypeDecl.Equation.params = [];
                    private_ = false; manifest = None; constraints = []};
                  representation = None};
               get = None})];
           compiled = false; removed = [];
           doc =
            {Odoc_xref2.Component.CComment.elements = [];
             warnings_tag = None}});
      canonical = None; hidden = false};
   get = None}

The values returned are the resolved path to the module, and a representation of the module itself. We then turn the module into a signature via expansion_of_module, which in this case is quite simple since the module contains an explicit signature:

# get_ok @@ Tools.expansion_of_module env (Component.Delayed.get module_);;
- : Tools.expansion =
Odoc_xref2.Tools.Signature
 {Odoc_xref2.Component.Signature.items =
   [Odoc_xref2.Component.Signature.Type (`LType (t, 0),
     Odoc_model.Lang.Signature.Ordinary,
     {Odoc_xref2.Component.Delayed.v =
       Some
        {Odoc_xref2.Component.TypeDecl.source_loc = None;
         doc =
          {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
         canonical = None;
         equation =
          {Odoc_xref2.Component.TypeDecl.Equation.params = [];
           private_ = false; manifest = None; constraints = []};
         representation = None};
      get = None})];
  compiled = false; removed = [];
  doc = {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None}}

We're now in a position to verify the existence of the type t we're looking up - and indeed it is there. We therefore construct the new resolved path to this type : `Type (path, "t"), and return this and the definition of the type, which in this case is uninteresting.

Indirection#

Let's now examine the case when a module's signature has to be found from the environment.

let test_data = {|
module type M = sig
    type t
end
module N : M
type u = N.t
|};;
let sg = Common.signature_of_mli_string test_data;;
let env = Env.open_signature sg Env.empty;;

It proceeds much as the previous example until we get the result of looking up the module N:

# let (path, module_) = get_ok @@ Tools.resolve_module env (`Resolved (`Gpath (`Identifier (Common.root_module "N"))));;
val path : Cpath.Resolved.module_ =
  `Gpath
    (`Identifier
       {Odoc_model__Paths_types.iv =
         `Module
           ({Odoc_model__Paths_types.iv =
              `Root
                (Some
                  {Odoc_model__Paths_types.iv = `Page (None, None);
                   ihash = 236059787; ikey = "p_None"},
                 Root);
             ihash = 818126955; ikey = "r_Root.p_None"},
            N);
        ihash = 502470005; ikey = "m_N.r_Root.p_None"})
val module_ : Component.Module.t Component.Delayed.t =
  {Odoc_xref2.Component.Delayed.v =
    Some
     {Odoc_xref2.Component.Module.source_loc = None;
      doc =
       {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
      type_ =
       Odoc_xref2.Component.Module.ModuleType
        (Odoc_xref2.Component.ModuleType.Path
          {Odoc_xref2.Component.ModuleType.p_expansion = None;
           p_path =
            `Identifier
              ({Odoc_model__Paths_types.iv =
                 `ModuleType
                   ({Odoc_model__Paths_types.iv =
                      `Root
                        (Some
                          {Odoc_model__Paths_types.iv = `Page (None, None);
                           ihash = 236059787; ikey = "p_None"},
                         Root);
                     ihash = 818126955; ikey = "r_Root.p_None"},
                    M);
                ihash = 459143770; ikey = "mt_M.r_Root.p_None"},
               false)});
      canonical = None; hidden = false};
   get = None}

This time turning the module into a signature demonstrates why the function expansion_of_module requires the environment. We need to lookup the module type M from the environment to determine the signature of the module. After this though the resolution is as before.

Local paths#

We now look at an example involving local paths. These paths happen when a path refers to something that isn't in the toplevel environment. We'll use the following example to explain the idea:

let test_data = {|
module type M = sig
    module type N = sig
        type t
    end
    module B : N
end
module A : M
type u = A.B.t
|};;
let sg = Common.signature_of_mli_string test_data;;
let env = Env.open_signature sg Env.empty;;

The definition of module B constrains it to have a signature given by the module type N. However, N is not defined at the top level here, so it has a local identifier. We can see this by looking up module M from the environment:

# let m = Env.(lookup_by_id s_module_type) (Odoc_model.Paths.Identifier.Mk.module_type (Common.id, Odoc_model.Names.ModuleTypeName.make_std "M")) env;;
val m : Component.Element.module_type option =
  Some
   (`ModuleType
      ({Odoc_model__Paths_types.iv =
         `ModuleType
           ({Odoc_model__Paths_types.iv =
              `Root
                (Some
                  {Odoc_model__Paths_types.iv = `Page (None, None);
                   ihash = 236059787; ikey = "p_None"},
                 Root);
             ihash = 818126955; ikey = "r_Root.p_None"},
            M);
        ihash = 459143770; ikey = "mt_M.r_Root.p_None"},
       {Odoc_xref2.Component.ModuleType.source_loc = None;
        doc =
         {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
        canonical = None;
        expr =
         Some
          (Odoc_xref2.Component.ModuleType.Signature
            {Odoc_xref2.Component.Signature.items =
              [Odoc_xref2.Component.Signature.ModuleType
                (`LModuleType (N, 1),
                {Odoc_xref2.Component.Delayed.v =
                  Some
                   {Odoc_xref2.Component.ModuleType.source_loc = None;
                    doc =
                     {Odoc_xref2.Component.CComment.elements = [];
                      warnings_tag = None};
                    canonical = None;
                    expr =
                     Some
                      (Odoc_xref2.Component.ModuleType.Signature
                        {Odoc_xref2.Component.Signature.items =
                          [Odoc_xref2.Component.Signature.Type
                            (`LType (t, 2),
                            Odoc_model.Lang.Signature.Ordinary,
                            {Odoc_xref2.Component.Delayed.v =
                              Some
                               {Odoc_xref2.Component.TypeDecl.source_loc =
                                 None;
                                doc =
                                 {Odoc_xref2.Component.CComment.elements = [];
                                  warnings_tag = None};
                                canonical = None;
                                equation =
                                 {Odoc_xref2.Component.TypeDecl.Equation.params
                                   = [];
                                  private_ = false; manifest = None;
                                  constraints = []};
                                representation = None};
                             get = None})];
                         compiled = false; removed = [];
                         doc =
                          {Odoc_xref2.Component.CComment.elements = [];
                           warnings_tag = None}})};
                 get = None});
               Odoc_xref2.Component.Signature.Module (`LModule (B, 0),
                Odoc_model.Lang.Signature.Ordinary,
                {Odoc_xref2.Component.Delayed.v =
                  Some
                   {Odoc_xref2.Component.Module.source_loc = None;
                    doc =
                     {Odoc_xref2.Component.CComment.elements = [];
                      warnings_tag = None};
                    type_ =
                     Odoc_xref2.Component.Module.ModuleType
                      (Odoc_xref2.Component.ModuleType.Path
                        {Odoc_xref2.Component.ModuleType.p_expansion = None;
                         p_path = `Local (`LModuleType (N, 1), false)});
                    canonical = None; hidden = false};
                 get = None})];
             compiled = false; removed = [];
             doc =
              {Odoc_xref2.Component.CComment.elements = [];
               warnings_tag = None}})}))

We can see here that module B has type Path (`Resolved (`Local (`LModuleType (N, 1)))) which refers to the module type defined just above it.

To look up we need to have fully qualified paths for all items so this needs some work. The way this is handled is that when we want to look up an element within a module, we don't just convert it blindly to a signature. Since we have the fully qualified path to the module, we prefix all the identifiers bound in that signature with that path to turn them into global identifiers.

Concretely, we start here wanting to resolve the path for type u, which is A.B.t. The compiler has started us off by resolving the A:

# Common.LangUtils.Lens.get u_manifest sg ;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`DotT
      (`Dot
         (`Identifier
            ({Odoc_model__Paths_types.iv =
               `Module
                 ({Odoc_model__Paths_types.iv =
                    `Root
                      (Some
                        {Odoc_model__Paths_types.iv = `Page (None, None);
                         ihash = 236059787; ikey = "p_None"},
                       Root);
                   ihash = 818126955; ikey = "r_Root.p_None"},
                  A);
              ihash = 353272258; ikey = "m_A.r_Root.p_None"},
             false),
          B),
       t),
   []))

we look up A from the environment:

# let p = `Gpath (`Identifier (Common.root_module "A")) in
  let m = get_ok @@ Tools.lookup_module env p in
  let sg = get_ok @@ Tools.expansion_of_module env (Component.Delayed.get m) in
  Tools.prefix_signature (`Module p, sg);;
Line 4, characters 38-40:
Error: The value sg has type Tools.expansion
       but an expression was expected of type Component.Signature.t

So before the prefixing operation we had that the type of the module was

   type_ =
      Odoc_xref2.Component.Module.ModuleType
      (Odoc_xref2.Component.ModuleType.Path
         (`Resolved (`Local (`LModuleType (N, 1)))));

and afterwards it is

   type_ =
   Odoc_xref2.Component.Module.ModuleType
      (Odoc_xref2.Component.ModuleType.Path
      (`Resolved
         (`ModuleType
            (`Module
               (`Identifier (`Module (`Root (Common.root, Root), A))),
               N))));

We now look up module B from this signature, which once again we need to convert to a signature to find t. We find the type above, which we can then convert in turn into a signature. Once again, we go down the path until we find the identifier (A in this case), look that up from the environment, then look up the module type N. We can then turn this into the signature for B, prefixing local paths with the resolved path A.B (though in this case there are now no local identifiers.) Finally we can now look up t, which we then return along with the fully resolved identifier.

# fst @@ get_ok @@ Tools.resolve_type env
    (`DotT
      (`Dot
         (`Resolved
            (`Gpath (`Identifier (Common.root_module "A"))),
          ModuleName.make_std "B"),
       TypeName.make_std "t"));;
- : Cpath.Resolved.type_ =
`Type
  (`Module
     (`Module
        (`Module
           (`Gpath
              (`Identifier
                 {Odoc_model__Paths_types.iv =
                   `Module
                     ({Odoc_model__Paths_types.iv =
                        `Root
                          (Some
                            {Odoc_model__Paths_types.iv = `Page (None, None);
                             ihash = 236059787; ikey = "p_None"},
                           Root);
                       ihash = 818126955; ikey = "r_Root.p_None"},
                      A);
                  ihash = 353272258; ikey = "m_A.r_Root.p_None"})),
         B)),
   t)

Module aliases#

let test_data = {|
module A : sig
  module M : sig type t end
  module N = M
end

type t = A.N.t
|}
let sg = Common.signature_of_mli_string test_data;;
let resolved = Common.compile_signature sg;;

Let's look at t's manifest:

# Common.LangUtils.Lens.get t_manifest resolved ;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Alias
            (`Module
               (`Identifier
                  {Odoc_model__Paths_types.iv =
                    `Module
                      ({Odoc_model__Paths_types.iv =
                         `Root
                           (Some
                             {Odoc_model__Paths_types.iv = `Page (None, None);
                              ihash = 236059787; ikey = "p_None"},
                            Root);
                        ihash = 818126955; ikey = "r_Root.p_None"},
                       A);
                   ihash = 353272258; ikey = "m_A.r_Root.p_None"},
                M),
             `Dot
               (`Identifier
                  ({Odoc_model__Paths_types.iv =
                     `Module
                       ({Odoc_model__Paths_types.iv =
                          `Root
                            (Some
                              {Odoc_model__Paths_types.iv =
                                `Page (None, None);
                               ihash = 236059787; ikey = "p_None"},
                             Root);
                         ihash = 818126955; ikey = "r_Root.p_None"},
                        A);
                    ihash = 353272258; ikey = "m_A.r_Root.p_None"},
                   false),
                N)),
          t)),
   []))

When we turn A.N.t into a link, we need to render A.N.t as the link text (going down the right-hand side of the Alias constructor), but link to A.M.t since A.N will not have an expansion.

let test_data = {|
module A : sig
  module M : sig type t end
  module N = M
  module O = N
end

type t = A.O.t
|}
let sg = Common.signature_of_mli_string test_data;;
let resolved = Common.compile_signature sg;;

# Common.LangUtils.Lens.get t_manifest resolved ;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Alias
            (`Alias
               (`Module
                  (`Identifier
                     {Odoc_model__Paths_types.iv =
                       `Module
                         ({Odoc_model__Paths_types.iv =
                            `Root
                              (Some
                                {Odoc_model__Paths_types.iv =
                                  `Page (None, None);
                                 ihash = 236059787; ikey = "p_None"},
                               Root);
                           ihash = 818126955; ikey = "r_Root.p_None"},
                          A);
                      ihash = 353272258; ikey = "m_A.r_Root.p_None"},
                   M),
                `Dot
                  (`Identifier
                     ({Odoc_model__Paths_types.iv =
                        `Module
                          ({Odoc_model__Paths_types.iv =
                             `Root
                               (Some
                                 {Odoc_model__Paths_types.iv =
                                   `Page (None, None);
                                  ihash = 236059787; ikey = "p_None"},
                                Root);
                            ihash = 818126955; ikey = "r_Root.p_None"},
                           A);
                       ihash = 353272258; ikey = "m_A.r_Root.p_None"},
                      false),
                   N)),
             `Dot
               (`Identifier
                  ({Odoc_model__Paths_types.iv =
                     `Module
                       ({Odoc_model__Paths_types.iv =
                          `Root
                            (Some
                              {Odoc_model__Paths_types.iv =
                                `Page (None, None);
                               ihash = 236059787; ikey = "p_None"},
                             Root);
                         ihash = 818126955; ikey = "r_Root.p_None"},
                        A);
                    ihash = 353272258; ikey = "m_A.r_Root.p_None"},
                   false),
                O)),
          t)),
   []))

Module substitution#

We'll now look at a case where we perform a module substitution on a signature.

In the following example we have an interesting case where we have a module with a module type in it, and we make a substitution of this module.

let test_data = {|
module type A = sig
module M : sig module type S end
module N : M.S
end

module B : sig module type S = sig type t end end

module C : A with module M = B

type t = C.N.t
|};;
let sg = Common.signature_of_mli_string test_data;;
let resolved = Common.compile_signature sg;;
let env = Env.open_signature sg Env.empty;;

So in module type A, module N has type M.S, which does not contain a declaration for type t. When we make the substitution, although we're substituting M, because the signature of N is M.S, we also change N. So in module C, N should now contain a type t.

Once again, we look at the resolution of type t = C.N.t. When we look up the module C we find that the type_ field look as follows:

# let module_C_lens =
  let open Common.LangUtils.Lens in
  Signature.module_ "C";;
val module_C_lens :
  (Odoc_model.Lang.Signature.t, Odoc_model.Lang.Module.t)
  Common.LangUtils.Lens.lens =
  {Odoc_xref_test.Common.LangUtils.Lens.get = <fun>; set = <fun>}
# Common.LangUtils.Lens.get module_C_lens sg;;
- : Odoc_model.Lang.Module.t =
{Odoc_model.Lang.Module.id =
  {Odoc_model__Paths_types.iv =
    `Module
      ({Odoc_model__Paths_types.iv =
         `Root
           (Some
             {Odoc_model__Paths_types.iv = `Page (None, None);
              ihash = 236059787; ikey = "p_None"},
            Root);
        ihash = 818126955; ikey = "r_Root.p_None"},
       C);
   ihash = 43786577; ikey = "m_C.r_Root.p_None"};
 source_loc = None;
 doc = {Odoc_model__.Comment.elements = []; warnings_tag = None};
 type_ =
  Odoc_model.Lang.Module.ModuleType
   (Odoc_model.Lang.ModuleType.With
     {Odoc_model.Lang.ModuleType.w_substitutions =
       [Odoc_model.Lang.ModuleType.ModuleEq (`Dot (`Root, "M"),
         Odoc_model.Lang.Module.Alias
          (`Identifier
             ({Odoc_model__Paths_types.iv =
                `Module
                  ({Odoc_model__Paths_types.iv =
                     `Root
                       (Some
                         {Odoc_model__Paths_types.iv = `Page (None, None);
                          ihash = 236059787; ikey = "p_None"},
                        Root);
                    ihash = 818126955; ikey = "r_Root.p_None"},
                   B);
               ihash = 814134997; ikey = "m_B.r_Root.p_None"},
              false),
           None))];
      w_expansion = None;
      w_expr =
       Odoc_model.Lang.ModuleType.U.Path
        (`Identifier
           ({Odoc_model__Paths_types.iv =
              `ModuleType
                ({Odoc_model__Paths_types.iv =
                   `Root
                     (Some
                       {Odoc_model__Paths_types.iv = `Page (None, None);
                        ihash = 236059787; ikey = "p_None"},
                      Root);
                  ihash = 818126955; ikey = "r_Root.p_None"},
                 A);
             ihash = 231492881; ikey = "mt_A.r_Root.p_None"},
            false))});
 canonical = None; hidden = false}

Clearly there is no type t declared in here. Let's get the representation of module C we see the following:

# let m = get_ok @@ Tools.lookup_module env (`Gpath (`Identifier (Common.root_module "C")));;
val m : Component.Module.t Component.Delayed.t =
  {Odoc_xref2.Component.Delayed.v =
    Some
     {Odoc_xref2.Component.Module.source_loc = None;
      doc =
       {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
      type_ =
       Odoc_xref2.Component.Module.ModuleType
        (Odoc_xref2.Component.ModuleType.With
          {Odoc_xref2.Component.ModuleType.w_substitutions =
            [Odoc_xref2.Component.ModuleType.ModuleEq (`Dot (`Root, "M"),
              Odoc_xref2.Component.Module.Alias
               (`Identifier
                  ({Odoc_model__Paths_types.iv =
                     `Module
                       ({Odoc_model__Paths_types.iv =
                          `Root
                            (Some
                              {Odoc_model__Paths_types.iv =
                                `Page (None, None);
                               ihash = 236059787; ikey = "p_None"},
                             Root);
                         ihash = 818126955; ikey = "r_Root.p_None"},
                        B);
                    ihash = 814134997; ikey = "m_B.r_Root.p_None"},
                   false),
               None))];
           w_expansion = None;
           w_expr =
            Odoc_xref2.Component.ModuleType.U.Path
             (`Identifier
                ({Odoc_model__Paths_types.iv =
                   `ModuleType
                     ({Odoc_model__Paths_types.iv =
                        `Root
                          (Some
                            {Odoc_model__Paths_types.iv = `Page (None, None);
                             ihash = 236059787; ikey = "p_None"},
                           Root);
                       ihash = 818126955; ikey = "r_Root.p_None"},
                      A);
                  ihash = 231492881; ikey = "mt_A.r_Root.p_None"},
                 false))});
      canonical = None; hidden = false};
   get = None}

now we can ask for the signature of this module:

# let sg = get_ok @@ Tools.expansion_of_module env (Component.Delayed.get m);;
val sg : Tools.expansion =
  Odoc_xref2.Tools.Signature
   {Odoc_xref2.Component.Signature.items =
     [Odoc_xref2.Component.Signature.Module (`LModule (M, 31),
       Odoc_model.Lang.Signature.Ordinary,
       {Odoc_xref2.Component.Delayed.v =
         Some
          {Odoc_xref2.Component.Module.source_loc = None;
           doc =
            {Odoc_xref2.Component.CComment.elements = [];
             warnings_tag = None};
           type_ =
            Odoc_xref2.Component.Module.Alias
             (`Identifier
                ({Odoc_model__Paths_types.iv =
                   `Module
                     ({Odoc_model__Paths_types.iv =
                        `Root
                          (Some
                            {Odoc_model__Paths_types.iv = `Page (None, None);
                             ihash = 236059787; ikey = "p_None"},
                           Root);
                       ihash = 818126955; ikey = "r_Root.p_None"},
                      B);
                  ihash = 814134997; ikey = "m_B.r_Root.p_None"},
                 false),
             None);
           canonical = None; hidden = false};
        get = None});
      Odoc_xref2.Component.Signature.Module (`LModule (N, 32),
       Odoc_model.Lang.Signature.Ordinary,
       {Odoc_xref2.Component.Delayed.v =
         Some
          {Odoc_xref2.Component.Module.source_loc = None;
           doc =
            {Odoc_xref2.Component.CComment.elements = [];
             warnings_tag = None};
           type_ =
            Odoc_xref2.Component.Module.ModuleType
             (Odoc_xref2.Component.ModuleType.Path
               {Odoc_xref2.Component.ModuleType.p_expansion = None;
                p_path =
                 `DotMT (`Substituted (`Local (`LModule (M, 31), false)), S)});
           canonical = None; hidden = false};
        get = None})];
    compiled = false; removed = [];
    doc = {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None}}

and we can see the module M is now an alias of the root module B. We can now look up module N from within this and find its signature:

# let m = get_ok @@ Tools.lookup_module env
      (`Module (`Module (`Gpath (`Identifier (Common.root_module "C"))), ModuleName.make_std "N"));;
val m : Component.Module.t Component.Delayed.t =
  {Odoc_xref2.Component.Delayed.v =
    Some
     {Odoc_xref2.Component.Module.source_loc = None;
      doc =
       {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
      type_ =
       Odoc_xref2.Component.Module.ModuleType
        (Odoc_xref2.Component.ModuleType.Path
          {Odoc_xref2.Component.ModuleType.p_expansion = None;
           p_path =
            `DotMT
              (`Substituted
                 (`Module
                    (`Module
                       (`Gpath
                          (`Identifier
                             {Odoc_model__Paths_types.iv =
                               `Module
                                 ({Odoc_model__Paths_types.iv =
                                    `Root
                                      (Some
                                        {Odoc_model__Paths_types.iv =
                                          `Page (None, None);
                                         ihash = 236059787; ikey = "p_None"},
                                       Root);
                                   ihash = 818126955; ikey = "r_Root.p_None"},
                                  C);
                              ihash = 43786577; ikey = "m_C.r_Root.p_None"})),
                     M)),
               S)});
      canonical = None; hidden = false};
   get = None}
# get_ok @@ Tools.expansion_of_module env (Component.Delayed.get m);;
- : Tools.expansion =
Odoc_xref2.Tools.Signature
 {Odoc_xref2.Component.Signature.items =
   [Odoc_xref2.Component.Signature.Type (`LType (t, 41),
     Odoc_model.Lang.Signature.Ordinary,
     {Odoc_xref2.Component.Delayed.v =
       Some
        {Odoc_xref2.Component.TypeDecl.source_loc = None;
         doc =
          {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None};
         canonical = None;
         equation =
          {Odoc_xref2.Component.TypeDecl.Equation.params = [];
           private_ = false; manifest = None; constraints = []};
         representation = None};
      get = None})];
  compiled = false; removed = [];
  doc = {Odoc_xref2.Component.CComment.elements = []; warnings_tag = None}}

where we've correctly identified that a type t exists in the signature. The path in type t is resolved as:

# Common.LangUtils.Lens.get t_manifest resolved;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Module
            (`Identifier
               {Odoc_model__Paths_types.iv =
                 `Module
                   ({Odoc_model__Paths_types.iv =
                      `Root
                        (Some
                          {Odoc_model__Paths_types.iv = `Page (None, None);
                           ihash = 236059787; ikey = "p_None"},
                         Root);
                     ihash = 818126955; ikey = "r_Root.p_None"},
                    C);
                ihash = 43786577; ikey = "m_C.r_Root.p_None"},
             N),
          t)),
   []))

Interesting functor#

let test_data = {|
module M : sig
  module F(X : sig module type S end) : sig
    module type S = X.S
    module N : X.S
  end
  module T : sig
    module type S = sig type t end
  end
  module O : F(T).S
end
type t = M.O.t
type s = M.F(M.T).N.t
|};;
let sg = Common.signature_of_mli_string test_data;;
let t_manifest = type_manifest "t";;
let s_manifest = type_manifest "s";;
let resolved = Common.compile_signature sg;;

The interesting thing here is the difference between type t and type s. The module M.O has a concrete representation in the file and the expansion of this will contain a declaration of type t - hence the path representing M.O.t does not need a Subst constructor in it. However, the path to M.F(M.T).N.t can't point directly at a type within a module as there isn't one - in some sense F(M.T) is making a brand new module on the fly without binding it anywhere, and the type within this is not within the body of the functor itself.

# Common.LangUtils.Lens.get (type_manifest "t") resolved;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Subst
            (`AliasModuleType
               (`ModuleType
                  (`Substituted
                     (`Module
                        (`Identifier
                           {Odoc_model__Paths_types.iv =
                             `Module
                               ({Odoc_model__Paths_types.iv =
                                  `Root
                                    (Some
                                      {Odoc_model__Paths_types.iv =
                                        `Page (None, None);
                                       ihash = 236059787; ikey = "p_None"},
                                     Root);
                                 ihash = 818126955; ikey = "r_Root.p_None"},
                                M);
                            ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                         T)),
                   S),
                `SubstT
                  (`ModuleType
                     (`Substituted
                        (`Module
                           (`Identifier
                              {Odoc_model__Paths_types.iv =
                                `Module
                                  ({Odoc_model__Paths_types.iv =
                                     `Root
                                       (Some
                                         {Odoc_model__Paths_types.iv =
                                           `Page (None, None);
                                          ihash = 236059787; ikey = "p_None"},
                                        Root);
                                    ihash = 818126955;
                                    ikey = "r_Root.p_None"},
                                   M);
                               ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                            T)),
                      S),
                   `ModuleType
                     (`Apply
                        (`Module
                           (`Identifier
                              {Odoc_model__Paths_types.iv =
                                `Module
                                  ({Odoc_model__Paths_types.iv =
                                     `Root
                                       (Some
                                         {Odoc_model__Paths_types.iv =
                                           `Page (None, None);
                                          ihash = 236059787; ikey = "p_None"},
                                        Root);
                                    ihash = 818126955;
                                    ikey = "r_Root.p_None"},
                                   M);
                               ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                            F),
                         `Module
                           (`Identifier
                              {Odoc_model__Paths_types.iv =
                                `Module
                                  ({Odoc_model__Paths_types.iv =
                                     `Root
                                       (Some
                                         {Odoc_model__Paths_types.iv =
                                           `Page (None, None);
                                          ihash = 236059787; ikey = "p_None"},
                                        Root);
                                    ihash = 818126955;
                                    ikey = "r_Root.p_None"},
                                   M);
                               ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                            T)),
                      S))),
             `Module
               (`Identifier
                  {Odoc_model__Paths_types.iv =
                    `Module
                      ({Odoc_model__Paths_types.iv =
                         `Root
                           (Some
                             {Odoc_model__Paths_types.iv = `Page (None, None);
                              ihash = 236059787; ikey = "p_None"},
                            Root);
                        ihash = 818126955; ikey = "r_Root.p_None"},
                       M);
                   ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                O)),
          t)),
   []))
# Common.LangUtils.Lens.get (type_manifest "s") resolved;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Subst
            (`ModuleType
               (`Substituted
                  (`Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      T)),
                S),
             `Module
               (`Apply
                  (`Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      F),
                   `Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      T)),
                N)),
          t)),
   []))

In the following example, type t does not require a Subst constructor since although the pattern is the same as above -- that a new type t appears in module O despite not being present in the definition of the functor -- because the module O is bound it will be expanded in the expansion phase of odoc's work, and hence we can simply point right inside the module.

We distinguish between the two cases via the is_resolve parameter, which is true when we are directly resolving a path, but false when we simply wish to look up the signature of a module.

let test_data = {|
module M : sig
  module F(X : sig module type S end) : sig
    module type S = sig
      module N : X.S
    end
  end
  module T : sig
    module type S = sig type t end
  end
  module O : F(T).S
end
type t = M.O.N.t
|}
let sg = Common.signature_of_mli_string test_data;;
let env = Env.open_signature sg Env.empty;;
let resolved = Common.compile_signature sg;;

# Common.LangUtils.Lens.get t_manifest resolved;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Subst
            (`ModuleType
               (`Substituted
                  (`Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      T)),
                S),
             `Module
               (`Module
                  (`Identifier
                     {Odoc_model__Paths_types.iv =
                       `Module
                         ({Odoc_model__Paths_types.iv =
                            `Root
                              (Some
                                {Odoc_model__Paths_types.iv =
                                  `Page (None, None);
                                 ihash = 236059787; ikey = "p_None"},
                               Root);
                           ihash = 818126955; ikey = "r_Root.p_None"},
                          M);
                      ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                   O),
                N)),
          t)),
   []))

This following example also shouldn't have a Subst, since although as before we're effectively constructing a new module M.O(M) on the fly here, the subsequent path .N.t is actually present in the body of the functor and is independent of the argument (in fact, the argument in this case is totally ignored). Consequently the resolution proceeds without encountering a Substituted node and we therefore don't end up putting a Subst node in the returned path.

let test_data = {|
module M : sig
  module F(X : sig module type S end) : sig
    module type S = sig
      module N : X.S
    end
  end
  module T : sig
    module type S = sig type t end
  end
  module O : functor (X : sig end) -> F(T).S
end
type t = M.O(M.T).N.t
|}
let sg = Common.signature_of_mli_string test_data;;
let env = Env.open_signature sg Env.empty;;
let resolved = Common.compile_signature sg;;

# Common.LangUtils.Lens.get t_manifest resolved;;
- : Odoc_model.Lang.TypeExpr.t option =
Some
 (Odoc_model.Lang.TypeExpr.Constr
   (`Resolved
      (`Type
         (`Subst
            (`ModuleType
               (`Substituted
                  (`Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      T)),
                S),
             `Module
               (`Apply
                  (`Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      O),
                   `Module
                     (`Identifier
                        {Odoc_model__Paths_types.iv =
                          `Module
                            ({Odoc_model__Paths_types.iv =
                               `Root
                                 (Some
                                   {Odoc_model__Paths_types.iv =
                                     `Page (None, None);
                                    ihash = 236059787; ikey = "p_None"},
                                  Root);
                              ihash = 818126955; ikey = "r_Root.p_None"},
                             M);
                         ihash = 716453475; ikey = "m_M.r_Root.p_None"},
                      T)),
                N)),
          t)),
   []))