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 =
33 | Constant of UriManager.uri
34 | Bound of int | Variable | Proposition | Datatype | Dead;;
35 type path_string = path_string_elem list;;
38 (* needed by the retrieve_* functions, to know the arities of the
42 | Constant uri -> UriManager.name_of_uri uri
43 | Bound i -> string_of_int i
45 | Proposition -> "Prop"
49 let pppath l = String.concat "::" (List.map ppelem l) ;;
50 let elem_of_cic = function
51 | Cic.Meta _ | Cic.Implicit _ -> Variable
52 | Cic.Rel i -> Bound i
53 | Cic.Sort (Cic.Prop) -> Proposition
54 | Cic.Sort _ -> Datatype
55 | Cic.Const _ | Cic.Var _ | Cic.MutInd _ | Cic.MutConstruct _ as t ->
56 (try Constant (CicUtil.uri_of_term t)
57 with Invalid_argument _ -> assert false)
59 assert false (* should not happen *)
60 | Cic.LetIn _ | Cic.Lambda _ | Cic.Prod _ | Cic.Cast _
61 | Cic.MutCase _ | Cic.Fix _ | Cic.CoFix _ ->
62 HLog.debug "FIXME: the trie receives an invalid term";
64 (* assert false universe.ml removes these *)
66 let path_string_of_term arities =
67 let set_arity arities k n =
68 (assert (k<>Variable || n=0);
69 if k = Dead then arities else (k,n)::(List.remove_assoc k arities))
71 let rec aux arities = function
72 | Cic.Appl ((hd::tl) as l) ->
74 set_arity arities (elem_of_cic hd) (List.length tl) in
76 (fun (arities,path) t ->
77 let arities,tpath = aux arities t in
80 | t -> arities, [elem_of_cic t]
84 let compare_elem e1 e2 =
86 | Constant u1,Constant u2 -> UriManager.compare u1 u2
87 | e1,e2 -> Pervasives.compare e1 e2
90 module OrderedPathStringElement = struct
91 type t = path_string_elem
92 let compare = compare_elem
95 module PSMap = Map.Make(OrderedPathStringElement);;
99 module DiscriminationTree = Trie.Make(PSMap);;
101 type t = A.t DiscriminationTree.t * (path_string_elem*int) list
102 let empty = DiscriminationTree.empty, [] ;;
104 let iter (dt, _ ) f =
105 DiscriminationTree.iter (fun _ x -> f x) dt
108 let index (tree,arity) term info =
109 let arity,ps = path_string_of_term arity term in
111 try DiscriminationTree.find ps tree
112 with Not_found -> A.empty in
113 let tree = DiscriminationTree.add ps (A.add info ps_set) tree in
117 let remove_index (tree,arity) term info =
118 let arity,ps = path_string_of_term arity term in
120 let ps_set = A.remove info (DiscriminationTree.find ps tree) in
121 if A.is_empty ps_set then
122 DiscriminationTree.remove ps tree,arity
124 DiscriminationTree.add ps ps_set tree,arity
129 let in_index (tree,arity) term test =
130 let arity,ps = path_string_of_term arity term in
132 let ps_set = DiscriminationTree.find ps tree in
138 let head_of_term = function
139 | Cic.Appl (hd::tl) -> hd
143 let rec skip_prods = function
144 | Cic.Prod (_,_,t) -> skip_prods t
148 let rec subterm_at_pos pos term =
154 (try subterm_at_pos pos (List.nth l index)
155 with Failure _ -> raise Not_found)
156 | _ -> raise Not_found
160 let rec after_t pos term =
163 | [] -> raise Not_found
166 (fun i r -> if r = [] then [i+1] else i::r) pos []
169 ignore(subterm_at_pos pos' term ); pos'
173 (fun i (r, b) -> if b then (i::r, true) else (r, true))
180 let next_t pos term =
181 let t = subterm_at_pos pos term in
183 let _ = subterm_at_pos [1] t in
188 | pos -> after_t pos term
191 let retrieve_generalizations (tree,arity) term =
192 let term = skip_prods term in
193 let rec retrieve tree term pos =
195 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
196 | DiscriminationTree.Node (_, map) ->
199 elem_of_cic (head_of_term (subterm_at_pos pos term))
201 if hd_term = Variable then A.empty else
203 let n = PSMap.find hd_term map in
205 | DiscriminationTree.Node (Some s, _) -> s
206 | DiscriminationTree.Node (None, _) ->
211 retrieve n term newpos
216 let n = PSMap.find Variable map in
217 let newpos = try after_t pos term with Not_found -> [-1] in
218 if newpos = [-1] then
220 | DiscriminationTree.Node (Some s, _) -> A.union s res
223 A.union res (retrieve n term newpos)
227 retrieve tree term []
231 let jump_list arities = function
232 | DiscriminationTree.Node (value, map) ->
235 | DiscriminationTree.Node (v, m) ->
242 try List.assoc k arities
245 (get (n-1 + a) v) @ res) m []
252 with Not_found -> 0 in
258 let retrieve_unifiables (tree,arities) term =
259 let term = skip_prods term in
260 let rec retrieve tree term pos =
262 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
263 | DiscriminationTree.Node (_, map) ->
265 try Some (subterm_at_pos pos term) with Not_found -> None
269 | Some (Cic.Meta _) ->
270 let newpos = try next_t pos term with Not_found -> [] in
271 let jl = jump_list arities tree in
273 (fun r s -> A.union r s)
275 (List.map (fun t -> retrieve t term newpos) jl)
278 let hd_term = elem_of_cic (head_of_term subterm) in
279 if hd_term = Variable then
282 let n = PSMap.find hd_term map in
284 | DiscriminationTree.Node (Some s, _) -> s
285 | DiscriminationTree.Node (None, _) ->
286 retrieve n term (next_t pos term)
291 let n = PSMap.find Variable map in
294 with Not_found -> [-1]
296 if newpos = [-1] then
298 | DiscriminationTree.Node (Some s, _) ->
302 A.union res (retrieve n term newpos)
306 retrieve tree term []