]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/cic/path_indexing.ml
short names
[helm.git] / helm / software / components / cic / path_indexing.ml
1 (* Copyright (C) 2005, HELM Team.
2  * 
3  * This file is part of HELM, an Hypertextual, Electronic
4  * Library of Mathematics, developed at the Computer Science
5  * Department, University of Bologna, Italy.
6  * 
7  * HELM is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  * 
12  * HELM is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with HELM; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20  * MA  02111-1307, USA.
21  * 
22  * For details, see the HELM World-Wide-Web page,
23  * http://cs.unibo.it/helm/.
24  *)
25
26 (* $Id$ *)
27
28 (* path indexing implementation *)
29
30 (* position of the subterm, subterm (Appl are not stored...) *)
31
32 module PathIndexing =
33   functor(A:Set.S) -> 
34     struct
35
36 type path_string_elem = Index of int | Term of Cic.term;;
37 type path_string = path_string_elem list;; 
38
39
40 let rec path_strings_of_term index =
41   let module C = Cic in function
42   | C.Meta _ -> [ [Index index; Term (C.Implicit None)] ]
43   | C.Appl (hd::tl) ->
44       let p = if index > 0 then [Index index; Term hd] else [Term hd] in
45       let _, res = 
46         List.fold_left
47           (fun (i, r) t ->
48              let rr = path_strings_of_term i t in
49              (i+1, r @ (List.map (fun ps -> p @ ps) rr)))
50           (1, []) tl
51       in
52       res
53   | term -> [ [Index index; Term term] ]
54 ;;
55
56 (*
57 let string_of_path_string ps =
58   String.concat "."
59     (List.map
60        (fun e ->
61           let s =
62             match e with
63             | Index i -> "Index " ^ (string_of_int i)
64             | Term t -> "Term " ^ (CicPp.ppterm t)
65           in
66           "(" ^ s ^ ")")
67        ps)
68 ;;  
69 *)
70
71 module OrderedPathStringElement = struct
72   type t = path_string_elem
73
74   let compare t1 t2 =
75     match t1, t2 with
76     | Index i, Index j -> Pervasives.compare i j
77     | Term t1, Term t2 -> if t1 = t2 then 0 else Pervasives.compare t1 t2
78     | Index _, Term _ -> -1
79     | Term _, Index _ -> 1
80 end
81
82 module PSMap = Map.Make(OrderedPathStringElement);;
83
84 module PSTrie = Trie.Make(PSMap);;
85
86 type t = A.t PSTrie.t
87 type key = Cic.term
88 let empty = PSTrie.empty
89 let arities = Hashtbl.create 0
90
91 let index trie term info =
92   let ps = path_strings_of_term 0 term in
93   List.fold_left 
94   (fun trie ps ->
95      let ps_set = try PSTrie.find ps trie with Not_found -> A.empty in
96      let trie = PSTrie.add ps (A.add info ps_set) trie in
97        trie) trie ps
98
99 let remove_index trie term info=
100   let ps = path_strings_of_term 0 term in
101   List.fold_left
102     (fun trie ps ->
103        try
104         let ps_set = A.remove info (PSTrie.find ps trie) in
105         if A.is_empty ps_set then
106           PSTrie.remove ps trie
107         else
108           PSTrie.add ps ps_set trie
109        with Not_found -> trie) trie ps
110 ;;
111
112 let in_index trie term test =
113   let ps = path_strings_of_term 0 term in
114   let ok ps =
115     try
116       let set = PSTrie.find ps trie in
117         A.exists test set
118     with Not_found ->
119       false
120   in
121   List.exists ok ps
122 ;;
123
124
125 let head_of_term = function
126   | Cic.Appl (hd::tl) -> hd
127   | term -> term
128 ;;
129
130
131 let subterm_at_pos index term =
132   if index = 0 then
133     term
134   else
135     match term with
136     | Cic.Appl l ->
137         (try List.nth l index with Failure _ -> raise Not_found)
138     | _ -> raise Not_found
139 ;;
140
141
142 let rec retrieve_generalizations trie term =
143   match trie with
144   | PSTrie.Node (value, map) ->
145       let res = 
146         match term with
147         | Cic.Meta _ -> A.empty
148         | term ->
149             let hd_term = head_of_term term in
150             try
151               let n = PSMap.find (Term hd_term) map in
152               match n with
153               | PSTrie.Node (Some s, _) -> s
154               | PSTrie.Node (None, m) ->
155                   let l = 
156                     PSMap.fold
157                       (fun k v res ->
158                          match k with
159                          | Index i ->
160                              let t = subterm_at_pos i term in
161                              let s = retrieve_generalizations v t in
162                              s::res
163                          | _ -> res)
164                       m []
165                   in
166                   match l with
167                   | hd::tl ->
168                       List.fold_left (fun r s -> A.inter r s) hd tl
169                   | _ -> A.empty
170             with Not_found ->
171               A.empty
172       in
173       try
174         let n = PSMap.find (Term (Cic.Implicit None)) map in
175         match n with
176         | PSTrie.Node (Some s, _) -> A.union res s
177         | _ -> res
178       with Not_found ->
179         res
180 ;;
181
182
183 let rec retrieve_unifiables trie term =
184   match trie with
185   | PSTrie.Node (value, map) ->
186       let res = 
187         match term with
188         | Cic.Meta _ ->
189             PSTrie.fold
190               (fun ps v res -> A.union res v)
191               (PSTrie.Node (None, map))
192               A.empty
193         | _ ->
194             let hd_term = head_of_term term in
195             try
196               let n = PSMap.find (Term hd_term) map in
197               match n with
198               | PSTrie.Node (Some v, _) -> v
199               | PSTrie.Node (None, m) ->
200                   let l = 
201                     PSMap.fold
202                       (fun k v res ->
203                          match k with
204                          | Index i ->
205                              let t = subterm_at_pos i term in
206                              let s = retrieve_unifiables v t in
207                              s::res
208                          | _ -> res)
209                       m []
210                   in
211                   match l with
212                   | hd::tl ->
213                       List.fold_left (fun r s -> A.inter r s) hd tl
214                   | _ -> A.empty
215             with Not_found ->
216               A.empty
217       in
218       try
219         let n = PSMap.find (Term (Cic.Implicit None)) map in
220         match n with
221         | PSTrie.Node (Some s, _) -> A.union res s
222         | _ -> res
223       with Not_found ->
224         res
225 ;;
226
227 end