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 module DiscriminationTree = struct
46 type key = path_string
47 type t = Node of PosEqSet.t option * (t PSMap.t)
49 let empty = Node (None, PSMap.empty)
53 | [], Node (None, _) -> raise Not_found
54 | [], Node (Some v, _) -> v
55 | x::r, Node (_, m) -> find r (PSMap.find x m)
59 | [], Node (None, _) -> false
60 | [], Node (Some _, _) -> true
61 | x::r, Node (_, m) -> try mem r (PSMap.find x m) with Not_found -> false
64 let rec ins = function
65 | [], Node (_, m) -> Node (Some v, m)
66 | x::r, Node (v, m) ->
67 let t' = try PSMap.find x m with Not_found -> empty in
68 let t'' = ins (r, t') in
69 Node (v, PSMap.add x t'' m)
75 | [], Node (_, m) -> Node (None, m)
76 | x::r, Node (v, m) ->
78 let t' = remove r (PSMap.find x m) in
79 let m' = if t' = empty then PSMap.remove x m else PSMap.add x t' m in
84 let rec fold f t acc =
85 let rec traverse revp t acc = match t with
87 PSMap.fold (fun x -> traverse (x::revp)) m acc
89 f (List.rev revp) v (PSMap.fold (fun x -> traverse (x::revp)) m acc)
96 let string_of_discrimination_tree tree =
97 let rec to_string level = function
98 | DiscriminationTree.Node (value, map) ->
102 (String.make (2 * level) ' ') ^
103 "{" ^ (String.concat "; "
106 "(" ^ (Utils.string_of_pos p) ^ ", " ^
107 (Inference.string_of_equality e) ^ ")")
108 (PosEqSet.elements v))) ^ "}"
115 let ks = CicPp.ppterm k in
116 let rs = to_string (level+1) v in
117 ((String.make (2 * level) ' ') ^ ks ^ "\n" ^ rs)::s)
126 let index tree equality =
127 let _, (_, l, r, ordering), _, _ = equality in
128 let psl = path_string_of_term l
129 and psr = path_string_of_term r in
130 let index pos tree ps =
132 try DiscriminationTree.find ps tree with Not_found -> PosEqSet.empty in
134 DiscriminationTree.add ps (PosEqSet.add (pos, equality) ps_set) tree in
138 | Utils.Gt -> index Utils.Left tree psl
139 | Utils.Lt -> index Utils.Right tree psr
141 let tree = index Utils.Left tree psl in
142 index Utils.Right tree psr
146 let remove_index tree equality =
147 let _, (_, l, r, ordering), _, _ = equality in
148 let psl = path_string_of_term l
149 and psr = path_string_of_term r in
150 let remove_index pos tree ps =
153 PosEqSet.remove (pos, equality) (DiscriminationTree.find ps tree) in
154 if PosEqSet.is_empty ps_set then
155 DiscriminationTree.remove ps tree
157 DiscriminationTree.add ps ps_set tree
162 | Utils.Gt -> remove_index Utils.Left tree psl
163 | Utils.Lt -> remove_index Utils.Right tree psr
165 let tree = remove_index Utils.Left tree psl in
166 remove_index Utils.Right tree psr
170 let in_index tree equality =
171 let _, (_, l, r, ordering), _, _ = equality in
172 let psl = path_string_of_term l
173 and psr = path_string_of_term r in
174 let meta_convertibility = Inference.meta_convertibility_eq equality in
177 let set = DiscriminationTree.find ps tree in
178 PosEqSet.exists (fun (p, e) -> meta_convertibility e) set
186 let head_of_term = function
187 | Cic.Appl (hd::tl) -> hd
188 (* | Cic.Meta _ -> Cic.Implicit None *)
193 let rec subterm_at_pos pos term =
199 (try subterm_at_pos pos (List.nth l index) with _ -> raise Not_found)
200 | _ -> raise Not_found
204 let rec after_t pos term =
207 | [] -> raise Not_found
208 | pos -> List.fold_right (fun i r -> if r = [] then [i+1] else i::r) pos []
211 let t = subterm_at_pos pos' term in pos'
215 (fun i (r, b) -> if b then (i::r, true) else (r, true)) pos ([], false)
221 let next_t pos term =
222 let t = subterm_at_pos pos term in
224 let _ = subterm_at_pos [1] t in
229 | pos -> after_t pos term
233 let retrieve_generalizations tree term =
234 let rec retrieve tree term pos =
236 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
237 | DiscriminationTree.Node (_, map) ->
240 let hd_term = head_of_term (subterm_at_pos pos term) in
241 let n = PSMap.find hd_term map in
243 | DiscriminationTree.Node (Some s, _) -> s
244 | DiscriminationTree.Node (None, _) ->
245 let newpos = try next_t pos term with Not_found -> [] in
246 retrieve n term newpos
251 let n = PSMap.find (Cic.Implicit None) map in
252 let newpos = try after_t pos term with _ -> [-1] in
253 if newpos = [-1] then
255 | DiscriminationTree.Node (Some s, _) -> PosEqSet.union s res
258 PosEqSet.union res (retrieve n term newpos)
262 retrieve tree term []
266 let jump_list = function
267 | DiscriminationTree.Node (value, map) ->
270 | DiscriminationTree.Node (v, m) ->
276 let a = try Hashtbl.find arities k with Not_found -> 0 in
277 (get (n-1 + a) v) @ res) m []
281 let arity = try Hashtbl.find arities k with Not_found -> 0 in
287 let retrieve_unifiables tree term =
288 let rec retrieve tree term pos =
290 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
291 | DiscriminationTree.Node (_, map) ->
293 try Some (subterm_at_pos pos term) with Not_found -> None
296 | None -> PosEqSet.empty
297 | Some (Cic.Meta _) ->
298 let newpos = try next_t pos term with Not_found -> [] in
299 let jl = jump_list tree in
301 (fun r s -> PosEqSet.union r s)
303 (List.map (fun t -> retrieve t term newpos) jl)
307 let hd_term = head_of_term subterm in
308 let n = PSMap.find hd_term map in
310 | DiscriminationTree.Node (Some s, _) -> s
311 | DiscriminationTree.Node (None, _) ->
312 retrieve n term (next_t pos term)
317 let n = PSMap.find (Cic.Implicit None) map in
318 let newpos = try after_t pos term with _ -> [-1] in
319 if newpos = [-1] then
321 | DiscriminationTree.Node (Some s, _) -> PosEqSet.union s res
324 PosEqSet.union res (retrieve n term newpos)
328 retrieve tree term []