Rephrasing this question. Given we wanted to develop an improved version
of ocamldep that (a) reads in cmi files from non-project-local
directories, and (b) processes all files of the project as a whole, and
(c) outputs dependencies precisely. Is there an algorithm that is better
than

- for all permutations p of the project files:
  - env := <modules defined in the non-project-local cmi files>
  - for all files f of p:
    - localenv := []
    - AST := parse f
    - interpret the module calculus of the AST, taking env
      (the toplevel modules) and localenv (the local module
      scope) into account, with these details:
       * if there is an unknown module identifier this is an
         error, and we go on with the next permutation
       * any definition of a module modifies localenv
       * the "open" directive is interpreted strictly using
         env and localenv
    - no error yet:
      - env := env + (f -> localenv)
        (i.e. add the module corresponding to the file to env)
 - if there is a permutation p that doesn't run into an error,
   re-run the dependency analyzer for p and output the deps
   between the (now unambiguously identified) toplevel modules
   (the keys of env)

I think this algorithm is a precise solution to the ocamldep problem
(well, I did not take mli files into account, but that shouldn't be too
difficult to add). However, it is horribly inefficient. Is there
anything better?

Gerd


Am Sonntag, den 10.07.2016, 13:03 +0200 schrieb Gerd Stolpmann:
> Let's have a closer look why it is relatively error-prone to extract the
> dependencies. The tool in question is ocamldep. It is fairly dumb in so
> far it is only parsing the source code, and then looks at all
> module-related constructs (open, include, module, etc.). Because it
> never looks into already compiled interfaces and also proceeds file by
> file, it may sometimes emit wrong dependency information. For example,
> when there is
> 
> open M1
> open M2
> 
> at the beginning of a file, ocamldep doesn't know whether M2 is another
> top-level module, or whether it is a submodule of M1. ocamldep normally
> errs on the side of generating too many dependencies, which is then
> tried to be corrected by only accepting those deps corresponding to
> existing files. In this example, this would mean that a dependency to M2
> is emitted when there is a file M2.ml. Note that this is wrong when M2
> is actually a submodule of M1 AND the file M2.ml exists.
> 
> So how to fix this? In my opinion there are two solutions. You can
> either have a more intelligent ocamldep (e.g. one that reads in
> non-local cmi files and uses that information and also tries to
> interpret all project ml files at once and not file by file - btw, did
> anybody check whether there is an algorithm that precisely solves the
> problem?). The other solution path is to mark toplevel modules in the
> syntax of OCaml (e.g. you'd have to do "open ^M2" is M2 is a toplevel
> module).
-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------