-
Notifications
You must be signed in to change notification settings - Fork 631
/
constrintern.ml
3012 lines (2736 loc) · 128 KB
/
constrintern.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
(************************************************************************)
(* * The Coq Proof Assistant / The Coq Development Team *)
(* v * Copyright INRIA, CNRS and contributors *)
(* <O___,, * (see version control and CREDITS file for authors & dates) *)
(* \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 Structures
open Cases
open Constrexpr
open Constrexpr_ops
open Notation_term
open Notation_ops
open Notation
open Inductiveops
open Context.Rel.Declaration
open NumTok
(** 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
| Recursive
| Method
| Variable
type var_unique_id = string
(* dumpglob for binders should probably just not happen in contrintern *)
let var_uid =
let count = ref 0 in
fun id -> incr count; Decls.set_variable_uid !count;
Id.to_string id ^ ":" ^ string_of_int !count
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 *
(* signature of impargs of the variable *)
Impargs.implicit_status list *
(* subscopes of the args of the variable *)
scope_name list list *
(* unique ID for coqdoc links *)
var_unique_id
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;
}
(**********************************************************************)
(* 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
| ProjectionsOfDifferentRecords of Structure.t * Structure.t
exception InternalizationError of internalization_error
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 inductive_of_record s =
let inductive = GlobRef.IndRef (s.Structure.name) in
Nametab.shortest_qualid_of_global Id.Set.empty inductive
let explain_field_not_a_projection field_id =
pr_qualid field_id ++ str ": Not a projection"
let explain_projections_of_diff_records record1 record2 =
let inductive1_id = inductive_of_record record1 in
let inductive2_id = inductive_of_record record2 in
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
| ProjectionsOfDifferentRecords (inductive1_id, inductive2_id) ->
explain_projections_of_diff_records inductive1_id inductive2_id
in pp ++ str "."
let _ = CErrors.register_handler (function
| InternalizationError e ->
Some (explain_internalization_error e)
| _ -> None)
let error_bad_inductive_type ?loc ?info () =
user_err ?loc ?info (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_internalization_data env sigma id ty typ impl =
let impl = compute_implicits_with_manual env sigma typ (is_implicit_args()) impl in
(ty, impl, compute_arguments_scope env sigma typ, var_uid id)
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 id ty typ impl) map)
impls
let extend_internalization_data (r, impls, scopes, uid) impl scope =
(r, impls@[impl], scopes@[scope], uid)
(**********************************************************************)
(* 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
| InCustomEntry _,_ -> ntn,(l,ll,bl,bll)
| InConstrEntry, ntn ->
let ntn' = ref ntn in
let rec contract_squash n = function
| [] -> []
| { CAst.v = CNotation (None,(InConstrEntry,"{ _ }"),([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 *)
(InConstrEntry,!ntn'),(l,ll,bl,bll)
let contract_curly_brackets_pat ntn (l,ll,bl) =
match ntn with
| InCustomEntry _,_ -> ntn,(l,ll,bl)
| InConstrEntry, ntn ->
let ntn' = ref ntn in
let rec contract_squash n = function
| [] -> []
| { CAst.v = CPatNotation (None,(InConstrEntry,"{ _ }"),([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 *)
(InConstrEntry,!ntn'),(l,ll,bl)
type local_univs = { bound : UnivNames.universe_binders; unb_univs : bool }
let empty_local_univs = { bound = UnivNames.empty_binders; unb_univs = false }
type abstraction_kind = AbsLambda | AbsPi
type intern_env = {
ids: Id.Set.t;
strict_check: bool option;
(* None = not passed via ltac yet: works as "true" unless when interpreting
ltac:() in which case we assume the default Ltac value, that is "false" *)
local_univs: local_univs;
tmp_scope: Notation_term.tmp_scope_name list;
scopes: Notation_term.scope_name list;
impls: internalization_env;
binder_block_names: abstraction_kind option (* None = unknown *) option;
ntn_binding_ids: Id.Set.t; (* subset of ids that are notation variables *)
}
type pattern_intern_env = {
pat_scopes: Notation_term.subscopes;
(* ids = Some means accept local variables; this is useful for
terms as patterns parsed as patterns in notations *)
pat_ids: Id.Set.t option;
}
(**********************************************************************)
(* Remembering the parsing scope of variables in notations *)
let make_current_scope tmp scopes = match tmp, scopes with
| [], scopes -> scopes
| [tmp_scope], (sc :: _) when String.equal sc tmp_scope -> scopes
| tmp_scope, scopes -> tmp_scope @ scopes
let pr_scope_stack begin_of_sentence l =
let bstr x =
if begin_of_sentence then str (CString.capitalize_ascii x) else str x in
match l with
| [] -> bstr "the empty scope stack"
| [a] -> bstr "scope " ++ str a
| l -> bstr "scope stack " ++
str "[" ++ prlist_with_sep pr_comma str l ++ str "]"
let warn_inconsistent_scope =
CWarnings.create ~name:"inconsistent-scopes" ~category:CWarnings.CoreCategories.syntax
(fun (id,scopes1,scopes2) ->
(str "Argument " ++ Id.print id ++
strbrk " was previously inferred to be in " ++
pr_scope_stack false scopes1 ++
strbrk " but is here used in " ++
pr_scope_stack false scopes2 ++
strbrk ". " ++
pr_scope_stack true scopes1 ++
strbrk " will be used at parsing time unless you override it by" ++
strbrk " annotating the argument with an explicit scope of choice."))
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_notation_var_scope ?loc id (tmp_scope,subscopes as scopes) ntnbinders ntnvars =
try
let _,idscopes,ntn_binding_ids,typ = Id.Map.find id ntnvars in
match typ with
| Notation_term.NtnInternTypeOnlyBinder -> error_expect_binder_notation_type ?loc id
| Notation_term.NtnInternTypeAny principal ->
let () = 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 Option.is_empty principal && not (List.equal String.equal s' s) then
warn_inconsistent_scope ?loc (id,s',s)
in
let () = match !ntn_binding_ids with
| None -> ntn_binding_ids := Some ntnbinders
| Some ntnbinders' -> ntn_binding_ids := Some (Id.Set.inter ntnbinders ntnbinders')
in
()
with Not_found ->
(* Not in a notation *)
()
let set_var_is_binder ?loc id ntnvars =
try
let used_as_binder,_,_,_ = Id.Map.find id ntnvars in
used_as_binder := true
with Not_found ->
(* Not in a notation *)
()
let set_type_scope env = {env with tmp_scope = Notation.current_type_scope_names ()}
let reset_tmp_scope env = {env with tmp_scope = []}
let set_env_scopes env (scopt,subscopes) =
{env with tmp_scope = scopt; scopes = subscopes @ env.scopes}
let env_for_pattern env =
{pat_scopes = (env.tmp_scope, env.scopes); pat_ids = Some env.ids}
let mkGProd ?loc (na,bk,t) body = DAst.make ?loc @@ GProd (na, None, bk, t, body)
let mkGLambda ?loc (na,bk,t) body = DAst.make ?loc @@ GLambda (na, None, bk, t, body)
(**********************************************************************)
(* Utilities for binders *)
let warn_shadowed_implicit_name =
CWarnings.create ~name:"shadowed-implicit-name" ~category:CWarnings.CoreCategories.syntax
Pp.(fun na -> str "Making shadowed name of implicit argument accessible by position.")
let exists_name na l =
match na with
| Name id -> List.exists (function Some { impl_pos = (Name id', _, _) } -> Id.equal id id' | _ -> false) l
| _ -> false
let build_impls ?loc n bk na acc =
let impl_status max =
let na =
if exists_name na acc then begin warn_shadowed_implicit_name ?loc na; Anonymous end
else na in
Some {
impl_pos = (na, n, (*TODO, enhancement: compute dependency*) None);
impl_expl = Manual;
impl_max = max;
impl_force = true
}
in
match bk with
| NonMaxImplicit -> impl_status false :: acc
| MaxImplicit -> impl_status true :: acc
| Explicit -> None :: acc
let impls_binder_list =
let rec aux acc n = function
| (na,_,bk,None,_) :: binders -> aux (build_impls n bk na acc) (n+1) binders
| (na,_,bk,Some _,_) :: binders -> aux acc n binders
| [] -> (n,acc)
in aux []
let impls_type_list n ?(args = []) =
let rec aux acc n c = match DAst.get c with
| GProd (na,_,bk,_,c) -> aux (build_impls n bk na acc) (n+1) c
| _ -> List.rev acc
in aux args n
let impls_term_list n ?(args = []) =
let rec aux acc n c = match DAst.get c with
| GLambda (na,_,bk,_,c) -> aux (build_impls n bk na acc) (n+1) c
| GRec (fix_kind, nas, args, tys, bds) ->
let nb = match fix_kind with |GFix (_, n) -> n | GCoFix n -> n in
let n,acc' = List.fold_left (fun (n,acc) (na, _, bk, _, _) -> (n+1,build_impls n bk na acc)) (n,acc) args.(nb) in
aux acc' n bds.(nb)
|_ -> List.rev acc
in aux args n
(* 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 ->
Loc.raise ?loc (InternalizationError (VariableCapture (id,id')))
| _::nal ->
check_capture ty nal
| [] ->
()
(** Status of the internalizer wrt "Arguments" of names *)
let restart_no_binders env =
{ env with binder_block_names = None}
(* Not in relation with the "Arguments" of a name *)
let restart_prod_binders env =
{ env with binder_block_names = Some (Some AbsPi) }
(* In a position binding a type to a name *)
let restart_lambda_binders env =
{ env with binder_block_names = Some (Some AbsLambda) }
(* In a position binding a body to a name *)
let switch_prod_binders env =
match env.binder_block_names with
| Some o when o <> Some AbsLambda -> restart_prod_binders env
| _ -> restart_no_binders env
(* In a position switching to a type *)
let switch_lambda_binders env =
match env.binder_block_names with
| Some o when o <> Some AbsPi -> restart_lambda_binders env
| _ -> restart_no_binders env
(* In a position switching to a term *)
let slide_binders env =
match env.binder_block_names with
| Some o when o <> Some AbsPi -> restart_prod_binders env
| _ -> restart_no_binders env
(* In a position of cast *)
let binder_status_fun = {
no = (fun x -> x);
restart_prod = on_snd restart_prod_binders;
restart_lambda = on_snd restart_lambda_binders;
switch_prod = on_snd switch_prod_binders;
switch_lambda = on_snd switch_lambda_binders;
slide = on_snd slide_binders;
}
(* [test_kind_strict] rules out pattern which refers to global other
than constructors or variables; It is used in instances of notations *)
let test_kind_pattern_in_notation ?loc = function
| GlobRef.ConstructRef _ -> ()
(* We do not accept non constructors to be used as variables in
patterns *)
| GlobRef.ConstRef _ ->
user_err ?loc (str "Found a constant while a pattern was expected.")
| GlobRef.IndRef _ ->
user_err ?loc (str "Found an inductive type while a pattern was expected.")
| GlobRef.VarRef _ ->
(* we accept a section variable name to be used as pattern variable *)
raise Not_found
let test_kind_ident_in_notation ?loc = function
| GlobRef.ConstructRef _ ->
user_err ?loc (str "Found a constructor while a variable name was expected.")
| GlobRef.ConstRef _ ->
user_err ?loc (str "Found a constant while a variable name was expected.")
| GlobRef.IndRef _ ->
user_err ?loc (str "Found an inductive type while a variable name was expected.")
| GlobRef.VarRef _ ->
(* we accept a section variable name to be used as pattern variable *)
raise Not_found
(* [test_kind_tolerant] allow global reference names to be used as pattern variables *)
let test_kind_tolerant ?loc = function
| GlobRef.ConstructRef _ -> ()
| GlobRef.ConstRef _ | GlobRef.IndRef _ | GlobRef.VarRef _ ->
(* A non-constructor global reference in a pattern is seen as a variable *)
raise Not_found
(**)
let locate_if_hole ?loc na c = match DAst.get c with
| GHole (GNamedHole _) -> c
| GHole _ ->
(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 (GBinderType na))
| _ -> c
let pure_push_name_env (id,implargs,is_ntn_id) env =
{env with
ids = Id.Set.add id env.ids;
impls = Id.Map.add id implargs env.impls;
ntn_binding_ids = if is_ntn_id then Id.Set.add id env.ntn_binding_ids else env.ntn_binding_ids;
}
let push_name_env ntnvars implargs env =
let open CAst in
function
| { loc; v = Anonymous } ->
env
| { loc; v = Name id } ->
if Id.Map.is_empty ntnvars && Id.equal id ldots_var
then error_ldots_var ?loc;
set_var_is_binder ?loc id ntnvars;
let uid = var_uid id in
Dumpglob.dump_binding ?loc uid;
pure_push_name_env (id,(Variable,implargs,[],uid),Id.Map.mem id ntnvars) 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,Id.Set.mem id env.ntn_binding_ids)) bl
let restore_binders_impargs env l =
List.fold_right pure_push_name_env l env
let warn_ignoring_unexpected_implicit_binder_declaration =
CWarnings.create ~name:"unexpected-implicit-declaration" ~category:CWarnings.CoreCategories.syntax
Pp.(fun () -> str "Ignoring implicit binder declaration in unexpected position.")
let check_implicit_meaningful ?loc k env =
if k <> Explicit && env.binder_block_names = None then
(warn_ignoring_unexpected_implicit_binder_declaration ?loc (); Explicit)
else
k
let intern_generalized_binder 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 ty
in
let ty' = intern_type {env with ids = ids; strict_check = Some false} 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 ntnvars [](*?*) env (make ?loc @@ Name x))
env fvs in
let b' = check_implicit_meaningful ?loc b' env in
let bl = List.map
CAst.(map (fun id ->
(Name id, MaxImplicit, DAst.make ?loc @@ GHole (GBinderType (Name id)))))
fvs
in
let na = match na with
| Anonymous ->
let id =
match ty with
| { v = CApp ({ v = CRef (qid,_) }, _) } when qualid_is_ident qid ->
qualid_basename qid
| _ -> default_non_dependent_ident
in
let ids' = List.fold_left (fun ids' lid -> Id.Set.add lid.CAst.v ids') ids' fvs in
let id =
Implicit_quantifiers.make_fresh ids' (Global.env ()) id
in
Name id
| _ -> na
in
let impls = impls_type_list 1 ty' in
(push_name_env ntnvars impls 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 (restart_prod_binders (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 1 ty in
List.fold_left
(fun (env, bl) ({loc;v=na} as locna) ->
let k = check_implicit_meaningful ?loc k env in
(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,r,bk,t) -> (na,None,bk,None,t)
| GLocalDef (na,r,c,Some t) -> (na,None,Explicit,Some c,t)
| GLocalDef (na,r,c,None) ->
let t = DAst.make ?loc @@ GHole (GBinderType na) in
(na,None,Explicit,Some c,t)
| GLocalPattern (_,_,_,_) ->
Loc.raise ?loc (Gramlib.Grammar.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 (reset_tmp_scope (restart_lambda_binders env)) def in
let ty = Option.map (intern (set_type_scope (restart_prod_binders env))) ty in
let impls = impls_term_list 1 term in
(push_name_env ntnvars impls env locna,
(na,term,ty))
let intern_cases_pattern_as_binder intern test_kind ntnvars env bk (CAst.{v=p;loc} as pv) =
let p,t,tmp_scope = match p with
| CPatCast (p, t) -> (p, Some t, (* Redone later, not nice: *) Notation.compute_glob_type_scope (intern (set_type_scope env) t))
| _ -> (pv, None, []) in
let il,disjpat =
let (il, subst_disjpat) = !intern_cases_pattern_fwd test_kind ntnvars (env_for_pattern {env with tmp_scope}) 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 na = alias_of_pat (List.hd disjpat) in
let env = List.fold_right (fun {loc;v=id} env -> push_name_env ntnvars [] env (make ?loc @@ Name id)) il env 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
let t = match t with
| Some t -> t
| None -> CAst.make ?loc @@ CHole (Some (GBinderType na.v)) in
let _, bl' = intern_assumption intern ntnvars env [na] (Default bk) t in
let {v=(_,bk,t)} = List.hd bl' in
let il = List.map (fun id -> id.v) il in
env,((disjpat,il),id),bk,t
let intern_local_binder_aux 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,None,c,t)) bl' in
env, bl' @ bl
| CLocalDef( {loc; v=na} as locna,_,def,ty) ->
let env,(na,def,ty) = intern_letin_binder intern ntnvars env (locna,def,ty) in
env, (DAst.make ?loc @@ GLocalDef (na,None,def,ty)) :: bl
| CLocalPattern p ->
let env, ((disjpat,il),id),bk,t = intern_cases_pattern_as_binder intern test_kind_tolerant ntnvars env Explicit p in
(env, (DAst.make ?loc:p.CAst.loc @@ GLocalPattern((disjpat,il),id,bk,t)) :: bl)
let intern_generalization intern env ntnvars loc bk c =
let c = intern {env with strict_check = Some false} c in
let fvs = Implicit_quantifiers.generalizable_vars_of_glob_constr ~bound:env.ids c in
let env', c' =
let abs =
let pi =
match Notation.current_type_scope_names () with
| [] -> false
| type_scopes ->
let is_type_scope = match env.tmp_scope with
| [] -> false
| scl -> List.equal String.equal scl type_scopes
in
is_type_scope ||
List.exists (fun sc -> String.List.mem sc env.scopes) type_scopes
in
if pi then
(fun {loc=loc';v=id} acc ->
DAst.make ?loc:(Loc.merge_opt loc' loc) @@
GProd (Name id, None, bk, DAst.make ?loc:loc' @@ GHole (GBinderType (Name id)), acc))
else
(fun {loc=loc';v=id} acc ->
DAst.make ?loc:(Loc.merge_opt loc' loc) @@
GLambda (Name id, None, bk, DAst.make ?loc:loc' @@ GHole (GBinderType (Name id)), acc))
in
List.fold_right (fun ({loc;v=id} as lid) (env, acc) ->
let env' = push_name_env ntnvars [] 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, r, b, oty) ->
expand_binders ?loc mk bl (DAst.make ?loc @@ GLetIn (n, r, 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 check_not_notation_variable f ntnvars =
(* Check bug #4690 *)
match DAst.get f with
| GVar id when Id.Map.mem id ntnvars ->
user_err (str "Prefix @ is not applicable to notation variables.")
| _ ->
()
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 (CAst.make ?loc:pat.loc na)); true
| _ -> false
let out_patvar = CAst.map_with_loc (fun ?loc -> function
| CPatAtom (Some qid) when qualid_is_ident qid ->
Name (qualid_basename qid)
| CPatAtom None -> Anonymous
| _ -> assert false)
let canonize_type = function
| None -> None
| Some t as t' ->
match DAst.get t with
| GHole (GBinderType _) -> None
| _ -> t'
let set_type ty1 ty2 =
match canonize_type ty1, canonize_type ty2 with
(* Not a meta-binding binder, we use the type given in the notation *)
| _, None -> ty1
(* A meta-binding binder meta-bound to a possibly-typed pattern *)
(* the binder is supposed to come w/o an explicit type in the notation *)
| None, Some _ -> ty2
| Some ty1, Some t2 ->
(* An explicitly typed meta-binding binder, not supposed to be a pattern; checked in interp_notation *)
user_err ?loc:t2.CAst.loc Pp.(str "Unexpected type constraint in notation already providing a type constraint.")
let cook_pattern ((disjpat, ids), id) =
let store,get = set_temporary_memory () in
let pat, na = match disjpat with
| [pat] when is_patvar_store store pat -> let na = get () in None, na.v
| _ -> Some ((ids,disjpat),id), Name id in
pat, na
let extract_pattern_from_binder b =
match DAst.get b with
| GLocalDef _ -> user_err ?loc:b.CAst.loc (str "Local definitions not supported here.")
| GLocalAssum (na, _, bk, t) -> None, na, bk, t
| GLocalPattern (patl, id, bk, ty) ->
let pat, na = cook_pattern (patl, id) in
pat, na, bk, ty
let traverse_binder intern_pat ntnvars (terms,_,binders,_ as subst) binderopt avoid (renaming,env) na ty =
match na with
| Anonymous -> (renaming,env), None, Anonymous, Explicit, set_type ty None
| Name id ->
let test_kind = test_kind_tolerant 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,pat,bk,t = intern_pat test_kind ntnvars env Explicit pat in
let pat, na = cook_pattern pat in
(renaming,env), pat, na, bk, set_type ty (Some t)
with Not_found ->
try
(* Trying to associate a pattern *)
let (pat,bk),(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 [] env na in
let ty' = DAst.make @@ GHole (GBinderType na.CAst.v) in
(renaming,env), None, na.v, bk, set_type ty (Some ty')
else
(* Interpret as a pattern *)
let env,pat,bk,t = intern_pat test_kind ntnvars env bk pat in
let pat, na = cook_pattern pat in
(renaming,env), pat, na, bk, set_type ty (Some t)
with Not_found ->
if option_mem_assoc id binderopt then
let binder = snd (Option.get binderopt) in
let pat, na, bk, t = extract_pattern_from_binder binder in
(renaming,env), pat, na, bk, set_type ty (Some t)
else
(* 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 = Id.Map.add id id' renaming in
(renaming,env), None, Name id', Explicit, set_type ty None
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 *)
| AddNList (* Insert a ".. term .." block *)
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 (GlobRef.ConstructRef c)) in
let hole = CAst.make ?loc @@ CHole (None) in
let params = List.make (Inductiveops.inductive_nparams (Global.env()) (fst c)) hole in
CAppExpl ((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
| l ->
(* if l has more than one element, this means we had a generalized binder *)
let select_iter a =
match DAst.get a with
| GLocalAssum (Name id,_,_,_) when Id.equal id ldots_var -> AddNList
| _ -> AddBinderIter (y,a) in
List.map select_iter l
let flatten_binders bl =
let dispatch = function
| CLocalAssum (nal,r,bk,t) -> List.map (fun na -> CLocalAssum ([na],r,bk,t)) nal
| a -> [a] in
List.flatten (List.map dispatch bl)
let rec adjust_env env = function
(* We need to adjust scopes, binder blocks ... to the env expected
at the recursive occurrence; We do an underapproximation... *)
| NProd (_,_,c) -> adjust_env (switch_prod_binders env) c
| NLambda (_,_,c) -> adjust_env (switch_lambda_binders env) c
| NLetIn (_,_,_,c) -> adjust_env env c
| NVar id when Id.equal id ldots_var -> env
| NCast (c,_,_) -> adjust_env env c
| NApp _ -> restart_no_binders env
| NVar _ | NRef _ | NHole _ | NGenarg _ | NCases _ | NLetTuple _ | NIf _
| NRec _ | NSort _ | NProj _ | NInt _ | NFloat _ | NArray _
| NList _ | NBinderList _ -> env (* to be safe, but restart should be ok *)
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 = []} in
match c with
| NVar id when Id.equal id ldots_var ->
(* apply the pending sequence of letin, term iterator instances,
binder iterator instances, and eventually terminator *)
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 (adjust_env env iter,[]) binder in
let binders = flatten_generalized_binders_if_any y binders in
aux_letin env (binders@rest,terminator,iter)
| AddBinderIter (y,binder)::rest,terminator,iter ->
(* [y] is the placeholder for the [binder] in [iter] *)
aux (terms,Some (y,binder),Some (rest,terminator,iter)) (renaming,env) iter
| AddTermIter nterms::rest,terminator,iter ->
(* This time, the variable [y] is the placeholder for the [binder] in [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 (adjust_env env iter) (na,c,t) in
DAst.make ?loc (GLetIn (na,None,c,t,aux_letin env (rest,terminator,iter)))
| AddNList::rest,terminator,iter ->
DAst.make ?loc (GApp (DAst.make ?loc (GVar ldots_var), [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'),([],[])
with Not_found ->
anomaly (Pp.str "Inconsistent substitution of recursive notation.") in
let select_iter a =
match a.CAst.v with
| CRef (qid,None) when qualid_is_ident qid && Id.equal (qualid_basename qid) ldots_var -> AddNList
| _ -> AddTermIter (Id.Map.add y (a,(scopt,subscopes)) terms) in
let l = List.map select_iter l in
aux (terms,None,Some (l,terminator,iter)) subinfos (NVar ldots_var)
| NHole (knd) ->
let knd = match knd with
| GBinderType (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
GBinderType na
| _ -> knd
in
DAst.make ?loc @@ GHole (knd)
| NGenarg arg ->
let mk_env id (c, scopes) map =
let nenv = set_env_scopes env scopes in
try
let gc = intern nenv c in
Id.Map.add id (gc) map
with Nametab.GlobalizationError _ -> map
in
let mk_env' ((c,_bk), (onlyident,(tmp_scope,subscopes))) =
let nenv = {env with tmp_scope; scopes = subscopes @ env.scopes} in
let test_kind =
if onlyident then test_kind_ident_in_notation
else test_kind_pattern_in_notation in
let _,((disjpat,_),_),_,_ty = intern_pat test_kind ntnvars nenv Explicit c in
(* TODO: use cast? *)
match disjpat with
| [pat] -> (glob_constr_of_cases_pattern (Global.env()) pat)
| _ -> 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
let arg = Genintern.generic_substitute_notation avoid bindings arg in
DAst.make ?loc @@ GGenarg 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, None, 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, None, c') when option_mem_assoc id binderopt ->
let binder = snd (Option.get binderopt) in
expand_binders ?loc mkGLambda [binder] (aux subst' (renaming,env) c')
| t ->
glob_constr_of_notation_constr_with_binders ?loc
(traverse_binder intern_pat ntnvars subst binderopt avoid) (aux subst') ~h:binder_status_fun 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,scopes) = Id.Map.find id terms in
intern (set_env_scopes env scopes) a
with Not_found ->
try
let (pat,bk),(onlyident,scopes) = Id.Map.find id binders in
let env = set_env_scopes env scopes in
let test_kind =
if onlyident then test_kind_ident_in_notation
else test_kind_pattern_in_notation in
let env,((disjpat,ids),id),bk,_ty = intern_pat test_kind ntnvars env bk pat in
(* TODO: use cast? *)
match disjpat with
| [pat] -> glob_constr_of_cases_pattern (Global.env()) pat
| _ -> user_err Pp.(str "Cannot turn a disjunctive pattern into a term.")
with Not_found ->
try