/*

 * Copyright © 2009, 2010 Codethink Limited

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library 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

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, see <http://www.gnu.org/licenses/>.

 *

 * Author: Ryan Lortie <desrt@desrt.ca>

 */

#include "config.h"

#include <stdlib.h>

#include <string.h>

#include <errno.h>

#include "gerror.h"

#include "gquark.h"

#include "gstring.h"

#include "gstrfuncs.h"

#include "gtestutils.h"

#include "gvariant.h"

#include "gvarianttype.h"

#include "gslice.h"

#include "gthread.h"

/*

 * two-pass algorithm

 * designed by ryan lortie and william hua

 * designed in itb-229 and at ghazi's, 2009.

 */

/**

 * G_VARIANT_PARSE_ERROR:

 *

 * Error domain for GVariant text format parsing.  Specific error codes

 * are not currently defined for this domain.  See #GError for

 * information on error domains.

 **/

/**

 * GVariantParseError:

 * @G_VARIANT_PARSE_ERROR_FAILED: generic error (unused)

 * @G_VARIANT_PARSE_ERROR_BASIC_TYPE_EXPECTED: a non-basic #GVariantType was given where a basic type was expected

 * @G_VARIANT_PARSE_ERROR_CANNOT_INFER_TYPE: cannot infer the #GVariantType

 * @G_VARIANT_PARSE_ERROR_DEFINITE_TYPE_EXPECTED: an indefinite #GVariantType was given where a definite type was expected

 * @G_VARIANT_PARSE_ERROR_INPUT_NOT_AT_END: extra data after parsing finished

 * @G_VARIANT_PARSE_ERROR_INVALID_CHARACTER: invalid character in number or unicode escape

 * @G_VARIANT_PARSE_ERROR_INVALID_FORMAT_STRING: not a valid #GVariant format string

 * @G_VARIANT_PARSE_ERROR_INVALID_OBJECT_PATH: not a valid object path

 * @G_VARIANT_PARSE_ERROR_INVALID_SIGNATURE: not a valid type signature

 * @G_VARIANT_PARSE_ERROR_INVALID_TYPE_STRING: not a valid #GVariant type string

 * @G_VARIANT_PARSE_ERROR_NO_COMMON_TYPE: could not find a common type for array entries

 * @G_VARIANT_PARSE_ERROR_NUMBER_OUT_OF_RANGE: the numerical value is out of range of the given type

 * @G_VARIANT_PARSE_ERROR_NUMBER_TOO_BIG: the numerical value is out of range for any type

 * @G_VARIANT_PARSE_ERROR_TYPE_ERROR: cannot parse as variant of the specified type

 * @G_VARIANT_PARSE_ERROR_UNEXPECTED_TOKEN: an unexpected token was encountered

 * @G_VARIANT_PARSE_ERROR_UNKNOWN_KEYWORD: an unknown keyword was encountered

 * @G_VARIANT_PARSE_ERROR_UNTERMINATED_STRING_CONSTANT: unterminated string constant

 * @G_VARIANT_PARSE_ERROR_VALUE_EXPECTED: no value given

 *

 * Error codes returned by parsing text-format GVariants.

 **/

G_DEFINE_QUARK (g-variant-parse-error-quark, g_variant_parse_error)

/**

 * g_variant_parser_get_error_quark:

 *

 * Same as g_variant_error_quark().

 *

 * Deprecated: Use g_variant_parse_error_quark() instead.

 */

GQuark

g_variant_parser_get_error_quark (void)

{

  return g_variant_parse_error_quark ();

}

typedef struct

{

  gint start, end;

} SourceRef;

G_GNUC_PRINTF(5, 0)

static void

parser_set_error_va (GError      **error,

                     SourceRef    *location,

                     SourceRef    *other,

                     gint          code,

                     const gchar  *format,

                     va_list       ap)

{

  GString *msg = g_string_new (NULL);

  if (location->start == location->end)

    g_string_append_printf (msg, "%d", location->start);

  else

    g_string_append_printf (msg, "%d-%d", location->start, location->end);

  if (other != NULL)

    {

      g_assert (other->start != other->end);

      g_string_append_printf (msg, ",%d-%d", other->start, other->end);

    }

  g_string_append_c (msg, ':');

  g_string_append_vprintf (msg, format, ap);

  g_set_error_literal (error, G_VARIANT_PARSE_ERROR, code, msg->str);

  g_string_free (msg, TRUE);

}

