glib/gvariant-parser.c

   1 /*
   2  * Copyright © 2009, 2010 Codethink Limited
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the licence, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  *
  19  * Author: Ryan Lortie <desrt@desrt.ca>
  20  */
  21
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include <errno.h>
  25 #include <glib.h>
  26
  27
  28 /*
  29  * two-pass algorithm
  30  * designed by ryan lortie and william hua
  31  * designed in itb-229 and at ghazi's, 2009.
  32  */
  33
  34 /**
  35  * G_VARIANT_PARSE_ERROR:
  36  *
  37  * Error domain for GVariant text format parsing.  Specific error codes
  38  * are not currently defined for this domain.  See #GError for
  39  * information on error domains.
  40  **/
  41 /**
  42  * GVariantParseError:
  43  * @G_VARIANT_PARSE_ERROR_FAILED: generic error
  44  *
  45  * Error codes returned by parsing text-format GVariants.  Currently the
  46  * parser makes no distinction between different types of error.
  47  **/
  48 GQuark
  49 g_variant_parser_get_error_quark (void)
  50 {
  51   static GQuark the_quark;
  52
  53   if (the_quark == 0)
  54     the_quark = g_quark_from_static_string ("g-variant-parse-error-quark");
  55
  56   return the_quark;
  57 }
  58
  59 typedef struct
  60 {
  61   gint start, end;
  62 } SourceRef;
  63
  64 static void
  65 parser_set_error_va (GError      **error,
  66                      SourceRef    *location,
  67                      SourceRef    *other,
  68                      const gchar  *format,
  69                      va_list       ap)
  70 {
  71   GString *msg = g_string_new (NULL);
  72
  73   if (location->start == location->end)
  74     g_string_append_printf (msg, "%d", location->start);
  75   else
  76     g_string_append_printf (msg, "%d-%d", location->start, location->end);
  77
  78   if (other != NULL)
  79     {
  80       g_assert (other->start != other->end);
  81       g_string_append_printf (msg, ",%d-%d", other->start, other->end);
  82     }
  83   g_string_append_c (msg, ':');
  84
  85   g_string_append_vprintf (msg, format, ap);
  86   g_set_error_literal (error, G_VARIANT_PARSE_ERROR, 0, msg->str);
  87   g_string_free (msg, TRUE);
  88 }
  89
  90 static void
  91 parser_set_error (GError      **error,
  92                   SourceRef    *location,
  93                   SourceRef    *other,
  94                   const gchar  *format,
  95                   ...)
  96 {
  97   va_list ap;
  98
  99   va_start (ap, format);
 100   parser_set_error_va (error, location, other, format, ap);
 101   va_end (ap);
 102 }
 103
 104 typedef struct
 105 {
 106   const gchar *start;
 107   const gchar *stream;
 108   const gchar *end;
 109
 110   const gchar *this;
 111 } TokenStream;
 112
 113
 114 static void
 115 token_stream_set_error (TokenStream  *stream,
 116                         GError      **error,
 117                         gboolean      this_token,
 118                         const gchar  *format,
 119                         ...)
 120 {
 121   SourceRef ref;
 122   va_list ap;
 123
 124   ref.start = stream->this - stream->start;
 125
 126   if (this_token)
 127     ref.end = stream->stream - stream->start;
 128   else
 129     ref.end = ref.start;
 130
 131   va_start (ap, format);
 132   parser_set_error_va (error, &ref, NULL, format, ap);
 133   va_end (ap);
 134 }
 135
 136 static void
 137 token_stream_prepare (TokenStream *stream)
 138 {
 139   gint brackets = 0;
 140   const gchar *end;
 141
 142   if (stream->this != NULL)
 143     return;
 144
 145   while (stream->stream != stream->end && g_ascii_isspace (*stream->stream))
 146     stream->stream++;
 147
 148   if (stream->stream == stream->end || *stream->stream == '\0')
 149     {
 150       stream->this = stream->stream;
 151       return;
 152     }
 153
 154   switch (stream->stream[0])
 155     {
 156     case '-': case '+': case '.': case '0': case '1': case '2':
 157     case '3': case '4': case '5': case '6': case '7': case '8':
 158     case '9':
 159       for (end = stream->stream; end != stream->end; end++)
 160         if (!g_ascii_isalnum (*end) &&
 161             *end != '-' && *end != '+' && *end != '.')
 162           break;
 163       break;
 164
 165     case 'b':
 166       if (stream->stream[1] == '\'' || stream->stream[1] == '"')
 167         {
 168           for (end = stream->stream + 2; end != stream->end; end++)
 169             if (*end == stream->stream[1] || *end == '\0' ||
 170                 (*end == '\\' && (++end == stream->end || *end == '\0')))
 171               break;
 172
 173           if (end != stream->end && *end)
 174             end++;
 175           break;
 176         }
 177
 178       else    /* ↓↓↓ */;
 179
 180     case 'a': /* 'b' */ case 'c': case 'd': case 'e': case 'f':
 181     case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':
 182     case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':
 183     case 's': case 't': case 'u': case 'v': case 'w': case 'x':
 184     case 'y': case 'z':
 185       for (end = stream->stream; end != stream->end; end++)
 186         if (!g_ascii_isalnum (*end))
 187           break;
 188       break;
 189
 190     case '\'': case '"':
 191       for (end = stream->stream + 1; end != stream->end; end++)
 192         if (*end == stream->stream[0] || *end == '\0' ||
 193             (*end == '\\' && (++end == stream->end || *end == '\0')))
 194           break;
 195
 196       if (end != stream->end && *end)
 197         end++;
 198       break;
 199
 200     case '@': case '%':
 201       /* stop at the first space, comma, colon or unmatched bracket.
 202        * deals nicely with cases like (%i, %i) or {%i: %i}.
 203        */
 204       for (end = stream->stream + 1;
 205            end != stream->end && *end != ',' &&
 206            *end != ':' && *end != '>' && !g_ascii_isspace (*end);
 207            end++)
 208
 209         if (*end == '(' || *end == '{')
 210           brackets++;
 211
 212         else if ((*end == ')' || *end == '}') && !brackets--)
 213           break;
 214
 215       break;
 216
 217     default:
 218       end = stream->stream + 1;
 219       break;
 220     }
 221
 222   stream->this = stream->stream;
 223   stream->stream = end;
 224 }
 225
 226 static void
 227 token_stream_next (TokenStream *stream)
 228 {
 229   stream->this = NULL;
 230 }
 231
 232 static gboolean
 233 token_stream_peek (TokenStream *stream,
 234                    gchar        first_char)
 235 {
 236   token_stream_prepare (stream);
 237
 238   return stream->this[0] == first_char;
 239 }
 240
 241 static gboolean
 242 token_stream_peek2 (TokenStream *stream,
 243                     gchar        first_char,
 244                     gchar        second_char)
 245 {
 246   token_stream_prepare (stream);
 247
 248   return stream->this[0] == first_char &&
 249          stream->this[1] == second_char;
 250 }
 251
 252 static gboolean
 253 token_stream_is_keyword (TokenStream *stream)
 254 {
 255   token_stream_prepare (stream);
 256
 257   return g_ascii_isalpha (stream->this[0]) &&
 258          g_ascii_isalpha (stream->this[1]);
 259 }
 260
 261 static gboolean
 262 token_stream_is_numeric (TokenStream *stream)
 263 {
 264   token_stream_prepare (stream);
 265
 266   return (g_ascii_isdigit (stream->this[0]) ||
 267           stream->this[0] == '-' ||
 268           stream->this[0] == '+' ||
 269           stream->this[0] == '.');
 270 }
 271
 272 static gboolean
 273 token_stream_consume (TokenStream *stream,
 274                       const gchar *token)
 275 {
 276   gint length = strlen (token);
 277
 278   token_stream_prepare (stream);
 279
 280   if (stream->stream - stream->this == length &&
 281       memcmp (stream->this, token, length) == 0)
 282     {
 283       token_stream_next (stream);
 284       return TRUE;
 285     }
 286
 287   return FALSE;
 288 }
 289
 290 static gboolean
 291 token_stream_require (TokenStream  *stream,
 292                       const gchar  *token,
 293                       const gchar  *purpose,
 294                       GError      **error)
 295 {
 296
 297   if (!token_stream_consume (stream, token))
 298     {
 299       token_stream_set_error (stream, error, FALSE,
 300                               "expected `%s'%s", token, purpose);
 301       return FALSE;
 302     }
 303
 304   return TRUE;
 305 }
 306
 307 static void
 308 token_stream_assert (TokenStream *stream,
 309                      const gchar *token)
 310 {
 311   gboolean correct_token;
 312
 313   correct_token = token_stream_consume (stream, token);
 314   g_assert (correct_token);
 315 }
 316
 317 static gchar *
 318 token_stream_get (TokenStream *stream)
 319 {
 320   gchar *result;
 321
 322   token_stream_prepare (stream);
 323
 324   result = g_strndup (stream->this, stream->stream - stream->this);
 325
 326   return result;
 327 }
 328
 329 static void
 330 token_stream_start_ref (TokenStream *stream,
 331                         SourceRef   *ref)
 332 {
 333   token_stream_prepare (stream);
 334   ref->start = stream->this - stream->start;
 335 }
 336
 337 static void
 338 token_stream_end_ref (TokenStream *stream,
 339                       SourceRef   *ref)
 340 {
 341   ref->end = stream->stream - stream->start;
 342 }
 343
 344 void
 345 pattern_copy (gchar       **out,
 346               const gchar **in)
 347 {
 348   gint brackets = 0;
 349
 350   while (**in == 'a' || **in == 'm' || **in == 'M')
 351     *(*out)++ = *(*in)++;
 352
 353   do
 354     {
 355       if (**in == '(' || **in == '{')
 356         brackets++;
 357
 358       else if (**in == ')' || **in == '}')
 359         brackets--;
 360
 361       *(*out)++ = *(*in)++;
 362     }
 363   while (brackets);
 364 }
 365
 366 static gchar *
 367 pattern_coalesce (const gchar *left,
 368                   const gchar *right)
 369 {
 370   gchar *result;
 371   gchar *out;
 372
 373   /* the length of the output is loosely bound by the sum of the input
 374    * lengths, not simply the greater of the two lengths.
 375    *
 376    *   (*(iii)) + ((iii)*) ((iii)(iii))
 377    *
 378    *      8     +    8    =  12
 379    */
 380   out = result = g_malloc (strlen (left) + strlen (right));
 381
 382   while (*left && *right)
 383     {
 384       if (*left == *right)
 385         {
 386           *out++ = *left++;
 387           right++;
 388         }
 389
 390       else
 391         {
 392           const gchar **one = &left, **the_other = &right;
 393
 394          again:
 395           if (**one == '*' && **the_other != ')')
 396             {
 397               pattern_copy (&out, the_other);
 398               (*one)++;
 399             }
 400
 401           else if (**one == 'M' && **the_other == 'm')
 402             {
 403               *out++ = *(*the_other)++;
 404             }
 405
 406           else if (**one == 'M' && **the_other != 'm')
 407             {
 408               (*one)++;
 409             }
 410
 411           else if (**one == 'N' && strchr ("ynqiuxthd", **the_other))
 412             {
 413               *out++ = *(*the_other)++;
 414               (*one)++;
 415             }
 416
 417           else if (**one == 'S' && strchr ("sog", **the_other))
 418             {
 419               *out++ = *(*the_other)++;
 420               (*one)++;
 421             }
 422
 423           else if (one == &left)
 424             {
 425               one = &right, the_other = &left;
 426               goto again;
 427             }
 428
 429           else
 430             break;
 431         }
 432     }
 433
 434   if (*left || *right)
 435     {
 436       g_free (result);
 437       result = NULL;
 438     }
 439   else
 440     *out++ = '\0';
 441
 442   return result;
 443 }
 444
 445 typedef struct _AST AST;
 446 typedef gchar *    (*get_pattern_func)    (AST                 *ast,
 447                                            GError             **error);
 448 typedef GVariant * (*get_value_func)      (AST                 *ast,
 449                                            const GVariantType  *type,
 450                                            GError             **error);
 451 typedef GVariant * (*get_base_value_func) (AST                 *ast,
 452                                            const GVariantType  *type,
 453                                            GError             **error);
 454 typedef void       (*free_func)           (AST                 *ast);
 455
 456 typedef struct
 457 {
 458   gchar *    (* get_pattern)    (AST                 *ast,
 459                                  GError             **error);
 460   GVariant * (* get_value)      (AST                 *ast,
 461                                  const GVariantType  *type,
 462                                  GError             **error);
 463   GVariant * (* get_base_value) (AST                 *ast,
 464                                  const GVariantType  *type,
 465                                  GError             **error);
 466   void       (* free)           (AST                 *ast);
 467 } ASTClass;
 468
 469 struct _AST
 470 {
 471   const ASTClass *class;
 472   SourceRef source_ref;
 473 };
 474
 475 static gchar *
 476 ast_get_pattern (AST     *ast,
 477                  GError **error)
 478 {
 479   return ast->class->get_pattern (ast, error);
 480 }
 481
 482 static GVariant *
 483 ast_get_value (AST                 *ast,
 484                const GVariantType  *type,
 485                GError             **error)
 486 {
 487   return ast->class->get_value (ast, type, error);
 488 }
 489
 490 static void
 491 ast_free (AST *ast)
 492 {
 493   ast->class->free (ast);
 494 }
 495
 496 static void
 497 ast_set_error (AST          *ast,
 498                GError      **error,
 499                AST          *other_ast,
 500                const gchar  *format,
 501                ...)
 502 {
 503   va_list ap;
 504
 505   va_start (ap, format);
 506   parser_set_error_va (error, &ast->source_ref,
 507                        other_ast ? & other_ast->source_ref : NULL,
 508                        format, ap);
 509   va_end (ap);
 510 }
 511
 512 static GVariant *
 513 ast_type_error (AST                 *ast,
 514                 const GVariantType  *type,
 515                 GError             **error)
 516 {
 517   gchar *typestr;
 518
 519   typestr = g_variant_type_dup_string (type);
 520   ast_set_error (ast, error, NULL,
 521                  "can not parse as value of type `%s'",
 522                  typestr);
 523   g_free (typestr);
 524
 525   return NULL;
 526 }
 527
 528 static GVariant *
 529 ast_resolve (AST     *ast,
 530              GError **error)
 531 {
 532   GVariant *value;
 533   gchar *pattern;
 534   gint i, j = 0;
 535
 536   pattern = ast_get_pattern (ast, error);
 537
 538   if (pattern == NULL)
 539     return NULL;
 540
 541   /* choose reasonable defaults
 542    *
 543    *   1) favour non-maybe values where possible
 544    *   2) default type for strings is 's'
 545    *   3) default type for integers is 'i'
 546    */
 547   for (i = 0; pattern[i]; i++)
 548     switch (pattern[i])
 549       {
 550       case '*':
 551         ast_set_error (ast, error, NULL, "unable to infer type");
 552         g_free (pattern);
 553         return NULL;
 554
 555       case 'M':
 556         break;
 557
 558       case 'S':
 559         pattern[j++] = 's';
 560         break;
 561
 562       case 'N':
 563         pattern[j++] = 'i';
 564         break;
 565
 566       default:
 567         pattern[j++] = pattern[i];
 568         break;
 569       }
 570   pattern[j++] = '\0';
 571
 572   value = ast_get_value (ast, G_VARIANT_TYPE (pattern), error);
 573   g_free (pattern);
 574
 575   return value;
 576 }
 577
 578
 579 static AST *parse (TokenStream  *stream,
 580                    va_list      *app,
 581                    GError      **error);
 582
 583 static void
 584 ast_array_append (AST  ***array,
 585                   gint   *n_items,
 586                   AST    *ast)
 587 {
 588   if ((*n_items & (*n_items - 1)) == 0)
 589     *array = g_renew (AST *, *array, *n_items ? 2 ** n_items : 1);
 590
 591   (*array)[(*n_items)++] = ast;
 592 }
 593
 594 static void
 595 ast_array_free (AST  **array,
 596                 gint   n_items)
 597 {
 598   gint i;
 599
 600   for (i = 0; i < n_items; i++)
 601     ast_free (array[i]);
 602   g_free (array);
 603 }
 604
 605 static gchar *
 606 ast_array_get_pattern (AST    **array,
 607                        gint     n_items,
 608                        GError **error)
 609 {
 610   gchar *pattern;
 611   gint i;
 612
 613   pattern = ast_get_pattern (array[0], error);
 614
 615   if (pattern == NULL)
 616     return NULL;
 617
 618   for (i = 1; i < n_items; i++)
 619     {
 620       gchar *tmp, *merged;
 621
 622       tmp = ast_get_pattern (array[i], error);
 623
 624       if (tmp == NULL)
 625         {
 626           g_free (pattern);
 627           return NULL;
 628         }
 629
 630       merged = pattern_coalesce (pattern, tmp);
 631       g_free (pattern);
 632       pattern = merged;
 633
 634       if (merged == NULL)
 635         /* set coalescence implies pairwise coalescence (i think).
 636          * we should therefore be able to trace the failure to a single
 637          * pair of values.
 638          */
 639         {
 640           int j = 0;
 641
 642           while (TRUE)
 643             {
 644               gchar *tmp2;
 645               gchar *m;
 646
 647               /* if 'j' reaches 'i' then we failed to find the pair */
 648               g_assert (j < i);
 649
 650               tmp2 = ast_get_pattern (array[j], NULL);
 651               g_assert (tmp2 != NULL);
 652
 653               m = pattern_coalesce (tmp, tmp2);
 654               g_free (tmp2);
 655               g_free (m);
 656
 657               if (m == NULL)
 658                 {
 659                   /* we found a conflict between 'i' and 'j'.
 660                    *
 661                    * report the error.  note: 'j' is first.
 662                    */
 663                   ast_set_error (array[j], error, array[i],
 664                                  "unable to find a common type");
 665                   g_free (tmp);
 666                   return NULL;
 667                 }
 668
 669               j++;
 670             }
 671         }
 672     }
 673
 674   return pattern;
 675 }
 676
 677 typedef struct
 678 {
 679   AST ast;
 680
 681   AST *child;
 682 } Maybe;
 683
 684 static gchar *
 685 maybe_get_pattern (AST     *ast,
 686                    GError **error)
 687 {
 688   Maybe *maybe = (Maybe *) ast;
 689
 690   if (maybe->child != NULL)
 691     {
 692       gchar *child_pattern;
 693       gchar *pattern;
 694
 695       child_pattern = ast_get_pattern (maybe->child, error);
 696
 697       if (child_pattern == NULL)
 698         return NULL;
 699
 700       pattern = g_strdup_printf ("m%s", child_pattern);
 701       g_free (child_pattern);
 702
 703       return pattern;
 704     }
 705
 706   return g_strdup ("m*");
 707 }
 708
 709 static GVariant *
 710 maybe_get_value (AST                 *ast,
 711                  const GVariantType  *type,
 712                  GError             **error)
 713 {
 714   Maybe *maybe = (Maybe *) ast;
 715   GVariant *value;
 716
 717   if (!g_variant_type_is_maybe (type))
 718     return ast_type_error (ast, type, error);
 719
 720   type = g_variant_type_element (type);
 721
 722   if (maybe->child)
 723     {
 724       value = ast_get_value (maybe->child, type, error);
 725
 726       if (value == NULL)
 727         return NULL;
 728     }
 729   else
 730     value = NULL;
 731
 732   return g_variant_new_maybe (type, value);
 733 }
 734
 735 static void
 736 maybe_free (AST *ast)
 737 {
 738   Maybe *maybe = (Maybe *) ast;
 739
 740   if (maybe->child != NULL)
 741     ast_free (maybe->child);
 742
 743   g_slice_free (Maybe, maybe);
 744 }
 745
 746 static AST *
 747 maybe_parse (TokenStream  *stream,
 748              va_list      *app,
 749              GError      **error)
 750 {
 751   static const ASTClass maybe_class = {
 752     maybe_get_pattern,
 753     maybe_get_value, NULL,
 754     maybe_free
 755   };
 756   AST *child = NULL;
 757   Maybe *maybe;
 758
 759   if (token_stream_consume (stream, "just"))
 760     {
 761       child = parse (stream, app, error);
 762       if (child == NULL)
 763         return NULL;
 764     }
 765
 766   else if (!token_stream_consume (stream, "nothing"))
 767     {
 768       token_stream_set_error (stream, error, TRUE, "unknown keyword");
 769       return NULL;
 770     }
 771
 772   maybe = g_slice_new (Maybe);
 773   maybe->ast.class = &maybe_class;
 774   maybe->child = child;
 775
 776   return (AST *) maybe;
 777 }
 778
 779 static GVariant *
 780 maybe_wrapper (AST                 *ast,
 781                const GVariantType  *type,
 782                GError             **error)
 783 {
 784   const GVariantType *t;
 785   GVariant *value;
 786   int depth;
 787
 788   for (depth = 0, t = type;
 789        g_variant_type_is_maybe (t);
 790        depth++, t = g_variant_type_element (t));
 791
 792   value = ast->class->get_base_value (ast, t, error);
 793
 794   if (value == NULL)
 795     return NULL;
 796
 797   while (depth--)
 798     value = g_variant_new_maybe (NULL, value);
 799
 800   return value;
 801 }
 802
 803 typedef struct
 804 {
 805   AST ast;
 806
 807   AST **children;
 808   gint n_children;
 809 } Array;
 810
 811 static gchar *
 812 array_get_pattern (AST     *ast,
 813                    GError **error)
 814 {
 815   Array *array = (Array *) ast;
 816   gchar *pattern;
 817   gchar *result;
 818
 819   if (array->n_children == 0)
 820     return g_strdup ("Ma*");
 821
 822   pattern = ast_array_get_pattern (array->children, array->n_children, error);
 823
 824   if (pattern == NULL)
 825     return NULL;
 826
 827   result = g_strdup_printf ("Ma%s", pattern);
 828   g_free (pattern);
 829
 830   return result;
 831 }
 832
 833 static GVariant *
 834 array_get_value (AST                 *ast,
 835                  const GVariantType  *type,
 836                  GError             **error)
 837 {
 838   Array *array = (Array *) ast;
 839   const GVariantType *childtype;
 840   GVariantBuilder builder;
 841   gint i;
 842
 843   if (!g_variant_type_is_array (type))
 844     return ast_type_error (ast, type, error);
 845
 846   g_variant_builder_init (&builder, type);
 847   childtype = g_variant_type_element (type);
 848
 849   for (i = 0; i < array->n_children; i++)
 850     {
 851       GVariant *child;
 852
 853       if (!(child = ast_get_value (array->children[i], childtype, error)))
 854         {
 855           g_variant_builder_clear (&builder);
 856           return NULL;
 857         }
 858
 859       g_variant_builder_add_value (&builder, child);
 860     }
 861
 862   return g_variant_builder_end (&builder);
 863 }
 864
 865 static void
 866 array_free (AST *ast)
 867 {
 868   Array *array = (Array *) ast;
 869
 870   ast_array_free (array->children, array->n_children);
 871   g_slice_free (Array, array);
 872 }
 873
 874 static AST *
 875 array_parse (TokenStream  *stream,
 876              va_list      *app,
 877              GError      **error)
 878 {
 879   static const ASTClass array_class = {
 880     array_get_pattern,
 881     maybe_wrapper, array_get_value,
 882     array_free
 883   };
 884   gboolean need_comma = FALSE;
 885   Array *array;
 886
 887   array = g_slice_new (Array);
 888   array->ast.class = &array_class;
 889   array->children = NULL;
 890   array->n_children = 0;
 891
 892   token_stream_assert (stream, "[");
 893   while (!token_stream_consume (stream, "]"))
 894     {
 895       AST *child;
 896
 897       if (need_comma &&
 898           !token_stream_require (stream, ",",
 899                                  " or `]' to follow array element",
 900                                  error))
 901         goto error;
 902
 903       child = parse (stream, app, error);
 904
 905       if (!child)
 906         goto error;
 907
 908       ast_array_append (&array->children, &array->n_children, child);
 909       need_comma = TRUE;
 910     }
 911
 912   return (AST *) array;
 913
 914  error:
 915   ast_array_free (array->children, array->n_children);
 916   g_slice_free (Array, array);
 917
 918   return NULL;
 919 }
 920
 921 typedef struct
 922 {
 923   AST ast;
 924
 925   AST **children;
 926   gint n_children;
 927 } Tuple;
 928
 929 static gchar *
 930 tuple_get_pattern (AST     *ast,
 931                    GError **error)
 932 {
 933   Tuple *tuple = (Tuple *) ast;
 934   gchar *result = NULL;
 935   gchar **parts;
 936   gint i;
 937
 938   parts = g_new (gchar *, tuple->n_children + 4);
 939   parts[tuple->n_children + 1] = (gchar *) ")";
 940   parts[tuple->n_children + 2] = NULL;
 941   parts[0] = (gchar *) "M(";
 942
 943   for (i = 0; i < tuple->n_children; i++)
 944     if (!(parts[i + 1] = ast_get_pattern (tuple->children[i], error)))
 945       break;
 946
 947   if (i == tuple->n_children)
 948     result = g_strjoinv ("", parts);
 949
 950   /* parts[0] should not be freed */
 951   while (i)
 952     g_free (parts[i--]);
 953   g_free (parts);
 954
 955   return result;
 956 }
 957
 958 static GVariant *
 959 tuple_get_value (AST                 *ast,
 960                  const GVariantType  *type,
 961                  GError             **error)
 962 {
 963   Tuple *tuple = (Tuple *) ast;
 964   const GVariantType *childtype;
 965   GVariantBuilder builder;
 966   gint i;
 967
 968   if (!g_variant_type_is_tuple (type))
 969     return ast_type_error (ast, type, error);
 970
 971   g_variant_builder_init (&builder, type);
 972   childtype = g_variant_type_first (type);
 973
 974   for (i = 0; i < tuple->n_children; i++)
 975     {
 976       GVariant *child;
 977
 978       if (!(child = ast_get_value (tuple->children[i], childtype, error)))
 979         {
 980           g_variant_builder_clear (&builder);
 981           return FALSE;
 982         }
 983
 984       g_variant_builder_add_value (&builder, child);
 985       childtype = g_variant_type_next (childtype);
 986     }
 987
 988   return g_variant_builder_end (&builder);
 989 }
 990
 991 static void
 992 tuple_free (AST *ast)
 993 {
 994   Tuple *tuple = (Tuple *) ast;
 995
 996   ast_array_free (tuple->children, tuple->n_children);
 997   g_slice_free (Tuple, tuple);
 998 }
 999
