(* Copyright (C) 2000, HELM Team.
 * 
 * This file is part of HELM, an Hypertextual, Electronic
 * Library of Mathematics, developed at the Computer Science
 * Department, University of Bologna, Italy.
 * 
 * HELM is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * HELM is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HELM; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA  02111-1307, USA.
 * 
 * For details, see the HELM World-Wide-Web page,
 * http://cs.unibo.it/helm/.
 *)

(* $Id$ *)

let debug_print = fun _ -> ();;

let lift_from k n =
 let rec liftaux k = function
    | NCic.Const _ 
    | NCic.Sort _ as t -> t
    | NCic.Rel m ->
       if m < k then NCic.Rel m
       else NCic.Rel (m + n)
    | NCic.Meta (i,(m,l)) when k <= m -> NCic.Meta (i,(m+n,l))
    | NCic.Meta (_,(m,NCic.Irl l)) as t when k > l + m -> t
    | NCic.Meta (i,(m,l)) -> 
       let lctx = NCicUtils.expand_local_context l in
       NCic.Meta (i, (m, NCic.Ctx (List.map (liftaux (k-m)) lctx)))
    | NCic.Implicit _ -> (* was the identity *) assert false
    | NCic.Prod (n,s,t) -> NCic.Prod (n, liftaux k s, liftaux (k+1) t)
    | NCic.Lambda (n,s,t) -> NCic.Lambda (n, liftaux k s, liftaux (k+1) t)
    | NCic.LetIn (n,ty,te,t) -> 
       NCic.LetIn (n, liftaux k ty, liftaux k te, liftaux (k+1) t)
    | NCic.Appl l -> NCic.Appl (List.map (liftaux k) l)
    | NCic.Match (r,outty,t,pl) ->
       NCic.Match (r,liftaux k outty,liftaux k t, List.map (liftaux k) pl)
 in
 liftaux k
;;

let lift ?(from=1) n t =
  if n = 0 then t
  else lift_from from n t
;;

(* subst t1 t2                                                          *)
(*  substitutes [t1] for [Rel 1] in [t2]                                *)
(*  if avoid_beta_redexes is true (default: false) no new beta redexes  *)
(*  are generated. WARNING: the substitution can diverge when t2 is not *)
(*  well typed and avoid_beta_redexes is true.                          *)
(*  map_arg is ReductionStrategy.from_env_for_unwind when psubst is     *)
(*  used to implement nCicReduction.unwind'                             *)
let rec psubst ?(avoid_beta_redexes=false) delift lift_args map_arg args = 
 let nargs = List.length args in
 let rec substaux k = function
    | NCic.Sort _ 
    | NCic.Const _ as t -> t
    | NCic.Rel n as t ->
       (match n with
       | n when n >= (k+nargs) -> if delift then NCic.Rel (n - nargs) else t
       | n when n < k -> t
       | n (* k <= n < k+nargs *) ->
        (try lift (k+lift_args) (map_arg (List.nth args (n-k)))
         with Failure _ -> assert false))
    | NCic.Meta (i,(m,l)) as t when m >= k + nargs - 1 -> 
        if delift then NCic.Meta (i,(m-nargs,l)) else t
    | NCic.Meta (i,(m,(NCic.Irl l as irl))) as t when k > l + m -> 
        if delift then NCic.Meta (i,(m-nargs,irl)) else t
    | NCic.Meta (i,(m,l)) -> 
       let lctx = NCicUtils.expand_local_context l in
       (* 1-nargs < k-m, when <= 0 is still reasonable because we will
        * substitute args[ k-m ... k-m+nargs-1 > 0 ] *)
       NCic.Meta (i,(m, NCic.Ctx (List.map (substaux (k-m)) lctx)))
    | NCic.Implicit _ -> assert false (* was identity *)
    | NCic.Prod (n,s,t) -> NCic.Prod (n, substaux k s, substaux (k + 1) t)
    | NCic.Lambda (n,s,t) -> NCic.Lambda (n, substaux k s, substaux (k + 1) t)
    | NCic.LetIn (n,ty,te,t) -> 
       NCic.LetIn (n, substaux k ty, substaux k te, substaux (k + 1) t)
    | NCic.Appl (he::tl) ->
       (* Invariant: no Appl applied to another Appl *)
       let rec avoid he = function
         | [] -> he
         | arg::tl as args->
             (match he with
             | NCic.Appl l -> NCic.Appl (l@args)
             | NCic.Lambda (_,_,bo) when avoid_beta_redexes ->
                 (* map_arg is here \x.x, Obj magic is needed because 
                  * we don't have polymorphic recursion w/o records *)
                 avoid (psubst 
                   ~avoid_beta_redexes true 0 Obj.magic [Obj.magic arg] bo) tl
             | _ as he -> NCic.Appl (he::args))
       in
       let tl = List.map (substaux k) tl in
       avoid (substaux k he) tl
    | NCic.Appl _ -> assert false
    | NCic.Match (r,outt,t,pl) ->
       NCic.Match (r,substaux k outt, substaux k t, List.map (substaux k) pl)
 in
  substaux 1
;;

let subst ?avoid_beta_redexes arg = 
  psubst ?avoid_beta_redexes true 0 (fun x -> x)[arg];;

(* subst_meta (n, Some [t_1 ; ... ; t_n]) t                                  *)
(*  returns the term [t] where [Rel i] is substituted with [t_i] lifted by n *)
(*  [t_i] is lifted as usual when it crosses an abstraction                  *)
(* subst_meta (n, Non) t -> lift n t                                        *)
let subst_meta = function 
  | m, NCic.Irl _ 
  | m, NCic.Ctx [] -> lift m 
  | m, NCic.Ctx l  -> psubst false m (fun x -> x) l 
;;