1 (* Copyright (C) 2004, 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 (* identity_relocation_list_for_metavariable i canonical_context *)
27 (* returns the identity relocation list, which is the list [1 ; ... ; n] *)
28 (* where n = List.length [canonical_context] *)
29 (*CSC: ma mi basta la lunghezza del contesto canonico!!!*)
30 let identity_relocation_list_for_metavariable ?(start = 1) canonical_context =
34 | (n,None::tl) -> None::(aux ((n+1),tl))
35 | (n,_::tl) -> (Some (Cic.Rel n))::(aux ((n+1),tl))
37 aux (start,canonical_context)
39 (* Returns the first meta whose number is above the *)
40 (* number of the higher meta. *)
41 let new_meta metasenv subst =
46 | None, n::tl -> aux (Some n,tl)
47 | Some m, n::tl -> if n > m then aux (Some n,tl) else aux (Some m,tl)
50 (List.map (fun (i, _, _) -> i) metasenv) @ (List.map fst subst)
52 1 + aux (None, indexes)
54 (* let apply_subst_context = CicMetaSubst.apply_subst_context;; *)
55 (* questa o la precedente sembrano essere equivalenti come tempi *)
56 let apply_subst_context _ context = context ;;
58 let mk_implicit metasenv subst context =
59 let newmeta = new_meta metasenv subst in
60 let newuniv = CicUniv.fresh () in
61 let irl = identity_relocation_list_for_metavariable context in
62 (* in the following mk_* functions we apply substitution to canonical
63 * context since we have the invariant that the metasenv has already been
64 * instantiated with subst *)
65 let context = apply_subst_context subst context in
66 ([ newmeta, [], Cic.Sort (Cic.Type newuniv) ;
68 newmeta + 1, context, Cic.Meta (newmeta, []);
69 newmeta + 2, context, Cic.Meta (newmeta + 1,irl) ] @ metasenv,
72 let mk_implicit_type metasenv subst context =
73 let newmeta = new_meta metasenv subst in
74 let newuniv = CicUniv.fresh () in
75 let context = apply_subst_context subst context in
76 ([ newmeta, [], Cic.Sort (Cic.Type newuniv);
78 newmeta + 1, context, Cic.Meta (newmeta, []) ] @metasenv,
81 let mk_implicit_sort metasenv subst =
82 let newmeta = new_meta metasenv subst in
83 let newuniv = CicUniv.fresh () in
84 ([ newmeta, [], Cic.Sort (Cic.Type newuniv)] @ metasenv, newmeta)
87 let n_fresh_metas metasenv subst context n =
88 if n = 0 then metasenv, []
90 let irl = identity_relocation_list_for_metavariable context in
91 let context = apply_subst_context subst context in
92 let newmeta = new_meta metasenv subst in
93 let newuniv = CicUniv.fresh () in
94 let rec aux newmeta n =
95 if n = 0 then metasenv, []
97 let metasenv', l = aux (newmeta + 3) (n-1) in
99 (newmeta, context, Cic.Sort (Cic.Type newuniv))::
100 (newmeta + 1, context, Cic.Meta (newmeta, irl))::
101 (newmeta + 2, context, Cic.Meta (newmeta + 1,irl))::metasenv',
102 Cic.Meta(newmeta+2,irl)::l in
105 let fresh_subst metasenv subst context uris =
106 let irl = identity_relocation_list_for_metavariable context in
107 let context = apply_subst_context subst context in
108 let newmeta = new_meta metasenv subst in
109 let newuniv = CicUniv.fresh () in
110 let rec aux newmeta = function
113 let metasenv', l = aux (newmeta + 3) tl in
115 (newmeta, context, Cic.Sort (Cic.Type newuniv))::
116 (newmeta + 1, context, Cic.Meta (newmeta, irl))::
117 (newmeta + 2, context, Cic.Meta (newmeta + 1,irl))::metasenv',
118 (uri,Cic.Meta(newmeta+2,irl))::l in
121 let expand_implicits metasenv subst context term =
122 let rec aux metasenv context = function
123 | (Cic.Rel _) as t -> metasenv, t
124 | (Cic.Sort _) as t -> metasenv, t
125 | Cic.Const (uri, subst) ->
126 let metasenv', subst' = do_subst metasenv context subst in
127 metasenv', Cic.Const (uri, subst')
128 | Cic.Var (uri, subst) ->
129 let metasenv', subst' = do_subst metasenv context subst in
130 metasenv', Cic.Var (uri, subst')
131 | Cic.MutInd (uri, i, subst) ->
132 let metasenv', subst' = do_subst metasenv context subst in
133 metasenv', Cic.MutInd (uri, i, subst')
134 | Cic.MutConstruct (uri, i, j, subst) ->
135 let metasenv', subst' = do_subst metasenv context subst in
136 metasenv', Cic.MutConstruct (uri, i, j, subst')
138 let metasenv', l' = do_local_context metasenv context l in
139 metasenv', Cic.Meta (n, l')
140 | Cic.Implicit (Some `Type) ->
141 let (metasenv', idx) = mk_implicit_type metasenv subst context in
142 let irl = identity_relocation_list_for_metavariable context in
143 metasenv', Cic.Meta (idx, irl)
144 | Cic.Implicit (Some `Closed) ->
145 let (metasenv', idx) = mk_implicit metasenv subst [] in
146 metasenv', Cic.Meta (idx, [])
147 | Cic.Implicit None ->
148 let (metasenv', idx) = mk_implicit metasenv subst context in
149 let irl = identity_relocation_list_for_metavariable context in
150 metasenv', Cic.Meta (idx, irl)
151 | Cic.Cast (te, ty) ->
152 let metasenv', ty' = aux metasenv context ty in
153 let metasenv'', te' = aux metasenv' context te in
154 metasenv'', Cic.Cast (te', ty')
155 | Cic.Prod (name, s, t) ->
156 let metasenv', s' = aux metasenv context s in
158 aux metasenv' (Some (name, Cic.Decl s') :: context) t
160 metasenv'', Cic.Prod (name, s', t')
161 | Cic.Lambda (name, s, t) ->
162 let metasenv', s' = aux metasenv context s in
164 aux metasenv' (Some (name, Cic.Decl s') :: context) t
166 metasenv'', Cic.Lambda (name, s', t')
167 | Cic.LetIn (name, s, t) ->
168 let metasenv', s' = aux metasenv context s in
170 aux metasenv' (Some (name, Cic.Def (s', None)) :: context) t
172 metasenv'', Cic.LetIn (name, s', t')
173 | Cic.Appl l when List.length l > 1 ->
176 (fun term (metasenv, terms) ->
177 let new_metasenv, term = aux metasenv context term in
178 new_metasenv, term :: terms)
181 metasenv', Cic.Appl l'
182 | Cic.Appl _ -> assert false
183 | Cic.MutCase (uri, i, outtype, term, patterns) ->
186 (fun term (metasenv, terms) ->
187 let new_metasenv, term = aux metasenv context term in
188 new_metasenv, term :: terms)
189 (outtype :: term :: patterns) (metasenv, [])
191 let outtype', term', patterns' =
193 | outtype' :: term' :: patterns' -> outtype', term', patterns'
196 metasenv', Cic.MutCase (uri, i, outtype', term', patterns')
197 | Cic.Fix (i, funs) ->
198 let metasenv', types =
200 (fun (name, _, typ, _) (metasenv, types) ->
201 let new_metasenv, new_type = aux metasenv context typ in
202 (new_metasenv, (name, new_type) :: types))
207 (fun (name, t) -> Some (Cic.Name name, Cic.Decl t))
211 let metasenv'', bodies =
213 (fun (_, _, _, body) (metasenv, bodies) ->
214 let new_metasenv, new_body = aux metasenv context' body in
215 (new_metasenv, new_body :: bodies))
218 let rec combine = function
219 | ((name, index, _, _) :: funs_tl),
220 ((_, typ) :: typ_tl),
222 (name, index, typ, body) :: combine (funs_tl, typ_tl, body_tl)
226 let funs' = combine (funs, types, bodies) in
227 metasenv'', Cic.Fix (i, funs')
228 | Cic.CoFix (i, funs) ->
229 let metasenv', types =
231 (fun (name, typ, _) (metasenv, types) ->
232 let new_metasenv, new_type = aux metasenv context typ in
233 (new_metasenv, (name, new_type) :: types))
238 (fun (name, t) -> Some (Cic.Name name, Cic.Decl t))
242 let metasenv'', bodies =
244 (fun (_, _, body) (metasenv, bodies) ->
245 let new_metasenv, new_body = aux metasenv context' body in
246 (new_metasenv, new_body :: bodies))
249 let rec combine = function
250 | ((name, _, _) :: funs_tl),
251 ((_, typ) :: typ_tl),
253 (name, typ, body) :: combine (funs_tl, typ_tl, body_tl)
257 let funs' = combine (funs, types, bodies) in
258 metasenv'', Cic.CoFix (i, funs')
259 and do_subst metasenv context subst =
261 (fun (uri, term) (metasenv, substs) ->
262 let metasenv', term' = aux metasenv context term in
263 (metasenv', (uri, term') :: substs))
265 and do_local_context metasenv context local_context =
267 (fun term (metasenv, local_context) ->
268 let metasenv', term' =
270 | None -> metasenv, None
272 let metasenv', term' = aux metasenv context term in
273 metasenv', Some term'
275 metasenv', term' :: local_context)
276 local_context (metasenv, [])
278 aux metasenv context term