-let product f l1 l2 =
- List.fold_left
- (fun acc x ->
- List.fold_left
- (fun acc y ->
- f x y :: acc)
- acc l2)
- [] l1
-;;
-
-let pos_in_list x l =
- match
- HExtlib.list_findopt (fun y i -> if y = x then Some i else None) l
- with
- | Some i -> i
- | None -> assert false
-;;
-
-let pos_of x t =
- match t with
- | NCic.Appl l -> pos_in_list x l
- | _ -> assert false
-;;
-
-let rec count_prod = function
- | NCic.Prod (_,_,x) -> 1 + count_prod x
- | _ -> 0
-;;
-
-let term_at i t =
- match t with
- | NCic.Appl l ->
- (match
- HExtlib.list_findopt (fun y j -> if i+1=j then Some y else None) l
- with
- | Some i -> i
- | None -> assert false)
- | _ -> assert false
-;;
-
-let src_tgt_of_ty_cpos_arity ty cpos arity =
- let pis = count_prod ty in
- let tpos = pis - arity in
- let rec aux i j = function
- | NCic.Prod (_,s,_) when i = j -> s
- | NCic.Prod (_,_,t) -> aux (i+1) j t
- | t -> assert (i = j); t
- in
- let mask t =
- let rec aux () = function
- | NCic.Meta _
- | NCic.Implicit _ as x -> x
- | NCic.Rel _ -> NCic.Implicit `Type
- | t -> NCicUtils.map (fun _ () -> ()) () aux t
- in
- aux () t
- in
- mask (aux 0 cpos ty), mask (aux 0 tpos ty)
-;;
-
-let close_in_context t metasenv =
- let rec aux m_subst subst ctx = function
- | (i,(tag,[],ty)) :: tl ->
- let name = "x" ^ string_of_int (List.length ctx) in
- let subst = (i,(tag,[],NCic.Rel (List.length tl+1),ty))::subst in
- let ty = NCicUntrusted.apply_subst (m_subst (List.length ctx)) ctx ty in
- let m_subst m =
- (i,(tag,[],NCic.Rel (m-List.length ctx),ty))::(m_subst m)
- in
- NCic.Lambda (name, ty, aux m_subst subst ((name,NCic.Decl ty)::ctx) tl)
- | [] ->
- (* STRONG ASSUMPTION:
- since metas occurring in t have an empty context,
- the substitution i build makes sense (i.e, the Rel
- I pun in the subst will not be lifted by subst_meta *)
- NCicUntrusted.apply_subst subst ctx
- (NCicSubstitution.lift (List.length ctx) t)
- | _ -> assert false
- in
- aux (fun _ -> []) [] [] metasenv
-;;
-
-let toposort metasenv =
- let module T = HTopoSort.Make(
- struct type t = int * NCic.conjecture let compare (i,_) (j,_) = i-j end)
- in
- let deps (_,(_,_,t)) =
- List.filter (fun (j,_) ->
- List.mem j (NCicUntrusted.metas_of_term [] [] t)) metasenv
- in
- T.topological_sort metasenv deps
-;;
-
-let basic_eval_ncoercion (name,t,s,d,p,a) status =
- let to_s =
- NCicCoercion.look_for_coercion status [] [] [] (NCic.Implicit `Type) s
- in
- let from_d =
- NCicCoercion.look_for_coercion status [] [] [] d (NCic.Implicit `Type)
- in
- let status = NCicCoercion.index_coercion status t s d a p in
- let c =
- List.find
- (function (_,NCic.Appl (x::_),_,_) -> x = t | _ -> assert false)
- (NCicCoercion.look_for_coercion status [] [] [] s d)
- in
- let composites =
- let to_s_o_c =
- product (fun (m1,t1,_,j) (mc,c,_,i) -> m1@mc,c,[i,t1],j,a)
- to_s [c]
- in
- let c_o_from_d =
- product (fun (mc,c,_,j) (m1,t1,ty,i) -> m1@mc,t1,[i,c],j,count_prod ty)
- [c] from_d
- in
- let to_s_o_c_o_from_d =
- product (fun (m1,t1,_,j) (m,t,upl,i,a)->
- m@m1,t,(i,t1)::upl,j,a)
- to_s c_o_from_d
- in
- to_s_o_c @ c_o_from_d @ to_s_o_c_o_from_d
- in
- let composites =
- HExtlib.filter_map
- (fun (metasenv, bo, upl, p, arity) ->
- try
- let metasenv, subst =
- List.fold_left
- (fun (metasenv,subst) (a,b) ->
- NCicUnification.unify status metasenv subst [] a b)
- (metasenv,[]) upl
- in
- let bo = NCicUntrusted.apply_subst subst [] bo in
- let metasenv = toposort metasenv in
- let bo = close_in_context bo metasenv in
- let pos =
- match p with
- | NCic.Meta (p,_) -> pos_in_list p (List.map fst metasenv)
- | _ -> assert false
- in
- let ty = NCicTypeChecker.typeof ~metasenv:[] ~subst:[] [] bo in
- let src,tgt = src_tgt_of_ty_cpos_arity ty pos arity in
-(*
- prerr_endline (
- NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] bo ^ " : " ^
- NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] ty ^ " as " ^
- NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] src ^ " ===> " ^
- NCicPp.ppterm ~metasenv:[] ~subst:[] ~context:[] tgt ^
- " cpos=" ^ string_of_int pos ^ " arity=" ^ string_of_int arity);
-*)
- Some (bo,src,tgt,arity,pos)
- with
- | NCicTypeChecker.TypeCheckerFailure _
- | NCicUnification.UnificationFailure _
- | NCicUnification.Uncertain _ -> None
- ) composites
- in
- List.fold_left
- (fun st (t,s,d,a,p) -> NCicCoercion.index_coercion st t s d a p)
- status composites
-;;