glib/gvariant-parser.c

   1 /*
   2  * Copyright © 2009, 2010 Codethink Limited
   3  *
   4  * SPDX-License-Identifier: LGPL-2.1-or-later
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  18  *
  19  * Author: Ryan Lortie <desrt@desrt.ca>
  20  */
  21
  22 #include "config.h"
  23
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include <errno.h>
  27
  28 #include "gerror.h"
  29 #include "gquark.h"
  30 #include "gstring.h"
  31 #include "gstrfuncs.h"
  32 #include "gtestutils.h"
  33 #include "gvariant.h"
  34 #include "glib/gvariant-core.h"
  35 #include "gvariant-internal.h"
  36 #include "gvarianttype.h"
  37 #include "gslice.h"
  38 #include "gthread.h"
  39
  40 /*
  41  * two-pass algorithm
  42  * designed by ryan lortie and william hua
  43  * designed in itb-229 and at ghazi's, 2009.
  44  */
  45
  46 /**
  47  * G_VARIANT_PARSE_ERROR:
  48  *
  49  * Error domain for GVariant text format parsing.  Specific error codes
  50  * are not currently defined for this domain.  See #GError for
  51  * information on error domains.
  52  **/
  53 /**
  54  * GVariantParseError:
  55  * @G_VARIANT_PARSE_ERROR_FAILED: generic error (unused)
  56  * @G_VARIANT_PARSE_ERROR_BASIC_TYPE_EXPECTED: a non-basic #GVariantType was given where a basic type was expected
  57  * @G_VARIANT_PARSE_ERROR_CANNOT_INFER_TYPE: cannot infer the #GVariantType
  58  * @G_VARIANT_PARSE_ERROR_DEFINITE_TYPE_EXPECTED: an indefinite #GVariantType was given where a definite type was expected
  59  * @G_VARIANT_PARSE_ERROR_INPUT_NOT_AT_END: extra data after parsing finished
  60  * @G_VARIANT_PARSE_ERROR_INVALID_CHARACTER: invalid character in number or unicode escape
  61  * @G_VARIANT_PARSE_ERROR_INVALID_FORMAT_STRING: not a valid #GVariant format string
  62  * @G_VARIANT_PARSE_ERROR_INVALID_OBJECT_PATH: not a valid object path
  63  * @G_VARIANT_PARSE_ERROR_INVALID_SIGNATURE: not a valid type signature
  64  * @G_VARIANT_PARSE_ERROR_INVALID_TYPE_STRING: not a valid #GVariant type string
  65  * @G_VARIANT_PARSE_ERROR_NO_COMMON_TYPE: could not find a common type for array entries
  66  * @G_VARIANT_PARSE_ERROR_NUMBER_OUT_OF_RANGE: the numerical value is out of range of the given type
  67  * @G_VARIANT_PARSE_ERROR_NUMBER_TOO_BIG: the numerical value is out of range for any type
  68  * @G_VARIANT_PARSE_ERROR_TYPE_ERROR: cannot parse as variant of the specified type
  69  * @G_VARIANT_PARSE_ERROR_UNEXPECTED_TOKEN: an unexpected token was encountered
  70  * @G_VARIANT_PARSE_ERROR_UNKNOWN_KEYWORD: an unknown keyword was encountered
  71  * @G_VARIANT_PARSE_ERROR_UNTERMINATED_STRING_CONSTANT: unterminated string constant
  72  * @G_VARIANT_PARSE_ERROR_VALUE_EXPECTED: no value given
  73  * @G_VARIANT_PARSE_ERROR_RECURSION: variant was too deeply nested; #GVariant is only guaranteed to handle nesting up to 64 levels (Since: 2.64)
  74  *
  75  * Error codes returned by parsing text-format GVariants.
  76  **/
  77 G_DEFINE_QUARK (g-variant-parse-error-quark, g_variant_parse_error)
  78
  79 /**
  80  * g_variant_parser_get_error_quark:
  81  *
  82  * Same as g_variant_error_quark().
  83  *
  84  * Deprecated: Use g_variant_parse_error_quark() instead.
  85  */
  86 GQuark
  87 g_variant_parser_get_error_quark (void)
  88 {
  89   return g_variant_parse_error_quark ();
  90 }
  91
  92 typedef struct
  93 {
  94   gint start, end;
  95 } SourceRef;
  96
  97 G_GNUC_PRINTF(5, 0)
  98 static void
  99 parser_set_error_va (GError      **error,
 100                      SourceRef    *location,
 101                      SourceRef    *other,
 102                      gint          code,
 103                      const gchar  *format,
 104                      va_list       ap)
 105 {
 106   GString *msg = g_string_new (NULL);
 107
 108   if (location->start == location->end)
 109     g_string_append_printf (msg, "%d", location->start);
 110   else
 111     g_string_append_printf (msg, "%d-%d", location->start, location->end);
 112
 113   if (other != NULL)
 114     {
 115       g_assert (other->start != other->end);
 116       g_string_append_printf (msg, ",%d-%d", other->start, other->end);
 117     }
 118   g_string_append_c (msg, ':');
 119
 120   g_string_append_vprintf (msg, format, ap);
 121   g_set_error_literal (error, G_VARIANT_PARSE_ERROR, code, msg->str);
 122   g_string_free (msg, TRUE);
 123 }
 124
 125 G_GNUC_PRINTF(5, 6)
 126 static void
 127 parser_set_error (GError      **error,
 128                   SourceRef    *location,
 129                   SourceRef    *other,
 130                   gint          code,
 131                   const gchar  *format,
 132                   ...)
 133 {
 134   va_list ap;
 135
 136   va_start (ap, format);
 137   parser_set_error_va (error, location, other, code, format, ap);
 138   va_end (ap);
 139 }
 140
 141 typedef struct
 142 {
 143   const gchar *start;
 144   const gchar *stream;
 145   const gchar *end;
 146
 147   const gchar *this;
 148 } TokenStream;
 149
 150
 151 G_GNUC_PRINTF(5, 6)
 152 static void
 153 token_stream_set_error (TokenStream  *stream,
 154                         GError      **error,
 155                         gboolean      this_token,
 156                         gint          code,
 157                         const gchar  *format,
 158                         ...)
 159 {
 160   SourceRef ref;
 161   va_list ap;
 162
 163   ref.start = stream->this - stream->start;
 164
 165   if (this_token)
 166     ref.end = stream->stream - stream->start;
 167   else
 168     ref.end = ref.start;
 169
 170   va_start (ap, format);
 171   parser_set_error_va (error, &ref, NULL, code, format, ap);
 172   va_end (ap);
 173 }
 174
 175 static gboolean
 176 token_stream_prepare (TokenStream *stream)
 177 {
 178   gint brackets = 0;
 179   const gchar *end;
 180
 181   if (stream->this != NULL)
 182     return TRUE;
 183
 184   while (stream->stream != stream->end && g_ascii_isspace (*stream->stream))
 185     stream->stream++;
 186
 187   if (stream->stream == stream->end || *stream->stream == '\0')
 188     {
 189       stream->this = stream->stream;
 190       return FALSE;
 191     }
 192
 193   switch (stream->stream[0])
 194     {
 195     case '-': case '+': case '.': case '0': case '1': case '2':
 196     case '3': case '4': case '5': case '6': case '7': case '8':
 197     case '9':
 198       for (end = stream->stream; end != stream->end; end++)
 199         if (!g_ascii_isalnum (*end) &&
 200             *end != '-' && *end != '+' && *end != '.')
 201           break;
 202       break;
 203
 204     case 'b':
 205       if (stream->stream + 1 != stream->end &&
 206           (stream->stream[1] == '\'' || stream->stream[1] == '"'))
 207         {
 208           for (end = stream->stream + 2; end != stream->end; end++)
 209             if (*end == stream->stream[1] || *end == '\0' ||
 210                 (*end == '\\' && (++end == stream->end || *end == '\0')))
 211               break;
 212
 213           if (end != stream->end && *end)
 214             end++;
 215           break;
 216         }
 217
 218       G_GNUC_FALLTHROUGH;
 219
 220     case 'a': /* 'b' */ case 'c': case 'd': case 'e': case 'f':
 221     case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':
 222     case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':
 223     case 's': case 't': case 'u': case 'v': case 'w': case 'x':
 224     case 'y': case 'z':
 225       for (end = stream->stream; end != stream->end; end++)
 226         if (!g_ascii_isalnum (*end))
 227           break;
 228       break;
 229
 230     case '\'': case '"':
 231       for (end = stream->stream + 1; end != stream->end; end++)
 232         if (*end == stream->stream[0] || *end == '\0' ||
 233             (*end == '\\' && (++end == stream->end || *end == '\0')))
 234           break;
 235
 236       if (end != stream->end && *end)
 237         end++;
 238       break;
 239
 240     case '@': case '%':
 241       /* stop at the first space, comma, colon or unmatched bracket.
 242        * deals nicely with cases like (%i, %i) or {%i: %i}.
 243        * Also: ] and > are never in format strings.
 244        */
 245       for (end = stream->stream + 1;
 246            end != stream->end && *end != '\0' && *end != ',' &&
 247            *end != ':' && *end != '>' && *end != ']' && !g_ascii_isspace (*end);
 248            end++)
 249
 250         if (*end == '(' || *end == '{')
 251           brackets++;
 252
 253         else if ((*end == ')' || *end == '}') && !brackets--)
 254           break;
 255
 256       break;
 257
 258     default:
 259       end = stream->stream + 1;
 260       break;
 261     }
 262
 263   stream->this = stream->stream;
 264   stream->stream = end;
 265
 266   /* We must have at least one byte in a token. */
 267   g_assert (stream->stream - stream->this >= 1);
 268
 269   return TRUE;
 270 }
 271
 272 static void
 273 token_stream_next (TokenStream *stream)
 274 {
 275   stream->this = NULL;
 276 }
 277
 278 static gboolean
 279 token_stream_peek (TokenStream *stream,
 280                    gchar        first_char)
 281 {
 282   if (!token_stream_prepare (stream))
 283     return FALSE;
 284
 285   return stream->stream - stream->this >= 1 &&
 286          stream->this[0] == first_char;
 287 }
 288
 289 static gboolean
 290 token_stream_peek2 (TokenStream *stream,
 291                     gchar        first_char,
 292                     gchar        second_char)
 293 {
 294   if (!token_stream_prepare (stream))
 295     return FALSE;
 296
 297   return stream->stream - stream->this >= 2 &&
 298          stream->this[0] == first_char &&
 299          stream->this[1] == second_char;
 300 }
 301
 302 static gboolean
 303 token_stream_is_keyword (TokenStream *stream)
 304 {
 305   if (!token_stream_prepare (stream))
 306     return FALSE;
 307
 308   return stream->stream - stream->this >= 2 &&
 309          g_ascii_isalpha (stream->this[0]) &&
 310          g_ascii_isalpha (stream->this[1]);
 311 }
 312
 313 static gboolean
 314 token_stream_is_numeric (TokenStream *stream)
 315 {
 316   if (!token_stream_prepare (stream))
 317     return FALSE;
 318
 319   return (stream->stream - stream->this >= 1 &&
 320           (g_ascii_isdigit (stream->this[0]) ||
 321            stream->this[0] == '-' ||
 322            stream->this[0] == '+' ||
 323            stream->this[0] == '.'));
 324 }
 325
 326 static gboolean
 327 token_stream_peek_string (TokenStream *stream,
 328                           const gchar *token)
 329 {
 330   gint length = strlen (token);
 331
 332   return token_stream_prepare (stream) &&
 333          stream->stream - stream->this == length &&
 334          memcmp (stream->this, token, length) == 0;
 335 }
 336
 337 static gboolean
 338 token_stream_consume (TokenStream *stream,
 339                       const gchar *token)
 340 {
 341   if (!token_stream_peek_string (stream, token))
 342     return FALSE;
 343
 344   token_stream_next (stream);
 345   return TRUE;
 346 }
 347
 348 static gboolean
 349 token_stream_require (TokenStream  *stream,
 350                       const gchar  *token,
 351                       const gchar  *purpose,
 352                       GError      **error)
 353 {
 354
 355   if (!token_stream_consume (stream, token))
 356     {
 357       token_stream_set_error (stream, error, FALSE,
 358                               G_VARIANT_PARSE_ERROR_UNEXPECTED_TOKEN,
 359                               "expected '%s'%s", token, purpose);
 360       return FALSE;
 361     }
 362
 363   return TRUE;
 364 }
 365
 366 static void
 367 token_stream_assert (TokenStream *stream,
 368                      const gchar *token)
 369 {
 370   gboolean correct_token G_GNUC_UNUSED  /* when compiling with G_DISABLE_ASSERT */;
 371
 372   correct_token = token_stream_consume (stream, token);
 373   g_assert (correct_token);
 374 }
 375
 376 static gchar *
 377 token_stream_get (TokenStream *stream)
 378 {
 379   gchar *result;
 380
 381   if (!token_stream_prepare (stream))
 382     return NULL;
 383
 384   result = g_strndup (stream->this, stream->stream - stream->this);
 385
 386   return result;
 387 }
 388
 389 static void
 390 token_stream_start_ref (TokenStream *stream,
 391                         SourceRef   *ref)
 392 {
 393   token_stream_prepare (stream);
 394   ref->start = stream->this - stream->start;
 395 }
 396
 397 static void
 398 token_stream_end_ref (TokenStream *stream,
 399                       SourceRef   *ref)
 400 {
 401   ref->end = stream->stream - stream->start;
 402 }
 403
 404 static void
 405 pattern_copy (gchar       **out,
 406               const gchar **in)
 407 {
 408   gint brackets = 0;
 409
 410   while (**in == 'a' || **in == 'm' || **in == 'M')
 411     *(*out)++ = *(*in)++;
 412
 413   do
 414     {
 415       if (**in == '(' || **in == '{')
 416         brackets++;
 417
 418       else if (**in == ')' || **in == '}')
 419         brackets--;
 420
 421       *(*out)++ = *(*in)++;
 422     }
 423   while (brackets);
 424 }
 425
 426 /* Returns the most general pattern that is subpattern of left and subpattern
 427  * of right, or NULL if there is no such pattern. */
 428 static gchar *
 429 pattern_coalesce (const gchar *left,
 430                   const gchar *right)
 431 {
 432   gchar *result;
 433   gchar *out;
 434
 435   /* the length of the output is loosely bound by the sum of the input
 436    * lengths, not simply the greater of the two lengths.
 437    *
 438    *   (*(iii)) + ((iii)*) ((iii)(iii))
 439    *
 440    *      8     +    8    =  12
 441    */
 442   out = result = g_malloc (strlen (left) + strlen (right));
 443
 444   while (*left && *right)
 445     {
 446       if (*left == *right)
 447         {
 448           *out++ = *left++;
 449           right++;
 450         }
 451
 452       else
 453         {
 454           const gchar **one = &left, **the_other = &right;
 455
 456          again:
 457           if (**one == '*' && **the_other != ')')
 458             {
 459               pattern_copy (&out, the_other);
 460               (*one)++;
 461             }
 462
 463           else if (**one == 'M' && **the_other == 'm')
 464             {
 465               *out++ = *(*the_other)++;
 466             }
 467
 468           else if (**one == 'M' && **the_other != 'm' && **the_other != '*')
 469             {
 470               (*one)++;
 471             }
 472
 473           else if (**one == 'N' && strchr ("ynqiuxthd", **the_other))
 474             {
 475               *out++ = *(*the_other)++;
 476               (*one)++;
 477             }
 478
 479           else if (**one == 'S' && strchr ("sog", **the_other))
 480             {
 481               *out++ = *(*the_other)++;
 482               (*one)++;
 483             }
 484
 485           else if (one == &left)
 486             {
 487               one = &right, the_other = &left;
 488               goto again;
 489             }
 490
 491           else
 492             break;
 493         }
 494     }
 495
 496   if (*left || *right)
 497     {
 498       g_free (result);
 499       result = NULL;
 500     }
 501   else
 502     *out++ = '\0';
 503
 504   return result;
 505 }
 506
 507 typedef struct _AST AST;
 508 typedef gchar *    (*get_pattern_func)    (AST                 *ast,
 509                                            GError             **error);
 510 typedef GVariant * (*get_value_func)      (AST                 *ast,
 511                                            const GVariantType  *type,
 512                                            GError             **error);
 513 typedef GVariant * (*get_base_value_func) (AST                 *ast,
 514                                            const GVariantType  *type,
 515                                            GError             **error);
 516 typedef void       (*free_func)           (AST                 *ast);
 517
 518 typedef struct
 519 {
 520   gchar *    (* get_pattern)    (AST                 *ast,
 521                                  GError             **error);
 522   GVariant * (* get_value)      (AST                 *ast,
 523                                  const GVariantType  *type,
 524                                  GError             **error);
 525   GVariant * (* get_base_value) (AST                 *ast,
 526                                  const GVariantType  *type,
 527                                  GError             **error);
 528   void       (* free)           (AST                 *ast);
 529 } ASTClass;
 530
 531 struct _AST
 532 {
 533   const ASTClass *class;
 534   SourceRef source_ref;
 535 };
 536
 537 static gchar *
 538 ast_get_pattern (AST     *ast,
 539                  GError **error)
 540 {
 541   return ast->class->get_pattern (ast, error);
 542 }
 543
 544 static GVariant *
 545 ast_get_value (AST                 *ast,
 546                const GVariantType  *type,
 547                GError             **error)
 548 {
 549   return ast->class->get_value (ast, type, error);
 550 }
 551
 552 static void
 553 ast_free (AST *ast)
 554 {
 555   ast->class->free (ast);
 556 }
 557
 558 G_GNUC_PRINTF(5, 6)
 559 static void
 560 ast_set_error (AST          *ast,
 561                GError      **error,
 562                AST          *other_ast,
 563                gint          code,
 564                const gchar  *format,
 565                ...)
 566 {
 567   va_list ap;
 568
 569   va_start (ap, format);
 570   parser_set_error_va (error, &ast->source_ref,
 571                        other_ast ? & other_ast->source_ref : NULL,
 572                        code,
 573                        format, ap);
 574   va_end (ap);
 575 }
 576
 577 static GVariant *
 578 ast_type_error (AST                 *ast,
 579                 const GVariantType  *type,
 580                 GError             **error)
 581 {
 582   gchar *typestr;
 583
 584   typestr = g_variant_type_dup_string (type);
 585   ast_set_error (ast, error, NULL,
 586                  G_VARIANT_PARSE_ERROR_TYPE_ERROR,
 587                  "can not parse as value of type '%s'",
 588                  typestr);
 589   g_free (typestr);
 590
 591   return NULL;
 592 }
 593
 594 static GVariant *
 595 ast_resolve (AST     *ast,
 596              GError **error)
 597 {
 598   GVariant *value;
 599   gchar *pattern;
 600   gint i, j = 0;
 601
 602   pattern = ast_get_pattern (ast, error);
 603
 604   if (pattern == NULL)
 605     return NULL;
 606
 607   /* choose reasonable defaults
 608    *
 609    *   1) favour non-maybe values where possible
 610    *   2) default type for strings is 's'
 611    *   3) default type for integers is 'i'
 612    */
 613   for (i = 0; pattern[i]; i++)
 614     switch (pattern[i])
 615       {
 616       case '*':
 617         ast_set_error (ast, error, NULL,
 618                        G_VARIANT_PARSE_ERROR_CANNOT_INFER_TYPE,
 619                        "unable to infer type");
 620         g_free (pattern);
 621         return NULL;
 622
 623       case 'M':
 624         break;
 625
 626       case 'S':
 627         pattern[j++] = 's';
 628         break;
 629
 630       case 'N':
 631         pattern[j++] = 'i';
 632         break;
 633
 634       default:
 635         pattern[j++] = pattern[i];
 636         break;
 637       }
 638   pattern[j++] = '\0';
 639
 640   value = ast_get_value (ast, G_VARIANT_TYPE (pattern), error);
 641   g_free (pattern);
 642
 643   return value;
 644 }
 645
 646
 647 static AST *parse (TokenStream  *stream,
 648                    guint         max_depth,
 649                    va_list      *app,
 650                    GError      **error);
 651
 652 static void
 653 ast_array_append (AST  ***array,
 654                   gint   *n_items,
 655                   AST    *ast)
 656 {
 657   if ((*n_items & (*n_items - 1)) == 0)
 658     *array = g_renew (AST *, *array, *n_items ? 2 ** n_items : 1);
 659
 660   (*array)[(*n_items)++] = ast;
 661 }
 662
 663 static void
 664 ast_array_free (AST  **array,
 665                 gint   n_items)
 666 {
 667   gint i;
 668
 669   for (i = 0; i < n_items; i++)
 670     ast_free (array[i]);
 671   g_free (array);
 672 }
 673
 674 static gchar *
 675 ast_array_get_pattern (AST    **array,
 676                        gint     n_items,
 677                        GError **error)
 678 {
 679   gchar *pattern;
 680   gint i;
 681
 682   /* Find the pattern which applies to all children in the array, by l-folding a
 683    * coalesce operation.
 684    */
 685   pattern = ast_get_pattern (array[0], error);
 686
 687   if (pattern == NULL)
 688     return NULL;
 689
 690   for (i = 1; i < n_items; i++)
 691     {
 692       gchar *tmp, *merged;
 693
 694       tmp = ast_get_pattern (array[i], error);
 695
 696       if (tmp == NULL)
 697         {
 698           g_free (pattern);
 699           return NULL;
 700         }
 701
 702       merged = pattern_coalesce (pattern, tmp);
 703       g_free (pattern);
 704       pattern = merged;
 705
 706       if (merged == NULL)
 707         /* set coalescence implies pairwise coalescence (i think).
 708          * we should therefore be able to trace the failure to a single
 709          * pair of values.
 710          */
 711         {
 712           int j = 0;
 713
 714           while (TRUE)
 715             {
 716               gchar *tmp2;
 717               gchar *m;
 718
 719               /* if 'j' reaches 'i' then we didn't find the pair that failed
 720                * to coalesce. This shouldn't happen (see above), but just in
 721                * case report an error:
 722                */
 723               if (j >= i)
 724                 {
 725                   ast_set_error (array[i], error, NULL,
 726                                  G_VARIANT_PARSE_ERROR_NO_COMMON_TYPE,
 727                                  "unable to find a common type");
 728                   g_free (tmp);
 729                   return NULL;
 730                 }
 731
 732               tmp2 = ast_get_pattern (array[j], NULL);
 733               g_assert (tmp2 != NULL);
 734
 735               m = pattern_coalesce (tmp, tmp2);
 736               g_free (tmp2);
 737               g_free (m);
 738
 739               if (m == NULL)
 740                 {
 741                   /* we found a conflict between 'i' and 'j'.
 742                    *
 743                    * report the error.  note: 'j' is first.
 744                    */
 745                   ast_set_error (array[j], error, array[i],
 746                                  G_VARIANT_PARSE_ERROR_NO_COMMON_TYPE,
 747                                  "unable to find a common type");
 748                   g_free (tmp);
 749                   return NULL;
 750                 }
 751
 752               j++;
 753             }
 754
 755         }
 756
 757       g_free (tmp);
 758     }
 759
 760   return pattern;
 761 }
 762
 763 typedef struct
 764 {
 765   AST ast;
 766
 767   AST *child;
 768 } Maybe;
 769
 770 static gchar *
 771 maybe_get_pattern (AST     *ast,
 772                    GError **error)
 773 {
 774   Maybe *maybe = (Maybe *) ast;
 775
 776   if (maybe->child != NULL)
 777     {
 778       gchar *child_pattern;
 779       gchar *pattern;
 780
 781       child_pattern = ast_get_pattern (maybe->child, error);
 782
 783       if (child_pattern == NULL)
 784         return NULL;
 785
 786       pattern = g_strdup_printf ("m%s", child_pattern);
 787       g_free (child_pattern);
 788
 789       return pattern;
 790     }
 791
 792   return g_strdup ("m*");
 793 }
 794
 795 static GVariant *
 796 maybe_get_value (AST                 *ast,
 797                  const GVariantType  *type,
 798                  GError             **error)
 799 {
 800   Maybe *maybe = (Maybe *) ast;
 801   GVariant *value;
 802
 803   if (!g_variant_type_is_maybe (type))
 804     return ast_type_error (ast, type, error);
 805
 806   type = g_variant_type_element (type);
 807
 808   if (maybe->child)
 809     {
 810       value = ast_get_value (maybe->child, type, error);
 811
 812       if (value == NULL)
 813         return NULL;
 814     }
 815   else
 816     value = NULL;
 817
 818   return g_variant_new_maybe (type, value);
 819 }
 820
 821 static void
 822 maybe_free (AST *ast)
 823 {
 824   Maybe *maybe = (Maybe *) ast;
 825
 826   if (maybe->child != NULL)
 827     ast_free (maybe->child);
 828
 829   g_slice_free (Maybe, maybe);
 830 }
 831
 832 static AST *
 833 maybe_parse (TokenStream  *stream,
 834              guint         max_depth,
 835              va_list      *app,
 836              GError      **error)
 837 {
 838   static const ASTClass maybe_class = {
 839     maybe_get_pattern,
 840     maybe_get_value, NULL,
 841     maybe_free
 842   };
 843   AST *child = NULL;
 844   Maybe *maybe;
 845
 846   if (token_stream_consume (stream, "just"))
 847     {
 848       child = parse (stream, max_depth - 1, app, error);
 849       if (child == NULL)
 850         return NULL;
 851     }
 852
 853   else if (!token_stream_consume (stream, "nothing"))
 854     {
 855       token_stream_set_error (stream, error, TRUE,
 856                               G_VARIANT_PARSE_ERROR_UNKNOWN_KEYWORD,
 857                               "unknown keyword");
 858       return NULL;
 859     }
 860
 861   maybe = g_slice_new (Maybe);
 862   maybe->ast.class = &maybe_class;
 863   maybe->child = child;
 864
 865   return (AST *) maybe;
 866 }
 867
 868 static GVariant *
 869 maybe_wrapper (AST                 *ast,
 870                const GVariantType  *type,
 871                GError             **error)
 872 {
 873   const GVariantType *base_type;
 874   GVariant *base_value;
 875   GVariant *value = NULL;
 876   unsigned int depth;
 877   gboolean trusted;
 878   GVariantTypeInfo *base_type_info = NULL;
 879   gsize base_serialised_fixed_size, base_serialised_size, serialised_size, n_suffix_zeros;
 880   guint8 *serialised = NULL;
 881   GBytes *bytes = NULL;
 882   gsize i;
 883
 884   for (depth = 0, base_type = type;
 885        g_variant_type_is_maybe (base_type);
 886        depth++, base_type = g_variant_type_element (base_type));
 887
 888   base_value = ast->class->get_base_value (ast, base_type, error);
 889
 890   if (base_value == NULL || depth == 0)
 891     return g_steal_pointer (&base_value);
 892
 893   /* This is the equivalent of calling g_variant_new_maybe() in a loop enough
 894    * times to match the number of nested maybe types in @type. It does the same
 895    * in a single `GVariant` allocation, though.
 896    *
 897    * This avoids maybe_wrapper() becoming an attack vector where a malicious
 898    * text-form variant can create a long array, and insert a typedecl for a
 899    * deeply nested maybe type on one of its elements. This is achievable with a
 900    * relatively short text form, but results in O(array length × typedecl depth)
 901    * allocations. This is a denial of service attack.
 902    *
 903    * Instead of constructing a tree of `GVariant`s in tree-form to match the
 904    * @ast, construct a single `GVariant` containing the serialised form of the
 905    * maybe-wrappers and the base value that they contain. This is relatively
 906    * straightforward: serialise the base value, and then append the correct
 907    * number of zero bytes for the maybe-wrappers.
 908    *
 909    * This is a bit of a layering violation, unfortunately.
 910    *
 911    * By doing this, the typedecl depth variable is reduced to O(1).
 912    */
 913   trusted = g_variant_is_trusted (base_value);
 914
 915   /* See https://developer.gnome.org/documentation/specifications/gvariant-specification-1.0.html#maybes
 916    *
 917    * The serialised form of a `Just x` is the serialised form of `x` if `x` is
 918    * fixed-size, and the serialised form of `x` plus a trailing zero byte if `x`
 919    * is variable-size. A `Maybe` variant is always variable-size, even if its
 920    * child element is fixed-size, because it might be `Nothing`. This means that
 921    * all the maybe-wrappers which are not the innermost are always serialised
 922    * with one trailing zero byte each.
 923    *
 924    * The serialised form of a `Nothing` is an empty byte sequence, but that’s
 925    * already handled above in the `base_value == NULL` case.
 926    */
 927   base_type_info = g_variant_type_info_get (base_type);
 928   g_variant_type_info_query (base_type_info, NULL, &base_serialised_fixed_size);
 929   g_variant_type_info_unref (base_type_info);
 930
 931   base_serialised_size = g_variant_get_size (base_value);
 932   n_suffix_zeros = (base_serialised_fixed_size > 0) ? depth - 1 : depth;
 933   g_assert (base_serialised_size <= G_MAXSIZE - n_suffix_zeros);
 934   serialised_size = base_serialised_size + n_suffix_zeros;
 935
 936   g_assert (serialised_size >= base_serialised_size);
 937
 938   /* Serialise the base value. */
 939   serialised = g_malloc (serialised_size);
 940   g_variant_store (base_value, serialised);
 941
 942   /* Zero-out the suffix zeros to complete the serialisation of the maybe wrappers. */
 943   for (i = base_serialised_size; i < serialised_size; i++)
 944     serialised[i] = 0;
 945
 946   bytes = g_bytes_new_take (g_steal_pointer (&serialised), serialised_size);
 947   value = g_variant_new_from_bytes (type, bytes, trusted);
 948   g_bytes_unref (bytes);
 949
 950   g_variant_unref (base_value);
 951
 952   return g_steal_pointer (&value);
 953 }
 954
 955 typedef struct
 956 {
 957   AST ast;
 958
 959   AST **children;
 960   gint n_children;
 961 } Array;
 962
 963 static gchar *
 964 array_get_pattern (AST     *ast,
 965                    GError **error)
 966 {
 967   Array *array = (Array *) ast;
 968   gchar *pattern;
 969   gchar *result;
 970
 971   if (array->n_children == 0)
 972     return g_strdup ("Ma*");
 973
 974   pattern = ast_array_get_pattern (array->children, array->n_children, error);
 975
 976   if (pattern == NULL)
 977     return NULL;
 978
 979   result = g_strdup_printf ("Ma%s", pattern);
 980   g_free (pattern);
 981
 982   return result;
 983 }
 984
 985 static GVariant *
 986 array_get_value (AST                 *ast,
 987                  const GVariantType  *type,
 988                  GError             **error)
 989 {
 990   Array *array = (Array *) ast;
 991   const GVariantType *childtype;
 992   GVariantBuilder builder;
 993   gint i;
 994
 995   if (!g_variant_type_is_array (type))
 996     return ast_type_error (ast, type, error);
 997
 998   g_variant_builder_init (&builder, type);
 999   childtype = g_variant_type_element (type);
1000
1001   for (i = 0; i < array->n_children; i++)
1002     {
1003       GVariant *child;
1004
1005       if (!(child = ast_get_value (array->children[i], childtype, error)))
1006         {
1007           g_variant_builder_clear (&builder);
1008           return NULL;
1009         }
1010
1011       g_variant_builder_add_value (&builder, child);
1012     }
1013
1014   return g_variant_builder_end (&builder);
1015 }
1016
1017 static void
1018 array_free (AST *ast)
1019 {
1020   Array *array = (Array *) ast;
1021
1022   ast_array_free (array->children, array->n_children);
1023   g_slice_free (Array, array);
1024 }
1025
1026 static AST *
1027 array_parse (TokenStream  *stream,
1028              guint         max_depth,
1029              va_list      *app,
1030              GError      **error)
1031 {
1032   static const ASTClass array_class = {
1033     array_get_pattern,
1034     maybe_wrapper, array_get_value,
1035     array_free
1036   };
1037   gboolean need_comma = FALSE;
1038   Array *array;
1039
1040   array = g_slice_new (Array);
1041   array->ast.class = &array_class;
1042   array->children = NULL;
1043   array->n_children = 0;
1044
1045   token_stream_assert (stream, "[");
1046   while (!token_stream_consume (stream, "]"))
1047     {
1048       AST *child;
1049
1050       if (need_comma &&
1051           !token_stream_require (stream, ",",
1052                                  " or ']' to follow array element",
1053                                  error))
1054         goto error;
1055
1056       child = parse (stream, max_depth - 1, app, error);
1057
1058       if (!child)
1059         goto error;
1060
1061       ast_array_append (&array->children, &array->n_children, child);
1062       need_comma = TRUE;
1063     }
1064
1065   return (AST *) array;
1066
1067  error:
1068   ast_array_free (array->children, array->n_children);
1069   g_slice_free (Array, array);
1070
1071   return NULL;
1072 }
1073
1074 typedef struct
1075 {
1076   AST ast;
1077
1078   AST **children;
1079   gint n_children;
1080 } Tuple;
1081
1082 static gchar *
1083 tuple_get_pattern (AST     *ast,
1084                    GError **error)
1085 {
1086   Tuple *tuple = (Tuple *) ast;
1087   gchar *result = NULL;
1088   gchar **parts;
1089   gint i;
1090
1091   parts = g_new (gchar *, tuple->n_children + 4);
1092   parts[tuple->n_children + 1] = (gchar *) ")";
1093   parts[tuple->n_children + 2] = NULL;
1094   parts[0] = (gchar *) "M(";
1095
1096   for (i = 0; i < tuple->n_children; i++)
1097     if (!(parts[i + 1] = ast_get_pattern (tuple->children[i], error)))
1098       break;
1099
1100   if (i == tuple->n_children)
1101     result = g_strjoinv ("", parts);
1102
1103   /* parts[0] should not be freed */
1104   while (i)
1105     g_free (parts[i--]);
1106   g_free (parts);
1107
1108   return result;
1109 }
1110
1111 static GVariant *
1112 tuple_get_value (AST                 *ast,
1113                  const GVariantType  *type,
1114                  GError             **error)
1115 {
1116   Tuple *tuple = (Tuple *) ast;
1117   const GVariantType *childtype;
1118   GVariantBuilder builder;
1119   gint i;
1120
1121   if (!g_variant_type_is_tuple (type))
1122     return ast_type_error (ast, type, error);
1123
1124   g_variant_builder_init (&builder, type);
1125   childtype = g_variant_type_first (type);
1126
1127   for (i = 0; i < tuple->n_children; i++)
1128     {
1129       GVariant *child;
1130
1131       if (childtype == NULL)
1132         {
1133           g_variant_builder_clear (&builder);
1134           return ast_type_error (ast, type, error);
1135         }
1136
1137       if (!(child = ast_get_value (tuple->children[i], childtype, error)))
1138         {
1139           g_variant_builder_clear (&builder);
1140           return FALSE;
1141         }
1142
1143       g_variant_builder_add_value (&builder, child);
1144       childtype = g_variant_type_next (childtype);
1145     }
1146
1147   if (childtype != NULL)
1148     {
1149       g_variant_builder_clear (&builder);
1150       return ast_type_error (ast, type, error);
1151     }
1152
1153   return g_variant_builder_end (&builder);
1154 }
1155
1156 static void
1157 tuple_free (AST *ast)
1158 {
1159   Tuple *tuple = (Tuple *) ast;
1160
1161   ast_array_free (tuple->children, tuple->n_children);
1162   g_slice_free (Tuple, tuple);
1163 }
1164
1165 static AST *
1166 tuple_parse (TokenStream  *stream,
1167              guint         max_depth,
1168              va_list      *app,
1169              GError      **error)
1170 {
1171   static const ASTClass tuple_class = {
1172     tuple_get_pattern,
1173     maybe_wrapper, tuple_get_value,
1174     tuple_free
1175   };
1176   gboolean need_comma = FALSE;
1177   gboolean first = TRUE;
1178   Tuple *tuple;
1179
1180   tuple = g_slice_new (Tuple);
1181   tuple->ast.class = &tuple_class;
1182   tuple->children = NULL;
1183   tuple->n_children = 0;
1184
1185   token_stream_assert (stream, "(");
1186   while (!token_stream_consume (stream, ")"))
1187     {
1188       AST *child;
1189
1190       if (need_comma &&
1191           !token_stream_require (stream, ",",
1192                                  " or ')' to follow tuple element",
1193                                  error))
1194         goto error;
1195
1196       child = parse (stream, max_depth - 1, app, error);
1197
1198       if (!child)
1199         goto error;
1200
1201       ast_array_append (&tuple->children, &tuple->n_children, child);
1202
1203       /* the first time, we absolutely require a comma, so grab it here
1204        * and leave need_comma = FALSE so that the code above doesn't
1205        * require a second comma.
1206        *
1207        * the second and remaining times, we set need_comma = TRUE.
1208        */
1209       if (first)
1210         {
1211           if (!token_stream_require (stream, ",",
1212                                      " after first tuple element", error))
1213             goto error;
1214
1215           first = FALSE;
1216         }
1217       else
1218         need_comma = TRUE;
1219     }
1220
1221   return (AST *) tuple;
1222
1223  error:
1224   ast_array_free (tuple->children, tuple->n_children);
1225   g_slice_free (Tuple, tuple);
1226
1227   return NULL;
1228 }
1229
1230 typedef struct
1231 {
1232   AST ast;
1233
1234   AST *value;
1235 } Variant;
1236
1237 static gchar *
1238 variant_get_pattern (AST     *ast,
1239                      GError **error)
1240 {
1241   return g_strdup ("Mv");
1242 }
1243
1244 static GVariant *
1245 variant_get_value (AST                 *ast,
1246                    const GVariantType  *type,
1247                    GError             **error)
1248 {
1249   Variant *variant = (Variant *) ast;
1250   GVariant *child;
1251
1252   if (!g_variant_type_equal (type, G_VARIANT_TYPE_VARIANT))
1253     return ast_type_error (ast, type, error);
1254
1255   child = ast_resolve (variant->value, error);
1256
1257   if (child == NULL)
1258     return NULL;
1259
1260   return g_variant_new_variant (child);
1261 }
1262
1263 static void
1264 variant_free (AST *ast)
1265 {
1266   Variant *variant = (Variant *) ast;
1267
1268   ast_free (variant->value);
1269   g_slice_free (Variant, variant);
1270 }
1271
1272 static AST *
1273 variant_parse (TokenStream  *stream,
1274                guint         max_depth,
1275                va_list      *app,
1276                GError      **error)
1277 {
1278   static const ASTClass variant_class = {
1279     variant_get_pattern,
1280     maybe_wrapper, variant_get_value,
1281     variant_free
1282   };
1283   Variant *variant;
1284   AST *value;
1285
1286   token_stream_assert (stream, "<");
1287   value = parse (stream, max_depth - 1, app, error);
1288
1289   if (!value)
1290     return NULL;
1291
1292   if (!token_stream_require (stream, ">", " to follow variant value", error))
1293     {
1294       ast_free (value);
1295       return NULL;
1296     }
1297
1298   variant = g_slice_new (Variant);
1299   variant->ast.class = &variant_class;
1300   variant->value = value;
1301
1302   return (AST *) variant;
1303 }
1304
1305 typedef struct
1306 {
1307   AST ast;
1308
1309   AST **keys;
1310   AST **values;
1311   gint n_children;
1312 } Dictionary;
1313
1314 static gchar *
1315 dictionary_get_pattern (AST     *ast,
1316                         GError **error)
1317 {
1318   Dictionary *dict = (Dictionary *) ast;
1319   gchar *value_pattern;
1320   gchar *key_pattern;
1321   gchar key_char;
1322   gchar *result;
1323
1324   if (dict->n_children == 0)
1325     return g_strdup ("Ma{**}");
1326
1327   key_pattern = ast_array_get_pattern (dict->keys,
1328                                        abs (dict->n_children),
1329                                        error);
1330
1331   if (key_pattern == NULL)
1332     return NULL;
1333
1334   /* we can not have maybe keys */
1335   if (key_pattern[0] == 'M')
1336     key_char = key_pattern[1];
1337   else
1338     key_char = key_pattern[0];
1339
1340   g_free (key_pattern);
1341
1342   /* the basic types,
1343    * plus undetermined number type and undetermined string type.
1344    */
1345   if (!strchr ("bynqiuxthdsogNS", key_char))
1346     {
1347       ast_set_error (ast, error, NULL,
1348                      G_VARIANT_PARSE_ERROR_BASIC_TYPE_EXPECTED,
1349                      "dictionary keys must have basic types");
1350       return NULL;
1351     }
1352
1353   value_pattern = ast_get_pattern (dict->values[0], error);
1354
1355   if (value_pattern == NULL)
1356     return NULL;
1357
1358   result = g_strdup_printf ("M%s{%c%s}",
1359                             dict->n_children > 0 ? "a" : "",
1360                             key_char, value_pattern);
1361   g_free (value_pattern);
1362
1363   return result;
1364 }
1365
1366 static GVariant *
1367 dictionary_get_value (AST                 *ast,
1368                       const GVariantType  *type,
1369                       GError             **error)
1370 {
1371   Dictionary *dict = (Dictionary *) ast;
1372
1373   if (dict->n_children == -1)
1374     {
1375       const GVariantType *subtype;
1376       GVariantBuilder builder;
1377       GVariant *subvalue;
1378
1379       if (!g_variant_type_is_dict_entry (type))
1380         return ast_type_error (ast, type, error);
1381
1382       g_variant_builder_init (&builder, type);
1383
1384       subtype = g_variant_type_key (type);
1385       if (!(subvalue = ast_get_value (dict->keys[0], subtype, error)))
1386         {
1387           g_variant_builder_clear (&builder);
1388           return NULL;
1389         }
1390       g_variant_builder_add_value (&builder, subvalue);
1391
1392       subtype = g_variant_type_value (type);
1393       if (!(subvalue = ast_get_value (dict->values[0], subtype, error)))
1394         {
1395           g_variant_builder_clear (&builder);
1396           return NULL;
1397         }
1398       g_variant_builder_add_value (&builder, subvalue);
1399
1400       return g_variant_builder_end (&builder);
1401     }
1402   else
1403     {
1404       const GVariantType *entry, *key, *val;
1405       GVariantBuilder builder;
1406       gint i;
1407
1408       if (!g_variant_type_is_subtype_of (type, G_VARIANT_TYPE_DICTIONARY))
1409         return ast_type_error (ast, type, error);
1410
1411       entry = g_variant_type_element (type);
1412       key = g_variant_type_key (entry);
1413       val = g_variant_type_value (entry);
1414
1415       g_variant_builder_init (&builder, type);
1416
1417       for (i = 0; i < dict->n_children; i++)
1418         {
1419           GVariant *subvalue;
1420
1421           g_variant_builder_open (&builder, entry);
1422
1423           if (!(subvalue = ast_get_value (dict->keys[i], key, error)))
1424             {
1425               g_variant_builder_clear (&builder);
1426               return NULL;
1427             }
1428           g_variant_builder_add_value (&builder, subvalue);
1429
1430           if (!(subvalue = ast_get_value (dict->values[i], val, error)))
1431             {
1432               g_variant_builder_clear (&builder);
1433               return NULL;
1434             }
1435           g_variant_builder_add_value (&builder, subvalue);
1436           g_variant_builder_close (&builder);
1437         }
1438
1439       return g_variant_builder_end (&builder);
1440     }
1441 }
1442
1443 static void
1444 dictionary_free (AST *ast)
1445 {
1446   Dictionary *dict = (Dictionary *) ast;
1447   gint n_children;
1448
1449   if (dict->n_children > -1)
1450     n_children = dict->n_children;
1451   else
1452     n_children = 1;
1453
1454   ast_array_free (dict->keys, n_children);
1455   ast_array_free (dict->values, n_children);
1456   g_slice_free (Dictionary, dict);
1457 }
1458
1459 static AST *
1460 dictionary_parse (TokenStream  *stream,
1461                   guint         max_depth,
1462                   va_list      *app,
1463                   GError      **error)
1464 {
1465   static const ASTClass dictionary_class = {
1466     dictionary_get_pattern,
1467     maybe_wrapper, dictionary_get_value,
1468     dictionary_free
1469   };
1470   gint n_keys, n_values;
1471   gboolean only_one;
1472   Dictionary *dict;
1473   AST *first;
1474
1475   dict = g_slice_new (Dictionary);
1476   dict->ast.class = &dictionary_class;
1477   dict->keys = NULL;
1478   dict->values = NULL;
1479   n_keys = n_values = 0;
1480
1481   token_stream_assert (stream, "{");
1482
1483   if (token_stream_consume (stream, "}"))
1484     {
1485       dict->n_children = 0;
1486       return (AST *) dict;
1487     }
1488
1489   if ((first = parse (stream, max_depth - 1, app, error)) == NULL)
1490     goto error;
1491
1492   ast_array_append (&dict->keys, &n_keys, first);
1493
1494   only_one = token_stream_consume (stream, ",");
1495   if (!only_one &&
1496       !token_stream_require (stream, ":",
1497                              " or ',' to follow dictionary entry key",
1498                              error))
1499     goto error;
1500
1501   if ((first = parse (stream, max_depth - 1, app, error)) == NULL)
1502     goto error;
1503
1504   ast_array_append (&dict->values, &n_values, first);
1505
1506   if (only_one)
1507     {
1508       if (!token_stream_require (stream, "}", " at end of dictionary entry",
1509                                  error))
1510         goto error;
1511
1512       g_assert (n_keys == 1 && n_values == 1);
1513       dict->n_children = -1;
1514
1515       return (AST *) dict;
1516     }
1517
1518   while (!token_stream_consume (stream, "}"))
1519     {
1520       AST *child;
1521
1522       if (!token_stream_require (stream, ",",
1523                                  " or '}' to follow dictionary entry", error))
1524         goto error;
1525
1526       child = parse (stream, max_depth - 1, app, error);
1527
1528       if (!child)
1529         goto error;
1530
1531       ast_array_append (&dict->keys, &n_keys, child);
1532
1533       if (!token_stream_require (stream, ":",
1534                                  " to follow dictionary entry key", error))
1535         goto error;
1536
1537       child = parse (stream, max_depth - 1, app, error);
1538
1539       if (!child)
1540         goto error;
1541
1542       ast_array_append (&dict->values, &n_values, child);
1543     }
1544
1545   g_assert (n_keys == n_values);
1546   dict->n_children = n_keys;
1547
1548   return (AST *) dict;
1549
1550  error:
1551   ast_array_free (dict->keys, n_keys);
1552   ast_array_free (dict->values, n_values);
1553   g_slice_free (Dictionary, dict);
1554
1555   return NULL;
1556 }
1557
1558 typedef struct
1559 {
1560   AST ast;
1561   gchar *string;
1562 } String;
1563
1564 static gchar *
1565 string_get_pattern (AST     *ast,
1566                     GError **error)
1567 {
1568   return g_strdup ("MS");
1569 }
1570
1571 static GVariant *
1572 string_get_value (AST                 *ast,
1573                   const GVariantType  *type,
1574                   GError             **error)
1575 {
1576   String *string = (String *) ast;
1577
1578   if (g_variant_type_equal (type, G_VARIANT_TYPE_STRING))
1579     return g_variant_new_string (string->string);
1580
1581   else if (g_variant_type_equal (type, G_VARIANT_TYPE_OBJECT_PATH))
1582     {
1583       if (!g_variant_is_object_path (string->string))
1584         {
1585           ast_set_error (ast, error, NULL,
1586                          G_VARIANT_PARSE_ERROR_INVALID_OBJECT_PATH,
1587                          "not a valid object path");
1588           return NULL;
1589         }
1590
1591       return g_variant_new_object_path (string->string);
1592     }
1593
1594   else if (g_variant_type_equal (type, G_VARIANT_TYPE_SIGNATURE))
1595     {
1596       if (!g_variant_is_signature (string->string))
1597         {
1598           ast_set_error (ast, error, NULL,
1599                          G_VARIANT_PARSE_ERROR_INVALID_SIGNATURE,
1600                          "not a valid signature");
1601           return NULL;
1602         }
1603
1604       return g_variant_new_signature (string->string);
1605     }
1606
1607   else
1608     return ast_type_error (ast, type, error);
1609 }
1610
1611 static void
1612 string_free (AST *ast)
1613 {
1614   String *string = (String *) ast;
1615
1616   g_free (string->string);
1617   g_slice_free (String, string);
1618 }
1619
1620 /* Accepts exactly @length hexadecimal digits. No leading sign or `0x`/`0X` prefix allowed.
1621  * No leading/trailing space allowed. */
1622 static gboolean
1623 unicode_unescape (const gchar  *src,
1624                   gint         *src_ofs,
1625                   gchar        *dest,
1626                   gint         *dest_ofs,
1627                   gsize         length,
1628                   SourceRef    *ref,
1629                   GError      **error)
1630 {
1631   gchar buffer[9];
1632   guint64 value = 0;
1633   gchar *end = NULL;
1634   gsize n_valid_chars;
1635
1636   (*src_ofs)++;
1637
1638   g_assert (length < sizeof (buffer));
1639   strncpy (buffer, src + *src_ofs, length);
1640   buffer[length] = '\0';
1641
1642   for (n_valid_chars = 0; n_valid_chars < length; n_valid_chars++)
1643     if (!g_ascii_isxdigit (buffer[n_valid_chars]))
1644       break;
1645
1646   if (n_valid_chars == length)
1647     value = g_ascii_strtoull (buffer, &end, 0x10);
1648
1649   if (value == 0 || end != buffer + length)
1650     {
1651       SourceRef escape_ref;
1652
1653       escape_ref = *ref;
1654       escape_ref.start += *src_ofs;
1655       escape_ref.end = escape_ref.start + n_valid_chars;
1656
1657       parser_set_error (error, &escape_ref, NULL,
1658                         G_VARIANT_PARSE_ERROR_INVALID_CHARACTER,
1659                         "invalid %" G_GSIZE_FORMAT "-character unicode escape", length);
1660       return FALSE;
1661     }
1662
1663   g_assert (value <= G_MAXUINT32);
1664
1665   *dest_ofs += g_unichar_to_utf8 (value, dest + *dest_ofs);
1666   *src_ofs += length;
1667
1668   return TRUE;
1669 }
1670
1671 static AST *
1672 string_parse (TokenStream  *stream,
1673               va_list      *app,
1674               GError      **error)
1675 {
1676   static const ASTClass string_class = {
1677     string_get_pattern,
1678     maybe_wrapper, string_get_value,
1679     string_free
1680   };
1681   String *string;
1682   SourceRef ref;
1683   gchar *token;
1684   gsize length;
1685   gchar quote;
1686   gchar *str;
1687   gint i, j;
1688
1689   token_stream_start_ref (stream, &ref);
1690   token = token_stream_get (stream);
1691   token_stream_end_ref (stream, &ref);
1692   length = strlen (token);
1693   quote = token[0];
1694
1695   str = g_malloc (length);
1696   g_assert (quote == '"' || quote == '\'');
1697   j = 0;
1698   i = 1;
1699   while (token[i] != quote)
1700     switch (token[i])
1701       {
1702       case '\0':
1703         parser_set_error (error, &ref, NULL,
1704                           G_VARIANT_PARSE_ERROR_UNTERMINATED_STRING_CONSTANT,
1705                           "unterminated string constant");
1706         g_free (token);
1707         g_free (str);
1708         return NULL;
1709
1710       case '\\':
1711         switch (token[++i])
1712           {
1713           case '\0':
1714             parser_set_error (error, &ref, NULL,
1715                               G_VARIANT_PARSE_ERROR_UNTERMINATED_STRING_CONSTANT,
1716                               "unterminated string constant");
1717             g_free (token);
1718             g_free (str);
1719             return NULL;
1720
1721           case 'u':
1722             if (!unicode_unescape (token, &i, str, &j, 4, &ref, error))
1723               {
1724                 g_free (token);
1725                 g_free (str);
1726                 return NULL;
1727               }
1728             continue;
1729
1730           case 'U':
1731             if (!unicode_unescape (token, &i, str, &j, 8, &ref, error))
1732               {
1733                 g_free (token);
1734                 g_free (str);
1735                 return NULL;
1736               }
1737             continue;
1738
1739           case 'a': str[j++] = '\a'; i++; continue;
1740           case 'b': str[j++] = '\b'; i++; continue;
1741           case 'f': str[j++] = '\f'; i++; continue;
1742           case 'n': str[j++] = '\n'; i++; continue;
1743           case 'r': str[j++] = '\r'; i++; continue;
1744           case 't': str[j++] = '\t'; i++; continue;
1745           case 'v': str[j++] = '\v'; i++; continue;
1746           case '\n': i++; continue;
1747           }
1748
1749         G_GNUC_FALLTHROUGH;
1750
1751       default:
1752         str[j++] = token[i++];
1753       }
1754   str[j++] = '\0';
1755   g_free (token);
1756
1757   string = g_slice_new (String);
1758   string->ast.class = &string_class;
1759   string->string = str;
1760
1761   token_stream_next (stream);
1762
1763   return (AST *) string;
1764 }
1765
1766 typedef struct
1767 {
1768   AST ast;
1769   gchar *string;
1770 } ByteString;
1771
1772 static gchar *
1773 bytestring_get_pattern (AST     *ast,
1774                         GError **error)
1775 {
1776   return g_strdup ("May");
1777 }
1778
1779 static GVariant *
1780 bytestring_get_value (AST                 *ast,
1781                       const GVariantType  *type,
1782                       GError             **error)
1783 {
1784   ByteString *string = (ByteString *) ast;
1785
1786   if (!g_variant_type_equal (type, G_VARIANT_TYPE_BYTESTRING))
1787     return ast_type_error (ast, type, error);
1788
1789   return g_variant_new_bytestring (string->string);
1790 }
1791
1792 static void
1793 bytestring_free (AST *ast)
1794 {
1795   ByteString *string = (ByteString *) ast;
1796
1797   g_free (string->string);
1798   g_slice_free (ByteString, string);
1799 }
1800
1801 static AST *
1802 bytestring_parse (TokenStream  *stream,
1803                   va_list      *app,
1804                   GError      **error)
1805 {
1806   static const ASTClass bytestring_class = {
1807     bytestring_get_pattern,
1808     maybe_wrapper, bytestring_get_value,
1809     bytestring_free
1810   };
1811   ByteString *string;
1812   SourceRef ref;
1813   gchar *token;
1814   gsize length;
1815   gchar quote;
1816   gchar *str;
1817   gint i, j;
1818
1819   token_stream_start_ref (stream, &ref);
1820   token = token_stream_get (stream);
1821   token_stream_end_ref (stream, &ref);
1822   g_assert (token[0] == 'b');
1823   length = strlen (token);
1824   quote = token[1];
1825
1826   str = g_malloc (length);
1827   g_assert (quote == '"' || quote == '\'');
1828   j = 0;
1829   i = 2;
1830   while (token[i] != quote)
1831     switch (token[i])
1832       {
1833       case '\0':
1834         parser_set_error (error, &ref, NULL,
1835                           G_VARIANT_PARSE_ERROR_UNTERMINATED_STRING_CONSTANT,
1836                           "unterminated string constant");
1837         g_free (str);
1838         g_free (token);
1839         return NULL;
1840
1841       case '\\':
1842         switch (token[++i])
1843           {
1844           case '\0':
1845             parser_set_error (error, &ref, NULL,
1846                               G_VARIANT_PARSE_ERROR_UNTERMINATED_STRING_CONSTANT,
1847                               "unterminated string constant");
1848             g_free (str);
1849             g_free (token);
1850             return NULL;
1851
1852           case '0': case '1': case '2': case '3':
1853           case '4': case '5': case '6': case '7':
1854             {
1855               /* up to 3 characters */
1856               guchar val = token[i++] - '0';
1857
1858               if ('0' <= token[i] && token[i] < '8')
1859                 val = (val << 3) | (token[i++] - '0');
1860
1861               if ('0' <= token[i] && token[i] < '8')
1862                 val = (val << 3) | (token[i++] - '0');
1863
1864               str[j++] = val;
1865             }
1866             continue;
1867
1868           case 'a': str[j++] = '\a'; i++; continue;
1869           case 'b': str[j++] = '\b'; i++; continue;
1870           case 'f': str[j++] = '\f'; i++; continue;
1871           case 'n': str[j++] = '\n'; i++; continue;
1872           case 'r': str[j++] = '\r'; i++; continue;
1873           case 't': str[j++] = '\t'; i++; continue;
1874           case 'v': str[j++] = '\v'; i++; continue;
1875           case '\n': i++; continue;
1876           }
1877
1878         G_GNUC_FALLTHROUGH;
1879
1880       default:
1881         str[j++] = token[i++];
1882       }
1883   str[j++] = '\0';
1884   g_free (token);
1885
1886   string = g_slice_new (ByteString);
1887   string->ast.class = &bytestring_class;
1888   string->string = str;
1889
1890   token_stream_next (stream);
1891
1892   return (AST *) string;
1893 }
1894
1895 typedef struct
1896 {
1897   AST ast;
1898
1899   gchar *token;
1900 } Number;
1901
1902 static gchar *
1903 number_get_pattern (AST     *ast,
1904                     GError **error)
1905 {
1906   Number *number = (Number *) ast;
1907
1908   if (strchr (number->token, '.') ||
1909       (!g_str_has_prefix (number->token, "0x") && strchr (number->token, 'e')) ||
1910       strstr (number->token, "inf") ||
1911       strstr (number->token, "nan"))
1912     return g_strdup ("Md");
1913
1914   return g_strdup ("MN");
1915 }
1916
1917 static GVariant *
1918 number_overflow (AST                 *ast,
1919                  const GVariantType  *type,
1920                  GError             **error)
1921 {
1922   ast_set_error (ast, error, NULL,
1923                  G_VARIANT_PARSE_ERROR_NUMBER_OUT_OF_RANGE,
1924                  "number out of range for type '%c'",
1925                  g_variant_type_peek_string (type)[0]);
1926   return NULL;
1927 }
1928
1929 static GVariant *
1930 number_get_value (AST                 *ast,
1931                   const GVariantType  *type,
1932                   GError             **error)
1933 {
1934   Number *number = (Number *) ast;
1935   const gchar *token;
1936   gboolean negative;
1937   gboolean floating;
1938   guint64 abs_val;
1939   gdouble dbl_val;
1940   gchar *end;
1941
1942   token = number->token;
1943
1944   if (g_variant_type_equal (type, G_VARIANT_TYPE_DOUBLE))
1945     {
1946       floating = TRUE;
1947
1948       errno = 0;
1949       dbl_val = g_ascii_strtod (token, &end);
1950       if (dbl_val != 0.0 && errno == ERANGE)
1951         {
1952           ast_set_error (ast, error, NULL,
1953                          G_VARIANT_PARSE_ERROR_NUMBER_TOO_BIG,
1954                          "number too big for any type");
1955           return NULL;
1956         }
1957
1958       /* silence uninitialised warnings... */
1959       negative = FALSE;
1960       abs_val = 0;
1961     }
1962   else
1963     {
1964       floating = FALSE;
1965       negative = token[0] == '-';
1966       if (token[0] == '-')
1967         token++;
1968
1969       errno = 0;
1970       abs_val = g_ascii_strtoull (token, &end, 0);
1971       if (abs_val == G_MAXUINT64 && errno == ERANGE)
1972         {
1973           ast_set_error (ast, error, NULL,
1974                          G_VARIANT_PARSE_ERROR_NUMBER_TOO_BIG,
1975                          "integer too big for any type");
1976           return NULL;
1977         }
1978
1979       if (abs_val == 0)
1980         negative = FALSE;
1981
1982       /* silence uninitialised warning... */
1983       dbl_val = 0.0;
1984     }
1985
1986   if (*end != '\0')
1987     {
1988       SourceRef ref;
1989
1990       ref = ast->source_ref;
1991       ref.start += end - number->token;
1992       ref.end = ref.start + 1;
1993
1994       parser_set_error (error, &ref, NULL,
1995                         G_VARIANT_PARSE_ERROR_INVALID_CHARACTER,
1996                         "invalid character in number");
1997       return NULL;
1998      }
1999
2000   if (floating)
2001     return g_variant_new_double (dbl_val);
2002
2003   switch (*g_variant_type_peek_string (type))
2004     {
2005     case 'y':
2006       if (negative || abs_val > G_MAXUINT8)
2007         return number_overflow (ast, type, error);
2008       return g_variant_new_byte (abs_val);
2009
2010     case 'n':
2011       if (abs_val - negative > G_MAXINT16)
2012         return number_overflow (ast, type, error);
2013       if (negative && abs_val > G_MAXINT16)
2014         return g_variant_new_int16 (G_MININT16);
2015       return g_variant_new_int16 (negative ?
2016                                   -((gint16) abs_val) : ((gint16) abs_val));
2017
2018     case 'q':
2019       if (negative || abs_val > G_MAXUINT16)
2020         return number_overflow (ast, type, error);
2021       return g_variant_new_uint16 (abs_val);
2022
2023     case 'i':
2024       if (abs_val - negative > G_MAXINT32)
2025         return number_overflow (ast, type, error);
2026       if (negative && abs_val > G_MAXINT32)
2027         return g_variant_new_int32 (G_MININT32);
2028       return g_variant_new_int32 (negative ?
2029                                   -((gint32) abs_val) : ((gint32) abs_val));
2030
2031     case 'u':
2032       if (negative || abs_val > G_MAXUINT32)
2033         return number_overflow (ast, type, error);
2034       return g_variant_new_uint32 (abs_val);
2035
2036     case 'x':
2037       if (abs_val - negative > G_MAXINT64)
2038         return number_overflow (ast, type, error);
2039       if (negative && abs_val > G_MAXINT64)
2040         return g_variant_new_int64 (G_MININT64);
2041       return g_variant_new_int64 (negative ?
2042                                   -((gint64) abs_val) : ((gint64) abs_val));
2043
2044     case 't':
2045       if (negative)
2046         return number_overflow (ast, type, error);
2047       return g_variant_new_uint64 (abs_val);
2048
2049     case 'h':
2050       if (abs_val - negative > G_MAXINT32)
2051         return number_overflow (ast, type, error);
2052       if (negative && abs_val > G_MAXINT32)
2053         return g_variant_new_handle (G_MININT32);
2054       return g_variant_new_handle (negative ?
2055                                    -((gint32) abs_val) : ((gint32) abs_val));
2056
2057     default:
2058       return ast_type_error (ast, type, error);
2059     }
2060 }
2061
2062 static void
2063 number_free (AST *ast)
2064 {
2065   Number *number = (Number *) ast;
2066
2067   g_free (number->token);
2068   g_slice_free (Number, number);
2069 }
2070
2071 static AST *
2072 number_parse (TokenStream  *stream,
2073               va_list      *app,
2074               GError      **error)
2075 {
2076   static const ASTClass number_class = {
2077     number_get_pattern,
2078     maybe_wrapper, number_get_value,
2079     number_free
2080   };
2081   Number *number;
2082
2083   number = g_slice_new (Number);
2084   number->ast.class = &number_class;
2085   number->token = token_stream_get (stream);
2086   token_stream_next (stream);
2087
2088   return (AST *) number;
2089 }
2090
2091 typedef struct
2092 {
2093   AST ast;
2094   gboolean value;
2095 } Boolean;
2096
2097 static gchar *
2098 boolean_get_pattern (AST     *ast,
2099                      GError **error)
2100 {
2101   return g_strdup ("Mb");
2102 }
2103
2104 static GVariant *
2105 boolean_get_value (AST                 *ast,
2106                    const GVariantType  *type,
2107                    GError             **error)
2108 {
2109   Boolean *boolean = (Boolean *) ast;
2110
2111   if (!g_variant_type_equal (type, G_VARIANT_TYPE_BOOLEAN))
2112     return ast_type_error (ast, type, error);
2113
2114   return g_variant_new_boolean (boolean->value);
2115 }
2116
2117 static void
2118 boolean_free (AST *ast)
2119 {
2120   Boolean *boolean = (Boolean *) ast;
2121
2122   g_slice_free (Boolean, boolean);
2123 }
2124
2125 static AST *
2126 boolean_new (gboolean value)
2127 {
2128   static const ASTClass boolean_class = {
2129     boolean_get_pattern,
2130     maybe_wrapper, boolean_get_value,
2131     boolean_free
2132   };
2133   Boolean *boolean;
2134
2135   boolean = g_slice_new (Boolean);
2136   boolean->ast.class = &boolean_class;
2137   boolean->value = value;
2138
2139   return (AST *) boolean;
2140 }
2141
2142 typedef struct
2143 {
2144   AST ast;
2145
2146   GVariant *value;
2147 } Positional;
2148
2149 static gchar *
2150 positional_get_pattern (AST     *ast,
2151                         GError **error)
2152 {
2153   Positional *positional = (Positional *) ast;
2154
2155   return g_strdup (g_variant_get_type_string (positional->value));
2156 }
2157
2158 static GVariant *
2159 positional_get_value (AST                 *ast,
2160                       const GVariantType  *type,
2161                       GError             **error)
2162 {
2163   Positional *positional = (Positional *) ast;
2164   GVariant *value;
2165
2166   g_assert (positional->value != NULL);
2167
2168   if G_UNLIKELY (!g_variant_is_of_type (positional->value, type))
2169     return ast_type_error (ast, type, error);
2170
2171   /* NOTE: if _get is called more than once then
2172    * things get messed up with respect to floating refs.
2173    *
2174    * fortunately, this function should only ever get called once.
2175    */
2176   g_assert (positional->value != NULL);
2177   value = positional->value;
2178   positional->value = NULL;
2179
2180   return value;
2181 }
2182
2183 static void
2184 positional_free (AST *ast)
2185 {
2186   Positional *positional = (Positional *) ast;
2187
2188   /* if positional->value is set, just leave it.
2189    * memory management doesn't matter in case of programmer error.
2190    */
2191   g_slice_free (Positional, positional);
2192 }
2193
2194 static AST *
2195 positional_parse (TokenStream  *stream,
2196                   va_list      *app,
2197                   GError      **error)
2198 {
2199   static const ASTClass positional_class = {
2200     positional_get_pattern,
2201     positional_get_value, NULL,
2202     positional_free
2203   };
2204   Positional *positional;
2205   const gchar *endptr;
2206   gchar *token;
2207
2208   token = token_stream_get (stream);
2209   g_assert (token[0] == '%');
2210
2211   positional = g_slice_new (Positional);
2212   positional->ast.class = &positional_class;
2213   positional->value = g_variant_new_va (token + 1, &endptr, app);
2214
2215   if (*endptr || positional->value == NULL)
2216     {
2217       token_stream_set_error (stream, error, TRUE,
2218                               G_VARIANT_PARSE_ERROR_INVALID_FORMAT_STRING,
2219                               "invalid GVariant format string");
2220       /* memory management doesn't matter in case of programmer error. */
2221       return NULL;
2222     }
2223
2224   token_stream_next (stream);
2225   g_free (token);
2226
2227   return (AST *) positional;
2228 }
2229
2230 typedef struct
2231 {
2232   AST ast;
2233
2234   GVariantType *type;
2235   AST *child;
2236 } TypeDecl;
2237
2238 static gchar *
2239 typedecl_get_pattern (AST     *ast,
2240                       GError **error)
2241 {
2242   TypeDecl *decl = (TypeDecl *) ast;
2243
2244   return g_variant_type_dup_string (decl->type);
2245 }
2246
2247 static GVariant *
2248 typedecl_get_value (AST                 *ast,
2249                     const GVariantType  *type,
2250                     GError             **error)
2251 {
2252   TypeDecl *decl = (TypeDecl *) ast;
2253
2254   return ast_get_value (decl->child, type, error);
2255 }
2256
2257 static void
2258 typedecl_free (AST *ast)
2259 {
2260   TypeDecl *decl = (TypeDecl *) ast;
2261
2262   ast_free (decl->child);
2263   g_variant_type_free (decl->type);
2264   g_slice_free (TypeDecl, decl);
2265 }
2266
2267 static AST *
2268 typedecl_parse (TokenStream  *stream,
2269                 guint         max_depth,
2270                 va_list      *app,
2271                 GError      **error)
2272 {
2273   static const ASTClass typedecl_class = {
2274     typedecl_get_pattern,
2275     typedecl_get_value, NULL,
2276     typedecl_free
2277   };
2278   GVariantType *type;
2279   TypeDecl *decl;
2280   AST *child;
2281
2282   if (token_stream_peek (stream, '@'))
2283     {
2284       gchar *token;
2285
2286       token = token_stream_get (stream);
2287
2288       if (!g_variant_type_string_is_valid (token + 1))
2289         {
2290           token_stream_set_error (stream, error, TRUE,
2291                                   G_VARIANT_PARSE_ERROR_INVALID_TYPE_STRING,
2292                                   "invalid type declaration");
2293           g_free (token);
2294
2295           return NULL;
2296         }
2297
2298       if (g_variant_type_string_get_depth_ (token + 1) > max_depth)
2299         {
2300           token_stream_set_error (stream, error, TRUE,
2301                                   G_VARIANT_PARSE_ERROR_RECURSION,
2302                                   "type declaration recurses too deeply");
2303           g_free (token);
2304
2305           return NULL;
2306         }
2307
2308       type = g_variant_type_new (token + 1);
2309
2310       if (!g_variant_type_is_definite (type))
2311         {
2312           token_stream_set_error (stream, error, TRUE,
2313                                   G_VARIANT_PARSE_ERROR_DEFINITE_TYPE_EXPECTED,
2314                                   "type declarations must be definite");
2315           g_variant_type_free (type);
2316           g_free (token);
2317
2318           return NULL;
2319         }
2320
2321       token_stream_next (stream);
2322       g_free (token);
2323     }
2324   else
2325     {
2326       if (token_stream_consume (stream, "boolean"))
2327         type = g_variant_type_copy (G_VARIANT_TYPE_BOOLEAN);
2328
2329       else if (token_stream_consume (stream, "byte"))
2330         type = g_variant_type_copy (G_VARIANT_TYPE_BYTE);
2331
2332       else if (token_stream_consume (stream, "int16"))
2333         type = g_variant_type_copy (G_VARIANT_TYPE_INT16);
2334
2335       else if (token_stream_consume (stream, "uint16"))
2336         type = g_variant_type_copy (G_VARIANT_TYPE_UINT16);
2337
2338       else if (token_stream_consume (stream, "int32"))
2339         type = g_variant_type_copy (G_VARIANT_TYPE_INT32);
2340
2341       else if (token_stream_consume (stream, "handle"))
2342         type = g_variant_type_copy (G_VARIANT_TYPE_HANDLE);
2343
2344       else if (token_stream_consume (stream, "uint32"))
2345         type = g_variant_type_copy (G_VARIANT_TYPE_UINT32);
2346
2347       else if (token_stream_consume (stream, "int64"))
2348         type = g_variant_type_copy (G_VARIANT_TYPE_INT64);
2349
2350       else if (token_stream_consume (stream, "uint64"))
2351         type = g_variant_type_copy (G_VARIANT_TYPE_UINT64);
2352
2353       else if (token_stream_consume (stream, "double"))
2354         type = g_variant_type_copy (G_VARIANT_TYPE_DOUBLE);
2355
2356       else if (token_stream_consume (stream, "string"))
2357         type = g_variant_type_copy (G_VARIANT_TYPE_STRING);
2358
2359       else if (token_stream_consume (stream, "objectpath"))
2360         type = g_variant_type_copy (G_VARIANT_TYPE_OBJECT_PATH);
2361
2362       else if (token_stream_consume (stream, "signature"))
2363         type = g_variant_type_copy (G_VARIANT_TYPE_SIGNATURE);
2364
2365       else
2366         {
2367           token_stream_set_error (stream, error, TRUE,
2368                                   G_VARIANT_PARSE_ERROR_UNKNOWN_KEYWORD,
2369                                   "unknown keyword");
2370           return NULL;
2371         }
2372     }
2373
2374   if ((child = parse (stream, max_depth - 1, app, error)) == NULL)
2375     {
2376       g_variant_type_free (type);
2377       return NULL;
2378     }
2379
2380   decl = g_slice_new (TypeDecl);
2381   decl->ast.class = &typedecl_class;
2382   decl->type = type;
2383   decl->child = child;
2384
2385   return (AST *) decl;
2386 }
2387
2388 static AST *
2389 parse (TokenStream  *stream,
2390        guint         max_depth,
2391        va_list      *app,
2392        GError      **error)
2393 {
2394   SourceRef source_ref;
2395   AST *result;
2396
2397   if (max_depth == 0)
2398     {
2399       token_stream_set_error (stream, error, FALSE,
2400                               G_VARIANT_PARSE_ERROR_RECURSION,
2401                               "variant nested too deeply");
2402       return NULL;
2403     }
2404
2405   token_stream_prepare (stream);
2406   token_stream_start_ref (stream, &source_ref);
2407
2408   if (token_stream_peek (stream, '['))
2409     result = array_parse (stream, max_depth, app, error);
2410
2411   else if (token_stream_peek (stream, '('))
2412     result = tuple_parse (stream, max_depth, app, error);
2413
2414   else if (token_stream_peek (stream, '<'))
2415     result = variant_parse (stream, max_depth, app, error);
2416
2417   else if (token_stream_peek (stream, '{'))
2418     result = dictionary_parse (stream, max_depth, app, error);
2419
2420   else if (app && token_stream_peek (stream, '%'))
2421     result = positional_parse (stream, app, error);
2422
2423   else if (token_stream_consume (stream, "true"))
2424     result = boolean_new (TRUE);
2425
2426   else if (token_stream_consume (stream, "false"))
2427     result = boolean_new (FALSE);
2428
2429   else if (token_stream_is_numeric (stream) ||
2430            token_stream_peek_string (stream, "inf") ||
2431            token_stream_peek_string (stream, "nan"))
2432     result = number_parse (stream, app, error);
2433
2434   else if (token_stream_peek (stream, 'n') ||
2435            token_stream_peek (stream, 'j'))
2436     result = maybe_parse (stream, max_depth, app, error);
2437
2438   else if (token_stream_peek (stream, '@') ||
2439            token_stream_is_keyword (stream))
2440     result = typedecl_parse (stream, max_depth, app, error);
2441
2442   else if (token_stream_peek (stream, '\'') ||
2443            token_stream_peek (stream, '"'))
2444     result = string_parse (stream, app, error);
2445
2446   else if (token_stream_peek2 (stream, 'b', '\'') ||
2447            token_stream_peek2 (stream, 'b', '"'))
2448     result = bytestring_parse (stream, app, error);
2449
2450   else
2451     {
2452       token_stream_set_error (stream, error, FALSE,
2453                               G_VARIANT_PARSE_ERROR_VALUE_EXPECTED,
2454                               "expected value");
2455       return NULL;
2456     }
2457
2458   if (result != NULL)
2459     {
2460       token_stream_end_ref (stream, &source_ref);
2461       result->source_ref = source_ref;
2462     }
2463
2464   return result;
2465 }
2466
2467 /**
2468  * g_variant_parse:
2469  * @type: (nullable): a #GVariantType, or %NULL
2470  * @text: a string containing a GVariant in text form
2471  * @limit: (nullable): a pointer to the end of @text, or %NULL
2472  * @endptr: (nullable): a location to store the end pointer, or %NULL
2473  * @error: (nullable): a pointer to a %NULL #GError pointer, or %NULL
2474  *
2475  * Parses a #GVariant from a text representation.
2476  *
2477  * A single #GVariant is parsed from the content of @text.
2478  *
2479  * The format is described [here][gvariant-text].
2480  *
2481  * The memory at @limit will never be accessed and the parser behaves as
2482  * if the character at @limit is the nul terminator.  This has the
2483  * effect of bounding @text.
2484  *
2485  * If @endptr is non-%NULL then @text is permitted to contain data
2486  * following the value that this function parses and @endptr will be
2487  * updated to point to the first character past the end of the text
2488  * parsed by this function.  If @endptr is %NULL and there is extra data
2489  * then an error is returned.
2490  *
2491  * If @type is non-%NULL then the value will be parsed to have that
2492  * type.  This may result in additional parse errors (in the case that
2493  * the parsed value doesn't fit the type) but may also result in fewer
2494  * errors (in the case that the type would have been ambiguous, such as
2495  * with empty arrays).
2496  *
2497  * In the event that the parsing is successful, the resulting #GVariant
2498  * is returned. It is never floating, and must be freed with
2499  * g_variant_unref().
2500  *
2501  * In case of any error, %NULL will be returned.  If @error is non-%NULL
2502  * then it will be set to reflect the error that occurred.
2503  *
2504  * Officially, the language understood by the parser is "any string
2505  * produced by g_variant_print()".
2506  *
2507  * There may be implementation specific restrictions on deeply nested values,
2508  * which would result in a %G_VARIANT_PARSE_ERROR_RECURSION error. #GVariant is
2509  * guaranteed to handle nesting up to at least 64 levels.
2510  *
2511  * Returns: a non-floating reference to a #GVariant, or %NULL
2512  **/
2513 GVariant *
2514 g_variant_parse (const GVariantType  *type,
2515                  const gchar         *text,
2516                  const gchar         *limit,
2517                  const gchar        **endptr,
2518                  GError             **error)
2519 {
2520   TokenStream stream = { 0, };
2521   GVariant *result = NULL;
2522   AST *ast;
2523
2524   g_return_val_if_fail (text != NULL, NULL);
2525   g_return_val_if_fail (text == limit || text != NULL, NULL);
2526
2527   stream.start = text;
2528   stream.stream = text;
2529   stream.end = limit;
2530
2531   if ((ast = parse (&stream, G_VARIANT_MAX_RECURSION_DEPTH, NULL, error)))
2532     {
2533       if (type == NULL)
2534         result = ast_resolve (ast, error);
2535       else
2536         result = ast_get_value (ast, type, error);
2537
2538       if (result != NULL)
2539         {
2540           g_variant_ref_sink (result);
2541
2542           if (endptr == NULL)
2543             {
2544               while (stream.stream != limit &&
2545                      g_ascii_isspace (*stream.stream))
2546                 stream.stream++;
2547
2548               if (stream.stream != limit && *stream.stream != '\0')
2549                 {
2550                   SourceRef ref = { stream.stream - text,
2551                                     stream.stream - text };
2552
2553                   parser_set_error (error, &ref, NULL,
2554                                     G_VARIANT_PARSE_ERROR_INPUT_NOT_AT_END,
2555                                     "expected end of input");
2556                   g_variant_unref (result);
2557
2558                   result = NULL;
2559                 }
2560             }
2561           else
2562             *endptr = stream.stream;
2563         }
2564
2565       ast_free (ast);
2566     }
2567
2568   return result;
2569 }
2570
2571 /**
2572  * g_variant_new_parsed_va:
2573  * @format: a text format #GVariant
2574  * @app: a pointer to a #va_list
2575  *
2576  * Parses @format and returns the result.
2577  *
2578  * This is the version of g_variant_new_parsed() intended to be used
2579  * from libraries.
2580  *
2581  * The return value will be floating if it was a newly created GVariant
2582  * instance.  In the case that @format simply specified the collection
2583  * of a #GVariant pointer (eg: @format was "%*") then the collected
2584  * #GVariant pointer will be returned unmodified, without adding any
2585  * additional references.
2586  *
2587  * Note that the arguments in @app must be of the correct width for their types
2588  * specified in @format when collected into the #va_list. See
2589  * the [GVariant varargs documentation][gvariant-varargs].
2590  *
2591  * In order to behave correctly in all cases it is necessary for the
2592  * calling function to g_variant_ref_sink() the return result before
2593  * returning control to the user that originally provided the pointer.
2594  * At this point, the caller will have their own full reference to the
2595  * result.  This can also be done by adding the result to a container,
2596  * or by passing it to another g_variant_new() call.
2597  *
2598  * Returns: a new, usually floating, #GVariant
2599  **/
2600 GVariant *
2601 g_variant_new_parsed_va (const gchar *format,
2602                          va_list     *app)
2603 {
2604   TokenStream stream = { 0, };
2605   GVariant *result = NULL;
2606   GError *error = NULL;
2607   AST *ast;
2608
2609   g_return_val_if_fail (format != NULL, NULL);
2610   g_return_val_if_fail (app != NULL, NULL);
2611
2612   stream.start = format;
2613   stream.stream = format;
2614   stream.end = NULL;
2615
2616   if ((ast = parse (&stream, G_VARIANT_MAX_RECURSION_DEPTH, app, &error)))
2617     {
2618       result = ast_resolve (ast, &error);
2619       ast_free (ast);
2620     }
2621
2622   if (error != NULL)
2623     g_error ("g_variant_new_parsed: %s", error->message);
2624
2625   if (*stream.stream)
2626     g_error ("g_variant_new_parsed: trailing text after value");
2627
2628   g_clear_error (&error);
2629
2630   return result;
2631 }
2632
2633 /**
2634  * g_variant_new_parsed:
2635  * @format: a text format #GVariant
2636  * @...: arguments as per @format
2637  *
2638  * Parses @format and returns the result.
2639  *
2640  * @format must be a text format #GVariant with one extension: at any
2641  * point that a value may appear in the text, a '%' character followed
2642  * by a GVariant format string (as per g_variant_new()) may appear.  In
2643  * that case, the same arguments are collected from the argument list as
2644  * g_variant_new() would have collected.
2645  *
2646  * Note that the arguments must be of the correct width for their types
2647  * specified in @format. This can be achieved by casting them. See
2648  * the [GVariant varargs documentation][gvariant-varargs].
2649  *
2650  * Consider this simple example:
2651  * |[<!-- language="C" -->
2652  *  g_variant_new_parsed ("[('one', 1), ('two', %i), (%s, 3)]", 2, "three");
2653  * ]|
2654  *
2655  * In the example, the variable argument parameters are collected and
2656  * filled in as if they were part of the original string to produce the
2657  * result of
2658  * |[<!-- language="C" -->
2659  * [('one', 1), ('two', 2), ('three', 3)]
2660  * ]|
2661  *
2662  * This function is intended only to be used with @format as a string
2663  * literal.  Any parse error is fatal to the calling process.  If you
2664  * want to parse data from untrusted sources, use g_variant_parse().
2665  *
2666  * You may not use this function to return, unmodified, a single
2667  * #GVariant pointer from the argument list.  ie: @format may not solely
2668  * be anything along the lines of "%*", "%?", "\%r", or anything starting
2669  * with "%@".
2670  *
2671  * Returns: a new floating #GVariant instance
2672  **/
2673 GVariant *
2674 g_variant_new_parsed (const gchar *format,
2675                       ...)
2676 {
2677   GVariant *result;
2678   va_list ap;
2679
2680   va_start (ap, format);
2681   result = g_variant_new_parsed_va (format, &ap);
2682   va_end (ap);
2683
2684   return result;
2685 }
2686
2687 /**
2688  * g_variant_builder_add_parsed:
2689  * @builder: a #GVariantBuilder
2690  * @format: a text format #GVariant
2691  * @...: arguments as per @format
2692  *
2693  * Adds to a #GVariantBuilder.
2694  *
2695  * This call is a convenience wrapper that is exactly equivalent to
2696  * calling g_variant_new_parsed() followed by
2697  * g_variant_builder_add_value().
2698  *
2699  * Note that the arguments must be of the correct width for their types
2700  * specified in @format_string. This can be achieved by casting them. See
2701  * the [GVariant varargs documentation][gvariant-varargs].
2702  *
2703  * This function might be used as follows:
2704  *
2705  * |[<!-- language="C" -->
2706  * GVariant *
2707  * make_pointless_dictionary (void)
2708  * {
2709  *   GVariantBuilder builder;
2710  *   int i;
2711  *
2712  *   g_variant_builder_init (&builder, G_VARIANT_TYPE_ARRAY);
2713  *   g_variant_builder_add_parsed (&builder, "{'width', <%i>}", 600);
2714  *   g_variant_builder_add_parsed (&builder, "{'title', <%s>}", "foo");
2715  *   g_variant_builder_add_parsed (&builder, "{'transparency', <0.5>}");
2716  *   return g_variant_builder_end (&builder);
2717  * }
2718  * ]|
2719  *
2720  * Since: 2.26
2721  */
2722 void
2723 g_variant_builder_add_parsed (GVariantBuilder *builder,
2724                               const gchar     *format,
2725                               ...)
2726 {
2727   va_list ap;
2728
2729   va_start (ap, format);
2730   g_variant_builder_add_value (builder, g_variant_new_parsed_va (format, &ap));
2731   va_end (ap);
2732 }
2733
2734 static gboolean
2735 parse_num (const gchar *num,
2736            const gchar *limit,
2737            guint       *result)
2738 {
2739   gchar *endptr;
2740   gint64 bignum;
2741
2742   bignum = g_ascii_strtoll (num, &endptr, 10);
2743
2744   if (endptr != limit)
2745     return FALSE;
2746
2747   if (bignum < 0 || bignum > G_MAXINT)
2748     return FALSE;
2749
2750   *result = (guint) bignum;
2751
2752   return TRUE;
2753 }
2754
2755 static void
2756 add_last_line (GString     *err,
2757                const gchar *str)
2758 {
2759   const gchar *last_nl;
2760   gchar *chomped;
2761   gint i;
2762
2763   /* This is an error at the end of input.  If we have a file
2764    * with newlines, that's probably the empty string after the
2765    * last newline, which is not the most useful thing to show.
2766    *
2767    * Instead, show the last line of non-whitespace that we have
2768    * and put the pointer at the end of it.
2769    */
2770   chomped = g_strchomp (g_strdup (str));
2771   last_nl = strrchr (chomped, '\n');
2772   if (last_nl == NULL)
2773     last_nl = chomped;
2774   else
2775     last_nl++;
2776
2777   /* Print the last line like so:
2778    *
2779    *   [1, 2, 3,
2780    *            ^
2781    */
2782   g_string_append (err, "  ");
2783   if (last_nl[0])
2784     g_string_append (err, last_nl);
2785   else
2786     g_string_append (err, "(empty input)");
2787   g_string_append (err, "\n  ");
2788   for (i = 0; last_nl[i]; i++)
2789     g_string_append_c (err, ' ');
2790   g_string_append (err, "^\n");
2791   g_free (chomped);
2792 }
2793
2794 static void
2795 add_lines_from_range (GString     *err,
2796                       const gchar *str,
2797                       const gchar *start1,
2798                       const gchar *end1,
2799                       const gchar *start2,
2800                       const gchar *end2)
2801 {
2802   while (str < end1 || str < end2)
2803     {
2804       const gchar *nl;
2805
2806       nl = str + strcspn (str, "\n");
2807
2808       if ((start1 < nl && str < end1) || (start2 < nl && str < end2))
2809         {
2810           const gchar *s;
2811
2812           /* We're going to print this line */
2813           g_string_append (err, "  ");
2814           g_string_append_len (err, str, nl - str);
2815           g_string_append (err, "\n  ");
2816
2817           /* And add underlines... */
2818           for (s = str; s < nl; s++)
2819             {
2820               if ((start1 <= s && s < end1) || (start2 <= s && s < end2))
2821                 g_string_append_c (err, '^');
2822               else
2823                 g_string_append_c (err, ' ');
2824             }
2825           g_string_append_c (err, '\n');
2826         }
2827
2828       if (!*nl)
2829         break;
2830
2831       str = nl + 1;
2832     }
2833 }
2834
2835 /**
2836  * g_variant_parse_error_print_context:
2837  * @error: a #GError from the #GVariantParseError domain
2838  * @source_str: the string that was given to the parser
2839  *
2840  * Pretty-prints a message showing the context of a #GVariant parse
2841  * error within the string for which parsing was attempted.
2842  *
2843  * The resulting string is suitable for output to the console or other
2844  * monospace media where newlines are treated in the usual way.
2845  *
2846  * The message will typically look something like one of the following:
2847  *
2848  * |[
2849  * unterminated string constant:
2850  *   (1, 2, 3, 'abc
2851  *             ^^^^
2852  * ]|
2853  *
2854  * or
2855  *
2856  * |[
2857  * unable to find a common type:
2858  *   [1, 2, 3, 'str']
2859  *    ^        ^^^^^
2860  * ]|
2861  *
2862  * The format of the message may change in a future version.
2863  *
2864  * @error must have come from a failed attempt to g_variant_parse() and
2865  * @source_str must be exactly the same string that caused the error.
2866  * If @source_str was not nul-terminated when you passed it to
2867  * g_variant_parse() then you must add nul termination before using this
2868  * function.
2869  *
2870  * Returns: (transfer full): the printed message
2871  *
2872  * Since: 2.40
2873  **/
2874 gchar *
2875 g_variant_parse_error_print_context (GError      *error,
2876                                      const gchar *source_str)
2877 {
2878   const gchar *colon, *dash, *comma;
2879   gboolean success = FALSE;
2880   GString *err;
2881
2882   g_return_val_if_fail (error->domain == G_VARIANT_PARSE_ERROR, FALSE);
2883
2884   /* We can only have a limited number of possible types of ranges
2885    * emitted from the parser:
2886    *
2887    *  - a:          -- usually errors from the tokeniser (eof, invalid char, etc.)
2888    *  - a-b:        -- usually errors from handling one single token
2889    *  - a-b,c-d:    -- errors involving two tokens (ie: type inferencing)
2890    *
2891    * We never see, for example "a,c".
2892    */
2893
2894   colon = strchr (error->message, ':');
2895   dash = strchr (error->message, '-');
2896   comma = strchr (error->message, ',');
2897
2898   if (!colon)
2899     return NULL;
2900
2901   err = g_string_new (colon + 1);
2902   g_string_append (err, ":\n");
2903
2904   if (dash == NULL || colon < dash)
2905     {
2906       guint point;
2907
2908       /* we have a single point */
2909       if (!parse_num (error->message, colon, &point))
2910         goto out;
2911
2912       if (point >= strlen (source_str))
2913         /* the error is at the end of the input */
2914         add_last_line (err, source_str);
2915       else
2916         /* otherwise just treat it as an error at a thin range */
2917         add_lines_from_range (err, source_str, source_str + point, source_str + point + 1, NULL, NULL);
2918     }
2919   else
2920     {
2921       /* We have one or two ranges... */
2922       if (comma && comma < colon)
2923         {
2924           guint start1, end1, start2, end2;
2925           const gchar *dash2;
2926
2927           /* Two ranges */
2928           dash2 = strchr (comma, '-');
2929
2930           if (!parse_num (error->message, dash, &start1) || !parse_num (dash + 1, comma, &end1) ||
2931               !parse_num (comma + 1, dash2, &start2) || !parse_num (dash2 + 1, colon, &end2))
2932             goto out;
2933
2934           add_lines_from_range (err, source_str,
2935                                 source_str + start1, source_str + end1,
2936                                 source_str + start2, source_str + end2);
2937         }
2938       else
2939         {
2940           guint start, end;
2941
2942           /* One range */
2943           if (!parse_num (error->message, dash, &start) || !parse_num (dash + 1, colon, &end))
2944             goto out;
2945
2946           add_lines_from_range (err, source_str, source_str + start, source_str + end, NULL, NULL);
2947         }
2948     }
2949
2950   success = TRUE;
2951
2952 out:
2953   return g_string_free (err, !success);
2954 }