G_GNUC_PRINTF(5, 6)

static void

parser_set_error (GError      **error,

                  SourceRef    *location,

                  SourceRef    *other,

                  gint          code,

                  const gchar  *format,

                  ...)

{

  va_list ap;

  va_start (ap, format);

  parser_set_error_va (error, location, other, code, format, ap);

  va_end (ap);

}

typedef struct

{

  const gchar *start;

  const gchar *stream;

  const gchar *end;

  const gchar *this;

} TokenStream;

G_GNUC_PRINTF(5, 6)

static void

token_stream_set_error (TokenStream  *stream,

                        GError      **error,

                        gboolean      this_token,

                        gint          code,

                        const gchar  *format,

                        ...)

{

  SourceRef ref;

  va_list ap;

  ref.start = stream->this - stream->start;

  if (this_token)

    ref.end = stream->stream - stream->start;

  else

    ref.end = ref.start;

  va_start (ap, format);

  parser_set_error_va (error, &ref, NULL, code, format, ap);

  va_end (ap);

}

static gboolean

token_stream_prepare (TokenStream *stream)

{

  gint brackets = 0;

  const gchar *end;

  if (stream->this != NULL)

    return TRUE;

  while (stream->stream != stream->end && g_ascii_isspace (*stream->stream))

    stream->stream++;

  if (stream->stream == stream->end || *stream->stream == '\0')

    {

      stream->this = stream->stream;

      return FALSE;

    }

  switch (stream->stream[0])

    {

    case '-': case '+': case '.': case '0': case '1': case '2':

    case '3': case '4': case '5': case '6': case '7': case '8':

    case '9':

      for (end = stream->stream; end != stream->end; end++)

        if (!g_ascii_isalnum (*end) &&

            *end != '-' && *end != '+' && *end != '.')

          break;

      break;

    case 'b':

      if (stream->stream[1] == '\'' || stream->stream[1] == '"')

        {

          for (end = stream->stream + 2; end != stream->end; end++)

            if (*end == stream->stream[1] || *end == '\0' ||

                (*end == '\\' && (++end == stream->end || *end == '\0')))

              break;

          if (end != stream->end && *end)

            end++;

          break;

        }

      else

        {

          /* ↓↓↓ */

        }

    case 'a': /* 'b' */ case 'c': case 'd': case 'e': case 'f':

    case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':

    case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':

    case 's': case 't': case 'u': case 'v': case 'w': case 'x':

    case 'y': case 'z':

      for (end = stream->stream; end != stream->end; end++)

        if (!g_ascii_isalnum (*end))

          break;

      break;

    case '\'': case '"':

      for (end = stream->stream + 1; end != stream->end; end++)

        if (*end == stream->stream[0] || *end == '\0' ||

            (*end == '\\' && (++end == stream->end || *end == '\0')))

          break;

      if (end != stream->end && *end)

        end++;

      break;

    case '@': case '%':

      /* stop at the first space, comma, colon or unmatched bracket.

       * deals nicely with cases like (%i, %i) or {%i: %i}.

       * Also: ] and > are never in format strings.

       */

      for (end = stream->stream + 1;

           end != stream->end && *end != '\0' && *end != ',' &&

           *end != ':' && *end != '>' && *end != ']' && !g_ascii_isspace (*end);

           end++)

        if (*end == '(' || *end == '{')

          brackets++;

        else if ((*end == ')' || *end == '}') && !brackets--)

          break;

      break;

    default:

      end = stream->stream + 1;

      break;

    }

  stream->this = stream->stream;

  stream->stream = end;

  return TRUE;

}

static void

token_stream_next (TokenStream *stream)

{

  stream->this = NULL;

}

static gboolean

token_stream_peek (TokenStream *stream,

                   gchar        first_char)

{

  if (!token_stream_prepare (stream))

    return FALSE;

  return stream->this[0] == first_char;

}

static gboolean

token_stream_peek2 (TokenStream *stream,

                    gchar        first_char,

                    gchar        second_char)

