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       g_free (tmp);
 675     }
 676
 677   return pattern;
 678 }
 679
 680 typedef struct
 681 {
 682   AST ast;
 683
 684   AST *child;
 685 } Maybe;
 686
 687 static gchar *
 688 maybe_get_pattern (AST     *ast,
 689                    GError **error)
 690 {
 691   Maybe *maybe = (Maybe *) ast;
 692
 693   if (maybe->child != NULL)
 694     {
 695       gchar *child_pattern;
 696       gchar *pattern;
 697
 698       child_pattern = ast_get_pattern (maybe->child, error);
 699
 700       if (child_pattern == NULL)
 701         return NULL;
 702
 703       pattern = g_strdup_printf ("m%s", child_pattern);
 704       g_free (child_pattern);
 705
 706       return pattern;
 707     }
 708
 709   return g_strdup ("m*");
 710 }
 711
 712 static GVariant *
 713 maybe_get_value (AST                 *ast,
 714                  const GVariantType  *type,
 715                  GError             **error)
 716 {
 717   Maybe *maybe = (Maybe *) ast;
 718   GVariant *value;
 719
 720   if (!g_variant_type_is_maybe (type))
 721     return ast_type_error (ast, type, error);
 722
 723   type = g_variant_type_element (type);
 724
 725   if (maybe->child)
 726     {
 727       value = ast_get_value (maybe->child, type, error);
 728
 729       if (value == NULL)
 730         return NULL;
 731     }
 732   else
 733     value = NULL;
 734
 735   return g_variant_new_maybe (type, value);
 736 }
 737
 738 static void
 739 maybe_free (AST *ast)
 740 {
 741   Maybe *maybe = (Maybe *) ast;
 742
 743   if (maybe->child != NULL)
 744     ast_free (maybe->child);
 745
 746   g_slice_free (Maybe, maybe);
 747 }
 748
 749 static AST *
 750 maybe_parse (TokenStream  *stream,
 751              va_list      *app,
 752              GError      **error)
 753 {
 754   static const ASTClass maybe_class = {
 755     maybe_get_pattern,
 756     maybe_get_value, NULL,
 757     maybe_free
 758   };
 759   AST *child = NULL;
 760   Maybe *maybe;
 761
 762   if (token_stream_consume (stream, "just"))
 763     {
 764       child = parse (stream, app, error);
 765       if (child == NULL)
 766         return NULL;
 767     }
 768
 769   else if (!token_stream_consume (stream, "nothing"))
 770     {
 771       token_stream_set_error (stream, error, TRUE, "unknown keyword");
 772       return NULL;
 773     }
 774
 775   maybe = g_slice_new (Maybe);
 776   maybe->ast.class = &maybe_class;
 777   maybe->child = child;
 778
 779   return (AST *) maybe;
 780 }
 781
 782 static GVariant *
 783 maybe_wrapper (AST                 *ast,
 784                const GVariantType  *type,
 785                GError             **error)
 786 {
 787   const GVariantType *t;
 788   GVariant *value;
 789   int depth;
 790
 791   for (depth = 0, t = type;
 792        g_variant_type_is_maybe (t);
 793        depth++, t = g_variant_type_element (t));
 794
 795   value = ast->class->get_base_value (ast, t, error);
 796
 797   if (value == NULL)
 798     return NULL;
 799
 800   while (depth--)
 801     value = g_variant_new_maybe (NULL, value);
 802
 803   return value;
 804 }
 805
 806 typedef struct
 807 {
 808   AST ast;
 809
 810   AST **children;
 811   gint n_children;
 812 } Array;
 813
 814 static gchar *
 815 array_get_pattern (AST     *ast,
 816                    GError **error)
 817 {
 818   Array *array = (Array *) ast;
 819   gchar *pattern;
 820   gchar *result;
 821
 822   if (array->n_children == 0)
 823     return g_strdup ("Ma*");
 824
 825   pattern = ast_array_get_pattern (array->children, array->n_children, error);
 826
 827   if (pattern == NULL)
 828     return NULL;
 829
 830   result = g_strdup_printf ("Ma%s", pattern);
 831   g_free (pattern);
 832
 833   return result;
 834 }
 835
 836 static GVariant *
 837 array_get_value (AST                 *ast,
 838                  const GVariantType  *type,
 839                  GError             **error)
 840 {
 841   Array *array = (Array *) ast;
 842   const GVariantType *childtype;
 843   GVariantBuilder builder;
 844   gint i;
 845
 846   if (!g_variant_type_is_array (type))
 847     return ast_type_error (ast, type, error);
 848
 849   g_variant_builder_init (&builder, type);
 850   childtype = g_variant_type_element (type);
 851
 852   for (i = 0; i < array->n_children; i++)
 853     {
 854       GVariant *child;
 855
 856       if (!(child = ast_get_value (array->children[i], childtype, error)))
 857         {
 858           g_variant_builder_clear (&builder);
 859           return NULL;
 860         }
 861
 862       g_variant_builder_add_value (&builder, child);
 863     }
 864
 865   return g_variant_builder_end (&builder);
 866 }
 867
 868 static void
 869 array_free (AST *ast)
 870 {
 871   Array *array = (Array *) ast;
 872
 873   ast_array_free (array->children, array->n_children);
 874   g_slice_free (Array, array);
 875 }
 876
 877 static AST *
 878 array_parse (TokenStream  *stream,
 879              va_list      *app,
 880              GError      **error)
 881 {
 882   static const ASTClass array_class = {
 883     array_get_pattern,
 884     maybe_wrapper, array_get_value,
 885     array_free
 886   };
 887   gboolean need_comma = FALSE;
 888   Array *array;
 889
 890   array = g_slice_new (Array);
 891   array->ast.class = &array_class;
 892   array->children = NULL;
 893   array->n_children = 0;
 894
 895   token_stream_assert (stream, "[");
 896   while (!token_stream_consume (stream, "]"))
 897     {
 898       AST *child;
 899
 900       if (need_comma &&
 901           !token_stream_require (stream, ",",
 902                                  " or `]' to follow array element",
 903                                  error))
 904         goto error;
 905
 906       child = parse (stream, app, error);
 907
 908       if (!child)
 909         goto error;
 910
 911       ast_array_append (&array->children, &array->n_children, child);
 912       need_comma = TRUE;
 913     }
 914
 915   return (AST *) array;
 916
 917  error:
 918   ast_array_free (array->children, array->n_children);
 919   g_slice_free (Array, array);
 920
 921   return NULL;
 922 }
 923
 924 typedef struct
 925 {
 926   AST ast;
 927
 928   AST **children;
 929   gint n_children;
 930 } Tuple;
 931
 932 static gchar *
 933 tuple_get_pattern (AST     *ast,
 934                    GError **error)
 935 {
 936   Tuple *tuple = (Tuple *) ast;
 937   gchar *result = NULL;
 938   gchar **parts;
 939   gint i;
 940
 941   parts = g_new (gchar *, tuple->n_children + 4);
 942   parts[tuple->n_children + 1] = (gchar *) ")";
 943   parts[tuple->n_children + 2] = NULL;
 944   parts[0] = (gchar *) "M(";
 945
 946   for (i = 0; i < tuple->n_children; i++)
 947     if (!(parts[i + 1] = ast_get_pattern (tuple->children[i], error)))
 948       break;
 949
 950   if (i == tuple->n_children)
 951     result = g_strjoinv ("", parts);
 952
 953   /* parts[0] should not be freed */
 954   while (i)
 955     g_free (parts[i--]);
 956   g_free (parts);
 957
 958   return result;
 959 }
 960
 961 static GVariant *
 962 tuple_get_value (AST                 *ast,
 963                  const GVariantType  *type,
 964                  GError             **error)
 965 {
 966   Tuple *tuple = (Tuple *) ast;
 967   const GVariantType *childtype;
 968   GVariantBuilder builder;
 969   gint i;
 970
 971   if (!g_variant_type_is_tuple (type))
 972     return ast_type_error (ast, type, error);
 973
 974   g_variant_builder_init (&builder, type);
 975   childtype = g_variant_type_first (type);
 976
 977   for (i = 0; i < tuple->n_children; i++)
 978     {
 979       GVariant *child;
 980
 981       if (!(child = ast_get_value (tuple->children[i], childtype, error)))
 982         {
 983           g_variant_builder_clear (&builder);
 984           return FALSE;
 985         }
 986
 987       g_variant_builder_add_value (&builder, child);
 988       childtype = g_variant_type_next (childtype);
 989     }
 990
 991   return g_variant_builder_end (&builder);
 992 }
 993
 994 static void
 995 tuple_free (AST *ast)
 996 {
 997   Tuple *tuple = (Tuple *) ast;
 998
 999   ast_array_free (tuple->children, tuple->n_children);
1000   g_slice_free (Tuple, tuple);
1001 }
1002
1003 static AST *
1004 tuple_parse (TokenStream  *stream,
1005              va_list      *app,
1006              GError      **error)
1007 {
1008   static const ASTClass tuple_class = {
1009     tuple_get_pattern,
1010     maybe_wrapper, tuple_get_value,
1011     tuple_free
1012   };
1013   gboolean need_comma = FALSE;
1014   gboolean first = TRUE;
1015   Tuple *tuple;
1016
1017   tuple = g_slice_new (Tuple);
1018   tuple->ast.class = &tuple_class;
1019   tuple->children = NULL;
1020   tuple->n_children = 0;
1021
1022   token_stream_assert (stream, "(");
1023   while (!token_stream_consume (stream, ")"))
1024     {
1025       AST *child;
1026
1027       if (need_comma &&
1028           !token_stream_require (stream, ",",
1029                                  " or `)' to follow tuple element",
1030                                  error))
1031         goto error;
1032
1033       child = parse (stream, app, error);
1034
1035       if (!child)
1036         goto error;
1037
1038       ast_array_append (&tuple->children, &tuple->n_children, child);
1039
1040       /* the first time, we absolutely require a comma, so grab it here
1041        * and leave need_comma = FALSE so that the code above doesn't
1042        * require a second comma.
1043        *
1044        * the second and remaining times, we set need_comma = TRUE.
1045        */
1046       if (first)
1047         {
1048           if (!token_stream_require (stream, ",",
1049                                      " after first tuple element", error))
1050             goto error;
1051
1052           first = FALSE;
1053         }
1054       else
1055         need_comma = TRUE;
1056     }
1057
1058   return (AST *) tuple;
1059
1060  error:
1061   ast_array_free (tuple->children, tuple->n_children);
1062   g_slice_free (Tuple, tuple);
1063
1064   return NULL;
1065 }
1066
1067 typedef struct
1068 {
1069   AST ast;
1070
1071   AST *value;
1072 } Variant;
1073
1074 static gchar *
1075 variant_get_pattern (AST     *ast,
1076                      GError **error)
1077 {
1078   return g_strdup ("Mv");
1079 }
1080
1081 static GVariant *
1082 variant_get_value (AST                 *ast,
1083                    const GVariantType  *type,
1084                    GError             **error)
1085 {
1086   Variant *variant = (Variant *) ast;
1087   GVariant *child;
1088
1089   g_assert (g_variant_type_equal (type, G_VARIANT_TYPE_VARIANT));
1090   child = ast_resolve (variant->value, error);
1091
1092   if (child == NULL)
1093     return NULL;
1094
1095   return g_variant_new_variant (child);
1096 }
1097
1098 static void
1099 variant_free (AST *ast)
1100 {
1101   Variant *variant = (Variant *) ast;
1102
1103   ast_free (variant->value);
1104   g_slice_free (Variant, variant);
1105 }
1106
1107 static AST *
1108 variant_parse (TokenStream  *stream,
1109                va_list      *app,
1110                GError      **error)
1111 {
1112   static const ASTClass variant_class = {
1113     variant_get_pattern,
1114     maybe_wrapper, variant_get_value,
1115     variant_free
1116   };
1117   Variant *variant;
1118   AST *value;
1119
1120   token_stream_assert (stream, "<");
1121   value = parse (stream, app, error);
1122
1123   if (!value)
1124     return NULL;
1125
1126   if (!token_stream_require (stream, ">", " to follow variant value", error))
1127     {
1128       ast_free (value);
1129       return NULL;
1130     }
1131
1132   variant = g_slice_new (Variant);
1133   variant->ast.class = &variant_class;
1134   variant->value = value;
1135
1136   return (AST *) variant;
1137 }
1138
1139 typedef struct
1140 {
1141   AST ast;
1142
1143   AST **keys;
1144   AST **values;
1145   gint n_children;
1146 } Dictionary;
1147
1148 static gchar *
1149 dictionary_get_pattern (AST     *ast,
1150                         GError **error)
1151 {
1152   Dictionary *dict = (Dictionary *) ast;
1153   gchar *value_pattern;
1154   gchar *key_pattern;
1155   gchar key_char;
1156   gchar *result;
1157
1158   if (dict->n_children == 0)
1159     return g_strdup ("Ma{**}");
1160
1161   key_pattern = ast_array_get_pattern (dict->keys,
1162                                        abs (dict->n_children),
1163                                        error);
1164
1165   if (key_pattern == NULL)
1166     return NULL;
1167
1168   /* we can not have maybe keys */
1169   if (key_pattern[0] == 'M')
1170     key_char = key_pattern[1];
1171   else
1172     key_char = key_pattern[0];
1173
1174   g_free (key_pattern);
1175
1176   /* the basic types,
1177    * plus undetermined number type and undetermined string type.
1178    */
1179   if (!strchr ("bynqiuxthdsogNS", key_char))
1180     {
1181       ast_set_error (ast, error, NULL,
1182                      "dictionary keys must have basic types");
1183       return NULL;
1184     }
1185
1186   value_pattern = ast_get_pattern (dict->values[0], error);
1187
1188   if (value_pattern == NULL)
1189     return NULL;
1190
1191   result = g_strdup_printf ("M%s{%c%s}",
1192                             dict->n_children > 0 ? "a" : "",
1193                             key_char, value_pattern);
1194   g_free (value_pattern);
1195
1196   return result;
1197 }
1198
1199 static GVariant *
1200 dictionary_get_value (AST                 *ast,
1201                       const GVariantType  *type,
1202                       GError             **error)
1203 {
1204   Dictionary *dict = (Dictionary *) ast;
1205
1206   if (dict->n_children == -1)
1207     {
1208       const GVariantType *subtype;
1209       GVariantBuilder builder;
1210       GVariant *subvalue;
1211
1212       if (!g_variant_type_is_dict_entry (type))
1213         return ast_type_error (ast, type, error);
1214
1215       g_variant_builder_init (&builder, type);
1216
1217       subtype = g_variant_type_key (type);
1218       if (!(subvalue = ast_get_value (dict->keys[0], subtype, error)))
1219         {
1220           g_variant_builder_clear (&builder);
1221           return FALSE;
1222         }
1223       g_variant_builder_add_value (&builder, subvalue);
1224
1225       subtype = g_variant_type_value (type);
1226       if (!(subvalue = ast_get_value (dict->values[0], subtype, error)))
1227         {
1228           g_variant_builder_clear (&builder);
1229           return FALSE;
1230         }
1231       g_variant_builder_add_value (&builder, subvalue);
1232
1233       return g_variant_builder_end (&builder);
1234     }
1235   else
1236     {
1237       const GVariantType *entry, *key, *val;
1238       GVariantBuilder builder;
1239       gint i;
1240
1241       if (!g_variant_type_is_subtype_of (type, G_VARIANT_TYPE_DICTIONARY))
1242         return ast_type_error (ast, type, error);
1243
1244       entry = g_variant_type_element (type);
1245       key = g_variant_type_key (entry);
1246       val = g_variant_type_value (entry);
1247
1248       g_variant_builder_init (&builder, type);
1249
1250       for (i = 0; i < dict->n_children; i++)
1251         {
1252           GVariant *subvalue;
1253
1254           g_variant_builder_open (&builder, entry);
1255
1256           if (!(subvalue = ast_get_value (dict->keys[i], key, error)))
1257             {
1258               g_variant_builder_clear (&builder);
1259               return FALSE;
1260             }
1261           g_variant_builder_add_value (&builder, subvalue);
1262
1263           if (!(subvalue = ast_get_value (dict->values[i], val, error)))
1264             {
1265               g_variant_builder_clear (&builder);
1266               return FALSE;
1267             }
1268           g_variant_builder_add_value (&builder, subvalue);
1269           g_variant_builder_close (&builder);
1270         }
1271
1272       return g_variant_builder_end (&builder);
1273     }
1274 }
1275
1276 static void
1277 dictionary_free (AST *ast)
1278 {
1279   Dictionary *dict = (Dictionary *) ast;
1280   gint n_children;
1281
1282   if (dict->n_children > -1)
1283     n_children = dict->n_children;
1284   else
1285     n_children = 1;
1286
1287   ast_array_free (dict->keys, n_children);
1288   ast_array_free (dict->values, n_children);
1289   g_slice_free (Dictionary, dict);
1290 }
1291
1292 static AST *
1293 dictionary_parse (TokenStream  *stream,
1294                   va_list      *app,
1295                   GError      **error)
1296 {
1297   static const ASTClass dictionary_class = {
1298     dictionary_get_pattern,
1299     maybe_wrapper, dictionary_get_value,
1300     dictionary_free
1301   };
1302   gint n_keys, n_values;
1303   gboolean only_one;
1304   Dictionary *dict;
1305   AST *first;
1306
1307   dict = g_slice_new (Dictionary);
1308   dict->ast.class = &dictionary_class;
1309   dict->keys = NULL;
1310   dict->values = NULL;
1311   n_keys = n_values = 0;
1312
1313   token_stream_assert (stream, "{");
1314
1315   if (token_stream_consume (stream, "}"))
1316     {
1317       dict->n_children = 0;
1318       return (AST *) dict;
1319     }
1320
1321   if ((first = parse (stream, app, error)) == NULL)
1322     goto error;
1323
1324   ast_array_append (&dict->keys, &n_keys, first);
1325
1326   only_one = token_stream_consume (stream, ",");
1327   if (!only_one &&
1328       !token_stream_require (stream, ":",
1329                              " or `,' to follow dictionary entry key",
1330                              error))
1331     goto error;
1332
1333   if ((first = parse (stream, app, error)) == NULL)
1334     goto error;
1335
1336   ast_array_append (&dict->values, &n_values, first);
1337
1338   if (only_one)
1339     {
1340       if (!token_stream_require (stream, "}", " at end of dictionary entry",
1341                                  error))
1342         goto error;
1343
1344       g_assert (n_keys == 1 && n_values == 1);
1345       dict->n_children = -1;
1346
1347       return (AST *) dict;
1348     }
1349
1350   while (!token_stream_consume (stream, "}"))
1351     {
1352       AST *child;
1353
1354       if (!token_stream_require (stream, ",",
1355                                  " or `}' to follow dictionary entry", error))
1356         goto error;
1357
1358       child = parse (stream, app, error);
1359
1360       if (!child)
1361         goto error;
1362
1363       ast_array_append (&dict->keys, &n_keys, child);
1364
1365       if (!token_stream_require (stream, ":",
1366                                  " to follow dictionary entry key", error))
1367         goto error;
1368
1369       child = parse (stream, app, error);
1370
1371       if (!child)
1372         goto error;
1373
1374       ast_array_append (&dict->values, &n_values, child);
1375     }
1376
1377   g_assert (n_keys == n_values);
1378   dict->n_children = n_keys;
1379
1380   return (AST *) dict;
1381
1382  error:
1383   ast_array_free (dict->keys, n_keys);
1384   ast_array_free (dict->values, n_values);
1385   g_slice_free (Dictionary, dict);
1386
1387   return NULL;
1388 }
1389
1390 typedef struct
1391 {
1392   AST ast;
1393   gchar *string;
1394 } String;
1395
1396 static gchar *
1397 string_get_pattern (AST     *ast,
1398                     GError **error)
1399 {
1400   return g_strdup ("MS");
1401 }
1402
1403 static GVariant *
1404 string_get_value (AST                 *ast,
1405                   const GVariantType  *type,
1406                   GError             **error)
1407 {
1408   String *string = (String *) ast;
1409
1410   if (g_variant_type_equal (type, G_VARIANT_TYPE_STRING))
1411     return g_variant_new_string (string->string);
1412
1413   else if (g_variant_type_equal (type, G_VARIANT_TYPE_OBJECT_PATH))
1414     {
1415       if (!g_variant_is_object_path (string->string))
1416         {
1417           ast_set_error (ast, error, NULL, "not a valid object path");
1418           return NULL;
1419         }
1420
1421       return g_variant_new_object_path (string->string);
1422     }
1423
1424   else if (g_variant_type_equal (type, G_VARIANT_TYPE_SIGNATURE))
1425     {
1426       if (!g_variant_is_signature (string->string))
1427         {
1428           ast_set_error (ast, error, NULL, "not a valid signature");
1429           return NULL;
1430         }
1431
1432       return g_variant_new_signature (string->string);
1433     }
1434
1435   else
1436     return ast_type_error (ast, type, error);
1437 }
1438
1439 static void
1440 string_free (AST *ast)
1441 {
1442   String *string = (String *) ast;
1443
1444   g_free (string->string);
1445   g_slice_free (String, string);
1446 }
1447
1448 static gboolean
1449 unicode_unescape (const gchar  *src,
1450                   gint         *src_ofs,
1451                   gchar        *dest,
1452                   gint         *dest_ofs,
1453                   gint          length,
1454                   SourceRef    *ref,
1455                   GError      **error)
1456 {
1457   gchar buffer[9];
1458   guint64 value;
1459   gchar *end;
1460
1461   (*src_ofs)++;
1462
1463   g_assert (length < sizeof (buffer));
1464   strncpy (buffer, src + *src_ofs, length);
1465   buffer[length] = '\0';
1466
1467   value = g_ascii_strtoull (buffer, &end, 0x10);
1468
1469   if (value == 0 || end != buffer + length)
1470     {
1471       parser_set_error (error, ref, NULL,
1472                         "invalid %d-character unicode escape", length);
1473       return FALSE;
1474     }
1475
1476   g_assert (value <= G_MAXUINT32);
1477
1478   *dest_ofs += g_unichar_to_utf8 (value, dest + *dest_ofs);
1479   *src_ofs += length;
1480
1481   return TRUE;
1482 }
1483
1484 static AST *
1485 string_parse (TokenStream  *stream,
1486               va_list      *app,
1487               GError      **error)
1488 {
1489   static const ASTClass string_class = {
1490     string_get_pattern,
1491     maybe_wrapper, string_get_value,
1492     string_free
1493   };
1494   String *string;
1495   SourceRef ref;
1496   gchar *token;
1497   gsize length;
1498   gchar quote;
1499   gchar *str;
1500   gint i, j;
1501
1502   token_stream_start_ref (stream, &ref);
1503   token = token_stream_get (stream);
1504   token_stream_end_ref (stream, &ref);
1505   length = strlen (token);
1506   quote = token[0];
1507
1508   str = g_malloc (length);
1509   g_assert (quote == '"' || quote == '\'');
1510   j = 0;
1511   i = 1;
1512   while (token[i] != quote)
1513     switch (token[i])
1514       {
1515       case '\0':
1516         parser_set_error (error, &ref, NULL,
1517                           "unterminated string constant");
1518         g_free (token);
1519         g_free (str);
1520         return NULL;
1521
1522       case '\\':
1523         switch (token[++i])
1524           {
1525           case '\0':
1526             parser_set_error (error, &ref, NULL,
1527                               "unterminated string constant");
1528             g_free (token);
1529             g_free (str);
1530             return NULL;
1531
1532           case 'u':
1533             if (!unicode_unescape (token, &i, str, &j, 4, &ref, error))
1534               {
1535                 g_free (token);
1536                 g_free (str);
1537                 return NULL;
1538               }
1539             continue;
1540
1541           case 'U':
1542             if (!unicode_unescape (token, &i, str, &j, 8, &ref, error))
1543               {
1544                 g_free (token);
1545                 g_free (str);
1546                 return NULL;
1547               }
1548             continue;
1549
1550           case 'a': str[j++] = '\a'; i++; continue;
1551           case 'b': str[j++] = '\b'; i++; continue;
1552           case 'f': str[j++] = '\f'; i++; continue;
1553           case 'n': str[j++] = '\n'; i++; continue;
1554           case 'r': str[j++] = '\r'; i++; continue;
1555           case 't': str[j++] = '\t'; i++; continue;
1556           case 'v': str[j++] = '\v'; i++; continue;
1557           case '\n': i++; continue;
1558           }
1559
1560       default:
1561         str[j++] = token[i++];
1562       }
1563   str[j++] = '\0';
1564   g_free (token);
1565
1566   string = g_slice_new (String);
1567   string->ast.class = &string_class;
1568   string->string = str;
1569
1570   token_stream_next (stream);
1571
1572   return (AST *) string;
1573 }
1574
1575 typedef struct
1576 {
1577   AST ast;
1578   gchar *string;
1579 } ByteString;
1580
1581 static gchar *
1582 bytestring_get_pattern (AST     *ast,
1583                         GError **error)
1584 {
1585   return g_strdup ("May");
1586 }
1587
1588 static GVariant *
1589 bytestring_get_value (AST                 *ast,
1590                       const GVariantType  *type,
1591                       GError             **error)
1592 {
1593   ByteString *string = (ByteString *) ast;
1594
1595   g_assert (g_variant_type_equal (type, G_VARIANT_TYPE_BYTESTRING));
1596
1597   return g_variant_new_bytestring (string->string);
1598 }
1599
1600 static void
1601 bytestring_free (AST *ast)
1602 {
1603   ByteString *string = (ByteString *) ast;
1604
1605   g_free (string->string);
1606   g_slice_free (ByteString, string);
1607 }
1608
1609 static AST *
1610 bytestring_parse (TokenStream  *stream,
1611                   va_list      *app,
1612                   GError      **error)
1613 {
1614   static const ASTClass bytestring_class = {
1615     bytestring_get_pattern,
1616     maybe_wrapper, bytestring_get_value,
1617     bytestring_free
1618   };
1619   ByteString *string;
1620   SourceRef ref;
1621   gchar *token;
1622   gsize length;
1623   gchar quote;
1624   gchar *str;
1625   gint i, j;
1626
1627   token_stream_start_ref (stream, &ref);
1628   token = token_stream_get (stream);
1629   token_stream_end_ref (stream, &ref);
1630   g_assert (token[0] == 'b');
1631   length = strlen (token);
1632   quote = token[1];
1633
1634   str = g_malloc (length);
1635   g_assert (quote == '"' || quote == '\'');
1636   j = 0;
1637   i = 2;
1638   while (token[i] != quote)
1639     switch (token[i])
1640       {
1641       case '\0':
1642         parser_set_error (error, &ref, NULL,
1643                           "unterminated string constant");
1644         g_free (token);
1645         return NULL;
1646
1647       case '\\':
1648         switch (token[++i])
1649           {
1650           case '\0':
1651             parser_set_error (error, &ref, NULL,
1652                               "unterminated string constant");
1653             g_free (token);
1654             return NULL;
1655
1656           case '0': case '1': case '2': case '3':
1657           case '4': case '5': case '6': case '7':
1658             {
1659               /* up to 3 characters */
1660               guchar val = token[i++] - '0';
1661
1662               if ('0' <= token[i] && token[i] < '8')
1663                 val = (val << 3) | (token[i++] - '0');
1664
1665               if ('0' <= token[i] && token[i] < '8')
1666                 val = (val << 3) | (token[i++] - '0');
1667
1668               str[j++] = val;
1669             }
1670             continue;
1671
1672           case 'a': str[j++] = '\a'; i++; continue;
1673           case 'b': str[j++] = '\b'; i++; continue;
1674           case 'f': str[j++] = '\f'; i++; continue;
1675           case 'n': str[j++] = '\n'; i++; continue;
1676           case 'r': str[j++] = '\r'; i++; continue;
1677           case 't': str[j++] = '\t'; i++; continue;
1678           case 'v': str[j++] = '\v'; i++; continue;
1679           case '\n': i++; continue;
1680           }
1681
1682       default:
1683         str[j++] = token[i++];
1684       }
1685   str[j++] = '\0';
1686   g_free (token);
1687
1688   string = g_slice_new (ByteString);
1689   string->ast.class = &bytestring_class;
1690   string->string = str;
1691
1692   token_stream_next (stream);
1693
1694   return (AST *) string;
1695 }
1696
1697 typedef struct
1698 {
1699   AST ast;
1700
1701   gchar *token;
1702 } Number;
1703
1704 static gchar *
1705 number_get_pattern (AST     *ast,
1706                     GError **error)
1707 {
1708   Number *number = (Number *) ast;
1709
1710   if (strchr (number->token, '.') ||
1711       (!g_str_has_prefix (number->token, "0x") &&
1712        strchr (number->token, 'e')))
1713     return g_strdup ("Md");
1714
1715   return g_strdup ("MN");
1716 }
1717
1718 static GVariant *
1719 number_overflow (AST                 *ast,
1720                  const GVariantType  *type,
1721                  GError             **error)
1722 {
1723   ast_set_error (ast, error, NULL, "number out of range for type `%c'",
1724                  g_variant_type_peek_string (type)[0]);
1725   return NULL;
1726 }
1727
1728 static GVariant *
1729 number_get_value (AST                 *ast,
1730                   const GVariantType  *type,
1731                   GError             **error)
1732 {
1733   Number *number = (Number *) ast;
1734   const gchar *token;
1735   gboolean negative;
1736   gboolean floating;
1737   guint64 abs_val;
1738   gdouble dbl_val;
1739   gchar *end;
1740
1741   token = number->token;
1742
1743   if (g_variant_type_equal (type, G_VARIANT_TYPE_DOUBLE))
1744     {
1745       floating = TRUE;
1746
1747       errno = 0;
1748       dbl_val = g_ascii_strtod (token, &end);
1749       if (dbl_val != 0.0 && errno == ERANGE)
1750         {
1751           ast_set_error (ast, error, NULL, "number too big for any type");
1752           return NULL;
1753         }
1754
1755       /* silence uninitialised warnings... */
1756       negative = FALSE;
1757       abs_val = 0;
1758     }
1759   else
1760     {
1761       floating = FALSE;
1762       negative = token[0] == '-';
1763       if (token[0] == '-')
1764         token++;
1765
1766       errno = 0;
1767       abs_val = g_ascii_strtoull (token, &end, 0);
1768       if (abs_val == G_MAXUINT64 && errno == ERANGE)
1769         {
1770           ast_set_error (ast, error, NULL, "integer too big for any type");
1771           return NULL;
1772         }
1773
1774       if (abs_val == 0)
1775         negative = FALSE;
1776
1777       /* silence uninitialised warning... */
1778       dbl_val = 0.0;
1779     }
1780
1781   if (*end != '\0')
1782     {
1783       SourceRef ref;
1784
1785       ref = ast->source_ref;
1786       ref.start += end - number->token;
1787       ref.end = ref.start + 1;
1788
1789       parser_set_error (error, &ref, NULL,
1790                         "invalid character in number");
1791       return NULL;
1792      }
1793
1794   if (floating)
1795     return g_variant_new_double (dbl_val);
1796
1797   switch (*g_variant_type_peek_string (type))
1798     {
1799     case 'y':
1800       if (negative || abs_val > G_MAXUINT8)
1801         return number_overflow (ast, type, error);
1802       return g_variant_new_byte (abs_val);
1803
1804     case 'n':
1805       if (abs_val - negative > G_MAXINT16)
1806         return number_overflow (ast, type, error);
1807       return g_variant_new_int16 (negative ? -abs_val : abs_val);
1808
1809     case 'q':
1810       if (negative || abs_val > G_MAXUINT16)
1811         return number_overflow (ast, type, error);
1812       return g_variant_new_uint16 (negative ? -abs_val : abs_val);
1813
1814     case 'i':
1815       if (abs_val - negative > G_MAXINT32)
1816         return number_overflow (ast, type, error);
1817       return g_variant_new_int32 (negative ? -abs_val : abs_val);
1818
1819     case 'u':
1820       if (negative || abs_val > G_MAXUINT32)
1821         return number_overflow (ast, type, error);
1822       return g_variant_new_uint32 (negative ? -abs_val : abs_val);
1823
1824     case 'x':
1825       if (abs_val - negative > G_MAXINT64)
1826         return number_overflow (ast, type, error);
1827       return g_variant_new_int64 (negative ? -abs_val : abs_val);
1828
1829     case 't':
1830       if (negative)
1831         return number_overflow (ast, type, error);
1832       return g_variant_new_uint64 (negative ? -abs_val : abs_val);
1833
1834     case 'h':
1835       if (abs_val - negative > G_MAXINT32)
1836         return number_overflow (ast, type, error);
1837       return g_variant_new_handle (negative ? -abs_val : abs_val);
1838
1839     default:
1840       return ast_type_error (ast, type, error);
1841     }
1842 }
1843
1844 static void
1845 number_free (AST *ast)
1846 {
1847   Number *number = (Number *) ast;
1848
1849   g_free (number->token);
1850   g_slice_free (Number, number);
1851 }
1852
1853 static AST *
1854 number_parse (TokenStream  *stream,
1855               va_list      *app,
1856               GError      **error)
1857 {
1858   static const ASTClass number_class = {
1859     number_get_pattern,
1860     maybe_wrapper, number_get_value,
1861     number_free
1862   };
1863   Number *number;
1864
1865   number = g_slice_new (Number);
1866   number->ast.class = &number_class;
1867   number->token = token_stream_get (stream);
1868   token_stream_next (stream);
1869
1870   return (AST *) number;
1871 }
1872
1873 typedef struct
1874 {
1875   AST ast;
1876   gboolean value;
1877 } Boolean;
1878
1879 static gchar *
1880 boolean_get_pattern (AST     *ast,
1881                      GError **error)
1882 {
1883   return g_strdup ("Mb");
1884 }
1885
1886 static GVariant *
1887 boolean_get_value (AST                 *ast,
1888                    const GVariantType  *type,
1889                    GError             **error)
1890 {
1891   Boolean *boolean = (Boolean *) ast;
1892
1893   if (!g_variant_type_equal (type, G_VARIANT_TYPE_BOOLEAN))
1894     return ast_type_error (ast, type, error);
1895
1896   return g_variant_new_boolean (boolean->value);
1897 }
1898
1899 static void
1900 boolean_free (AST *ast)
1901 {
1902   Boolean *boolean = (Boolean *) ast;
1903
1904   g_slice_free (Boolean, boolean);
1905 }
1906
1907 static AST *
1908 boolean_new (gboolean value)
1909 {
1910   static const ASTClass boolean_class = {
1911     boolean_get_pattern,
1912     maybe_wrapper, boolean_get_value,
1913     boolean_free
1914   };
1915   Boolean *boolean;
1916
1917   boolean = g_slice_new (Boolean);
1918   boolean->ast.class = &boolean_class;
1919   boolean->value = value;
1920
1921   return (AST *) boolean;
1922 }
1923
1924 typedef struct
1925 {
1926   AST ast;
1927
1928   GVariant *value;
1929 } Positional;
1930
1931 static gchar *
1932 positional_get_pattern (AST     *ast,
1933                         GError **error)
1934 {
1935   Positional *positional = (Positional *) ast;
1936
1937   return g_strdup (g_variant_get_type_string (positional->value));
1938 }
1939
1940 static GVariant *
1941 positional_get_value (AST                 *ast,
1942                       const GVariantType  *type,
1943                       GError             **error)
1944 {
1945   Positional *positional = (Positional *) ast;
1946   GVariant *value;
1947
1948   g_assert (positional->value != NULL);
1949
1950   if G_UNLIKELY (!g_variant_is_of_type (positional->value, type))
1951     return ast_type_error (ast, type, error);
1952
1953   /* NOTE: if _get is called more than once then
1954    * things get messed up with respect to floating refs.
1955    *
1956    * fortunately, this function should only ever get called once.
1957    */
1958   g_assert (positional->value != NULL);
1959   value = positional->value;
1960   positional->value = NULL;
1961
1962   return value;
1963 }
1964
1965 static void
1966 positional_free (AST *ast)
1967 {
1968   Positional *positional = (Positional *) ast;
1969
1970   /* if positional->value is set, just leave it.
1971    * memory management doesn't matter in case of programmer error.
1972    */
1973   g_slice_free (Positional, positional);
1974 }
1975
1976 static AST *
1977 positional_parse (TokenStream  *stream,
1978                   va_list      *app,
1979                   GError      **error)
1980 {
1981   static const ASTClass positional_class = {
1982     positional_get_pattern,
1983     positional_get_value, NULL,
1984     positional_free
1985   };
1986   Positional *positional;
1987   const gchar *endptr;
1988   gchar *token;
1989
1990   token = token_stream_get (stream);
1991   g_assert (token[0] == '%');
1992
1993   positional = g_slice_new (Positional);
1994   positional->ast.class = &positional_class;
1995   positional->value = g_variant_new_va (token + 1, &endptr, app);
1996
1997   if (*endptr || positional->value == NULL)
1998     {
1999       token_stream_set_error (stream, error, TRUE,
2000                               "invalid GVariant format string");
2001       /* memory management doesn't matter in case of programmer error. */
2002       return NULL;
2003     }
2004
2005   token_stream_next (stream);
2006   g_free (token);
2007
2008   return (AST *) positional;
2009 }
2010
2011 typedef struct
2012 {
2013   AST ast;
2014
2015   GVariantType *type;
2016   AST *child;
2017 } TypeDecl;
2018
2019 static gchar *
2020 typedecl_get_pattern (AST     *ast,
2021                       GError **error)
2022 {
2023   TypeDecl *decl = (TypeDecl *) ast;
2024
2025   return g_variant_type_dup_string (decl->type);
2026 }
2027
2028 static GVariant *
2029 typedecl_get_value (AST                 *ast,
2030                     const GVariantType  *type,
2031                     GError             **error)
2032 {
2033   TypeDecl *decl = (TypeDecl *) ast;
2034
2035   return ast_get_value (decl->child, type, error);
2036 }
2037
2038 static void
2039 typedecl_free (AST *ast)
2040 {
2041   TypeDecl *decl = (TypeDecl *) ast;
2042
2043   ast_free (decl->child);
2044   g_variant_type_free (decl->type);
2045   g_slice_free (TypeDecl, decl);
2046 }
2047
2048 static AST *
2049 typedecl_parse (TokenStream  *stream,
2050                 va_list      *app,
2051                 GError      **error)
2052 {
2053   static const ASTClass typedecl_class = {
2054     typedecl_get_pattern,
2055     typedecl_get_value, NULL,
2056     typedecl_free
2057   };
2058   GVariantType *type;
2059   TypeDecl *decl;
2060   AST *child;
2061
2062   if (token_stream_peek (stream, '@'))
2063     {
2064       gchar *token;
2065
2066       token = token_stream_get (stream);
2067
2068       if (!g_variant_type_string_is_valid (token + 1))
2069         {
2070           token_stream_set_error (stream, error, TRUE,
2071                                   "invalid type declaration");
2072           g_free (token);
2073
2074           return NULL;
2075         }
2076
2077       type = g_variant_type_new (token + 1);
2078
2079       if (!g_variant_type_is_definite (type))
2080         {
2081           token_stream_set_error (stream, error, TRUE,
2082                                   "type declarations must be definite");
2083           g_variant_type_free (type);
2084           g_free (token);
2085
2086           return NULL;
2087         }
2088
2089       token_stream_next (stream);
2090       g_free (token);
2091     }
2092   else
2093     {
2094       if (token_stream_consume (stream, "boolean"))
2095         type = g_variant_type_copy (G_VARIANT_TYPE_BOOLEAN);
2096
2097       else if (token_stream_consume (stream, "byte"))
2098         type = g_variant_type_copy (G_VARIANT_TYPE_BYTE);
2099
2100       else if (token_stream_consume (stream, "int16"))
2101         type = g_variant_type_copy (G_VARIANT_TYPE_INT16);
2102
2103       else if (token_stream_consume (stream, "uint16"))
2104         type = g_variant_type_copy (G_VARIANT_TYPE_UINT16);
2105
2106       else if (token_stream_consume (stream, "int32"))
2107         type = g_variant_type_copy (G_VARIANT_TYPE_INT32);
2108
2109       else if (token_stream_consume (stream, "handle"))
2110         type = g_variant_type_copy (G_VARIANT_TYPE_HANDLE);
2111
2112       else if (token_stream_consume (stream, "uint32"))
2113         type = g_variant_type_copy (G_VARIANT_TYPE_UINT32);
2114
2115       else if (token_stream_consume (stream, "int64"))
2116         type = g_variant_type_copy (G_VARIANT_TYPE_INT64);
2117
2118       else if (token_stream_consume (stream, "uint64"))
2119         type = g_variant_type_copy (G_VARIANT_TYPE_UINT64);
2120
2121       else if (token_stream_consume (stream, "double"))
2122         type = g_variant_type_copy (G_VARIANT_TYPE_DOUBLE);
2123
2124       else if (token_stream_consume (stream, "string"))
2125         type = g_variant_type_copy (G_VARIANT_TYPE_STRING);
2126
2127       else if (token_stream_consume (stream, "objectpath"))
2128         type = g_variant_type_copy (G_VARIANT_TYPE_OBJECT_PATH);
2129
2130       else if (token_stream_consume (stream, "signature"))
2131         type = g_variant_type_copy (G_VARIANT_TYPE_SIGNATURE);
2132
2133       else
2134         {
2135           token_stream_set_error (stream, error, TRUE, "unknown keyword");
2136           return NULL;
2137         }
2138     }
2139
2140   if ((child = parse (stream, app, error)) == NULL)
2141     {
2142       g_variant_type_free (type);
2143       return NULL;
2144     }
2145
2146   decl = g_slice_new (TypeDecl);
2147   decl->ast.class = &typedecl_class;
2148   decl->type = type;
2149   decl->child = child;
2150
2151   return (AST *) decl;
2152 }
2153
2154 static AST *
2155 parse (TokenStream  *stream,
2156        va_list      *app,
2157        GError      **error)
2158 {
2159   SourceRef source_ref;
2160   AST *result;
2161
2162   token_stream_prepare (stream);
2163   token_stream_start_ref (stream, &source_ref);
2164
2165   if (token_stream_peek (stream, '['))
2166     result = array_parse (stream, app, error);
2167
2168   else if (token_stream_peek (stream, '('))
2169     result = tuple_parse (stream, app, error);
2170
2171   else if (token_stream_peek (stream, '<'))
2172     result = variant_parse (stream, app, error);
2173
2174   else if (token_stream_peek (stream, '{'))
2175     result = dictionary_parse (stream, app, error);
2176
2177   else if (app && token_stream_peek (stream, '%'))
2178     result = positional_parse (stream, app, error);
2179
2180   else if (token_stream_consume (stream, "true"))
2181     result = boolean_new (TRUE);
2182
2183   else if (token_stream_consume (stream, "false"))
2184     result = boolean_new (FALSE);
2185
2186   else if (token_stream_peek (stream, 'n') ||
2187            token_stream_peek (stream, 'j'))
2188     result = maybe_parse (stream, app, error);
2189
2190   else if (token_stream_peek (stream, '@') ||
2191            token_stream_is_keyword (stream))
2192     result = typedecl_parse (stream, app, error);
2193
2194   else if (token_stream_is_numeric (stream))
2195     result = number_parse (stream, app, error);
2196
2197   else if (token_stream_peek (stream, '\'') ||
2198            token_stream_peek (stream, '"'))
2199     result = string_parse (stream, app, error);
2200
2201   else if (token_stream_peek2 (stream, 'b', '\'') ||
2202            token_stream_peek2 (stream, 'b', '"'))
2203     result = bytestring_parse (stream, app, error);
2204
2205   else
2206     {
2207       token_stream_set_error (stream, error, FALSE, "expected value");
2208       return NULL;
2209     }
2210
2211   if (result != NULL)
2212     {
2213       token_stream_end_ref (stream, &source_ref);
2214       result->source_ref = source_ref;
2215     }
2216
2217   return result;
2218 }
2219
2220 /**
2221  * g_variant_parse:
2222  * @type: a #GVariantType, or %NULL
2223  * @text: a string containing a GVariant in text form
2224  * @limit: a pointer to the end of @text, or %NULL
2225  * @endptr: a location to store the end pointer, or %NULL
2226  * @error: a pointer to a %NULL #GError pointer, or %NULL
2227  * @Returns: a reference to a #GVariant, or %NULL
2228  *
2229  * Parses a #GVariant from a text representation.
2230  *
2231  * A single #GVariant is parsed from the content of @text.
2232  *
2233  * The memory at @limit will never be accessed and the parser behaves as
2234  * if the character at @limit is the nul terminator.  This has the
2235  * effect of bounding @text.
2236  *
2237  * If @endptr is non-%NULL then @text is permitted to contain data
2238  * following the value that this function parses and @endptr will be
2239  * updated to point to the first character past the end of the text
2240  * parsed by this function.  If @endptr is %NULL and there is extra data
2241  * then an error is returned.
2242  *
2243  * If @type is non-%NULL then the value will be parsed to have that
2244  * type.  This may result in additional parse errors (in the case that
2245  * the parsed value doesn't fit the type) but may also result in fewer
2246  * errors (in the case that the type would have been ambiguous, such as
2247  * with empty arrays).
2248  *
2249  * In the event that the parsing is successful, the resulting #GVariant
2250  * is returned.
2251  *
2252  * In case of any error, %NULL will be returned.  If @error is non-%NULL
2253  * then it will be set to reflect the error that occured.
2254  *
2255  * Officially, the language understood by the parser is "any string
2256  * produced by g_variant_print()".
2257  **/
2258 GVariant *
2259 g_variant_parse (const GVariantType  *type,
2260                  const gchar         *text,
2261                  const gchar         *limit,
2262                  const gchar        **endptr,
2263                  GError             **error)
2264 {
2265   TokenStream stream = { 0, };
2266   GVariant *result = NULL;
2267   AST *ast;
2268
2269   g_return_val_if_fail (text != NULL, NULL);
2270   g_return_val_if_fail (text == limit || text != NULL, NULL);
2271
2272   stream.start = text;
2273   stream.stream = text;
2274   stream.end = limit;
2275
2276   if ((ast = parse (&stream, NULL, error)))
2277     {
2278       if (type == NULL)
2279         result = ast_resolve (ast, error);
2280       else
2281         result = ast_get_value (ast, type, error);
2282
2283       if (result != NULL)
2284         {
2285           g_variant_ref_sink (result);
2286
2287           if (endptr == NULL)
2288             {
2289               while (stream.stream != limit &&
2290                      g_ascii_isspace (*stream.stream))
2291                 stream.stream++;
2292
2293               if (stream.stream != limit && *stream.stream != '\0')
2294                 {
2295                   SourceRef ref = { stream.stream - text,
2296                                     stream.stream - text };
2297
2298                   parser_set_error (error, &ref, NULL,
2299                                     "expected end of input");
2300                   g_variant_unref (result);
2301
2302                   result = NULL;
2303                 }
2304             }
2305           else
2306             *endptr = stream.stream;
2307         }
2308
2309       ast_free (ast);
2310     }
2311
2312   return result;
2313 }
2314
2315 /**
2316  * g_variant_new_parsed_va:
2317  * @format: a text format #GVariant
2318  * @app: a pointer to a #va_list
2319  * @returns: a new, usually floating, #GVariant
2320  *
2321  * Parses @format and returns the result.
2322  *
2323  * This is the version of g_variant_new_parsed() intended to be used
2324  * from libraries.
2325  *
2326  * The return value will be floating if it was a newly created GVariant
2327  * instance.  In the case that @format simply specified the collection
2328  * of a #GVariant pointer (eg: @format was "%*") then the collected
2329  * #GVariant pointer will be returned unmodified, without adding any
2330  * additional references.
2331  *
2332  * In order to behave correctly in all cases it is necessary for the
2333  * calling function to g_variant_ref_sink() the return result before
2334  * returning control to the user that originally provided the pointer.
2335  * At this point, the caller will have their own full reference to the
2336  * result.  This can also be done by adding the result to a container,
2337  * or by passing it to another g_variant_new() call.
2338  **/
2339 GVariant *
2340 g_variant_new_parsed_va (const gchar *format,
2341                          va_list     *app)
2342 {
2343   TokenStream stream = { 0, };
2344   GVariant *result = NULL;
2345   GError *error = NULL;
2346   AST *ast;
2347
2348   g_return_val_if_fail (format != NULL, NULL);
2349   g_return_val_if_fail (app != NULL, NULL);
2350
2351   stream.start = format;
2352   stream.stream = format;
2353   stream.end = NULL;
2354
2355   if ((ast = parse (&stream, app, &error)))
2356     {
2357       result = ast_resolve (ast, &error);
2358       ast_free (ast);
2359     }
2360
2361   if (result == NULL)
2362     g_error ("g_variant_new_parsed: %s", error->message);
2363
2364   if (*stream.stream)
2365     g_error ("g_variant_new_parsed: trailing text after value");
2366
2367   return result;
2368 }
2369
2370 /**
2371  * g_variant_new_parsed:
2372  * @format: a text format #GVariant
2373  * @...: arguments as per @format
2374  * @returns: a new floating #GVariant instance
2375  *
2376  * Parses @format and returns the result.
2377  *
2378  * @format must be a text format #GVariant with one extention: at any
2379  * point that a value may appear in the text, a '%' character followed
2380  * by a GVariant format string (as per g_variant_new()) may appear.  In
2381  * that case, the same arguments are collected from the argument list as
2382  * g_variant_new() would have collected.
2383  *
2384  * Consider this simple example:
2385  *
2386  * <informalexample><programlisting>
2387  *  g_variant_new_parsed ("[('one', 1), ('two', %i), (%s, 3)]", 2, "three");
2388  * </programlisting></informalexample>
2389  *
2390  * In the example, the variable argument parameters are collected and
2391  * filled in as if they were part of the original string to produce the
2392  * result of <code>[('one', 1), ('two', 2), ('three', 3)]</code>.
2393  *
2394  * This function is intended only to be used with @format as a string
2395  * literal.  Any parse error is fatal to the calling process.  If you
2396  * want to parse data from untrusted sources, use g_variant_parse().
2397  *
2398  * You may not use this function to return, unmodified, a single
2399  * #GVariant pointer from the argument list.  ie: @format may not solely
2400  * be anything along the lines of "%*", "%?", "%r", or anything starting
2401  * with "%@".
2402  **/
2403 GVariant *
2404 g_variant_new_parsed (const gchar *format,
2405                       ...)
2406 {
2407   GVariant *result;
2408   va_list ap;
2409
2410   va_start (ap, format);
2411   result = g_variant_new_parsed_va (format, &ap);
2412   va_end (ap);
2413
2414   return result;
2415 }
2416
2417 /**
2418  * g_variant_builder_add_parsed:
2419  * @builder: a #GVariantBuilder
2420  * @format: a text format #GVariant
2421  * @...: arguments as per @format
2422  *
2423  * Adds to a #GVariantBuilder.
2424  *
2425  * This call is a convenience wrapper that is exactly equivalent to
2426  * calling g_variant_new_parsed() followed by
2427  * g_variant_builder_add_value().
2428  *
2429  * This function might be used as follows:
2430  *
2431  * <programlisting>
2432  * GVariant *
2433  * make_pointless_dictionary (void)
2434  * {
2435  *   GVariantBuilder *builder;
2436  *   int i;
2437  *
2438  *   builder = g_variant_builder_new (G_VARIANT_TYPE_ARRAY);
2439  *   g_variant_builder_add_parsed (builder, "{'width', <%i>}", 600);
2440  *   g_variant_builder_add_parsed (builder, "{'title', <%s>}", "foo");
2441  *   g_variant_builder_add_parsed (builder, "{'transparency', <0.5>}");
2442  *   return g_variant_builder_end (builder);
2443  * }
2444  * </programlisting>
2445  *
2446  * Since: 2.26
2447  **/
2448 void
2449 g_variant_builder_add_parsed (GVariantBuilder *builder,
2450                               const gchar     *format,
2451                               ...)
2452 {
2453   va_list ap;
2454
2455   va_start (ap, format);
2456   g_variant_builder_add_value (builder, g_variant_new_parsed_va (format, &ap));
2457   va_end (ap);
2458 }