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_______________________________________________________________ *)
15 module Ref = NReference
17 let lift_from status ?(no_implicit=true) k n =
18 let rec liftaux k = function
19 | C.Rel m as t -> if m < k then t else C.Rel (m + n)
20 | C.Meta (i,(m,(C.Irl 0 as l))) when k <= m+1 -> C.Meta (i,(m,l))
21 | C.Meta (i,(m,l)) when k <= m+1 -> C.Meta (i,(m+n,l))
22 | C.Meta (_,(m,C.Irl l)) as t when k > l + m -> t
24 let lctx = NCicUtils.expand_local_context l in
25 C.Meta (i, (m, C.Ctx (HExtlib.sharing_map (liftaux (k-m)) lctx)))
26 | C.Implicit _ as t -> (* was the identity *)
27 if no_implicit then assert false
29 | t -> NCicUtils.map status (fun _ k -> k + 1) k liftaux t
34 let lift status ?(from=1) ?(no_implicit=true) n t =
35 if n = 0 then t else lift_from status ~no_implicit from n t
40 (* substitutes [t1] for [Rel 1] in [t2] *)
41 (* if avoid_beta_redexes is true (default: false) no new beta redexes *)
42 (* are generated. WARNING: the substitution can diverge when t2 is not *)
43 (* well typed and avoid_beta_redexes is true. *)
44 (* map_arg is ReductionStrategy.from_env_for_unwind when psubst is *)
45 (* used to implement nCicReduction.unwind' *)
46 let rec psubst status ?(avoid_beta_redexes=false) ?(no_implicit=true) map_arg args =
47 let nargs = List.length args in
48 let rec substaux k = function
51 | n when n >= (k+nargs) ->
52 if nargs <> 0 then C.Rel (n - nargs) else t
54 | n (* k <= n < k+nargs *) ->
55 (try lift status ~no_implicit (k-1) (map_arg (List.nth args (n-k)))
56 with Failure _ | Invalid_argument _ -> assert false))
57 | C.Meta (i,(m,l)) as t when m >= k + nargs - 1 ->
58 if nargs <> 0 then C.Meta (i,(m-nargs,l)) else t
59 | C.Meta (_,(m,(C.Irl l))) as t when k > l + m -> t
61 let lctx = NCicUtils.expand_local_context l in
63 C.Ctx (HExtlib.sharing_map
64 (fun x -> substaux k (lift status ~no_implicit m x)) lctx)))
65 | C.Implicit _ as t ->
66 if no_implicit then assert false (* was identity *)
68 | C.Appl (he::tl) as t ->
69 (* Invariant: no Appl applied to another Appl *)
70 let rec avoid he' = function
74 | C.Appl l -> C.Appl (l@args)
75 | C.Lambda (_,_,bo) when avoid_beta_redexes ->
76 (* map_arg is here \x.x, Obj magic is needed because
77 * we don't have polymorphic recursion w/o records *)
79 ~avoid_beta_redexes ~no_implicit
80 Obj.magic [Obj.magic arg] bo) tl'
81 | _ -> if he == he' && args == tl then t else C.Appl (he'::args))
83 let tl = HExtlib.sharing_map (substaux k) tl in
84 avoid (substaux k he) tl
85 | t -> NCicUtils.map status (fun _ k -> k + 1) k substaux t
90 let subst status ?avoid_beta_redexes ?no_implicit arg =
91 psubst status ?avoid_beta_redexes ?no_implicit(fun x -> x)[arg];;
93 (* subst_meta (n, C.Ctx [t_1 ; ... ; t_n]) t *)
94 (* returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *)
95 (* [t_i] is lifted as usual when it crosses an abstraction *)
96 (* subst_meta (n, (C.Irl _ | C.Ctx [])) t | -> lift status n t *)
97 let subst_meta status = function
99 | m, C.Ctx [] -> lift status m
100 | m, C.Ctx l -> psubst status (lift status m) l