{

  if (!token_stream_prepare (stream))

    return FALSE;

  return stream->this[0] == first_char &&

         stream->this[1] == second_char;

}

static gboolean

token_stream_is_keyword (TokenStream *stream)

{

  if (!token_stream_prepare (stream))

    return FALSE;

  return g_ascii_isalpha (stream->this[0]) &&

         g_ascii_isalpha (stream->this[1]);

}

static gboolean

token_stream_is_numeric (TokenStream *stream)

{

  if (!token_stream_prepare (stream))

    return FALSE;

  return (g_ascii_isdigit (stream->this[0]) ||

          stream->this[0] == '-' ||

          stream->this[0] == '+' ||

          stream->this[0] == '.');

}

static gboolean

token_stream_peek_string (TokenStream *stream,

                          const gchar *token)

{

  gint length = strlen (token);

  return token_stream_prepare (stream) &&

         stream->stream - stream->this == length &&

         memcmp (stream->this, token, length) == 0;

}

static gboolean

token_stream_consume (TokenStream *stream,

                      const gchar *token)

{

  if (!token_stream_peek_string (stream, token))

    return FALSE;

  token_stream_next (stream);

  return TRUE;

}

static gboolean

token_stream_require (TokenStream  *stream,

                      const gchar  *token,

                      const gchar  *purpose,

                      GError      **error)

{

  if (!token_stream_consume (stream, token))

    {

      token_stream_set_error (stream, error, FALSE,

                              G_VARIANT_PARSE_ERROR_UNEXPECTED_TOKEN,

                              "expected '%s'%s", token, purpose);

      return FALSE;

    }

  return TRUE;

}

static void

token_stream_assert (TokenStream *stream,

                     const gchar *token)

{

  gboolean correct_token;

  correct_token = token_stream_consume (stream, token);

  g_assert (correct_token);

}

static gchar *

token_stream_get (TokenStream *stream)

{

  gchar *result;

  if (!token_stream_prepare (stream))

    return NULL;

  result = g_strndup (stream->this, stream->stream - stream->this);

  return result;

}

static void

token_stream_start_ref (TokenStream *stream,

                        SourceRef   *ref)

{

  token_stream_prepare (stream);

  ref->start = stream->this - stream->start;

}

static void

token_stream_end_ref (TokenStream *stream,

                      SourceRef   *ref)

{

  ref->end = stream->stream - stream->start;

}

static void

pattern_copy (gchar       **out,

              const gchar **in)

{

  gint brackets = 0;

  while (**in == 'a' || **in == 'm' || **in == 'M')

    *(*out)++ = *(*in)++;

  do

    {

      if (**in == '(' || **in == '{')

        brackets++;

      else if (**in == ')' || **in == '}')

        brackets--;

      *(*out)++ = *(*in)++;

    }

  while (brackets);

}

static gchar *

pattern_coalesce (const gchar *left,

                  const gchar *right)

{

  gchar *result;

  gchar *out;

  /* the length of the output is loosely bound by the sum of the input

   * lengths, not simply the greater of the two lengths.

   *

   *   (*(iii)) + ((iii)*) ((iii)(iii))

   *

   *      8     +    8    =  12

   */

  out = result = g_malloc (strlen (left) + strlen (right));

  while (*left && *right)

    {

      if (*left == *right)

        {

          *out++ = *left++;

          right++;

        }

      else

        {

          const gchar **one = &left, **the_other = &right;

         again:

          if (**one == '*' && **the_other != ')')

            {

              pattern_copy (&out, the_other);

              (*one)++;

            }

          else if (**one == 'M' && **the_other == 'm')

            {

              *out++ = *(*the_other)++;

            }

          else if (**one == 'M' && **the_other != 'm')

            {

              (*one)++;

            }

          else if (**one == 'N' && strchr ("ynqiuxthd", **the_other))

            {

              *out++ = *(*the_other)++;

              (*one)++;

            }

          else if (**one == 'S' && strchr ("sog", **the_other))

            {

              *out++ = *(*the_other)++;

              (*one)++;

            }

          else if (one == &left)

            {

              one = &right, the_other = &left;

              goto again;

            }

          else

            break;

        }

    }

  if (*left || *right)

    {

      g_free (result);

      result = NULL;

    }

  else

    *out++ = '\0';

  return result;

}

