/* gmarkup.c - Simple XML-like parser

 *

 *  Copyright 2000, 2003 Red Hat, Inc.

 *  Copyright 2007, 2008 Ryan Lortie <desrt@desrt.ca>

 *

 * 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/>.

 */

#include "config.h"

#include <stdarg.h>

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

#include <errno.h>

#include "gmarkup.h"

#include "gatomic.h"

#include "gslice.h"

#include "galloca.h"

#include "gstrfuncs.h"

#include "gstring.h"

#include "gtestutils.h"

#include "glibintl.h"

#include "gthread.h"

/**

 * SECTION:markup

 * @Title: Simple XML Subset Parser

 * @Short_description: parses a subset of XML

 * @See_also: [XML Specification](http://www.w3.org/TR/REC-xml/)

 *

 * The "GMarkup" parser is intended to parse a simple markup format

 * that's a subset of XML. This is a small, efficient, easy-to-use

 * parser. It should not be used if you expect to interoperate with

 * other applications generating full-scale XML. However, it's very

 * useful for application data files, config files, etc. where you

 * know your application will be the only one writing the file.

 * Full-scale XML parsers should be able to parse the subset used by

 * GMarkup, so you can easily migrate to full-scale XML at a later

 * time if the need arises.

 *

 * GMarkup is not guaranteed to signal an error on all invalid XML;

 * the parser may accept documents that an XML parser would not.

 * However, XML documents which are not well-formed (which is a

 * weaker condition than being valid. See the

 * [XML specification](http://www.w3.org/TR/REC-xml/)

 * for definitions of these terms.) are not considered valid GMarkup

 * documents.

 *

 * Simplifications to XML include:

 *

 * - Only UTF-8 encoding is allowed

 *

 * - No user-defined entities

 *

 * - Processing instructions, comments and the doctype declaration

 *   are "passed through" but are not interpreted in any way

 *

 * - No DTD or validation

 *

 * The markup format does support:

 *

 * - Elements

 *

 * - Attributes

 *

 * - 5 standard entities: & < > " '

 *

 * - Character references

 *

 * - Sections marked as CDATA

 */

G_DEFINE_QUARK (g-markup-error-quark, g_markup_error)

typedef enum

{

  STATE_START,

  STATE_AFTER_OPEN_ANGLE,

  STATE_AFTER_CLOSE_ANGLE,

  STATE_AFTER_ELISION_SLASH, /* the slash that obviates need for end element */

  STATE_INSIDE_OPEN_TAG_NAME,

  STATE_INSIDE_ATTRIBUTE_NAME,

  STATE_AFTER_ATTRIBUTE_NAME,

  STATE_BETWEEN_ATTRIBUTES,

  STATE_AFTER_ATTRIBUTE_EQUALS_SIGN,

  STATE_INSIDE_ATTRIBUTE_VALUE_SQ,

  STATE_INSIDE_ATTRIBUTE_VALUE_DQ,

  STATE_INSIDE_TEXT,

  STATE_AFTER_CLOSE_TAG_SLASH,

  STATE_INSIDE_CLOSE_TAG_NAME,

  STATE_AFTER_CLOSE_TAG_NAME,

  STATE_INSIDE_PASSTHROUGH,

  STATE_ERROR

} GMarkupParseState;

typedef struct

{

  const char *prev_element;

  const GMarkupParser *prev_parser;

  gpointer prev_user_data;

} GMarkupRecursionTracker;

struct _GMarkupParseContext

{

  const GMarkupParser *parser;

  volatile gint ref_count;

  GMarkupParseFlags flags;

  gint line_number;

  gint char_number;

  GMarkupParseState state;

  gpointer user_data;

  GDestroyNotify dnotify;

  /* A piece of character data or an element that

   * hasn't "ended" yet so we haven't yet called

   * the callback for it.

   */

  GString *partial_chunk;

  GSList *spare_chunks;

  GSList *tag_stack;

  GSList *tag_stack_gstr;

  GSList *spare_list_nodes;

  GString **attr_names;

  GString **attr_values;

  gint cur_attr;

  gint alloc_attrs;

  const gchar *current_text;

  gssize       current_text_len;

  const gchar *current_text_end;

  /* used to save the start of the last interesting thingy */

  const gchar *start;

  const gchar *iter;

  guint document_empty : 1;

  guint parsing : 1;

  guint awaiting_pop : 1;

  gint balance;

  /* subparser support */

  GSList *subparser_stack; /* (GMarkupRecursionTracker *) */

  const char *subparser_element;

  gpointer held_user_data;

};

