#include <defs.h>


typedef struct mcpu_macro_arg mcpu_macro_arg;
struct mcpu_macro_arg
{
  const __mpu_char16_t *raw;
  size_t                raw_length;
  mcpu_text             expanded;
  int                   expanded_ready;
};


static unsigned
macro_hash( const __mpu_char16_t *name, size_t length )
{
  unsigned h = 5381U;
  size_t   i;

  for( i = 0; i < length; ++i )
    h = ((h << 5) + h) ^ (unsigned)name[i];

  return( h % MCPU_CPP_MACRO_BUCKETS );
}


static __mpu_char16_t *
dup_text( const __mpu_char16_t *text, size_t length )
{
  __mpu_char16_t *copy;

  copy = (__mpu_char16_t *)calloc( length + 1, sizeof(__mpu_char16_t) );
  if( copy == NULL )
    return( NULL );

  if( length != 0 )
    memcpy( copy, text, length * sizeof(__mpu_char16_t) );

  return( copy );
}


static void
free_argnames( __mpu_char16_t **argnames, size_t *argname_lengths,
               int nargs )
{
  int i;

  if( argnames )
  {
    for( i = 0; i < nargs; ++i )
      free( argnames[i] );
  }

  free( argnames );
  free( argname_lengths );
}


static void
free_macro_contents( mcpu_macro *macro )
{
  if( macro == NULL )
    return;

  free( macro->name );
  free_argnames( macro->argnames, macro->argname_lengths, macro->nargs );
  free( macro->replacement );
}


void
mcpu_macro_table_init( mcpu_macro_table *table )
{
  if( table )
    memset( table, 0, sizeof(*table) );
}


void
mcpu_macro_table_free( mcpu_macro_table *table )
{
  unsigned i;

  if( table == NULL )
    return;

  for( i = 0; i < MCPU_CPP_MACRO_BUCKETS; ++i )
  {
    mcpu_macro *macro = table->bucket[i];

    while( macro )
    {
      mcpu_macro *next = macro->next;
      free_macro_contents( macro );
      free( macro );
      macro = next;
    }

    table->bucket[i] = NULL;
  }
}


mcpu_macro *
mcpu_macro_find( mcpu_macro_table *table,
                 const __mpu_char16_t *name, size_t name_length )
{
  mcpu_macro *macro;
  unsigned    h;

  if( table == NULL || name == NULL || name_length == 0 )
    return( NULL );

  h = macro_hash( name, name_length );
  for( macro = table->bucket[h]; macro; macro = macro->next )
  {
    if( macro->name_length == name_length &&
        memcmp( macro->name, name,
                name_length * sizeof(__mpu_char16_t) ) == 0 )
      return( macro );
  }

  return( NULL );
}


static int
copy_argnames( const __mpu_char16_t *const *argnames,
               const size_t *argname_lengths, size_t nargs,
               __mpu_char16_t ***copy_names, size_t **copy_lengths )
{
  __mpu_char16_t **names = NULL;
  size_t          *lengths = NULL;
  size_t           i;

  *copy_names = NULL;
  *copy_lengths = NULL;

  if( nargs == 0 )
    return( 0 );

  names = (__mpu_char16_t **)calloc( nargs, sizeof(*names) );
  lengths = (size_t *)calloc( nargs, sizeof(*lengths) );
  if( names == NULL || lengths == NULL )
    goto fail;

  for( i = 0; i < nargs; ++i )
  {
    names[i] = dup_text( argnames[i], argname_lengths[i] );
    if( names[i] == NULL )
      goto fail;
    lengths[i] = argname_lengths[i];
  }

  *copy_names = names;
  *copy_lengths = lengths;
  return( 0 );

fail:
  if( names )
  {
    for( i = 0; i < nargs; ++i )
      free( names[i] );
  }
  free( names );
  free( lengths );
  return( -1 );
}


static int
macro_install( mcpu_macro_table *table,
               const __mpu_char16_t *name, size_t name_length,
               int nargs, int variadic,
               const __mpu_char16_t *const *argnames,
               const size_t *argname_lengths,
               const __mpu_char16_t *replacement,
               size_t replacement_length,
               enum mcpu_macro_builtin builtin,
               unsigned builtin_bits,
               enum mcpu_macro_origin origin )
{
  mcpu_macro      *macro;
  __mpu_char16_t  *new_replacement;
  __mpu_char16_t **new_argnames = NULL;
  size_t          *new_argname_lengths = NULL;
  unsigned         h;

  if( table == NULL || name == NULL || name_length == 0 ||
      (replacement == NULL && replacement_length != 0) || nargs < -1 ||
      (variadic && nargs < 0) ||
      (nargs > 0 && (argnames == NULL || argname_lengths == NULL)) )
  {
    errno = EINVAL;
    return( -1 );
  }

  new_replacement = dup_text( replacement, replacement_length );
  if( new_replacement == NULL )
    return( -1 );

  if( nargs >= 0 &&
      copy_argnames(argnames, argname_lengths, (size_t)nargs,
                    &new_argnames, &new_argname_lengths) != 0 )
  {
    free( new_replacement );
    return( -1 );
  }

  macro = mcpu_macro_find( table, name, name_length );
  if( macro )
  {
    free_argnames( macro->argnames, macro->argname_lengths, macro->nargs );
    free( macro->replacement );
    macro->nargs = nargs;
    macro->variadic = variadic;
    macro->argnames = new_argnames;
    macro->argname_lengths = new_argname_lengths;
    macro->replacement = new_replacement;
    macro->replacement_length = replacement_length;
    macro->builtin = builtin;
    macro->builtin_bits = builtin_bits;
    macro->origin = origin;
    return( 0 );
  }

  macro = (mcpu_macro *)calloc( 1, sizeof(*macro) );
  if( macro == NULL )
  {
    free_argnames( new_argnames, new_argname_lengths, nargs );
    free( new_replacement );
    return( -1 );
  }

  macro->name = dup_text( name, name_length );
  if( macro->name == NULL )
  {
    free_argnames( new_argnames, new_argname_lengths, nargs );
    free( new_replacement );
    free( macro );
    return( -1 );
  }

  macro->name_length = name_length;
  macro->nargs = nargs;
  macro->variadic = variadic;
  macro->argnames = new_argnames;
  macro->argname_lengths = new_argname_lengths;
  macro->replacement = new_replacement;
  macro->replacement_length = replacement_length;
  macro->builtin = builtin;
  macro->builtin_bits = builtin_bits;
  macro->origin = origin;

  h = macro_hash( name, name_length );
  macro->next = table->bucket[h];
  table->bucket[h] = macro;

  return( 0 );
}


int
mcpu_macro_define_object( mcpu_macro_table *table,
                          const __mpu_char16_t *name,
                          size_t name_length,
                          const __mpu_char16_t *replacement,
                          size_t replacement_length,
                          enum mcpu_macro_origin origin )
{
  return( macro_install(table, name, name_length, -1, 0, NULL, NULL,
                        replacement, replacement_length,
                        MCPU_MACRO_BUILTIN_NONE, 0, origin) );
}


int
mcpu_macro_define_builtin( mcpu_macro_table *table,
                           const __mpu_char16_t *name,
                           size_t name_length,
                           enum mcpu_macro_builtin builtin )
{
  if( builtin == MCPU_MACRO_BUILTIN_NONE )
  {
    errno = EINVAL;
    return( -1 );
  }

  return( macro_install(table, name, name_length, -1, 0, NULL, NULL,
                        NULL, 0, builtin, 0, MCPU_MACRO_ORIGIN_BUILTIN) );
}


int
mcpu_macro_define_sized_builtin( mcpu_macro_table *table,
                                 const __mpu_char16_t *name,
                                 size_t name_length,
                                 enum mcpu_macro_builtin builtin,
                                 unsigned bits )
{
  if( builtin < MCPU_MACRO_BUILTIN_REAL_MAX || bits == 0 )
  {
    errno = EINVAL;
    return( -1 );
  }

  return( macro_install(table, name, name_length, -1, 0, NULL, NULL,
                        NULL, 0, builtin, bits, MCPU_MACRO_ORIGIN_BUILTIN) );
}


int
mcpu_macro_define_function( mcpu_macro_table *table,
                            const __mpu_char16_t *name,
                            size_t name_length,
                            const __mpu_char16_t *const *argnames,
                            const size_t *argname_lengths,
                            size_t nargs, int variadic,
                            const __mpu_char16_t *replacement,
                            size_t replacement_length,
                            enum mcpu_macro_origin origin )
{
  if( nargs > (size_t)INT_MAX )
  {
    errno = EOVERFLOW;
    return( -1 );
  }

  return( macro_install(table, name, name_length, (int)nargs, variadic,
                        argnames, argname_lengths,
                        replacement, replacement_length,
                        MCPU_MACRO_BUILTIN_NONE, 0, origin) );
}