typedef struct _AST AST;

typedef gchar *    (*get_pattern_func)    (AST                 *ast,

                                           GError             **error);

typedef GVariant * (*get_value_func)      (AST                 *ast,

                                           const GVariantType  *type,

                                           GError             **error);

typedef GVariant * (*get_base_value_func) (AST                 *ast,

                                           const GVariantType  *type,

                                           GError             **error);

typedef void       (*free_func)           (AST                 *ast);

typedef struct

{

  gchar *    (* get_pattern)    (AST                 *ast,

                                 GError             **error);

  GVariant * (* get_value)      (AST                 *ast,

                                 const GVariantType  *type,

                                 GError             **error);

  GVariant * (* get_base_value) (AST                 *ast,

                                 const GVariantType  *type,

                                 GError             **error);

  void       (* free)           (AST                 *ast);

} ASTClass;

struct _AST

{

  const ASTClass *class;

  SourceRef source_ref;

};

static gchar *

ast_get_pattern (AST     *ast,

                 GError **error)

{

  return ast->class->get_pattern (ast, error);

}

static GVariant *

ast_get_value (AST                 *ast,

               const GVariantType  *type,

               GError             **error)

{

  return ast->class->get_value (ast, type, error);

}

static void

ast_free (AST *ast)

{

  ast->class->free (ast);

}

G_GNUC_PRINTF(5, 6)

static void

ast_set_error (AST          *ast,

               GError      **error,

               AST          *other_ast,

               gint          code,

               const gchar  *format,

               ...)

{

  va_list ap;

  va_start (ap, format);

  parser_set_error_va (error, &ast->source_ref,

                       other_ast ? & other_ast->source_ref : NULL,

                       code,

                       format, ap);

  va_end (ap);

}

static GVariant *

ast_type_error (AST                 *ast,

                const GVariantType  *type,

                GError             **error)

{

  gchar *typestr;

  typestr = g_variant_type_dup_string (type);

  ast_set_error (ast, error, NULL,

                 G_VARIANT_PARSE_ERROR_TYPE_ERROR,

                 "can not parse as value of type '%s'",

                 typestr);

  g_free (typestr);

  return NULL;

}

static GVariant *

ast_resolve (AST     *ast,

             GError **error)

{

  GVariant *value;

  gchar *pattern;

  gint i, j = 0;

  pattern = ast_get_pattern (ast, error);

  if (pattern == NULL)

    return NULL;

  /* choose reasonable defaults

   *

   *   1) favour non-maybe values where possible

   *   2) default type for strings is 's'

   *   3) default type for integers is 'i'

   */

  for (i = 0; pattern[i]; i++)

    switch (pattern[i])

      {

      case '*':

        ast_set_error (ast, error, NULL,

                       G_VARIANT_PARSE_ERROR_CANNOT_INFER_TYPE,

                       "unable to infer type");

        g_free (pattern);

        return NULL;

      case 'M':

        break;

      case 'S':

        pattern[j++] = 's';

        break;

      case 'N':

        pattern[j++] = 'i';

        break;

      default:

        pattern[j++] = pattern[i];

        break;

      }

  pattern[j++] = '\0';

  value = ast_get_value (ast, G_VARIANT_TYPE (pattern), error);

  g_free (pattern);

  return value;

}

static AST *parse (TokenStream  *stream,

                   va_list      *app,

                   GError      **error);

static void

ast_array_append (AST  ***array,

                  gint   *n_items,

                  AST    *ast)

{

  if ((*n_items & (*n_items - 1)) == 0)

    *array = g_renew (AST *, *array, *n_items ? 2 ** n_items : 1);

  (*array)[(*n_items)++] = ast;

}

static void

ast_array_free (AST  **array,

                gint   n_items)

{

  gint i;

  for (i = 0; i < n_items; i++)

    ast_free (array[i]);

  g_free (array);

}

static gchar *

ast_array_get_pattern (AST    **array,

                       gint     n_items,

                       GError **error)

