[pspp] / src / language / lexer / macro.c

/* PSPP - a program for statistical analysis.
   Copyright (C) 2021 Free Software Foundation, Inc.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

#include <config.h>

#include "language/lexer/macro.h"

#include <limits.h>
#include <stdlib.h>

#include "data/settings.h"
#include "language/lexer/segment.h"
#include "language/lexer/scan.h"
#include "libpspp/assertion.h"
#include "libpspp/i18n.h"
#include "libpspp/message.h"
#include "libpspp/str.h"

#include "gettext.h"
#define _(msgid) gettext (msgid)

void
macro_token_copy (struct macro_token *dst, const struct macro_token *src)
{
  token_copy (&dst->token, &src->token);
  ss_alloc_substring (&dst->representation, src->representation);
}

void
macro_token_uninit (struct macro_token *mt)
{
  token_uninit (&mt->token);
  ss_dealloc (&mt->representation);
}

void
macro_tokens_copy (struct macro_tokens *dst, const struct macro_tokens *src)
{
  *dst = (struct macro_tokens) {
    .mts = xmalloc (src->n * sizeof *dst->mts),
    .n = src->n,
    .allocated = src->n,
  };
  for (size_t i = 0; i < src->n; i++)
    macro_token_copy (&dst->mts[i], &src->mts[i]);
}

void
macro_tokens_uninit (struct macro_tokens *mts)
{
  for (size_t i = 0; i < mts->n; i++)
    macro_token_uninit (&mts->mts[i]);
  free (mts->mts);
}

struct macro_token *
macro_tokens_add_uninit (struct macro_tokens *mts)
{
  if (mts->n >= mts->allocated)
    mts->mts = x2nrealloc (mts->mts, &mts->allocated, sizeof *mts->mts);
  return &mts->mts[mts->n++];
}

void
macro_tokens_add (struct macro_tokens *mts, const struct macro_token *mt)
{
  macro_token_copy (macro_tokens_add_uninit (mts), mt);
}

void
macro_tokens_print (const struct macro_tokens *mts, FILE *stream)
{
  for (size_t i = 0; i < mts->n; i++)
    token_print (&mts->mts[i].token, stream);
}

void
macro_destroy (struct macro *m)
{
  if (!m)
    return;

  free (m->name);
  for (size_t i = 0; i < m->n_params; i++)
    {
      struct macro_param *p = &m->params[i];
      free (p->name);

      macro_tokens_uninit (&p->def);

      switch (p->arg_type)
        {
        case ARG_N_TOKENS:
          break;

        case ARG_CHAREND:
          token_uninit (&p->charend);
          break;

        case ARG_ENCLOSE:
          token_uninit (&p->enclose[0]);
          token_uninit (&p->enclose[1]);
          break;

        case ARG_CMDEND:
          break;
        }
    }
  free (m->params);
  macro_tokens_uninit (&m->body);
  free (m);
}
\f
struct macro_set *
macro_set_create (void)
{
  struct macro_set *set = xmalloc (sizeof *set);
  *set = (struct macro_set) {
    .macros = HMAP_INITIALIZER (set->macros),
  };
  return set;
}

void
macro_set_destroy (struct macro_set *set)
{
  if (!set)
    return;

  struct macro *macro, *next;
  HMAP_FOR_EACH_SAFE (macro, next, struct macro, hmap_node, &set->macros)
    {
      hmap_delete (&set->macros, &macro->hmap_node);
      macro_destroy (macro);
    }
  hmap_destroy (&set->macros);
  free (set);
}

static unsigned int
hash_macro_name (const char *name)
{
  return utf8_hash_case_string (name, 0);
}

static struct macro *
macro_set_find__ (struct macro_set *set, const char *name)
{
  struct macro *macro;
  HMAP_FOR_EACH_WITH_HASH (macro, struct macro, hmap_node,
                           hash_macro_name (name), &set->macros)
    if (!utf8_strcasecmp (macro->name, name))
      return macro;

  return NULL;
}

const struct macro *
macro_set_find (const struct macro_set *set, const char *name)
{
  return macro_set_find__ (CONST_CAST (struct macro_set *, set), name);
}

/* Adds M to SET.  M replaces any existing macro with the same name.  Takes
   ownership of M. */