/*

 * Helpers to reduce our allocation overhead, we have

 * a well defined allocation lifecycle.

 */

static GSList *

get_list_node (GMarkupParseContext *context, gpointer data)

{

  GSList *node;

  if (context->spare_list_nodes != NULL)

    {

      node = context->spare_list_nodes;

      context->spare_list_nodes = g_slist_remove_link (context->spare_list_nodes, node);

    }

  else

    node = g_slist_alloc();

  node->data = data;

  return node;

}

static void

free_list_node (GMarkupParseContext *context, GSList *node)

{

  node->data = NULL;

  context->spare_list_nodes = g_slist_concat (node, context->spare_list_nodes);

}

static inline void

string_blank (GString *string)

{

  string->str[0] = '\0';

  string->len = 0;

}

/**

 * g_markup_parse_context_new:

 * @parser: a #GMarkupParser

 * @flags: one or more #GMarkupParseFlags

 * @user_data: user data to pass to #GMarkupParser functions

 * @user_data_dnotify: user data destroy notifier called when

 *     the parse context is freed

 *

 * Creates a new parse context. A parse context is used to parse

 * marked-up documents. You can feed any number of documents into

 * a context, as long as no errors occur; once an error occurs,

 * the parse context can't continue to parse text (you have to

 * free it and create a new parse context).

 *

 * Returns: a new #GMarkupParseContext

 **/

GMarkupParseContext *

g_markup_parse_context_new (const GMarkupParser *parser,

                            GMarkupParseFlags    flags,

                            gpointer             user_data,

                            GDestroyNotify       user_data_dnotify)

{

  GMarkupParseContext *context;

  g_return_val_if_fail (parser != NULL, NULL);

  context = g_new (GMarkupParseContext, 1);

  context->ref_count = 1;

  context->parser = parser;

  context->flags = flags;

  context->user_data = user_data;

  context->dnotify = user_data_dnotify;

  context->line_number = 1;

  context->char_number = 1;

  context->partial_chunk = NULL;

  context->spare_chunks = NULL;

  context->spare_list_nodes = NULL;

  context->state = STATE_START;

  context->tag_stack = NULL;

  context->tag_stack_gstr = NULL;

  context->attr_names = NULL;

  context->attr_values = NULL;

  context->cur_attr = -1;

  context->alloc_attrs = 0;

  context->current_text = NULL;

  context->current_text_len = -1;

  context->current_text_end = NULL;

  context->start = NULL;

  context->iter = NULL;

  context->document_empty = TRUE;

  context->parsing = FALSE;

  context->awaiting_pop = FALSE;

  context->subparser_stack = NULL;

  context->subparser_element = NULL;

  /* this is only looked at if awaiting_pop = TRUE.  initialise anyway. */

  context->held_user_data = NULL;

  context->balance = 0;

  return context;

}

/**

 * g_markup_parse_context_ref:

 * @context: a #GMarkupParseContext

 *

 * Increases the reference count of @context.

 *

 * Returns: the same @context

 *

 * Since: 2.36

 **/

GMarkupParseContext *

g_markup_parse_context_ref (GMarkupParseContext *context)

{

  g_return_val_if_fail (context != NULL, NULL);

  g_return_val_if_fail (context->ref_count > 0, NULL);

  g_atomic_int_inc (&context->ref_count);

  return context;

}

/**

 * g_markup_parse_context_unref:

 * @context: a #GMarkupParseContext

 *

 * Decreases the reference count of @context.  When its reference count

 * drops to 0, it is freed.

 *

 * Since: 2.36

 **/

void

g_markup_parse_context_unref (GMarkupParseContext *context)

{

  g_return_if_fail (context != NULL);

  g_return_if_fail (context->ref_count > 0);

  if (g_atomic_int_dec_and_test (&context->ref_count))

    g_markup_parse_context_free (context);

}

static void

string_full_free (gpointer ptr)

{

  g_string_free (ptr, TRUE);

}

static void clear_attributes (GMarkupParseContext *context);

/**

 * g_markup_parse_context_free:

 * @context: a #GMarkupParseContext

 *

 * Frees a #GMarkupParseContext.

 *

 * This function can't be called from inside one of the

 * #GMarkupParser functions or while a subparser is pushed.

 */

void

g_markup_parse_context_free (GMarkupParseContext *context)

