Debian Codegraph @

src/macro.c

raw
1 /*
2 * macro.c - macro implementation
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #define LIBGAUCHE_BODY
35 #include "gauche.h"
36 #include "gauche/priv/configP.h"
37 #include "gauche/code.h"
38 #include "gauche/vminsn.h"
39 #include "gauche/priv/macroP.h"
40 #include "gauche/priv/identifierP.h"
41 #include "gauche/priv/builtin-syms.h"
42
43 /* avoid C++ reserved name conflict.
44 (I hate languages that take away names from programmers!) */
45 #define template templat
46
47 /* define if you want to debug syntax-rule expander */
48 /*#define DEBUG_SYNRULE*/
49
50 /*===================================================================
51 * Syntax object
52 */
53
54 static void syntax_print(ScmObj obj, ScmPort *port,
55 ScmWriteContext *mode SCM_UNUSED)
56 {
57 ScmSymbol *name = SCM_SYNTAX(obj)->name;
58 ScmModule *mod = SCM_SYNTAX(obj)->mod;
59 if (mod == NULL) {
60 Scm_Printf(port, "#<syntax %A>", (name ? SCM_OBJ(name) : SCM_FALSE));
61 } else {
62 Scm_Printf(port, "#<syntax %A#%A>",
63 mod->name,
64 (name ? SCM_OBJ(name) : SCM_FALSE));
65 }
66 }
67
68 SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_SyntaxClass, syntax_print);
69
70 ScmObj Scm_MakeSyntax(ScmSymbol *name, ScmModule *mod, ScmObj handler)
71 {
72 ScmSyntax *s = SCM_NEW(ScmSyntax);
73 SCM_SET_CLASS(s, SCM_CLASS_SYNTAX);
74 s->name = name;
75 s->mod = mod;
76 s->handler = handler;
77 return SCM_OBJ(s);
78 }
79
80 /*===================================================================
81 * Macro object
82 */
83
84 ScmObj Scm_MakeMacro(ScmObj name, ScmObj transformer,
85 ScmObj info, u_long flags)
86 {
87 ScmMacro *s = SCM_NEW(ScmMacro);
88 SCM_SET_CLASS(s, SCM_CLASS_MACRO);
89 s->name = name;
90 s->transformer = transformer;
91 s->info_alist = info;
92 s->flags = flags;
93 return SCM_OBJ(s);
94 }
95
96 ScmObj Scm_MacroTransformer(ScmMacro *mac)
97 {
98 return mac->transformer;
99 }
100
101 ScmObj Scm_MacroName(ScmMacro *mac)
102 {
103 return (mac->name? SCM_OBJ(mac->name) : SCM_FALSE);
104 }
105
106 /* Called from syntax-parameterize.
107 This API is internal and subject to change.
108 */
109 void Scm__SwapMacroTransformer(ScmMacro *mac,
110 ScmObj *pxformer,
111 u_long *pflags)
112 {
113 if (!(mac->flags & SCM_MACRO_PARAMETERIZABLE)) {
114 Scm_Error("Macro %S is not parameterizable.", SCM_OBJ(mac));
115 }
116 ScmObj oxformer = mac->transformer;
117 u_long oflags = mac->flags;
118
119 mac->transformer = *pxformer;
120 mac->flags = *pflags | SCM_MACRO_PARAMETERIZABLE;
121
122 *pxformer = oxformer;
123 *pflags = oflags & (~SCM_MACRO_PARAMETERIZABLE);
124 }
125
126 /*===================================================================
127 * SyntaxPattern object
128 * Repesents a repeatable subpattern
129 * (e.g. x ...), as well as the placeholder of the repeated match
130 * in a template.
131 */
132
133 typedef struct ScmSyntaxPatternRec {
134 SCM_HEADER;
135 ScmObj pattern; /* subpattern */
136 ScmObj vars; /* pattern variables in this subpattern */
137 short level; /* level of this subpattern */
138 short numFollowingItems; /* only used in pattern (not template).
139 this specifies the # of items that follows
140 the repetition, excluding the last CDR.
141
142 E.g. From (x ... y z), `x ...' part becomes
143 SyntaxPattern with numFollowingItems=2.
144 From (x ... . y), `x ...' part becomes
145 SyntaxPattern with numFollowingItems=0. */
146 } ScmSyntaxPattern;
147
148 SCM_CLASS_DECL(Scm_SyntaxPatternClass);
149 #define SCM_CLASS_SYNTAX_PATTERN (&Scm_SyntaxPatternClass)
150
151 #define SCM_SYNTAX_PATTERN(obj) ((ScmSyntaxPattern*)(obj))
152 #define SCM_SYNTAX_PATTERN_P(obj) SCM_XTYPEP(obj, SCM_CLASS_SYNTAX_PATTERN)
153
154 static void pattern_print(ScmObj obj, ScmPort *port,
155 ScmWriteContext *ctx SCM_UNUSED)
156 {
157 Scm_Printf(port, "#<pattern:%d%S %S%s>",
158 SCM_SYNTAX_PATTERN(obj)->level,
159 SCM_SYNTAX_PATTERN(obj)->vars,
160 SCM_SYNTAX_PATTERN(obj)->pattern,
161 SCM_SYNTAX_PATTERN(obj)->numFollowingItems? " ..." : "");
162 }
163
164 SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_SyntaxPatternClass, pattern_print);
165
166 ScmSyntaxPattern *make_syntax_pattern(int level, int numFollowing)
167 {
168 ScmSyntaxPattern *p = SCM_NEW(ScmSyntaxPattern);
169 SCM_SET_CLASS(p, SCM_CLASS_SYNTAX_PATTERN);
170 p->pattern = SCM_NIL;
171 p->vars = SCM_NIL;
172 p->level = level;
173 p->numFollowingItems = numFollowing;
174 return p;
175 }
176
177 /*===================================================================
178 * SyntaxRules object
179 * Internal object to construct pattern matcher
180 */
181
182 static void synrule_print(ScmObj obj, ScmPort *port,
183 ScmWriteContext *mode SCM_UNUSED)
184 {
185 ScmSyntaxRules *r = SCM_SYNTAX_RULES(obj);
186
187 Scm_Printf(port, "#<syntax-rules(%d)\n", r->numRules);
188 for (int i = 0; i < r->numRules; i++) {
189 Scm_Printf(port, "%2d: (numPvars=%d, maxLevel=%d)\n",
190 i, r->rules[i].numPvars, r->rules[i].maxLevel);
191 Scm_Printf(port, " pattern = %S\n", r->rules[i].pattern);
192 Scm_Printf(port, " template = %S\n", r->rules[i].template);
193 }
194 Scm_Printf(port, ">");
195 }
196
197 SCM_DEFINE_BUILTIN_CLASS_SIMPLE(Scm_SyntaxRulesClass, synrule_print);
198
199 ScmSyntaxRules *make_syntax_rules(int nr)
200 {
201 ScmSyntaxRules *r = SCM_NEW2(ScmSyntaxRules *,
202 sizeof(ScmSyntaxRules)+(nr-1)*sizeof(ScmSyntaxRuleBranch));
203 SCM_SET_CLASS(r, SCM_CLASS_SYNTAX_RULES);
204 r->numRules = nr;
205 return r;
206 }
207
208 /*===================================================================
209 * Traditional Macro
210 */
211
212 static ScmMacro *resolve_macro_autoload(ScmAutoload *adata)
213 {
214 ScmObj mac = Scm_ResolveAutoload(adata, 0);
215 if (SCM_UNBOUNDP(mac)) {
216 Scm_Error("tried to autoload macro %S, but it caused circular autoload.", adata->name);
217 }
218 if (!SCM_MACROP(mac)) {
219 Scm_Error("tried to autoload macro %S, but it yields non-macro object: %S", adata->name, mac);
220 }
221 return SCM_MACRO(mac);
222 }
223
224 static ScmObj macro_autoload(ScmObj *argv, int argc, void *data)
225 {
226 SCM_ASSERT(argc == 2);
227 ScmObj form = argv[0];
228 ScmObj env = argv[1];
229 /* Important to save form and env before calling resolve_macro_autoload,
230 for it may overwrite stack region pointed by argv. */
231 SCM_ASSERT(SCM_AUTOLOADP(data));
232 ScmMacro *mac = resolve_macro_autoload(SCM_AUTOLOAD(data));
233 return Scm_CallMacroExpander(mac, form, env);
234 }
235
236 #define AUTOLOAD_MACRO_SUFFIX " (autoload)"
237
238 ScmObj Scm_MakeMacroAutoload(ScmSymbol *name, ScmAutoload *adata)
239 {
240 ScmObj transformer = Scm_MakeSubr(macro_autoload, adata,
241 2, 0, SCM_FALSE);
242 ScmObj name1 = Scm_StringAppendC(SCM_SYMBOL_NAME(name),
243 AUTOLOAD_MACRO_SUFFIX,
244 sizeof(AUTOLOAD_MACRO_SUFFIX)-1,
245 sizeof(AUTOLOAD_MACRO_SUFFIX)-1);
246 return Scm_MakeMacro(Scm_MakeSymbol(SCM_STRING(name1), FALSE),
247 transformer, SCM_NIL, 0);
248 }
249
250 /*===================================================================
251 * R5RS Macro
252 */
253
254 /* Keeping hygienic reference
255 *
256 * - symbols which a template inserts into the expanded form are
257 * converted to identifiers at the macro definition time, encapsulating
258 * the defining environment of the macro. So it doesn't interfere
259 * with the macro call environment.
260 *
261 * - literal symbols provided to the syntax-rules are also converted
262 * to identifiers encapsulating the defining environment, and the
263 * environment information is used when comparing with the symbols
264 * in the macro call.
265 *
266 * - symbols in the macro call is treated as they are. Since the result
267 * of macro expansion is immediately compiled in the macro call
268 * environment, those symbols can refer proper bindings.
269 */
270
271 /*-------------------------------------------------------------------
272 * pattern language compiler
273 * - recognize repeatable subpatterns and replace it to SyntaxPattern node.
274 * - convert free symbols in the template into identifiers
275 * - convert pattern variables into LREF object.
276 */
277 /* TODO: avoid unnecessary consing as much as possible */
278
279 /* context of pattern traversal */
280 typedef struct {
281 ScmObj name; /* name of this macro (for error msg)*/
282 ScmObj form; /* form being compiled (for error msg) */
283 ScmObj literals; /* list of literals */
284 ScmObj pvars; /* list of (pvar . pvref) */
285 ScmObj renames; /* list of (var . identifier) Keep mapping
286 of input symbol/identifier to fresh
287 identifier */
288 ScmObj ellipsis; /* symbol/identifier/keyword for ellipsis
289 SCM_TRUE means default (...)
290 SCM_FALSE means disabled */
291 int pvcnt; /* counter of pattern variables */
292 int maxlev; /* maximum level */
293 ScmModule *mod; /* module where this macro is defined */
294 ScmObj env; /* compiler env of this macro definition */
295 } PatternContext;
296
297 #define PVREF_P(pvref) SCM_PVREF_P(pvref)
298 #define PVREF_LEVEL(pvref) (int)SCM_PVREF_LEVEL(pvref)
299 #define PVREF_COUNT(pvref) (int)SCM_PVREF_COUNT(pvref)
300
301 #define PVREF_LEVEL_MAX 0xff
302 #define PVREF_COUNT_MAX 0xff
303
304 /* add pattern variable pvar. called when compiling a pattern */
305 static inline ScmObj add_pvar(PatternContext *ctx,
306 ScmSyntaxPattern *pat,
307 ScmObj pvar)
308 {
309 if (pat->level > PVREF_LEVEL_MAX) {
310 Scm_Error("Pattern levels too deeply nested in the macro definition of %S", ctx->name);
311 }
312 if (ctx->pvcnt > PVREF_COUNT_MAX) {
313 Scm_Error("Too many pattern variables in the macro definition of %S", ctx->name);
314 }
315 ScmObj pvref = SCM_MAKE_PVREF(pat->level, ctx->pvcnt);
316 if (!SCM_FALSEP(Scm_Assq(pvar, ctx->pvars))) {
317 Scm_Error("Pattern variable %S appears more than once in the macro definition of %S: %S",
318 pvar, ctx->name, ctx->form);
319 }
320 ctx->pvcnt++;
321 ctx->pvars = Scm_Acons(pvar, pvref, ctx->pvars);
322 pat->vars = Scm_Cons(pvref, pat->vars);
323 return pvref;
324 }
325
326 /* Like SCM_APPEND1 and SCM_APPEND, but try to preserve source info
327 of the input. SOURCE is the macro source in its definition, ORIGIN is
328 the macro expansion input in its entirety. ORIGIN is #f while compiling
329 a macro; only given when expanding it.
330 */
331 static ScmObj get_source_info_attrs(ScmObj source, ScmObj origin)
332 {
333 ScmObj attrs = SCM_NIL;
334 if (SCM_PAIRP(source)) {
335 ScmObj info = Scm_PairAttrGet(SCM_PAIR(source),
336 SCM_SYM_SOURCE_INFO, SCM_FALSE);
337 if (SCM_PAIRP(info))
338 attrs = Scm_Acons(SCM_SYM_SOURCE_INFO, info, attrs);
339 }
340 if (SCM_PAIRP(origin)) {
341 attrs = Scm_Acons(SCM_SYM_ORIGINAL, origin, attrs);
342 }
343 return attrs;
344 }
345
346
347 static void template_append1(ScmObj *head, ScmObj *tail,
348 ScmObj elt, ScmObj source, ScmObj origin)
349 {
350 if (SCM_NULLP(*head)) {
351 ScmObj attrs = get_source_info_attrs(source, origin);
352 if (SCM_PAIRP(attrs)) {
353 ScmObj p = Scm_MakeExtendedPair(elt, SCM_NIL, attrs);
354 *head = *tail = p;
355 return;
356 }
357 *head = *tail = Scm_Cons(elt, SCM_NIL);
358 return;
359 }
360 ScmObj p = Scm_Cons(elt, SCM_NIL);
361 SCM_SET_CDR(*tail, p);
362 *tail = p;
363 }
364
365 static void template_append(ScmObj *head, ScmObj *tail,
366 ScmObj rest, ScmObj source, ScmObj origin)
367 {
368 if (SCM_NULLP(*head)) {
369 if (SCM_PAIRP(rest)) {
370 ScmObj attrs = get_source_info_attrs(source, origin);
371 if (SCM_PAIRP(attrs)) {
372 ScmObj p = Scm_MakeExtendedPair(SCM_CAR(rest), SCM_CDR(rest),
373 attrs);
374 *head = p;
375 *tail = Scm_LastPair(p);
376 return;
377 }
378 }
379 *head = rest;
380 *tail = SCM_PAIRP(rest)? Scm_LastPair(rest) : rest;
381 return;
382 }
383 SCM_SET_CDR(*tail, rest);
384 /* rest can be () */
385 if (SCM_PAIRP(rest)) *tail = Scm_LastPair(rest);
386 }
387
388
389 /* returns pvref corresponds to the given pvar in template compilation.
390 if pvar is not a valid pvar, returns pvar itself. */
391 static inline ScmObj pvar_to_pvref(PatternContext *ctx,
392 ScmSyntaxPattern *pat,
393 ScmObj pvar)
394 {
395 ScmObj q = Scm_Assq(pvar, ctx->pvars);
396 if (!SCM_PAIRP(q)) return pvar;
397 ScmObj pvref = SCM_CDR(q);
398 if (PVREF_LEVEL(pvref) > pat->level) {
399 Scm_Error("%S: Pattern variable %S is used in wrong level: %S",
400 ctx->name, pvar, ctx->form);
401 }
402 return pvref;
403 }
404
405 static int isEllipsis(PatternContext *ctx, ScmObj obj)
406 {
407 if (SCM_FALSEP(ctx->ellipsis)) return FALSE; /* inside (... TEMPLATE) */
408 if (SCM_TRUEP(ctx->ellipsis)) {
409 /* default ellipsis (...) */
410 return Scm__ERCompare(SCM_SYM_ELLIPSIS, obj, ctx->mod, ctx->env);
411 } else {
412 /* specified ellipsis */
413 return SCM_EQ(ctx->ellipsis, obj);
414 }
415 }
416
417 #define ELLIPSIS_FOLLOWING(Pat, Ctx) \
418 (SCM_PAIRP(SCM_CDR(Pat)) && isEllipsis(Ctx, SCM_CADR(Pat)))
419
420 #define BAD_ELLIPSIS(Ctx) \
421 Scm_Error("Bad ellipsis usage in macro definition of %S: %S", \
422 Ctx->name, Ctx->form)
423
424 static ScmObj check_literals(ScmObj literals)
425 {
426 ScmObj lp, h = SCM_NIL, t = SCM_NIL;
427 SCM_FOR_EACH(lp, literals) {
428 ScmObj lit = SCM_CAR(lp);
429 if (SCM_SYMBOLP(lit) || SCM_IDENTIFIERP(lit))
430 SCM_APPEND1(h, t, lit);
431 else if (SCM_KEYWORDP(lit))
432 /* This branch is to allow r7rs-compliant code to go through
433 with legacy mode. If keyword-symbol integration is turned on,
434 we never reach here. */;
435 else Scm_Error("literal list contains non-symbol: %S", literals);
436 }
437 if (!SCM_NULLP(lp))
438 Scm_Error("bad literal list in syntax-rules: %S", literals);
439 return h;
440 }
441
442 /* Renaming: Map input variable (symbol or identifier) to fresh identifier.
443 The same (eq?) variable must map to the same identifier. */
444 static ScmObj rename_variable(ScmObj var,
445 ScmObj *id_alist, /* ((var . id) ...) */
446 ScmModule *mod,
447 ScmObj env)
448 {
449 ScmObj id, p = Scm_Assq(var, *id_alist);
450 if (SCM_PAIRP(p)) return SCM_CDR(p);
451 if (SCM_SYMBOLP(var)) {
452 id = Scm_MakeIdentifier(var, mod, env);
453 } else {
454 SCM_ASSERT(SCM_IDENTIFIERP(var));
455 id = Scm_WrapIdentifier(SCM_IDENTIFIER(var));
456 }
457 *id_alist = Scm_Acons(var, id, *id_alist);
458 return id;
459 }
460
461
462 /* Compile a pattern or a template.
463 In the pattern, we replace variables to identifiers.
464 We also recognize pattern variables, and replace them for PVARs in
465 the pattern, and for PVREFs in the template.
466 When encounters a repeatable subpattern, replace it with
467 SyntaxPattern node.
468 */
469 static ScmObj compile_rule1(ScmObj form,
470 ScmSyntaxPattern *spat,
471 PatternContext *ctx,
472 int patternp)
473 {
474 if (SCM_PAIRP(form)) {
475 ScmObj h = SCM_NIL, t = SCM_NIL;
476 int ellipsis_seen = FALSE;
477
478 if (SCM_PAIRP(SCM_CDR(form)) && isEllipsis(ctx, SCM_CAR(form))) {
479 /* (... <template>) */
480 if (patternp) {
481 Scm_Error("in definition of macro %S: "
482 "<ellipsis> can't appear at the beginning of "
483 "list/vector: %S", ctx->name, form);
484 }
485 ScmObj save_elli = ctx->ellipsis, r;
486 ctx->ellipsis = SCM_FALSE;
487 r = compile_rule1(SCM_CADR(form), spat, ctx, FALSE);
488 ctx->ellipsis = save_elli;
489 return r;
490 }
491
492 ScmObj pp;
493 SCM_FOR_EACH(pp, form) {
494 if (ELLIPSIS_FOLLOWING(pp, ctx)) {
495 if (patternp && ellipsis_seen) {
496 Scm_Error("in definition of macro %S: "
497 "Ellipses are not allowed to appear "
498 "within the same list/vector more than once "
499 "in a pattern: %S", ctx->name, form);
500 }
501 ellipsis_seen = TRUE;
502
503 ScmObj base = SCM_CAR(pp);
504 pp = SCM_CDR(pp);
505
506 int num_trailing = 0;
507 int ellipsis_nesting = 1;
508 if (patternp) {
509 /* Count trailing items to set ScmSyntaxPattern->repeat. */
510 ScmObj trailing = SCM_CDR(pp);
511 while (SCM_PAIRP(trailing)) {
512 num_trailing++;
513 trailing = SCM_CDR(trailing);
514 }
515 } else {
516 /* srfi-149 allows more than one ellipsis to follow a
517 template. */
518 while (ELLIPSIS_FOLLOWING(pp, ctx)) {
519 ellipsis_nesting++;
520 if (!SCM_PAIRP(SCM_CDR(pp))) break;
521 pp = SCM_CDR(pp);
522 }
523 }
524 /* at this point, pp points the last ellipsis */
525
526 if (ctx->maxlev < spat->level + ellipsis_nesting)
527 ctx->maxlev = spat->level + ellipsis_nesting + 1;
528
529 ScmSyntaxPattern *outermost =
530 make_syntax_pattern(spat->level+1, num_trailing);
531 ScmSyntaxPattern *outer = outermost;
532 for (int i=1; i<ellipsis_nesting; i++) {
533 ScmSyntaxPattern *inner =
534 make_syntax_pattern(spat->level+i+1, 0);
535 outer->pattern = SCM_OBJ(inner);
536 outer = inner;
537 }
538 outer->pattern = compile_rule1(base, outer, ctx, patternp);
539 outermost->vars = outer->vars;
540 template_append1(&h, &t, SCM_OBJ(outermost), form, SCM_FALSE);
541 if (!patternp) {
542 ScmObj vp;
543 if (SCM_NULLP(outermost->vars)) {
544 Scm_Error("in definition of macro %S: "
545 "a template contains repetition "
546 "of constant form: %S",
547 ctx->name, form);
548 }
549 SCM_FOR_EACH(vp, outermost->vars) {
550 if (PVREF_LEVEL(SCM_CAR(vp)) >= outermost->level) break;
551 }
552 if (SCM_NULLP(vp)) {
553 Scm_Error("in definition of macro %S: "
554 "template's ellipsis nesting"
555 " is deeper than pattern's: %S",
556 ctx->name, form);
557 }
558 }
559 spat->vars = Scm_Append2(spat->vars, outermost->vars);
560 } else {
561 template_append1(&h, &t,
562 compile_rule1(SCM_CAR(pp), spat, ctx, patternp),
563 form, SCM_FALSE);
564 }
565 }
566 if (!SCM_NULLP(pp))
567 template_append(&h, &t, compile_rule1(pp, spat, ctx, patternp),
568 form, SCM_FALSE);
569 return h;
570 }
571 else if (SCM_VECTORP(form)) {
572 /* TODO: this is a sloppy implementation.
573 Eliminate intermediate list structure! */
574 ScmObj l = Scm_VectorToList(SCM_VECTOR(form), 0, -1);
575 return Scm_ListToVector(compile_rule1(l, spat, ctx, patternp), 0, -1);
576 }
577 if (SCM_SYMBOLP(form)||SCM_IDENTIFIERP(form)) {
578 if (isEllipsis(ctx, form)) BAD_ELLIPSIS(ctx);
579 if (!SCM_FALSEP(Scm_Memq(form, ctx->literals))) {
580 if (patternp)
581 return rename_variable(form, &ctx->renames, ctx->mod, ctx->env);
582 else
583 return form; /* template renaming is done in expansion time */
584 }
585 if (patternp && Scm__ERCompare(form, SCM_SYM_UNDERBAR,
586 ctx->mod, ctx->env)) {
587 return SCM_SYM_UNDERBAR;
588 }
589 if (patternp) {
590 return add_pvar(ctx, spat, form);
591 } else {
592 ScmObj pvref = pvar_to_pvref(ctx, spat, form);
593 if (pvref == form) {
594 return form;
595 } else {
596 spat->vars = Scm_Cons(pvref, spat->vars);
597 return pvref;
598 }
599 }
600 }
601 return form;
602 }
603
604 /* compile rules into ScmSyntaxRules structure
605 NB: We use ScmSyntaxPattern for the toplevel node of pattern and template;
606 they are just a placeholders and they don't represent repetition. */
607 static ScmSyntaxRules *compile_rules(ScmObj name,
608 ScmObj ellipsis,
609 ScmObj literals,
610 ScmObj rules,
611 ScmModule *mod,
612 ScmObj env) /* compiler env */
613 {
614 PatternContext ctx;
615 int numRules = Scm_Length(rules);
616
617 if (numRules < 0) goto badform;
618 if (Scm_Length(literals) < 0) goto badform;
619
620 ctx.name = name;
621 ctx.ellipsis = ellipsis;
622 ctx.literals = check_literals(literals);
623 ctx.mod = mod;
624 ctx.env = env;
625 ctx.renames = SCM_NIL;
626
627 /* Corner case when literal contains the same (free-identifer=?) symbol
628 as ellipsis. R7RS specifies the literal has precedence.
629 https://srfi-email.schemers.org/srfi-148/msg/6115633 */
630 if (!SCM_FALSEP(ellipsis)) {
631 ScmObj cp;
632 SCM_FOR_EACH(cp, ctx.literals) {
633 if (isEllipsis(&ctx, SCM_CAR(cp))) {
634 ctx.ellipsis = SCM_FALSE;
635 break;
636 }
637 }
638 }
639
640 ScmSyntaxRules *sr = make_syntax_rules(numRules);
641 sr->name = name;
642 sr->numRules = numRules;
643 sr->maxNumPvars = 0;
644 sr->mod = mod;
645 sr->env = env;
646 ScmObj rp = rules;
647 for (int i=0; i < numRules; i++, rp = SCM_CDR(rp)) {
648 ScmObj rule = SCM_CAR(rp);
649 if (Scm_Length(rule) != 2) goto badform;
650
651 ScmSyntaxPattern *pat = make_syntax_pattern(0, 0);
652 ScmSyntaxPattern *tmpl = make_syntax_pattern(0, 0);
653 ctx.pvars = SCM_NIL;
654 ctx.pvcnt = 0;
655 ctx.maxlev = 0;
656
657 ctx.form = SCM_CAR(rule);
658 if (SCM_PAIRP(ctx.form)) {
659 pat->pattern = compile_rule1(SCM_CDR(ctx.form), pat, &ctx, TRUE);
660 } else {
661 if (!SCM_SYMBOLP(ctx.form) && !SCM_IDENTIFIERP(ctx.form)) goto badform;
662 /* This happens for identifier macro. we allow the entire input.
663 The entire input always match. The identifier in the pattern
664 doesn't matter; we use underscore for placeholder.*/
665 pat->pattern = SCM_SYM_UNDERBAR;
666 }
667
668 ctx.form = SCM_CADR(rule);
669 tmpl->pattern = compile_rule1(ctx.form, tmpl, &ctx, FALSE);
670
671 sr->rules[i].pattern = SCM_OBJ(pat->pattern);
672 sr->rules[i].template = SCM_OBJ(tmpl->pattern);
673 sr->rules[i].numPvars = ctx.pvcnt;
674 sr->rules[i].maxLevel = ctx.maxlev;
675 if (ctx.pvcnt > sr->maxNumPvars) sr->maxNumPvars = ctx.pvcnt;
676 }
677 return sr;
678
679 badform:
680 Scm_Error("malformed macro %S: %S", name,
681 Scm_Cons(SCM_SYM_SYNTAX_RULES, Scm_Cons(literals, rules)));
682 return NULL; /* dummy */
683 }
684
685 /*-------------------------------------------------------------------
686 * pattern language matcher
687 */
688
689 /* Matchvec
690 * A sort of shallow binding technique is used to bind pattern
691 * variables with matched patterns.
692 *
693 * Matchlist itself is an assoc list whose key is a pattern variable.
694 * It's value is a tree of the same depth of the pattern variable.
695 *
696 * Suppose you have a pattern
697 * (?a (?b (?c ?d ...) ...) ...)
698 * In it, pattern variable ?a is level 0, ?b is 1, ?c is 2 and ?d is 3.
699 * When the pattern matches the following form:
700 * (1 (2 (3 4 5) (6)) (7 (8 9) (10 11 12)))
701 * trees bound to each pattern variables are like this:
702 *
703 * ?a => 1
704 * ?b => (2 7)
705 * ?c => ((3 6) (8 10))
706 * ?d => (((4 5) ()) ((9) (11 12)))
707 */
708
709 typedef struct {
710 ScmObj branch; /* current level match */
711 ScmObj sprout; /* current sprout */
712 ScmObj root; /* root of the tree */
713 } MatchVar;
714
715 static MatchVar *alloc_matchvec(int numPvars)
716 {
717 return SCM_NEW_ARRAY(MatchVar, numPvars);
718 }
719
720 static void init_matchvec(MatchVar *mvec, int numPvars)
721 {
722 int i;
723 for (i=0; i<numPvars; i++) {
724 mvec[i].branch = mvec[i].sprout = mvec[i].root = SCM_NIL;
725 }
726 }
727
728 /* get value associated to the pvref. if exhausted, return SCM_UNBOUND
729 and set exhaust level in *exlev. */
730 static ScmObj get_pvref_value(ScmObj pvref, MatchVar *mvec,
731 int *indices, int *exlev)
732 {
733 int level = PVREF_LEVEL(pvref), count = PVREF_COUNT(pvref);
734 ScmObj tree = mvec[count].root;
735 for (int i=1; i<=level; i++) {
736 for (int j=0; j<indices[i]; j++) {
737 if (!SCM_PAIRP(tree)) {
738 *exlev = i;
739 return SCM_UNBOUND;
740 }
741 tree = SCM_CDR(tree);
742 }
743 if (!SCM_PAIRP(tree)) {
744 *exlev = i;
745 return SCM_UNBOUND;
746 }
747 tree = SCM_CAR(tree);
748 }
749 return tree;
750 }
751
752 /* for debug */
753 #ifdef DEBUG_SYNRULE
754 static void print_matchvec(MatchVar *mvec, int numPvars, ScmPort *port)
755 {
756 for (int i=0; i<numPvars; i++) {
757 Scm_Printf(port, "[%S %S %S]\n",
758 mvec[i].branch, mvec[i].sprout, mvec[i].root);
759 }
760 }
761 #endif
762
763 static int match_synrule(ScmObj form, ScmObj pattern, ScmObj mod, ScmObj env,
764 MatchVar *mvec);
765
766 #define SPROUT Scm_Cons(SCM_NIL, SCM_NIL)
767
768 /* add a new "sprout" to the given tree at the given level. */
769 static void grow_branch(MatchVar *rec, int level)
770 {
771 if (level <= 1) return;
772 if (rec->root == SCM_NIL) {
773 rec->sprout = rec->root = SPROUT;
774 if (level == 2) return;
775 }
776
777 ScmObj trunc = rec->root;
778 for (int i=1; i<level-1; i++, trunc = SCM_CAR(trunc)) {
779 SCM_FOR_EACH(trunc, trunc) {
780 if (SCM_NULLP(SCM_CDR(trunc))) break;
781 }
782 if (SCM_NULLP(SCM_CAR(trunc))) {
783 for (i++; i<level-1; i++, trunc = SCM_CAR(trunc)) {
784 SCM_SET_CAR_UNCHECKED(trunc, SPROUT);
785 }
786 rec->sprout = SPROUT;
787 SCM_SET_CAR_UNCHECKED(trunc, rec->sprout);
788 return;
789 }
790 }
791 SCM_FOR_EACH(trunc, trunc) {
792 if (SCM_NULLP(SCM_CDR(trunc))) {
793 rec->sprout = SPROUT;
794 SCM_SET_CDR_UNCHECKED(trunc, rec->sprout);
795 break;
796 }
797 }
798 }
799
800 static void enter_subpattern(ScmSyntaxPattern *subpat, MatchVar *mvec)
801 {
802 ScmObj pp;
803 SCM_FOR_EACH(pp, subpat->vars) {
804 ScmObj pvref = SCM_CAR(pp);
805 int count = PVREF_COUNT(pvref);
806 grow_branch(mvec+count, subpat->level);
807 }
808 }
809
810 static void exit_subpattern(ScmSyntaxPattern *subpat, MatchVar *mvec)
811 {
812 ScmObj pp;
813 SCM_FOR_EACH(pp, subpat->vars) {
814 ScmObj pvref = SCM_CAR(pp);
815 int count = PVREF_COUNT(pvref);
816 if (PVREF_LEVEL(pvref) == subpat->level) {
817 if (subpat->level == 1) {
818 mvec[count].root = Scm_ReverseX(mvec[count].branch);
819 } else {
820 SCM_SET_CAR_UNCHECKED(mvec[count].sprout,
821 Scm_ReverseX(mvec[count].branch));
822 mvec[count].branch = SCM_NIL;
823 }
824 }
825 }
826 }
827
828 /* add pattern variable PVREF and its matched object MATCHED into MVEC */
829 static inline void match_insert(ScmObj pvref, ScmObj matched, MatchVar *mvec)
830 {
831 int count = PVREF_COUNT(pvref);
832 if (PVREF_LEVEL(pvref) == 0) {
833 mvec[count].root = matched;
834 } else {
835 mvec[count].branch = Scm_Cons(matched, mvec[count].branch);
836 }
837 }
838
839 static inline int match_subpattern(ScmObj form, ScmSyntaxPattern *pat,
840 ScmObj rest, ScmObj mod, ScmObj env,
841 MatchVar *mvec)
842 {
843 /* TODO: If pat->numFollowingItems == 0, we don't need to calculate
844 length beforehand. Some optimization opportunity. */
845 int limit = 0;
846 for (ScmObj p = form; SCM_PAIRP(p); p = SCM_CDR(p)) {
847 limit++;
848 }
849 limit -= pat->numFollowingItems;
850
851 enter_subpattern(pat, mvec);
852 while (limit > 0) {
853 if (!match_synrule(SCM_CAR(form), pat->pattern, mod, env, mvec))
854 return FALSE;
855 form = SCM_CDR(form);
856 limit--;
857 }
858 exit_subpattern(pat, mvec);
859 return match_synrule(form, rest, mod, env, mvec);
860 }
861
862 /* See if form matches pattern. If match, add matched syntax variable
863 bindings to match vector and return TRUE; otherwise, return FALSE
864 */
865 static int match_synrule(ScmObj form, ScmObj pattern, ScmObj mod, ScmObj env,
866 MatchVar *mvec)
867 {
868 if (PVREF_P(pattern)) {
869 match_insert(pattern, form, mvec);
870 return TRUE;
871 }
872 if (SCM_EQ(pattern, SCM_SYM_UNDERBAR)) {
873 return TRUE; /* unconditional match */
874 }
875 if (SCM_IDENTIFIERP(pattern)) {
876 return Scm__ERCompare(pattern, form, SCM_MODULE(mod), env);
877 }
878 if (SCM_SYNTAX_PATTERN_P(pattern)) {
879 return match_subpattern(form, SCM_SYNTAX_PATTERN(pattern),
880 SCM_NIL, mod, env, mvec);
881 }
882 if (SCM_PAIRP(pattern)) {
883 while (SCM_PAIRP(pattern)) {
884 ScmObj elt = SCM_CAR(pattern);
885 if (SCM_SYNTAX_PATTERN_P(elt)) {
886 return match_subpattern(form, SCM_SYNTAX_PATTERN(elt),
887 SCM_CDR(pattern),
888 mod, env, mvec);
889 } else if (!SCM_PAIRP(form)) {
890 return FALSE;
891 } else {
892 if (!match_synrule(SCM_CAR(form), elt, mod, env, mvec))
893 return FALSE;
894 pattern = SCM_CDR(pattern);
895 form = SCM_CDR(form);
896 }
897 }
898 if (!SCM_NULLP(pattern))
899 return match_synrule(form, pattern, mod, env, mvec);
900 else
901 return SCM_NULLP(form);
902 }
903 if (SCM_VECTORP(pattern)) {
904 if (!SCM_VECTORP(form)) return FALSE;
905 int plen = SCM_VECTOR_SIZE(pattern);
906 int elli = SCM_VECTOR_SIZE(form);
907 int flen = elli;
908 int has_elli = FALSE;
909 if (plen == 0) return (flen == 0);
910 for (int i=0; i < plen; i++) {
911 if (SCM_SYNTAX_PATTERN_P(SCM_VECTOR_ELEMENT(pattern, i))) {
912 has_elli = TRUE;
913 elli = i;
914 break;
915 }
916 }
917 if ((!has_elli && plen!=flen) || (has_elli && plen-1>flen)) return FALSE;
918
919 for (int i=0; i < elli; i++) {
920 if (!match_synrule(SCM_VECTOR_ELEMENT(form, i),
921 SCM_VECTOR_ELEMENT(pattern, i),
922 mod, env, mvec))
923 return FALSE;
924 }
925 if (elli < flen) {
926 ScmObj pat = SCM_VECTOR_ELEMENT(pattern, elli);
927 ScmObj prest = Scm_VectorToList(SCM_VECTOR(pattern), elli+1, plen);
928 ScmObj frest = Scm_VectorToList(SCM_VECTOR(form), elli, flen);
929 return match_subpattern(frest, SCM_SYNTAX_PATTERN(pat),
930 prest, mod, env, mvec);
931 } else {
932 return TRUE;
933 }
934 }
935
936 /* literal */
937 return Scm_EqualP(pattern, form);
938 }
939
940 /*-------------------------------------------------------------------
941 * pattern language transformer
942 */
943
944 /* If a pattern variable is exhausted, SCM_UNBOUND is returned. */
945 static ScmObj realize_template_rec(ScmObj src,
946 ScmSyntaxRules *sr,
947 ScmObj template,
948 MatchVar *mvec,
949 int level,
950 int *indices,
951 ScmObj *idlist,
952 int *exlev)
953 {
954 if (SCM_PAIRP(template)) {
955 ScmObj h = SCM_NIL, t = SCM_NIL;
956 while (SCM_PAIRP(template)) {
957 ScmObj e = SCM_CAR(template);
958 if (SCM_SYNTAX_PATTERN_P(e)) {
959 ScmObj r = realize_template_rec(src, sr, e, mvec, level,
960 indices, idlist, exlev);
961 if (SCM_UNBOUNDP(r)) return r;
962 template_append(&h, &t, r, template, src);
963 } else {
964 ScmObj r = realize_template_rec(src, sr, e, mvec, level,
965 indices, idlist, exlev);
966 if (SCM_UNBOUNDP(r)) return r;
967 template_append1(&h, &t, r, template, src);
968 }
969 template = SCM_CDR(template);
970 }
971 if (!SCM_NULLP(template)) {
972 ScmObj r = realize_template_rec(src, sr, template, mvec, level,
973 indices, idlist, exlev);
974 if (SCM_UNBOUNDP(r)) return r;
975 if (SCM_NULLP(h)) return r; /* (a ... . b) and a ... is empty */
976 template_append(&h, &t, r, template, src);
977 }
978 return h;
979 }
980 if (PVREF_P(template)) {
981 return get_pvref_value(template, mvec, indices, exlev);
982 }
983 if (SCM_SYNTAX_PATTERN_P(template)) {
984 ScmSyntaxPattern *pat = SCM_SYNTAX_PATTERN(template);
985 ScmObj h = SCM_NIL, t = SCM_NIL;
986 indices[level+1] = 0;
987 for (;;) {
988 ScmObj r = realize_template_rec(src, sr, pat->pattern, mvec,
989 level+1, indices, idlist, exlev);
990 if (SCM_UNBOUNDP(r)) return (*exlev < pat->level)? r : h;
991 if (SCM_SYNTAX_PATTERN_P(pat->pattern)) {
992 SCM_APPEND(h, t, r);
993 } else {
994 SCM_APPEND1(h, t, r);
995 }
996 indices[level+1]++;
997 }
998 }
999 if (SCM_VECTORP(template)) {
1000 ScmObj h = SCM_NIL, t = SCM_NIL;
1001 int len = SCM_VECTOR_SIZE(template);
1002 ScmObj *pe = SCM_VECTOR_ELEMENTS(template);
1003
1004 for (int i=0; i<len; i++, pe++) {
1005 if (SCM_SYNTAX_PATTERN_P(*pe)) {
1006 ScmObj r = realize_template_rec(src, sr, *pe, mvec, level,
1007 indices, idlist, exlev);
1008 if (SCM_UNBOUNDP(r)) return r;
1009 SCM_APPEND(h, t, r);
1010 } else {
1011 ScmObj r = realize_template_rec(src, sr, *pe, mvec, level,
1012 indices, idlist, exlev);
1013 if (SCM_UNBOUNDP(r)) return r;
1014 SCM_APPEND1(h, t, r);
1015 }
1016 }
1017 return Scm_ListToVector(h, 0, -1);
1018 }
1019 if (SCM_SYMBOLP(template) || SCM_IDENTIFIERP(template)) {
1020 return rename_variable(template, idlist, sr->mod, sr->env);
1021 }
1022 return template;
1023 }
1024
1025 #define DEFAULT_MAX_LEVEL 10
1026
1027 static ScmObj realize_template(ScmObj src,
1028 ScmSyntaxRules *sr,
1029 ScmSyntaxRuleBranch *branch,
1030 MatchVar *mvec)
1031 {
1032 int index[DEFAULT_MAX_LEVEL], *indices = index;
1033 int exlev = 0;
1034 ScmObj idlist = SCM_NIL;
1035
1036 if (branch->maxLevel > DEFAULT_MAX_LEVEL)
1037 indices = SCM_NEW_ATOMIC2(int*, (branch->maxLevel+1) * sizeof(int));
1038 for (int i=0; i<=branch->maxLevel; i++) indices[i] = 0;
1039 return realize_template_rec(src, sr, branch->template, mvec, 0,
1040 indices, &idlist, &exlev);
1041 }
1042
1043 static ScmObj synrule_expand(ScmObj form, ScmObj mod, ScmObj env, ScmSyntaxRules *sr)
1044 {
1045 MatchVar *mvec = alloc_matchvec(sr->maxNumPvars);
1046
1047 #ifdef DEBUG_SYNRULE
1048 Scm_Printf(SCM_CUROUT, "**** synrule_transform: %S\n", form);
1049 #endif
1050 for (int i=0; i<sr->numRules; i++) {
1051 #ifdef DEBUG_SYNRULE
1052 Scm_Printf(SCM_CUROUT, "pattern #%d: %S\n", i, sr->rules[i].pattern);
1053 #endif
1054 init_matchvec(mvec, sr->rules[i].numPvars);
1055
1056 int matched = FALSE;
1057 if (sr->rules[i].pattern == SCM_SYM_UNDERBAR) {
1058 matched = TRUE; /* unconditionally match */
1059 } else {
1060 matched = match_synrule(SCM_CDR(form), sr->rules[i].pattern, mod, env, mvec);
1061 }
1062 if (matched) {
1063 #ifdef DEBUG_SYNRULE
1064 Scm_Printf(SCM_CUROUT, "success #%d:\n", i);
1065 print_matchvec(mvec, sr->rules[i].numPvars, SCM_CUROUT);
1066 #endif
1067 ScmObj expanded = realize_template(form, sr, &sr->rules[i], mvec);
1068 #ifdef DEBUG_SYNRULE
1069 Scm_Printf(SCM_CUROUT, "result: %S\n", expanded);
1070 #endif
1071 return expanded;
1072 }
1073 }
1074 Scm_Error("malformed %S: %S", SCM_CAR(form), form);
1075 return SCM_NIL;
1076 }
1077
1078 static ScmObj synrule_transform(ScmObj *argv, int argc, void *data)
1079 {
1080 SCM_ASSERT(argc == 2);
1081 ScmObj form = argv[0];
1082 ScmObj cenv = argv[1];
1083 SCM_ASSERT(SCM_VECTORP(cenv));
1084 ScmObj module = SCM_VECTOR_ELEMENT(cenv, 0); /* macro use env */
1085 ScmObj frames = SCM_VECTOR_ELEMENT(cenv, 1); /* macro use env */
1086 ScmSyntaxRules *sr = (ScmSyntaxRules *)data;
1087 return synrule_expand(form, module, frames, sr);
1088 }
1089
1090 /* NB: a stub for the new compiler (TEMPORARY) */
1091 ScmObj Scm_CompileSyntaxRules(ScmObj name, ScmObj src, ScmObj ellipsis,
1092 ScmObj literals, ScmObj rules,
1093 ScmObj mod, ScmObj env)
1094 {
1095 if (SCM_IDENTIFIERP(name)) name = SCM_OBJ(SCM_IDENTIFIER(name)->name);
1096 if (!SCM_MODULEP(mod)) Scm_Error("module required, but got %S", mod);
1097 ScmSyntaxRules *sr = compile_rules(name, ellipsis, literals, rules,
1098 SCM_MODULE(mod), env);
1099 ScmObj sr_xform = Scm_MakeSubr(synrule_transform, sr,
1100 2, 0, SCM_FALSE);
1101
1102 ScmObj info = SCM_NIL, info_tail = SCM_NIL;
1103 if (SCM_PAIRP(src)) {
1104 SCM_APPEND1(info, info_tail, Scm_Cons(SCM_SYM_SOURCE, src));
1105 ScmObj source_info = Scm_PairAttrGet(SCM_PAIR(src),
1106 SCM_SYM_SOURCE_INFO,
1107 SCM_FALSE);
1108 if (SCM_PAIRP(source_info)) {
1109 SCM_APPEND1(info, info_tail,
1110 Scm_Cons(SCM_SYM_SOURCE_INFO, source_info));
1111 }
1112 }
1113
1114 return Scm_MakeMacro(name, sr_xform, info, 0);
1115 }
1116
1117 /*===================================================================
1118 * macro-expand
1119 */
1120
1121 ScmObj Scm_CallMacroExpander(ScmMacro *mac, ScmObj expr, ScmObj cenv)
1122 {
1123 SCM_ASSERT(SCM_VECTORP(cenv));
1124 return Scm_ApplyRec2(mac->transformer, expr, cenv);
1125 }
1126
1127 /*===================================================================
1128 * Initializer
1129 */
1130
1131 void Scm__InitMacro(void)
1132 {
1133 Scm_InitStaticClass(&Scm_SyntaxPatternClass, "<syntax-pattern>",
1134 Scm_GaucheInternalModule(), NULL, 0);
1135 }