Re: [Caml-list] Is there an efficient precise ocamldep - Was: why is building ocaml hard?

["Petter A. Urkedal" <paurkedal@gmail.com>]

On 10 July 2016 at 13:33, Gerd Stolpmann <info@gerd-stolpmann.de> wrote:
> 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?

I think at least we can reduce upper bound for number of iteration
from n! to n(n-1)/2 by observing that once we find a module which is
successfully analysed, we can keep it for the next iteration:  The a
pass over n local files will either succeed in finding a module which
is successfully analysed, leaving n - 1 to be analysed, or fail, in
which case the dependencies are unsatifiable.