void
macro_set_add (struct macro_set *set, struct macro *m)
{
  struct macro *victim = macro_set_find__ (set, m->name);
  if (victim)
    {
      hmap_delete (&set->macros, &victim->hmap_node);
      macro_destroy (victim);
    }

  hmap_insert (&set->macros, &m->hmap_node, hash_macro_name (m->name));
}
\f
enum me_state
  {
    /* Error state. */
    ME_ERROR,

    /* Accumulating tokens in me->params toward the end of any type of
       argument. */
    ME_ARG,

    /* Expecting the opening delimiter of an ARG_ENCLOSE argument. */
    ME_ENCLOSE,

    /* Expecting a keyword for a keyword argument. */
    ME_KEYWORD,

    /* Expecting an equal sign for a keyword argument. */
    ME_EQUALS,
  };


struct macro_expander
  {
    const struct macro_set *macros;

    enum me_state state;
    size_t n_tokens;

    const struct macro *macro;
    struct macro_tokens **args;
    const struct macro_param *param;
  };

static int
me_finished (struct macro_expander *me)
{
  for (size_t i = 0; i < me->macro->n_params; i++)
    if (!me->args[i])
      {
        me->args[i] = xmalloc (sizeof *me->args[i]);
        macro_tokens_copy (me->args[i], &me->macro->params[i].def);
      }
  return me->n_tokens;
}

static int
me_next_arg (struct macro_expander *me)
{
  if (!me->param)
    {
      assert (!me->macro->n_params);
      return me_finished (me);
    }
  else if (me->param->positional)
    {
      me->param++;
      if (me->param >= &me->macro->params[me->macro->n_params])
        return me_finished (me);
      else
        {
          me->state = me->param->positional ? ME_ARG : ME_KEYWORD;
          return 0;
        }
    }
  else
    {
      for (size_t i = 0; i < me->macro->n_params; i++)
        if (!me->args[i])
          {
            me->state = ME_KEYWORD;
            return 0;
          }
      return me_finished (me);
    }
}

static int
me_error (struct macro_expander *me)
{
  me->state = ME_ERROR;
  return -1;
}

static int
me_add_arg (struct macro_expander *me, const struct macro_token *mt)
{
  const struct token *token = &mt->token;
  if (token->type == T_STOP)
    {
      msg (SE, _("Unexpected end of file reading argument %s "
                 "to macro %s."), me->param->name, me->macro->name);

      return me_error (me);
    }

  me->n_tokens++;

  const struct macro_param *p = me->param;
  struct macro_tokens **argp = &me->args[p - me->macro->params];
  if (!*argp)
    *argp = xzalloc (sizeof **argp);
  struct macro_tokens *arg = *argp;
  if (p->arg_type == ARG_N_TOKENS)
    {
      macro_tokens_add (arg, mt);
      if (arg->n >= p->n_tokens)
        return me_next_arg (me);
      return 0;
    }
  else if (p->arg_type == ARG_CMDEND)
    {
      if (token->type == T_ENDCMD || token->type == T_STOP)
        return me_next_arg (me);
      macro_tokens_add (arg, mt);
      return 0;
    }
  else
    {
      const struct token *end
        = p->arg_type == ARG_CMDEND ? &p->charend : &p->enclose[1];
      if (token_equal (token, end))
        return me_next_arg (me);
      macro_tokens_add (arg, mt);
      return 0;
    }
}

static int
me_expected (struct macro_expander *me, const struct macro_token *actual,
             const struct token *expected)
{
  const struct substring actual_s
    = (actual->representation.length ? actual->representation
       : ss_cstr (_("<end of input>")));
  char *expected_s = token_to_string (expected);
  msg (SE, _("Found `%.*s' while expecting `%s' reading argument %s "
             "to macro %s."),
       (int) actual_s.length, actual_s.string, expected_s,
       me->param->name, me->macro->name);
  free (expected_s);

  return me_error (me);
}

static int
me_enclose (struct macro_expander *me, const struct macro_token *mt)
{
  const struct token *token = &mt->token;
  me->n_tokens++;

  if (token_equal (&me->param->enclose[0], token))
    {
      me->state = ME_ARG;
      return 0;
    }

  return me_expected (me, mt, &me->param->enclose[0]);
}

static const struct macro_param *
macro_find_parameter_by_name (const struct macro *m, struct substring name)
{
  for (size_t i = 0; i < m->n_params; i++)
    {
      const struct macro_param *p = &m->params[i];
      struct substring p_name = ss_cstr (p->name);
      if (!utf8_strncasecmp (p_name.string, p_name.length,
                             name.string, name.length))
        return p;
    }
  return NULL;
}