int
mcpu_macro_definition_equal( const mcpu_macro *macro,
                             int nargs, int variadic,
                             const __mpu_char16_t *const *argnames,
                             const size_t *argname_lengths,
                             const __mpu_char16_t *replacement,
                             size_t replacement_length )
{
  int i;

  if( macro == NULL || macro->builtin != MCPU_MACRO_BUILTIN_NONE ||
      macro->nargs != nargs || macro->variadic != variadic ||
      macro->replacement_length != replacement_length )
    return( 0 );

  if( replacement_length != 0 &&
      memcmp( macro->replacement, replacement,
              replacement_length * sizeof(__mpu_char16_t) ) != 0 )
    return( 0 );

  if( nargs < 0 )
    return( 1 );

  for( i = 0; i < nargs; ++i )
  {
    if( macro->argname_lengths[i] != argname_lengths[i] ||
        memcmp( macro->argnames[i], argnames[i],
                argname_lengths[i] * sizeof(__mpu_char16_t) ) != 0 )
      return( 0 );
  }

  return( 1 );
}


int
mcpu_macro_undef( mcpu_macro_table *table,
                  const __mpu_char16_t *name, size_t name_length )
{
  mcpu_macro **link;
  unsigned     h;

  if( table == NULL || name == NULL || name_length == 0 )
  {
    errno = EINVAL;
    return( -1 );
  }

  h = macro_hash( name, name_length );
  link = &table->bucket[h];

  while( *link )
  {
    mcpu_macro *macro = *link;

    if( macro->name_length == name_length &&
        memcmp( macro->name, name,
                name_length * sizeof(__mpu_char16_t) ) == 0 )
    {
      *link = macro->next;
      free_macro_contents( macro );
      free( macro );
      return( 1 );
    }

    link = &macro->next;
  }

  return( 0 );
}


static int
is_quote16( __mpu_char16_t c, enum mcpu_language language )
{
  if( c == '"' || c == '`' )
    return( 1 );

  if( c == '\'' && language != MCPU_LANG_DIFF )
    return( 1 );

  return( 0 );
}


static int
is_space16( __mpu_char16_t c )
{
  return( c == ' ' || c == '\t' || c == '\f' || c == '\v' ||
          c == '\r' || c == '\n' );
}


static int
macro_argument_index( const mcpu_macro *macro,
                      const __mpu_char16_t *name, size_t name_length )
{
  int i;

  for( i = 0; i < macro->nargs; ++i )
  {
    if( macro->argname_lengths[i] == name_length &&
        memcmp( macro->argnames[i], name,
                name_length * sizeof(__mpu_char16_t) ) == 0 )
      return( i );
  }

  if( macro->variadic &&
      mcpu_text_equal_ascii(name, name_length, "__VA_ARGS__") )
    return( macro->nargs );

  return( -1 );
}


static void
macro_args_free( mcpu_macro_arg *args, size_t nargs )
{
  size_t i;

  if( args == NULL )
    return;

  for( i = 0; i < nargs; ++i )
    mcpu_text_free( &args[i].expanded );

  free( args );
}


static int
append_macro_arg( mcpu_macro_arg **args, size_t *nargs, size_t *capacity,
                  const __mpu_char16_t *raw, size_t raw_length )
{
  mcpu_macro_arg *new_args;
  size_t          new_capacity;

  if( *nargs == *capacity )
  {
    new_capacity = *capacity ? *capacity * 2 : 4;
    if( new_capacity < *capacity ||
        new_capacity > SIZE_MAX / sizeof(**args) )
    {
      errno = EOVERFLOW;
      return( -1 );
    }

    new_args = (mcpu_macro_arg *)realloc( *args,
                                         new_capacity * sizeof(**args) );
    if( new_args == NULL )
      return( -1 );

    *args = new_args;
    *capacity = new_capacity;
  }

  (*args)[*nargs].raw = raw;
  (*args)[*nargs].raw_length = raw_length;
  mcpu_text_init( &(*args)[*nargs].expanded );
  (*args)[*nargs].expanded_ready = 0;
  ++*nargs;

  return( 0 );
}


static int
parse_macro_args( const __mpu_char16_t *input, size_t length,
                  size_t open_paren, enum mcpu_language language,
                  mcpu_macro_arg **args_out, size_t *nargs_out,
                  size_t *after_call )
{
  mcpu_macro_arg *args = NULL;
  size_t          nargs = 0;
  size_t          capacity = 0;
  size_t          p = open_paren + 1;
  size_t          start = p;
  int             depth = 0;
  __mpu_char16_t  quote = 0;
  int             escaped = 0;

  while( p < length )
  {
    __mpu_char16_t c = input[p];

    if( quote )
    {
      if( escaped )
        escaped = 0;
      else if( c == '\\' )
        escaped = 1;
      else if( c == quote )
        quote = 0;
      else if( c == '\n' && quote == '\'' )
        quote = 0;

      ++p;
      continue;
    }

    if( is_quote16(c, language) )
    {
      quote = c;
      ++p;
      continue;
    }

    if( c == '(' )
    {
      ++depth;
      ++p;
      continue;
    }

    if( c == ')' )
    {
      if( depth != 0 )
      {
        --depth;
        ++p;
        continue;
      }

      if( append_macro_arg(&args, &nargs, &capacity,
                           input + start, p - start) != 0 )
        goto fail;

      *args_out = args;
      *nargs_out = nargs;
      *after_call = p + 1;
      return( 0 );
    }

    if( c == ',' && depth == 0 )
    {
      if( append_macro_arg(&args, &nargs, &capacity,
                           input + start, p - start) != 0 )
        goto fail;
      start = ++p;
      continue;
    }

    ++p;
  }

  errno = EINVAL;

fail:
  macro_args_free( args, nargs );
  return( -1 );
}


static int
prepare_variadic_args( const mcpu_macro *macro,
                       const __mpu_char16_t *input, size_t after_call,
                       mcpu_macro_arg **args_io, size_t *nargs_io )
{
  mcpu_macro_arg *args = *args_io;
  size_t          nargs = *nargs_io;
  size_t          fixed = (size_t)macro->nargs;
  size_t          i;

  if( !macro->variadic || nargs < fixed )
    return( 0 );

  if( nargs == fixed )
  {
    mcpu_macro_arg *new_args;

    new_args = (mcpu_macro_arg *)realloc( args,
                                          (fixed + 1) * sizeof(*args) );
    if( new_args == NULL )
      return( -1 );

    args = new_args;
    args[fixed].raw = input + after_call - 1;
    args[fixed].raw_length = 0;
    mcpu_text_init( &args[fixed].expanded );
    args[fixed].expanded_ready = 0;
    nargs = fixed + 1;
  }
  else
  {
    const __mpu_char16_t *begin = args[fixed].raw;
    const __mpu_char16_t *end = args[nargs - 1].raw +
                                 args[nargs - 1].raw_length;

    for( i = fixed + 1; i < nargs; ++i )
      mcpu_text_free( &args[i].expanded );

    args[fixed].raw = begin;
    args[fixed].raw_length = (size_t)(end - begin);
    nargs = fixed + 1;
  }

  *args_io = args;
  *nargs_io = nargs;
  return( 0 );
}


static int expand_range( mcpu_macro_table *table,
                         const __mpu_char16_t *input, size_t length,
                         enum mcpu_language language,
                         const mcpu_macro_expansion_context *context,
                         mcpu_text *output, unsigned depth );


static int
append_quoted_utf8( mcpu_text *output, const char *s )
{
  mcpu_text text;
  size_t    i;
  int       rc = -1;

  if( output == NULL || s == NULL )
  {
    errno = EINVAL;
    return( -1 );
  }

  mcpu_text_init( &text );
  if( mcpu_text_from_utf8(&text, s) != 0 ||
      mcpu_text_append_char(output, '"') != 0 )
    goto done;

  for( i = 0; i < text.length; ++i )
  {
    switch( text.data[i] )
    {
      case '\\':
      case '"':
        if( mcpu_text_append_char(output, '\\') != 0 ||
            mcpu_text_append_char(output, text.data[i]) != 0 )
          goto done;
        break;

      case '\n':
        if( mcpu_text_append_ascii(output, "\\n") != 0 )
          goto done;
        break;

      case '\r':
        if( mcpu_text_append_ascii(output, "\\r") != 0 )
          goto done;
        break;

      case '\t':
        if( mcpu_text_append_ascii(output, "\\t") != 0 )
          goto done;
        break;

      default:
        if( mcpu_text_append_char(output, text.data[i]) != 0 )
          goto done;
        break;
    }
  }

  if( mcpu_text_append_char(output, '"') != 0 )
    goto done;

  rc = 0;

done:
  mcpu_text_free( &text );
  return( rc );
}


static int
append_unsigned( mcpu_text *output, size_t value )
{
  char buf[64];

  snprintf( buf, sizeof(buf), "%lu", (unsigned long)value );
  return( mcpu_text_append_ascii(output, buf) );
}


