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 module DiscriminationTreeIndexing =
18 type path_string_elem =
19 | Constant of NUri.uri
20 | Bound of int | Variable | Proposition | Datatype | Dead;;
21 type path_string = path_string_elem list;;
24 (* needed by the retrieve_* functions, to know the arities of the
28 | Constant uri -> NUri.name_of_uri uri
29 | Bound i -> string_of_int i
31 | Proposition -> "Prop"
35 let pppath l = String.concat "::" (List.map ppelem l) ;;
36 let elem_of_cic = function
37 | NCic.Meta _ | NCic.Implicit _ -> Variable
38 | NCic.Rel i -> Bound i
39 | NCic.Sort (NCic.Prop) -> Proposition
40 | NCic.Sort _ -> Datatype
41 | NCic.Const _ | NCic.Var _ | NCic.MutInd _ | NCic.MutConstruct _ as t ->
42 (try Constant (CicUtil.uri_of_term t)
43 with Invalid_argument _ -> assert false)
45 assert false (* should not happen *)
46 | NCic.LetIn _ | NCic.Lambda _ | NCic.Prod _ | NCic.Cast _
47 | NCic.MutCase _ | NCic.Fix _ | NCic.CoFix _ ->
48 HLog.debug "FIXME: the trie receives an invalid term";
50 (* assert false universe.ml removes these *)
52 let path_string_of_term arities =
53 let set_arity arities k n =
54 (assert (k<>Variable || n=0);
55 if k = Dead then arities else (k,n)::(List.remove_assoc k arities))
57 let rec aux arities = function
58 | NCic.Appl ((hd::tl) as l) ->
60 set_arity arities (elem_of_cic hd) (List.length tl) in
62 (fun (arities,path) t ->
63 let arities,tpath = aux arities t in
66 | t -> arities, [elem_of_cic t]
70 let compare_elem e1 e2 =
72 | Constant u1,Constant u2 -> NUri.compare u1 u2
73 | e1,e2 -> Pervasives.compare e1 e2
76 module OrderedPathStringElement = struct
77 type t = path_string_elem
78 let compare = compare_elem
81 module PSMap = Map.Make(OrderedPathStringElement);;
85 module DiscriminationTree = Trie.Make(PSMap);;
87 type t = A.t DiscriminationTree.t * (path_string_elem*int) list
88 let empty = DiscriminationTree.empty, [] ;;
91 DiscriminationTree.iter (fun _ x -> f x) dt
94 let index (tree,arity) term info =
95 let arity,ps = path_string_of_term arity term in
97 try DiscriminationTree.find ps tree
98 with Not_found -> A.empty in
99 let tree = DiscriminationTree.add ps (A.add info ps_set) tree in
103 let remove_index (tree,arity) term info =
104 let arity,ps = path_string_of_term arity term in
106 let ps_set = A.remove info (DiscriminationTree.find ps tree) in
107 if A.is_empty ps_set then
108 DiscriminationTree.remove ps tree,arity
110 DiscriminationTree.add ps ps_set tree,arity
115 let in_index (tree,arity) term test =
116 let arity,ps = path_string_of_term arity term in
118 let ps_set = DiscriminationTree.find ps tree in
124 let head_of_term = function
125 | NCic.Appl (hd::tl) -> hd
129 let rec skip_prods = function
130 | NCic.Prod (_,_,t) -> skip_prods t
134 let rec subterm_at_pos pos term =
140 (try subterm_at_pos pos (List.nth l index)
141 with Failure _ -> raise Not_found)
142 | _ -> raise Not_found
146 let rec after_t pos term =
149 | [] -> raise Not_found
152 (fun i r -> if r = [] then [i+1] else i::r) pos []
155 ignore(subterm_at_pos pos' term ); pos'
159 (fun i (r, b) -> if b then (i::r, true) else (r, true))
166 let next_t pos term =
167 let t = subterm_at_pos pos term in
169 let _ = subterm_at_pos [1] t in
174 | pos -> after_t pos term
177 let retrieve_generalizations (tree,arity) term =
178 let term = skip_prods term in
179 let rec retrieve tree term pos =
181 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
182 | DiscriminationTree.Node (_, map) ->
185 elem_of_cic (head_of_term (subterm_at_pos pos term))
187 if hd_term = Variable then A.empty else
189 let n = PSMap.find hd_term map in
191 | DiscriminationTree.Node (Some s, _) -> s
192 | DiscriminationTree.Node (None, _) ->
197 retrieve n term newpos
202 let n = PSMap.find Variable map in
203 let newpos = try after_t pos term with Not_found -> [-1] in
204 if newpos = [-1] then
206 | DiscriminationTree.Node (Some s, _) -> A.union s res
209 A.union res (retrieve n term newpos)
213 retrieve tree term []
217 let jump_list arities = function
218 | DiscriminationTree.Node (value, map) ->
221 | DiscriminationTree.Node (v, m) ->
228 try List.assoc k arities
231 (get (n-1 + a) v) @ res) m []
238 with Not_found -> 0 in
244 let retrieve_unifiables (tree,arities) term =
245 let term = skip_prods term in
246 let rec retrieve tree term pos =
248 | DiscriminationTree.Node (Some s, _) when pos = [] -> s
249 | DiscriminationTree.Node (_, map) ->
251 try Some (subterm_at_pos pos term) with Not_found -> None
255 | Some (NCic.Meta _) ->
256 let newpos = try next_t pos term with Not_found -> [] in
257 let jl = jump_list arities tree in
259 (fun r s -> A.union r s)
261 (List.map (fun t -> retrieve t term newpos) jl)
264 let hd_term = elem_of_cic (head_of_term subterm) in
265 if hd_term = Variable then
268 let n = PSMap.find hd_term map in
270 | DiscriminationTree.Node (Some s, _) -> s
271 | DiscriminationTree.Node (None, _) ->
272 retrieve n term (next_t pos term)
277 let n = PSMap.find Variable map in
280 with Not_found -> [-1]
282 if newpos = [-1] then
284 | DiscriminationTree.Node (Some s, _) ->
288 A.union res (retrieve n term newpos)
292 retrieve tree term []