Type-directed API search

[ghost]

This is a feature request.

It would be really nice if Merlin could perform Coq-like type-directed searches, similar to what SearchPattern does in Coq.

The main use case I would have for this feature would be to query "which functions can produce a type M.t"? Or "which functions use this type M.t"? All that in the context of a large code base where the user needs a value of type C.t and he knows that function f: A.t -> B.t -> C.t exists, but then he wonders how to produce a B.t in order to give it to f, and then he finds out after much effort that a function g: D.t -> B.t exists, but then he has to find out how to obtain a D.t...

Here's an example, adapted from the Coq reference manual:

# open NPeano;;
# SearchPattern (nat -> bool);;
NPeano.testbit: nat -> nat -> bool
NPeano.odd: nat -> bool
leb: nat -> nat -> bool
NPeano.even: nat -> bool
beq_nat: nat -> nat -> bool

Note that, in Coq's case, trying to match nat -> bool will produce results including nat -> nat -> bool as well, which may or may not be useful (it might return too many results).

In Coq's SearchPattern, the underscore character is used as a sort of "wildcard", when the user does not care about which types to consider. Here's a fictitious example using OCaml's Int32:

# open Int32;;
# SearchPattern (_ -> int32);; (* how can I obtain a value of type int32? *)
Int32.zero : int32 (* in a more "strict" setting, this would not be returned*)
Int32.one : int32
...
Int32.neg : int32 -> int32
Int32.add : int32 -> int32 -> int32
....
Int32.to_string : int32 -> string
Int32.bits_of_float : float -> int32

Polymorphic types may or may not be an issue (in terms of syntax):

# SearchPattern (_ -> 'a Stack.t);; (* how to construct a Stack.t ? *)
Stack.create: unit -> 'a Stack.t
Stack.copy: 'a Stack.t -> 'a Stack.t
# SearchPattern (_ -> _ list) (* which functions produce lists of any kind? *)
...

Other queries might involve specific modules:

# SearchPattern (string) inside Int32;; (* which functions in Int32 are related to strings? *)
Int32.of_string : string -> int32
Int32.to_string : int32 -> string

In principle, this last use case might be dealt with by directly grepping the .ml/.mli file. However, if there are included modules coming from other files, or modules which are only part of a given file, querying would be faster than grepping each of them.

I have no idea what should be done with variant types or objects, since I rarely use them.

Note that this is almost exactly what ocamloscope does, but that project seems to have had little development lately, and it requires building a database which might require recompiling OPAM packages, etc. In principle Merlin already knows which files to look at (those in .merlin), and it already parses the files anyway, so in theory (from a very naive point of view), it would just need to store the type information for the parsed functions in a mini-database and make it accessible via queries.

Finally, note that while the generic SearchPattern might be very complicated, specialized queries such as produces-type <type-pattern> or uses-type <type-pattern> would already be very handy and possibly much simpler to code.

[let-def]

The branch experimental-polarity implements such feature, but there is not yet any user-interface.

The query language use variance of types to direct the search, e.g. "-string +int" finds a way to produce an int from a string. It is limited to type constructors at the current time, no objects nor variants.

Do you have any suggestion on the GUI to put above that?

[hcarty]

A useful start would be equivalent to the vim interface's :MerlinTypeOf <expr>

[let-def]

What about the results?
TypeOf displays a single result (though you can navigate), here we have should expect lists of non-negligible size (same size as completion).

... Sublime text will be the less painful to bind to such feature :).

[gasche]

This would suggest the following interface:

• the user writes the query directly in the buffer, selects it, and runs the command
• the command results are presented as a completion list
• if one completion option is chosen, it replaces the query, otherwise the selection is left as-is

[let-def]

I opened #612 to track my developments related to this feature.

[SamB]

Since this sounds a lot like Hoogle (but, you know, not for Haskell), https://github.com/ndmitchell/hoogle/ might be a good source of user interfaces to rip off
– excuse me – use or take inspiration from. (Or maybe just do a web search for integrations for whatever religion – I mean, development environment.)

[xvw]

Almot 9 years after, tada: #1828
I think we can close the ticket?