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 <stdlib.h>
  22
  23 #include "data/settings.h"
  24 #include "language/lexer/segment.h"
  25 #include "language/lexer/scan.h"
  26 #include "libpspp/assertion.h"
  27 #include "libpspp/i18n.h"
  28 #include "libpspp/message.h"
  29 #include "libpspp/str.h"
  30
  31 #include "gettext.h"
  32 #define _(msgid) gettext (msgid)
  33
  34 void
  35 macro_token_copy (struct macro_token *dst, const struct macro_token *src)
  36 {
  37   token_copy (&dst->token, &src->token);
  38   ss_alloc_substring (&dst->representation, src->representation);
  39 }
  40
  41 void
  42 macro_token_uninit (struct macro_token *mt)
  43 {
  44   token_uninit (&mt->token);
  45   ss_dealloc (&mt->representation);
  46 }
  47
  48 void
  49 macro_tokens_copy (struct macro_tokens *dst, const struct macro_tokens *src)
  50 {
  51   *dst = (struct macro_tokens) {
  52     .mts = xmalloc (src->n * sizeof *dst->mts),
  53     .n = src->n,
  54     .allocated = src->n,
  55   };
  56   for (size_t i = 0; i < src->n; i++)
  57     macro_token_copy (&dst->mts[i], &src->mts[i]);
  58 }
  59
  60 void
  61 macro_tokens_uninit (struct macro_tokens *mts)
  62 {
  63   for (size_t i = 0; i < mts->n; i++)
  64     macro_token_uninit (&mts->mts[i]);
  65   free (mts->mts);
  66 }
  67
  68 void
  69 macro_tokens_add (struct macro_tokens *mts, const struct macro_token *mt)
  70 {
  71   if (mts->n >= mts->allocated)
  72     mts->mts = x2nrealloc (mts->mts, &mts->allocated, sizeof *mts->mts);
  73   macro_token_copy (&mts->mts[mts->n++], mt);
  74 }
  75
  76 void
  77 macro_tokens_print (const struct macro_tokens *mts, FILE *stream)
  78 {
  79   for (size_t i = 0; i < mts->n; i++)
  80     token_print (&mts->mts[i].token, stream);
  81 }
  82
  83 void
  84 macro_destroy (struct macro *m)
  85 {
  86   if (!m)
  87     return;
  88
  89   free (m->name);
  90   for (size_t i = 0; i < m->n_params; i++)
  91     {
  92       struct macro_param *p = &m->params[i];
  93       free (p->name);
  94
  95       macro_tokens_uninit (&p->def);
  96
  97       switch (p->arg_type)
  98         {
  99         case ARG_N_TOKENS:
 100           break;
 101
 102         case ARG_CHAREND:
 103           token_uninit (&p->charend);
 104           break;
 105
 106         case ARG_ENCLOSE:
 107           token_uninit (&p->enclose[0]);
 108           token_uninit (&p->enclose[1]);
 109           break;
 110
 111         case ARG_CMDEND:
 112           break;
 113         }
 114     }
 115   free (m->params);
 116   macro_tokens_uninit (&m->body);
 117   free (m);
 118 }
 119 \f
 120 struct macro_set *
 121 macro_set_create (void)
 122 {
 123   struct macro_set *set = xmalloc (sizeof *set);
 124   *set = (struct macro_set) {
 125     .macros = HMAP_INITIALIZER (set->macros),
 126   };
 127   return set;
 128 }
 129
 130 void
 131 macro_set_destroy (struct macro_set *set)
 132 {
 133   if (!set)
 134     return;
 135
 136   struct macro *macro, *next;
 137   HMAP_FOR_EACH_SAFE (macro, next, struct macro, hmap_node, &set->macros)
 138     {
 139       hmap_delete (&set->macros, &macro->hmap_node);
 140       macro_destroy (macro);
 141     }
 142   hmap_destroy (&set->macros);
 143   free (set);
 144 }
 145
 146 static unsigned int
 147 hash_macro_name (const char *name)
 148 {
 149   return utf8_hash_case_string (name, 0);
 150 }
 151
 152 static struct macro *
 153 macro_set_find__ (struct macro_set *set, const char *name)
 154 {
 155   struct macro *macro;
 156   HMAP_FOR_EACH_WITH_HASH (macro, struct macro, hmap_node,
 157                            hash_macro_name (name), &set->macros)
 158     if (!utf8_strcasecmp (macro->name, name))
 159       return macro;
 160
 161   return NULL;
 162 }
 163
 164 const struct macro *
 165 macro_set_find (const struct macro_set *set, const char *name)
 166 {
 167   return macro_set_find__ (CONST_CAST (struct macro_set *, set), name);
 168 }
 169
 170 /* Adds M to SET.  M replaces any existing macro with the same name.  Takes
 171    ownership of M. */
 172 void
 173 macro_set_add (struct macro_set *set, struct macro *m)
 174 {
 175   struct macro *victim = macro_set_find__ (set, m->name);
 176   if (victim)
 177     {
 178       hmap_delete (&set->macros, &victim->hmap_node);
 179       macro_destroy (victim);
 180     }
 181
 182   hmap_insert (&set->macros, &m->hmap_node, hash_macro_name (m->name));
 183 }
 184 \f
 185 enum me_state
 186   {
 187     /* Error state. */
 188     ME_ERROR,
 189
 190     /* Accumulating tokens in me->params toward the end of any type of
 191        argument. */
 192     ME_ARG,
 193
 194     /* Expecting the opening delimiter of an ARG_ENCLOSE argument. */
 195     ME_ENCLOSE,
 196
 197     /* Expecting a keyword for a keyword argument. */
 198     ME_KEYWORD,
 199
 200     /* Expecting an equal sign for a keyword argument. */
 201     ME_EQUALS,
 202   };
 203
 204
 205 struct macro_expander
 206   {
 207     const struct macro_set *macros;
 208
 209     enum me_state state;
 210     size_t n_tokens;
 211
 212     const struct macro *macro;
 213     struct macro_tokens **args;
 214     const struct macro_param *param;
 215   };
 216
 217 static int
 218 me_finished (struct macro_expander *me)
 219 {
 220   for (size_t i = 0; i < me->macro->n_params; i++)
 221     if (!me->args[i])
 222       {
 223         me->args[i] = xmalloc (sizeof *me->args[i]);
 224         macro_tokens_copy (me->args[i], &me->macro->params[i].def);
 225       }
 226   return me->n_tokens;
 227 }
 228
 229 static int
 230 me_next_arg (struct macro_expander *me)
 231 {
 232   if (!me->param)
 233     {
 234       assert (!me->macro->n_params);
 235       return me_finished (me);
 236     }
 237   else if (me->param->positional)
 238     {
 239       me->param++;
 240       if (me->param >= &me->macro->params[me->macro->n_params])
 241         return me_finished (me);
 242       else
 243         {
 244           me->state = me->param->positional ? ME_ARG : ME_KEYWORD;
 245           return 0;
 246         }
 247     }
 248   else
 249     {
 250       for (size_t i = 0; i < me->macro->n_params; i++)
 251         if (!me->args[i])
 252           {
 253             me->state = ME_KEYWORD;
 254             return 0;
 255           }
 256       return me_finished (me);
 257     }
 258 }
 259
 260 static int
 261 me_error (struct macro_expander *me)
 262 {
 263   me->state = ME_ERROR;
 264   return -1;
 265 }
 266
 267 static int
 268 me_add_arg (struct macro_expander *me, const struct macro_token *mt)
 269 {
 270   const struct token *token = &mt->token;
 271   if (token->type == T_STOP)
 272     {
 273       msg (SE, _("Unexpected end of file reading argument %s "
 274                  "to macro %s."), me->param->name, me->macro->name);
 275
 276       return me_error (me);
 277     }
 278
 279   me->n_tokens++;
 280
 281   const struct macro_param *p = me->param;
 282   struct macro_tokens **argp = &me->args[p - me->macro->params];
 283   if (!*argp)
 284     *argp = xzalloc (sizeof **argp);
 285   struct macro_tokens *arg = *argp;
 286   if (p->arg_type == ARG_N_TOKENS)
 287     {
 288       macro_tokens_add (arg, mt);
 289       if (arg->n >= p->n_tokens)
 290         return me_next_arg (me);
 291       return 0;
 292     }
 293   else if (p->arg_type == ARG_CMDEND)
 294     {
 295       if (token->type == T_ENDCMD || token->type == T_STOP)
 296         return me_next_arg (me);
 297       macro_tokens_add (arg, mt);
 298       return 0;
 299     }
 300   else
 301     {
 302       const struct token *end
 303         = p->arg_type == ARG_CMDEND ? &p->charend : &p->enclose[1];
 304       if (token_equal (token, end))
 305         return me_next_arg (me);
 306       macro_tokens_add (arg, mt);
 307       return 0;
 308     }
 309 }
 310
 311 static int
 312 me_expected (struct macro_expander *me, const struct macro_token *actual,
 313              const struct token *expected)
 314 {
 315   const struct substring actual_s
 316     = (actual->representation.length ? actual->representation
 317        : ss_cstr (_("<end of input>")));
 318   char *expected_s = token_to_string (expected);
 319   msg (SE, _("Found `%.*s' while expecting `%s' reading argument %s "
 320              "to macro %s."),
 321        (int) actual_s.length, actual_s.string, expected_s,
 322        me->param->name, me->macro->name);
 323   free (expected_s);
 324
 325   return me_error (me);
 326 }
 327
 328 static int
 329 me_enclose (struct macro_expander *me, const struct macro_token *mt)
 330 {
 331   const struct token *token = &mt->token;
 332   me->n_tokens++;
 333
 334   if (token_equal (&me->param->enclose[0], token))
 335     {
 336       me->state = ME_ARG;
 337       return 0;
 338     }
 339
 340   return me_expected (me, mt, &me->param->enclose[0]);
 341 }
 342
 343 static const struct macro_param *
 344 macro_find_parameter_by_name (const struct macro *m, struct substring name)
 345 {
 346   for (size_t i = 0; i < m->n_params; i++)
 347     {
 348       const struct macro_param *p = &m->params[i];
 349       struct substring p_name = ss_cstr (p->name);
 350       if (!utf8_strncasecmp (p_name.string, p_name.length,
 351                              name.string, name.length))
 352         return p;
 353     }
 354   return NULL;
 355 }
 356
 357 static int
 358 me_keyword (struct macro_expander *me, const struct macro_token *mt)
 359 {
 360   const struct token *token = &mt->token;
 361   if (token->type != T_ID)
 362     return me_finished (me);
 363
 364   const struct macro_param *p = macro_find_parameter_by_name (me->macro,
 365                                                               token->string);
 366   if (p)
 367     {
 368       size_t arg_index = p - me->macro->params;
 369       me->param = p;
 370       if (me->args[arg_index])
 371         {
 372           msg (SE,
 373                _("Argument %s multiply specified in call to macro %s."),
 374                p->name, me->macro->name);
 375           return me_error (me);
 376         }
 377
 378       me->n_tokens++;
 379       me->state = ME_EQUALS;
 380       return 0;
 381     }
 382
 383   return me_finished (me);
 384 }
 385
 386 static int
 387 me_equals (struct macro_expander *me, const struct macro_token *mt)
 388 {
 389   const struct token *token = &mt->token;
 390   me->n_tokens++;
 391
 392   if (token->type == T_EQUALS)
 393     {
 394       me->state = ME_ARG;
 395       return 0;
 396     }
 397
 398   return me_expected (me, mt, &(struct token) { .type = T_EQUALS });
 399 }
 400
 401 int
 402 macro_expander_create (const struct macro_set *macros,
 403                        const struct token *token,
 404                        struct macro_expander **mep)
 405 {
 406   *mep = NULL;
 407   if (macro_set_is_empty (macros))
 408     return -1;
 409   if (token->type != T_ID && token->type != T_MACRO_ID)
 410     return -1;
 411
 412   const struct macro *macro = macro_set_find (macros, token->string.string);
 413   if (!macro)
 414     return -1;
 415
 416   struct macro_expander *me = xmalloc (sizeof *me);
 417   *me = (struct macro_expander) {
 418     .macros = macros,
 419     .n_tokens = 1,
 420     .macro = macro,
 421   };
 422   *mep = me;
 423
 424   if (!macro->n_params)
 425     return 1;
 426   else
 427     {
 428       me->state = macro->params[0].positional ? ME_ARG : ME_KEYWORD;
 429       me->args = xcalloc (macro->n_params, sizeof *me->args);
 430       me->param = macro->params;
 431       return 0;
 432     }
 433 }
 434
 435 void
 436 macro_expander_destroy (struct macro_expander *me)
 437 {
 438   if (!me)
 439     return;
 440
 441   for (size_t i = 0; i < me->macro->n_params; i++)
 442     if (me->args[i])
 443       {
 444         macro_tokens_uninit (me->args[i]);
 445         free (me->args[i]);
 446       }
 447   free (me->args);
 448   free (me);
 449 }
 450
 451 /* Adds TOKEN to the collection of tokens in ME that potentially need to be
 452    macro expanded.
 453
 454    Returns -1 if the tokens added do not actually invoke a macro.  The caller
 455    should consume the first token without expanding it.
 456
 457    Returns 0 if the macro expander needs more tokens, for macro arguments or to
 458    decide whether this is actually a macro invocation.  The caller should call
 459    macro_expander_add() again with the next token.
 460
 461    Returns a positive number to indicate that the returned number of tokens
 462    invoke a macro.  The number returned might be less than the number of tokens
 463    added because it can take a few tokens of lookahead to determine whether the
 464    macro invocation is finished.  The caller should call
 465    macro_expander_get_expansion() to obtain the expansion. */
 466 int
 467 macro_expander_add (struct macro_expander *me, const struct macro_token *mt)
 468 {
 469   switch (me->state)
 470     {
 471     case ME_ERROR:
 472       return -1;
 473
 474     case ME_ARG:
 475       return me_add_arg (me, mt);
 476
 477     case ME_ENCLOSE:
 478       return me_enclose (me, mt);
 479
 480     case ME_KEYWORD:
 481       return me_keyword (me, mt);
 482
 483     case ME_EQUALS:
 484       return me_equals (me, mt);
 485
 486     default:
 487       NOT_REACHED ();
 488     }
 489 }
 490
 491 struct parse_macro_function_ctx
 492   {
 493     const struct macro_tokens *mts;
 494     size_t *idx;
 495     struct macro_tokens *args;
 496     int nesting_countdown;
 497     const struct macro_set *macros;
 498     const struct macro_expander *me;
 499     bool *expand;
 500   };
 501
 502 static void
 503 macro_expand (const struct macro_tokens *,
 504               int nesting_countdown, const struct macro_set *,
 505               const struct macro_expander *, bool *expand, struct macro_tokens *exp);
 506
 507 static bool
 508 parse_macro_function (struct parse_macro_function_ctx *ctx,
 509                       struct substring function,
 510                       int min_args, int max_args)
 511 {
 512   struct macro_token *tokens = ctx->mts->mts;
 513   size_t n_tokens = ctx->mts->n;
 514
 515   if (!ss_equals_case (tokens[0].token.string, function))
 516     return false;
 517
 518   size_t lparen_idx = *ctx->idx + 1;
 519   if (lparen_idx >= n_tokens || tokens[lparen_idx].token.type != T_LPAREN)
 520     {
 521       printf ("`(' expected following %s'\n", function.string);
 522       return false;
 523     }
 524
 525   *ctx->args = (struct macro_tokens) { .n = 0 };
 526
 527   size_t i = lparen_idx + 1;
 528   for (size_t j = i; ; j++)
 529     {
 530       if (j >= n_tokens)
 531         {
 532           printf ("Missing closing parenthesis in arguments to %s.\n",
 533                   function.string);
 534           goto error;
 535         }
 536
 537       int type = tokens[j].token.type;
 538       if (type == T_LPAREN)
 539         {
 540           int paren_nesting_level = 1;
 541           do
 542             {
 543               j++;
 544               if (j >= n_tokens)
 545                 {
 546                   printf ("Missing closing parenthesis in argument %zu to %s.\n",
 547                           ctx->args->n + 1, function.string);
 548                   goto error;
 549                 }
 550               if (tokens[j].token.type == T_LPAREN)
 551                 paren_nesting_level++;
 552               else if (tokens[j].token.type == T_RPAREN)
 553                 paren_nesting_level--;
 554             }
 555           while (paren_nesting_level != 0);
 556         }
 557       else if (type == T_RPAREN || type == T_COMMA)
 558         {
 559           struct macro_tokens expanded_arg = { .n = 0 };
 560           macro_expand (&(const struct macro_tokens) { .mts = &tokens[i], .n = j - i },
 561                         ctx->nesting_countdown, ctx->macros,
 562                         ctx->me, ctx->expand, &expanded_arg);
 563
 564           if (expanded_arg.n != 1)
 565             {
 566               printf ("argument %zu to %s must be a single token "
 567                       "(not %zu tokens)\n", ctx->args->n + 1, function.string,
 568                       expanded_arg.n);
 569               macro_tokens_uninit (&expanded_arg);
 570               goto error;
 571             }
 572
 573           macro_tokens_add (ctx->args, &expanded_arg.mts[0]);
 574           macro_tokens_uninit (&expanded_arg);
 575
 576           i = j + 1;
 577           if (type == T_RPAREN)
 578             break;
 579         }
 580     }
 581
 582   if (ctx->args->n < min_args || ctx->args->n > max_args)
 583     {
 584       printf ("Wrong number of argument to %s.\n", function.string);
 585       goto error;
 586     }
 587   *ctx->idx = i;
 588   return true;
 589
 590 error:
 591   macro_tokens_uninit (ctx->args);
 592   return false;
 593 }
 594
 595 static void
 596 macro_expand (const struct macro_tokens *mts,
 597               int nesting_countdown, const struct macro_set *macros,
 598               const struct macro_expander *me, bool *expand,
 599               struct macro_tokens *exp)
 600 {
 601   if (nesting_countdown <= 0)
 602     {
 603       printf ("maximum nesting level exceeded\n");
 604       for (size_t i = 0; i < mts->n; i++)
 605         macro_tokens_add (exp, &mts->mts[i]);
 606       return;
 607     }
 608
 609   for (size_t i = 0; i < mts->n; i++)
 610     {
 611       const struct macro_token *mt = &mts->mts[i];
 612       const struct token *token = &mt->token;
 613       if (token->type == T_MACRO_ID && me)
 614         {
 615           const struct macro_param *param = macro_find_parameter_by_name (
 616             me->macro, token->string);
 617           if (param)
 618             {
 619               printf ("expand %s to:\n", param->name);
 620               const struct macro_tokens *arg = me->args[param - me->macro->params];
 621               macro_tokens_print (arg, stdout);
 622               if (*expand && param->expand_arg)
 623                 macro_expand (arg, nesting_countdown, macros, NULL, expand, exp);
 624               else
 625                 for (size_t i = 0; i < arg->n; i++)
 626                   macro_tokens_add (exp, &arg->mts[i]);
 627               continue;
 628             }
 629         }
 630
 631       if (*expand)
 632         {
 633           struct macro_expander *subme;
 634           int retval = macro_expander_create (macros, token, &subme);
 635           for (size_t j = 1; !retval; j++)
 636             {
 637               const struct macro_token stop = { .token = { .type = T_STOP } };
 638               retval = macro_expander_add (
 639                 subme, i + j < mts->n ? &mts->mts[i + j] : &stop);
 640             }
 641           if (retval > 0)
 642             {
 643               i += retval - 1;
 644               macro_expand (&subme->macro->body, nesting_countdown - 1, macros,
 645                             subme, expand, exp);
 646               macro_expander_destroy (subme);
 647               continue;
 648             }
 649
 650           macro_expander_destroy (subme);
 651         }
 652
 653       if (token->type != T_MACRO_ID)
 654         {
 655           macro_tokens_add (exp, mt);
 656           continue;
 657         }
 658
 659 #if 0
 660       struct macro_function
 661         {
 662           const char *name;
 663           int min_args;
 664           int max_args;
 665         };
 666       static const struct macro_function functions[] = {
 667         { "!length", 1, 1 },
 668         { "!concat", 1, INT_MAX },
 669         { "!substr", 2, 3 },
 670         { "!index", 2, 2 },
 671         { "!head", 1, 1 },
 672         { "!tail", 1, 1 },
 673         { "!quote", 1, 1 },
 674         { "!unquote", 1, 1 },
 675         { "!upcase", 1, 1 },
 676         { "!blanks", 1, 1 },
 677         { "!eval", 1, 1 },
 678       };
 679 #endif
 680       /* Maybe each arg should just be a string, either a quoted string or a
 681          non-quoted string containing tokens. */
 682       struct macro_tokens args;
 683       struct parse_macro_function_ctx ctx = {
 684         .mts = mts,
 685         .idx = &i,
 686         .args = &args,
 687         .nesting_countdown = nesting_countdown,
 688         .macros = macros,
 689         .me = me,
 690         .expand = expand,
 691       };
 692       if (parse_macro_function (&ctx, ss_cstr ("!length"), 1, 1))
 693         {
 694           size_t length = args.mts[0].representation.length;
 695           struct macro_token mt = {
 696             .token = { .type = T_POS_NUM, .number = length },
 697             .representation = ss_cstr (xasprintf ("%zu", length)),
 698           };
 699           macro_tokens_add (exp, &mt);
 700           macro_token_uninit (&mt);
 701
 702           macro_tokens_uninit (&args);
 703         }
 704       else if (parse_macro_function (&ctx, ss_cstr ("!blanks"), 1, 1))
 705         {
 706           /* XXX this isn't right, it might be a character string containing a
 707              positive integer, e.g. via !CONCAT. */
 708           if (args.mts[0].token.type != T_POS_NUM)
 709             printf ("argument to !BLANKS must be positive integer\n");
 710           else
 711             {
 712               struct string s = DS_EMPTY_INITIALIZER;
 713               ds_put_byte_multiple (&s, ' ', args.mts[0].token.number);
 714
 715               struct macro_token mt = {
 716                 .token = { .type = T_ID, .string = s.ss },
 717                 .representation = s.ss
 718               };
 719               macro_tokens_add (exp, &mt);
 720
 721               ds_destroy (&s);
 722             }
 723           macro_tokens_uninit (&args);
 724         }
 725       else if (ss_equals_case (token->string, ss_cstr ("!onexpand")))
 726         *expand = true;
 727       else if (ss_equals_case (token->string, ss_cstr ("!offexpand")))
 728         *expand = false;
 729       else
 730         macro_tokens_add (exp, mt);
 731     }
 732 }
 733
 734 void
 735 macro_expander_get_expansion (struct macro_expander *me, struct macro_tokens *exp)
 736 {
 737   for (size_t i = 0; i < me->macro->n_params; i++)
 738     {
 739       printf ("%s:\n", me->macro->params[i].name);
 740       macro_tokens_print (me->args[i], stdout);
 741     }
 742
 743   bool expand = true;
 744   macro_expand (&me->macro->body, settings_get_mnest (),
 745                 me->macros, me, &expand, exp);
 746
 747   printf ("expansion:\n");
 748   macro_tokens_print (exp, stdout);
 749 }
 750