static int
me_keyword (struct macro_expander *me, const struct macro_token *mt)
{
  const struct token *token = &mt->token;
  if (token->type != T_ID)
    return me_finished (me);

  const struct macro_param *p = macro_find_parameter_by_name (me->macro,
                                                              token->string);
  if (p)
    {
      size_t arg_index = p - me->macro->params;
      me->param = p;
      if (me->args[arg_index])
        {
          msg (SE,
               _("Argument %s multiply specified in call to macro %s."),
               p->name, me->macro->name);
          return me_error (me);
        }

      me->n_tokens++;
      me->state = ME_EQUALS;
      return 0;
    }

  return me_finished (me);
}

static int
me_equals (struct macro_expander *me, const struct macro_token *mt)
{
  const struct token *token = &mt->token;
  me->n_tokens++;

  if (token->type == T_EQUALS)
    {
      me->state = ME_ARG;
      return 0;
    }

  return me_expected (me, mt, &(struct token) { .type = T_EQUALS });
}

int
macro_expander_create (const struct macro_set *macros,
                       const struct token *token,
                       struct macro_expander **mep)
{
  *mep = NULL;
  if (macro_set_is_empty (macros))
    return -1;
  if (token->type != T_ID && token->type != T_MACRO_ID)
    return -1;

  const struct macro *macro = macro_set_find (macros, token->string.string);
  if (!macro)
    return -1;

  struct macro_expander *me = xmalloc (sizeof *me);
  *me = (struct macro_expander) {
    .macros = macros,
    .n_tokens = 1,
    .macro = macro,
  };
  *mep = me;

  if (!macro->n_params)
    return 1;
  else
    {
      me->state = macro->params[0].positional ? ME_ARG : ME_KEYWORD;
      me->args = xcalloc (macro->n_params, sizeof *me->args);
      me->param = macro->params;
      return 0;
    }
}

void
macro_expander_destroy (struct macro_expander *me)
{
  if (!me)
    return;

  for (size_t i = 0; i < me->macro->n_params; i++)
    if (me->args[i])
      {
        macro_tokens_uninit (me->args[i]);
        free (me->args[i]);
      }
  free (me->args);
  free (me);
}

/* Adds TOKEN to the collection of tokens in ME that potentially need to be
   macro expanded.

   Returns -1 if the tokens added do not actually invoke a macro.  The caller
   should consume the first token without expanding it.

   Returns 0 if the macro expander needs more tokens, for macro arguments or to
   decide whether this is actually a macro invocation.  The caller should call
   macro_expander_add() again with the next token.

   Returns a positive number to indicate that the returned number of tokens
   invoke a macro.  The number returned might be less than the number of tokens
   added because it can take a few tokens of lookahead to determine whether the
   macro invocation is finished.  The caller should call
   macro_expander_get_expansion() to obtain the expansion. */
int
macro_expander_add (struct macro_expander *me, const struct macro_token *mt)
{
  switch (me->state)
    {
    case ME_ERROR:
      return -1;

    case ME_ARG:
      return me_add_arg (me, mt);

    case ME_ENCLOSE:
      return me_enclose (me, mt);

    case ME_KEYWORD:
      return me_keyword (me, mt);

    case ME_EQUALS:
      return me_equals (me, mt);

    default:
      NOT_REACHED ();
    }
}

/* Each argument to a macro function is one of:

       - A quoted string or other single literal token.

       - An argument to the macro being expanded, e.g. !1 or a named argument.

       - !*.

       - A function invocation.

   Each function invocation yields a character sequence to be turned into a
   sequence of tokens.  The case where that character sequence is a single
   quoted string is an important special case.
*/
struct parse_macro_function_ctx
  {
    struct macro_token *input;
    size_t n_input;
    int nesting_countdown;
    const struct macro_set *macros;
    const struct macro_expander *me;
    bool *expand;
  };

static void
macro_expand (const struct macro_tokens *,
              int nesting_countdown, const struct macro_set *,
              const struct macro_expander *, bool *expand, struct macro_tokens *exp);

static bool
expand_macro_function (struct parse_macro_function_ctx *ctx,
                       struct macro_token *output,
                       size_t *input_consumed);