{

  g_return_if_fail (context != NULL);

  g_return_if_fail (!context->parsing);

  g_return_if_fail (!context->subparser_stack);

  g_return_if_fail (!context->awaiting_pop);

  if (context->dnotify)

    (* context->dnotify) (context->user_data);

  clear_attributes (context);

  g_free (context->attr_names);

  g_free (context->attr_values);

  g_slist_free_full (context->tag_stack_gstr, string_full_free);

  g_slist_free (context->tag_stack);

  g_slist_free_full (context->spare_chunks, string_full_free);

  g_slist_free (context->spare_list_nodes);

  if (context->partial_chunk)

    g_string_free (context->partial_chunk, TRUE);

  g_free (context);

}

static void pop_subparser_stack (GMarkupParseContext *context);

static void

mark_error (GMarkupParseContext *context,

            GError              *error)

{

  context->state = STATE_ERROR;

  if (context->parser->error)

    (*context->parser->error) (context, error, context->user_data);

  /* report the error all the way up to free all the user-data */

  while (context->subparser_stack)

    {

      pop_subparser_stack (context);

      context->awaiting_pop = FALSE; /* already been freed */

      if (context->parser->error)

        (*context->parser->error) (context, error, context->user_data);

    }

}

static void

set_error (GMarkupParseContext  *context,

           GError              **error,

           GMarkupError          code,

           const gchar          *format,

           ...) G_GNUC_PRINTF (4, 5);

static void

set_error_literal (GMarkupParseContext  *context,

                   GError              **error,

                   GMarkupError          code,

                   const gchar          *message)

{

  GError *tmp_error;

  tmp_error = g_error_new_literal (G_MARKUP_ERROR, code, message);

  g_prefix_error (&tmp_error,

                  _("Error on line %d char %d: "),

                  context->line_number,

                  context->char_number);

  mark_error (context, tmp_error);

  g_propagate_error (error, tmp_error);

}

G_GNUC_PRINTF(4, 5)

static void

set_error (GMarkupParseContext  *context,

           GError              **error,

           GMarkupError          code,

           const gchar          *format,

           ...)

{

  gchar *s;

  gchar *s_valid;

  va_list args;

  va_start (args, format);

  s = g_strdup_vprintf (format, args);

  va_end (args);

  /* Make sure that the GError message is valid UTF-8

   * even if it is complaining about invalid UTF-8 in the markup

   */

  s_valid = g_utf8_make_valid (s, -1);

  set_error_literal (context, error, code, s);

  g_free (s);

  g_free (s_valid);

}

static void

propagate_error (GMarkupParseContext  *context,

                 GError              **dest,

                 GError               *src)

{

  if (context->flags & G_MARKUP_PREFIX_ERROR_POSITION)

    g_prefix_error (&src,

                    _("Error on line %d char %d: "),

                    context->line_number,

                    context->char_number);

  mark_error (context, src);

  g_propagate_error (dest, src);

}

#define IS_COMMON_NAME_END_CHAR(c) \

  ((c) == '=' || (c) == '/' || (c) == '>' || (c) == ' ')

static gboolean

slow_name_validate (GMarkupParseContext  *context,

                    const gchar          *name,

                    GError              **error)

{

  const gchar *p = name;

  if (!g_utf8_validate (name, strlen (name), NULL))

    {

      set_error (context, error, G_MARKUP_ERROR_BAD_UTF8,

                 _("Invalid UTF-8 encoded text in name - not valid '%s'"), name);

      return FALSE;

    }

  if (!(g_ascii_isalpha (*p) ||

        (!IS_COMMON_NAME_END_CHAR (*p) &&

         (*p == '_' ||

          *p == ':' ||

          g_unichar_isalpha (g_utf8_get_char (p))))))

    {

      set_error (context, error, G_MARKUP_ERROR_PARSE,

                 _("'%s' is not a valid name"), name);

      return FALSE;

    }

  for (p = g_utf8_next_char (name); *p != '\0'; p = g_utf8_next_char (p))

    {

      /* is_name_char */

      if (!(g_ascii_isalnum (*p) ||

            (!IS_COMMON_NAME_END_CHAR (*p) &&

             (*p == '.' ||

              *p == '-' ||

              *p == '_' ||

              *p == ':' ||

              g_unichar_isalpha (g_utf8_get_char (p))))))

        {

          set_error (context, error, G_MARKUP_ERROR_PARSE,

                     _("'%s' is not a valid name: '%c'"), name, *p);

          return FALSE;

        }

    }

  return TRUE;

}

/*

 * Use me for elements, attributes etc.

 */

static gboolean

name_validate (GMarkupParseContext  *context,

               const gchar          *name,

               GError              **error)

