module C = NCic
module Ref = NReference
+let debug = ref false;;
let indent = ref "";;
-let inside c = indent := !indent ^ String.make 1 c;;
-let outside () = indent := String.sub !indent 0 (String.length !indent -1);;
-
-
-let pp s =
+let times = ref [];;
+let pp s =
+ if !debug then
prerr_endline (Printf.sprintf "%-20s" !indent ^ " " ^ Lazy.force s)
-;;
+;;
+let inside c =
+ if !debug then
+ begin
+ let time1 = Unix.gettimeofday () in
+ indent := !indent ^ String.make 1 c;
+ times := time1 :: !times;
+ prerr_endline ("{{{" ^ !indent ^ " ")
+ end
+;;
+let outside ok =
+ if !debug then
+ begin
+ let time2 = Unix.gettimeofday () in
+ let time1 =
+ match !times with time1::tl -> times := tl; time1 | [] -> assert false in
+ prerr_endline ("}}} " ^ string_of_float (time2 -. time1));
+ if not ok then prerr_endline "exception raised!";
+ try
+ indent := String.sub !indent 0 (String.length !indent -1)
+ with
+ Invalid_argument _ -> indent := "??"; ()
+ end
+;;
-let pp _ = ();;
let wrap_exc msg = function
| NCicUnification.Uncertain _ -> Uncertain msg
| e -> raise e
;;
-let exp_implicit metasenv context expty =
- let foo x = match expty with Some t -> `WithType t | None -> x in
+let exp_implicit rdb ~localise metasenv subst context with_type t =
function
- | `Closed -> NCicMetaSubst.mk_meta metasenv [] (foo `Term)
- | `Type -> NCicMetaSubst.mk_meta metasenv context (foo `Type)
- | `Term -> NCicMetaSubst.mk_meta metasenv context (foo `Term)
+ | `Closed ->
+ let metasenv,subst,expty =
+ match with_type with
+ None -> metasenv,subst,None
+ | Some typ ->
+ let (metasenv,subst),typ =
+ try
+ NCicMetaSubst.delift
+ ~unify:(fun m s c t1 t2 ->
+ try Some (NCicUnification.unify rdb m s c t1 t2)
+ with NCicUnification.UnificationFailure _ | NCicUnification.Uncertain _ -> None)
+ metasenv subst context 0 (0,NCic.Irl 0) typ
+ with
+ NCicMetaSubst.MetaSubstFailure _
+ | NCicMetaSubst.Uncertain _ ->
+ raise (RefineFailure (lazy (localise t,"Trying to create a closed meta with a non closed type")))
+
+ in
+ metasenv,subst,Some typ
+ in
+ NCicMetaSubst.mk_meta metasenv [] ?with_type:expty `IsTerm,subst
+ | `Type -> NCicMetaSubst.mk_meta metasenv context ?with_type `IsType,subst
+ | `Term -> NCicMetaSubst.mk_meta metasenv context ?with_type `IsTerm,subst
+ | `Tagged s ->
+ NCicMetaSubst.mk_meta
+ ~attrs:[`Name s] metasenv context ?with_type `IsTerm,subst
+ | `Vector ->
+ raise (RefineFailure (lazy (localise t, "A vector of implicit terms " ^
+ "can only be used in argument position")))
| _ -> assert false
;;
-
let check_allowed_sort_elimination rdb localise r orig =
let mkapp he arg =
match he with
match arity1 with
| C.Prod (name,so1,de1) (* , t ==?== C.Prod _ *) ->
let metasenv, _, meta, _ =
- NCicMetaSubst.mk_meta metasenv ((name,C.Decl so1)::context) `Type
+ NCicMetaSubst.mk_meta metasenv ((name,C.Decl so1)::context) `IsType
in
let metasenv, subst =
try NCicUnification.unify rdb metasenv subst context
aux metasenv subst ((name, C.Decl so1)::context)
(mkapp (NCicSubstitution.lift 1 ind) (C.Rel 1)) de1 meta
| C.Sort _ (* , t ==?== C.Prod _ *) ->
- let metasenv, _, meta, _ = NCicMetaSubst.mk_meta metasenv [] `Type in
+ let metasenv, _, meta, _ = NCicMetaSubst.mk_meta metasenv [] `IsSort in
let metasenv, subst =
try NCicUnification.unify rdb metasenv subst context
arity2 (C.Prod ("_", ind, meta))
with exc -> raise (wrap_exc (lazy (localise orig,
"Sort elimination not allowed ")) exc))
| _ -> assert false
- (*D*)in outside(); rc with exc -> outside (); raise exc
+ (*D*)in outside true; rc with exc -> outside false; raise exc
in
aux
;;
?(localise=fun _ -> Stdpp.dummy_loc)
metasenv subst context term expty
=
- let force_ty skip_lambda metasenv subst context orig t infty expty =
+ let force_ty skip_lambda skip_appl metasenv subst context orig t infty expty =
(*D*)inside 'F'; try let rc =
match expty with
| Some expty ->
(match t with
| C.Implicit _ -> assert false
| C.Lambda _ when skip_lambda -> metasenv, subst, t, expty
+ | C.Appl _ when skip_appl -> metasenv, subst, t, expty
| _ ->
- pp (lazy (
+ pp (lazy ("forcing infty=expty: "^
(NCicPp.ppterm ~metasenv ~subst ~context infty) ^ " === " ^
(NCicPp.ppterm ~metasenv ~subst:[] ~context expty)));
try
let metasenv, subst =
+ (*D*)inside 'U'; try let rc =
NCicUnification.unify rdb metasenv subst context infty expty
+ (*D*)in outside true; rc with exc -> outside false; raise exc
in
metasenv, subst, t, expty
- with exc ->
+ with
+ | NCicUnification.Uncertain _
+ | NCicUnification.UnificationFailure _ as exc ->
try_coercions rdb ~localise
metasenv subst context t orig infty expty true exc)
| None -> metasenv, subst, t, infty
- (*D*)in outside(); rc with exc -> outside (); raise exc
+ (*D*)in outside true; rc with exc -> outside false; raise exc
in
let rec typeof_aux metasenv subst context expty =
fun t as orig ->
(*D*)inside 'R'; try let rc =
- pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t));
- pp (lazy (if expty = None then "NONE" else "SOME"));
- if (List.exists (fun (i,_) -> i=29) subst) then
- pp (lazy (NCicPp.ppsubst ~metasenv subst));
+ pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t ^ " ::exp:: " ^
+ match expty with None -> "None" | Some e ->
+ NCicPp.ppterm ~metasenv ~subst ~context e));
let metasenv, subst, t, infty =
match t with
| C.Rel n ->
raise (RefineFailure (lazy (localise t,"unbound variable"))))
in
metasenv, subst, t, infty
- | C.Sort (C.Type [false,u]) -> metasenv,subst,t,(C.Sort (C.Type [true, u]))
- | C.Sort (C.Type _) ->
- raise (AssertFailure (lazy ("Cannot type an inferred type: "^
- NCicPp.ppterm ~subst ~metasenv ~context t)))
- | C.Sort _ -> metasenv,subst,t,(C.Sort (C.Type NCicEnvironment.type0))
+ | C.Sort s ->
+ (try metasenv, subst, t, C.Sort (NCicEnvironment.typeof_sort s)
+ with
+ | NCicEnvironment.UntypableSort msg ->
+ raise (RefineFailure (lazy (localise t, Lazy.force msg)))
+ | NCicEnvironment.AssertFailure msg -> raise (AssertFailure msg))
| C.Implicit infos ->
- let metasenv,_,t,ty = exp_implicit metasenv context expty infos in
- metasenv, subst, t, ty
+ let (metasenv,_,t,ty),subst =
+ exp_implicit rdb ~localise metasenv subst context expty t infos
+ in
+ if expty = None then
+ typeof_aux metasenv subst context None t
+ else
+ metasenv, subst, t, ty
| C.Meta (n,l) as t ->
- let ty =
+ let metasenv, ty =
try
- let _,_,_,ty = NCicUtils.lookup_subst n subst in ty
- with NCicUtils.Subst_not_found _ -> try
- let _,_,ty = NCicUtils.lookup_meta n metasenv in
- match ty with C.Implicit _ ->
- prerr_endline (string_of_int n);
- prerr_endline (NCicPp.ppmetasenv ~subst metasenv);
- prerr_endline (NCicPp.ppsubst ~metasenv subst);
- assert false | _ -> ty
- with NCicUtils.Meta_not_found _ ->
- raise (AssertFailure (lazy (Printf.sprintf
- "%s not found" (NCicPp.ppterm ~subst ~metasenv ~context t))))
+ let _,_,_,ty = NCicUtils.lookup_subst n subst in metasenv, ty
+ with NCicUtils.Subst_not_found _ ->
+ NCicMetaSubst.extend_meta metasenv n
in
metasenv, subst, t, NCicSubstitution.subst_meta l ty
| C.Const _ ->
let (metasenv,subst), exp_ty_t =
match exp_s with
| Some exp_s ->
- (try NCicUnification.unify rdb metasenv subst context s exp_s,exp_ty_t
+ (try
+ pp(lazy("Force source to: "^NCicPp.ppterm ~metasenv ~subst
+ ~context exp_s));
+ NCicUnification.unify ~test_eq_only:true rdb metasenv subst context s exp_s,exp_ty_t
with exc -> raise (wrap_exc (lazy (localise orig_s, Printf.sprintf
"Source type %s was expected to be %s" (NCicPp.ppterm ~metasenv
~subst ~context s) (NCicPp.ppterm ~metasenv ~subst ~context
typeof_aux metasenv subst context_for_t exp_ty_t t
in
if force_after then
- force_ty false metasenv subst context orig
+ force_ty false true metasenv subst context orig
(C.Lambda(n,s,t)) (C.Prod (n,s,ty_t)) expty
else
metasenv, subst, C.Lambda(n,s,t), C.Prod (n,s,ty_t)
let metasenv, subst, t, _ =
typeof_aux metasenv subst context (Some ty) t in
let context1 = (n, C.Def (t,ty)) :: context in
+ let metasenv, subst, expty1 =
+ match expty with
+ | None -> metasenv, subst, None
+ | Some x ->
+ let m, s, x =
+ NCicUnification.delift_type_wrt_terms
+ rdb metasenv subst context1 (NCicSubstitution.lift 1 x)
+ [NCicSubstitution.lift 1 t]
+ in
+ m, s, Some x
+ in
let metasenv, subst, bo, bo_ty =
- typeof_aux metasenv subst context1 None bo
+ typeof_aux metasenv subst context1 expty1 bo
in
let bo_ty = NCicSubstitution.subst ~avoid_beta_redexes:true t bo_ty in
metasenv, subst, C.LetIn (n, ty, t, bo), bo_ty
| C.Appl ((he as orig_he)::(_::_ as args)) ->
- let upto =
- match orig_he with C.Meta _ -> List.length args | _ -> 0
+ let upto = match orig_he with C.Meta _ -> List.length args | _ -> 0 in
+ let hbr t =
+ if upto > 0 then NCicReduction.head_beta_reduce ~upto t else t
in
- let metasenv, subst, he, ty_he =
- typeof_aux metasenv subst context None he in
- let metasenv, subst, t, ty =
- eat_prods rdb ~localise
- metasenv subst context orig_he he ty_he args
+ let refine_appl () =
+ let metasenv, subst, he, ty_he =
+ typeof_aux metasenv subst context None he in
+ let metasenv, subst, t, ty =
+ eat_prods rdb ~localise force_ty metasenv subst context expty t
+ orig_he he ty_he args in
+ metasenv, subst, hbr t, ty
in
- let t = if upto > 0 then NCicReduction.head_beta_reduce ~upto t else t in
- metasenv, subst, t, ty
+ if args = [C.Implicit `Vector] && expty <> None then
+ (* we try here to expand the vector a 0 implicits, but we use
+ * the expected type *)
+ try
+ let metasenv, subst, he, ty_he =
+ typeof_aux metasenv subst context expty he in
+ metasenv, subst, hbr he, ty_he
+ with Uncertain _ | RefineFailure _ -> refine_appl ()
+ else refine_appl ()
| C.Appl _ -> raise (AssertFailure (lazy "Appl of length < 2"))
| C.Match (Ref.Ref (_,Ref.Ind (_,tyno,_)) as r,
outtype,(term as orig_term),pl) as orig ->
(* next lines are to do a subst-expansion of the outtype, so
that when it becomes a beta-abstraction, the beta-redex is
fired during substitution *)
- (*CSC: this is instantiate! should we move it from tactics to the
- refiner? I think so! *)
- let metasenv,metanoouttype,newouttype,metaoutsort =
- NCicMetaSubst.mk_meta metasenv context `Term in
- let metasenv,subst =
- NCicUnification.unify rdb metasenv subst context outsort metaoutsort in
- let metasenv =
- List.filter (function (j,_) -> j <> metanoouttype) metasenv in
+ let _,fresh_metanoouttype,newouttype,_ =
+ NCicMetaSubst.mk_meta metasenv context `IsTerm in
let subst =
- (metanoouttype,(Some "outtype",context,outtype,metaoutsort))::subst in
+ (fresh_metanoouttype,([`Name "outtype"],context,outtype,outsort))
+ ::subst in
let outtype = newouttype in
(* let's control if the sort elimination is allowed: [(I q1 ... qr)|B] *)
NCicTypeChecker.type_of_branch
~subst context leftno outtype cons ty_cons in
pp (lazy ("TYPEOFBRANCH: " ^
- NCicPp.ppterm ~metasenv ~subst ~context p ^ " ::: " ^
+ NCicPp.ppterm ~metasenv ~subst ~context p ^ " ::inf:: " ^
NCicPp.ppterm ~metasenv ~subst ~context ty_branch ));
let metasenv, subst, p, _ =
typeof_aux metasenv subst context (Some ty_branch) p in
metasenv, subst, C.Match (r, outtype, term, pl),resty
| C.Match _ -> assert false
in
- pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t ^ " :: "^
+ pp (lazy (NCicPp.ppterm ~metasenv ~subst ~context t ^ " ::inf:: "^
NCicPp.ppterm ~metasenv ~subst ~context infty ));
- force_ty true metasenv subst context orig t infty expty
- (*D*)in outside(); rc with exc -> outside (); raise exc
+ force_ty true true metasenv subst context orig t infty expty
+ (*D*)in outside true; rc with exc -> outside false; raise exc
in
typeof_aux metasenv subst context expty term
let rec first exc = function
| [] ->
raise (wrap_exc (lazy (localise orig_t, Printf.sprintf
- "The term %s has type %s but is here used with type %s"
+ "The term\n%s\nhas type\n%s\nbut is here used with type\n%s"
(NCicPp.ppterm ~metasenv ~subst ~context t)
(NCicPp.ppterm ~metasenv ~subst ~context infty)
(NCicPp.ppterm ~metasenv ~subst ~context expty))) exc)
- | (metasenv, newterm, newtype, meta)::tl ->
+ | (_,metasenv, newterm, newtype, meta)::tl ->
try
+ pp (lazy("K=" ^ NCicPp.ppterm ~metasenv ~subst ~context newterm));
pp (lazy ( "UNIFICATION in CTX:\n"^
NCicPp.ppcontext ~metasenv ~subst context
^ "\nMENV: " ^
NCicPp.ppmetasenv metasenv ~subst
^ "\nOF: " ^
- NCicPp.ppterm ~metasenv ~subst ~context meta ^ " === " ^
- NCicPp.ppterm ~metasenv ~subst ~context t ^ "\n"));
+ NCicPp.ppterm ~metasenv ~subst ~context t ^ " === " ^
+ NCicPp.ppterm ~metasenv ~subst ~context meta ^ "\n"));
let metasenv, subst =
- NCicUnification.unify rdb metasenv subst context meta t
+ NCicUnification.unify rdb metasenv subst context t meta
in
pp (lazy ( "UNIFICATION in CTX:\n"^
NCicPp.ppcontext ~metasenv ~subst context
| NCicUnification.UnificationFailure _ -> first exc tl
| NCicUnification.Uncertain _ as exc -> first exc tl
in
+ pp(lazy("try_coercion " ^
+ NCicPp.ppterm ~metasenv ~subst ~context infty ^ " |---> " ^
+ NCicPp.ppterm ~metasenv ~subst ~context expty));
first exc
- (NCicCoercion.look_for_coercion rdb metasenv subst context infty expty)
+ (NCicCoercion.look_for_coercion
+ rdb metasenv subst context infty expty)
and force_to_sort rdb metasenv subst context t orig_t localise ty =
match NCicReduction.whd ~subst context ty with
| C.Sort _ as ty -> metasenv, subst, t, ty
| ty ->
try_coercions rdb ~localise metasenv subst context
- t orig_t ty (NCic.Sort (NCic.Type NCicEnvironment.type0)) false
+ t orig_t ty (NCic.Sort (NCic.Type
+ (match NCicEnvironment.get_universes () with
+ | x::_ -> x
+ | _ -> assert false))) false
(Uncertain (lazy (localise orig_t,
"The type of " ^ NCicPp.ppterm ~metasenv ~subst ~context t
^ " is not a sort: " ^ NCicPp.ppterm ~metasenv ~subst ~context ty)))
with NCicUtils.Subst_not_found _ -> aux 'M')
| _ -> aux 'H'
-and eat_prods rdb
- ~localise metasenv subst context orig_he he ty_he args
-=
+and eat_prods rdb ~localise force_ty metasenv subst context expty orig_t orig_he he ty_he args =
(*D*)inside 'E'; try let rc =
- let rec aux metasenv subst args_so_far he ty_he = function
- | []->metasenv, subst, NCicUntrusted.mk_appl he (List.rev args_so_far), ty_he
+ let rec aux metasenv subst args_so_far he ty_he xxx =
+ (*D*)inside 'V'; try let rc =
+ match xxx with
+ | [] ->
+ let res = NCicUntrusted.mk_appl he (List.rev args_so_far) in
+ pp(lazy("FORCE FINAL APPL: " ^
+ NCicPp.ppterm ~metasenv ~subst ~context res ^
+ " of type " ^ NCicPp.ppterm ~metasenv ~subst ~context ty_he
+ ^ " to type " ^ match expty with None -> "None" | Some x ->
+ NCicPp.ppterm ~metasenv ~subst ~context x));
+ (* whatever the term is, we force the type. in case of ((Lambda..) ?...)
+ * the application may also be a lambda! *)
+ force_ty false false metasenv subst context orig_t res ty_he expty
+ | NCic.Implicit `Vector::tl ->
+ let has_some_more_pis x =
+ match NCicReduction.whd ~subst context x with
+ | NCic.Meta _ | NCic.Appl (NCic.Meta _::_) -> false
+ | _ -> true
+ in
+ (try
+ aux metasenv subst args_so_far he ty_he tl
+ with
+ | Uncertain _
+ | RefineFailure _ as exc when has_some_more_pis ty_he ->
+ (try
+ aux metasenv subst args_so_far he ty_he
+ (NCic.Implicit `Term :: NCic.Implicit `Vector :: tl)
+ with
+ Uncertain msg | RefineFailure msg -> raise (wrap_exc msg exc))
+ | RefineFailure msg when not (has_some_more_pis ty_he) ->
+ (* instantiating the head could change the has_some_more_pis flag *)
+ raise (Uncertain msg))
| arg::tl ->
match NCicReduction.whd ~subst context ty_he with
| C.Prod (_,s,t) ->
let metasenv, subst, arg, _ =
- typeof rdb ~localise
- metasenv subst context arg (Some s) in
+ typeof rdb ~localise metasenv subst context arg (Some s) in
let t = NCicSubstitution.subst ~avoid_beta_redexes:true arg t in
aux metasenv subst (arg :: args_so_far) he t tl
| C.Meta _
| C.Appl (C.Meta _ :: _) as t ->
let metasenv, subst, arg, ty_arg =
- typeof rdb ~localise
- metasenv subst context arg None in
+ typeof rdb ~localise metasenv subst context arg None in
let name = guess_name subst context ty_arg in
let metasenv, _, meta, _ =
NCicMetaSubst.mk_meta metasenv
- ((name,C.Decl ty_arg) :: context) `Type
+ ((name,C.Decl ty_arg) :: context) `IsType
in
let flex_prod = C.Prod (name, ty_arg, meta) in
(* next line grants that ty_args is a type *)
let metasenv,subst, flex_prod, _ =
- typeof rdb ~localise metasenv subst
- context flex_prod None in
+ typeof rdb ~localise metasenv subst context flex_prod None in
+(*
pp (lazy ( "UNIFICATION in CTX:\n"^
NCicPp.ppcontext ~metasenv ~subst context
^ "\nOF: " ^
NCicPp.ppterm ~metasenv ~subst ~context t ^ " === " ^
NCicPp.ppterm ~metasenv ~subst ~context flex_prod ^ "\n"));
- let metasenv, subst =
+*)
+ let metasenv, subst =
try NCicUnification.unify rdb metasenv subst context t flex_prod
with exc -> raise (wrap_exc (lazy (localise orig_he, Printf.sprintf
("The term %s has an inferred type %s, but is applied to the" ^^
(NCicPp.ppterm ~metasenv ~subst ~context he)
(NCicPp.ppterm ~metasenv ~subst ~context t)
(NCicPp.ppterm ~metasenv ~subst ~context arg)
- (NCicPp.ppterm ~metasenv ~subst ~context ty_arg))) exc)
+ (NCicPp.ppterm ~metasenv ~subst ~context ty_arg)))
+ (match exc with
+ | NCicUnification.UnificationFailure m ->
+ NCicUnification.Uncertain m
+ | x -> x))
(* XXX coerce to funclass *)
in
let meta = NCicSubstitution.subst ~avoid_beta_redexes:true arg meta in
"only %d arguments") (NCicPp.ppterm ~metasenv ~subst ~context he)
(List.length args) (List.length args_so_far))))
in
- aux metasenv subst [] newhead newheadty (arg :: tl)
+ aux metasenv subst [] newhead newheadty (arg :: tl)
+ (*D*)in outside true; rc with exc -> outside false; raise exc
in
(* We need to reverse the order of the new created metas since they
are pushed on top of the metasenv in the wrong order *)
List.partition (fun (i,_) -> i <= highest_meta) metasenv
in
(List.rev metasenv_new) @ metasenv_old, subst, newhead, newheadty
- (*D*)in outside(); rc with exc -> outside (); raise exc
+ (*D*)in outside true; rc with exc -> outside false; raise exc
;;
let rec first f l1 l2 =
"and those of its inductive type"))))
else
metasenv,subst,item1::context
- ) (metasenv,subst,[]) sx_context_ty_rev sx_context_te_rev
+ ) (metasenv,subst,tys) sx_context_ty_rev sx_context_te_rev
with Invalid_argument "List.fold_left2" -> assert false in
let con_sort= NCicTypeChecker.typeof ~subst ~metasenv context te in
(match
uri, height, metasenv, subst, C.Inductive (ind, leftno, itl, attr)
;;
-NCicUnification.set_refiner_typeof typeof;;
-
(* vim:set foldmethod=marker: *)
projects / helm.git / blobdiff