1 type path_string_elem = Cic.term;;
2 type path_string = path_string_elem list;;
5 (* needed by the retrieve_* functions, to know the arities of the "functions" *)
6 let arities = Hashtbl.create 11;;
9 let rec path_string_of_term = function
10 | Cic.Meta _ -> [Cic.Implicit None]
11 | Cic.Appl ((hd::tl) as l) ->
12 if not (Hashtbl.mem arities hd) then
13 Hashtbl.add arities hd (List.length tl);
14 List.concat (List.map path_string_of_term l)
19 let string_of_path_string ps =
20 String.concat "." (List.map CicPp.ppterm ps)
24 module OrderedPathStringElement = struct
25 type t = path_string_elem
27 let compare = Pervasives.compare
30 module PSMap = Map.Make(OrderedPathStringElement);;
33 module OrderedPosEquality = struct
34 type t = Utils.pos * Inference.equality
36 let compare = Pervasives.compare
39 module PosEqSet = Set.Make(OrderedPosEquality);;
42 module DiscriminationTree = Trie.Make(PSMap);;
45 let string_of_discrimination_tree tree =
46 let rec to_string level = function
47 | DiscriminationTree.Node (value, map) ->
51 (String.make (2 * level) ' ') ^
52 "{" ^ (String.concat "; "
55 "(" ^ (Utils.string_of_pos p) ^ ", " ^
56 (Inference.string_of_equality e) ^ ")")
57 (PosEqSet.elements v))) ^ "}"
64 let ks = CicPp.ppterm k in
65 let rs = to_string (level+1) v in
66 ((String.make (2 * level) ' ') ^ ks ^ "\n" ^ rs)::s)
75 let index tree equality =
76 let _, _, (_, l, r, ordering), _, _ = equality in
77 let psl = path_string_of_term l
78 and psr = path_string_of_term r in
79 let index pos tree ps =
81 try DiscriminationTree.find ps tree with Not_found -> PosEqSet.empty in
83 DiscriminationTree.add ps (PosEqSet.add (pos, equality) ps_set) tree in
87 | Utils.Gt -> index Utils.Left tree psl
88 | Utils.Lt -> index Utils.Right tree psr
90 let tree = index Utils.Left tree psl in
91 index Utils.Right tree psr
95 let remove_index tree equality =
96 let _, _, (_, l, r, ordering), _, _ = equality in
97 let psl = path_string_of_term l
98 and psr = path_string_of_term r in
99 let remove_index pos tree ps =
102 PosEqSet.remove (pos, equality) (DiscriminationTree.find ps tree) in
103 if PosEqSet.is_empty ps_set then
104 DiscriminationTree.remove ps tree
106 DiscriminationTree.add ps ps_set tree
111 | Utils.Gt -> remove_index Utils.Left tree psl
112 | Utils.Lt -> remove_index Utils.Right tree psr
114 let tree = remove_index Utils.Left tree psl in
115 remove_index Utils.Right tree psr
119 let in_index tree equality =
120 let _, _, (_, l, r, ordering), _, _ = equality in
121 let psl = path_string_of_term l
122 and psr = path_string_of_term r in
123 let meta_convertibility = Inference.meta_convertibility_eq equality in
126 let set = DiscriminationTree.find ps tree in
127 PosEqSet.exists (fun (p, e) -> meta_convertibility e) set
135 let head_of_term = function
136 | Cic.Appl (hd::tl) -> hd
137 (* | Cic.Meta _ -> Cic.Implicit None *)
142 let rec subterm_at_pos pos term =
148 (try subterm_at_pos pos (List.nth l index)
149 with Failure _ -> raise Not_found)
150 | _ -> raise Not_found
154 let rec after_t pos term =
157 | [] -> raise Not_found
158 | pos -> List.fold_right (fun i r -> if r = [] then [i+1] else i::r) pos []
161 let t = subterm_at_pos pos' term in pos'
165 (fun i (r, b) -> if b then (i::r, true) else (r, true)) pos ([], false)
171 let next_t pos term =
172 let t = subterm_at_pos pos term in
174 let _ = subterm_at_pos [1] t in
179 | pos -> after_t pos term
183 let retrieve_generalizations tree term =
184 let rec retrieve tree term pos =
186 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
187 | DiscriminationTree.Node (_, map) ->
190 let hd_term = head_of_term (subterm_at_pos pos term) in
191 let n = PSMap.find hd_term map in
193 | DiscriminationTree.Node (Some s, _) -> s
194 | DiscriminationTree.Node (None, _) ->
195 let newpos = try next_t pos term with Not_found -> [] in
196 retrieve n term newpos
201 let n = PSMap.find (Cic.Implicit None) map in
202 let newpos = try after_t pos term with Not_found -> [-1] in
203 if newpos = [-1] then
205 | DiscriminationTree.Node (Some s, _) -> PosEqSet.union s res
208 PosEqSet.union res (retrieve n term newpos)
212 retrieve tree term []
216 let jump_list = function
217 | DiscriminationTree.Node (value, map) ->
220 | DiscriminationTree.Node (v, m) ->
226 let a = try Hashtbl.find arities k with Not_found -> 0 in
227 (get (n-1 + a) v) @ res) m []
231 let arity = try Hashtbl.find arities k with Not_found -> 0 in
237 let retrieve_unifiables tree term =
238 let rec retrieve tree term pos =
240 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
241 | DiscriminationTree.Node (_, map) ->
243 try Some (subterm_at_pos pos term) with Not_found -> None
246 | None -> PosEqSet.empty
247 | Some (Cic.Meta _) ->
248 let newpos = try next_t pos term with Not_found -> [] in
249 let jl = jump_list tree in
251 (fun r s -> PosEqSet.union r s)
253 (List.map (fun t -> retrieve t term newpos) jl)
257 let hd_term = head_of_term subterm in
258 let n = PSMap.find hd_term map in
260 | DiscriminationTree.Node (Some s, _) -> s
261 | DiscriminationTree.Node (None, _) ->
262 retrieve n term (next_t pos term)
267 let n = PSMap.find (Cic.Implicit None) map in
268 let newpos = try after_t pos term with Not_found -> [-1] in
269 if newpos = [-1] then
271 | DiscriminationTree.Node (Some s, _) -> PosEqSet.union s res
274 PosEqSet.union res (retrieve n term newpos)
278 retrieve tree term []