{

  gchar *pattern;

  gint i;

  pattern = ast_get_pattern (array[0], error);

  if (pattern == NULL)

    return NULL;

  for (i = 1; i < n_items; i++)

    {

      gchar *tmp, *merged;

      tmp = ast_get_pattern (array[i], error);

      if (tmp == NULL)

        {

          g_free (pattern);

          return NULL;

        }

      merged = pattern_coalesce (pattern, tmp);

      g_free (pattern);

      pattern = merged;

      if (merged == NULL)

        /* set coalescence implies pairwise coalescence (i think).

         * we should therefore be able to trace the failure to a single

         * pair of values.

         */

        {

          int j = 0;

          while (TRUE)

            {

              gchar *tmp2;

              gchar *m;

              /* if 'j' reaches 'i' then we failed to find the pair */

              g_assert (j < i);

              tmp2 = ast_get_pattern (array[j], NULL);

              g_assert (tmp2 != NULL);

              m = pattern_coalesce (tmp, tmp2);

              g_free (tmp2);

              g_free (m);

              if (m == NULL)

                {

                  /* we found a conflict between 'i' and 'j'.

                   *

                   * report the error.  note: 'j' is first.

                   */

                  ast_set_error (array[j], error, array[i],

                                 G_VARIANT_PARSE_ERROR_NO_COMMON_TYPE,

                                 "unable to find a common type");

                  g_free (tmp);

                  return NULL;

                }

              j++;

            }

        }

      g_free (tmp);

    }

  return pattern;

}

typedef struct

{

  AST ast;

  AST *child;

} Maybe;

static gchar *

maybe_get_pattern (AST     *ast,

                   GError **error)

{

  Maybe *maybe = (Maybe *) ast;

  if (maybe->child != NULL)

    {

      gchar *child_pattern;

      gchar *pattern;

      child_pattern = ast_get_pattern (maybe->child, error);

      if (child_pattern == NULL)

        return NULL;

      pattern = g_strdup_printf ("m%s", child_pattern);

      g_free (child_pattern);

      return pattern;

    }

  return g_strdup ("m*");

}

static GVariant *

maybe_get_value (AST                 *ast,

                 const GVariantType  *type,

                 GError             **error)

{

  Maybe *maybe = (Maybe *) ast;

  GVariant *value;

  if (!g_variant_type_is_maybe (type))

    return ast_type_error (ast, type, error);

  type = g_variant_type_element (type);

  if (maybe->child)

    {

      value = ast_get_value (maybe->child, type, error);

      if (value == NULL)

        return NULL;

    }

  else

    value = NULL;

  return g_variant_new_maybe (type, value);

}

static void

maybe_free (AST *ast)

{

  Maybe *maybe = (Maybe *) ast;

  if (maybe->child != NULL)

    ast_free (maybe->child);

  g_slice_free (Maybe, maybe);

}

static AST *

maybe_parse (TokenStream  *stream,

             va_list      *app,

             GError      **error)

{

  static const ASTClass maybe_class = {

    maybe_get_pattern,

    maybe_get_value, NULL,

    maybe_free

  };

  AST *child = NULL;

  Maybe *maybe;

  if (token_stream_consume (stream, "just"))

    {

      child = parse (stream, app, error);

      if (child == NULL)

        return NULL;

    }

  else if (!token_stream_consume (stream, "nothing"))

    {

      token_stream_set_error (stream, error, TRUE,

                              G_VARIANT_PARSE_ERROR_UNKNOWN_KEYWORD,

                              "unknown keyword");

      return NULL;

    }

  maybe = g_slice_new (Maybe);

  maybe->ast.class = &maybe_class;

  maybe->child = child;

  return (AST *) maybe;

}

static GVariant *

maybe_wrapper (AST                 *ast,

               const GVariantType  *type,

               GError             **error)

{

  const GVariantType *t;

  GVariant *value;

  int depth;

  for (depth = 0, t = type;

       g_variant_type_is_maybe (t);

       depth++, t = g_variant_type_element (t));

  value = ast->class->get_base_value (ast, t, error);

  if (value == NULL)

    return NULL;

  while (depth--)

    value = g_variant_new_maybe (NULL, value);

  return value;

}

typedef struct

{

  AST ast;

  AST **children;

  gint n_children;

} Array;

static gchar *

array_get_pattern (AST     *ast,

                   GError **error)

{

  Array *array = (Array *) ast;

  gchar *pattern;

  gchar *result;