static int
expand_builtin( const mcpu_macro *macro,
                const mcpu_macro_expansion_context *context,
                mcpu_text *output )
{
  if( macro == NULL || output == NULL )
  {
    errno = EINVAL;
    return( -1 );
  }

  if( macro->builtin >= MCPU_MACRO_BUILTIN_FILE &&
      macro->builtin <= MCPU_MACRO_BUILTIN_INCLUDE_LEVEL && context == NULL )
  {
    errno = EINVAL;
    return( -1 );
  }

  switch( macro->builtin )
  {
    case MCPU_MACRO_BUILTIN_FILE:
      return( append_quoted_utf8(output, context->filename ?
                                 context->filename : "") );

    case MCPU_MACRO_BUILTIN_LINE:
      return( append_unsigned(output, context->line_number) );

    case MCPU_MACRO_BUILTIN_DATE:
      return( append_quoted_utf8(output, context->date ? context->date : "") );

    case MCPU_MACRO_BUILTIN_TIME:
      return( append_quoted_utf8(output, context->time ? context->time : "") );

    case MCPU_MACRO_BUILTIN_BASE_FILE:
      return( append_quoted_utf8(output, context->base_filename ?
                                 context->base_filename : "") );

    case MCPU_MACRO_BUILTIN_INCLUDE_LEVEL:
      return( append_unsigned(output, context->include_level) );

    case MCPU_MACRO_BUILTIN_REAL_MAX:
    case MCPU_MACRO_BUILTIN_REAL_MIN:
    case MCPU_MACRO_BUILTIN_REAL_EPSILON:
    case MCPU_MACRO_BUILTIN_REAL_MAX_EXP:
    case MCPU_MACRO_BUILTIN_REAL_MIN_EXP:
    case MCPU_MACRO_BUILTIN_REAL_MAX_10_EXP:
    case MCPU_MACRO_BUILTIN_REAL_MIN_10_EXP:
      return( mcpu_predefined_expand_builtin(macro->builtin,
                                              macro->builtin_bits,
                                              output) );

    case MCPU_MACRO_BUILTIN_NONE:
    default:
      errno = EINVAL;
      return( -1 );
  }
}


static int
ensure_arg_expanded( mcpu_macro_table *table, mcpu_macro_arg *arg,
                     enum mcpu_language language,
                     const mcpu_macro_expansion_context *context,
                     unsigned depth )
{
  const __mpu_char16_t *raw;
  size_t                raw_length;

  if( arg->expanded_ready )
    return( 0 );

  raw = arg->raw;
  raw_length = arg->raw_length;

  while( raw_length != 0 && is_space16(*raw) )
  {
    ++raw;
    --raw_length;
  }
  while( raw_length != 0 && is_space16(raw[raw_length - 1]) )
    --raw_length;

  if( expand_range(table, raw, raw_length,
                   language, context,
                   &arg->expanded, depth + 1) != 0 )
    return( -1 );

  arg->expanded_ready = 1;
  return( 0 );
}


static int
append_stringified_arg( mcpu_text *output,
                        const __mpu_char16_t *raw, size_t raw_length,
                        enum mcpu_language language )
{
  size_t         p = 0;
  __mpu_char16_t quote = 0;
  int            escaped = 0;
  int            pending_space = 0;

  while( raw_length != 0 && is_space16(*raw) )
  {
    ++raw;
    --raw_length;
  }
  while( raw_length != 0 && is_space16(raw[raw_length - 1]) )
    --raw_length;

  if( mcpu_text_append_char(output, '"') != 0 )
    return( -1 );

  while( p < raw_length )
  {
    __mpu_char16_t c = raw[p++];

    if( quote == 0 && is_space16(c) )
    {
      pending_space = 1;
      continue;
    }

    if( pending_space )
    {
      if( mcpu_text_append_char(output, ' ') != 0 )
        return( -1 );
      pending_space = 0;
    }

    if( c == '"' || (quote != 0 && c == '\\') )
    {
      if( mcpu_text_append_char(output, '\\') != 0 )
        return( -1 );
    }

    if( mcpu_text_append_char(output, c) != 0 )
      return( -1 );

    if( quote != 0 )
    {
      if( escaped )
        escaped = 0;
      else if( c == '\\' )
        escaped = 1;
      else if( c == quote )
        quote = 0;
    }
    else if( is_quote16(c, language) )
    {
      quote = c;
      escaped = 0;
    }
  }

  return( mcpu_text_append_char(output, '"') );
}


/***************************************************************
  Token concatenation works with
  preprocessing tokens rather than plain character concatenation.
  Parameters adjacent to ## are inserted without prescan, empty
  arguments act as placemarkers, pasted tokens are formed first,
  and the resulting replacement list is rescanned.
 ***************************************************************/
enum mcpu_macro_piece_kind
{
  MCPU_MACRO_PIECE_TOKEN = 0,
  MCPU_MACRO_PIECE_SPACE,
  MCPU_MACRO_PIECE_PASTE,
  MCPU_MACRO_PIECE_PLACEMARKER
};

typedef struct mcpu_macro_piece mcpu_macro_piece;
struct mcpu_macro_piece
{
  enum mcpu_macro_piece_kind kind;
  mcpu_text                  text;
};

typedef struct mcpu_macro_piece_list mcpu_macro_piece_list;
struct mcpu_macro_piece_list
{
  mcpu_macro_piece *piece;
  size_t            count;
  size_t            capacity;
};


static void
macro_piece_list_init( mcpu_macro_piece_list *list )
{
  if( list )
    memset( list, 0, sizeof(*list) );
}


static void
macro_piece_list_free( mcpu_macro_piece_list *list )
{
  size_t i;

  if( list == NULL )
    return;

  for( i = 0; i < list->count; ++i )
    mcpu_text_free( &list->piece[i].text );

  free( list->piece );
  memset( list, 0, sizeof(*list) );
}


static int
macro_piece_list_reserve( mcpu_macro_piece_list *list, size_t need )
{
  mcpu_macro_piece *p;
  size_t            capacity;

  if( need <= list->capacity )
    return( 0 );

  capacity = list->capacity ? list->capacity : 16;
  while( capacity < need )
  {
    if( capacity > SIZE_MAX / 2 )
    {
      errno = EOVERFLOW;
      return( -1 );
    }
    capacity *= 2;
  }

  if( capacity > SIZE_MAX / sizeof(*p) )
  {
    errno = EOVERFLOW;
    return( -1 );
  }

  p = (mcpu_macro_piece *)realloc( list->piece,
                                   capacity * sizeof(*p) );
  if( p == NULL )
    return( -1 );

  list->piece = p;
  list->capacity = capacity;
  return( 0 );
}


static int
macro_piece_list_append( mcpu_macro_piece_list *list,
                         enum mcpu_macro_piece_kind kind,
                         const __mpu_char16_t *text, size_t length )
{
  mcpu_macro_piece *piece;

  if( macro_piece_list_reserve(list, list->count + 1) != 0 )
    return( -1 );

  piece = &list->piece[list->count];
  piece->kind = kind;
  mcpu_text_init( &piece->text );

  if( length != 0 && mcpu_text_append(&piece->text, text, length) != 0 )
  {
    mcpu_text_free( &piece->text );
    return( -1 );
  }

  ++list->count;
  return( 0 );
}


static int
macro_piece_list_append_piece( mcpu_macro_piece_list *list,
                               const mcpu_macro_piece *piece )
{
  return( macro_piece_list_append(list, piece->kind,
                                  piece->text.data, piece->text.length) );
}


static void
macro_piece_list_erase( mcpu_macro_piece_list *list,
                        size_t first, size_t count )
{
  size_t i;

  if( count == 0 || first >= list->count )
    return;

  if( count > list->count - first )
    count = list->count - first;

  for( i = first; i < first + count; ++i )
    mcpu_text_free( &list->piece[i].text );

  if( first + count < list->count )
    memmove( list->piece + first,
             list->piece + first + count,
             (list->count - first - count) * sizeof(*list->piece) );

  list->count -= count;
}


static int
macro_is_digit16( __mpu_char16_t c )
{
  return( c >= '0' && c <= '9' );
}


static size_t
macro_pp_number_end( const __mpu_char16_t *text, size_t length, size_t p )
{
  size_t q = p + 1;

  while( q < length )
  {
    __mpu_char16_t c = text[q];

    if( mcpu_pp_is_identifier_char(c) || c == '.' )
    {
      ++q;
      continue;
    }

    if( (c == '+' || c == '-') && q != p )
    {
      __mpu_char16_t prev = text[q - 1];

      if( prev == 'e' || prev == 'E' || prev == 'p' || prev == 'P' )
      {
        ++q;
        continue;
      }
    }

    break;
  }

  return( q );
}


static size_t
macro_quote_end( const __mpu_char16_t *text, size_t length, size_t p )
{
  __mpu_char16_t quote = text[p++];
  int            escaped = 0;

  while( p < length )
  {
    __mpu_char16_t c = text[p++];

    if( escaped )
      escaped = 0;
    else if( c == '\\' )
      escaped = 1;
    else if( c == quote || c == '\n' )
      break;
  }

  return( p );
}


static size_t
macro_literal_prefix_length( const __mpu_char16_t *text, size_t length,
                             size_t p, enum mcpu_language language )
{
  size_t q = p;

  if( q + 2 < length && text[q] == 'u' && text[q + 1] == '8' &&
      (text[q + 2] == '"' ||
       (text[q + 2] == '\'' && language != MCPU_LANG_DIFF)) )
    return( 2 );

  if( q + 1 < length &&
      (text[q] == 'L' || text[q] == 'u' || text[q] == 'U') &&
      (text[q + 1] == '"' ||
       (text[q + 1] == '\'' && language != MCPU_LANG_DIFF)) )
    return( 1 );

  return( 0 );
}