static size_t
parse_function_arg (struct parse_macro_function_ctx *ctx,
                    size_t i, struct macro_token *farg)
{
  struct macro_token *tokens = ctx->input;
  const struct token *token = &tokens[i].token;
  if (token->type == T_MACRO_ID)
    {
      const struct macro_param *param = macro_find_parameter_by_name (
        ctx->me->macro, token->string);
      if (param)
        {
          size_t param_idx = param - ctx->me->macro->params;
          const struct macro_tokens *marg = ctx->me->args[param_idx];
          if (marg->n == 1)
            macro_token_copy (farg, &marg->mts[0]);
          else
            {
              struct string s = DS_EMPTY_INITIALIZER;
              for (size_t i = 0; i < marg->n; i++)
                {
                  if (i)
                    ds_put_byte (&s, ' ');
                  ds_put_substring (&s, marg->mts[i].representation);
                }

              struct substring s_copy;
              ss_alloc_substring (&s_copy, s.ss);

              *farg = (struct macro_token) {
                .token = { .type = T_MACRO_ID, .string = s.ss },
                .representation = s_copy,
              };
            }
          return 1;
        }

      struct parse_macro_function_ctx subctx = {
        .input = &ctx->input[i],
        .n_input = ctx->n_input - i,
        .nesting_countdown = ctx->nesting_countdown,
        .macros = ctx->macros,
        .me = ctx->me,
        .expand = ctx->expand,
      };
      size_t subinput_consumed;
      if (expand_macro_function (&subctx, farg, &subinput_consumed))
        return subinput_consumed;
    }

  macro_token_copy (farg, &tokens[i]);
  return 1;
}

static bool
parse_macro_function (struct parse_macro_function_ctx *ctx,
                      struct macro_tokens *args,
                      struct substring function,
                      int min_args, int max_args,
                      size_t *input_consumed)
{
  struct macro_token *tokens = ctx->input;
  size_t n_tokens = ctx->n_input;

  if (!n_tokens
      || tokens[0].token.type != T_MACRO_ID
      || !ss_equals_case (tokens[0].token.string, function))
    return false;

  if (n_tokens < 2 || tokens[1].token.type != T_LPAREN)
    {
      printf ("`(' expected following %s'\n", function.string);
      return false;
    }

  *args = (struct macro_tokens) { .n = 0 };

  for (size_t i = 2;; )
    {
      if (i >= n_tokens)
        goto unexpected_end;
      if (tokens[i].token.type == T_RPAREN)
        {
          *input_consumed = i + 1;
          if (args->n < min_args || args->n > max_args)
            {
              printf ("Wrong number of arguments to %s.\n", function.string);
              goto error;
            }
          return true;
        }

      i += parse_function_arg (ctx, i, macro_tokens_add_uninit (args));
      if (i >= n_tokens)
        goto unexpected_end;

      if (tokens[i].token.type == T_COMMA)
        i++;
      else if (tokens[i].token.type != T_RPAREN)
        {
          printf ("Expecting `,' or `)' in %s invocation.", function.string);
          goto error;
        }
    }

unexpected_end:
  printf ("Missing closing parenthesis in arguments to %s.\n",
          function.string);
  /* Fall through. */
error:
  macro_tokens_uninit (args);
  return false;
}

