2 ||M|| This file is part of HELM, an Hypertextual, Electronic
3 ||A|| Library of Mathematics, developed at the Computer Science
4 ||T|| Department, University of Bologna, Italy.
6 ||T|| HELM is free software; you can redistribute it and/or
7 ||A|| modify it under the terms of the GNU General Public License
8 \ / version 2 or (at your option) any later version.
9 \ / This software is distributed as is, NO WARRANTY.
10 V_______________________________________________________________ *)
14 type path_string_elem =
15 | Constant of NUri.uri
23 type path_string = path_string_elem list;;
26 | Constant uri -> NUri.name_of_uri uri
27 | Bound i -> string_of_int i
29 | Proposition -> "Prop"
32 "DEAD("^NCicPp.ppterm ~context:[] ~subst:[] ~metasenv:[] t^")"
35 let pp_path_string l = String.concat "::" (List.map ppelem l) ;;
37 let elem_of_cic = function
38 | NCic.Meta _ | NCic.Implicit _ -> Variable
39 | NCic.Rel i -> Bound i
40 | NCic.Sort (NCic.Prop) -> Proposition
41 | NCic.Sort _ -> Datatype
42 | NCic.Const (NReference.Ref (u,_)) -> Constant u
43 | NCic.Appl _ -> assert false (* should not happen *)
44 | NCic.LetIn _ | NCic.Lambda _ | NCic.Prod _ | NCic.Match _ as t ->
46 "FIXME: the discrimination tree receives an invalid term";
50 let path_string_of_term arities =
51 let set_arity arities k n =
52 (assert (k<>Variable || n=0);
56 (* here we override, but partial instantiation may trick us *)
57 (k,n)::(List.remove_assoc k arities))
59 let rec aux arities = function
60 | NCic.Appl ((hd::tl) as l) ->
62 set_arity arities (elem_of_cic hd) (List.length tl)
65 (fun (arities,path) t ->
66 let arities,tpath = aux arities t in
69 | t -> arities, [elem_of_cic t]
74 let compare_elem e1 e2 =
76 | Constant u1,Constant u2 -> NUri.compare u1 u2
77 | e1,e2 -> Pervasives.compare e1 e2
80 let head_of_term = function
81 | NCic.Appl (hd::tl) -> hd
85 let rec skip_prods = function
86 | NCic.Prod (_,_,t) -> skip_prods t
91 module DiscriminationTreeIndexing =
95 module OrderedPathStringElement = struct
96 type t = path_string_elem
97 let compare = compare_elem
100 module PSMap = Map.Make(OrderedPathStringElement);;
104 module DiscriminationTree = Trie.Make(PSMap);;
106 type t = A.t DiscriminationTree.t * (path_string_elem*int) list
108 let empty = DiscriminationTree.empty, [] ;;
110 let iter (dt, _ ) f =
111 DiscriminationTree.iter (fun y x -> f y x) dt
114 let index (tree,arity) term info =
115 let arity,ps = path_string_of_term arity term in
117 try DiscriminationTree.find ps tree
118 with Not_found -> A.empty in
119 let tree = DiscriminationTree.add ps (A.add info ps_set) tree in
123 let remove_index (tree,arity) term info =
124 let arity,ps = path_string_of_term arity term in
126 let ps_set = A.remove info (DiscriminationTree.find ps tree) in
127 if A.is_empty ps_set then
128 DiscriminationTree.remove ps tree,arity
130 DiscriminationTree.add ps ps_set tree,arity
135 let in_index (tree,arity) term test =
136 let arity,ps = path_string_of_term arity term in
138 let ps_set = DiscriminationTree.find ps tree in
144 let rec subterm_at_pos pos term =
150 (try subterm_at_pos pos (List.nth l index)
151 with Failure _ -> raise Not_found)
152 | _ -> raise Not_found
156 let rec after_t pos term =
159 | [] -> raise Not_found
162 (fun i r -> if r = [] then [i+1] else i::r) pos []
165 ignore(subterm_at_pos pos' term ); pos'
169 (fun i (r, b) -> if b then (i::r, true) else (r, true))
176 let next_t pos term =
177 let t = subterm_at_pos pos term in
179 let _ = subterm_at_pos [1] t in
184 | pos -> after_t pos term
187 let retrieve_generalizations (tree,arity) term =
188 let term = skip_prods term in
189 let rec retrieve tree term pos =
191 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
192 | DiscriminationTree.Node (_, map) ->
195 elem_of_cic (head_of_term (subterm_at_pos pos term))
197 if hd_term = Variable then A.empty else
199 let n = PSMap.find hd_term map in
201 | DiscriminationTree.Node (Some s, _) -> s
202 | DiscriminationTree.Node (None, _) ->
207 retrieve n term newpos
212 let n = PSMap.find Variable map in
213 let newpos = try after_t pos term with Not_found -> [-1] in
214 if newpos = [-1] then
216 | DiscriminationTree.Node (Some s, _) -> A.union s res
219 A.union res (retrieve n term newpos)
223 retrieve tree term []
227 let jump_list arities = function
228 | DiscriminationTree.Node (value, map) ->
231 | DiscriminationTree.Node (v, m) ->
238 try List.assoc k arities
241 (get (n-1 + a) v) @ res) m []
248 with Not_found -> 0 in
254 let retrieve_unifiables (tree,arities) term =
255 let term = skip_prods term in
256 let rec retrieve tree term pos =
258 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
259 | DiscriminationTree.Node (_, map) ->
261 try Some (subterm_at_pos pos term) with Not_found -> None
265 | Some (NCic.Meta _) ->
266 let newpos = try next_t pos term with Not_found -> [] in
267 let jl = jump_list arities tree in
269 (fun r s -> A.union r s)
271 (List.map (fun t -> retrieve t term newpos) jl)
274 let hd_term = elem_of_cic (head_of_term subterm) in
275 if hd_term = Variable then
278 let n = PSMap.find hd_term map in
280 | DiscriminationTree.Node (Some s, _) -> s
281 | DiscriminationTree.Node (None, _) ->
282 retrieve n term (next_t pos term)
287 let n = PSMap.find Variable map in
290 with Not_found -> [-1]
292 if newpos = [-1] then
294 | DiscriminationTree.Node (Some s, _) ->
298 A.union res (retrieve n term newpos)
302 retrieve tree term []