static int
macro_ascii_at( const __mpu_char16_t *text, size_t length,
                size_t p, const char *s )
{
  size_t i = 0;

  while( s[i] )
  {
    if( p + i >= length ||
        text[p + i] != (__mpu_char16_t)(unsigned char)s[i] )
      return( 0 );
    ++i;
  }

  return( 1 );
}


static size_t
macro_punctuator_length( const __mpu_char16_t *text,
                         size_t length, size_t p )
{
  static const char *const punctuators[] =
  {
    "%:%:",
    ">>=", "<<=", "...",
    "->", "++", "--", "<<", ">>", "<=", ">=", "==", "!=",
    "&&", "||", "*=", "/=", "%=", "+=", "-=", "&=", "^=", "|=",
    "<:", ":>", "<%", "%>", "%:", "##",
    "[", "]", "(", ")", "{", "}", ".", "&", "*", "+", "-",
    "~", "!", "/", "%", "<", ">", "^", "|", "?", ":", ";",
    "=", ",", "#",
    NULL
  };
  size_t i;

  for( i = 0; punctuators[i] != NULL; ++i )
  {
    size_t n = strlen( punctuators[i] );

    if( macro_ascii_at(text, length, p, punctuators[i]) )
      return( n );
  }

  return( 0 );
}


static int
macro_piece_list_tokenize( mcpu_macro_piece_list *list,
                           const __mpu_char16_t *text, size_t length,
                           enum mcpu_language language,
                           int recognize_paste )
{
  size_t p = 0;

  while( p < length )
  {
    size_t q;

    if( is_space16(text[p]) )
    {
      q = p + 1;
      while( q < length && is_space16(text[q]) )
        ++q;

      if( macro_piece_list_append(list, MCPU_MACRO_PIECE_SPACE,
                                  text + p, q - p) != 0 )
        return( -1 );
      p = q;
      continue;
    }

    if( recognize_paste && p + 1 < length &&
        text[p] == '#' && text[p + 1] == '#' )
    {
      if( macro_piece_list_append(list, MCPU_MACRO_PIECE_PASTE,
                                  NULL, 0) != 0 )
        return( -1 );
      p += 2;
      continue;
    }

    {
      size_t prefix_length;

      prefix_length = macro_literal_prefix_length(text, length, p, language);
      if( prefix_length != 0 )
      {
        q = macro_quote_end( text, length, p + prefix_length );
        if( macro_piece_list_append(list, MCPU_MACRO_PIECE_TOKEN,
                                    text + p, q - p) != 0 )
          return( -1 );
        p = q;
        continue;
      }
    }

    if( is_quote16(text[p], language) )
    {
      q = macro_quote_end( text, length, p );
      if( macro_piece_list_append(list, MCPU_MACRO_PIECE_TOKEN,
                                  text + p, q - p) != 0 )
        return( -1 );
      p = q;
      continue;
    }

    if( mcpu_pp_is_identifier_start(text[p]) )
    {
      q = p + 1;
      while( q < length && mcpu_pp_is_identifier_char(text[q]) )
        ++q;

      if( macro_piece_list_append(list, MCPU_MACRO_PIECE_TOKEN,
                                  text + p, q - p) != 0 )
        return( -1 );
      p = q;
      continue;
    }

    if( macro_is_digit16(text[p]) ||
        (text[p] == '.' && p + 1 < length && macro_is_digit16(text[p + 1])) )
    {
      q = macro_pp_number_end( text, length, p );
      if( macro_piece_list_append(list, MCPU_MACRO_PIECE_TOKEN,
                                  text + p, q - p) != 0 )
        return( -1 );
      p = q;
      continue;
    }

    q = macro_punctuator_length( text, length, p );
    if( q != 0 )
    {
      if( macro_piece_list_append(list, MCPU_MACRO_PIECE_TOKEN,
                                  text + p, q) != 0 )
        return( -1 );
      p += q;
      continue;
    }

    if( macro_piece_list_append(list, MCPU_MACRO_PIECE_TOKEN,
                                text + p, 1) != 0 )
      return( -1 );
    ++p;
  }

  return( 0 );
}


static int
macro_piece_is_ascii( const mcpu_macro_piece *piece, const char *s )
{
  if( piece == NULL || piece->kind != MCPU_MACRO_PIECE_TOKEN )
    return( 0 );

  return( mcpu_text_equal_ascii(piece->text.data, piece->text.length, s) );
}


static int
macro_replacement_has_paste( const mcpu_macro *macro,
                             enum mcpu_language language )
{
  size_t         p = 0;
  __mpu_char16_t quote = 0;
  int            escaped = 0;

  while( p < macro->replacement_length )
  {
    __mpu_char16_t c = macro->replacement[p];

    if( quote )
    {
      if( escaped )
        escaped = 0;
      else if( c == '\\' )
        escaped = 1;
      else if( c == quote || c == '\n' )
        quote = 0;
      ++p;
      continue;
    }

    if( is_quote16(c, language) )
    {
      quote = c;
      ++p;
      continue;
    }

    if( c == '#' && p + 1 < macro->replacement_length &&
        macro->replacement[p + 1] == '#' )
      return( 1 );

    ++p;
  }

  return( 0 );
}


static int
macro_replacement_has_va_opt( const mcpu_macro *macro,
                              enum mcpu_language language )
{
  size_t         p = 0;
  __mpu_char16_t quote = 0;
  int            escaped = 0;

  while( p < macro->replacement_length )
  {
    __mpu_char16_t c = macro->replacement[p];

    if( quote )
    {
      if( escaped )
        escaped = 0;
      else if( c == '\\' )
        escaped = 1;
      else if( c == quote || c == '\n' )
        quote = 0;
      ++p;
      continue;
    }

    if( is_quote16(c, language) )
    {
      quote = c;
      ++p;
      continue;
    }

    if( mcpu_pp_is_identifier_start(c) )
    {
      size_t q = p + 1;

      while( q < macro->replacement_length &&
             mcpu_pp_is_identifier_char(macro->replacement[q]) )
        ++q;

      if( mcpu_text_equal_ascii(macro->replacement + p, q - p,
                                "__VA_OPT__") )
        return( 1 );

      p = q;
      continue;
    }

    ++p;
  }

  return( 0 );
}


static int
macro_piece_parameter_index( const mcpu_macro *macro,
                             const mcpu_macro_piece *piece )
{
  if( piece == NULL || piece->kind != MCPU_MACRO_PIECE_TOKEN )
    return( -1 );

  return( macro_argument_index(macro, piece->text.data, piece->text.length) );
}


static int
macro_piece_parameter_is_pasted( const mcpu_macro_piece_list *replacement,
                                 size_t index )
{
  size_t p;

  p = index;
  while( p != 0 )
  {
    --p;
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_SPACE )
      continue;
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_PASTE )
      return( 1 );
    break;
  }

  p = index + 1;
  while( p < replacement->count )
  {
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_SPACE )
    {
      ++p;
      continue;
    }
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_PASTE )
      return( 1 );
    break;
  }

  return( 0 );
}


static int
macro_append_raw_argument( mcpu_macro_piece_list *list,
                           const mcpu_macro_arg *arg,
                           enum mcpu_language language )
{
  const __mpu_char16_t *raw = arg->raw;
  size_t                raw_length = arg->raw_length;

  while( raw_length != 0 && is_space16(*raw) )
  {
    ++raw;
    --raw_length;
  }
  while( raw_length != 0 && is_space16(raw[raw_length - 1]) )
    --raw_length;

  if( raw_length == 0 )
    return( macro_piece_list_append(list, MCPU_MACRO_PIECE_PLACEMARKER,
                                    NULL, 0) );

  return( macro_piece_list_tokenize(list, raw, raw_length,
                                    language, 0) );
}


static int
macro_append_expanded_argument( mcpu_macro_table *table,
                                mcpu_macro_piece_list *list,
                                mcpu_macro_arg *arg,
                                enum mcpu_language language,
                                const mcpu_macro_expansion_context *context,
                                unsigned depth )
{
  if( ensure_arg_expanded(table, arg, language, context, depth) != 0 )
    return( -1 );

  return( macro_piece_list_tokenize(list,
                                    arg->expanded.data,
                                    arg->expanded.length,
                                    language, 0) );
}


static int
macro_append_stringified_argument( mcpu_macro_piece_list *list,
                                   const mcpu_macro_arg *arg,
                                   enum mcpu_language language )
{
  mcpu_text stringified;
  int       rc;

  mcpu_text_init( &stringified );
  rc = append_stringified_arg( &stringified,
                               arg->raw, arg->raw_length,
                               language );
  if( rc == 0 )
    rc = macro_piece_list_append( list, MCPU_MACRO_PIECE_TOKEN,
                                  stringified.data, stringified.length );

  mcpu_text_free( &stringified );
  return( rc );
}


static int macro_resolve_pastes(
                   mcpu_macro_piece_list *list,
                   enum mcpu_language language,
                   const mcpu_macro_expansion_context *context );
static int macro_pieces_to_text(
                   const mcpu_macro_piece_list *list, mcpu_text *text );


