1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
(** This module provide a way to transform a type into strings, in such a way
that the strings can be used for type search.
The chosen representation is polarity : we do not represent the [->] or the [*]
constructors, but instead compute the "polarity" of every type name/constructor
like [int] or ['a] that is part of the whole type expression.
The polarity of a component of a type indicates if it is produced or consumed by
the type. In the type [int -> string], [int] has negative polarity because it is
being consumed, and [string] has positive polarity because it is being produced.
We say that the polarities of [int -> string] are [-int] and [+string].
Once you have computed the polarities of the type of an entry [e], you can
register each polarity as corresponding to [e] in the search database.
Then, when the user queries for a type, we compute the polarities of the query
type, and search for the entries.
We then return the result corresponding to intersection of each polarity: if the
user queries for [int -> string], we want to have every entry which consumes an
[int] and produces a [string], that is the intersection of the entries
associated to [-int] with the entries associated to [+string].
How is polarity computed exactly ? When you have [t -> u], the polarity of [t]
is inversed, and the polarity of [u] stays the same. A good example of this is
the type of {!Stdlib.Out_channel.with_open_gen} :
{[
val with_open_gen : open_flag list -> int -> string -> (t -> 'a) -> 'a
]}
Here the polarities are [-open_flag list], [-int], [-string], [+Out_channel.t],
[-'a] and [+'a]. The fact that we have [+Out_channel.t] might be puzzling at
first, because an [Out_channel.t] is not returned by the function, but
{!Stdlib.Out_channel.with_open_gen} is indeed one of the possible ways to create
an [Out_channel.t].
There is however a complication. If the user queries for [int -> int -> string],
then the polarities will be [-int], [-int] and [+string]. An entry of type [int
tring] would be included in the intersection of these polarities. But the
user explicitely asked for two integers to be consumed. To fix this issue, we
track the number of occurences of each polarity.
The polarities for [int -> int -> string], become [(-int, 2)] and [(+string, 1)]
and allows us to filter entries according to this information.
There is a mechanism for types with parameters like ['a list]. I might explain
it in the future.
TODO : Give an example even if not the full explanation. *)
module Sign : sig
type t =
| Pos
| Neg
val to_string : t -> string
val not : t -> t
end
type t = string * int * Sign.t
(** The search database is a suffix tree structure, implemented in
{!Suffix_tree}. It is a solely text-based datastructure. Therefore, we need
a text represention for the polarities.
The polarity [+t] is represented by ["+t"], and the polarity [-t] is
represented by ["-t"].
The fact that the sign is in the front is important : ["+flo"] is a prefix of
["+float"], but ["flo+"] is not a prefix nor a suffix of ["float+"]. This
allows to answer incomplete queries.
The integer represents the occurences of the polarity, as explained in the
toplevel documentation of the module. *)
val of_typ : any_is_poly:bool -> Typexpr.t -> t Seq.t
(** [of_typ ~ignore_any ~all_names typ] is the list of polarised types
corresponding to [typ].
- If [any_is_poly] is true, the type [_] will be treated like a type variable
['a], otherwise it will be represented solely by its sign ("+" or "-"). *)
val poly : string
|