{

  char mask;

  const char *p;

  /* name start char */

  p = name;

  if (G_UNLIKELY (IS_COMMON_NAME_END_CHAR (*p) ||

                  !(g_ascii_isalpha (*p) || *p == '_' || *p == ':')))

    goto slow_validate;

  for (mask = *p++; *p != '\0'; p++)

    {

      mask |= *p;

      /* is_name_char */

      if (G_UNLIKELY (!(g_ascii_isalnum (*p) ||

                        (!IS_COMMON_NAME_END_CHAR (*p) &&

                         (*p == '.' ||

                          *p == '-' ||

                          *p == '_' ||

                          *p == ':')))))

        goto slow_validate;

    }

  if (mask & 0x80) /* un-common / non-ascii */

    goto slow_validate;

  return TRUE;

 slow_validate:

  return slow_name_validate (context, name, error);

}

static gboolean

text_validate (GMarkupParseContext  *context,

               const gchar          *p,

               gint                  len,

               GError              **error)

{

  if (!g_utf8_validate (p, len, NULL))

    {

      set_error (context, error, G_MARKUP_ERROR_BAD_UTF8,

                 _("Invalid UTF-8 encoded text in name - not valid '%s'"), p);

      return FALSE;

    }

  else

    return TRUE;

}

static gchar*

char_str (gunichar c,

          gchar   *buf)

{

  memset (buf, 0, 8);

  g_unichar_to_utf8 (c, buf);

  return buf;

}

static gchar*

utf8_str (const gchar *utf8,

          gchar       *buf)

{

  char_str (g_utf8_get_char (utf8), buf);

  return buf;

}

G_GNUC_PRINTF(5, 6)

static void

set_unescape_error (GMarkupParseContext  *context,

                    GError              **error,

                    const gchar          *remaining_text,

                    GMarkupError          code,

                    const gchar          *format,

                    ...)

{

  GError *tmp_error;

  gchar *s;

  va_list args;

  gint remaining_newlines;

  const gchar *p;

  remaining_newlines = 0;

  p = remaining_text;

  while (*p != '\0')

    {

      if (*p == '\n')

        ++remaining_newlines;

      ++p;

    }

  va_start (args, format);

  s = g_strdup_vprintf (format, args);

  va_end (args);

  tmp_error = g_error_new (G_MARKUP_ERROR,

                           code,

                           _("Error on line %d: %s"),

                           context->line_number - remaining_newlines,

                           s);

  g_free (s);

  mark_error (context, tmp_error);

  g_propagate_error (error, tmp_error);

}

/*

 * re-write the GString in-place, unescaping anything that escaped.

 * most XML does not contain entities, or escaping.

 */

static gboolean

unescape_gstring_inplace (GMarkupParseContext  *context,

                          GString              *string,

                          gboolean             *is_ascii,

                          GError              **error)