static int
macro_va_opt_bounds( const mcpu_macro_piece_list *replacement,
                     size_t index, size_t limit,
                     size_t *content_start, size_t *content_end,
                     size_t *after )
{
  size_t p;
  int    depth;

  if( replacement == NULL || index >= limit ||
      !macro_piece_is_ascii(&replacement->piece[index], "__VA_OPT__") )
  {
    errno = EINVAL;
    return( -1 );
  }

  p = index + 1;
  while( p < limit && replacement->piece[p].kind == MCPU_MACRO_PIECE_SPACE )
    ++p;

  if( p >= limit || !macro_piece_is_ascii(&replacement->piece[p], "(") )
  {
    errno = EINVAL;
    return( -1 );
  }

  *content_start = ++p;
  depth = 1;
  while( p < limit )
  {
    if( macro_piece_is_ascii(&replacement->piece[p], "(") )
      ++depth;
    else if( macro_piece_is_ascii(&replacement->piece[p], ")") )
    {
      --depth;
      if( depth == 0 )
      {
        *content_end = p;
        *after = p + 1;
        return( 0 );
      }
    }
    ++p;
  }

  errno = EINVAL;
  return( -1 );
}


static int
macro_va_opt_is_pasted( const mcpu_macro_piece_list *replacement,
                        size_t index, size_t after, size_t limit )
{
  size_t p;

  p = index;
  while( p != 0 )
  {
    --p;
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_SPACE )
      continue;
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_PASTE )
      return( 1 );
    break;
  }

  p = after;
  while( p < limit )
  {
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_SPACE )
    {
      ++p;
      continue;
    }
    if( replacement->piece[p].kind == MCPU_MACRO_PIECE_PASTE )
      return( 1 );
    break;
  }

  return( 0 );
}


static int
macro_piece_list_has_token( const mcpu_macro_piece_list *list )
{
  size_t i;

  for( i = 0; i < list->count; ++i )
  {
    if( list->piece[i].kind == MCPU_MACRO_PIECE_TOKEN )
      return( 1 );
  }

  return( 0 );
}


static int
macro_piece_list_append_range( mcpu_macro_piece_list *dst,
                               const mcpu_macro_piece_list *src )
{
  size_t i;

  for( i = 0; i < src->count; ++i )
  {
    if( macro_piece_list_append_piece(dst, &src->piece[i]) != 0 )
      return( -1 );
  }

  return( 0 );
}


static int
macro_variadic_has_tokens( mcpu_macro_table *table,
                           const mcpu_macro *macro,
                           mcpu_macro_arg *args,
                           enum mcpu_language language,
                           const mcpu_macro_expansion_context *context,
                           unsigned depth )
{
  mcpu_macro_arg *arg;
  size_t          i;

  if( !macro->variadic )
    return( 0 );

  arg = &args[macro->nargs];
  if( ensure_arg_expanded(table, arg, language, context, depth) != 0 )
    return( -1 );

  for( i = 0; i < arg->expanded.length; ++i )
  {
    if( !is_space16(arg->expanded.data[i]) )
      return( 1 );
  }

  return( 0 );
}


static int macro_substitute_piece_range(
                   mcpu_macro_table *table,
                   mcpu_macro *macro,
                   mcpu_macro_arg *args,
                   const mcpu_macro_piece_list *replacement,
                   size_t begin, size_t end,
                   enum mcpu_language language,
                   const mcpu_macro_expansion_context *context,
                   unsigned depth,
                   mcpu_macro_piece_list *substituted );


static int
macro_append_stringified_va_opt( mcpu_macro_table *table,
                                 mcpu_macro *macro,
                                 mcpu_macro_arg *args,
                                 const mcpu_macro_piece_list *replacement,
                                 size_t content_start, size_t content_end,
                                 enum mcpu_language language,
                                 const mcpu_macro_expansion_context *context,
                                 unsigned depth,
                                 mcpu_macro_piece_list *substituted )
{
  mcpu_macro_piece_list content;
  mcpu_text             text;
  mcpu_text             stringified;
  int                   nonempty;
  int                   rc = -1;

  macro_piece_list_init( &content );
  mcpu_text_init( &text );
  mcpu_text_init( &stringified );

  nonempty = macro_variadic_has_tokens(table, macro, args,
                                       language, context, depth);
  if( nonempty < 0 )
    goto done;

  if( nonempty )
  {
    if( macro_substitute_piece_range(table, macro, args, replacement,
                                     content_start, content_end,
                                     language, context, depth,
                                     &content) != 0 ||
        macro_resolve_pastes(&content, language, context) != 0 ||
        macro_pieces_to_text(&content, &text) != 0 )
      goto done;
  }

  if( append_stringified_arg(&stringified,
                             text.data, text.length, language) != 0 ||
      macro_piece_list_append(substituted, MCPU_MACRO_PIECE_TOKEN,
                              stringified.data, stringified.length) != 0 )
    goto done;

  rc = 0;

done:
  mcpu_text_free( &stringified );
  mcpu_text_free( &text );
  macro_piece_list_free( &content );
  return( rc );
}


static int
macro_substitute_piece_range( mcpu_macro_table *table,
                              mcpu_macro *macro,
                              mcpu_macro_arg *args,
                              const mcpu_macro_piece_list *replacement,
                              size_t begin, size_t end,
                              enum mcpu_language language,
                              const mcpu_macro_expansion_context *context,
                              unsigned depth,
                              mcpu_macro_piece_list *substituted )
{
  size_t i = begin;

  while( i < end )
  {
    const mcpu_macro_piece *piece = &replacement->piece[i];
    int                     argno;

    if( piece->kind == MCPU_MACRO_PIECE_SPACE ||
        piece->kind == MCPU_MACRO_PIECE_PASTE )
    {
      if( macro_piece_list_append_piece(substituted, piece) != 0 )
        return( -1 );
      ++i;
      continue;
    }

    if( macro_piece_is_ascii(piece, "#") )
    {
      size_t j = i + 1;

      while( j < end &&
             replacement->piece[j].kind == MCPU_MACRO_PIECE_SPACE )
        ++j;

      if( j >= end )
      {
        errno = EINVAL;
        return( -1 );
      }

      argno = macro_piece_parameter_index( macro, &replacement->piece[j] );
      if( argno >= 0 )
      {
        if( macro_append_stringified_argument(substituted,
                                              &args[argno], language) != 0 )
          return( -1 );
        i = j + 1;
        continue;
      }

      if( macro_piece_is_ascii(&replacement->piece[j], "__VA_OPT__") )
      {
        size_t content_start;
        size_t content_end;
        size_t after;

        if( macro_va_opt_bounds(replacement, j, end,
                                &content_start, &content_end, &after) != 0 ||
            macro_append_stringified_va_opt(table, macro, args, replacement,
                                            content_start, content_end,
                                            language, context, depth,
                                            substituted) != 0 )
          return( -1 );

        i = after;
        continue;
      }

      errno = EINVAL;
      return( -1 );
    }

    if( macro_piece_is_ascii(piece, "__VA_OPT__") )
    {
      mcpu_macro_piece_list content;
      size_t                content_start;
      size_t                content_end;
      size_t                after;
      int                   nonempty;
      int                   pasted;
      int                   rc = -1;

      macro_piece_list_init( &content );
      if( macro_va_opt_bounds(replacement, i, end,
                              &content_start, &content_end, &after) != 0 )
        goto va_done;

      nonempty = macro_variadic_has_tokens(table, macro, args,
                                           language, context, depth);
      if( nonempty < 0 )
        goto va_done;

      pasted = macro_va_opt_is_pasted(replacement, i, after, end);
      if( nonempty )
      {
        if( macro_substitute_piece_range(table, macro, args, replacement,
                                         content_start, content_end,
                                         language, context, depth,
                                         &content) != 0 ||
            macro_resolve_pastes(&content, language, context) != 0 )
          goto va_done;

        if( pasted && !macro_piece_list_has_token(&content) )
        {
          if( macro_piece_list_append(substituted,
                                      MCPU_MACRO_PIECE_PLACEMARKER,
                                      NULL, 0) != 0 )
            goto va_done;
        }
        else if( macro_piece_list_append_range(substituted, &content) != 0 )
          goto va_done;
      }
      else if( pasted &&
               macro_piece_list_append(substituted,
                                       MCPU_MACRO_PIECE_PLACEMARKER,
                                       NULL, 0) != 0 )
        goto va_done;

      rc = 0;

va_done:
      macro_piece_list_free( &content );
      if( rc != 0 )
        return( -1 );
      i = after;
      continue;
    }

    argno = macro_piece_parameter_index( macro, piece );
    if( argno >= 0 )
    {
      if( macro_piece_parameter_is_pasted(replacement, i) )
      {
        if( macro_append_raw_argument(substituted,
                                      &args[argno], language) != 0 )
          return( -1 );
      }
      else
      {
        if( macro_append_expanded_argument(table, substituted,
                                           &args[argno], language,
                                           context, depth) != 0 )
          return( -1 );
      }

      ++i;
      continue;
    }

    if( macro_piece_list_append_piece(substituted, piece) != 0 )
      return( -1 );
    ++i;
  }

  return( 0 );
}