static bool
expand_macro_function (struct parse_macro_function_ctx *ctx,
                       struct macro_token *output,
                       size_t *input_consumed)
{
  struct macro_tokens args;

  if (parse_macro_function (ctx, &args, ss_cstr ("!length"), 1, 1,
                            input_consumed))
    {
      size_t length = args.mts[0].representation.length;
      *output = (struct macro_token) {
        .token = { .type = T_POS_NUM, .number = length },
        .representation = ss_cstr (xasprintf ("%zu", length)),
      };
    }
  else if (parse_macro_function (ctx, &args, ss_cstr ("!blanks"), 1, 1,
                                 input_consumed))
    {
      /* XXX this isn't right, it might be a character string containing a
         positive integer, e.g. via !CONCAT. */
      if (args.mts[0].token.type != T_POS_NUM)
        {
          printf ("argument to !BLANKS must be positive integer\n");
          macro_token_uninit (output);
          return false;
        }

      struct string s = DS_EMPTY_INITIALIZER;
      ds_put_byte_multiple (&s, ' ', args.mts[0].token.number);

      *output = (struct macro_token) {
        .token = { .type = T_ID, .string = s.ss },
        .representation = s.ss,
      };
    }
  else if (parse_macro_function (ctx, &args, ss_cstr ("!concat"), 1, INT_MAX,
                                 input_consumed))
    {
      struct string s;
      bool all_strings = true;
      for (size_t i = 0; i < args.n; i++)
        {
          if (args.mts[i].token.type == T_STRING)
            ds_put_substring (&s, args.mts[i].token.string);
          else
            {
              all_strings = false;
              ds_put_substring (&s, args.mts[i].representation);
            }
        }

      if (all_strings)
        {
          *output = (struct macro_token) {
            .token = { .type = T_STRING, .string = s.ss },
          };
          output->representation = ss_cstr (token_to_string (&output->token));
        }
      else
        {
          *output = (struct macro_token) {
            .token = { .type = T_MACRO_ID /*XXX*/, .string = s.ss },
          };
          ss_alloc_substring (&output->representation, s.ss);
        }
    }
  else
    return false;

  macro_tokens_uninit (&args);
  return true;
}

static void
macro_expand (const struct macro_tokens *mts,
              int nesting_countdown, const struct macro_set *macros,
              const struct macro_expander *me, bool *expand,
              struct macro_tokens *exp)
{
  if (nesting_countdown <= 0)
    {
      printf ("maximum nesting level exceeded\n");
      for (size_t i = 0; i < mts->n; i++)
        macro_tokens_add (exp, &mts->mts[i]);
      return;
    }

  for (size_t i = 0; i < mts->n; i++)
    {
      const struct macro_token *mt = &mts->mts[i];
      const struct token *token = &mt->token;
      if (token->type == T_MACRO_ID && me)
        {
          const struct macro_param *param = macro_find_parameter_by_name (
            me->macro, token->string);
          if (param)
            {
              const struct macro_tokens *arg = me->args[param - me->macro->params];
              //macro_tokens_print (arg, stdout);
              if (*expand && param->expand_arg)
                macro_expand (arg, nesting_countdown, macros, NULL, expand, exp);
              else
                for (size_t i = 0; i < arg->n; i++)
                  macro_tokens_add (exp, &arg->mts[i]);
              continue;
            }
        }

      if (*expand)
        {
          struct macro_expander *subme;
          int retval = macro_expander_create (macros, token, &subme);
          for (size_t j = 1; !retval; j++)
            {
              const struct macro_token stop = { .token = { .type = T_STOP } };
              retval = macro_expander_add (
                subme, i + j < mts->n ? &mts->mts[i + j] : &stop);
            }
          if (retval > 0)
            {
              i += retval - 1;
              macro_expand (&subme->macro->body, nesting_countdown - 1, macros,
                            subme, expand, exp);
              macro_expander_destroy (subme);
              continue;
            }

          macro_expander_destroy (subme);
        }

      if (token->type != T_MACRO_ID)
        {
          macro_tokens_add (exp, mt);
          continue;
        }

      /* Maybe each arg should just be a string, either a quoted string or a
         non-quoted string containing tokens. */
      struct parse_macro_function_ctx ctx = {
        .input = &mts->mts[i],
        .n_input = mts->n - i,
        .nesting_countdown = nesting_countdown,
        .macros = macros,
        .me = me,
        .expand = expand,
      };
      struct macro_token function_output;
      size_t function_consumed;
      if (expand_macro_function (&ctx, &function_output, &function_consumed))
        {
          i += function_consumed - 1;

          

          continue;
        }

      if (ss_equals_case (token->string, ss_cstr ("!onexpand")))
        *expand = true;
      else if (ss_equals_case (token->string, ss_cstr ("!offexpand")))
        *expand = false;
      else
        macro_tokens_add (exp, mt);
    }
}

void
macro_expander_get_expansion (struct macro_expander *me, struct macro_tokens *exp)
{
#if 0
  for (size_t i = 0; i < me->macro->n_params; i++)
    {
      printf ("%s:\n", me->macro->params[i].name);
      macro_tokens_print (me->args[i], stdout);
    }
#endif

  bool expand = true;
  macro_expand (&me->macro->body, settings_get_mnest (),
                me->macros, me, &expand, exp);

#if 0
  printf ("expansion:\n");
  macro_tokens_print (exp, stdout);
#endif
}