pintos-os.org Git - pspp/blob - src/language/lexer/macro.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2021 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18
  19 #include "language/lexer/macro.h"
  20
  21 #include <errno.h>
  22 #include <limits.h>
  23 #include <stdlib.h>
  24
  25 #include "data/settings.h"
  26 #include "language/lexer/segment.h"
  27 #include "language/lexer/scan.h"
  28 #include "libpspp/assertion.h"
  29 #include "libpspp/cast.h"
  30 #include "libpspp/i18n.h"
  31 #include "libpspp/message.h"
  32 #include "libpspp/str.h"
  33 #include "libpspp/string-array.h"
  34
  35 #include "gettext.h"
  36 #define _(msgid) gettext (msgid)
  37
  38 void
  39 macro_token_copy (struct macro_token *dst, const struct macro_token *src)
  40 {
  41   token_copy (&dst->token, &src->token);
  42   ss_alloc_substring (&dst->representation, src->representation);
  43 }
  44
  45 void
  46 macro_token_uninit (struct macro_token *mt)
  47 {
  48   token_uninit (&mt->token);
  49   ss_dealloc (&mt->representation);
  50 }
  51
  52 void
  53 macro_token_to_representation (struct macro_token *mt, struct string *s)
  54 {
  55   ds_put_substring (s, mt->representation);
  56 }
  57
  58 void
  59 macro_tokens_copy (struct macro_tokens *dst, const struct macro_tokens *src)
  60 {
  61   *dst = (struct macro_tokens) {
  62     .mts = xmalloc (src->n * sizeof *dst->mts),
  63     .n = src->n,
  64     .allocated = src->n,
  65   };
  66   for (size_t i = 0; i < src->n; i++)
  67     macro_token_copy (&dst->mts[i], &src->mts[i]);
  68 }
  69
  70 void
  71 macro_tokens_uninit (struct macro_tokens *mts)
  72 {
  73   for (size_t i = 0; i < mts->n; i++)
  74     macro_token_uninit (&mts->mts[i]);
  75   free (mts->mts);
  76 }
  77
  78 struct macro_token *
  79 macro_tokens_add_uninit (struct macro_tokens *mts)
  80 {
  81   if (mts->n >= mts->allocated)
  82     mts->mts = x2nrealloc (mts->mts, &mts->allocated, sizeof *mts->mts);
  83   return &mts->mts[mts->n++];
  84 }
  85
  86 void
  87 macro_tokens_add (struct macro_tokens *mts, const struct macro_token *mt)
  88 {
  89   macro_token_copy (macro_tokens_add_uninit (mts), mt);
  90 }
  91
  92 void
  93 macro_tokens_from_string (struct macro_tokens *mts, const struct substring src,
  94                           enum segmenter_mode mode)
  95 {
  96   struct state
  97     {
  98       struct segmenter segmenter;
  99       struct substring body;
 100     };
 101
 102   struct state state = {
 103     .segmenter = SEGMENTER_INIT (mode),
 104     .body = src,
 105   };
 106   struct state saved = state;
 107
 108   while (state.body.length > 0)
 109     {
 110       struct macro_token mt = {
 111         .token = { .type = T_STOP },
 112         .representation = { .string = state.body.string },
 113       };
 114       struct token *token = &mt.token;
 115
 116       struct scanner scanner;
 117       scanner_init (&scanner, token);
 118
 119       for (;;)
 120         {
 121           enum segment_type type;
 122           int seg_len = segmenter_push (&state.segmenter, state.body.string,
 123                                         state.body.length, true, &type);
 124           assert (seg_len >= 0);
 125
 126           struct substring segment = ss_head (state.body, seg_len);
 127           ss_advance (&state.body, seg_len);
 128
 129           enum scan_result result = scanner_push (&scanner, type, segment, token);
 130           if (result == SCAN_SAVE)
 131             saved = state;
 132           else if (result == SCAN_BACK)
 133             {
 134               state = saved;
 135               break;
 136             }
 137           else if (result == SCAN_DONE)
 138             break;
 139         }
 140
 141       /* We have a token in 'token'. */
 142       if (is_scan_type (token->type))
 143         {
 144           if (token->type != SCAN_SKIP)
 145             {
 146               printf ("error\n");
 147               /* XXX report error */
 148             }
 149         }
 150       else
 151         {
 152           mt.representation.length = state.body.string - mt.representation.string;
 153           macro_tokens_add (mts, &mt);
 154         }
 155       token_uninit (token);
 156     }
 157 }
 158
 159 void
 160 macro_tokens_print (const struct macro_tokens *mts, FILE *stream)
 161 {
 162   for (size_t i = 0; i < mts->n; i++)
 163     token_print (&mts->mts[i].token, stream);
 164 }
 165
 166 enum token_class
 167   {
 168     TC_ENDCMD,                  /* No space before or after (new-line after). */
 169     TC_BINOP,                   /* Space on both sides. */
 170     TC_COMMA,                   /* Space afterward. */
 171     TC_ID,                      /* Don't need spaces except sequentially. */
 172     TC_PUNCT,                   /* Don't need spaces except sequentially. */
 173   };
 174
 175 static bool
 176 needs_space (enum token_class prev, enum token_class next)
 177 {
 178   /* Don't need a space before or after the end of a command.
 179      (A new-line is needed afterward as a special case.) */
 180   if (prev == TC_ENDCMD || next == TC_ENDCMD)
 181     return false;
 182
 183   /* Binary operators always have a space on both sides. */
 184   if (prev == TC_BINOP || next == TC_BINOP)
 185     return true;
 186
 187   /* A comma always has a space afterward. */
 188   if (prev == TC_COMMA)
 189     return true;
 190
 191   /* Otherwise, PREV is TC_ID or TC_PUNCT, which only need a space if there are
 192      two or them in a row. */
 193   return prev == next;
 194 }
 195
 196 static enum token_class
 197 classify_token (enum token_type type)
 198 {
 199   switch (type)
 200     {
 201     case T_ID:
 202     case T_MACRO_ID:
 203     case T_POS_NUM:
 204     case T_NEG_NUM:
 205     case T_STRING:
 206       return TC_ID;
 207
 208     case T_STOP:
 209       return TC_PUNCT;
 210
 211     case T_ENDCMD:
 212       return TC_ENDCMD;
 213
 214     case T_LPAREN:
 215     case T_RPAREN:
 216     case T_LBRACK:
 217     case T_RBRACK:
 218       return TC_PUNCT;
 219
 220     case T_PLUS:
 221     case T_DASH:
 222     case T_ASTERISK:
 223     case T_SLASH:
 224     case T_EQUALS:
 225     case T_AND:
 226     case T_OR:
 227     case T_NOT:
 228     case T_EQ:
 229     case T_GE:
 230     case T_GT:
 231     case T_LE:
 232     case T_LT:
 233     case T_NE:
 234     case T_ALL:
 235     case T_BY:
 236     case T_TO:
 237     case T_WITH:
 238     case T_EXP:
 239     case T_MACRO_PUNCT:
 240       return TC_BINOP;
 241
 242     case T_COMMA:
 243       return TC_COMMA;
 244     }
 245
 246   NOT_REACHED ();
 247 }
 248
 249 void
 250 macro_tokens_to_representation (struct macro_tokens *mts, struct string *s)
 251 {
 252   if (!mts->n)
 253     return;
 254
 255   macro_token_to_representation (&mts->mts[0], s);
 256   for (size_t i = 1; i < mts->n; i++)
 257     {
 258       enum token_type prev = mts->mts[i - 1].token.type;
 259       enum token_type next = mts->mts[i].token.type;
 260
 261       if (prev == T_ENDCMD)
 262         ds_put_byte (s, '\n');
 263       else
 264         {
 265           enum token_class pc = classify_token (prev);
 266           enum token_class nc = classify_token (next);
 267           if (needs_space (pc, nc))
 268             ds_put_byte (s, ' ');
 269         }
 270
 271       macro_token_to_representation (&mts->mts[i], s);
 272     }
 273 }
 274
 275 void
 276 macro_destroy (struct macro *m)
 277 {
 278   if (!m)
 279     return;
 280
 281   free (m->name);
 282   for (size_t i = 0; i < m->n_params; i++)
 283     {
 284       struct macro_param *p = &m->params[i];
 285       free (p->name);
 286
 287       macro_tokens_uninit (&p->def);
 288
 289       switch (p->arg_type)
 290         {
 291         case ARG_N_TOKENS:
 292           break;
 293
 294         case ARG_CHAREND:
 295           token_uninit (&p->charend);
 296           break;
 297
 298         case ARG_ENCLOSE:
 299           token_uninit (&p->enclose[0]);
 300           token_uninit (&p->enclose[1]);
 301           break;
 302
 303         case ARG_CMDEND:
 304           break;
 305         }
 306     }
 307   free (m->params);
 308   macro_tokens_uninit (&m->body);
 309   free (m);
 310 }
 311 \f
 312 struct macro_set *
 313 macro_set_create (void)
 314 {
 315   struct macro_set *set = xmalloc (sizeof *set);
 316   *set = (struct macro_set) {
 317     .macros = HMAP_INITIALIZER (set->macros),
 318   };
 319   return set;
 320 }
 321
 322 void
 323 macro_set_destroy (struct macro_set *set)
 324 {
 325   if (!set)
 326     return;
 327
 328   struct macro *macro, *next;
 329   HMAP_FOR_EACH_SAFE (macro, next, struct macro, hmap_node, &set->macros)
 330     {
 331       hmap_delete (&set->macros, &macro->hmap_node);
 332       macro_destroy (macro);
 333     }
 334   hmap_destroy (&set->macros);
 335   free (set);
 336 }
 337
 338 static unsigned int
 339 hash_macro_name (const char *name)
 340 {
 341   return utf8_hash_case_string (name, 0);
 342 }
 343
 344 static struct macro *
 345 macro_set_find__ (struct macro_set *set, const char *name)
 346 {
 347   struct macro *macro;
 348   HMAP_FOR_EACH_WITH_HASH (macro, struct macro, hmap_node,
 349                            hash_macro_name (name), &set->macros)
 350     if (!utf8_strcasecmp (macro->name, name))
 351       return macro;
 352
 353   return NULL;
 354 }
 355
 356 const struct macro *
 357 macro_set_find (const struct macro_set *set, const char *name)
 358 {
 359   return macro_set_find__ (CONST_CAST (struct macro_set *, set), name);
 360 }
 361
 362 /* Adds M to SET.  M replaces any existing macro with the same name.  Takes
 363    ownership of M. */
 364 void
 365 macro_set_add (struct macro_set *set, struct macro *m)
 366 {
 367   struct macro *victim = macro_set_find__ (set, m->name);
 368   if (victim)
 369     {
 370       hmap_delete (&set->macros, &victim->hmap_node);
 371       macro_destroy (victim);
 372     }
 373
 374   hmap_insert (&set->macros, &m->hmap_node, hash_macro_name (m->name));
 375 }
 376 \f
 377 enum me_state
 378   {
 379     /* Error state. */
 380     ME_ERROR,
 381
 382     /* Accumulating tokens in me->params toward the end of any type of
 383        argument. */
 384     ME_ARG,
 385
 386     /* Expecting the opening delimiter of an ARG_ENCLOSE argument. */
 387     ME_ENCLOSE,
 388
 389     /* Expecting a keyword for a keyword argument. */
 390     ME_KEYWORD,
 391
 392     /* Expecting an equal sign for a keyword argument. */
 393     ME_EQUALS,
 394   };
 395
 396
 397 struct macro_expander
 398   {
 399     const struct macro_set *macros;
 400
 401     enum me_state state;
 402     size_t n_tokens;
 403
 404     const struct macro *macro;
 405     struct macro_tokens **args;
 406     const struct macro_param *param;
 407   };
 408
 409 static int
 410 me_finished (struct macro_expander *me)
 411 {
 412   for (size_t i = 0; i < me->macro->n_params; i++)
 413     if (!me->args[i])
 414       {
 415         me->args[i] = xmalloc (sizeof *me->args[i]);
 416         macro_tokens_copy (me->args[i], &me->macro->params[i].def);
 417       }
 418   return me->n_tokens;
 419 }
 420
 421 static int
 422 me_next_arg (struct macro_expander *me)
 423 {
 424   if (!me->param)
 425     {
 426       assert (!me->macro->n_params);
 427       return me_finished (me);
 428     }
 429   else if (me->param->positional)
 430     {
 431       me->param++;
 432       if (me->param >= &me->macro->params[me->macro->n_params])
 433         return me_finished (me);
 434       else
 435         {
 436           me->state = (!me->param->positional ? ME_KEYWORD
 437                        : me->param->arg_type == ARG_ENCLOSE ? ME_ENCLOSE
 438                        : ME_ARG);
 439           return 0;
 440         }
 441     }
 442   else
 443     {
 444       for (size_t i = 0; i < me->macro->n_params; i++)
 445         if (!me->args[i])
 446           {
 447             me->state = ME_KEYWORD;
 448             return 0;
 449           }
 450       return me_finished (me);
 451     }
 452 }
 453
 454 static int
 455 me_error (struct macro_expander *me)
 456 {
 457   me->state = ME_ERROR;
 458   return -1;
 459 }
 460
 461 static int
 462 me_add_arg (struct macro_expander *me, const struct macro_token *mt)
 463 {
 464   const struct macro_param *p = me->param;
 465
 466   const struct token *token = &mt->token;
 467   if ((token->type == T_ENDCMD || token->type == T_STOP)
 468       && p->arg_type != ARG_CMDEND)
 469     {
 470       msg (SE, _("Unexpected end of command reading argument %s "
 471                  "to macro %s."), me->param->name, me->macro->name);
 472
 473       return me_error (me);
 474     }
 475
 476   me->n_tokens++;
 477
 478   struct macro_tokens **argp = &me->args[p - me->macro->params];
 479   if (!*argp)
 480     *argp = xzalloc (sizeof **argp);
 481   struct macro_tokens *arg = *argp;
 482   if (p->arg_type == ARG_N_TOKENS)
 483     {
 484       macro_tokens_add (arg, mt);
 485       if (arg->n >= p->n_tokens)
 486         return me_next_arg (me);
 487       return 0;
 488     }
 489   else if (p->arg_type == ARG_CMDEND)
 490     {
 491       if (token->type == T_ENDCMD || token->type == T_STOP)
 492         return me_next_arg (me);
 493       macro_tokens_add (arg, mt);
 494       return 0;
 495     }
 496   else
 497     {
 498       const struct token *end
 499         = p->arg_type == ARG_CHAREND ? &p->charend : &p->enclose[1];
 500       if (token_equal (token, end))
 501         return me_next_arg (me);
 502       macro_tokens_add (arg, mt);
 503       return 0;
 504     }
 505 }
 506
 507 static int
 508 me_expected (struct macro_expander *me, const struct macro_token *actual,
 509              const struct token *expected)
 510 {
 511   const struct substring actual_s
 512     = (actual->representation.length ? actual->representation
 513        : ss_cstr (_("<end of input>")));
 514   char *expected_s = token_to_string (expected);
 515   msg (SE, _("Found `%.*s' while expecting `%s' reading argument %s "
 516              "to macro %s."),
 517        (int) actual_s.length, actual_s.string, expected_s,
 518        me->param->name, me->macro->name);
 519   free (expected_s);
 520
 521   return me_error (me);
 522 }
 523
 524 static int
 525 me_enclose (struct macro_expander *me, const struct macro_token *mt)
 526 {
 527   const struct token *token = &mt->token;
 528   me->n_tokens++;
 529
 530   if (token_equal (&me->param->enclose[0], token))
 531     {
 532       me->state = ME_ARG;
 533       return 0;
 534     }
 535
 536   return me_expected (me, mt, &me->param->enclose[0]);
 537 }
 538
 539 static const struct macro_param *
 540 macro_find_parameter_by_name (const struct macro *m, struct substring name)
 541 {
 542   if (ss_first (name) == '!')
 543     ss_advance (&name, 1);
 544
 545   for (size_t i = 0; i < m->n_params; i++)
 546     {
 547       const struct macro_param *p = &m->params[i];
 548       struct substring p_name = ss_cstr (p->name + 1);
 549       if (!utf8_strncasecmp (p_name.string, p_name.length,
 550                              name.string, name.length))
 551         return p;
 552     }
 553   return NULL;
 554 }
 555
 556 static int
 557 me_keyword (struct macro_expander *me, const struct macro_token *mt)
 558 {
 559   const struct token *token = &mt->token;
 560   if (token->type != T_ID)
 561     return me_finished (me);
 562
 563   const struct macro_param *p = macro_find_parameter_by_name (me->macro,
 564                                                               token->string);
 565   if (p)
 566     {
 567       size_t arg_index = p - me->macro->params;
 568       me->param = p;
 569       if (me->args[arg_index])
 570         {
 571           msg (SE,
 572                _("Argument %s multiply specified in call to macro %s."),
 573                p->name, me->macro->name);
 574           return me_error (me);
 575         }
 576
 577       me->n_tokens++;
 578       me->state = ME_EQUALS;
 579       return 0;
 580     }
 581
 582   return me_finished (me);
 583 }
 584
 585 static int
 586 me_equals (struct macro_expander *me, const struct macro_token *mt)
 587 {
 588   const struct token *token = &mt->token;
 589   me->n_tokens++;
 590
 591   if (token->type == T_EQUALS)
 592     {
 593       me->state = ME_ARG;
 594       return 0;
 595     }
 596
 597   return me_expected (me, mt, &(struct token) { .type = T_EQUALS });
 598 }
 599
 600 int
 601 macro_expander_create (const struct macro_set *macros,
 602                        const struct token *token,
 603                        struct macro_expander **mep)
 604 {
 605   *mep = NULL;
 606   if (macro_set_is_empty (macros))
 607     return -1;
 608   if (token->type != T_ID && token->type != T_MACRO_ID)
 609     return -1;
 610
 611   const struct macro *macro = macro_set_find (macros, token->string.string);
 612   if (!macro)
 613     return -1;
 614
 615   struct macro_expander *me = xmalloc (sizeof *me);
 616   *me = (struct macro_expander) {
 617     .macros = macros,
 618     .n_tokens = 1,
 619     .macro = macro,
 620   };
 621   *mep = me;
 622
 623   if (!macro->n_params)
 624     return 1;
 625   else
 626     {
 627       me->state = (!macro->params[0].positional ? ME_KEYWORD
 628                    : macro->params[0].arg_type == ARG_ENCLOSE ? ME_ENCLOSE
 629                    : ME_ARG);
 630       me->args = xcalloc (macro->n_params, sizeof *me->args);
 631       me->param = macro->params;
 632       return 0;
 633     }
 634 }
 635
 636 void
 637 macro_expander_destroy (struct macro_expander *me)
 638 {
 639   if (!me)
 640     return;
 641
 642   for (size_t i = 0; i < me->macro->n_params; i++)
 643     if (me->args[i])
 644       {
 645         macro_tokens_uninit (me->args[i]);
 646         free (me->args[i]);
 647       }
 648   free (me->args);
 649   free (me);
 650 }
 651
 652 /* Adds TOKEN to the collection of tokens in ME that potentially need to be
 653    macro expanded.
 654
 655    Returns -1 if the tokens added do not actually invoke a macro.  The caller
 656    should consume the first token without expanding it.
 657
 658    Returns 0 if the macro expander needs more tokens, for macro arguments or to
 659    decide whether this is actually a macro invocation.  The caller should call
 660    macro_expander_add() again with the next token.
 661
 662    Returns a positive number to indicate that the returned number of tokens
 663    invoke a macro.  The number returned might be less than the number of tokens
 664    added because it can take a few tokens of lookahead to determine whether the
 665    macro invocation is finished.  The caller should call
 666    macro_expander_get_expansion() to obtain the expansion. */
 667 int
 668 macro_expander_add (struct macro_expander *me, const struct macro_token *mt)
 669 {
 670   switch (me->state)
 671     {
 672     case ME_ERROR:
 673       return -1;
 674
 675     case ME_ARG:
 676       return me_add_arg (me, mt);
 677
 678     case ME_ENCLOSE:
 679       return me_enclose (me, mt);
 680
 681     case ME_KEYWORD:
 682       return me_keyword (me, mt);
 683
 684     case ME_EQUALS:
 685       return me_equals (me, mt);
 686
 687     default:
 688       NOT_REACHED ();
 689     }
 690 }
 691
 692 /* Each argument to a macro function is one of:
 693
 694        - A quoted string or other single literal token.
 695
 696        - An argument to the macro being expanded, e.g. !1 or a named argument.
 697
 698        - !*.
 699
 700        - A function invocation.
 701
 702    Each function invocation yields a character sequence to be turned into a
 703    sequence of tokens.  The case where that character sequence is a single
 704    quoted string is an important special case.
 705 */
 706 struct parse_macro_function_ctx
 707   {
 708     const struct macro_token *input;
 709     size_t n_input;
 710     int nesting_countdown;
 711     const struct macro_set *macros;
 712     const struct macro_expander *me;
 713     bool *expand;
 714   };
 715
 716 static void
 717 macro_expand (const struct macro_tokens *,
 718               int nesting_countdown, const struct macro_set *,
 719               const struct macro_expander *, bool *expand, struct macro_tokens *exp);
 720
 721 static bool
 722 expand_macro_function (struct parse_macro_function_ctx *ctx,
 723                        struct string *output, size_t *input_consumed);
 724
 725 /* Returns true if the pair of tokens starting at offset OFS within MTS are !*,
 726    false otherwise. */
 727 static bool
 728 is_bang_star (const struct macro_token *mts, size_t n, size_t ofs)
 729 {
 730   return (ofs + 1 < n
 731           && mts[ofs].token.type == T_MACRO_ID
 732           && ss_equals (mts[ofs].token.string, ss_cstr ("!"))
 733           && mts[ofs + 1].token.type == T_ASTERISK);
 734 }
 735
 736 static size_t
 737 parse_function_arg (struct parse_macro_function_ctx *ctx,
 738                     size_t i, struct string *farg)
 739 {
 740   const struct macro_token *tokens = ctx->input;
 741   const struct token *token = &tokens[i].token;
 742   if (token->type == T_MACRO_ID)
 743     {
 744       const struct macro_param *param = macro_find_parameter_by_name (
 745         ctx->me->macro, token->string);
 746       if (param)
 747         {
 748           size_t param_idx = param - ctx->me->macro->params;
 749           const struct macro_tokens *marg = ctx->me->args[param_idx];
 750           for (size_t i = 0; i < marg->n; i++)
 751             {
 752               if (i)
 753                 ds_put_byte (farg, ' ');
 754               ds_put_substring (farg, marg->mts[i].representation);
 755             }
 756           return 1;
 757         }
 758
 759       if (is_bang_star (ctx->input, ctx->n_input, i))
 760         {
 761           for (size_t i = 0; i < ctx->me->macro->n_params; i++)
 762             {
 763               if (!ctx->me->macro->params[i].positional)
 764                 break;
 765
 766               const struct macro_tokens *marg = ctx->me->args[i];
 767               for (size_t j = 0; j < marg->n; j++)
 768                 {
 769                   if (i || j)
 770                     ds_put_byte (farg, ' ');
 771                   ds_put_substring (farg, marg->mts[j].representation);
 772                 }
 773             }
 774           return 2;
 775         }
 776
 777       struct parse_macro_function_ctx subctx = {
 778         .input = &ctx->input[i],
 779         .n_input = ctx->n_input - i,
 780         .nesting_countdown = ctx->nesting_countdown,
 781         .macros = ctx->macros,
 782         .me = ctx->me,
 783         .expand = ctx->expand,
 784       };
 785       size_t subinput_consumed;
 786       if (expand_macro_function (&subctx, farg, &subinput_consumed))
 787         return subinput_consumed;
 788     }
 789
 790   ds_put_substring (farg, tokens[i].representation);
 791   return 1;
 792 }
 793
 794 static bool
 795 parse_macro_function (struct parse_macro_function_ctx *ctx,
 796                       struct string_array *args,
 797                       struct substring function,
 798                       int min_args, int max_args,
 799                       size_t *input_consumed)
 800 {
 801   const struct macro_token *tokens = ctx->input;
 802   size_t n_tokens = ctx->n_input;
 803
 804   if (!n_tokens
 805       || tokens[0].token.type != T_MACRO_ID
 806       || !ss_equals_case (tokens[0].token.string, function))
 807     return false;
 808
 809   if (n_tokens < 2 || tokens[1].token.type != T_LPAREN)
 810     {
 811       printf ("`(' expected following %s'\n", function.string);
 812       return false;
 813     }
 814
 815   string_array_init (args);
 816
 817   for (size_t i = 2;; )
 818     {
 819       if (i >= n_tokens)
 820         goto unexpected_end;
 821       if (tokens[i].token.type == T_RPAREN)
 822         {
 823           *input_consumed = i + 1;
 824           if (args->n < min_args || args->n > max_args)
 825             {
 826               printf ("Wrong number of arguments to %s.\n", function.string);
 827               goto error;
 828             }
 829           return true;
 830         }
 831
 832       struct string s = DS_EMPTY_INITIALIZER;
 833       i += parse_function_arg (ctx, i, &s);
 834       if (i >= n_tokens)
 835         {
 836           ds_destroy (&s);
 837           goto unexpected_end;
 838         }
 839       string_array_append_nocopy (args, ds_steal_cstr (&s));
 840
 841       if (tokens[i].token.type == T_COMMA)
 842         i++;
 843       else if (tokens[i].token.type != T_RPAREN)
 844         {
 845           printf ("Expecting `,' or `)' in %s invocation.", function.string);
 846           goto error;
 847         }
 848     }
 849
 850 unexpected_end:
 851   printf ("Missing closing parenthesis in arguments to %s.\n",
 852           function.string);
 853   /* Fall through. */
 854 error:
 855   string_array_destroy (args);
 856   return false;
 857 }
 858
 859 static bool
 860 unquote_string (const char *s, struct string *content)
 861 {
 862   struct string_lexer slex;
 863   string_lexer_init (&slex, s, strlen (s), SEG_MODE_INTERACTIVE /* XXX */);
 864
 865   struct token token1;
 866   if (!string_lexer_next (&slex, &token1))
 867     return false;
 868
 869   if (token1.type != T_STRING)
 870     {
 871       token_uninit (&token1);
 872       return false;
 873     }
 874
 875   struct token token2;
 876   if (string_lexer_next (&slex, &token2))
 877     {
 878       token_uninit (&token1);
 879       token_uninit (&token2);
 880       return false;
 881     }
 882
 883   ds_put_substring (content, token1.string);
 884   token_uninit (&token1);
 885   return true;
 886 }
 887
 888 static const char *
 889 unquote_string_in_place (const char *s, struct string *tmp)
 890 {
 891   ds_init_empty (tmp);
 892   return unquote_string (s, tmp) ? ds_cstr (tmp) : s;
 893 }
 894
 895 static bool
 896 parse_integer (const char *s, int *np)
 897 {
 898   errno = 0;
 899
 900   char *tail;
 901   long int n = strtol (s, &tail, 10);
 902   *np = n < INT_MIN ? INT_MIN : n > INT_MAX ? INT_MAX : n;
 903   tail += strspn (tail, CC_SPACES);
 904   return *tail == '\0' && errno != ERANGE && n == *np;
 905 }
 906
 907 static bool
 908 expand_macro_function (struct parse_macro_function_ctx *ctx,
 909                        struct string *output,
 910                        size_t *input_consumed)
 911 {
 912   struct string_array args;
 913
 914   if (parse_macro_function (ctx, &args, ss_cstr ("!length"), 1, 1,
 915                             input_consumed))
 916     ds_put_format (output, "%zu", strlen (args.strings[0]));
 917   else if (parse_macro_function (ctx, &args, ss_cstr ("!blanks"), 1, 1,
 918                                  input_consumed))
 919     {
 920       int n;
 921       if (!parse_integer (args.strings[0], &n))
 922         {
 923           printf ("argument to !BLANKS must be non-negative integer (not \"%s\")\n", args.strings[0]);
 924           string_array_destroy (&args);
 925           return false;
 926         }
 927
 928       ds_put_byte_multiple (output, ' ', n);
 929     }
 930   else if (parse_macro_function (ctx, &args, ss_cstr ("!concat"), 1, INT_MAX,
 931                                  input_consumed))
 932     {
 933       for (size_t i = 0; i < args.n; i++)
 934         if (!unquote_string (args.strings[i], output))
 935           ds_put_cstr (output, args.strings[i]);
 936     }
 937   else if (parse_macro_function (ctx, &args, ss_cstr ("!head"), 1, 1,
 938                                  input_consumed))
 939     {
 940       struct string tmp;
 941       const char *s = unquote_string_in_place (args.strings[0], &tmp);
 942
 943       struct macro_tokens mts = { .n = 0 };
 944       macro_tokens_from_string (&mts, ss_cstr (s), SEG_MODE_INTERACTIVE /* XXX */);
 945       if (mts.n > 0)
 946         ds_put_substring (output, mts.mts[0].representation);
 947       macro_tokens_uninit (&mts);
 948       ds_destroy (&tmp);
 949     }
 950   else if (parse_macro_function (ctx, &args, ss_cstr ("!index"), 2, 2,
 951                                  input_consumed))
 952     {
 953       const char *haystack = args.strings[0];
 954       const char *needle = strstr (haystack, args.strings[1]);
 955       ds_put_format (output, "%zu", needle ? needle - haystack + 1 : 0);
 956     }
 957   else if (parse_macro_function (ctx, &args, ss_cstr ("!quote"), 1, 1,
 958                                  input_consumed))
 959     {
 960       if (unquote_string (args.strings[0], NULL))
 961         ds_put_cstr (output, args.strings[0]);
 962       else
 963         {
 964           ds_extend (output, strlen (args.strings[0]) + 2);
 965           ds_put_byte (output, '\'');
 966           for (const char *p = args.strings[0]; *p; p++)
 967             {
 968               if (*p == '\'')
 969                 ds_put_byte (output, '\'');
 970               ds_put_byte (output, *p);
 971             }
 972           ds_put_byte (output, '\'');
 973         }
 974     }
 975   else if (parse_macro_function (ctx, &args, ss_cstr ("!substr"), 2, 3,
 976                                  input_consumed))
 977     {
 978       int start;
 979       if (!parse_integer (args.strings[1], &start) || start < 1)
 980         {
 981           printf ("second argument to !SUBSTR must be positive integer (not \"%s\")\n", args.strings[1]);
 982           string_array_destroy (&args);
 983           return false;
 984         }
 985
 986       int count = INT_MAX;
 987       if (args.n > 2 && (!parse_integer (args.strings[2], &count) || count < 0))
 988         {
 989           printf ("third argument to !SUBSTR must be non-negative integer (not \"%s\")\n", args.strings[1]);
 990           string_array_destroy (&args);
 991           return false;
 992         }
 993
 994       struct substring s = ss_cstr (args.strings[0]);
 995       ds_put_substring (output, ss_substr (s, start - 1, count));
 996     }
 997   else if (parse_macro_function (ctx, &args, ss_cstr ("!tail"), 1, 1,
 998                                  input_consumed))
 999     {
1000       struct string tmp;
1001       const char *s = unquote_string_in_place (args.strings[0], &tmp);
1002
1003       struct macro_tokens mts = { .n = 0 };
1004       macro_tokens_from_string (&mts, ss_cstr (s), SEG_MODE_INTERACTIVE /* XXX */);
1005       if (mts.n > 1)
1006         {
1007           struct macro_tokens tail = { .mts = mts.mts + 1, .n = mts.n - 1 };
1008           macro_tokens_to_representation (&tail, output);
1009         }
1010       macro_tokens_uninit (&mts);
1011       ds_destroy (&tmp);
1012     }
1013   else if (parse_macro_function (ctx, &args, ss_cstr ("!unquote"), 1, 1,
1014                                  input_consumed))
1015     {
1016       if (!unquote_string (args.strings[0], output))
1017         ds_put_cstr (output, args.strings[0]);
1018     }
1019   else if (parse_macro_function (ctx, &args, ss_cstr ("!upcase"), 1, 1,
1020                                  input_consumed))
1021     {
1022       struct string tmp;
1023       const char *s = unquote_string_in_place (args.strings[0], &tmp);
1024       char *upper = utf8_to_upper (s);
1025       ds_put_cstr (output, upper);
1026       free (upper);
1027       ds_destroy (&tmp);
1028     }
1029   else if (parse_macro_function (ctx, &args, ss_cstr ("!eval"), 1, 1,
1030                                  input_consumed))
1031     {
1032       struct macro_tokens mts = { .n = 0 };
1033       macro_tokens_from_string (&mts, ss_cstr (args.strings[0]),
1034                                 SEG_MODE_INTERACTIVE /* XXX */);
1035       struct macro_tokens exp = { .n = 0 };
1036       macro_expand (&mts, ctx->nesting_countdown - 1, ctx->macros,
1037                     ctx->me, ctx->expand, &exp);
1038       macro_tokens_to_representation (&exp, output);
1039       macro_tokens_uninit (&exp);
1040       macro_tokens_uninit (&mts);
1041     }
1042   else if (ctx->n_input > 0
1043            && ctx->input[0].token.type == T_MACRO_ID
1044            && ss_equals_case (ctx->input[0].token.string, ss_cstr ("!null")))
1045     {
1046       *input_consumed = 1;
1047       return true;
1048     }
1049   else
1050     return false;
1051
1052   string_array_destroy (&args);
1053   return true;
1054 }
1055
1056 struct expr_context
1057   {
1058     int nesting_countdown;
1059     const struct macro_set *macros;
1060     const struct macro_expander *me;
1061     bool *expand;
1062   };
1063
1064 static char *macro_evaluate_or (const struct expr_context *ctx,
1065                                 const struct macro_token **tokens,
1066                                 const struct macro_token *end);
1067
1068 static char *
1069 macro_evaluate_literal (const struct expr_context *ctx,
1070                         const struct macro_token **tokens,
1071                         const struct macro_token *end)
1072 {
1073   const struct macro_token *p = *tokens;
1074   if (p >= end)
1075     return NULL;
1076   if (p->token.type == T_LPAREN)
1077     {
1078       p++;
1079       char *value = macro_evaluate_or (ctx, &p, end);
1080       if (!value)
1081         return NULL;
1082       if (p >= end || p->token.type != T_RPAREN)
1083         {
1084           free (value);
1085           printf ("expecting ')' in macro expression\n");
1086           return NULL;
1087         }
1088       p++;
1089       *tokens = p;
1090       return value;
1091     }
1092
1093   struct parse_macro_function_ctx fctx = {
1094     .input = p,
1095     .n_input = end - p,
1096     .nesting_countdown = ctx->nesting_countdown,
1097     .macros = ctx->macros,
1098     .me = ctx->me,
1099     .expand = ctx->expand,
1100   };
1101   struct string function_output = DS_EMPTY_INITIALIZER;
1102   size_t function_consumed;
1103   if (expand_macro_function (&fctx, &function_output, &function_consumed))
1104     {
1105       *tokens = p + function_consumed;
1106       return ds_steal_cstr (&function_output);
1107     }
1108
1109   *tokens = p + 1;
1110   return ss_xstrdup (p->representation);
1111 }
1112
1113 static char *
1114 macro_evaluate_logical (const struct expr_context *ctx,
1115                         const struct macro_token **tokens,
1116                         const struct macro_token *end)
1117 {
1118   const struct macro_token *p = *tokens;
1119   char *lhs = macro_evaluate_literal (ctx, &p, end);
1120   if (!lhs)
1121     return NULL;
1122
1123   enum token_type op = p < end ? p->token.type : T_STOP;
1124   if (op != T_EQUALS && op != T_EQ && op != T_NE && op != T_LT
1125       && op != T_GT && op != T_LE && op != T_GE)
1126     {
1127       *tokens = p;
1128       return lhs;
1129     }
1130   p++;
1131
1132   char *rhs = macro_evaluate_literal (ctx, &p, end);
1133   if (!rhs)
1134     {
1135       free (lhs);
1136       return NULL;
1137     }
1138
1139   struct string lhs_tmp, rhs_tmp;
1140   int cmp = strcmp/*XXX*/ (unquote_string_in_place (lhs, &lhs_tmp),
1141                            unquote_string_in_place (rhs, &rhs_tmp));
1142   ds_destroy (&lhs_tmp);
1143   ds_destroy (&rhs_tmp);
1144
1145   free (lhs);
1146   free (rhs);
1147
1148   bool b = (op == T_EQUALS || op == T_EQ ? !cmp
1149             : op == T_NE ? cmp
1150             : op == T_LT ? cmp < 0
1151             : op == T_GT ? cmp > 0
1152             : op == T_LE ? cmp <= 0
1153             :/*op == T_GE*/cmp >= 0);
1154
1155   *tokens = p;
1156   return xstrdup (b ? "1" : "0");
1157 }
1158
1159 static char *
1160 macro_evaluate_not (const struct expr_context *ctx,
1161                     const struct macro_token **tokens,
1162                     const struct macro_token *end)
1163 {
1164   const struct macro_token *p = *tokens;
1165
1166   unsigned int negations = 0;
1167   while (p < end && p->token.type == T_NOT)
1168     {
1169       p++;
1170       negations++;
1171     }
1172
1173   char *operand = macro_evaluate_logical (ctx, &p, end);
1174   if (!operand || !negations)
1175     {
1176       *tokens = p;
1177       return operand;
1178     }
1179
1180   bool b = strcmp (operand, "0") ^ (negations & 1);
1181   free (operand);
1182   *tokens = p;
1183   return xstrdup (b ? "1" : "0");
1184 }
1185
1186 static char *
1187 macro_evaluate_and (const struct expr_context *ctx,
1188                     const struct macro_token **tokens,
1189                     const struct macro_token *end)
1190 {
1191   const struct macro_token *p = *tokens;
1192   char *lhs = macro_evaluate_not (ctx, &p, end);
1193   if (!lhs)
1194     return NULL;
1195
1196   while (p < end && p->token.type == T_AND)
1197     {
1198       p++;
1199       char *rhs = macro_evaluate_not (ctx, &p, end);
1200       if (!rhs)
1201         {
1202           free (lhs);
1203           return NULL;
1204         }
1205
1206       bool b = strcmp (lhs, "0") && strcmp (rhs, "0");
1207       free (lhs);
1208       free (rhs);
1209       lhs = xstrdup (b ? "1" : "0");
1210     }
1211   *tokens = p;
1212   return lhs;
1213 }
1214
1215 static char *
1216 macro_evaluate_or (const struct expr_context *ctx,
1217                    const struct macro_token **tokens,
1218                    const struct macro_token *end)
1219 {
1220   const struct macro_token *p = *tokens;
1221   char *lhs = macro_evaluate_and (ctx, &p, end);
1222   if (!lhs)
1223     return NULL;
1224
1225   while (p < end && p->token.type == T_OR)
1226     {
1227       p++;
1228       char *rhs = macro_evaluate_and (ctx, &p, end);
1229       if (!rhs)
1230         {
1231           free (lhs);
1232           return NULL;
1233         }
1234
1235       bool b = strcmp (lhs, "0") || strcmp (rhs, "0");
1236       free (lhs);
1237       free (rhs);
1238       lhs = xstrdup (b ? "1" : "0");
1239     }
1240   *tokens = p;
1241   return lhs;
1242 }
1243
1244 static char *
1245 macro_evaluate_expression (const struct macro_token **tokens, size_t n_tokens,
1246                            int nesting_countdown, const struct macro_set *macros,
1247                            const struct macro_expander *me, bool *expand)
1248 {
1249   const struct expr_context ctx = {
1250     .nesting_countdown = nesting_countdown,
1251     .macros = macros,
1252     .me = me,
1253     .expand = expand,
1254   };
1255   return macro_evaluate_or (&ctx, tokens, *tokens + n_tokens);
1256 }
1257
1258 static const struct macro_token *
1259 find_ifend_clause (const struct macro_token *p, const struct macro_token *end)
1260 {
1261   size_t nesting = 0;
1262   for (; p < end; p++)
1263     {
1264       if (p->token.type != T_MACRO_ID)
1265         continue;
1266
1267       if (ss_equals_case (p->token.string, ss_cstr ("!IF")))
1268         nesting++;
1269       else if (ss_equals_case (p->token.string, ss_cstr ("!IFEND")))
1270         {
1271           if (!nesting)
1272             return p;
1273           nesting--;
1274         }
1275       else if (ss_equals_case (p->token.string, ss_cstr ("!ELSE")) && !nesting)
1276         return p;
1277     }
1278   return NULL;
1279 }
1280
1281 static size_t
1282 macro_expand_if (const struct macro_token *tokens, size_t n_tokens,
1283                  int nesting_countdown, const struct macro_set *macros,
1284                  const struct macro_expander *me, bool *expand,
1285                  struct macro_tokens *exp)
1286 {
1287   const struct macro_token *p = tokens;
1288   const struct macro_token *end = tokens + n_tokens;
1289
1290   if (p >= end || !ss_equals_case (p->token.string, ss_cstr ("!IF")))
1291     return 0;
1292
1293   p++;
1294   char *result = macro_evaluate_expression (&p, end - p,
1295                                             nesting_countdown, macros, me, expand);
1296   if (!result)
1297     return 0;
1298   bool b = strcmp (result, "0");
1299   free (result);
1300
1301   if (p >= end
1302       || p->token.type != T_MACRO_ID
1303       || !ss_equals_case (p->token.string, ss_cstr ("!THEN")))
1304     {
1305       printf ("!THEN expected\n");
1306       return 0;
1307     }
1308
1309   const struct macro_token *start_then = p + 1;
1310   const struct macro_token *end_then = find_ifend_clause (start_then, end);
1311   if (!end_then)
1312     {
1313       printf ("!ELSE or !IFEND expected\n");
1314       return 0;
1315     }
1316
1317   const struct macro_token *start_else, *end_if;
1318   if (ss_equals_case (end_then->token.string, ss_cstr ("!ELSE")))
1319     {
1320       start_else = end_then + 1;
1321       end_if = find_ifend_clause (start_else, end);
1322       if (!end_if
1323           || !ss_equals_case (end_if->token.string, ss_cstr ("!IFEND")))
1324         {
1325           printf ("!IFEND expected\n");
1326           return 0;
1327         }
1328     }
1329   else
1330     {
1331       start_else = NULL;
1332       end_if = end_then;
1333     }
1334
1335   const struct macro_token *start;
1336   size_t n;
1337   if (b)
1338     {
1339       start = start_then;
1340       n = end_then - start_then;
1341     }
1342   else if (start_else)
1343     {
1344       start = start_else;
1345       n = end_if - start_else;
1346     }
1347   else
1348     {
1349       start = NULL;
1350       n = 0;
1351     }
1352
1353   if (n)
1354     {
1355       struct macro_tokens mts = {
1356         .mts = CONST_CAST (struct macro_token *, start),
1357         .n = n,
1358       };
1359       macro_expand (&mts, nesting_countdown, macros, me, expand, exp);
1360     }
1361   return (end_if + 1) - tokens;
1362 }
1363
1364 static void
1365 macro_expand (const struct macro_tokens *mts,
1366               int nesting_countdown, const struct macro_set *macros,
1367               const struct macro_expander *me, bool *expand,
1368               struct macro_tokens *exp)
1369 {
1370   if (nesting_countdown <= 0)
1371     {
1372       printf ("maximum nesting level exceeded\n");
1373       for (size_t i = 0; i < mts->n; i++)
1374         macro_tokens_add (exp, &mts->mts[i]);
1375       return;
1376     }
1377
1378   for (size_t i = 0; i < mts->n; i++)
1379     {
1380       const struct macro_token *mt = &mts->mts[i];
1381       const struct token *token = &mt->token;
1382       if (token->type == T_MACRO_ID && me)
1383         {
1384           const struct macro_param *param = macro_find_parameter_by_name (
1385             me->macro, token->string);
1386           if (param)
1387             {
1388               const struct macro_tokens *arg = me->args[param - me->macro->params];
1389               //macro_tokens_print (arg, stdout);
1390               if (*expand && param->expand_arg)
1391                 macro_expand (arg, nesting_countdown, macros, NULL, expand, exp);
1392               else
1393                 for (size_t i = 0; i < arg->n; i++)
1394                   macro_tokens_add (exp, &arg->mts[i]);
1395               continue;
1396             }
1397
1398           if (is_bang_star (mts->mts, mts->n, i))
1399             {
1400               for (size_t j = 0; j < me->macro->n_params; j++)
1401                 {
1402                   const struct macro_param *param = &me->macro->params[j];
1403                   if (!param->positional)
1404                     break;
1405
1406                   const struct macro_tokens *arg = me->args[j];
1407                   if (*expand && param->expand_arg)
1408                     macro_expand (arg, nesting_countdown, macros, NULL, expand, exp);
1409                   else
1410                     for (size_t k = 0; k < arg->n; k++)
1411                       macro_tokens_add (exp, &arg->mts[k]);
1412                 }
1413               i++;
1414               continue;
1415             }
1416
1417           size_t n = macro_expand_if (&mts->mts[i], mts->n - i,
1418                                       nesting_countdown, macros, me, expand,
1419                                       exp);
1420           if (n > 0)
1421             {
1422               i += n - 1;
1423               continue;
1424             }
1425         }
1426
1427       if (*expand)
1428         {
1429           struct macro_expander *subme;
1430           int retval = macro_expander_create (macros, token, &subme);
1431           for (size_t j = 1; !retval; j++)
1432             {
1433               const struct macro_token endcmd = { .token = { .type = T_ENDCMD } };
1434               retval = macro_expander_add (
1435                 subme, i + j < mts->n ? &mts->mts[i + j] : &endcmd);
1436             }
1437           if (retval > 0)
1438             {
1439               i += retval - 1;
1440               macro_expand (&subme->macro->body, nesting_countdown - 1, macros,
1441                             subme, expand, exp);
1442               macro_expander_destroy (subme);
1443               continue;
1444             }
1445
1446           macro_expander_destroy (subme);
1447         }
1448
1449       if (token->type != T_MACRO_ID)
1450         {
1451           macro_tokens_add (exp, mt);
1452           continue;
1453         }
1454
1455       struct parse_macro_function_ctx ctx = {
1456         .input = &mts->mts[i],
1457         .n_input = mts->n - i,
1458         .nesting_countdown = nesting_countdown,
1459         .macros = macros,
1460         .me = me,
1461         .expand = expand,
1462       };
1463       struct string function_output = DS_EMPTY_INITIALIZER;
1464       size_t function_consumed;
1465       if (expand_macro_function (&ctx, &function_output, &function_consumed))
1466         {
1467           i += function_consumed - 1;
1468
1469           macro_tokens_from_string (exp, function_output.ss,
1470                                     SEG_MODE_INTERACTIVE /* XXX */);
1471           ds_destroy (&function_output);
1472
1473           continue;
1474         }
1475
1476       if (ss_equals_case (token->string, ss_cstr ("!onexpand")))
1477         *expand = true;
1478       else if (ss_equals_case (token->string, ss_cstr ("!offexpand")))
1479         *expand = false;
1480       else
1481         macro_tokens_add (exp, mt);
1482     }
1483 }
1484
1485 void
1486 macro_expander_get_expansion (struct macro_expander *me, struct macro_tokens *exp)
1487 {
1488 #if 0
1489   for (size_t i = 0; i < me->macro->n_params; i++)
1490     {
1491       printf ("%s:\n", me->macro->params[i].name);
1492       macro_tokens_print (me->args[i], stdout);
1493     }
1494 #endif
1495
1496   bool expand = true;
1497   macro_expand (&me->macro->body, settings_get_mnest (),
1498                 me->macros, me, &expand, exp);
1499
1500 #if 0
1501   printf ("expansion:\n");
1502   macro_tokens_print (exp, stdout);
1503 #endif
1504 }
1505