static int
macro_build_function_pieces( mcpu_macro_table *table,
                             mcpu_macro *macro,
                             mcpu_macro_arg *args,
                             enum mcpu_language language,
                             const mcpu_macro_expansion_context *context,
                             unsigned depth,
                             mcpu_macro_piece_list *substituted )
{
  mcpu_macro_piece_list replacement;
  int                   rc = -1;

  macro_piece_list_init( &replacement );
  if( macro_piece_list_tokenize(&replacement,
                                macro->replacement,
                                macro->replacement_length,
                                language, 1) != 0 )
    goto done;

  if( macro_substitute_piece_range(table, macro, args, &replacement,
                                   0, replacement.count,
                                   language, context, depth,
                                   substituted) != 0 )
    goto done;

  rc = 0;

done:
  macro_piece_list_free( &replacement );
  return( rc );
}


static void
macro_normalize_paste_spacing( mcpu_macro_piece_list *list )
{
  size_t i = 0;

  while( i < list->count )
  {
    if( list->piece[i].kind == MCPU_MACRO_PIECE_SPACE &&
        ((i != 0 && list->piece[i - 1].kind == MCPU_MACRO_PIECE_PASTE) ||
         (i + 1 < list->count &&
          list->piece[i + 1].kind == MCPU_MACRO_PIECE_PASTE)) )
    {
      macro_piece_list_erase( list, i, 1 );
      if( i != 0 )
        --i;
      continue;
    }
    ++i;
  }

  i = 1;
  while( i < list->count )
  {
    if( list->piece[i - 1].kind == MCPU_MACRO_PIECE_PASTE &&
        list->piece[i].kind == MCPU_MACRO_PIECE_PASTE )
    {
      /***********************************************************
        GNU CPP accepts a run of adjacent ## operators as one paste
        operator.  Preserve that long-standing behavior.
       ***********************************************************/
      macro_piece_list_erase( list, i, 1 );
      continue;
    }
    ++i;
  }
}


static int
macro_paste_is_single_token( const mcpu_text *text,
                             enum mcpu_language language )
{
  mcpu_macro_piece_list tokens;
  int                   valid;

  macro_piece_list_init( &tokens );
  if( macro_piece_list_tokenize(&tokens,
                                text->data, text->length,
                                language, 0) != 0 )
  {
    macro_piece_list_free( &tokens );
    return( -1 );
  }

  valid = tokens.count == 1 &&
          tokens.piece[0].kind == MCPU_MACRO_PIECE_TOKEN;
  macro_piece_list_free( &tokens );
  return( valid );
}


static int
macro_warn_invalid_paste( const mcpu_macro_piece *left,
                          const mcpu_macro_piece *right,
                          const mcpu_macro_expansion_context *context )
{
  char *l = mcpu_text_to_utf8( left->text.data, left->text.length );
  char *r = mcpu_text_to_utf8( right->text.data, right->text.length );

  int rc;

  rc = mcpp_diagnostic_warning(
         context ? context->options : NULL,
         context && context->filename ? context->filename : "<input>",
         context ? context->line_number : 0,
         "pasting \"%s\" and \"%s\" does not give a valid preprocessing token",
         l ? l : "?", r ? r : "?" );

  free( l );
  free( r );
  return( rc );
}


static int
macro_resolve_pastes( mcpu_macro_piece_list *list,
                      enum mcpu_language language,
                      const mcpu_macro_expansion_context *context )
{
  size_t i;

  macro_normalize_paste_spacing( list );

  for( ;; )
  {
    for( i = 0; i < list->count; ++i )
    {
      if( list->piece[i].kind == MCPU_MACRO_PIECE_PASTE )
        break;
    }

    if( i == list->count )
      break;

    if( i == 0 || i + 1 >= list->count ||
        list->piece[i - 1].kind == MCPU_MACRO_PIECE_SPACE ||
        list->piece[i + 1].kind == MCPU_MACRO_PIECE_SPACE ||
        list->piece[i - 1].kind == MCPU_MACRO_PIECE_PASTE ||
        list->piece[i + 1].kind == MCPU_MACRO_PIECE_PASTE )
    {
      errno = EINVAL;
      return( -1 );
    }

    if( list->piece[i - 1].kind == MCPU_MACRO_PIECE_PLACEMARKER &&
        list->piece[i + 1].kind == MCPU_MACRO_PIECE_PLACEMARKER )
    {
      macro_piece_list_erase( list, i, 2 );
      continue;
    }

    if( list->piece[i - 1].kind == MCPU_MACRO_PIECE_PLACEMARKER )
    {
      macro_piece_list_erase( list, i - 1, 2 );
      continue;
    }

    if( list->piece[i + 1].kind == MCPU_MACRO_PIECE_PLACEMARKER )
    {
      macro_piece_list_erase( list, i, 2 );
      continue;
    }

    {
      mcpu_text pasted;
      int       valid;

      mcpu_text_init( &pasted );
      if( mcpu_text_append(&pasted,
                           list->piece[i - 1].text.data,
                           list->piece[i - 1].text.length) != 0 ||
          mcpu_text_append(&pasted,
                           list->piece[i + 1].text.data,
                           list->piece[i + 1].text.length) != 0 )
      {
        mcpu_text_free( &pasted );
        return( -1 );
      }

      valid = macro_paste_is_single_token( &pasted, language );
      if( valid < 0 )
      {
        mcpu_text_free( &pasted );
        return( -1 );
      }

      if( !valid )
      {
        /***********************************************************
          GNU CPP documents this case as a diagnostic followed by
          emission of the two original tokens.  Whitespace between
          them is unspecified, so keep them adjacent and discard ##.
         ***********************************************************/
        if( macro_warn_invalid_paste(&list->piece[i - 1],
                                     &list->piece[i + 1], context) != 0 )
        {
          mcpu_text_free( &pasted );
          return( -1 );
        }
        mcpu_text_free( &pasted );
        macro_piece_list_erase( list, i, 1 );
        continue;
      }

      mcpu_text_free( &list->piece[i - 1].text );
      list->piece[i - 1].text = pasted;
      list->piece[i - 1].kind = MCPU_MACRO_PIECE_TOKEN;
      macro_piece_list_erase( list, i, 2 );
    }
  }

  i = 0;
  while( i < list->count )
  {
    if( list->piece[i].kind == MCPU_MACRO_PIECE_PLACEMARKER )
    {
      macro_piece_list_erase( list, i, 1 );
      continue;
    }
    ++i;
  }

  return( 0 );
}


static int
macro_pieces_to_text( const mcpu_macro_piece_list *list, mcpu_text *text )
{
  size_t i;
  int    previous_space = 0;

  for( i = 0; i < list->count; ++i )
  {
    if( list->piece[i].kind == MCPU_MACRO_PIECE_PASTE ||
        list->piece[i].kind == MCPU_MACRO_PIECE_PLACEMARKER )
    {
      errno = EINVAL;
      return( -1 );
    }

    if( list->piece[i].kind == MCPU_MACRO_PIECE_SPACE )
    {
      /***********************************************************
        Removal of an empty parameter, placemarker or __VA_OPT__
        fragment can make two replacement-list space pieces
        adjacent.  They are one logical whitespace separator.

        Preserve the text of a single space piece: it may come from
        inside an actual macro argument, whose formatting is not part
        of replacement-list normalization.
       ***********************************************************/
      if( previous_space )
        continue;
      previous_space = 1;
    }
    else
      previous_space = 0;

    if( mcpu_text_append(text,
                         list->piece[i].text.data,
                         list->piece[i].text.length) != 0 )
      return( -1 );
  }

  return( 0 );
}


static int
expand_function_macro_with_paste( mcpu_macro_table *table,
                                  mcpu_macro *macro,
                                  mcpu_macro_arg *args,
                                  enum mcpu_language language,
                                  const mcpu_macro_expansion_context *context,
                                  mcpu_text *output, unsigned depth )
{
  mcpu_macro_piece_list pieces;
  mcpu_text             substituted;
  int                   rc = -1;

  macro_piece_list_init( &pieces );
  mcpu_text_init( &substituted );

  if( macro_build_function_pieces(table, macro, args,
                                  language, context, depth,
                                  &pieces) != 0 ||
      macro_resolve_pastes(&pieces, language, context) != 0 ||
      macro_pieces_to_text(&pieces, &substituted) != 0 )
    goto done;

  macro->expanding = 1;
  rc = expand_range( table, substituted.data, substituted.length,
                     language, context, output, depth + 1 );
  macro->expanding = 0;

done:
  macro->expanding = 0;
  mcpu_text_free( &substituted );
  macro_piece_list_free( &pieces );
  return( rc );
}


static int
expand_object_macro_with_paste( mcpu_macro_table *table,
                                mcpu_macro *macro,
                                enum mcpu_language language,
                                const mcpu_macro_expansion_context *context,
                                mcpu_text *output, unsigned depth )
{
  mcpu_macro_piece_list pieces;
  mcpu_text             substituted;
  int                   rc = -1;

  macro_piece_list_init( &pieces );
  mcpu_text_init( &substituted );

  if( macro_piece_list_tokenize(&pieces,
                                macro->replacement,
                                macro->replacement_length,
                                language, 1) != 0 ||
      macro_resolve_pastes(&pieces, language, context) != 0 ||
      macro_pieces_to_text(&pieces, &substituted) != 0 )
    goto done;

  macro->expanding = 1;
  rc = expand_range( table, substituted.data, substituted.length,
                     language, context, output, depth + 1 );
  macro->expanding = 0;

done:
  macro->expanding = 0;
  mcpu_text_free( &substituted );
  macro_piece_list_free( &pieces );
  return( rc );
}


