]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/cic/discrimination_tree.ml
- transcript: patched to generate CoRN_notation.ma instead of CoRN.ma
[helm.git] / helm / software / components / cic / discrimination_tree.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 module DiscriminationTreeIndexing =  
29   functor (A:Set.S) -> 
30     struct
31
32       type path_string_elem = 
33         | Function | Constant of UriManager.uri 
34         | Bound of int | Variable | Proposition | Datatype ;;
35       type path_string = path_string_elem list;;
36
37
38       (* needed by the retrieve_* functions, to know the arities of the
39        * "functions" *)
40       
41       let ppelem = function
42         | Function -> "Fun"
43         | Constant uri -> UriManager.name_of_uri uri
44         | Bound i -> string_of_int i
45         | Variable -> "?"
46         | Proposition -> "Prop"
47         | Datatype -> "Type"
48       ;;
49       let pppath l = String.concat "::" (List.map ppelem l) ;;
50       let elem_of_cic = function
51         | Cic.Meta _ -> Variable
52         | Cic.Lambda _ -> Function
53         | Cic.Rel i -> Bound i
54         | Cic.Sort (Cic.Prop) -> Proposition
55         | Cic.Sort _ -> Datatype
56         | term ->
57             try Constant (CicUtil.uri_of_term term)
58             with Invalid_argument _ -> Variable (* HACK! *)
59       ;;
60       let path_string_of_term arities = 
61         let set_arity n = function
62           | Variable -> Hashtbl.replace arities Variable 0
63           | e -> Hashtbl.replace arities e n
64         in
65         let rec aux = function
66           | Cic.Appl ((hd::tl) as l) ->
67 (*
68               if Hashtbl.mem arities (elem_of_cic hd) then
69                 begin
70                   let n = Hashtbl.find arities (elem_of_cic hd) in
71                   if n <> List.length tl then
72                     begin
73                       prerr_endline 
74                         (String.concat " " 
75                           (List.map (fun x -> ppelem (elem_of_cic x)) l))
76                     end;
77                   assert(n = List.length tl)
78                 end;
79 *)
80               set_arity (List.length tl) (elem_of_cic hd);
81 (*               Hashtbl.replace arities (elem_of_cic hd) (List.length tl); *)
82               List.concat (List.map aux l)
83           | t -> [elem_of_cic t]
84         in 
85           aux
86       ;;
87       let compare_elem e1 e2 =
88         match e1,e2 with
89         | Constant u1,Constant u2 -> UriManager.compare u1 u2
90         | e1,e2 -> Pervasives.compare e1 e2
91       ;;
92
93       module OrderedPathStringElement = struct
94         type t = path_string_elem
95         let compare = compare_elem
96       end
97
98       module PSMap = Map.Make(OrderedPathStringElement);;
99
100       type key = PSMap.key
101
102       module DiscriminationTree = Trie.Make(PSMap);;
103
104       type t = A.t DiscriminationTree.t * (path_string_elem, int) Hashtbl.t
105       let empty = DiscriminationTree.empty, Hashtbl.create 11;;
106
107 (*
108       module OrderedPosEquality = struct
109         type t = Utils.pos * Inference.equality
110         let compare = Pervasives.compare
111       end
112
113       module PosEqSet = Set.Make(OrderedPosEquality);;
114
115       let string_of_discrimination_tree tree =
116         let rec to_string level = function
117           | DiscriminationTree.Node (value, map) ->
118               let s =
119                 match value with
120                   | Some v ->
121                       (String.make (2 * level) ' ') ^
122                         "{" ^ (String.concat "; "
123                                  (List.map
124                                     (fun (p, e) ->
125                                        "(" ^ (Utils.string_of_pos p) ^ ", " ^ 
126                                          (Inference.string_of_equality e) ^ ")")
127                                     (PosEqSet.elements v))) ^ "}"
128                   | None -> "" 
129               in
130               let rest =
131                 String.concat "\n"
132                   (PSMap.fold
133                      (fun k v s ->
134                         let ks = CicPp.ppterm k in
135                         let rs = to_string (level+1) v in
136                           ((String.make (2 * level) ' ') ^ ks ^ "\n" ^ rs)::s)
137                      map [])
138               in
139                 s ^ rest
140         in
141           to_string 0 tree
142       ;;
143 *)
144
145       let index (tree,arity) term info =
146         let ps = path_string_of_term arity term in
147         let ps_set =
148           try DiscriminationTree.find ps tree 
149           with Not_found -> A.empty in
150         let tree = DiscriminationTree.add ps (A.add info ps_set) tree in
151         tree,arity
152       ;;
153
154 (*
155       let index tree equality =
156         let _, _, (_, l, r, ordering), _, _ = equality in
157         let psl = path_string_of_term l
158         and psr = path_string_of_term r in
159         let index pos tree ps =
160           let ps_set =
161             try DiscriminationTree.find ps tree with Not_found -> PosEqSet.empty in
162           let tree =
163             DiscriminationTree.add ps (PosEqSet.add (pos, equality) ps_set) tree in
164             tree
165         in
166           match ordering with
167             | Utils.Gt -> index Utils.Left tree psl
168             | Utils.Lt -> index Utils.Right tree psr
169             | _ ->
170                 let tree = index Utils.Left tree psl in
171                   index Utils.Right tree psr
172       ;;
173 *)
174
175       let remove_index (tree,arity) term info =
176         let ps = path_string_of_term arity term in
177         try
178           let ps_set = A.remove info (DiscriminationTree.find ps tree) in
179           if A.is_empty ps_set then
180             DiscriminationTree.remove ps tree,arity
181           else
182             DiscriminationTree.add ps ps_set tree,arity
183         with Not_found ->
184           tree,arity
185       ;;
186
187 (*
188 let remove_index tree equality =
189   let _, _, (_, l, r, ordering), _, _ = equality in
190   let psl = path_string_of_term l
191   and psr = path_string_of_term r in
192   let remove_index pos tree ps =
193     try
194       let ps_set =
195         PosEqSet.remove (pos, equality) (DiscriminationTree.find ps tree) in
196       if PosEqSet.is_empty ps_set then
197         DiscriminationTree.remove ps tree
198       else
199         DiscriminationTree.add ps ps_set tree
200     with Not_found ->
201       tree
202   in
203   match ordering with
204   | Utils.Gt -> remove_index Utils.Left tree psl
205   | Utils.Lt -> remove_index Utils.Right tree psr
206   | _ ->
207       let tree = remove_index Utils.Left tree psl in
208       remove_index Utils.Right tree psr
209 ;;
210 *)
211
212
213       let in_index (tree,arity) term test =
214         let ps = path_string_of_term arity term in
215         try
216           let ps_set = DiscriminationTree.find ps tree in
217           A.exists test ps_set
218         with Not_found ->
219           false
220       ;;
221
222 (*
223       let in_index tree equality =
224         let _, _, (_, l, r, ordering), _, _ = equality in
225         let psl = path_string_of_term l
226         and psr = path_string_of_term r in
227         let meta_convertibility = Inference.meta_convertibility_eq equality in
228         let ok ps =
229           try
230             let set = DiscriminationTree.find ps tree in
231               PosEqSet.exists (fun (p, e) -> meta_convertibility e) set
232           with Not_found ->
233             false
234         in
235           (ok psl) || (ok psr)
236 ;;
237 *)
238
239
240       let head_of_term = function
241         | Cic.Appl (hd::tl) -> hd
242         | term -> term
243       ;;
244
245       let rec skip_prods = function
246         | Cic.Prod (_,_,t) -> skip_prods t
247         | term -> term
248       ;;
249
250       let rec subterm_at_pos pos term =
251         match pos with
252           | [] -> term
253           | index::pos ->
254               match term with
255                 | Cic.Appl l ->
256                     (try subterm_at_pos pos (List.nth l index)
257                      with Failure _ -> raise Not_found)
258                 | _ -> raise Not_found
259       ;;
260
261
262       let rec after_t pos term =
263         let pos' =
264           match pos with
265             | [] -> raise Not_found
266             | pos -> 
267                 List.fold_right 
268                   (fun i r -> if r = [] then [i+1] else i::r) pos []
269         in
270           try
271             ignore(subterm_at_pos pos' term ); pos'
272           with Not_found ->
273             let pos, _ =
274               List.fold_right
275                 (fun i (r, b) -> if b then (i::r, true) else (r, true))
276                 pos ([], false)
277             in
278               after_t pos term
279       ;;
280
281
282       let next_t pos term =
283         let t = subterm_at_pos pos term in
284           try
285             let _ = subterm_at_pos [1] t in
286               pos @ [1]
287           with Not_found ->
288             match pos with
289               | [] -> [1]
290               | pos -> after_t pos term
291       ;;     
292
293       let retrieve_generalizations (tree,arity) term =
294         let term = skip_prods term in
295         let rec retrieve tree term pos =
296           match tree with
297             | DiscriminationTree.Node (Some s, _) when pos = [] -> s
298             | DiscriminationTree.Node (_, map) ->
299                 let res =
300                   let hd_term = 
301                     elem_of_cic (head_of_term (subterm_at_pos pos term)) 
302                   in
303                   if hd_term = Variable then A.empty else
304                   try
305                     let n = PSMap.find hd_term map in
306                       match n with
307                         | DiscriminationTree.Node (Some s, _) -> s
308                         | DiscriminationTree.Node (None, _) ->
309                             let newpos = 
310                               try next_t pos term 
311                               with Not_found -> [] 
312                             in
313                               retrieve n term newpos
314                   with Not_found ->
315                     A.empty
316                 in
317                   try
318                     let n = PSMap.find Variable map in
319                     let newpos = try after_t pos term with Not_found -> [-1] in
320                       if newpos = [-1] then
321                         match n with
322                           | DiscriminationTree.Node (Some s, _) -> A.union s res
323                           | _ -> res
324                       else
325                         A.union res (retrieve n term newpos)
326                   with Not_found ->
327                     res
328         in
329           retrieve tree term []
330       ;;
331
332
333       let jump_list arities = function
334         | DiscriminationTree.Node (value, map) ->
335             let rec get n tree =
336               match tree with
337                 | DiscriminationTree.Node (v, m) ->
338                     if n = 0 then
339                       [tree]
340                     else
341                       PSMap.fold
342                         (fun k v res ->
343                            let a = 
344                              try Hashtbl.find arities k 
345                              with Not_found -> 0 
346                            in
347                              (get (n-1 + a) v) @ res) m []
348             in
349               PSMap.fold
350                 (fun k v res ->
351                    let arity = try Hashtbl.find arities k with Not_found -> 0 in
352                      (get arity v) @ res)
353                 map []
354       ;;
355
356
357       let retrieve_unifiables (tree,arities) term =
358         let term = skip_prods term in
359         let rec retrieve tree term pos =
360           match tree with
361             | DiscriminationTree.Node (Some s, _) when pos = [] -> s
362             | DiscriminationTree.Node (_, map) ->
363                 let subterm =
364                   try Some (subterm_at_pos pos term) with Not_found -> None
365                 in
366                 match subterm with
367                 | None -> A.empty
368                 | Some (Cic.Meta _) ->
369                       let newpos = try next_t pos term with Not_found -> [] in
370                       let jl = jump_list arities tree in
371                         List.fold_left
372                           (fun r s -> A.union r s)
373                           A.empty
374                           (List.map (fun t -> retrieve t term newpos) jl)
375                   | Some subterm ->
376                       let res = 
377                         let hd_term = elem_of_cic (head_of_term subterm) in
378                         if hd_term = Variable then A.empty else
379                         try
380                           let n = PSMap.find hd_term map in
381                             match n with
382                               | DiscriminationTree.Node (Some s, _) -> s
383                               | DiscriminationTree.Node (None, _) ->
384                                   retrieve n term (next_t pos term)
385                         with Not_found ->
386                           A.empty
387                       in
388                         try
389                           let n = PSMap.find Variable map in
390                           let newpos = 
391                             try after_t pos term 
392                             with Not_found -> [-1] 
393                           in
394                             if newpos = [-1] then
395                               match n with
396                                 | DiscriminationTree.Node (Some s, _) -> 
397                                     A.union s res
398                                 | _ -> res
399                             else
400                               A.union res (retrieve n term newpos)
401                         with Not_found ->
402                           res
403       in
404         retrieve tree term []
405   end
406 ;;
407