Quellcode-Bibliothek

^© Kompilation durch diese Firma

[Weder Korrektheit noch Funktionsfähigkeit der Software werden zugesichert.]

Datei: seq2set.prf Sprache: SML

Original von: Coq^©

(************************************************************************)
(*         *   The Coq Proof Assistant / The Coq Development Team       *)
(*  v      *   INRIA, CNRS and contributors - Copyright 1999-2018       *)
(* <O___,, *       (see CREDITS file for the list of authors)           *)
(*   \VV/  **************************************************************)
(*    //   *    This file is distributed under the terms of the         *)
(*         *     GNU Lesser General Public License Version 2.1          *)
(*         *     (see LICENSE file for the text of the license)         *)
(************************************************************************)

open Pp
open CErrors
open Util
open CAst
open Names
open Nameops
open Namegen
open Constr
open Context
open Libnames
open Globnames
open Impargs
open Glob_term
open Glob_ops
open Patternops
open Pretyping
open Cases
open Constrexpr
open Constrexpr_ops
open Notation_term
open Notation_ops
open Notation
open Inductiveops
open Decl_kinds
open Context.Rel.Declaration

(** constr_expr -> glob_constr translation:
    - it adds holes for implicit arguments
    - it replaces notations by their value (scopes stuff are here)
    - it recognizes global vars from local ones
    - it prepares pattern matching problems (a pattern becomes a tree
      where nodes are constructor/variable pairs and leafs are variables)

    All that at once, fasten your seatbelt!
*)

(* To interpret implicits and arg scopes of variables in inductive
   types and recursive definitions and of projection names in records *)

type var_internalization_type =
  | Inductive of Id.t list (* list of params *) * bool (* true = check for possible capture *)
  | Recursive
  | Method
  | Variable

type var_internalization_data =
    (* type of the "free" variable, for coqdoc, e.g. while typing the
       constructor of JMeq, "JMeq" behaves as a variable of type Inductive *)
    var_internalization_type *
    (* impargs to automatically add to the variable, e.g. for "JMeq A a B b"
       in implicit mode, this is [A;B] and this adds (A:=A) and (B:=B) *)
    Id.t list *
    (* signature of impargs of the variable *)
    Impargs.implicit_status list *
    (* subscopes of the args of the variable *)
    scope_name option list

type internalization_env =
    (var_internalization_data) Id.Map.t

type ltac_sign = {
  ltac_vars : Id.Set.t;
  ltac_bound : Id.Set.t;
  ltac_extra : Genintern.Store.t;
}

let interning_grammar = ref false

(* Historically for parsing grammar rules, but in fact used only for
   translator, v7 parsing, and unstrict tactic internalization *)
let for_grammar f x =
  interning_grammar := true;
  let a = f x in
    interning_grammar := false;
    a

(**********************************************************************)
(* Locating reference, possibly via an abbreviation *)

let locate_reference qid =
  Smartlocate.global_of_extended_global (Nametab.locate_extended qid)

let is_global id =
  try
    let _ = locate_reference (qualid_of_ident id) in true
  with Not_found ->
    false

let global_reference_of_reference qid =
  locate_reference qid

let global_reference id =
  locate_reference (qualid_of_ident id)

let construct_reference ctx id =
  try
    VarRef (let _ = Context.Named.lookup id ctx in id)
  with Not_found ->
    global_reference id

let global_reference_in_absolute_module dir id =
  Nametab.global_of_path (Libnames.make_path dir id)

(**********************************************************************)
(* Internalization errors                                             *)

type internalization_error =
  | VariableCapture of Id.t * Id.t
  | IllegalMetavariable
  | NotAConstructor of qualid
  | UnboundFixName of bool * Id.t
  | NonLinearPattern of Id.t
  | BadPatternsNumber of int * int
  | NotAProjection of qualid
  | NotAProjectionOf of qualid * qualid
  | ProjectionsOfDifferentRecords of qualid * qualid

exception InternalizationError of internalization_error Loc.located

let explain_variable_capture id id' =
  Id.print id ++ str " is dependent in the type of " ++ Id.print id' ++
  strbrk ": cannot interpret both of them with the same type"

let explain_illegal_metavariable =
  str "Metavariables allowed only in patterns"

let explain_not_a_constructor qid =
  str "Unknown constructor: " ++ pr_qualid qid

let explain_unbound_fix_name is_cofix id =
  str "The name" ++ spc () ++ Id.print id ++
  spc () ++ str "is not bound in the corresponding" ++ spc () ++
  str (if is_cofix then "co" else "") ++ str "fixpoint definition"

let explain_non_linear_pattern id =
  str "The variable " ++ Id.print id ++ str " is bound several times in pattern"

let explain_bad_patterns_number n1 n2 =
  str "Expecting " ++ int n1 ++ str (String.plural n1 " pattern") ++
  str " but found " ++ int n2

let explain_field_not_a_projection field_id =
  pr_qualid field_id ++ str ": Not a projection"

let explain_field_not_a_projection_of field_id inductive_id =
  pr_qualid field_id ++ str ": Not a projection of inductive " ++ pr_qualid inductive_id

let explain_projections_of_diff_records inductive1_id inductive2_id =
  str "This record contains fields of both " ++ pr_qualid inductive1_id ++
  str " and " ++ pr_qualid inductive2_id

let explain_internalization_error e =
  let pp = match e with
  | VariableCapture (id,id') -> explain_variable_capture id id'
  | IllegalMetavariable -> explain_illegal_metavariable
  | NotAConstructor ref -> explain_not_a_constructor ref
  | UnboundFixName (iscofix,id) -> explain_unbound_fix_name iscofix id
  | NonLinearPattern id -> explain_non_linear_pattern id
  | BadPatternsNumber (n1,n2) -> explain_bad_patterns_number n1 n2
  | NotAProjection field_id -> explain_field_not_a_projection field_id
  | NotAProjectionOf (field_id, inductive_id) ->
    explain_field_not_a_projection_of field_id inductive_id
  | ProjectionsOfDifferentRecords (inductive1_id, inductive2_id) ->
    explain_projections_of_diff_records inductive1_id inductive2_id
  in pp ++ str "."

let error_bad_inductive_type ?loc =
  user_err ?loc  (str
    "This should be an inductive type applied to patterns.")

let error_parameter_not_implicit ?loc =
  user_err ?loc  (str
   "The parameters do not bind in patterns;" ++ spc () ++ str
    "they must be replaced by '_'.")

let error_ldots_var ?loc =
  user_err ?loc  (str "Special token " ++ Id.print ldots_var ++
    str " is for use in the Notation command.")

(**********************************************************************)
(* Pre-computing the implicit arguments and arguments scopes needed   *)
(* for interpretation *)

let parsing_explicit = ref false

let empty_internalization_env = Id.Map.empty

let compute_explicitable_implicit imps = function
  | Inductive (params,_) ->
      (* In inductive types, the parameters are fixed implicit arguments *)
      let sub_impl,_ = List.chop (List.length params) imps in
      let sub_impl' = List.filter is_status_implicit sub_impl in
      List.map name_of_implicit sub_impl'
  | Recursive | Method | Variable ->
      (* Unable to know in advance what the implicit arguments will be *)
      []

let compute_internalization_data env sigma ty typ impl =
  let impl = compute_implicits_with_manual env sigma typ (is_implicit_args()) impl in
  let expls_impl = compute_explicitable_implicit impl ty in
  (ty, expls_impl, impl, compute_arguments_scope sigma typ)

let compute_internalization_env env sigma ?(impls=empty_internalization_env) ty =
  List.fold_left3
    (fun map id typ impl -> Id.Map.add id (compute_internalization_data env sigma ty typ impl) map)
    impls

(**********************************************************************)
(* Contracting "{ _ }" in notations *)

let rec wildcards ntn n =
  if Int.equal n (String.length ntn) then []
  else let l = spaces ntn (n+1) in if ntn.[n] == '_' then n::l else l
and spaces ntn n =
  if Int.equal n (String.length ntn) then []
  else if ntn.[n] == ' ' then wildcards ntn (n+1) else spaces ntn (n+1)

let expand_notation_string ntn n =
  let pos = List.nth (wildcards ntn 0) n in
  let hd = if Int.equal pos 0 then "" else String.sub ntn 0 pos in
  let tl =
    if Int.equal pos (String.length ntn) then ""
    else String.sub ntn (pos+1) (String.length ntn - pos -1) in
  hd ^ "{ _ }" ^ tl

(* This contracts the special case of "{ _ }" for sumbool, sumor notations *)
(* Remark: expansion of squash at definition is done in metasyntax.ml *)
let contract_curly_brackets ntn (l,ll,bl,bll) =
  match ntn with
  | InCustomEntryLevel _,_ -> ntn,(l,ll,bl,bll)
  | InConstrEntrySomeLevel, ntn ->
  let ntn' = ref ntn in
  let rec contract_squash n = function
    | [] -> []
    | { CAst.v = CNotation ((InConstrEntrySomeLevel,"{ _ }"),([a],[],[],[])) } :: l ->
        ntn' := expand_notation_string !ntn' n;
        contract_squash n (a::l)
    | a :: l ->
        a::contract_squash (n+1) l in
  let l = contract_squash 0 l in
  (* side effect; don't inline *)
  (InConstrEntrySomeLevel,!ntn'),(l,ll,bl,bll)

let contract_curly_brackets_pat ntn (l,ll) =
  match ntn with
  | InCustomEntryLevel _,_ -> ntn,(l,ll)
  | InConstrEntrySomeLevel, ntn ->
  let ntn' = ref ntn in
  let rec contract_squash n = function
    | [] -> []
    | { CAst.v = CPatNotation ((InConstrEntrySomeLevel,"{ _ }"),([a],[]),[]) } :: l ->
        ntn' := expand_notation_string !ntn' n;
        contract_squash n (a::l)
    | a :: l ->
        a::contract_squash (n+1) l in
  let l = contract_squash 0 l in
  (* side effect; don't inline *)
  (InConstrEntrySomeLevel,!ntn'),(l,ll)

type intern_env = {
  ids: Names.Id.Set.t;
  unb: bool;
  tmp_scope: Notation_term.tmp_scope_name option;
  scopes: Notation_term.scope_name list;
  impls: internalization_env }

(**********************************************************************)
(* Remembering the parsing scope of variables in notations            *)

let make_current_scope tmp scopes = match tmp, scopes with
| Some tmp_scope, (sc :: _) when String.equal sc tmp_scope -> scopes
| Some tmp_scope, scopes -> tmp_scope :: scopes
| None, scopes -> scopes

let pr_scope_stack = function
  | [] -> str "the empty scope stack"
  | [a] -> str "scope " ++ str a
  | l -> str "scope stack " ++
      str "[" ++ prlist_with_sep pr_comma str l ++ str "]"

let error_inconsistent_scope ?loc id scopes1 scopes2 =
  user_err ?loc ~hdr:"set_var_scope"
   (Id.print id ++ str " is here used in " ++
    pr_scope_stack scopes2 ++ strbrk " while it was elsewhere used in " ++
    pr_scope_stack scopes1)

let error_expect_binder_notation_type ?loc id =
  user_err ?loc
   (Id.print id ++
    str " is expected to occur in binding position in the right-hand side.")

let set_var_scope ?loc id istermvar (tmp_scope,subscopes as scopes) ntnvars =
  try
    let used_as_binder,idscopes,typ = Id.Map.find id ntnvars in
    if not istermvar then used_as_binder := true;
    let () = if istermvar then
      (* scopes have no effect on the interpretation of identifiers *)
      begin match !idscopes with
      | None -> idscopes := Some scopes
      | Some (tmp_scope', subscopes') ->
        let s' = make_current_scope tmp_scope' subscopes' in
        let s = make_current_scope tmp_scope subscopes in
        if not (List.equal String.equal s' s) then error_inconsistent_scope ?loc id s' s
      end
    in
    match typ with
    | Notation_term.NtnInternTypeOnlyBinder ->
if istermvar then error_expect_binder_notation_type ?loc id
    | Notation_term.NtnInternTypeAny -> ()
  with Not_found ->
    (* Not in a notation *)
    ()

let set_type_scope env = {env with tmp_scope = Notation.current_type_scope_name ()}

let reset_tmp_scope env = {env with tmp_scope = None}

let set_env_scopes env (scopt,subscopes) =
  {env with tmp_scope = scopt; scopes = subscopes @ env.scopes}

let mkGProd ?loc (na,bk,t) body = DAst.make ?loc @@ GProd (na, bk, t, body)
let mkGLambda ?loc (na,bk,t) body = DAst.make ?loc @@ GLambda (na, bk, t, body)

(**********************************************************************)
(* Utilities for binders                                              *)
let build_impls = function
  |Implicit -> (function
    |Name id ->  Some (id, Impargs.Manual, (true,true))
    |Anonymous -> Some (Id.of_string "_", Impargs.Manual, (true,true)))
  |Explicit -> fun _ -> None

let impls_type_list ?(args = []) =
  let rec aux acc c = match DAst.get c with
    | GProd (na,bk,_,c) -> aux ((build_impls bk na)::acc) c
    | _ -> (Variable,[],List.append args (List.rev acc),[])
  in aux []

let impls_term_list ?(args = []) =
  let rec aux acc c = match DAst.get c with
    | GLambda (na,bk,_,c) -> aux ((build_impls bk na)::acc) c
    | GRec (fix_kind, nas, args, tys, bds) ->
       let nb = match fix_kind with |GFix (_, n) -> n | GCoFix n -> n in
       let acc' = List.fold_left (fun a (na, bk, _, _) -> (build_impls bk na)::a) acc args.(nb) in
  aux acc' bds.(nb)
    |_ -> (Variable,[],List.append args (List.rev acc),[])
  in aux []

(* Check if in binder "(x1 x2 .. xn : t)", none of x1 .. xn-1 occurs in t *)
let rec check_capture ty = let open CAst in function
  | { loc; v = Name id } :: { v = Name id' } :: _ when occur_glob_constr id ty ->
      raise (InternalizationError (loc,VariableCapture (id,id')))
  | _::nal ->
      check_capture ty nal
  | [] ->
      ()

let locate_if_hole ?loc na c = match DAst.get c with
  | GHole (_,naming,arg) ->
      (try match na with
| Name id -> glob_constr_of_notation_constr ?loc
                (Reserve.find_reserved_type id)
| Anonymous -> raise Not_found
      with Not_found -> DAst.make ?loc @@ GHole (Evar_kinds.BinderType na, naming, arg))
  | _ -> c

let reset_hidden_inductive_implicit_test env =
  { env with impls = Id.Map.map (function
         | (Inductive (params,_),b,c,d) -> (Inductive (params,false),b,c,d)
         | x -> x) env.impls }

let check_hidden_implicit_parameters ?loc id impls =
  if Id.Map.exists (fun _ -> function
    | (Inductive (indparams,check),_,_,_) when check -> Id.List.mem id indparams
    | _ -> false) impls
  then
    user_err ?loc (Id.print id ++ strbrk " is already used as name of " ++
      strbrk "a parameter of the inductive type; bound variables in " ++
      strbrk "the type of a constructor shall use a different name.")

let pure_push_name_env (id,implargs) env =
  {env with ids = Id.Set.add id env.ids; impls = Id.Map.add id implargs env.impls}

let push_name_env ?(global_level=false) ntnvars implargs env =
  let open CAst in
  function
  | { loc; v = Anonymous } ->
      if global_level then
user_err ?loc (str "Anonymous variables not allowed");
      env
  | { loc; v = Name id } ->
      check_hidden_implicit_parameters ?loc id env.impls ;
      if Id.Map.is_empty ntnvars && Id.equal id ldots_var
        then error_ldots_var ?loc;
      set_var_scope ?loc id false (env.tmp_scope,env.scopes) ntnvars;
      if global_level then Dumpglob.dump_definition CAst.(make ?loc id) true "var"
      else Dumpglob.dump_binding ?loc id;
      pure_push_name_env (id,implargs) env

let remember_binders_impargs env bl =
  List.map_filter (fun (na,_,_,_) ->
      match na with
      | Anonymous -> None
      | Name id -> Some (id,Id.Map.find id env.impls)) bl

let restore_binders_impargs env l =
  List.fold_right pure_push_name_env l env

let intern_generalized_binder ?(global_level=false) intern_type ntnvars
    env {loc;v=na} b' t ty =
  let ids = (match na with Anonymous -> fun x -> x | Name na -> Id.Set.add na) env.ids in
  let ty, ids' =
    if t then ty, ids else
      Implicit_quantifiers.implicit_application ids
Implicit_quantifiers.combine_params_freevar ty
  in
  let ty' = intern_type {env with ids = ids; unb = true} ty in
  let fvs = Implicit_quantifiers.generalizable_vars_of_glob_constr ~bound:ids ~allowed:ids' ty' in
  let env' = List.fold_left
    (fun env {loc;v=x} -> push_name_env ~global_level ntnvars (Variable,[],[],[])(*?*) env (make ?loc @@ Name x))
    env fvs in
  let bl = List.map
    CAst.(map (fun id ->
      (Name id, Implicit, DAst.make ?loc @@ GHole (Evar_kinds.BinderType (Name id), IntroAnonymous, None))))
    fvs
  in
  let na = match na with
    | Anonymous ->
if global_level then na
else
   let name =
     let id =
       match ty with
              | { v = CApp ((_, { v = CRef (qid,_) } ), _) } when qualid_is_ident qid ->
                qualid_basename qid
       | _ -> default_non_dependent_ident
     in Implicit_quantifiers.make_fresh ids' (Global.env ()) id
   in Name name
    | _ -> na
  in (push_name_env ~global_level ntnvars (impls_type_list ty')(*?*) env' (make ?loc na)), (make ?loc (na,b',ty')) :: List.rev bl

let intern_assumption intern ntnvars env nal bk ty =
  let intern_type env = intern (set_type_scope env) in
  match bk with
  | Default k ->
      let ty = intern_type env ty in
      check_capture ty nal;
      let impls = impls_type_list ty in
      List.fold_left
        (fun (env, bl) ({loc;v=na} as locna) ->
          (push_name_env ntnvars impls env locna,
           (make ?loc (na,k,locate_if_hole ?loc na ty))::bl))
(env, []) nal
  | Generalized (b',t) ->
     let env, b = intern_generalized_binder intern_type ntnvars env (List.hd nal) b' t ty in
     env, b

let glob_local_binder_of_extended = DAst.with_loc_val (fun ?loc -> function
  | GLocalAssum (na,bk,t) -> (na,bk,None,t)
  | GLocalDef (na,bk,c,Some t) -> (na,bk,Some c,t)
  | GLocalDef (na,bk,c,None) ->
      let t = DAst.make ?loc @@ GHole(Evar_kinds.BinderType na,IntroAnonymous,None) in
      (na,bk,Some c,t)
  | GLocalPattern (_,_,_,_) ->
      Loc.raise ?loc (Stream.Error "pattern with quote not allowed here")
  )

let intern_cases_pattern_fwd = ref (fun _ -> failwith "intern_cases_pattern_fwd")

let intern_letin_binder intern ntnvars env (({loc;v=na} as locna),def,ty) =
  let term = intern env def in
  let ty = Option.map (intern env) ty in
  (push_name_env ntnvars (impls_term_list term) env locna,
   (na,Explicit,term,ty))

let intern_cases_pattern_as_binder ?loc ntnvars env p =
  let il,disjpat =
    let (il, subst_disjpat) = !intern_cases_pattern_fwd ntnvars (None,env.scopes) p in
    let substl,disjpat = List.split subst_disjpat in
    if not (List.for_all (fun subst -> Id.Map.equal Id.equal subst Id.Map.empty) substl) then
      user_err ?loc (str "Unsupported nested \"as\" clause.");
    il,disjpat
  in
  let env = List.fold_right (fun {loc;v=id} env -> push_name_env ntnvars (Variable,[],[],[]) env (make ?loc @@ Name id)) il env in
  let na = alias_of_pat (List.hd disjpat) in
  let ienv = Name.fold_right Id.Set.remove na env.ids in
  let id = Namegen.next_name_away_with_default "pat" na ienv in
  let na = make ?loc @@ Name id in
  env,((disjpat,il),id),na

let intern_local_binder_aux ?(global_level=false) intern ntnvars (env,bl) = function
  | CLocalAssum(nal,bk,ty) ->
      let env, bl' = intern_assumption intern ntnvars env nal bk ty in
      let bl' = List.map (fun {loc;v=(na,c,t)} -> DAst.make ?loc @@ GLocalAssum (na,c,t)) bl' in
      env, bl' @ bl
  | CLocalDef( {loc; v=na} as locna,def,ty) ->
     let env,(na,bk,def,ty) = intern_letin_binder intern ntnvars env (locna,def,ty) in
     env, (DAst.make ?loc @@ GLocalDef (na,bk,def,ty)) :: bl
  | CLocalPattern {loc;v=(p,ty)} ->
      let tyc =
        match ty with
        | Some ty -> ty
        | None -> CAst.make ?loc @@ CHole(None,IntroAnonymous,None)
      in
      let env, ((disjpat,il),id),na = intern_cases_pattern_as_binder ?loc ntnvars env p in
      let bk = Default Explicit in
      let _, bl' = intern_assumption intern ntnvars env [na] bk tyc in
      let {v=(_,bk,t)} = List.hd bl' in
      (env, (DAst.make ?loc @@ GLocalPattern((disjpat,List.map (fun x -> x.v) il),id,bk,t)) :: bl)

let intern_generalization intern env ntnvars loc bk ak c =
  let c = intern {env with unb = true} c in
  let fvs = Implicit_quantifiers.generalizable_vars_of_glob_constr ~bound:env.ids c in
  let env', c' =
    let abs =
      let pi = match ak with
| Some AbsPi -> true
        | Some _ -> false
| None ->
          match Notation.current_type_scope_name () with
          | Some type_scope ->
              let is_type_scope = match env.tmp_scope with
              | None -> false
              | Some sc -> String.equal sc type_scope
              in
              is_type_scope ||
              String.List.mem type_scope env.scopes
          | None -> false
      in
if pi then
          (fun {loc=loc';v=id} acc ->
            DAst.make ?loc:(Loc.merge_opt loc' loc) @@
            GProd (Name id, bk, DAst.make ?loc:loc' @@ GHole (Evar_kinds.BinderType (Name id), IntroAnonymous, None), acc))
else
          (fun {loc=loc';v=id} acc ->
            DAst.make ?loc:(Loc.merge_opt loc' loc) @@
            GLambda (Name id, bk, DAst.make ?loc:loc' @@ GHole (Evar_kinds.BinderType (Name id), IntroAnonymous, None), acc))
    in
      List.fold_right (fun ({loc;v=id} as lid) (env, acc) ->
        let env' = push_name_env ntnvars (Variable,[],[],[]) env CAst.(make @@ Name id) in
   (env', abs lid acc)) fvs (env,c)
  in c'

let rec expand_binders ?loc mk bl c =
  match bl with
  | [] -> c
  | b :: bl ->
     match DAst.get b with
     | GLocalDef (n, bk, b, oty) ->
        expand_binders ?loc mk bl (DAst.make ?loc @@ GLetIn (n, b, oty, c))
     | GLocalAssum (n, bk, t) ->
        expand_binders ?loc mk bl (mk ?loc (n,bk,t) c)
     | GLocalPattern ((disjpat,ids), id, bk, ty) ->
        let tm = DAst.make ?loc (GVar id) in
        (* Distribute the disjunctive patterns over the shared right-hand side *)
        let eqnl = List.map (fun pat -> CAst.make ?loc (ids,[pat],c)) disjpat in
        let c = DAst.make ?loc @@ GCases (LetPatternStyle, None, [tm,(Anonymous,None)], eqnl) in
        expand_binders ?loc mk bl (mk ?loc (Name id,Explicit,ty) c)

(**********************************************************************)
(* Syntax extensions                                                  *)

let option_mem_assoc id = function
  | Some (id',c) -> Id.equal id id'
  | None -> false

let find_fresh_name renaming (terms,termlists,binders,binderlists) avoid id =
  let fold1 _ (c, _) accu = Id.Set.union (free_vars_of_constr_expr c) accu in
  let fold2 _ (l, _) accu =
    let fold accu c = Id.Set.union (free_vars_of_constr_expr c) accu in
    List.fold_left fold accu l
  in
  let fold3 _ x accu = Id.Set.add x accu in
  let fvs1 = Id.Map.fold fold1 terms avoid in
  let fvs2 = Id.Map.fold fold2 termlists fvs1 in
  let fvs3 = Id.Map.fold fold3 renaming fvs2 in
  (* TODO binders *)
  next_ident_away_from id (fun id -> Id.Set.mem id fvs3)

let is_patvar c =
  match DAst.get c with
  | PatVar _ -> true
  | _ -> false

let is_patvar_store store pat =
  match DAst.get pat with
  | PatVar na -> ignore(store na); true
  | _ -> false

let out_patvar pat =
  match pat.v with
  | CPatAtom (Some qid) when qualid_is_ident qid ->
    Name (qualid_basename qid)
  | CPatAtom None -> Anonymous
  | _ -> assert false

let term_of_name = function
  | Name id -> DAst.make (GVar id)
  | Anonymous ->
       let st = Evar_kinds.Define (not (Program.get_proofs_transparency ())) in
    DAst.make (GHole (Evar_kinds.QuestionMark { Evar_kinds.default_question_mark with Evar_kinds.qm_obligation=st }, IntroAnonymous, None))

let traverse_binder intern_pat ntnvars (terms,_,binders,_ as subst) avoid (renaming,env) = function
| Anonymous -> (renaming,env), None, Anonymous
| Name id ->
  let store,get = set_temporary_memory () in
  try
    (* We instantiate binder name with patterns which may be parsed as terms *)
    let pat = coerce_to_cases_pattern_expr (fst (Id.Map.find id terms)) in
    let env,((disjpat,ids),id),na = intern_pat ntnvars env pat in
    let pat, na = match disjpat with
    | [pat] when is_patvar_store store pat -> let na = get () in None, na
    | _ -> Some ((List.map (fun x -> x.v) ids,disjpat),id), na.v in
    (renaming,env), pat, na
  with Not_found ->
  try
    (* Trying to associate a pattern *)
    let pat,(onlyident,scopes) = Id.Map.find id binders in
    let env = set_env_scopes env scopes in
    if onlyident then
      (* Do not try to interpret a variable as a constructor *)
      let na = out_patvar pat in
      let env = push_name_env ntnvars (Variable,[],[],[]) env (make ?loc:pat.loc na) in
      (renaming,env), None, na
    else
      (* Interpret as a pattern *)
      let env,((disjpat,ids),id),na = intern_pat ntnvars env pat in
      let pat, na =
        match disjpat with
        | [pat] when is_patvar_store store pat -> let na = get () in None, na
        | _ -> Some ((List.map (fun x -> x.v) ids,disjpat),id), na.v in
      (renaming,env), pat, na
  with Not_found ->
    (* Binders not bound in the notation do not capture variables *)
    (* outside the notation (i.e. in the substitution) *)
    let id' = find_fresh_name renaming subst avoid id in
    let renaming' =
      if Id.equal id id' then renaming else Id.Map.add id id' renaming
    in
    (renaming',env), None, Name id'

type binder_action =
| AddLetIn of lname * constr_expr * constr_expr option
| AddTermIter of (constr_expr * subscopes) Names.Id.Map.t
| AddPreBinderIter of Id.t * local_binder_expr (* A binder to be internalized *)
| AddBinderIter of Id.t * extended_glob_local_binder (* A binder already internalized - used for generalized binders *)

let dmap_with_loc f n =
  CAst.map_with_loc (fun ?loc c -> f ?loc (DAst.get_thunk c)) n

let error_cannot_coerce_wildcard_term ?loc () =
  user_err ?loc Pp.(str "Cannot turn \"_\" into a term.")

let error_cannot_coerce_disjunctive_pattern_term ?loc () =
  user_err ?loc Pp.(str "Cannot turn a disjunctive pattern into a term.")

let terms_of_binders bl =
  let rec term_of_pat pt = dmap_with_loc (fun ?loc -> function
    | PatVar (Name id)   -> CRef (qualid_of_ident id, None)
    | PatVar (Anonymous) -> error_cannot_coerce_wildcard_term ?loc ()
    | PatCstr (c,l,_) ->
       let qid = qualid_of_path ?loc (Nametab.path_of_global (ConstructRef c)) in
       let hole = CAst.make ?loc @@ CHole (None,IntroAnonymous,None) in
       let params = List.make (Inductiveops.inductive_nparams (fst c)) hole in
       CAppExpl ((None,qid,None),params @ List.map term_of_pat l)) pt in
  let rec extract_variables l = match l with
    | bnd :: l ->
      let loc = bnd.loc in
      begin match DAst.get bnd with
      | GLocalAssum (Name id,_,_) -> (CAst.make ?loc @@ CRef (qualid_of_ident ?loc id, None)) :: extract_variables l
      | GLocalDef (Name id,_,_,_) -> extract_variables l
      | GLocalDef (Anonymous,_,_,_)
      | GLocalAssum (Anonymous,_,_) -> user_err Pp.(str "Cannot turn \"_\" into a term.")
      | GLocalPattern (([u],_),_,_,_) -> term_of_pat u :: extract_variables l
      | GLocalPattern ((_,_),_,_,_) -> error_cannot_coerce_disjunctive_pattern_term ?loc ()
      end
    | [] -> [] in
  extract_variables bl

let flatten_generalized_binders_if_any y l =
  match List.rev l with
  | [] -> assert false
  | a::l -> a, List.map (fun a -> AddBinderIter (y,a)) l (* if l not empty, this means we had a generalized binder *)

let flatten_binders bl =
  let dispatch = function
    | CLocalAssum (nal,bk,t) -> List.map (fun na -> CLocalAssum ([na],bk,t)) nal
    | a -> [a] in
  List.flatten (List.map dispatch bl)

let instantiate_notation_constr loc intern intern_pat ntnvars subst infos c =
  let (terms,termlists,binders,binderlists) = subst in
  (* when called while defining a notation, avoid capturing the private binders
     of the expression by variables bound by the notation (see #3892) *)
  let avoid = Id.Map.domain ntnvars in
  let rec aux (terms,binderopt,iteropt as subst') (renaming,env) c =
    let subinfos = renaming,{env with tmp_scope = None} in
    match c with
    | NVar id when Id.equal id ldots_var ->
        let rec aux_letin env = function
        | [],terminator,_ -> aux (terms,None,None) (renaming,env) terminator
        | AddPreBinderIter (y,binder)::rest,terminator,iter ->
           let env,binders = intern_local_binder_aux intern ntnvars (env,[]) binder in
           let binder,extra = flatten_generalized_binders_if_any y binders in
           aux (terms,Some (y,binder),Some (extra@rest,terminator,iter)) (renaming,env) iter
        | AddBinderIter (y,binder)::rest,terminator,iter ->
           aux (terms,Some (y,binder),Some (rest,terminator,iter)) (renaming,env) iter
        | AddTermIter nterms::rest,terminator,iter ->
           aux (nterms,None,Some (rest,terminator,iter)) (renaming,env) iter
        | AddLetIn (na,c,t)::rest,terminator,iter ->
           let env,(na,_,c,t) = intern_letin_binder intern ntnvars env (na,c,t) in
           DAst.make ?loc (GLetIn (na,c,t,aux_letin env (rest,terminator,iter))) in
        aux_letin env (Option.get iteropt)
    | NVar id -> subst_var subst' (renaming, env) id
    | NList (x,y,iter,terminator,revert) ->
      let l,(scopt,subscopes) =
        (* All elements of the list are in scopes (scopt,subscopes) *)
        try
          let l,scopes = Id.Map.find x termlists in
          (if revert then List.rev l else l),scopes
        with Not_found ->
        try
          let (bl,(scopt,subscopes)) = Id.Map.find x binderlists in
   let env,bl' = List.fold_left (intern_local_binder_aux intern ntnvars) (env,[]) bl in
          terms_of_binders (if revert then bl' else List.rev bl'),(None,[])
        with Not_found ->
          anomaly (Pp.str "Inconsistent substitution of recursive notation.") in
      let l = List.map (fun a -> AddTermIter ((Id.Map.add y (a,(scopt,subscopes)) terms))) l in
      aux (terms,None,Some (l,terminator,iter)) subinfos (NVar ldots_var)
    | NHole (knd, naming, arg) ->
      let knd = match knd with
      | Evar_kinds.BinderType (Name id as na) ->
        let na =
          try (coerce_to_name (fst (Id.Map.find id terms))).v
          with Not_found ->
          try Name (Id.Map.find id renaming)
          with Not_found -> na
        in
        Evar_kinds.BinderType na
      | _ -> knd
      in
      let arg = match arg with
      | None -> None
      | Some arg ->
        let mk_env id (c, (tmp_scope, subscopes)) map =
          let nenv = {env with tmp_scope; scopes = subscopes @ env.scopes} in
          try
            let gc = intern nenv c in
            Id.Map.add id (gc, None) map
          with Nametab.GlobalizationError _ -> map
        in
        let mk_env' (c, (onlyident,(tmp_scope,subscopes))) =
          let nenv = {env with tmp_scope; scopes = subscopes @ env.scopes} in
          if onlyident then
            let na = out_patvar c in term_of_name na, None
          else
            let _,((disjpat,_),_),_ = intern_pat ntnvars nenv c in
            match disjpat with
            | [pat] -> (glob_constr_of_cases_pattern pat, None)
            | _ -> error_cannot_coerce_disjunctive_pattern_term ?loc:c.loc ()
        in
        let terms = Id.Map.fold mk_env terms Id.Map.empty in
        let binders = Id.Map.map mk_env' binders in
        let bindings = Id.Map.fold Id.Map.add terms binders in
        Some (Genintern.generic_substitute_notation bindings arg)
      in
      DAst.make ?loc @@ GHole (knd, naming, arg)
    | NBinderList (x,y,iter,terminator,revert) ->
      (try
        (* All elements of the list are in scopes (scopt,subscopes) *)
        let (bl,(scopt,subscopes)) = Id.Map.find x binderlists in
        (* We flatten binders so that we can interpret them at substitution time *)
        let bl = flatten_binders bl in
        let bl = if revert then List.rev bl else bl in
        (* We isolate let-ins which do not contribute to the repeated pattern *)
        let l = List.map (function | CLocalDef (na,c,t) -> AddLetIn (na,c,t)
                                   | binder -> AddPreBinderIter (y,binder)) bl in
        (* We stack the binders to iterate or let-ins to insert *)
        aux (terms,None,Some (l,terminator,iter)) subinfos (NVar ldots_var)
      with Not_found ->
          anomaly (Pp.str "Inconsistent substitution of recursive notation."))
    | NProd (Name id, NHole _, c') when option_mem_assoc id binderopt ->
        let binder = snd (Option.get binderopt) in
        expand_binders ?loc mkGProd [binder] (aux subst' (renaming,env) c')
    | NLambda (Name id,NHole _,c') when option_mem_assoc id binderopt ->
        let binder = snd (Option.get binderopt) in
        expand_binders ?loc mkGLambda [binder] (aux subst' (renaming,env) c')
    (* Two special cases to keep binder name synchronous with BinderType *)
    | NProd (na,NHole(Evar_kinds.BinderType na',naming,arg),c')
        when Name.equal na na' ->
        let subinfos,disjpat,na = traverse_binder intern_pat ntnvars subst avoid subinfos na in
        let ty = DAst.make ?loc @@ GHole (Evar_kinds.BinderType na,naming,arg) in
        DAst.make ?loc @@ GProd (na,Explicit,ty,Option.fold_right apply_cases_pattern disjpat (aux subst' subinfos c'))
    | NLambda (na,NHole(Evar_kinds.BinderType na',naming,arg),c')
        when Name.equal na na' ->
        let subinfos,disjpat,na = traverse_binder intern_pat ntnvars subst  avoid subinfos na in
        let ty = DAst.make ?loc @@ GHole (Evar_kinds.BinderType na,naming,arg) in
        DAst.make ?loc @@ GLambda (na,Explicit,ty,Option.fold_right apply_cases_pattern disjpat (aux subst' subinfos c'))
    | t ->
      glob_constr_of_notation_constr_with_binders ?loc
        (traverse_binder intern_pat ntnvars subst  avoid) (aux subst') subinfos t
  and subst_var (terms, binderopt, _terminopt) (renaming, env) id =
    (* subst remembers the delimiters stack in the interpretation *)
    (* of the notations *)
    try
      let (a,(scopt,subscopes)) = Id.Map.find id terms in
      intern {env with tmp_scope = scopt;
                scopes = subscopes @ env.scopes} a
    with Not_found ->
    try
      let pat,(onlyident,scopes) = Id.Map.find id binders in
      let env = set_env_scopes env scopes in
      (* We deactivate impls to avoid the check on hidden parameters *)
      (* and since we are only interested in the pattern as a term *)
      let env = reset_hidden_inductive_implicit_test env in
      if onlyident then
        term_of_name (out_patvar pat)
      else
        let env,((disjpat,ids),id),na = intern_pat ntnvars env pat in
        match disjpat with
        | [pat] -> glob_constr_of_cases_pattern pat
        | _ -> user_err Pp.(str "Cannot turn a disjunctive pattern into a term.")
    with Not_found ->
    try
      match binderopt with
      | Some (x,binder) when Id.equal x id ->
         let terms = terms_of_binders [binder] in
         assert (List.length terms = 1);
         intern env (List.hd terms)
      | _ -> raise Not_found
    with Not_found ->
    DAst.make ?loc (
    try
      GVar (Id.Map.find id renaming)
    with Not_found ->
      (* Happens for local notation joint with inductive/fixpoint defs *)
      GVar id)
  in aux (terms,None,None) infos c

(* Turning substitution coming from parsing and based on production
   into a substitution for interpretation and based on binding/constr
   distinction *)

let cases_pattern_of_name {loc;v=na} =
  let atom = match na with Name id -> Some (qualid_of_ident ?loc id) | Anonymous -> None in
  CAst.make ?loc (CPatAtom atom)

let split_by_type ids subst =
  let bind id scl l s =
    match l with
    | [] -> assert false
    | a::l -> l, Id.Map.add id (a,scl) s in
  let (terms,termlists,binders,binderlists),subst =
    List.fold_left (fun ((terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists')) (id,((_,scl),typ)) ->
    match typ with
    | NtnTypeConstr ->
       let terms,terms' = bind id scl terms terms' in
       (terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists')
    | NtnTypeBinder NtnBinderParsedAsConstr (AsIdentOrPattern | AsStrictPattern) ->
       let a,terms = match terms with a::terms -> a,terms | _ -> assert false in
       let binders' = Id.Map.add id (coerce_to_cases_pattern_expr a,(false,scl)) binders' in
       (terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists')
    | NtnTypeBinder NtnBinderParsedAsConstr AsIdent ->
       let a,terms = match terms with a::terms -> a,terms | _ -> assert false in
       let binders' = Id.Map.add id (cases_pattern_of_name (coerce_to_name a),(true,scl)) binders' in
       (terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists')
    | NtnTypeBinder (NtnParsedAsIdent | NtnParsedAsPattern _ as x) ->
       let onlyident = (x = NtnParsedAsIdent) in
       let binders,binders' = bind id (onlyident,scl) binders binders' in
       (terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists')
    | NtnTypeConstrList ->
       let termlists,termlists' = bind id scl termlists termlists' in
       (terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists')
    | NtnTypeBinderList ->
       let binderlists,binderlists' = bind id scl binderlists binderlists' in
       (terms,termlists,binders,binderlists),(terms',termlists',binders',binderlists'))
                   (subst,(Id.Map.empty,Id.Map.empty,Id.Map.empty,Id.Map.empty)) ids in
  assert (terms = [] && termlists = [] && binders = [] && binderlists = []);
  subst

let split_by_type_pat ?loc ids subst =
  let bind id (_,scopes) l s =
    match l with
    | [] -> assert false
    | a::l -> l, Id.Map.add id (a,scopes) s in
  let (terms,termlists),subst =
    List.fold_left (fun ((terms,termlists),(terms',termlists')) (id,(scl,typ)) ->
    match typ with
    | NtnTypeConstr | NtnTypeBinder _ ->
       let terms,terms' = bind id scl terms terms' in
       (terms,termlists),(terms',termlists')
    | NtnTypeConstrList ->
       let termlists,termlists' = bind id scl termlists termlists' in
       (terms,termlists),(terms',termlists')
    | NtnTypeBinderList -> error_invalid_pattern_notation ?loc ())
                   (subst,(Id.Map.empty,Id.Map.empty)) ids in
  assert (terms = [] && termlists = []);
  subst

let make_subst ids l =
  let fold accu (id, scopes) a = Id.Map.add id (a, scopes) accu in
  List.fold_left2 fold Id.Map.empty ids l

let intern_notation intern env ntnvars loc ntn fullargs =
  (* Adjust to parsing of { } *)
  let ntn,fullargs = contract_curly_brackets ntn fullargs in
  (* Recover interpretation { } *)
  let ((ids,c),df) = interp_notation ?loc ntn (env.tmp_scope,env.scopes) in
  Dumpglob.dump_notation_location (ntn_loc ?loc fullargs ntn) ntn df;
  (* Dispatch parsing substitution to an interpretation substitution *)
  let subst = split_by_type ids fullargs in
  (* Instantiate the notation *)
  instantiate_notation_constr loc intern intern_cases_pattern_as_binder ntnvars subst (Id.Map.empty, env) c

(**********************************************************************)
(* Discriminating between bound variables and global references       *)

let string_of_ty = function
  | Inductive _ -> "ind"
  | Recursive -> "def"
  | Method -> "meth"
  | Variable -> "var"

let gvar (loc, id) us = match us with
| None -> DAst.make ?loc @@ GVar id
| Some _ ->
  user_err ?loc  (str "Variable " ++ Id.print id ++
    str " cannot have a universe instance")

let intern_var env (ltacvars,ntnvars) namedctx loc id us =
  (* Is [id] a notation variable *)
  if Id.Map.mem id ntnvars then
    begin
      if not (Id.Map.mem id env.impls) then set_var_scope ?loc id true (env.tmp_scope,env.scopes) ntnvars;
      gvar (loc,id) us, [], [], []
    end
  else
  (* Is [id] registered with implicit arguments *)
  try
    let ty,expl_impls,impls,argsc = Id.Map.find id env.impls in
    let expl_impls = List.map
      (fun id -> CAst.make ?loc @@ CRef (qualid_of_ident ?loc id,None), Some (make ?loc @@ ExplByName id)) expl_impls in
    let tys = string_of_ty ty in
    Dumpglob.dump_reference ?loc "<>" (Id.to_string id) tys;
    gvar (loc,id) us, make_implicits_list impls, argsc, expl_impls
  with Not_found ->
  (* Is [id] bound in current term or is an ltac var bound to constr *)
  if Id.Set.mem id env.ids || Id.Set.mem id ltacvars.ltac_vars
  then
    gvar (loc,id) us, [], [], []
  else if Id.equal id ldots_var
  (* Is [id] the special variable for recursive notations? *)
  then if Id.Map.is_empty ntnvars
    then error_ldots_var ?loc
    else gvar (loc,id) us, [], [], []
  else if Id.Set.mem id ltacvars.ltac_bound then
    (* Is [id] bound to a free name in ltac (this is an ltac error message) *)
    user_err ?loc ~hdr:"intern_var"
     (str "variable " ++ Id.print id ++ str " should be bound to a term.")
  else
    (* Is [id] a goal or section variable *)
    let _ = Environ.lookup_named_ctxt id namedctx in
      try
(* [id] a section variable *)
(* Redundant: could be done in intern_qualid *)
let ref = VarRef id in
let impls = implicits_of_global ref in
let scopes = find_arguments_scope ref in
Dumpglob.dump_reference ?loc "<>" (string_of_qualid (Decls.variable_secpath id)) "var";
DAst.make ?loc @@ GRef (ref, us), impls, scopes, []
      with e when CErrors.noncritical e ->
(* [id] a goal variable *)
gvar (loc,id) us, [], [], []

let find_appl_head_data c =
  match DAst.get c with
  | GRef (ref,_) ->
    let impls = implicits_of_global ref in
    let scopes = find_arguments_scope ref in
      c, impls, scopes, []
  | GApp (r, l) ->
    begin match DAst.get r with
    | GRef (ref,_) when l != [] ->
      let n = List.length l in
      let impls = implicits_of_global ref in
      let scopes = find_arguments_scope ref in
c, List.map (drop_first_implicits n) impls,
List.skipn_at_least n scopes,[]
    | _ -> c,[],[],[]
    end
  | _ -> c,[],[],[]

let error_not_enough_arguments ?loc =
  user_err ?loc  (str "Abbreviation is not applied enough.")

let check_no_explicitation l =
  let is_unset (a, b) = match b with None -> false | Some _ -> true in
  let l = List.filter is_unset l in
  match l with
  | [] -> ()
  | (_, None) :: _ -> assert false
  | (_, Some {loc}) :: _ ->
    user_err ?loc  (str"Unexpected explicitation of the argument of an abbreviation.")

let dump_extended_global loc = function
  | TrueGlobal ref -> (*feedback_global loc ref;*) Dumpglob.add_glob ?loc ref
  | SynDef sp -> Dumpglob.add_glob_kn ?loc sp

let intern_extended_global_of_qualid qid =
  let r = Nametab.locate_extended qid in dump_extended_global qid.CAst.loc r; r

let intern_reference qid =
  let r =
    try intern_extended_global_of_qualid qid
    with Not_found -> Nametab.error_global_not_found qid
  in
  Smartlocate.global_of_extended_global r

let sort_info_of_level_info (info: level_info) : (Libnames.qualid * int) option =
  match info with
  | UAnonymous -> None
  | UUnknown -> None
  | UNamed id -> Some (id, 0)

let glob_sort_of_level (level: glob_level) : glob_sort =
  match level with
  | GSProp -> GSProp
  | GProp -> GProp
  | GSet -> GSet
  | GType info -> GType [sort_info_of_level_info info]

(* Is it a global reference or a syntactic definition? *)
let intern_qualid ?(no_secvar=false) qid intern env ntnvars us args =
  let loc = qid.loc in
  match intern_extended_global_of_qualid qid with
  | TrueGlobal (VarRef _) when no_secvar ->
      (* Rule out section vars since these should have been found by intern_var *)
      raise Not_found
  | TrueGlobal ref -> (DAst.make ?loc @@ GRef (ref, us)), Some ref, args
  | SynDef sp ->
      let (ids,c) = Syntax_def.search_syntactic_definition ?loc sp in
      let nids = List.length ids in
      if List.length args < nids then error_not_enough_arguments ?loc;
      let args1,args2 = List.chop nids args in
      check_no_explicitation args1;
      let terms = make_subst ids (List.map fst args1) in
      let subst = (terms, Id.Map.empty, Id.Map.empty, Id.Map.empty) in
      let infos = (Id.Map.empty, env) in
      let c = instantiate_notation_constr loc intern intern_cases_pattern_as_binder ntnvars subst infos c in
      let loc = c.loc in
      let err () =
        user_err ?loc  (str "Notation " ++ pr_qualid qid
                  ++ str " cannot have a universe instance,"
                  ++ str " its expanded head does not start with a reference")
      in
      let c = match us, DAst.get c with
      | None, _ -> c
      | Some _, GRef (ref, None) -> DAst.make ?loc @@ GRef (ref, us)
      | Some _, GApp (r, arg) ->
        let loc' = r.CAst.loc in
        begin match DAst.get r with
        | GRef (ref, None) ->
          DAst.make ?loc @@ GApp (DAst.make ?loc:loc' @@ GRef (ref, us), arg)
        | _ -> err ()
        end
      | Some [s], GSort (GType []) -> DAst.make ?loc @@ GSort (glob_sort_of_level s)
      | Some [_old_level], GSort _new_sort ->
        (* TODO: add old_level and new_sort to the error message *)
        user_err ?loc (str "Cannot change universe level of notation " ++ pr_qualid qid)
      | Some _, _ -> err ()
      in
      c, None, args2

let warn_nonprimitive_projection =
  CWarnings.create ~name:"nonprimitive-projection-syntax" ~category:"syntax" ~default:CWarnings.Disabled
    Pp.(fun f -> pr_qualid f ++ str " used as a primitive projection but is not one.")

let error_nonprojection_syntax ?loc qid =
  CErrors.user_err ?loc ~hdr:"nonprojection-syntax" Pp.(pr_qualid qid ++ str" is not a projection.")

let check_applied_projection isproj realref qid =
  match isproj with
  | None -> ()
  | Some projargs ->
    let is_prim = match realref with
      | None | Some (IndRef _ | ConstructRef _ | VarRef _) -> false
      | Some (ConstRef c) ->
        if Recordops.is_primitive_projection c then true
        else if Recordops.is_projection c then false
        else error_nonprojection_syntax ?loc:qid.loc qid
        (* TODO check projargs, note we will need implicit argument info *)
    in
    if not is_prim then warn_nonprimitive_projection ?loc:qid.loc qid

let intern_applied_reference ~isproj intern env namedctx (_, ntnvars as lvar) us args qid =
  let loc = qid.CAst.loc in
  if qualid_is_ident qid then
      try
        let res = intern_var env lvar namedctx loc (qualid_basename qid) us in
        check_applied_projection isproj None qid;
        res, args
      with Not_found ->
      try
        let r, realref, args2 = intern_qualid ~no_secvar:true qid intern env ntnvars us args in
        check_applied_projection isproj realref qid;
let x, imp, scopes, l = find_appl_head_data r in
   (x,imp,scopes,l), args2
      with Not_found ->
        (* Extra allowance for non globalizing functions *)
        if !interning_grammar || env.unb then
          (* check_applied_projection ?? *)
          (gvar (loc,qualid_basename qid) us, [], [], []), args
        else Nametab.error_global_not_found qid
  else
    let r,realref,args2 =
      try intern_qualid qid intern env ntnvars us args
      with Not_found -> Nametab.error_global_not_found qid
    in
    check_applied_projection isproj realref qid;
    let x, imp, scopes, l = find_appl_head_data r in
    (x,imp,scopes,l), args2

let interp_reference vars r =
  let (r,_,_,_),_ =
    intern_applied_reference ~isproj:None (fun _ -> error_not_enough_arguments ?loc:None)
      {ids = Id.Set.empty; unb = false ;
       tmp_scope = None; scopes = []; impls = empty_internalization_env}
      Environ.empty_named_context_val
      (vars, Id.Map.empty) None [] r
  in r

(**********************************************************************)
(** {5 Cases }                                                        *)

(** Private internalization patterns *)
type 'a raw_cases_pattern_expr_r =
  | RCPatAlias of 'a raw_cases_pattern_expr * lname
  | RCPatCstr  of GlobRef.t
    * 'a raw_cases_pattern_expr list * 'a raw_cases_pattern_expr list
  (** [RCPatCstr (loc, c, l1, l2)] represents [((@ c l1) l2)] *)
  | RCPatAtom  of (lident * (Notation_term.tmp_scope_name option * Notation_term.scope_name list)) option
  | RCPatOr    of 'a raw_cases_pattern_expr list
and 'a raw_cases_pattern_expr = ('a raw_cases_pattern_expr_r, 'a) DAst.t

(** {6 Elementary bricks } *)
let apply_scope_env env = function
  | [] -> {env with tmp_scope = None}, []
  | sc::scl -> {env with tmp_scope = sc}, scl

let rec simple_adjust_scopes n scopes =
  (* Note: they can be less scopes than arguments but also more scopes *)
  (* than arguments because extra scopes are used in the presence of *)
  (* coercions to funclass *)
  if Int.equal n 0 then [] else match scopes with
  | [] -> None :: simple_adjust_scopes (n-1) []
  | sc::scopes -> sc :: simple_adjust_scopes (n-1) scopes

let find_remaining_scopes pl1 pl2 ref =
  let impls_st = implicits_of_global ref in
  let len_pl1 = List.length pl1 in
  let len_pl2 = List.length pl2 in
  let impl_list = if Int.equal len_pl1 0
    then select_impargs_size len_pl2 impls_st
    else List.skipn_at_least len_pl1 (select_stronger_impargs impls_st) in
  let allscs = find_arguments_scope ref in
  let scope_list = List.skipn_at_least len_pl1 allscs in
  let rec aux = function
    |[],l -> l
    |_,[] -> []
    |h::t,_::tt when is_status_implicit h -> aux (t,tt)
    |_::t,h::tt -> h :: aux (t,tt)
  in ((try List.firstn len_pl1 allscs with Failure _ -> simple_adjust_scopes len_pl1 allscs),
      simple_adjust_scopes len_pl2 (aux (impl_list,scope_list)))

(* @return the first variable that occurs twice in a pattern

naive n^2 algo *)
let rec has_duplicate = function
  | [] -> None
  | x::l -> if Id.List.mem x l then (Some x) else has_duplicate l

let loc_of_multiple_pattern pl =
Loc.merge_opt (cases_pattern_expr_loc (List.hd pl)) (cases_pattern_expr_loc (List.last pl))

let loc_of_lhs lhs =
Loc.merge_opt (loc_of_multiple_pattern (List.hd lhs)) (loc_of_multiple_pattern (List.last lhs))

let check_linearity lhs ids =
  match has_duplicate ids with
    | Some id ->
raise (InternalizationError (loc_of_lhs lhs,NonLinearPattern id))
    | None ->
()

(* Match the number of pattern against the number of matched args *)
let check_number_of_pattern loc n l =
  let p = List.length l in
  if not (Int.equal n p) then raise (InternalizationError (loc,BadPatternsNumber (n,p)))

let check_or_pat_variables loc ids idsl =
  let eq_id {v=id} {v=id'} = Id.equal id id' in
  (* Collect remaining patterns which do not have the same variables as the first pattern *)
  let idsl = List.filter (fun ids' -> not (List.eq_set eq_id ids ids')) idsl in
  match idsl with
  | ids'::_ ->
    (* Look for an [id] which is either in [ids] and not in [ids'] or in [ids'] and not in [ids] *)
    let ids'' = List.subtract eq_id ids ids' in
    let ids'' = if ids'' = [] then List.subtract eq_id ids' ids else ids'' in
    user_err ?loc
      (strbrk "The components of this disjunctive pattern must bind the same variables (" ++
       Id.print (List.hd ids'').v ++ strbrk " is not bound in all patterns).")
  | [] -> ()

(** Use only when params were NOT asked to the user.
    @return if letin are included *)
let check_constructor_length env loc cstr len_pl pl0 =
  let n = len_pl + List.length pl0 in
  if Int.equal n (Inductiveops.constructor_nallargs cstr) then false else
    (Int.equal n (Inductiveops.constructor_nalldecls cstr) ||
      (error_wrong_numarg_constructor ?loc env cstr
         (Inductiveops.constructor_nrealargs cstr)))

open Declarations

(* Similar to Cases.adjust_local_defs but on RCPat *)
let insert_local_defs_in_pattern (ind,j) l =
  let (mib,mip) = Global.lookup_inductive ind in
  if mip.mind_consnrealdecls.(j-1) = mip.mind_consnrealargs.(j-1) then
    (* Optimisation *) l
  else
    let (ctx, _) = mip.mind_nf_lc.(j-1) in
    let decls = List.skipn (Context.Rel.length mib.mind_params_ctxt) (List.rev ctx) in
    let rec aux decls args =
      match decls, args with
      | Context.Rel.Declaration.LocalDef _ :: decls, args -> (DAst.make @@ RCPatAtom None) :: aux decls args
      | _, [] -> [] (* In particular, if there were trailing local defs, they have been inserted *)
      | Context.Rel.Declaration.LocalAssum _ :: decls, a :: args -> a :: aux decls args
      | _ -> assert false in
    aux decls l

let add_local_defs_and_check_length loc env g pl args = match g with
  | ConstructRef cstr ->
     (* We consider that no variables corresponding to local binders
        have been given in the "explicit" arguments, which come from a
        "@C args" notation or from a custom user notation *)
     let pl' = insert_local_defs_in_pattern cstr pl in
     let maxargs = Inductiveops.constructor_nalldecls cstr in
     if List.length pl' + List.length args > maxargs then
       error_wrong_numarg_constructor ?loc env cstr (Inductiveops.constructor_nrealargs cstr);
     (* Two possibilities: either the args are given with explicit
     variables for local definitions, then we give the explicit args
     extended with local defs, so that there is nothing more to be
     added later on; or the args are not enough to have all arguments,
     which a priori means local defs to add in the [args] part, so we
     postpone the insertion of local defs in the explicit args *)
     (* Note: further checks done later by check_constructor_length *)
     if List.length pl' + List.length args = maxargs then pl' else pl
  | _ -> pl

let add_implicits_check_length fail nargs nargs_with_letin impls_st len_pl1 pl2 =
  let impl_list = if Int.equal len_pl1 0
    then select_impargs_size (List.length pl2) impls_st
    else List.skipn_at_least len_pl1 (select_stronger_impargs impls_st) in
  let remaining_args = List.fold_left (fun i x -> if is_status_implicit x then i else succ i) in
  let rec aux i = function
    |[],l -> let args_len = List.length l + List.length impl_list + len_pl1 in
      ((if Int.equal args_len nargs then false
       else Int.equal args_len nargs_with_letin || (fst (fail (nargs - List.length impl_list + i))))
        ,l)
    |imp::q as il,[] -> if is_status_implicit imp && maximal_insertion_of imp
      then let (b,out) = aux i (q,[]) in (b,(DAst.make @@ RCPatAtom None)::out)
      else fail (remaining_args (len_pl1+i) il)
    |imp::q,(hh::tt as l) -> if is_status_implicit imp
      then let (b,out) = aux i (q,l) in (b,(DAst.make @@ RCPatAtom None)::out)
      else let (b,out) = aux (succ i) (q,tt) in (b,hh::out)
  in aux 0 (impl_list,pl2)

let add_implicits_check_constructor_length env loc c len_pl1 pl2 =
  let nargs = Inductiveops.constructor_nallargs c in
  let nargs' = Inductiveops.constructor_nalldecls c in
  let impls_st = implicits_of_global (ConstructRef c) in
  add_implicits_check_length (error_wrong_numarg_constructor ?loc env c)
    nargs nargs' impls_st len_pl1 pl2

let add_implicits_check_ind_length env loc c len_pl1 pl2 =
  let nallargs = inductive_nallargs_env env c in
  let nalldecls = inductive_nalldecls_env env c in
  let impls_st = implicits_of_global (IndRef c) in
  add_implicits_check_length (error_wrong_numarg_inductive ?loc env c)
    nallargs nalldecls impls_st len_pl1 pl2

(** Do not raise NotEnoughArguments thanks to preconditions*)
let chop_params_pattern loc ind args with_letin =
  let nparams = if with_letin
    then Inductiveops.inductive_nparamdecls ind
    else Inductiveops.inductive_nparams ind in
  assert (nparams <= List.length args);
  let params,args = List.chop nparams args in
  List.iter (fun c -> match DAst.get c with
    | PatVar Anonymous -> ()
    | PatVar _ | PatCstr(_,_,_) -> error_parameter_not_implicit ?loc:c.CAst.loc) params;
  args

let find_constructor loc add_params ref =
  let (ind,_ as cstr) = match ref with
  | ConstructRef cstr -> cstr
  | IndRef _ ->
    let error = str "There is an inductive name deep in a \"in\" clause." in
    user_err ?loc ~hdr:"find_constructor" error
  | ConstRef _ | VarRef _ ->
    let error = str "This reference is not a constructor." in
    user_err ?loc ~hdr:"find_constructor" error
  in
  cstr, match add_params with
    | Some nb_args ->
      let nb =
        if Int.equal nb_args (Inductiveops.constructor_nrealdecls cstr)
          then Inductiveops.inductive_nparamdecls ind
          else Inductiveops.inductive_nparams ind
      in
      List.make nb ([], [(Id.Map.empty, DAst.make @@ PatVar Anonymous)])
    | None -> []

let find_pattern_variable qid =
  if qualid_is_ident qid then qualid_basename qid
  else raise (InternalizationError(qid.CAst.loc,NotAConstructor qid))

let check_duplicate loc fields =
  let eq (ref1, _) (ref2, _) = qualid_eq ref1 ref2 in
  let dups = List.duplicates eq fields in
  match dups with
  | [] -> ()
  | (r, _) :: _ ->
    user_err ?loc (str "This record defines several times the field " ++
      pr_qualid r ++ str ".")

let inductive_of_record loc record =
  let inductive = IndRef (inductive_of_constructor record.Recordops.s_CONST) in
  Nametab.shortest_qualid_of_global ?loc Id.Set.empty inductive

(** [sort_fields ~complete loc fields completer] expects a list
    [fields] of field assignments [f = e1; g = e2; ...], where [f, g]
    are fields of a record and [e1] are "values" (either terms, when
    interning a record construction, or patterns, when intering record
    pattern-matching). It will sort the fields according to the record
    declaration order (which is important when type-checking them in
    presence of dependencies between fields). If the parameter
    [complete] is true, we require the assignment to be complete: all
    the fields of the record must be present in the
    assignment. Otherwise the record assignment may be partial
    (in a pattern, we may match on some fields only), and we call the
    function [completer] to fill the missing fields; the returned
    field assignment list is always complete. *)
let sort_fields ~complete loc fields completer =
  match fields with
    | [] -> None
    | (first_field_ref, first_field_value):: other_fields ->
        let (first_field_glob_ref, record) =
          try
            let gr = global_reference_of_reference first_field_ref in
            (gr, Recordops.find_projection gr)
          with Not_found ->
            raise (InternalizationError(loc, NotAProjection first_field_ref))
        in
        (* the number of parameters *)
        let nparams = record.Recordops.s_EXPECTEDPARAM in
        (* the reference constructor of the record *)
        let base_constructor =
          let global_record_id = ConstructRef record.Recordops.s_CONST in
          try Nametab.shortest_qualid_of_global ?loc Id.Set.empty global_record_id
          with Not_found ->
            anomaly (str "Environment corruption for records.") in
        let () = check_duplicate loc fields in
        let (end_index,    (* one past the last field index *)
             first_field_index,  (* index of the first field of the record *)
             proj_list)    (* list of projections *)
          =
          (* eliminate the first field from the projections,
             but keep its index *)
          let rec build_proj_list projs proj_kinds idx ~acc_first_idx acc =
            match projs with
              | [] -> (idx, acc_first_idx, acc)
              | (Some field_glob_id) :: projs ->
                 let field_glob_ref = ConstRef field_glob_id in
                 let first_field = GlobRef.equal field_glob_ref first_field_glob_ref in
                 begin match proj_kinds with
                    | [] -> anomaly (Pp.str "Number of projections mismatch.")
                    | (_, regular) :: proj_kinds ->
                       (* "regular" is false when the field is defined
                           by a let-in in the record declaration
                           (its value is fixed from other fields). *)
                       if first_field && not regular && complete then
                         user_err ?loc  (str "No local fields allowed in a record construction.")
                       else if first_field then
                         build_proj_list projs proj_kinds (idx+1) ~acc_first_idx:idx acc
                       else if not regular && complete then
                         (* skip non-regular fields *)
                         build_proj_list projs proj_kinds idx ~acc_first_idx acc
                       else
                         build_proj_list projs proj_kinds (idx+1) ~acc_first_idx
                                         ((idx, field_glob_id) :: acc)
                 end
              | None :: projs ->
                 if complete then
                   (* we don't want anonymous fields *)
                   user_err ?loc  (str "This record contains anonymous fields.")
                 else
                   (* anonymous arguments don't appear in proj_kinds *)
                   build_proj_list projs proj_kinds (idx+1) ~acc_first_idx acc
          in
          build_proj_list record.Recordops.s_PROJ record.Recordops.s_PROJKIND 1 ~acc_first_idx:0 []
        in
        (* now we want to have all fields assignments indexed by their place in
           the constructor *)
        let rec index_fields fields remaining_projs acc =
          match fields with
            | (field_ref, field_value) :: fields ->
               let field_glob_ref = try global_reference_of_reference field_ref
               with Not_found ->
                 user_err ?loc ~hdr:"intern"
                               (str "The field \"" ++ pr_qualid field_ref ++ str "\" does not exist.") in
               let this_field_record = try Recordops.find_projection field_glob_ref
                 with Not_found ->
                   let inductive_ref = inductive_of_record loc record in
                   raise (InternalizationError(loc, NotAProjectionOf (field_ref, inductive_ref)))
               in
               let remaining_projs, (field_index, _) =
                 let the_proj (idx, glob_id) = GlobRef.equal field_glob_ref (ConstRef glob_id) in
                 try CList.extract_first the_proj remaining_projs
                 with Not_found ->
                   let ind1 = inductive_of_record loc record in
                   let ind2 = inductive_of_record loc this_field_record in
                   raise (InternalizationError(loc, ProjectionsOfDifferentRecords (ind1, ind2)))
               in
               index_fields fields remaining_projs ((field_index, field_value) :: acc)
            | [] ->
               (* the order does not matter as we sort them next,
                  List.rev_* is just for efficiency *)
               let remaining_fields =
                 let complete_field (idx, field_ref) = (idx,
                 completer idx field_ref record.Recordops.s_CONST) in
                 List.rev_map complete_field remaining_projs in
               List.rev_append remaining_fields acc
        in
        let unsorted_indexed_fields =
          index_fields other_fields proj_list
            [(first_field_index, first_field_value)] in
        let sorted_indexed_fields =
          let cmp_by_index (i, _) (j, _) = Int.compare i j in
          List.sort cmp_by_index unsorted_indexed_fields in
        let sorted_fields = List.map snd sorted_indexed_fields in
        Some (nparams, base_constructor, sorted_fields)

(** {6 Manage multiple aliases} *)

type alias = {
  alias_ids : lident list;
  alias_map : Id.t Id.Map.t;
}

let empty_alias = {
  alias_ids = [];
  alias_map = Id.Map.empty;
}

  (* [merge_aliases] returns the sets of all aliases encountered at this
     point and a substitution mapping extra aliases to the first one *)
let merge_aliases aliases {loc;v=na} =
  match na with
  | Anonymous -> aliases
  | Name id ->
  let alias_ids = aliases.alias_ids @ [make ?loc id] in
  let alias_map = match aliases.alias_ids with
  | [] -> aliases.alias_map
  | {v=id'} :: _ -> Id.Map.add id id' aliases.alias_map
  in
  { alias_ids; alias_map; }

let alias_of als = match als.alias_ids with
| [] -> Anonymous
| {v=id} :: _ -> Name id

(** {6 Expanding notations }

    @returns a raw_case_pattern_expr :
    - no notations and syntactic definition
    - global reference and identifier instead of reference

*)

let is_zero s =
  let rec aux i =
    Int.equal (String.length s) i || ((s.[i] == '0' || s.[i] == '_') && aux (i+1))
  in aux 0
let is_zero n = is_zero n.NumTok.int && is_zero n.NumTok.frac

let merge_subst s1 s2 = Id.Map.fold Id.Map.add s1 s2

let product_of_cases_patterns aliases idspl =
  (* each [pl] is a disjunction of patterns over common identifiers [ids] *)
  (* We stepwise build a disjunction of patterns [ptaill] over common [ids'] *)
  List.fold_right (fun (ids,pl) (ids',ptaill) ->
    (ids @ ids',
     (* Cartesian prod of the or-pats for the nth arg and the tail args *)
     List.flatten (
       List.map (fun (subst,p) ->
  List.map (fun (subst',ptail) -> (merge_subst subst subst',p::ptail)) ptaill) pl)))
    idspl (aliases.alias_ids,[aliases.alias_map,[]])

let rec subst_pat_iterator y t = DAst.(map (function
  | RCPatAtom id as p ->
    begin match id with Some ({v=x},_) when Id.equal x y -> DAst.get t | _ -> p end
  | RCPatCstr (id,l1,l2) ->
    RCPatCstr (id,List.map (subst_pat_iterator y t) l1,
         List.map (subst_pat_iterator y t) l2)
  | RCPatAlias (p,a) -> RCPatAlias (subst_pat_iterator y t p,a)
  | RCPatOr pl -> RCPatOr (List.map (subst_pat_iterator y t) pl)))

let is_non_zero c = match c with
| { CAst.v = CPrim (Numeral (SPlus, p)) } -> not (is_zero p)
| _ -> false

let is_non_zero_pat c = match c with
| { CAst.v = CPatPrim (Numeral (SPlus, p)) } -> not (is_zero p)
| _ -> false

let get_asymmetric_patterns = Goptions.declare_bool_option_and_ref
    ~depr:false
    ~name:"no parameters in constructors"
    ~key:["Asymmetric";"Patterns"]
    ~value:false

let drop_notations_pattern looked_for genv =
  (* At toplevel, Constructors and Inductives are accepted, in recursive calls
     only constructor are allowed *)
  let ensure_kind top loc g =
    try
--> --------------------

--> maximum size reached

--> --------------------

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.40Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤

Begriffe der Konzeptbildung Was zu einem Entwurf gehört
Begriffe der Konzeptbildung Hier finden Sie eine Liste der Produkte des Unternehmens
Mittel

Quellcode-Bibliothek

^© Kompilation durch diese Firma

[Weder Korrektheit noch Funktionsfähigkeit der Software werden zugesichert.]

Datei: seq2set.prf Sprache: SML

Original von: Coq^©

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.40Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤

Lebenszyklus

Ziele

Bot Zugriff

Quellcode-Bibliothek

© Kompilation durch diese Firma

[Weder Korrektheit noch Funktionsfähigkeit der Software werden zugesichert.]

Datei: seq2set.prf Sprache: SML

Original von: Coq©

¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.40Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤

Lebenszyklus

Ziele

Bot Zugriff

^© Kompilation durch diese Firma

Original von: Coq^©