static int
expand_function_macro( mcpu_macro_table *table, mcpu_macro *macro,
                       mcpu_macro_arg *args, size_t nargs,
                       enum mcpu_language language,
                       const mcpu_macro_expansion_context *context,
                       mcpu_text *output, unsigned depth )
{
  mcpu_text substituted;
  size_t    p = 0;
  size_t    i;
  int       rc = -1;

  if( !macro->variadic && macro->nargs == 0 && nargs == 1 )
  {
    int all_space = 1;

    for( i = 0; i < args[0].raw_length; ++i )
    {
      if( !is_space16(args[0].raw[i]) )
      {
        all_space = 0;
        break;
      }
    }

    if( all_space )
      nargs = 0;
  }

  if( nargs < (size_t)macro->nargs + (macro->variadic ? 1U : 0U) )
  {
    char *name = mcpu_text_to_utf8( macro->name, macro->name_length );
    fprintf( stderr, "%s:%u: error: macro '%s' used with too few arguments\n",
             context && context->filename ? context->filename : "<input>",
             context ? context->line_number : 0,
             name ? name : "?" );
    free( name );
    errno = EINVAL;
    return( -1 );
  }

  if( !macro->variadic && nargs > (size_t)macro->nargs )
  {
    char *name = mcpu_text_to_utf8( macro->name, macro->name_length );
    fprintf( stderr, "%s:%u: error: macro '%s' used with too many arguments\n",
             context && context->filename ? context->filename : "<input>",
             context ? context->line_number : 0,
             name ? name : "?" );
    free( name );
    errno = EINVAL;
    return( -1 );
  }

  if( macro_replacement_has_paste(macro, language) ||
      macro_replacement_has_va_opt(macro, language) )
    return( expand_function_macro_with_paste(table, macro, args,
                                             language, context,
                                             output, depth) );

  mcpu_text_init( &substituted );

  while( p < macro->replacement_length )
  {
    if( is_quote16(macro->replacement[p], language) )
    {
      __mpu_char16_t quote = macro->replacement[p];
      int            escaped = 0;
      int            first = 1;

      do
      {
        __mpu_char16_t c = macro->replacement[p++];

        if( mcpu_text_append_char(&substituted, c) != 0 )
          goto substituted_fail;

        if( first )
          first = 0;
        else if( escaped )
          escaped = 0;
        else if( c == '\\' )
          escaped = 1;
        else if( c == quote )
          break;
        else if( c == '\n' )
          break;
      }
      while( p < macro->replacement_length );

      continue;
    }

    if( macro->replacement[p] == '#' )
    {
      size_t q = p + 1;
      size_t start;
      int    argno;

      if( q < macro->replacement_length && macro->replacement[q] == '#' )
      {
        errno = EINVAL;
        goto substituted_fail;
      }

      while( q < macro->replacement_length && is_space16(macro->replacement[q]) )
        ++q;

      if( q >= macro->replacement_length ||
          !mcpu_pp_is_identifier_start(macro->replacement[q]) )
      {
        errno = EINVAL;
        goto substituted_fail;
      }

      start = q++;
      while( q < macro->replacement_length &&
             mcpu_pp_is_identifier_char(macro->replacement[q]) )
        ++q;

      argno = macro_argument_index( macro,
                                    macro->replacement + start, q - start );
      if( argno < 0 )
      {
        errno = EINVAL;
        goto substituted_fail;
      }

      if( append_stringified_arg(&substituted,
                                 args[argno].raw,
                                 args[argno].raw_length,
                                 language) != 0 )
        goto substituted_fail;

      p = q;
      continue;
    }

    if( mcpu_pp_is_identifier_start(macro->replacement[p]) )
    {
      size_t start = p++;
      int    argno;

      while( p < macro->replacement_length &&
             mcpu_pp_is_identifier_char(macro->replacement[p]) )
        ++p;

      argno = macro_argument_index( macro,
                                    macro->replacement + start, p - start );
      if( argno >= 0 )
      {
        /***********************************************************
          Ordinary parameter occurrences use
          the macro-expanded actual argument.  Stringified occurrences
          above deliberately use the raw spelling and therefore do not
          force this expansion.
         ***********************************************************/
        if( ensure_arg_expanded(table, &args[argno], language,
                                context, depth) != 0 )
          goto substituted_fail;

        if( mcpu_text_append(&substituted,
                             args[argno].expanded.data,
                             args[argno].expanded.length) != 0 )
          goto substituted_fail;
      }
      else if( mcpu_text_append(&substituted,
                                macro->replacement + start, p - start) != 0 )
        goto substituted_fail;

      continue;
    }

    if( mcpu_text_append_char(&substituted, macro->replacement[p++]) != 0 )
      goto substituted_fail;
  }

  macro->expanding = 1;
  rc = expand_range( table, substituted.data, substituted.length,
                     language, context,
                     output, depth + 1 );

substituted_fail:
  mcpu_text_free( &substituted );

  macro->expanding = 0;
  return( rc );
}


static int
expand_range( mcpu_macro_table *table,
              const __mpu_char16_t *input, size_t length,
              enum mcpu_language language,
              const mcpu_macro_expansion_context *context,
              mcpu_text *output, unsigned depth )
{
  size_t p = 0;

  if( depth > MCPU_CPP_MACRO_EXPANSION_LIMIT )
  {
    errno = ELOOP;
    return( -1 );
  }

  while( p < length )
  {
    if( is_quote16(input[p], language) )
    {
      __mpu_char16_t quote = input[p];
      int            escaped = 0;
      int            first = 1;

      do
      {
        __mpu_char16_t c = input[p++];

        if( mcpu_text_append_char(output, c) != 0 )
          return( -1 );

        if( first )
          first = 0;
        else if( escaped )
          escaped = 0;
        else if( c == '\\' )
          escaped = 1;
        else if( c == quote )
          break;
        else if( c == '\n' )
          break;
      }
      while( p < length );

      continue;
    }

    if( mcpu_pp_is_identifier_start(input[p]) )
    {
      size_t      start = p++;
      mcpu_macro *macro;

      while( p < length && mcpu_pp_is_identifier_char(input[p]) )
        ++p;

      macro = mcpu_macro_find( table, input + start, p - start );
      if( macro && !macro->expanding )
      {
        if( macro->builtin != MCPU_MACRO_BUILTIN_NONE )
        {
          if( expand_builtin(macro, context, output) != 0 )
            return( -1 );
          continue;
        }

        if( macro->nargs < 0 )
        {
          int rc;

          if( macro_replacement_has_paste(macro, language) )
            rc = expand_object_macro_with_paste(table, macro,
                                                language, context,
                                                output, depth);
          else
          {
            macro->expanding = 1;
            rc = expand_range( table,
                               macro->replacement,
                               macro->replacement_length,
                               language, context,
                               output, depth + 1 );
            macro->expanding = 0;
          }

          if( rc != 0 )
            return( -1 );
          continue;
        }
        else
        {
          size_t q = p;

          while( q < length && is_space16(input[q]) )
            ++q;

          if( q < length && input[q] == '(' )
          {
            mcpu_macro_arg *args = NULL;
            size_t          nargs = 0;
            size_t          after_call;
            int             rc;

            if( parse_macro_args(input, length, q, language,
                                 &args, &nargs, &after_call) != 0 )
            {
              char *name = mcpu_text_to_utf8( macro->name,
                                              macro->name_length );
              fprintf( stderr,
                       "%s:%u: error: unterminated argument list for macro '%s'\n",
                       context && context->filename ? context->filename : "<input>",
                       context ? context->line_number : 0,
                       name ? name : "?" );
              free( name );
              return( -1 );
            }

            if( prepare_variadic_args(macro, input, after_call,
                                      &args, &nargs) != 0 )
            {
              macro_args_free( args, nargs );
              return( -1 );
            }

            rc = expand_function_macro( table, macro, args, nargs,
                                        language, context,
                                        output, depth );
            macro_args_free( args, nargs );
            if( rc != 0 )
              return( -1 );

            p = after_call;
            continue;
          }
        }
      }

      if( mcpu_text_append(output, input + start, p - start) != 0 )
        return( -1 );

      continue;
    }

    if( mcpu_text_append_char(output, input[p++]) != 0 )
      return( -1 );
  }

  return( 0 );
}



static int
macro_name_compare( const void *a, const void *b )
{
  const mcpu_macro *ma = *(const mcpu_macro * const *)a;
  const mcpu_macro *mb = *(const mcpu_macro * const *)b;
  size_t            n;
  size_t            i;

  n = ma->name_length < mb->name_length ? ma->name_length : mb->name_length;
  for( i = 0; i < n; ++i )
  {
    if( ma->name[i] < mb->name[i] )
      return( -1 );
    if( ma->name[i] > mb->name[i] )
      return( 1 );
  }

  if( ma->name_length < mb->name_length )
    return( -1 );
  if( ma->name_length > mb->name_length )
    return( 1 );
  return( 0 );
}


