1 (* Copyright (C) 2005, HELM Team.
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.
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.
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.
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,
22 * For details, see the HELM World-Wide-Web page,
23 * http://cs.unibo.it/helm/.
28 module DiscriminationTreeIndexing =
32 type path_string_elem = Cic.term;;
33 type path_string = path_string_elem list;;
36 (* needed by the retrieve_* functions, to know the arities of the "functions" *)
38 let arities = Hashtbl.create 11;;
40 let shared_implicit = [Cic.Implicit None]
42 let rec path_string_of_term = function
43 | Cic.Meta _ -> shared_implicit
44 | Cic.Appl ((hd::tl) as l) ->
45 if not (Hashtbl.mem arities hd) then
46 Hashtbl.add arities hd (List.length tl);
47 List.concat (List.map path_string_of_term l)
52 module OrderedPathStringElement = struct
53 type t = path_string_elem
55 let compare = Pervasives.compare
58 module PSMap = Map.Make(OrderedPathStringElement);;
62 module DiscriminationTree = Trie.Make(PSMap);;
64 type t = A.t DiscriminationTree.t
65 let empty = DiscriminationTree.empty
68 module OrderedPosEquality = struct
69 type t = Utils.pos * Inference.equality
70 let compare = Pervasives.compare
73 module PosEqSet = Set.Make(OrderedPosEquality);;
75 let string_of_discrimination_tree tree =
76 let rec to_string level = function
77 | DiscriminationTree.Node (value, map) ->
81 (String.make (2 * level) ' ') ^
82 "{" ^ (String.concat "; "
85 "(" ^ (Utils.string_of_pos p) ^ ", " ^
86 (Inference.string_of_equality e) ^ ")")
87 (PosEqSet.elements v))) ^ "}"
94 let ks = CicPp.ppterm k in
95 let rs = to_string (level+1) v in
96 ((String.make (2 * level) ' ') ^ ks ^ "\n" ^ rs)::s)
105 let index tree term info =
106 let ps = path_string_of_term term in
108 try DiscriminationTree.find ps tree
109 with Not_found -> A.empty in
111 DiscriminationTree.add ps (A.add info ps_set) tree in
115 let index tree equality =
116 let _, _, (_, l, r, ordering), _, _ = equality in
117 let psl = path_string_of_term l
118 and psr = path_string_of_term r in
119 let index pos tree ps =
121 try DiscriminationTree.find ps tree with Not_found -> PosEqSet.empty in
123 DiscriminationTree.add ps (PosEqSet.add (pos, equality) ps_set) tree in
127 | Utils.Gt -> index Utils.Left tree psl
128 | Utils.Lt -> index Utils.Right tree psr
130 let tree = index Utils.Left tree psl in
131 index Utils.Right tree psr
135 let remove_index tree term info =
136 let ps = path_string_of_term term in
139 A.remove info (DiscriminationTree.find ps tree) in
140 if A.is_empty ps_set then
141 DiscriminationTree.remove ps tree
143 DiscriminationTree.add ps ps_set tree
148 let remove_index tree equality =
149 let _, _, (_, l, r, ordering), _, _ = equality in
150 let psl = path_string_of_term l
151 and psr = path_string_of_term r in
152 let remove_index pos tree ps =
155 PosEqSet.remove (pos, equality) (DiscriminationTree.find ps tree) in
156 if PosEqSet.is_empty ps_set then
157 DiscriminationTree.remove ps tree
159 DiscriminationTree.add ps ps_set tree
164 | Utils.Gt -> remove_index Utils.Left tree psl
165 | Utils.Lt -> remove_index Utils.Right tree psr
167 let tree = remove_index Utils.Left tree psl in
168 remove_index Utils.Right tree psr
173 let in_index tree term test =
174 let ps = path_string_of_term term in
176 let ps_set = DiscriminationTree.find ps tree in
182 let in_index tree equality =
183 let _, _, (_, l, r, ordering), _, _ = equality in
184 let psl = path_string_of_term l
185 and psr = path_string_of_term r in
186 let meta_convertibility = Inference.meta_convertibility_eq equality in
189 let set = DiscriminationTree.find ps tree in
190 PosEqSet.exists (fun (p, e) -> meta_convertibility e) set
199 let head_of_term = function
200 | Cic.Appl (hd::tl) -> hd
205 let rec subterm_at_pos pos term =
211 (try subterm_at_pos pos (List.nth l index)
212 with Failure _ -> raise Not_found)
213 | _ -> raise Not_found
217 let rec after_t pos term =
220 | [] -> raise Not_found
221 | pos -> List.fold_right (fun i r -> if r = [] then [i+1] else i::r) pos []
224 ignore(subterm_at_pos pos' term ); pos'
228 (fun i (r, b) -> if b then (i::r, true) else (r, true)) pos ([], false)
234 let next_t pos term =
235 let t = subterm_at_pos pos term in
237 let _ = subterm_at_pos [1] t in
242 | pos -> after_t pos term
246 let retrieve_generalizations tree term =
247 let rec retrieve tree term pos =
249 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
250 | DiscriminationTree.Node (_, map) ->
253 let hd_term = head_of_term (subterm_at_pos pos term) in
254 let n = PSMap.find hd_term map in
256 | DiscriminationTree.Node (Some s, _) -> s
257 | DiscriminationTree.Node (None, _) ->
258 let newpos = try next_t pos term with Not_found -> [] in
259 retrieve n term newpos
264 let n = PSMap.find (Cic.Implicit None) map in
265 let newpos = try after_t pos term with Not_found -> [-1] in
266 if newpos = [-1] then
268 | DiscriminationTree.Node (Some s, _) -> A.union s res
271 A.union res (retrieve n term newpos)
275 retrieve tree term []
279 let jump_list = function
280 | DiscriminationTree.Node (value, map) ->
283 | DiscriminationTree.Node (v, m) ->
289 let a = try Hashtbl.find arities k with Not_found -> 0 in
290 (get (n-1 + a) v) @ res) m []
294 let arity = try Hashtbl.find arities k with Not_found -> 0 in
300 let retrieve_unifiables tree term =
301 let rec retrieve tree term pos =
303 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
304 | DiscriminationTree.Node (_, map) ->
306 try Some (subterm_at_pos pos term) with Not_found -> None
310 | Some (Cic.Meta _) ->
311 let newpos = try next_t pos term with Not_found -> [] in
312 let jl = jump_list tree in
314 (fun r s -> A.union r s)
316 (List.map (fun t -> retrieve t term newpos) jl)
320 let hd_term = head_of_term subterm in
321 let n = PSMap.find hd_term map in
323 | DiscriminationTree.Node (Some s, _) -> s
324 | DiscriminationTree.Node (None, _) ->
325 retrieve n term (next_t pos term)
330 let n = PSMap.find (Cic.Implicit None) map in
331 let newpos = try after_t pos term with Not_found -> [-1] in
332 if newpos = [-1] then
334 | DiscriminationTree.Node (Some s, _) -> A.union s res
337 A.union res (retrieve n term newpos)
341 retrieve tree term []