-
Notifications
You must be signed in to change notification settings - Fork 2
/
sexp-rewrite.el
1708 lines (1547 loc) · 65 KB
/
sexp-rewrite.el
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
;;; sexp-rewrite.el --- pattern-based rewriting of sexp-structured code -*- lexical-binding:t -*-
;; Copyright 2013-2019 Ryan Culpepper.
;; Released under the terms of the GPL version 3 or later;
;; see the text after `sexprw-legal-notice' for details.
;; Version: 0.04
(defconst sexprw-copyright "Copyright 2013-2019 Ryan Culpepper")
(defconst sexprw-version "0.04")
(defconst sexprw-author-name "Ryan Culpepper")
(defconst sexprw-author-email "ryanc@racket-lang.org")
(defconst sexprw-web-page "https://github.com/rmculpepper/sexp-rewrite")
(defconst sexprw-legal-notice
"This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License at http://www.gnu.org/licenses/gpl-3.0.html
for more details.")
;;; Commentary:
;; ============================================================
;; TO DO
;; short term
;; - make sure sugared pattern lang is complete for core pattern lang
;; - automated testing
;; - documentation, rationale, etc
;; - documentation for individual tactics ??
;; - support COMMENT var kind
;; - better comment handling (custom regexp? may need hook)
;; - improve guard support
;; - require guard extends env?
;; - add ranges back to block matches
;; - might be useful for recursive processing ??
;; - package nicely in Emacs idiom
;; - minor mode ??
;; - make sure keybindings are added politely
;; - customization options ??
;; - tweak whitespace handling ??
;; - hook for scan-sexps replacement
;; - hook for scan-whitespace, scan-comments replacements
;; - custom var to disable square brackets (use parens instead)
;; - build "tactic apropos"---search by literals in tactic pattern & template
;; - more interactive/flexible rewriting
;; - eg, move let/let*/letrec bindings to <interactive point>
;; - put rewrite rules in "bundles", and enable different "bundles" for
;; different major modes (scheme-mode, racket-mode, emacs-lisp-mode, ...)
;; long term
;; - port to DrRacket
;; - use DrRacket semantic info (eg, freevars) for safety
;; ============================================================
;; Misc notes
;; Matching functions, etc return nil on failure, only raise error on
;; bad input (illegal pattern, etc).
;; ============================================================
;; Keybindings
;;; Code:
(defvar sexprw-mode-map
(let ((mainmap (make-sparse-keymap))
(map (make-sparse-keymap)))
(define-key mainmap (kbd "C-c C-s") map)
(define-key map "e" 'sexprw-auto-expression)
(define-key map "d" 'sexprw-auto-definition)
(define-key map "x" 'sexprw-execute-tactic)
(define-key map "s" 'sexprw-search-pattern)
(define-key map "i" 'sexprw-search-rewrite)
(define-key map "[" 'sexprw-squarify)
(define-key map "(" 'sexprw-roundify)
(define-key map "k" 'sexprw-kill-next-sexpagon-sexp)
(define-key map "w" 'sexprw-kill-sexpagon-region)
(define-key map "y" 'sexprw-yank-sexpagon)
(define-key map (kbd "M-SPC") 'sexprw-collapse-space/move-sexps)
(define-key map [tab] 'sexprw-indent-rigidly)
(define-key map (kbd "r e")
(lambda () (interactive) (sexprw-auto-expression 100)))
(define-key map (kbd "r d")
(lambda () (interactive) (sexprw-auto-definition 100)))
mainmap))
(defvar sexprw-auto-expression-tactics nil
"List of tactics tried by `sexprw-auto-expression'.")
(defvar sexprw-auto-definition-tactics nil
"List of tactics tried by `sexprw-auto-definition'.")
(defvar sexprw-tactic-history nil)
(defvar sexprw-pattern-history nil)
(defvar sexprw-template-history nil)
(defgroup sexprw nil
"Customization options for sexp-rewrite."
:group 'scheme)
(defcustom sexprw-disabled-auto-tactics nil
"Tactics that should not be run automatically.
Affects only `sexprw-auto-expression' and `sexprw-auto-definition';
disabled tactics can still be run via `sexprw-execute-tactic', etc."
:type '(repeat symbol))
;;;###autoload
(define-minor-mode sexprw-mode
"Minor mode for pattern-based rewrite of sexp-structured code."
;; Implicitly activates sexprw-mode-map when enabled.
:init-value nil)
;; FIXME: This should likely be in an emacs-lisp-rewrite.el with corresponding
;; rewrite rules.
;;;###autoload
(add-hook 'emacs-lisp-mode-hook #'sexprw-mode)
;;;###autoload
(add-hook 'scheme-mode-hook #'sexprw-mode)
(defun sexprw-disable-tactic (tactic-name)
(interactive
(list (sexprw-read-tactic-from-minibuffer)))
(push tactic-name sexprw-disabled-auto-tactics))
(defun sexprw-enable-tactic (tactic-name)
(interactive
(list (sexprw-read-tactic-from-minibuffer)))
(setq sexprw-disabled-auto-tactics
(delete tactic-name sexprw-disabled-auto-tactics)))
;; ============================================================
;; Debugging and diagnostics
(defvar sexprw-current-operation nil
"Name of currently executing operation.")
(defvar sexprw-failure-info nil
"Information about last sexp-rewrite failure(s).")
(defun sexprw-fail (info)
(push (cons sexprw-current-operation (cons (point) info)) sexprw-failure-info)
nil)
(defun sexprw-show-failure-info ()
(interactive)
(message "%S" sexprw-failure-info))
(define-error 'sexprw-template-error "Error instantiating template")
;; ============================================================
;; Running tactics
(defun sexprw-auto-expression (&optional times)
"Run the default sexp-rewrite tactics for expressions.
Customizable via the variable `sexprw-auto-expression-tactics'."
(interactive "p")
(sexprw-execute-tactics sexprw-auto-expression-tactics times t))
(defun sexprw-auto-definition (&optional times)
"Run the default sexp-rewrite tactics for definitions.
Customizable via the variable `sexprw-auto-definition-tactics'."
(interactive "p")
(sexprw-execute-tactics sexprw-auto-definition-tactics times t))
(defun sexprw-execute-tactic (tactic-name &optional times0)
"Read sexprw-rewrite tactic, then try to execute it."
(interactive
(list (sexprw-read-tactic-from-minibuffer)
(prefix-numeric-value current-prefix-arg)))
(sexprw-execute-tactics (list tactic-name) times0 nil))
(defun sexprw-execute-tactics (tactic-names times0 respect-disabled)
(setq sexprw-failure-info nil)
(let ((rused (sexprw-run-tactics-until-success tactic-names times0)))
(cond ((consp rused)
(cond ((= (length rused) 1)
(message "Applied tactic %s" (car rused)))
(t (message "Applied tactics: %s" (reverse rused)))))
(t
(cond ((= (length tactic-names) 1)
(message "Tactic %s not applicable" (car tactic-names)))
(t (message "No applicable tactic")))))))
;; sexprw-run-tactic* functions return list of successful tactics in
;; reverse order
(defun sexprw-run-tactic (tactic-name)
(let* ((nt-val (sexprw-nt-value tactic-name))
(nt-pattern (nth 1 nt-val)))
(and (let ((sexprw-current-operation `(tactic ,tactic-name))) ; fluid-let
(sexprw-rewrite/ast nt-pattern '(VAR $out)))
(list tactic-name))))
(defun sexprw-run-tactics-until-success (tactics &optional times0 respect-disabled)
(let ((times times0)
success
rused)
(while (> times 0)
(setq times (1- times))
(setq success nil)
(dolist (tactic tactics)
(unless (memq tactic sexprw-disabled-auto-tactics)
(unless success
(when (sexprw-run-tactic tactic)
(setq success t)
(setq rused (cons tactic rused))))))
(unless success (setq times 0)))
rused))
;; ============================================================
;; Rewriting
(defun sexprw-rewrite (pattern template &optional guard)
(interactive
(list
(read-from-minibuffer "Pattern: " nil nil t 'sexprw-pattern-history)
(read-from-minibuffer "Template: " nil nil t 'sexprw-template-history)))
;; (message "parsed pattern = %S" (sexprw-desugar-pattern pattern nil))
(sexprw-rewrite/ast (sexprw-desugar-pattern pattern nil)
(sexprw-desugar-pattern template t)
guard))
(defun sexprw-rewrite/ast (pattern template &optional guard)
(save-excursion
(sexprw-skip-whitespace)
(let* ((init-point (point))
;; puts point after pattern match
(replacement (sexprw-compute-rewrite/ast pattern template guard)))
(and replacement
(progn
(delete-and-extract-region init-point (point))
(sexprw-emit replacement)
t)))))
(defun sexprw-compute-rewrite/ast (pattern template &optional guard)
;; (message "pattern = %S" pattern)
;; (message "template = %S" template)
(let ((env (sexprw-match pattern)))
;; (message "point = %S" (point))
;; (message "env = %S" env)
(and env
(sexprw-check-nonlinear-patterns (car env))
(let ((env* (if guard (funcall guard (car env)) env)))
;; (message "guarded env = %S" env*)
(and (or env*
(sexprw-fail `(guard env= ,env)))
(let ((preoutput
(condition-case error-info
(sexprw-template* template (car env*))
(template-error
(sexprw-fail `(template ,error-info guard-env=
,(car env*)))))))
;; (message "preoutput = %S" preoutput)
(and preoutput
(let ((output
(condition-case error-info
(sexprw-output preoutput)
(template-error
(sexprw-fail `(output ,error-info))))))
;; (message "output = %S" output)
output))))))))
;; FIXME: here's another quadratic function...
(defun sexprw-check-nonlinear-patterns (env0)
(let ((ok t)
(env env0))
(while (and env ok)
(let* ((entry1 (car env))
(key1 (car entry1))
(rest-env (cdr env)))
(setq env rest-env)
(let ((entry2 (assq key1 rest-env)))
(when entry2
(unless (sexprw-entry-equal (cdr entry1) (cdr entry2))
(sexprw-fail `(nonlinear-pvar ,key1 env= ,env0))
(setq ok nil))))))
ok))
(defun sexprw-entry-equal (a b)
(cond ((and (eq (car a) 'rep) (eq (car b) 'rep)
(= (length a) (length b)))
(let ((as (cdr a))
(bs (cdr b))
(ok t))
(while (and as bs)
(setq ok (sexprw-entry-equal (car as) (car bs)))
(setq as (cdr as))
(setq bs (cdr bs)))
ok))
((and (eq (car a) 'block) (eq (car b) 'block))
;; FIXME: could compare sexpagons (if exist), slightly more equalities
(equal (sexprw-block-text a)
(sexprw-block-text b)))
(t nil)))
;; ============================================================
;; Pretty patterns and templates
;; PP ::= symbol ~ (quote symbol)
;; | $name:nt ~ (VAR $name nt) ; sigil is part of pvar name
;; | $name ~ (VAR $name sexp)
;; | (PP*) ~ (LIST P*)
;; | (!@ PP*) ~ (SPLICE P*)
;; | (!SPLICE PP*) ~ (SPLICE P*)
;; | PP ... ~ (pREP P <Pk>) ; <Pk> is patterns that follow,
;; ; grouped as splice
;; | (!OR PP*) ~ (OR P*)
;; | (!AND PP*) ~ (AND P*)
;; | (!GUARD P expr)~ (GUARD P expr)
;; PT ::= like PP, with following additions and replacements:
;; | [ PT* ] ~ (SQLIST T*)
;; | (!SQ PT*) ~ (SQLIST T*)
;; | !NL ~ (NL)
;; | !SP ~ (SP)
;; | !SL ~ (SL)
;; | !NOSP ~ (NONE)
;; | (!REP PT vars) ~ (tREP T vars)
;; | PT ... ~ (tREP T nil) ; vars=nil means "auto"
(defun sexprw-desugar-pattern (pretty template)
(cond ((null pretty)
'(LIST))
((symbolp pretty)
(sexprw-desugar-pattern-symbol pretty template))
((vectorp pretty)
(if template
(cons 'SQLIST (sexprw-desugar-pattern-list (append pretty nil) template))
(cons 'LIST (sexprw-desugar-pattern-list (append pretty nil) template))))
((not (consp pretty))
(error "Bad %s: %S" (if template "template" "pattern") pretty))
((memq (car pretty) '(!@ !SPLICE))
(cons 'SPLICE (sexprw-desugar-pattern-list (cdr pretty) template)))
((eq (car pretty) '!SQ)
(if template
(cons 'SQLIST (sexprw-desugar-pattern-list (cdr pretty) template))
(error "Bad pattern (!SQ not allowed): %S" pretty)))
((eq (car pretty) '!REP)
(if template
(list 'tREP (sexprw-desugar-pattern (nth 1 pretty)) (nth 2 pretty))
(error "Bad pattern (!REP not allowed): %S" pretty)))
((eq (car pretty) '!OR)
(if template
(error "Bad template (!OR not allowed): %S" pretty)
(cons 'OR
(mapcar (lambda (p) (sexprw-desugar-pattern p nil))
(cdr pretty)))))
((eq (car pretty) '!AND)
(if template
(error "Bad template (!AND not allowed): %S" pretty)
(cons 'AND
(if (consp (cdr pretty))
(cons (sexprw-desugar-pattern (cadr pretty) nil)
(mapcar (lambda (p) (sexprw-desugar-pattern p nil))
(cddr pretty)))
nil))))
((eq (car pretty) '!GUARD)
(if template
(error "Bad template (!GUARD not allowed): %S" pretty)
(let* ((subpattern (sexprw-desugar-pattern (nth 1 pretty) nil))
(guard (nth 2 pretty)))
(unless (functionp guard)
(error "Bad template: guard is not a function: %S" pretty))
(list 'GUARD subpattern guard))))
(t ; list
(cons 'LIST (sexprw-desugar-pattern-list pretty template)))))
(defun sexprw-desugar-pattern-symbol (pretty template)
(let ((name (symbol-name pretty)))
(cond ((and template (eq pretty '!NL))
'(NL))
((and template (eq pretty '!SP))
'(SP))
((and template (eq pretty '!NOSP))
'(NONE))
((and template (eq pretty '!SL))
'(SL))
((eq pretty '...)
(error "Misplaced ellipses: %S" pretty))
((string-match "^[!]" name)
(error "Bad symbol in %s (reserved): %S"
(if template "template" "pattern")
pretty))
((string-match "^[$][_[:alpha:]][^:]*$" name)
(if template
`(VAR ,pretty)
`(VAR ,pretty sexp)))
((string-match "^\\([$][_[:alpha:]][^:]*\\):\\([[:alpha:]].*\\)$" name)
(let ((var (intern (match-string 1 name)))
(nt (intern (match-string 2 name))))
(when nil ;; too early, prevents mutually recursive nts, forward refs, etc.
(unless (sexprw-nt-symbolp nt)
(error "Bad pattern variable, no such sexpr-rewrite nonterminal: %S" pretty)))
`(VAR ,var ,nt)))
((string-match "^[$]" name)
(error "Bad pattern variable: %S" pretty))
(t `(quote ,pretty)))))
(defun sexprw-desugar-pattern-list (pretty template)
;; Note: *not* same as (mapcar sexprw-desugar-pattern ....),
;; because handles ellipses.
(let ((rpretty (reverse pretty))
(accum nil)
(dots nil))
(while rpretty
(let ((p1 (car rpretty)))
(setq rpretty (cdr rpretty))
(cond ((eq p1 '...)
(when dots (error "Repeated ellipses in pattern: %S" pretty))
(setq dots t))
(t
(let ((pp1 (sexprw-desugar-pattern p1 template)))
(when dots
(setq dots nil)
(cond (template
(setq pp1 (list 'tREP pp1 nil)))
(t
(setq pp1 (list 'pREP pp1 (cons 'SPLICE accum)))
(setq accum nil))))
(push pp1 accum))))))
(when dots (error "Misplaced dots at beginning of pattern: %S" pretty))
accum))
;; ============================================================
;; Core patterns
;; P ::= (LIST P*)
;; | (SPLICE P*)
;; | (quote symbol)
;; | (VAR symbol nt)
;; | (pREP P Pk)
;; | (AND P*)
;; | (OR P*)
;; | (GUARD P expr)
;;
;; Matching builds an alist mapping pvar symbols to EnvValue
;; EnvValue ::= Block
;; | (list 'rep EnvValue) ; representing depth>0 list
;; | (list 'pre PreOutput) ; representing computed output
;;
;; (pREP P Pk) means "P ... Pk": match as many P as possible s.t. still
;; possible to match Pk afterwards (then commit). Handling together
;; avoids (non-local) backtracking while supporting non-trivial Pks.
;; FIXME (or not): doesn't handle dotted-pair notation
;; TODO: support IMPURITY as kind, matches non-whitespace stuff
;; between (point) and next sexp.
(defconst sexprw-all-whitespace-re "[[:space:]\n]*")
(defconst sexprw-pure-atom-re
;; Note: vague approximation, doesn't distinguish numbers from symbols,
;; doesn't support \ and | escapes, etc, doesn't support Unicode chars.
;; FIXME: use [:alpha:] to capture more chars (Unicode) ???
;; FIXME: includes dot ?
;; FIXME: should be predicate, not regexp
"^[-~!@$^&*_+=:./<>?a-zA-Z#0-9]+$")
(defun sexprw-match (pattern)
"Matches the sexp starting at point against core PATTERN,
returning an \(list ENV) mapping the pattern variables of
PATTERN to fragments, or nil on failure. Advances point to end
of matched term(s)."
;; (message "matching (%S): %S" (point) pattern)
(cond ((not (consp pattern))
(error "Bad pattern: %s" pattern))
((eq (car pattern) 'quote)
;; Note: grabs pure-sexp, checks contains symbol
(let ((next (sexprw-grab-next-sexp t)))
(and (or next
(sexprw-fail `(match quote pure-sexp)))
(let ((pure-text (sexprw-block-pure-text next)))
(and (or (string-match sexprw-pure-atom-re pure-text)
(sexprw-fail `(match quote is-symbol)))
(or (equal pure-text (symbol-name (cadr pattern)))
(sexprw-fail
`(match quote equal
,(symbol-name (cadr pattern)))))
(list nil))))))
((eq (car pattern) 'VAR)
(sexprw-match-var (nth 1 pattern) (nth 2 pattern)))
((eq (car pattern) 'LIST)
(sexprw-match-list (cdr pattern)))
((eq (car pattern) 'SPLICE)
(sexprw-match-patterns (cdr pattern)))
((eq (car pattern) 'pREP)
(sexprw-match-rep (nth 1 pattern) (nth 2 pattern)))
((eq (car pattern) 'OR)
(let ((init-point (point))
(result nil)
(rfailinfos nil)
(alternatives (cdr pattern)))
(while (and (consp alternatives) (not result))
(goto-char init-point)
(let ((sexprw-failure-info nil)) ;; fluid-let
(setq result (sexprw-match (car alternatives)))
(push sexprw-failure-info rfailinfos))
(setq alternatives (cdr alternatives)))
(or result
(sexprw-fail `(match or inners= ,(reverse rfailinfos))))))
((eq (car pattern) 'AND)
(let ((init-point (point))
(renvs nil)
(ok t)
(first-time t)
(conjuncts (cdr pattern)))
;; Use restriction and looking-at (below) to ensure that
;; all conjuncts match the same sexps.
;; In other words, first conjunct constrains what
;; subsequent conjuncts can see.
(save-restriction
(while (and ok (consp conjuncts))
(goto-char init-point)
(let ((result (sexprw-match (car conjuncts))))
(cond ((and result
(or first-time
(looking-at
(concat sexprw-all-whitespace-re "\\'"))))
(setq first-time nil)
(push (car result) renvs)
(narrow-to-region init-point (point)))
(t
(setq ok nil))))
(setq conjuncts (cdr conjuncts)))
(and ok (list (apply #'append (reverse renvs)))))))
((eq (car pattern) 'GUARD)
(let ((result (sexprw-match (nth 1 pattern)))
(guard (nth 2 pattern)))
(and result
(let ((env (car result)))
(or (sexprw-check-guard-result (funcall guard env) env)
(sexprw-fail `(match guard env= ,env)))))))
(t (error "Bad pattern: %S" pattern))))
(defun sexprw-check-guard-result (result _env)
;; FIXME: check result is nil or (list extension-of-env)?
result)
(defun sexprw-match-var (pvar nt)
(unless (sexprw-nt-symbolp nt)
(error "Not defined as sexp-rewrite nt: %S" nt))
(sexprw-skip-whitespace)
(let* ((init-point (point))
(nt-val (sexprw-nt-value nt))
(nt-pattern (nth 1 nt-val))
(nt-attrs (nth 2 nt-val)))
(let ((result (sexprw-match nt-pattern)))
(and result
(sexprw-check-nonlinear-patterns (car result))
(let ((env (sexprw-adj-env (car result) nt nt-attrs pvar)))
(unless (assq pvar env)
(let ((b (sexprw-range-to-block init-point nil (point))))
(push (cons pvar b) env)))
(if (eq pvar '$_)
(list nil)
(list env)))))))
(defun sexprw-adj-env (env nt attrs prefix)
"Checks, restricts, and prefixes ENV."
(let ((new-env nil))
(dolist (attr attrs)
(let ((entry (assq attr env)))
(unless entry
(error "Nonterminal `%S' did not bind attribute `%S'" nt attr))
(let ((prefixed-attr
(if (eq attr '$)
prefix
(intern (format "%s.%s" prefix attr)))))
(push (cons prefixed-attr (cdr entry)) new-env))))
(reverse new-env)))
;; returns t on success, nil if fewer than n sexps before end
(defun sexprw-skip-forward-to-n-sexps-before-end (n)
(cond ((zerop n)
(goto-char (point-max)))
(t (let ((fast (point))
(slow (point)))
(setq fast (ignore-errors (scan-sexps fast n)))
(and fast
(progn
(while fast
(setq fast (ignore-errors (scan-sexps fast 1)))
(when fast (setq slow (scan-sexps slow 1))))
(goto-char slow)
t))))))
(defun sexprw-match-list (inners)
(let ((next (sexprw-grab-next-sexp t)))
(and (or next
(sexprw-fail `(match-list grab)))
(member (substring (sexprw-block-pure-text next) 0 1) '("(" "[" "{"))
;; narrow to just after start, just before end
(let ((result
(save-excursion
(save-restriction
(let ((start (sexprw-block-pure-start-position next))
(end (sexprw-block-end-position next)))
(goto-char (1+ start))
(narrow-to-region (1+ start) (1- end))
(let ((result (sexprw-match-patterns inners)))
(and result
(or (looking-at (concat sexprw-all-whitespace-re "\\'"))
(sexprw-fail `(match-list end check-whitespace)))
result)))))))
;; save-excursion resets point to end of list
result))))
(defun sexprw-match-patterns (inners)
(let ((accum (list '()))) ; nil or (list alist)
(dolist (inner inners)
(when accum
(let ((inner-result (sexprw-match inner)))
(setq accum (and inner-result
(list (append (car inner-result) (car accum))))))))
accum))
(defun sexprw-match-rep (inner after)
;; FIXME: add failure info
(let ((matches nil))
;; matches : (listof (list match-count reversed-env-list point))
;; Each entry is after successfully matching inner match-count times.
;; Stage 1: build up matches of inner pattern
(let ((count 0)
(renvs nil)
(last-point (point))
(proceed t))
(push (list count renvs last-point) matches)
(while proceed
(let ((next-result (sexprw-match inner)))
(cond ((and next-result (> (point) last-point))
(setq count (1+ count))
(setq last-point (point))
(push (car next-result) renvs)
(push (list count renvs last-point) matches))
(t
(setq proceed nil))))))
;; Stage 2: search for match that satisfies after pattern
(let ((answer nil))
(while (and matches (not answer))
(let* ((match0 (car matches))
(match-renvs (nth 1 match0))
(match-point (nth 2 match0)))
(setq matches (cdr matches))
(goto-char match-point)
(let ((next-result (sexprw-match after)))
(when next-result
(let* ((env (sexprw-reverse-merge-alists inner match-renvs))
(env (append (car next-result) env)))
(setq answer (list env)))))))
answer)))
;; FIXME: quadratic
(defun sexprw-reverse-merge-alists (inner alists)
;; Not every key might appear in every alist, due to OR patterns.
(let ((keys (delete-dups (sexprw-pattern-variables inner nil)))
(accum nil))
(dolist (key keys)
(let ((values nil))
(dolist (alist alists)
(let ((kv (assq key alist)))
(when kv (push (cdr kv) values))))
;; Don't reverse values; thus "reverse merge" alists
(push (cons key (cons 'rep values)) accum)))
accum))
(defun sexprw-pattern-variables (pattern onto)
;; Accept templates too
(cond ((eq (car pattern) 'VAR)
(when (> (length pattern) 2)
(let* ((pvar (nth 1 pattern))
(nt (nth 2 pattern))
(nt-val (sexprw-nt-value nt)))
(let ((attrs (nth 2 nt-val)))
(dolist (attr attrs)
(unless (eq attr '$)
(push (intern (format "%s.%s" pvar attr)) onto))))))
(cons (nth 1 pattern) onto))
((memq (car pattern) '(LIST SPLICE SQLIST OR))
(dolist (inner (cdr pattern))
(setq onto (sexprw-pattern-variables inner onto)))
onto)
((eq (car pattern) 'pREP)
(sexprw-pattern-variables (nth 1 pattern)
(sexprw-pattern-variables (nth 2 pattern) onto)))
((eq (car pattern) 'tREP)
(sexprw-pattern-variables (nth 1 pattern) onto))
((memq (car pattern) '(quote SP NL SL))
onto)
(t (error "Bad pattern: %S" pattern))))
;; ----
;; A Block is (list 'block TEXT ONELINEP STARTCOL IMPUREPREFIX START END).
(defun sexprw-block-text (block)
(nth 1 block))
(defun sexprw-block-onelinep (block)
(nth 2 block))
(defun sexprw-block-start-column (block)
(nth 3 block))
(defun sexprw-block-impure-prefix (block)
(nth 4 block))
(defun sexprw-block-start-position (block)
(nth 5 block))
(defun sexprw-block-end-position (block)
(nth 6 block))
(defun sexprw-block-purep (block)
(zerop (sexprw-block-impure-prefix block)))
(defun sexprw-block-pure-start-position (block)
(let ((start (sexprw-block-start-position block))
(impure-prefix (sexprw-block-impure-prefix block)))
(unless impure-prefix
(error "Block has unknown contents"))
(+ start impure-prefix)))
(defun sexprw-block-pure-text (block)
(let ((text (sexprw-block-text block))
(impure-prefix (sexprw-block-impure-prefix block)))
(cond ((null impure-prefix)
(error "Block has unknown contents"))
((zerop impure-prefix)
text)
(t (substring text 0 impure-prefix)))))
(defun sexprw-block-sexpagon (block)
(let* ((text (sexprw-block-text block))
(start-col (sexprw-block-start-column block)))
(sexprw-sexpagon text start-col)))
(defun sexprw-grab-next-sexp (require-pure)
"Grabs next sexp and returns Block or nil.
A Block is (list 'block TEXT ONELINEP STARTCOL IMPUREPREFIX START END).
TEXT is a string containing the contents of the block. ONELINEP
indicates if the block consists of a single line.
If IMPUREPREFIX is an integer, the block represents a single sexp
preceeded by comments, and IMPUREPREFIX is the number of
characters before the start of the sexp. If IMPUREPREFIX is nil,
then TEXT may represent multiple sexps or something else
entirely.
If REQUIRE-PURE is non-nil, then there must be no non-whitespace
characters before the start of the sexp, or else nil is returned.
On success, advances point to end of sexp."
(let ((result (sexprw-grab-next-sexp-range)))
(and result
(let ((nonws-point (nth 1 result))
(start-point (nth 2 result))
(end-point (nth 3 result)))
(and (or (not require-pure)
(= nonws-point start-point))
(progn
(goto-char end-point)
(sexprw-range-to-block nonws-point
start-point
end-point)))))))
(defun sexprw-range-to-block (start pure-start end)
(list 'block
(filter-buffer-substring start end)
(= (line-number-at-pos start)
(line-number-at-pos end))
(save-excursion
(save-restriction
(widen)
(goto-char start)
(- (point) (line-beginning-position))))
(and pure-start (- pure-start start))
start
end))
(defun sexprw-grab-next-sexp-range ()
;; FIXME/BUG: backwards scan loses things like quote prefix,
;; can lead to treating "'x" as atomic sexp (shouldn't be).
;; Maybe add custom comment handling to avoid backwards scan?
"Returns (list INIT-POINT NONWS-POINT START-POINT END-POINT) or nil.
INIT-POINT is where point started. NONWS-POINT is the location of
the first non-whitespace character. START-POINT is where the sexp
starts. END-POINT is where the sexp ends. Does not change
point."
(condition-case _error-info
(save-excursion
(let ((init-point (point)))
(sexprw-skip-whitespace)
(let* ((nonws-point (point))
(end-point (scan-sexps nonws-point 1))
(start-point (and end-point (scan-sexps end-point -1))))
;; scan-sexps signals error if EOF inside parens,
;; returns nil if EOF no sexp found
(cond ((and start-point
(< start-point end-point))
(list init-point nonws-point start-point end-point))
(t nil)))))
(scan-error
;; (message "Error is %s" error-info)
nil)))
(defun sexprw-skip-whitespace ()
(skip-chars-forward "[:space:]\n"))
;; ============================================================
;; Guard utilities
(defun sexprw-env-ref (env key)
"Fetch the value associated with KEY in ENV, or nil otherwise."
(let ((result (assq key env)))
(and result (cdr result))))
(defun sexprw-guard-all-distinct (env &rest pvars)
"Check that all of the atoms bound to the PVARS are distinct.
If there is a duplicate, or if any PVAR has a non-atom binding, return nil.
On success, return (list ENV), so suitable as the body of a guard function."
(let ((seen (make-hash-table :test 'equal))
(worklist nil)
(failed nil))
(dolist (pvar pvars)
(setq worklist (list (sexprw-env-ref env pvar)))
(while (and worklist (not failed))
(let ((item (car worklist)))
(setq worklist (cdr worklist))
(cond ((eq (car item) 'atom)
(when (gethash (cadr item) seen nil)
(setq failed t))
(puthash (cadr item) seen t))
((eq (car item) 'rep)
(setq worklist (append (cdr item) worklist)))
(t
(error "Non-atom value for pvar '%s': %S" pvar item)
(setq failed t))))))
(and (or (not failed)
(sexprw-fail `(guard all-distinct ,pvars)))
(list env))))
(defun sexprw-guard-no-dot (env &rest pvars)
"Check that none of the atoms bound to the PVARS is a dot.
On failure, return nil; on success, return (list ENV), so suitable as
guard body."
(let ((worklist nil)
(failed nil))
(dolist (pvar pvars)
(setq worklist (list (sexprw-env-ref env pvar)))
(while (and worklist (not failed))
(let ((item (car worklist)))
(setq worklist (cdr worklist))
(cond ((eq (car item) 'block)
(when (equal (sexprw-block-pure-text item) ".")
(setq failed t)))
((eq (car item) 'rep)
(setq worklist (append (cdr item) worklist)))
(t
(error "Bad value for pvar '%s': %S" pvar item))))))
(and (or (not failed)
(sexprw-fail `(guard no-dot)))
(list env))))
;; ============================================================
;; Templates
;;
;; T ::= string ; literal text, eg "\n" inserts non-latent newline
;; | (quote symbol) ; literal symbol
;; | (VAR symbol) ; pattern variable
;; | (LIST T*) ; parenthesized list
;; | (SQLIST T*) ; bracketed list
;; | (SPLICE T*) ; spliced list contents
;; | (SP) ; latent space (ie, change latent newline to latent
;; | ; space)
;; | (SL) ; latent "soft" newline: if surrounding list has any
;; ; NLs or multi-line blocks, NL, else ignore
;; | (NL) ; latent newline
;; | (tREP T vars) ; repetition
;;
;; PreOutput = (treeof PreOutputPart)
;; PreOutputPart =
;; - string
;; - 'SP
;; - 'NL
;; - 'SL
;; - 'NONE
;; - (cons 'SEXPAGON listofstring)
;; - (cons 'SL=nil PreOutput)
;; - (cons 'SL=NL PreOutput)
;; Interpret PreOutput left to right; *last* spacing symbol to occur wins.
;;
;; Output = (listof (U string 'NL (cons 'SEXPAGON listofstring)))
(defun sexprw-template (template env)
"Produces (cons 'pre PreOutput) for given TEMPLATE and ENV."
(cons 'pre (sexprw-template* (sexprw-desugar-pattern template t) env)))
(defvar sexprw-template*-multiline nil ;; boolean
"True when (hard) NL or multi-line block occurs in current LIST/SQLIST.")
(defun sexprw-template* (template env)
"Interprets core TEMPLATE using the pattern variables of ENV."
;; (message "** template = %S" template)
(cond ((stringp template)
template)
((not (consp template))
(error "Bad template: %S" template))
((eq (car template) 'quote)
(list (symbol-name (cadr template))
'SP))
((eq (car template) 'VAR)
(sexprw-template-var (cadr template) env))
((memq (car template) '(LIST SQLIST))
(let ((open (if (eq (car template) 'LIST) "(" "["))
(close (if (eq (car template) 'LIST) ")" "]"))
(multiline nil))
(let ((contents
(let ((sexprw-template*-multiline nil)) ;; fluid-let
(prog1 (sexprw-template-list-contents (cdr template) env)
(setq multiline sexprw-template*-multiline)))))
(when multiline (setq sexprw-template*-multiline t))
(list open
(cons (if multiline 'SL=NL 'SL=nil) contents)
'NONE
close
'SP))))
((eq (car template) 'SPLICE)
(sexprw-template-list-contents (cdr template) env))
((memq (car template) '(SP NL SL NONE))
(car template))
((eq (car template) 'tREP)
(sexprw-template-rep template env))))
(defun sexprw-template-rep (template env)
;; (message "env for rep = %S" env)
(let* ((inner (nth 1 template))
(vars (or (nth 2 template)
;; Take *all* depth>0 pvars in env that occur in template
;; (beware duplicate keys in alist)
(let* ((env-keys (sexprw-pattern-variables template '()))
;; FIXME: Ack! quadratic, mutates, etc
(env-keys (delete-dups env-keys))
(raccum '()))
(dolist (key env-keys)
(when (eq (car (cdr (assq key env))) 'rep)
(setq raccum (cons key raccum))))
(reverse raccum))))
(vals (mapcar (lambda (pvar)
(let ((entry (assq pvar env)))
(unless entry
(error "No entry for pvar '%s' in: %S" pvar env))
(let ((value (cdr entry)))
(unless (and (consp value) (eq (car value) 'rep))
(error "Value for pvar '%s' is not list (depth error): %S"
pvar entry))
(cdr value))))
vars)))
(unless vars (error "No repetition vars for tREP: %S" template))
(let* ((lengths (mapcar #'length vals))
(length1 (car lengths)))
(dolist (l lengths)
(unless (= l length1)
(signal 'template-error 'ellipsis-count-mismatch)))
(let ((raccum '()))
(dotimes (_i length1)
(let* ((extenv+vals (sexprw-split/extend-env vars vals env))
(extenv (car extenv+vals)))
(setq vals (cdr extenv+vals))
(setq raccum
(cons (sexprw-template* inner extenv)
raccum))))
(reverse raccum)))))
(defun sexprw-split/extend-env (vars vals env)
(let* ((val1s (mapcar #'car vals))
(rests (mapcar #'cdr vals)))
(while vars
(setq env (cons (cons (car vars) (car val1s)) env))
(setq vars (cdr vars))
(setq val1s (cdr val1s)))
(cons env rests)))
(defun sexprw-template-var (pvar env)
(let ((entry (assq pvar env)))
(unless entry
(error "No entry for pvar '%s'" pvar))
(let ((value (cdr entry)))
(cond ((and (consp value) (eq (car value) 'block))
(let ((text (sexprw-block-text value))
(lines (sexprw-block-sexpagon value))
(space (if (sexprw-block-onelinep value) 'SP 'NL)))
(unless (sexprw-block-onelinep value)