{

  char mask, *to;

  const char *from;

  gboolean normalize_attribute;

  *is_ascii = FALSE;

  /* are we unescaping an attribute or not ? */

  if (context->state == STATE_INSIDE_ATTRIBUTE_VALUE_SQ ||

      context->state == STATE_INSIDE_ATTRIBUTE_VALUE_DQ)

    normalize_attribute = TRUE;

  else

    normalize_attribute = FALSE;

  /*

   * Meeks' theorem: unescaping can only shrink text.

   * for < etc. this is obvious, for ￿ more

   * thought is required, but this is patently so.

   */

  mask = 0;

  for (from = to = string->str; *from != '\0'; from++, to++)

    {

      *to = *from;

      mask |= *to;

      if (normalize_attribute && (*to == '\t' || *to == '\n'))

        *to = ' ';

      if (*to == '\r')

        {

          *to = normalize_attribute ? ' ' : '\n';

          if (from[1] == '\n')

            from++;

        }

      if (*from == '&')

        {

          from++;

          if (*from == '#')

            {

              gint base = 10;

              gulong l;

              gchar *end = NULL;

              from++;

              if (*from == 'x')

                {

                  base = 16;

                  from++;

                }

              errno = 0;

              l = strtoul (from, &end, base);

              if (end == from || errno != 0)

                {

                  set_unescape_error (context, error,

                                      from, G_MARKUP_ERROR_PARSE,

                                      _("Failed to parse '%-.*s', which "

                                        "should have been a digit "

                                        "inside a character reference "

                                        "(ê for example) - perhaps "

                                        "the digit is too large"),

                                      (int)(end - from), from);

                  return FALSE;

                }

              else if (*end != ';')

                {

                  set_unescape_error (context, error,

                                      from, G_MARKUP_ERROR_PARSE,

                                      _("Character reference did not end with a "

                                        "semicolon; "

                                        "most likely you used an ampersand "

                                        "character without intending to start "

                                        "an entity - escape ampersand as &"));

                  return FALSE;

                }

              else

                {

                  /* characters XML 1.1 permits */

                  if ((0 < l && l <= 0xD7FF) ||

                      (0xE000 <= l && l <= 0xFFFD) ||

                      (0x10000 <= l && l <= 0x10FFFF))

                    {

                      gchar buf[8];

                      char_str (l, buf);

                      strcpy (to, buf);

                      to += strlen (buf) - 1;

                      from = end;

                      if (l >= 0x80) /* not ascii */

                        mask |= 0x80;

                    }

                  else

                    {

                      set_unescape_error (context, error,

                                          from, G_MARKUP_ERROR_PARSE,

                                          _("Character reference '%-.*s' does not "

                                            "encode a permitted character"),

                                          (int)(end - from), from);

                      return FALSE;

                    }

                }

            }

          else if (strncmp (from, "lt;", 3) == 0)

            {

              *to = '<';

              from += 2;

            }

          else if (strncmp (from, "gt;", 3) == 0)

            {

              *to = '>';

              from += 2;

            }

          else if (strncmp (from, "amp;", 4) == 0)

            {

              *to = '&';

              from += 3;

            }

          else if (strncmp (from, "quot;", 5) == 0)

            {

              *to = '"';

              from += 4;

            }

          else if (strncmp (from, "apos;", 5) == 0)

            {

              *to = '\'';

              from += 4;

            }

          else

            {

              if (*from == ';')

                set_unescape_error (context, error,

                                    from, G_MARKUP_ERROR_PARSE,

                                    _("Empty entity '&;' seen; valid "

                                      "entities are: & " < > '"));

              else

                {

                  const char *end = strchr (from, ';');

                  if (end)

                    set_unescape_error (context, error,

                                        from, G_MARKUP_ERROR_PARSE,

                                        _("Entity name '%-.*s' is not known"),

                                        (int)(end - from), from);

                  else

                    set_unescape_error (context, error,

                                        from, G_MARKUP_ERROR_PARSE,

                                        _("Entity did not end with a semicolon; "

                                          "most likely you used an ampersand "

                                          "character without intending to start "

                                          "an entity - escape ampersand as &"));

                }

              return FALSE;

            }

        }

    }

  g_assert (to - string->str <= string->len);

  if (to - string->str != string->len)

    g_string_truncate (string, to - string->str);

  *is_ascii = !(mask & 0x80);

  return TRUE;

}

static inline gboolean

advance_char (GMarkupParseContext *context)

{

  context->iter++;

  context->char_number++;

  if (G_UNLIKELY (context->iter == context->current_text_end))

      return FALSE;

  else if (G_UNLIKELY (*context->iter == '\n'))

    {

      context->line_number++;

      context->char_number = 1;

    }

  return TRUE;

}

static inline gboolean

xml_isspace (char c)

{

  return c == ' ' || c == '\t' || c == '\n' || c == '\r';

}

static void

skip_spaces (GMarkupParseContext *context)

{

  do

    {

      if (!xml_isspace (*context->iter))

        return;

    }

  while (advance_char (context));

}

static void

advance_to_name_end (GMarkupParseContext *context)

{

  do

    {

      if (IS_COMMON_NAME_END_CHAR (*(context->iter)))

        return;

      if (xml_isspace (*(context->iter)))

        return;

    }

  while (advance_char (context));

}

static void

release_chunk (GMarkupParseContext *context, GString *str)

{

  GSList *node;

  if (!str)

    return;

  if (str->allocated_len > 256)

    { /* large strings are unusual and worth freeing */

      g_string_free (str, TRUE);

      return;

    }

  string_blank (str);

  node = get_list_node (context, str);

  context->spare_chunks = g_slist_concat (node, context->spare_chunks);

}

static void

add_to_partial (GMarkupParseContext *context,

                const gchar         *text_start,

                const gchar         *text_end)

{

  if (context->partial_chunk == NULL)

    { /* allocate a new chunk to parse into */

      if (context->spare_chunks != NULL)

        {

          GSList *node = context->spare_chunks;

          context->spare_chunks = g_slist_remove_link (context->spare_chunks, node);

          context->partial_chunk = node->data;

          free_list_node (context, node);

        }

      else

        context->partial_chunk = g_string_sized_new (MAX (28, text_end - text_start));

    }

  if (text_start != text_end)

    g_string_insert_len (context->partial_chunk, -1,

                         text_start, text_end - text_start);

}

static inline void

truncate_partial (GMarkupParseContext *context)

{

  if (context->partial_chunk != NULL)

    string_blank (context->partial_chunk);

}

static inline const gchar*

current_element (GMarkupParseContext *context)

{