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/.
26 (* path indexing implementation *)
28 (* position of the subterm, subterm (Appl are not stored...) *)
29 type path_string_elem = Index of int | Term of Cic.term;;
30 type path_string = path_string_elem list;;
33 let rec path_strings_of_term index =
34 let module C = Cic in function
35 | C.Meta _ -> [ [Index index; Term (C.Implicit None)] ]
37 let p = if index > 0 then [Index index; Term hd] else [Term hd] in
41 let rr = path_strings_of_term i t in
42 (i+1, r @ (List.map (fun ps -> p @ ps) rr)))
46 | term -> [ [Index index; Term term] ]
50 let string_of_path_string ps =
56 | Index i -> "Index " ^ (string_of_int i)
57 | Term t -> "Term " ^ (CicPp.ppterm t)
64 module OrderedPathStringElement = struct
65 type t = path_string_elem
69 | Index i, Index j -> Pervasives.compare i j
70 | Term t1, Term t2 -> if t1 = t2 then 0 else Pervasives.compare t1 t2
71 | Index _, Term _ -> -1
72 | Term _, Index _ -> 1
75 module PSMap = Map.Make(OrderedPathStringElement);;
77 module OrderedPosEquality = struct
78 type t = Utils.pos * Inference.equality
80 let compare = Pervasives.compare
83 module PosEqSet = Set.Make(OrderedPosEquality);;
86 module PSTrie = Trie.Make(PSMap);;
89 let index trie equality =
90 let _, _, (_, l, r, ordering), _, _ = equality in
91 let psl = path_strings_of_term 0 l
92 and psr = path_strings_of_term 0 r in
93 let index pos trie ps =
94 let ps_set = try PSTrie.find ps trie with Not_found -> PosEqSet.empty in
95 let trie = PSTrie.add ps (PosEqSet.add (pos, equality) ps_set) trie in
99 | Utils.Gt -> List.fold_left (index Utils.Left) trie psl
100 | Utils.Lt -> List.fold_left (index Utils.Right) trie psr
102 let trie = List.fold_left (index Utils.Left) trie psl in
103 List.fold_left (index Utils.Right) trie psr
107 let remove_index trie equality =
108 let _, _, (_, l, r, ordering), _, _ = equality in
109 let psl = path_strings_of_term 0 l
110 and psr = path_strings_of_term 0 r in
111 let remove_index pos trie ps =
113 let ps_set = PosEqSet.remove (pos, equality) (PSTrie.find ps trie) in
114 if PosEqSet.is_empty ps_set then
115 PSTrie.remove ps trie
117 PSTrie.add ps ps_set trie
122 | Utils.Gt -> List.fold_left (remove_index Utils.Left) trie psl
123 | Utils.Lt -> List.fold_left (remove_index Utils.Right) trie psr
125 let trie = List.fold_left (remove_index Utils.Left) trie psl in
126 List.fold_left (remove_index Utils.Right) trie psr
130 let in_index trie equality =
131 let _, _, (_, l, r, ordering), _, _ = equality in
132 let psl = path_strings_of_term 0 l
133 and psr = path_strings_of_term 0 r in
134 let meta_convertibility = Inference.meta_convertibility_eq equality in
137 let set = PSTrie.find ps trie in
138 PosEqSet.exists (fun (p, e) -> meta_convertibility e) set
142 (List.exists ok psl) || (List.exists ok psr)
146 let head_of_term = function
147 | Cic.Appl (hd::tl) -> hd
152 let subterm_at_pos index term =
158 (try List.nth l index with Failure _ -> raise Not_found)
159 | _ -> raise Not_found
163 let rec retrieve_generalizations trie term =
165 | PSTrie.Node (value, map) ->
168 | Cic.Meta _ -> PosEqSet.empty
170 let hd_term = head_of_term term in
172 let n = PSMap.find (Term hd_term) map in
174 | PSTrie.Node (Some s, _) -> s
175 | PSTrie.Node (None, m) ->
181 let t = subterm_at_pos i term in
182 let s = retrieve_generalizations v t in
189 List.fold_left (fun r s -> PosEqSet.inter r s) hd tl
190 | _ -> PosEqSet.empty
195 let n = PSMap.find (Term (Cic.Implicit None)) map in
197 | PSTrie.Node (Some s, _) -> PosEqSet.union res s
204 let rec retrieve_unifiables trie term =
206 | PSTrie.Node (value, map) ->
211 (fun ps v res -> PosEqSet.union res v)
212 (PSTrie.Node (None, map))
215 let hd_term = head_of_term term in
217 let n = PSMap.find (Term hd_term) map in
219 | PSTrie.Node (Some v, _) -> v
220 | PSTrie.Node (None, m) ->
226 let t = subterm_at_pos i term in
227 let s = retrieve_unifiables v t in
234 List.fold_left (fun r s -> PosEqSet.inter r s) hd tl
235 | _ -> PosEqSet.empty
240 let n = PSMap.find (Term (Cic.Implicit None)) map in
242 | PSTrie.Node (Some s, _) -> PosEqSet.union res s
249 let retrieve_all trie term =
251 (fun k v s -> PosEqSet.union v s) trie PosEqSet.empty
255 let string_of_pstrie trie =
256 let rec to_string level = function
257 | PSTrie.Node (v, map) ->
261 (String.make (2 * level) ' ') ^
262 "{" ^ (String.concat "; "
265 "(" ^ (Utils.string_of_pos p) ^ ", " ^
266 (Inference.string_of_equality e) ^ ")")
267 (PosEqSet.elements v))) ^ "}"
276 | Index i -> "Index " ^ (string_of_int i)
277 | Term t -> "Term " ^ (CicPp.ppterm t)
279 let rs = to_string (level+1) v in
280 ((String.make (2 * level) ' ') ^ ks ^ "\n" ^ rs)::s)