1000 static AST *
1001 tuple_parse (TokenStream  *stream,
1002              va_list      *app,
1003              GError      **error)
1004 {
1005   static const ASTClass tuple_class = {
1006     tuple_get_pattern,
1007     maybe_wrapper, tuple_get_value,
1008     tuple_free
1009   };
1010   gboolean need_comma = FALSE;
1011   gboolean first = TRUE;
1012   Tuple *tuple;
1013
1014   tuple = g_slice_new (Tuple);
1015   tuple->ast.class = &tuple_class;
1016   tuple->children = NULL;
1017   tuple->n_children = 0;
1018
1019   token_stream_assert (stream, "(");
1020   while (!token_stream_consume (stream, ")"))
1021     {
1022       AST *child;
1023
1024       if (need_comma &&
1025           !token_stream_require (stream, ",",
1026                                  " or `)' to follow tuple element",
1027                                  error))
1028         goto error;
1029
1030       child = parse (stream, app, error);
1031
1032       if (!child)
1033         goto error;
1034
1035       ast_array_append (&tuple->children, &tuple->n_children, child);
1036
1037       /* the first time, we absolutely require a comma, so grab it here
1038        * and leave need_comma = FALSE so that the code above doesn't
1039        * require a second comma.
1040        *
1041        * the second and remaining times, we set need_comma = TRUE.
1042        */
1043       if (first)
1044         {
1045           if (!token_stream_require (stream, ",",
1046                                      " after first tuple element", error))
1047             goto error;
1048
1049           first = FALSE;
1050         }
1051       else
1052         need_comma = TRUE;
1053     }
1054
1055   return (AST *) tuple;
1056
1057  error:
1058   ast_array_free (tuple->children, tuple->n_children);
1059   g_slice_free (Tuple, tuple);
1060
1061   return NULL;
1062 }
1063
1064 typedef struct
1065 {
1066   AST ast;
1067
1068   AST *value;
1069 } Variant;
1070
1071 static gchar *
1072 variant_get_pattern (AST     *ast,
1073                      GError **error)
1074 {
1075   return g_strdup ("Mv");
1076 }
1077
1078 static GVariant *
1079 variant_get_value (AST                 *ast,
1080                    const GVariantType  *type,
1081                    GError             **error)
1082 {
1083   Variant *variant = (Variant *) ast;
1084   GVariant *child;
1085
1086   g_assert (g_variant_type_equal (type, G_VARIANT_TYPE_VARIANT));
1087   child = ast_resolve (variant->value, error);
1088
1089   if (child == NULL)
1090     return NULL;
1091
1092   return g_variant_new_variant (child);
1093 }
1094
1095 static void
1096 variant_free (AST *ast)
1097 {
1098   Variant *variant = (Variant *) ast;
1099
1100   ast_free (variant->value);
1101   g_slice_free (Variant, variant);
1102 }
1103
1104 static AST *
1105 variant_parse (TokenStream  *stream,
1106                va_list      *app,
1107                GError      **error)
1108 {
1109   static const ASTClass variant_class = {
1110     variant_get_pattern,
1111     maybe_wrapper, variant_get_value,
1112     variant_free
1113   };
1114   Variant *variant;
1115   AST *value;
1116
1117   token_stream_assert (stream, "<");
1118   value = parse (stream, app, error);
1119
1120   if (!value)
1121     return NULL;
1122
1123   if (!token_stream_require (stream, ">", " to follow variant value", error))
1124     {
1125       ast_free (value);
1126       return NULL;
1127     }
1128
1129   variant = g_slice_new (Variant);
1130   variant->ast.class = &variant_class;
1131   variant->value = value;
1132
1133   return (AST *) variant;
1134 }
1135
1136 typedef struct
1137 {
1138   AST ast;
1139
1140   AST **keys;
1141   AST **values;
1142   gint n_children;
1143 } Dictionary;
1144
1145 static gchar *
1146 dictionary_get_pattern (AST     *ast,
1147                         GError **error)
1148 {
1149   Dictionary *dict = (Dictionary *) ast;
1150   gchar *value_pattern;
1151   gchar *key_pattern;
1152   gchar key_char;
1153   gchar *result;
1154
1155   if (dict->n_children == 0)
1156     return g_strdup ("Ma{**}");
1157
1158   key_pattern = ast_array_get_pattern (dict->keys,
1159                                        abs (dict->n_children),
1160                                        error);
1161
1162   if (key_pattern == NULL)
1163     return NULL;
1164
1165   /* we can not have maybe keys */
1166   if (key_pattern[0] == 'M')
1167     key_char = key_pattern[1];
1168   else
1169     key_char = key_pattern[0];
1170
1171   g_free (key_pattern);
1172
1173   /* the basic types,
1174    * plus undetermined number type and undetermined string type.
1175    */
1176   if (!strchr ("bynqiuxthdsogNS", key_char))
1177     {
1178       ast_set_error (ast, error, NULL,
1179                      "dictionary keys must have basic types");
1180       return NULL;
1181     }
1182
1183   value_pattern = ast_get_pattern (dict->values[0], error);
1184
1185   if (value_pattern == NULL)
1186     return NULL;
1187
1188   result = g_strdup_printf ("M%s{%c%s}",
1189                             dict->n_children > 0 ? "a" : "",
1190                             key_char, value_pattern);
1191   g_free (value_pattern);
1192
1193   return result;
1194 }
1195
1196 static GVariant *
1197 dictionary_get_value (AST                 *ast,
1198                       const GVariantType  *type,
1199                       GError             **error)
1200 {
1201   Dictionary *dict = (Dictionary *) ast;
1202
1203   if (dict->n_children == -1)
1204     {
1205       const GVariantType *subtype;
1206       GVariantBuilder builder;
1207       GVariant *subvalue;
1208
1209       if (!g_variant_type_is_dict_entry (type))
1210         return ast_type_error (ast, type, error);
1211
1212       g_variant_builder_init (&builder, type);
1213
1214       subtype = g_variant_type_key (type);
1215       if (!(subvalue = ast_get_value (dict->keys[0], subtype, error)))
1216         {
1217           g_variant_builder_clear (&builder);
1218           return FALSE;
1219         }
1220       g_variant_builder_add_value (&builder, subvalue);
1221
1222       subtype = g_variant_type_value (type);
1223       if (!(subvalue = ast_get_value (dict->values[0], subtype, error)))
1224         {
1225           g_variant_builder_clear (&builder);
1226           return FALSE;
1227         }
1228       g_variant_builder_add_value (&builder, subvalue);
1229
1230       return g_variant_builder_end (&builder);
1231     }
1232   else
1233     {
1234       const GVariantType *entry, *key, *val;
1235       GVariantBuilder builder;
1236       gint i;
1237
1238       if (!g_variant_type_is_subtype_of (type, G_VARIANT_TYPE_DICTIONARY))
1239         return ast_type_error (ast, type, error);
1240
1241       entry = g_variant_type_element (type);
1242       key = g_variant_type_key (entry);
1243       val = g_variant_type_value (entry);
1244
1245       g_variant_builder_init (&builder, type);
1246
1247       for (i = 0; i < dict->n_children; i++)
1248         {
1249           GVariant *subvalue;
1250
1251           g_variant_builder_open (&builder, entry);
1252
1253           if (!(subvalue = ast_get_value (dict->keys[i], key, error)))
1254             {
1255               g_variant_builder_clear (&builder);
1256               return FALSE;
1257             }
1258           g_variant_builder_add_value (&builder, subvalue);
1259
1260           if (!(subvalue = ast_get_value (dict->values[i], val, error)))
1261             {
1262               g_variant_builder_clear (&builder);
1263               return FALSE;
1264             }
1265           g_variant_builder_add_value (&builder, subvalue);
1266           g_variant_builder_close (&builder);
1267         }
1268
1269       return g_variant_builder_end (&builder);
1270     }
1271 }
1272
1273 static void
1274 dictionary_free (AST *ast)
1275 {
1276   Dictionary *dict = (Dictionary *) ast;
1277   gint n_children;
1278
1279   if (dict->n_children > -1)
1280     n_children = dict->n_children;
1281   else
1282     n_children = 1;
1283
1284   ast_array_free (dict->keys, n_children);
1285   ast_array_free (dict->values, n_children);
1286   g_slice_free (Dictionary, dict);
1287 }
1288
1289 static AST *
1290 dictionary_parse (TokenStream  *stream,
1291                   va_list      *app,
1292                   GError      **error)
1293 {
1294   static const ASTClass dictionary_class = {
1295     dictionary_get_pattern,
1296     maybe_wrapper, dictionary_get_value,
1297     dictionary_free
1298   };
1299   gint n_keys, n_values;
1300   gboolean only_one;
1301   Dictionary *dict;
1302   AST *first;
1303
1304   dict = g_slice_new (Dictionary);
1305   dict->ast.class = &dictionary_class;
1306   dict->keys = NULL;
1307   dict->values = NULL;
1308   n_keys = n_values = 0;
1309
1310   token_stream_assert (stream, "{");
1311
1312   if (token_stream_consume (stream, "}"))
1313     {
1314       dict->n_children = 0;
1315       return (AST *) dict;
1316     }
1317
1318   if ((first = parse (stream, app, error)) == NULL)
1319     goto error;
1320
1321   ast_array_append (&dict->keys, &n_keys, first);
1322
1323   only_one = token_stream_consume (stream, ",");
1324   if (!only_one &&
1325       !token_stream_require (stream, ":",
1326                              " or `,' to follow dictionary entry key",
1327                              error))
1328     goto error;
1329
1330   if ((first = parse (stream, app, error)) == NULL)
1331     goto error;
1332
1333   ast_array_append (&dict->values, &n_values, first);
1334
1335   if (only_one)
1336     {
1337       if (!token_stream_require (stream, "}", " at end of dictionary entry",
1338                                  error))
1339         goto error;
1340
1341       g_assert (n_keys == 1 && n_values == 1);
1342       dict->n_children = -1;
1343
1344       return (AST *) dict;
1345     }
1346
1347   while (!token_stream_consume (stream, "}"))
1348     {
1349       AST *child;
1350
1351       if (!token_stream_require (stream, ",",
1352                                  " or `}' to follow dictionary entry", error))
1353         goto error;
1354
1355       child = parse (stream, app, error);
1356
1357       if (!child)
1358         goto error;
1359
1360       ast_array_append (&dict->keys, &n_keys, child);
1361
1362       if (!token_stream_require (stream, ":",
1363                                  " to follow dictionary entry key", error))
1364         goto error;
1365
1366       child = parse (stream, app, error);
1367
1368       if (!child)
1369         goto error;
1370
1371       ast_array_append (&dict->values, &n_values, child);
1372     }
1373
1374   g_assert (n_keys == n_values);
1375   dict->n_children = n_keys;
1376
1377   return (AST *) dict;
1378
1379  error:
1380   ast_array_free (dict->keys, n_keys);
1381   ast_array_free (dict->values, n_values);
1382   g_slice_free (Dictionary, dict);
1383
1384   return NULL;
1385 }
1386
1387 typedef struct
1388 {
1389   AST ast;
1390   gchar *string;
1391 } String;
1392
1393 static gchar *
1394 string_get_pattern (AST     *ast,
1395                     GError **error)
1396 {
1397   return g_strdup ("MS");
1398 }
1399
1400 static GVariant *
1401 string_get_value (AST                 *ast,
1402                   const GVariantType  *type,
1403                   GError             **error)
1404 {
1405   String *string = (String *) ast;
1406
1407   if (g_variant_type_equal (type, G_VARIANT_TYPE_STRING))
1408     return g_variant_new_string (string->string);
1409
1410   else if (g_variant_type_equal (type, G_VARIANT_TYPE_OBJECT_PATH))
1411     {
1412       if (!g_variant_is_object_path (string->string))
1413         {
1414           ast_set_error (ast, error, NULL, "not a valid object path");
1415           return NULL;
1416         }
1417
1418       return g_variant_new_object_path (string->string);
1419     }
1420
1421   else if (g_variant_type_equal (type, G_VARIANT_TYPE_SIGNATURE))
1422     {
1423       if (!g_variant_is_signature (string->string))
1424         {
1425           ast_set_error (ast, error, NULL, "not a valid signature");
1426           return NULL;
1427         }
1428
1429       return g_variant_new_signature (string->string);
1430     }
1431
1432   else
1433     return ast_type_error (ast, type, error);
1434 }
1435
1436 static void
1437 string_free (AST *ast)
1438 {
1439   String *string = (String *) ast;
1440
1441   g_free (string->string);
1442   g_slice_free (String, string);
1443 }
1444
1445 static gboolean
1446 unicode_unescape (const gchar  *src,
1447                   gint         *src_ofs,
1448                   gchar        *dest,
1449                   gint         *dest_ofs,
1450                   gint          length,
1451                   SourceRef    *ref,
1452                   GError      **error)
1453 {
1454   gchar buffer[9];
1455   guint64 value;
1456   gchar *end;
1457
1458   (*src_ofs)++;
1459
1460   g_assert (length < sizeof (buffer));
1461   strncpy (buffer, src + *src_ofs, length);
1462   buffer[length] = '\0';
1463
1464   value = g_ascii_strtoull (buffer, &end, 0x10);
1465
1466   if (value == 0 || end != buffer + length)
1467     {
1468       parser_set_error (error, ref, NULL,
1469                         "invalid %d-character unicode escape", length);
1470       return FALSE;
1471     }
1472
1473   g_assert (value <= G_MAXUINT32);
1474
1475   *dest_ofs += g_unichar_to_utf8 (value, dest + *dest_ofs);
1476   *src_ofs += length;
1477
1478   return TRUE;
1479 }
1480
1481 static AST *
1482 string_parse (TokenStream  *stream,
1483               va_list      *app,
1484               GError      **error)
1485 {
1486   static const ASTClass string_class = {
1487     string_get_pattern,
1488     maybe_wrapper, string_get_value,
1489     string_free
1490   };
1491   String *string;
1492   SourceRef ref;
1493   gchar *token;
1494   gsize length;
1495   gchar quote;
1496   gchar *str;
1497   gint i, j;
1498
1499   token_stream_start_ref (stream, &ref);
1500   token = token_stream_get (stream);
1501   token_stream_end_ref (stream, &ref);
1502   length = strlen (token);
1503   quote = token[0];
1504
1505   str = g_malloc (length);
1506   g_assert (quote == '"' || quote == '\'');
1507   j = 0;
1508   i = 1;
1509   while (token[i] != quote)
1510     switch (token[i])
1511       {
1512       case '\0':
1513         parser_set_error (error, &ref, NULL,
1514                           "unterminated string constant");
1515         g_free (token);
1516         return NULL;
1517
1518       case '\\':
1519         switch (token[++i])
1520           {
1521           case '\0':
1522             parser_set_error (error, &ref, NULL,
1523                               "unterminated string constant");
1524             g_free (token);
1525             return NULL;
1526
1527           case 'u':
1528             if (!unicode_unescape (token, &i, str, &j, 4, &ref, error))
1529               {
1530                 g_free (token);
1531                 return NULL;
1532               }
1533             continue;
1534
1535           case 'U':
1536             if (!unicode_unescape (token, &i, str, &j, 8, &ref, error))
1537               {
1538                 g_free (token);
1539                 return NULL;
1540               }
1541             continue;
1542
1543           case 'a': str[j++] = '\a'; i++; continue;
1544           case 'b': str[j++] = '\b'; i++; continue;
1545           case 'f': str[j++] = '\f'; i++; continue;
1546           case 'n': str[j++] = '\n'; i++; continue;
1547           case 'r': str[j++] = '\r'; i++; continue;
1548           case 't': str[j++] = '\t'; i++; continue;
1549           case 'v': str[j++] = '\v'; i++; continue;
1550           case '\n': i++; continue;
1551           }
1552
1553       default:
1554         str[j++] = token[i++];
1555       }
1556   str[j++] = '\0';
1557   g_free (token);
1558
1559   string = g_slice_new (String);
1560   string->ast.class = &string_class;
1561   string->string = str;
1562
1563   token_stream_next (stream);
1564
1565   return (AST *) string;
1566 }
1567
1568 typedef struct
1569 {
1570   AST ast;
1571   gchar *string;
1572 } ByteString;
1573
1574 static gchar *
1575 bytestring_get_pattern (AST     *ast,
1576                         GError **error)
1577 {
1578   return g_strdup ("May");
1579 }
1580
1581 static GVariant *
1582 bytestring_get_value (AST                 *ast,
1583                       const GVariantType  *type,
1584                       GError             **error)
1585 {
1586   ByteString *string = (ByteString *) ast;
1587
1588   g_assert (g_variant_type_equal (type, G_VARIANT_TYPE_BYTESTRING));
1589
1590   return g_variant_new_bytestring (string->string);
1591 }
1592
1593 static void
1594 bytestring_free (AST *ast)
1595 {
1596   ByteString *string = (ByteString *) ast;
1597
1598   g_free (string->string);
1599   g_slice_free (ByteString, string);
1600 }
1601
1602 static AST *
1603 bytestring_parse (TokenStream  *stream,
1604                   va_list      *app,
1605                   GError      **error)
1606 {
1607   static const ASTClass bytestring_class = {
1608     bytestring_get_pattern,
1609     maybe_wrapper, bytestring_get_value,
1610     bytestring_free
1611   };
1612   ByteString *string;
1613   SourceRef ref;
1614   gchar *token;
1615   gsize length;
1616   gchar quote;
1617   gchar *str;
1618   gint i, j;
1619
1620   token_stream_start_ref (stream, &ref);
1621   token = token_stream_get (stream);
1622   token_stream_end_ref (stream, &ref);
1623   g_assert (token[0] == 'b');
1624   length = strlen (token);
1625   quote = token[1];
1626
1627   str = g_malloc (length);
1628   g_assert (quote == '"' || quote == '\'');
1629   j = 0;
1630   i = 2;
1631   while (token[i] != quote)
1632     switch (token[i])
1633       {
1634       case '\0':
1635         parser_set_error (error, &ref, NULL,
1636                           "unterminated string constant");
1637         g_free (token);
1638         return NULL;
1639
1640       case '\\':
1641         switch (token[++i])
1642           {
1643           case '\0':
1644             parser_set_error (error, &ref, NULL,
1645                               "unterminated string constant");
1646             g_free (token);
1647             return NULL;
1648
1649           case '0': case '1': case '2': case '3':
1650           case '4': case '5': case '6': case '7':
1651             {
1652               /* up to 3 characters */
1653               guchar val = token[i++] - '0';
1654
1655               if ('0' <= token[i] && token[i] < '8')
1656                 val = (val << 3) | (token[i++] - '0');
1657
1658               if ('0' <= token[i] && token[i] < '8')
1659                 val = (val << 3) | (token[i++] - '0');
1660
1661               str[j++] = val;
1662             }
1663             continue;
1664
1665           case 'a': str[j++] = '\a'; i++; continue;
1666           case 'b': str[j++] = '\b'; i++; continue;
1667           case 'f': str[j++] = '\f'; i++; continue;
1668           case 'n': str[j++] = '\n'; i++; continue;
1669           case 'r': str[j++] = '\r'; i++; continue;
1670           case 't': str[j++] = '\t'; i++; continue;
1671           case 'v': str[j++] = '\v'; i++; continue;
1672           case '\n': i++; continue;
1673           }
1674
1675       default:
1676         str[j++] = token[i++];
1677       }
1678   str[j++] = '\0';
1679   g_free (token);
1680
1681   string = g_slice_new (ByteString);
1682   string->ast.class = &bytestring_class;
1683   string->string = str;
1684
1685   token_stream_next (stream);
1686
1687   return (AST *) string;
1688 }
1689
1690 typedef struct
1691 {
1692   AST ast;
1693
1694   gchar *token;
1695 } Number;
1696
1697 static gchar *
1698 number_get_pattern (AST     *ast,
1699                     GError **error)
1700 {
1701   Number *number = (Number *) ast;
1702
1703   if (strchr (number->token, '.') ||
1704       (!g_str_has_prefix (number->token, "0x") &&
1705        strchr (number->token, 'e')))
1706     return g_strdup ("Md");
1707
1708   return g_strdup ("MN");
1709 }
1710
1711 static GVariant *
1712 number_overflow (AST                 *ast,
1713                  const GVariantType  *type,
1714                  GError             **error)
1715 {
1716   ast_set_error (ast, error, NULL, "number out of range for type `%c'",
1717                  g_variant_type_peek_string (type)[0]);
1718   return NULL;
1719 }
1720
1721 static GVariant *
1722 number_get_value (AST                 *ast,
1723                   const GVariantType  *type,
1724                   GError             **error)
1725 {
1726   Number *number = (Number *) ast;
1727   const gchar *token;
1728   gboolean negative;
1729   gboolean floating;
1730   guint64 abs_val;
1731   gdouble dbl_val;
1732   gchar *end;
1733
1734   token = number->token;
1735
1736   if (g_variant_type_equal (type, G_VARIANT_TYPE_DOUBLE))
1737     {
1738       floating = TRUE;
1739
1740       errno = 0;
1741       dbl_val = g_ascii_strtod (token, &end);
1742       if (dbl_val != 0.0 && errno == ERANGE)
1743         {
1744           ast_set_error (ast, error, NULL, "number too big for any type");
1745           return NULL;
1746         }
1747
1748       /* silence uninitialised warnings... */
1749       negative = FALSE;
1750       abs_val = 0;
1751     }
1752   else
1753     {
1754       floating = FALSE;
1755       negative = token[0] == '-';
1756       if (token[0] == '-')
1757         token++;
1758
1759       errno = 0;
1760       abs_val = g_ascii_strtoull (token, &end, 0);
1761       if (abs_val == G_MAXUINT64 && errno == ERANGE)
1762         {
1763           ast_set_error (ast, error, NULL, "integer too big for any type");
1764           return NULL;
1765         }
1766
1767       if (abs_val == 0)
1768         negative = FALSE;
1769
1770       /* silence uninitialised warning... */
1771       dbl_val = 0.0;
1772     }
1773
1774   if (*end != '\0')
1775     {
1776       SourceRef ref;
1777
1778       ref = ast->source_ref;
1779       ref.start += end - number->token;
1780       ref.end = ref.start + 1;
1781
1782       parser_set_error (error, &ref, NULL,
1783                         "invalid character in number");
1784       return NULL;
1785      }
1786
1787   if (floating)
1788     return g_variant_new_double (dbl_val);
1789
1790   switch (*g_variant_type_peek_string (type))
1791     {
1792     case 'y':
1793       if (negative || abs_val > G_MAXUINT8)
1794         return number_overflow (ast, type, error);
1795       return g_variant_new_byte (abs_val);
1796
1797     case 'n':
1798       if (abs_val - negative > G_MAXINT16)
1799         return number_overflow (ast, type, error);
1800       return g_variant_new_int16 (negative ? -abs_val : abs_val);
1801
1802     case 'q':
1803       if (negative || abs_val > G_MAXUINT16)
1804         return number_overflow (ast, type, error);
1805       return g_variant_new_uint16 (negative ? -abs_val : abs_val);
1806
1807     case 'i':
1808       if (abs_val - negative > G_MAXINT32)
1809         return number_overflow (ast, type, error);
1810       return g_variant_new_int32 (negative ? -abs_val : abs_val);
1811
1812     case 'u':
1813       if (negative || abs_val > G_MAXUINT32)
1814         return number_overflow (ast, type, error);
1815       return g_variant_new_uint32 (negative ? -abs_val : abs_val);
1816
1817     case 'x':
1818       if (abs_val - negative > G_MAXINT64)
1819         return number_overflow (ast, type, error);
1820       return g_variant_new_int64 (negative ? -abs_val : abs_val);
1821
1822     case 't':
1823       if (negative)
1824         return number_overflow (ast, type, error);
1825       return g_variant_new_uint64 (negative ? -abs_val : abs_val);
1826
1827     case 'h':
1828       if (abs_val - negative > G_MAXINT32)
1829         return number_overflow (ast, type, error);
1830       return g_variant_new_handle (negative ? -abs_val : abs_val);
1831
1832     default:
1833       return ast_type_error (ast, type, error);
1834     }
1835 }
1836
1837 static void
1838 number_free (AST *ast)
1839 {
1840   Number *number = (Number *) ast;
1841
1842   g_free (number->token);
1843   g_slice_free (Number, number);
1844 }
1845
1846 static AST *
1847 number_parse (TokenStream  *stream,
1848               va_list      *app,
1849               GError      **error)
1850 {
1851   static const ASTClass number_class = {
1852     number_get_pattern,
1853     maybe_wrapper, number_get_value,
1854     number_free
1855   };
1856   Number *number;
1857
1858   number = g_slice_new (Number);
1859   number->ast.class = &number_class;
1860   number->token = token_stream_get (stream);
1861   token_stream_next (stream);
1862
1863   return (AST *) number;
1864 }
1865
1866 typedef struct
1867 {
1868   AST ast;
1869   gboolean value;
1870 } Boolean;
1871
1872 static gchar *
1873 boolean_get_pattern (AST     *ast,
1874                      GError **error)
1875 {
1876   return g_strdup ("Mb");
1877 }
1878
1879 static GVariant *
1880 boolean_get_value (AST                 *ast,
1881                    const GVariantType  *type,
1882                    GError             **error)
1883 {
1884   Boolean *boolean = (Boolean *) ast;
1885
1886   if (!g_variant_type_equal (type, G_VARIANT_TYPE_BOOLEAN))
1887     return ast_type_error (ast, type, error);
1888
1889   return g_variant_new_boolean (boolean->value);
1890 }
1891
1892 static void
1893 boolean_free (AST *ast)
1894 {
1895   Boolean *boolean = (Boolean *) ast;
1896
1897   g_slice_free (Boolean, boolean);
1898 }
1899
1900 static AST *
1901 boolean_new (gboolean value)
1902 {
1903   static const ASTClass boolean_class = {
1904     boolean_get_pattern,
1905     maybe_wrapper, boolean_get_value,
1906     boolean_free
1907   };
1908   Boolean *boolean;
1909
1910   boolean = g_slice_new (Boolean);
1911   boolean->ast.class = &boolean_class;
1912   boolean->value = value;
1913
1914   return (AST *) boolean;
1915 }
1916
1917 typedef struct
1918 {
1919   AST ast;
1920
1921   GVariant *value;
1922 } Positional;
1923
1924 static gchar *
1925 positional_get_pattern (AST     *ast,
1926                         GError **error)
1927 {
1928   Positional *positional = (Positional *) ast;
1929
1930   return g_strdup (g_variant_get_type_string (positional->value));
1931 }
1932
1933 static GVariant *
1934 positional_get_value (AST                 *ast,
1935                       const GVariantType  *type,
1936                       GError             **error)
1937 {
1938   Positional *positional = (Positional *) ast;
1939   GVariant *value;
1940
1941   g_assert (positional->value != NULL);
1942
1943   if G_UNLIKELY (!g_variant_is_of_type (positional->value, type))
1944     return ast_type_error (ast, type, error);
1945
1946   /* NOTE: if _get is called more than once then
1947    * things get messed up with respect to floating refs.
1948    *
1949    * fortunately, this function should only ever get called once.
1950    */
1951   g_assert (positional->value != NULL);
1952   value = positional->value;
1953   positional->value = NULL;
1954
1955   return value;
1956 }
1957
1958 static void
1959 positional_free (AST *ast)
1960 {
1961   Positional *positional = (Positional *) ast;
1962
1963   /* if positional->value is set, just leave it.
1964    * memory management doesn't matter in case of programmer error.
1965    */
1966   g_slice_free (Positional, positional);
1967 }
1968
1969 static AST *
1970 positional_parse (TokenStream  *stream,
1971                   va_list      *app,
1972                   GError      **error)
1973 {
1974   static const ASTClass positional_class = {
1975     positional_get_pattern,
1976     positional_get_value, NULL,
1977     positional_free
1978   };
1979   Positional *positional;
1980   const gchar *endptr;
1981   gchar *token;
1982
1983   token = token_stream_get (stream);
1984   g_assert (token[0] == '%');
1985
1986   positional = g_slice_new (Positional);
1987   positional->ast.class = &positional_class;
1988   positional->value = g_variant_new_va (token + 1, &endptr, app);
1989
1990   if (*endptr || positional->value == NULL)
1991     {
1992       token_stream_set_error (stream, error, TRUE,
1993                               "invalid GVariant format string");
1994       /* memory management doesn't matter in case of programmer error. */
1995       return NULL;
1996     }
1997
1998   token_stream_next (stream);
1999   g_free (token);
2000
2001   return (AST *) positional;
2002 }
2003
2004 typedef struct
2005 {
2006   AST ast;
2007
2008   GVariantType *type;
2009   AST *child;
2010 } TypeDecl;
2011
2012 static gchar *
2013 typedecl_get_pattern (AST     *ast,
2014                       GError **error)
2015 {
2016   TypeDecl *decl = (TypeDecl *) ast;
2017
2018   return g_variant_type_dup_string (decl->type);
2019 }
2020
2021 static GVariant *
2022 typedecl_get_value (AST                 *ast,
2023                     const GVariantType  *type,
2024                     GError             **error)
2025 {
2026   TypeDecl *decl = (TypeDecl *) ast;
2027
2028   return ast_get_value (decl->child, type, error);
2029 }
2030
2031 static void
2032 typedecl_free (AST *ast)
2033 {
2034   TypeDecl *decl = (TypeDecl *) ast;
2035
2036   ast_free (decl->child);
2037   g_variant_type_free (decl->type);
2038   g_slice_free (TypeDecl, decl);
2039 }
2040
2041 static AST *
2042 typedecl_parse (TokenStream  *stream,
2043                 va_list      *app,
2044                 GError      **error)
2045 {
2046   static const ASTClass typedecl_class = {
2047     typedecl_get_pattern,
2048     typedecl_get_value, NULL,
2049     typedecl_free
2050   };
2051   GVariantType *type;
2052   TypeDecl *decl;
2053   AST *child;
2054
2055   if (token_stream_peek (stream, '@'))
2056     {
2057       gchar *token;
2058
2059       token = token_stream_get (stream);
2060
2061       if (!g_variant_type_string_is_valid (token + 1))
2062         {
2063           token_stream_set_error (stream, error, TRUE,
2064                                   "invalid type declaration");
2065           g_free (token);
2066
2067           return NULL;
2068         }
2069
2070       type = g_variant_type_new (token + 1);
2071
2072       if (!g_variant_type_is_definite (type))
2073         {
2074           token_stream_set_error (stream, error, TRUE,
2075                                   "type declarations must be definite");
2076           g_variant_type_free (type);
2077           g_free (token);
2078
2079           return NULL;
2080         }
2081
2082       token_stream_next (stream);
2083       g_free (token);
2084     }
2085   else
2086     {
2087       if (token_stream_consume (stream, "boolean"))
2088         type = g_variant_type_copy (G_VARIANT_TYPE_BOOLEAN);
2089
2090       else if (token_stream_consume (stream, "byte"))
2091         type = g_variant_type_copy (G_VARIANT_TYPE_BYTE);
2092
2093       else if (token_stream_consume (stream, "int16"))
2094         type = g_variant_type_copy (G_VARIANT_TYPE_INT16);
2095
2096       else if (token_stream_consume (stream, "uint16"))
2097         type = g_variant_type_copy (G_VARIANT_TYPE_UINT16);
2098
2099       else if (token_stream_consume (stream, "int32"))
2100         type = g_variant_type_copy (G_VARIANT_TYPE_INT32);
2101
2102       else if (token_stream_consume (stream, "handle"))
2103         type = g_variant_type_copy (G_VARIANT_TYPE_HANDLE);
2104
2105       else if (token_stream_consume (stream, "uint32"))
2106         type = g_variant_type_copy (G_VARIANT_TYPE_UINT32);
2107
2108       else if (token_stream_consume (stream, "int64"))
2109         type = g_variant_type_copy (G_VARIANT_TYPE_INT64);
2110
2111       else if (token_stream_consume (stream, "uint64"))
2112         type = g_variant_type_copy (G_VARIANT_TYPE_UINT64);
2113
2114       else if (token_stream_consume (stream, "double"))
2115         type = g_variant_type_copy (G_VARIANT_TYPE_DOUBLE);
2116
2117       else if (token_stream_consume (stream, "string"))
2118         type = g_variant_type_copy (G_VARIANT_TYPE_STRING);
2119
2120       else if (token_stream_consume (stream, "objectpath"))
2121         type = g_variant_type_copy (G_VARIANT_TYPE_OBJECT_PATH);
2122
2123       else if (token_stream_consume (stream, "signature"))
2124         type = g_variant_type_copy (G_VARIANT_TYPE_SIGNATURE);
2125
2126       else
2127         {
2128           token_stream_set_error (stream, error, TRUE, "unknown keyword");
2129           return NULL;
2130         }
2131     }
2132
2133   if ((child = parse (stream, app, error)) == NULL)
2134     {
2135       g_variant_type_free (type);
2136       return NULL;
2137     }
2138
2139   decl = g_slice_new (TypeDecl);
2140   decl->ast.class = &typedecl_class;
2141   decl->type = type;
2142   decl->child = child;
2143
2144   return (AST *) decl;
2145 }
2146
2147 static AST *
2148 parse (TokenStream  *stream,
2149        va_list      *app,
2150        GError      **error)
2151 {
2152   SourceRef source_ref;
2153   AST *result;
2154
2155   token_stream_prepare (stream);
2156   token_stream_start_ref (stream, &source_ref);
2157
2158   if (token_stream_peek (stream, '['))
2159     result = array_parse (stream, app, error);
2160
2161   else if (token_stream_peek (stream, '('))
2162     result = tuple_parse (stream, app, error);
2163
2164   else if (token_stream_peek (stream, '<'))
2165     result = variant_parse (stream, app, error);
2166
2167   else if (token_stream_peek (stream, '{'))
2168     result = dictionary_parse (stream, app, error);
2169
2170   else if (app && token_stream_peek (stream, '%'))
2171     result = positional_parse (stream, app, error);
2172
2173   else if (token_stream_consume (stream, "true"))
2174     result = boolean_new (TRUE);
2175
2176   else if (token_stream_consume (stream, "false"))
2177     result = boolean_new (FALSE);
2178
2179   else if (token_stream_peek (stream, 'n') ||
2180            token_stream_peek (stream, 'j'))
2181     result = maybe_parse (stream, app, error);
2182
2183   else if (token_stream_peek (stream, '@') ||
2184            token_stream_is_keyword (stream))
2185     result = typedecl_parse (stream, app, error);
2186
2187   else if (token_stream_is_numeric (stream))
2188     result = number_parse (stream, app, error);
2189
2190   else if (token_stream_peek (stream, '\'') ||
2191            token_stream_peek (stream, '"'))
2192     result = string_parse (stream, app, error);
2193
2194   else if (token_stream_peek2 (stream, 'b', '\'') ||
2195            token_stream_peek2 (stream, 'b', '"'))
2196     result = bytestring_parse (stream, app, error);
2197
2198   else
2199     {
2200       token_stream_set_error (stream, error, FALSE, "expected value");
2201       return NULL;
2202     }
2203
2204   if (result != NULL)
2205     {
2206       token_stream_end_ref (stream, &source_ref);
2207       result->source_ref = source_ref;
2208     }
2209
2210   return result;
2211 }
2212
2213 /**
2214  * g_variant_parse:
2215  * @type: a #GVariantType, or %NULL
2216  * @text: a string containing a GVariant in text form
2217  * @limit: a pointer to the end of @text, or %NULL
2218  * @endptr: a location to store the end pointer, or %NULL
2219  * @error: a pointer to a %NULL #GError pointer, or %NULL
2220  * @Returns: a reference to a #GVariant, or %NULL
2221  *
2222  * Parses a #GVariant from a text representation.
2223  *
2224  * A single #GVariant is parsed from the content of @text.
2225  *
2226  * The memory at @limit will never be accessed and the parser behaves as
2227  * if the character at @limit is the nul terminator.  This has the
2228  * effect of bounding @text.
2229  *
2230  * If @endptr is non-%NULL then @text is permitted to contain data
2231  * following the value that this function parses and @endptr will be
2232  * updated to point to the first character past the end of the text
2233  * parsed by this function.  If @endptr is %NULL and there is extra data
2234  * then an error is returned.
2235  *
2236  * If @type is non-%NULL then the value will be parsed to have that
2237  * type.  This may result in additional parse errors (in the case that
2238  * the parsed value doesn't fit the type) but may also result in fewer
2239  * errors (in the case that the type would have been ambiguous, such as
2240  * with empty arrays).
2241  *
2242  * In the event that the parsing is successful, the resulting #GVariant
2243  * is returned.
2244  *
2245  * In case of any error, %NULL will be returned.  If @error is non-%NULL
2246  * then it will be set to reflect the error that occured.
2247  *
2248  * Officially, the language understood by the parser is "any string
2249  * produced by g_variant_print()".
2250  **/
2251 GVariant *
2252 g_variant_parse (const GVariantType  *type,
2253                  const gchar         *text,
2254                  const gchar         *limit,
2255                  const gchar        **endptr,
2256                  GError             **error)
2257 {
2258   TokenStream stream = { 0, };
2259   GVariant *result = NULL;
2260   AST *ast;
2261
2262   g_return_val_if_fail (text != NULL, NULL);
2263   g_return_val_if_fail (text == limit || text != NULL, NULL);
2264
2265   stream.start = text;
2266   stream.stream = text;
2267   stream.end = limit;
2268
2269   if ((ast = parse (&stream, NULL, error)))
2270     {
2271       if (type == NULL)
2272         result = ast_resolve (ast, error);
2273       else
2274         result = ast_get_value (ast, type, error);
2275
2276       if (result != NULL)
2277         {
2278           g_variant_ref_sink (result);
2279
2280           if (endptr == NULL)
2281             {
2282               while (stream.stream != limit &&
2283                      g_ascii_isspace (*stream.stream))
2284                 stream.stream++;
2285
2286               if (stream.stream != limit && *stream.stream != '\0')
2287                 {
2288                   SourceRef ref = { stream.stream - text,
2289                                     stream.stream - text };
2290
2291                   parser_set_error (error, &ref, NULL,
2292                                     "expected end of input");
2293                   g_variant_unref (result);
2294
2295                   result = NULL;
2296                 }
2297             }
2298           else
2299             *endptr = stream.stream;
2300         }
2301
2302       ast_free (ast);
2303     }
2304
2305   return result;
2306 }
2307
2308 /**
2309  * g_variant_new_parsed_va:
2310  * @format: a text format #GVariant
2311  * @app: a pointer to a #va_list
2312  * @returns: a new, usually floating, #GVariant
2313  *
2314  * Parses @format and returns the result.
2315  *
2316  * This is the version of g_variant_new_parsed() intended to be used
2317  * from libraries.
2318  *
2319  * The return value will be floating if it was a newly created GVariant
2320  * instance.  In the case that @format simply specified the collection
2321  * of a #GVariant pointer (eg: @format was "%*") then the collected
2322  * #GVariant pointer will be returned unmodified, without adding any
2323  * additional references.
2324  *
2325  * In order to behave correctly in all cases it is necessary for the
2326  * calling function to g_variant_ref_sink() the return result before
2327  * returning control to the user that originally provided the pointer.
2328  * At this point, the caller will have their own full reference to the
2329  * result.  This can also be done by adding the result to a container,
2330  * or by passing it to another g_variant_new() call.
2331  **/
2332 GVariant *
2333 g_variant_new_parsed_va (const gchar *format,
2334                          va_list     *app)
2335 {
2336   TokenStream stream = { 0, };
2337   GVariant *result = NULL;
2338   GError *error = NULL;
2339   AST *ast;
2340
2341   g_return_val_if_fail (format != NULL, NULL);
2342   g_return_val_if_fail (app != NULL, NULL);
2343
2344   stream.start = format;
2345   stream.stream = format;
2346   stream.end = NULL;
2347
2348   if ((ast = parse (&stream, app, &error)))
2349     {
2350       result = ast_resolve (ast, &error);
2351       ast_free (ast);
2352     }
2353
2354   if (result == NULL)
2355     g_error ("g_variant_new_parsed: %s", error->message);
2356
2357   if (*stream.stream)
2358     g_error ("g_variant_new_parsed: trailing text after value");
2359
2360   return result;
2361 }
2362
2363 /**
2364  * g_variant_new_parsed:
2365  * @format: a text format #GVariant
2366  * @...: arguments as per @format
2367  * @returns: a new floating #GVariant instance
2368  *
2369  * Parses @format and returns the result.
2370  *
2371  * @format must be a text format #GVariant with one extention: at any
2372  * point that a value may appear in the text, a '%' character followed
2373  * by a GVariant format string (as per g_variant_new()) may appear.  In
2374  * that case, the same arguments are collected from the argument list as
2375  * g_variant_new() would have collected.
2376  *
2377  * Consider this simple example:
2378  *
2379  * <informalexample><programlisting>
2380  *  g_variant_new_parsed ("[('one', 1), ('two', %i), (%s, 3)]", 2, "three");
2381  * </programlisting></informalexample>
2382  *
2383  * In the example, the variable argument parameters are collected and
2384  * filled in as if they were part of the original string to produce the
2385  * result of <code>[('one', 1), ('two', 2), ('three', 3)]</code>.
2386  *
2387  * This function is intended only to be used with @format as a string
2388  * literal.  Any parse error is fatal to the calling process.  If you
2389  * want to parse data from untrusted sources, use g_variant_parse().
2390  *
2391  * You may not use this function to return, unmodified, a single
2392  * #GVariant pointer from the argument list.  ie: @format may not solely
2393  * be anything along the lines of "%*", "%?", "%r", or anything starting
2394  * with "%@".
2395  **/
2396 GVariant *
2397 g_variant_new_parsed (const gchar *format,
2398                       ...)
2399 {
2400   GVariant *result;
2401   va_list ap;
2402
2403   va_start (ap, format);
2404   result = g_variant_new_parsed_va (format, &ap);
2405   va_end (ap);
2406
2407   return result;
2408 }
2409
2410 /**
2411  * g_variant_builder_add_parsed:
2412  * @builder: a #GVariantBuilder
2413  * @format: a text format #GVariant
2414  * @...: arguments as per @format
2415  *
2416  * Adds to a #GVariantBuilder.
2417  *
2418  * This call is a convenience wrapper that is exactly equivalent to
2419  * calling g_variant_new_parsed() followed by
2420  * g_variant_builder_add_value().
2421  *
2422  * This function might be used as follows:
2423  *
2424  * <programlisting>
2425  * GVariant *
2426  * make_pointless_dictionary (void)
2427  * {
2428  *   GVariantBuilder *builder;
2429  *   int i;
2430  *
2431  *   builder = g_variant_builder_new (G_VARIANT_TYPE_ARRAY);
2432  *   g_variant_builder_add_parsed (builder, "{'width', <%i>}", 600);
2433  *   g_variant_builder_add_parsed (builder, "{'title', <%s>}", "foo");
2434  *   g_variant_builder_add_parsed (builder, "{'transparency', <0.5>}");
2435  *   return g_variant_builder_end (builder);
2436  * }
2437  * </programlisting>
2438  *
2439  * Since: 2.26
2440  **/
2441 void
2442 g_variant_builder_add_parsed (GVariantBuilder *builder,
2443                               const gchar     *format,
2444                               ...)
2445 {
2446   va_list ap;
2447
2448   va_start (ap, format);
2449   g_variant_builder_add_value (builder, g_variant_new_parsed_va (format, &ap));
2450   va_end (ap);
2451 }