int
mcpu_macro_dump( const mcpu_macro_table *table, FILE *stream,
                 int include_predefined )
{
  mcpu_macro **list;
  size_t       predefined_count = 0;
  size_t       other_count = 0;
  size_t       count;
  size_t       i;
  size_t       k = 0;
  size_t       other_begin;

  if( table == NULL || stream == NULL )
  {
    errno = EINVAL;
    return( -1 );
  }

  for( i = 0; i < MCPU_CPP_MACRO_BUCKETS; ++i )
  {
    const mcpu_macro *macro;
    for( macro = table->bucket[i]; macro; macro = macro->next )
    {
      /* Context-dependent special macros are not useful in a static dump. */
      if( macro->builtin != MCPU_MACRO_BUILTIN_NONE &&
          macro->builtin < MCPU_MACRO_BUILTIN_REAL_MAX )
        continue;

      if( macro->origin == MCPU_MACRO_ORIGIN_BUILTIN )
        ++predefined_count;
      else
        ++other_count;
    }
  }

  count = other_count + (include_predefined ? predefined_count : 0);
  list = count ? (mcpu_macro **)calloc( count, sizeof(*list) ) : NULL;
  if( count != 0 && list == NULL )
    return( -1 );

  if( include_predefined )
  {
    for( i = 0; i < MCPU_CPP_MACRO_BUCKETS; ++i )
    {
      mcpu_macro *macro;
      for( macro = table->bucket[i]; macro; macro = macro->next )
      {
        if( (macro->builtin == MCPU_MACRO_BUILTIN_NONE ||
             macro->builtin >= MCPU_MACRO_BUILTIN_REAL_MAX) &&
            macro->origin == MCPU_MACRO_ORIGIN_BUILTIN )
          list[k++] = macro;
      }
    }
  }

  other_begin = k;
  for( i = 0; i < MCPU_CPP_MACRO_BUCKETS; ++i )
  {
    mcpu_macro *macro;
    for( macro = table->bucket[i]; macro; macro = macro->next )
    {
      if( (macro->builtin == MCPU_MACRO_BUILTIN_NONE ||
           macro->builtin >= MCPU_MACRO_BUILTIN_REAL_MAX) &&
          macro->origin != MCPU_MACRO_ORIGIN_BUILTIN )
        list[k++] = macro;
    }
  }

  if( include_predefined && predefined_count > 1 )
    qsort( list, predefined_count, sizeof(*list), macro_name_compare );
  if( other_count > 1 )
    qsort( list + other_begin, other_count, sizeof(*list), macro_name_compare );

  for( i = 0; i < count; ++i )
  {
    mcpu_macro *macro = list[i];
    char       *name = mcpu_text_to_utf8( macro->name, macro->name_length );
    char       *replacement = NULL;
    mcpu_text   generated;
    size_t      replacement_length;
    int         j;

    mcpu_text_init( &generated );
    if( macro->builtin == MCPU_MACRO_BUILTIN_NONE )
    {
      replacement = mcpu_text_to_utf8( macro->replacement,
                                       macro->replacement_length );
      replacement_length = macro->replacement_length;
    }
    else
    {
      if( expand_builtin(macro, NULL, &generated) != 0 )
      {
        free( name );
        mcpu_text_free( &generated );
        free( list );
        return( -1 );
      }
      replacement = mcpu_text_to_utf8( generated.data, generated.length );
      replacement_length = generated.length;
    }

    if( name == NULL || replacement == NULL )
    {
      free( name );
      free( replacement );
      mcpu_text_free( &generated );
      free( list );
      return( -1 );
    }

    if( fprintf(stream, "#define %s", name) < 0 )
      goto io_error;

    if( macro->nargs >= 0 )
    {
      if( fputc('(', stream) == EOF )
        goto io_error;
      for( j = 0; j < macro->nargs; ++j )
      {
        char *arg = mcpu_text_to_utf8( macro->argnames[j],
                                       macro->argname_lengths[j] );
        if( arg == NULL )
          goto io_error;
        if( j != 0 && fputc(',', stream) == EOF )
        {
          free( arg );
          goto io_error;
        }
        if( fputs(arg, stream) == EOF )
        {
          free( arg );
          goto io_error;
        }
        free( arg );
      }
      if( macro->variadic )
      {
        if( macro->nargs != 0 && fputc(',', stream) == EOF )
          goto io_error;
        if( fputs("...", stream) == EOF )
          goto io_error;
      }
      if( fputc(')', stream) == EOF )
        goto io_error;
    }

    if( replacement_length != 0 )
    {
      if( fputc(' ', stream) == EOF || fputs(replacement, stream) == EOF )
        goto io_error;
    }

    if( fputc('\n', stream) == EOF )
      goto io_error;

    free( name );
    free( replacement );
    mcpu_text_free( &generated );
    continue;

io_error:
    free( name );
    free( replacement );
    mcpu_text_free( &generated );
    free( list );
    return( -1 );
  }

  free( list );
  return( ferror(stream) ? -1 : 0 );
}


int
mcpu_macro_dump_text( const mcpu_macro_table *table, mcpu_text *output,
                      const char *line_filename )
{
  mcpu_macro **list;
  size_t       count = 0;
  size_t       i;
  size_t       k = 0;

  if( table == NULL || output == NULL )
  {
    errno = EINVAL;
    return( -1 );
  }

  for( i = 0; i < MCPU_CPP_MACRO_BUCKETS; ++i )
  {
    const mcpu_macro *macro;

    for( macro = table->bucket[i]; macro; macro = macro->next )
      if( macro->builtin == MCPU_MACRO_BUILTIN_NONE ||
          macro->builtin >= MCPU_MACRO_BUILTIN_REAL_MAX )
        ++count;
  }

  list = count ? (mcpu_macro **)calloc( count, sizeof(*list) ) : NULL;
  if( count != 0 && list == NULL )
    return( -1 );

  for( i = 0; i < MCPU_CPP_MACRO_BUCKETS; ++i )
  {
    mcpu_macro *macro;

    for( macro = table->bucket[i]; macro; macro = macro->next )
      if( macro->builtin == MCPU_MACRO_BUILTIN_NONE ||
          macro->builtin >= MCPU_MACRO_BUILTIN_REAL_MAX )
        list[k++] = macro;
  }

  if( count > 1 )
    qsort( list, count, sizeof(*list), macro_name_compare );

  for( i = 0; i < count; ++i )
  {
    mcpu_macro *macro = list[i];
    mcpu_text   generated;
    const __mpu_char16_t *replacement;
    size_t      replacement_length;
    int         j;

    mcpu_text_init( &generated );

    if( line_filename != NULL )
    {
      const char *marker = macro->origin == MCPU_MACRO_ORIGIN_COMMAND_LINE ?
                           "<command-line>" : "<built-in>";

      if( mcpu_text_append_ascii(output, "# 0 \"" ) != 0 ||
          mcpu_text_append_utf8(output, marker) != 0 ||
          mcpu_text_append_ascii(output, "\"\n") != 0 )
        goto fail;
    }

    if( mcpu_text_append_ascii(output, "#define ") != 0 ||
        mcpu_text_append(output, macro->name, macro->name_length) != 0 )
      goto fail;

    if( macro->nargs >= 0 )
    {
      if( mcpu_text_append_char(output, '(') != 0 )
        goto fail;

      for( j = 0; j < macro->nargs; ++j )
      {
        if( j != 0 && mcpu_text_append_char(output, ',') != 0 )
          goto fail;
        if( mcpu_text_append(output, macro->argnames[j],
                             macro->argname_lengths[j]) != 0 )
          goto fail;
      }

      if( macro->variadic )
      {
        if( macro->nargs != 0 && mcpu_text_append_char(output, ',') != 0 )
          goto fail;
        if( mcpu_text_append_ascii(output, "...") != 0 )
          goto fail;
      }

      if( mcpu_text_append_char(output, ')') != 0 )
        goto fail;
    }

    if( macro->builtin == MCPU_MACRO_BUILTIN_NONE )
    {
      replacement = macro->replacement;
      replacement_length = macro->replacement_length;
    }
    else
    {
      if( expand_builtin(macro, NULL, &generated) != 0 )
        goto fail;
      replacement = generated.data;
      replacement_length = generated.length;
    }

    if( replacement_length != 0 &&
        (mcpu_text_append_char(output, ' ') != 0 ||
         mcpu_text_append(output, replacement, replacement_length) != 0) )
      goto fail;

    if( mcpu_text_append_char(output, '\n') != 0 )
      goto fail;

    mcpu_text_free( &generated );
    continue;

fail:
    mcpu_text_free( &generated );
    free( list );
    return( -1 );
  }

  free( list );
  return( 0 );
}


int
mcpu_macro_expand( mcpu_macro_table *table,
                   const __mpu_char16_t *input, size_t length,
                   enum mcpu_language language,
                   const mcpu_macro_expansion_context *context,
                   mcpu_text *output )
{
  if( table == NULL || input == NULL || output == NULL )
  {
    errno = EINVAL;
    return( -1 );
  }

  mcpu_text_free( output );
  mcpu_text_init( output );

  return( expand_range(table, input, length, language,
                       context, output, 0) );
}