(*
    ||M||  This file is part of HELM, an Hypertextual, Electronic        
    ||A||  Library of Mathematics, developed at the Computer Science     
    ||T||  Department, University of Bologna, Italy.                     
    ||I||                                                                
    ||T||  HELM is free software; you can redistribute it and/or         
    ||A||  modify it under the terms of the GNU General Public License   
    \   /  version 2 or (at your option) any later version.              
     \ /   This software is distributed as is, NO WARRANTY.              
      V_______________________________________________________________ *)

module G = Options
module B = Brg

IFDEF TYPE THEN

let rec icm a = function
   | B.Sort _
   | B.LRef _
   | B.GRef _                        -> succ a
   | B.Bind (_, B.Void, t)           -> icm (succ a) t
   | B.Cast (u, t)                   -> icm (icm a u) t
   | B.Appl (_, u, t)
   | B.Bind (_, B.Abst (_, _, u), t)
   | B.Bind (_, B.Abbr u, t)         -> icm (icm (succ a) u) t

let iter map d =
   let rec iter_bind d = function
      | B.Void           -> B.Void
      | B.Abst (r, n, w) -> B.Abst (r, n, iter_term d w)
      | B.Abbr v         -> B.Abbr (iter_term d v)
   and iter_term d = function
      | B.Sort _ as t      -> t
      | B.GRef _ as t      -> t
      | B.LRef (a, i) as t -> if i < d then t else map d a i
      | B.Cast (w, v)      -> B.Cast (iter_term d w, iter_term d v)
      | B.Appl (a, w, u)   -> B.Appl (a, iter_term d w, iter_term d u)
      | B.Bind (y, b, u)   -> B.Bind (y, iter_bind d b, iter_term (succ d) u)
   in
   iter_term d

let lift_map h _ a i =
   if i + h >= 0 then B.LRef (a, i + h) else assert false

let lift h d t =
   if h = 0 then t else begin
(*
      G.icm := succ !G.icm; 
      G.icm := icm !G.icm t;
*)
      iter (lift_map h) d t
   end

END