libkern/c++/OSUnserializeXML.y

   1 /*
   2  * Copyright (c) 1999-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /*
  30  * HISTORY
  31  *
  32  * OSUnserializeXML.y created by rsulack on Tue Oct 12 1999
  33  */
  34
  35 // parser for unserializing OSContainer objects serialized to XML
  36 //
  37 // to build :
  38 //      bison -p OSUnserializeXML OSUnserializeXML.y
  39 //      head -50 OSUnserializeXML.y > OSUnserializeXML.cpp
  40 //      sed -e "s/#include <stdio.h>//" < OSUnserializeXML.tab.c >> OSUnserializeXML.cpp
  41 //
  42 //      when changing code check in both OSUnserializeXML.y and OSUnserializeXML.cpp
  43 //
  44 //
  45 //
  46 //
  47 //
  48 //               DO NOT EDIT OSUnserializeXML.cpp!
  49 //
  50 //                      this means you!
  51 //
  52 //
  53 //
  54 //
  55 //
  56 //
  57
  58
  59 %pure_parser
  60
  61 %{
  62 #include <string.h>
  63 #include <libkern/c++/OSMetaClass.h>
  64 #include <libkern/c++/OSContainers.h>
  65 #include <libkern/c++/OSLib.h>
  66
  67 #define MAX_OBJECTS     65535
  68
  69 #define YYSTYPE object_t *
  70 #define YYPARSE_PARAM   state
  71 #define YYLEX_PARAM     (parser_state_t *)state
  72
  73 // this is the internal struct used to hold objects on parser stack
  74 // it represents objects both before and after they have been created
  75 typedef struct object {
  76         struct object   *next;
  77         struct object   *free;
  78         struct object   *elements;
  79         OSObject        *object;
  80         OSSymbol        *key;                   // for dictionary
  81         int             size;
  82         void            *data;                  // for data
  83         char            *string;                // for string & symbol
  84         long long       number;                 // for number
  85         int             idref;
  86 } object_t;
  87
  88 // this code is reentrant, this structure contains all
  89 // state information for the parsing of a single buffer
  90 typedef struct parser_state {
  91         const char      *parseBuffer;           // start of text to be parsed
  92         int             parseBufferIndex;       // current index into text
  93         int             lineNumber;             // current line number
  94         object_t        *objects;               // internal objects in use
  95         object_t        *freeObjects;           // internal objects that are free
  96         OSDictionary    *tags;                  // used to remember "ID" tags
  97         OSString        **errorString;          // parse error with line
  98         OSObject        *parsedObject;          // resultant object of parsed text
  99         int             parsedObjectCount;
 100 } parser_state_t;
 101
 102 #define STATE           ((parser_state_t *)state)
 103
 104 #undef yyerror
 105 #define yyerror(s)      OSUnserializeerror(STATE, (s))
 106 static int              OSUnserializeerror(parser_state_t *state, const char *s);
 107
 108 static int              yylex(YYSTYPE *lvalp, parser_state_t *state);
 109
 110 static object_t         *newObject(parser_state_t *state);
 111 static void             freeObject(parser_state_t *state, object_t *o);
 112 static void             rememberObject(parser_state_t *state, int tag, OSObject *o);
 113 static object_t         *retrieveObject(parser_state_t *state, int tag);
 114 static void             cleanupObjects(parser_state_t *state);
 115
 116 static object_t         *buildDictionary(parser_state_t *state, object_t *o);
 117 static object_t         *buildArray(parser_state_t *state, object_t *o);
 118 static object_t         *buildSet(parser_state_t *state, object_t *o);
 119 static object_t         *buildString(parser_state_t *state, object_t *o);
 120 static object_t         *buildSymbol(parser_state_t *state, object_t *o);
 121 static object_t         *buildData(parser_state_t *state, object_t *o);
 122 static object_t         *buildNumber(parser_state_t *state, object_t *o);
 123 static object_t         *buildBoolean(parser_state_t *state, object_t *o);
 124
 125 extern "C" {
 126 extern void             *kern_os_malloc(size_t size);
 127 extern void             *kern_os_realloc(void * addr, size_t size);
 128 extern void             kern_os_free(void * addr);
 129
 130 } /* extern "C" */
 131
 132 #define malloc(s) kern_os_malloc(s)
 133 #define realloc(a, s) kern_os_realloc(a, s)
 134 #define free(a) kern_os_free((void *)a)
 135
 136 %}
 137 %token ARRAY
 138 %token BOOLEAN
 139 %token DATA
 140 %token DICTIONARY
 141 %token IDREF
 142 %token KEY
 143 %token NUMBER
 144 %token SET
 145 %token STRING
 146 %token SYNTAX_ERROR
 147 %% /* Grammar rules and actions follow */
 148
 149 input:    /* empty */           { yyerror("unexpected end of buffer");
 150                                   YYERROR;
 151                                 }
 152         | object                { STATE->parsedObject = $1->object;
 153                                   $1->object = 0;
 154                                   freeObject(STATE, $1);
 155                                   YYACCEPT;
 156                                 }
 157         | SYNTAX_ERROR          { yyerror("syntax error");
 158                                   YYERROR;
 159                                 }
 160         ;
 161
 162 object:   dict                  { $$ = buildDictionary(STATE, $1);
 163
 164                                   if (!yyval->object) {
 165                                     yyerror("buildDictionary");
 166                                     YYERROR;
 167                                   }
 168                                   STATE->parsedObjectCount++;
 169                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 170                                     yyerror("maximum object count");
 171                                     YYERROR;
 172                                   }
 173                                 }
 174         | array                 { $$ = buildArray(STATE, $1);
 175
 176                                   if (!yyval->object) {
 177                                     yyerror("buildArray");
 178                                     YYERROR;
 179                                   }
 180                                   STATE->parsedObjectCount++;
 181                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 182                                     yyerror("maximum object count");
 183                                     YYERROR;
 184                                   }
 185                                 }
 186         | set                   { $$ = buildSet(STATE, $1);
 187
 188                                   if (!yyval->object) {
 189                                     yyerror("buildSet");
 190                                     YYERROR;
 191                                   }
 192                                   STATE->parsedObjectCount++;
 193                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 194                                     yyerror("maximum object count");
 195                                     YYERROR;
 196                                   }
 197                                 }
 198         | string                { $$ = buildString(STATE, $1);
 199
 200                                   if (!yyval->object) {
 201                                     yyerror("buildString");
 202                                     YYERROR;
 203                                   }
 204                                   STATE->parsedObjectCount++;
 205                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 206                                     yyerror("maximum object count");
 207                                     YYERROR;
 208                                   }
 209                                 }
 210         | data                  { $$ = buildData(STATE, $1);
 211
 212                                   if (!yyval->object) {
 213                                     yyerror("buildData");
 214                                     YYERROR;
 215                                   }
 216                                   STATE->parsedObjectCount++;
 217                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 218                                     yyerror("maximum object count");
 219                                     YYERROR;
 220                                   }
 221                                 }
 222         | number                { $$ = buildNumber(STATE, $1);
 223
 224                                   if (!yyval->object) {
 225                                     yyerror("buildNumber");
 226                                     YYERROR;
 227                                   }
 228                                   STATE->parsedObjectCount++;
 229                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 230                                     yyerror("maximum object count");
 231                                     YYERROR;
 232                                   }
 233                                 }
 234         | boolean               { $$ = buildBoolean(STATE, $1);
 235
 236                                   if (!yyval->object) {
 237                                     yyerror("buildBoolean");
 238                                     YYERROR;
 239                                   }
 240                                   STATE->parsedObjectCount++;
 241                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 242                                     yyerror("maximum object count");
 243                                     YYERROR;
 244                                   }
 245                                 }
 246         | idref                 { $$ = retrieveObject(STATE, $1->idref);
 247                                   if ($$) {
 248                                     $$->object->retain();
 249                                   } else {
 250                                     yyerror("forward reference detected");
 251                                     YYERROR;
 252                                   }
 253                                   freeObject(STATE, $1);
 254
 255                                   STATE->parsedObjectCount++;
 256                                   if (STATE->parsedObjectCount > MAX_OBJECTS) {
 257                                     yyerror("maximum object count");
 258                                     YYERROR;
 259                                   }
 260                                 }
 261         ;
 262
 263 //------------------------------------------------------------------------------
 264
 265 dict:     '{' '}'               { $$ = $1;
 266                                   $$->elements = NULL;
 267                                 }
 268         | '{' pairs '}'         { $$ = $1;
 269                                   $$->elements = $2;
 270                                 }
 271         | DICTIONARY
 272         ;
 273
 274 pairs:    pair
 275         | pairs pair            { $$ = $2;
 276                                   $$->next = $1;
 277
 278                                   object_t *o;
 279                                   o = $$->next;
 280                                   while (o) {
 281                                     if (o->key == $$->key) {
 282                                       yyerror("duplicate dictionary key");
 283                                       YYERROR;
 284                                     }
 285                                     o = o->next;
 286                                   }
 287                                 }
 288         ;
 289
 290 pair:     key object            { $$ = $1;
 291                                   $$->key = (OSSymbol *)$$->object;
 292                                   $$->object = $2->object;
 293                                   $$->next = NULL;
 294                                   $2->object = 0;
 295                                   freeObject(STATE, $2);
 296                                 }
 297         ;
 298
 299 key:      KEY                   { $$ = buildSymbol(STATE, $1);
 300
 301 //                                STATE->parsedObjectCount++;
 302 //                                if (STATE->parsedObjectCount > MAX_OBJECTS) {
 303 //                                  yyerror("maximum object count");
 304 //                                  YYERROR;
 305 //                                }
 306                                 }
 307         ;
 308
 309 //------------------------------------------------------------------------------
 310
 311 array:    '(' ')'               { $$ = $1;
 312                                   $$->elements = NULL;
 313                                 }
 314         | '(' elements ')'      { $$ = $1;
 315                                   $$->elements = $2;
 316                                 }
 317         | ARRAY
 318         ;
 319
 320 set:      '[' ']'               { $$ = $1;
 321                                   $$->elements = NULL;
 322                                 }
 323         | '[' elements ']'      { $$ = $1;
 324                                   $$->elements = $2;
 325                                 }
 326         | SET
 327         ;
 328
 329 elements: object                { $$ = $1;
 330                                   $$->next = NULL;
 331                                 }
 332         | elements object       { $$ = $2;
 333                                   $$->next = $1;
 334                                 }
 335         ;
 336
 337 //------------------------------------------------------------------------------
 338
 339 boolean:  BOOLEAN
 340         ;
 341
 342 data:     DATA
 343         ;
 344
 345 idref:    IDREF
 346         ;
 347
 348 number:   NUMBER
 349         ;
 350
 351 string:   STRING
 352         ;
 353
 354 %%
 355
 356 int
 357 OSUnserializeerror(parser_state_t * state, const char *s)  /* Called by yyparse on errors */
 358 {
 359     if (state->errorString) {
 360         char tempString[128];
 361         snprintf(tempString, 128, "OSUnserializeXML: %s near line %d\n", s, state->lineNumber);
 362         *(state->errorString) = OSString::withCString(tempString);
 363     }
 364
 365     return 0;
 366 }
 367
 368 #define TAG_MAX_LENGTH          32
 369 #define TAG_MAX_ATTRIBUTES      32
 370 #define TAG_BAD                 0
 371 #define TAG_START               1
 372 #define TAG_END                 2
 373 #define TAG_EMPTY               3
 374 #define TAG_IGNORE              4
 375
 376 #define currentChar()   (state->parseBuffer[state->parseBufferIndex])
 377 #define nextChar()      (state->parseBuffer[++state->parseBufferIndex])
 378 #define prevChar()      (state->parseBuffer[state->parseBufferIndex - 1])
 379
 380 #define isSpace(c)      ((c) == ' ' || (c) == '\t')
 381 #define isAlpha(c)      (((c) >= 'A' && (c) <= 'Z') || ((c) >= 'a' && (c) <= 'z'))
 382 #define isDigit(c)      ((c) >= '0' && (c) <= '9')
 383 #define isAlphaDigit(c) ((c) >= 'a' && (c) <= 'f')
 384 #define isHexDigit(c)   (isDigit(c) || isAlphaDigit(c))
 385 #define isAlphaNumeric(c) (isAlpha(c) || isDigit(c) || ((c) == '-'))
 386
 387 static int
 388 getTag(parser_state_t *state,
 389        char tag[TAG_MAX_LENGTH],
 390        int *attributeCount,
 391        char attributes[TAG_MAX_ATTRIBUTES][TAG_MAX_LENGTH],
 392        char values[TAG_MAX_ATTRIBUTES][TAG_MAX_LENGTH] )
 393 {
 394         int length = 0;
 395         int c = currentChar();
 396         int tagType = TAG_START;
 397
 398         *attributeCount = 0;
 399
 400         if (c != '<') return TAG_BAD;
 401         c = nextChar();         // skip '<'
 402
 403
 404         // <!TAG   declarations     >
 405         // <!--     comments      -->
 406         if (c == '!') {
 407             c = nextChar();
 408             bool isComment = (c == '-') && ((c = nextChar()) != 0) && (c == '-');
 409             if (!isComment && !isAlpha(c)) return TAG_BAD;   // <!1, <!-A, <!eos
 410
 411             while (c && (c = nextChar()) != 0) {
 412                 if (c == '\n') state->lineNumber++;
 413                 if (isComment) {
 414                     if (c != '-') continue;
 415                     c = nextChar();
 416                     if (c != '-') continue;
 417                     c = nextChar();
 418                 }
 419                 if (c == '>') {
 420                     (void)nextChar();
 421                     return TAG_IGNORE;
 422                 }
 423                 if (isComment) break;
 424             }
 425             return TAG_BAD;
 426         }
 427
 428         else
 429
 430         // <? Processing Instructions  ?>
 431         if (c == '?') {
 432             while ((c = nextChar()) != 0) {
 433                 if (c == '\n') state->lineNumber++;
 434                 if (c != '?') continue;
 435                 c = nextChar();
 436                 if (!c) return TAG_IGNORE;
 437                 if (c == '>') {
 438                     (void)nextChar();
 439                     return TAG_IGNORE;
 440                 }
 441             }
 442             return TAG_BAD;
 443         }
 444
 445         else
 446
 447         // </ end tag >
 448         if (c == '/') {
 449                 c = nextChar();         // skip '/'
 450                 tagType = TAG_END;
 451         }
 452         if (!isAlpha(c)) return TAG_BAD;
 453
 454         /* find end of tag while copying it */
 455         while (isAlphaNumeric(c)) {
 456                 tag[length++] = c;
 457                 c = nextChar();
 458                 if (length >= (TAG_MAX_LENGTH - 1)) return TAG_BAD;
 459         }
 460
 461         tag[length] = 0;
 462
 463 //      printf("tag %s, type %d\n", tag, tagType);
 464
 465         // look for attributes of the form attribute = "value" ...
 466         while ((c != '>') && (c != '/')) {
 467                 while (isSpace(c)) c = nextChar();
 468
 469                 length = 0;
 470                 while (isAlphaNumeric(c)) {
 471                         attributes[*attributeCount][length++] = c;
 472                         if (length >= (TAG_MAX_LENGTH - 1)) return TAG_BAD;
 473                         c = nextChar();
 474                 }
 475                 attributes[*attributeCount][length] = 0;
 476
 477                 while (isSpace(c)) c = nextChar();
 478
 479                 if (c != '=') return TAG_BAD;
 480                 c = nextChar();
 481
 482                 while (isSpace(c)) c = nextChar();
 483
 484                 if (c != '"') return TAG_BAD;
 485                 c = nextChar();
 486                 length = 0;
 487                 while (c != '"') {
 488                         values[*attributeCount][length++] = c;
 489                         if (length >= (TAG_MAX_LENGTH - 1)) return TAG_BAD;
 490                         c = nextChar();
 491                         if (!c) return TAG_BAD;
 492                 }
 493                 values[*attributeCount][length] = 0;
 494
 495                 c = nextChar(); // skip closing quote
 496
 497 //              printf("        attribute '%s' = '%s', nextchar = '%c'\n",
 498 //                     attributes[*attributeCount], values[*attributeCount], c);
 499
 500                 (*attributeCount)++;
 501                 if (*attributeCount >= TAG_MAX_ATTRIBUTES) return TAG_BAD;
 502         }
 503
 504         if (c == '/') {
 505                 c = nextChar();         // skip '/'
 506                 tagType = TAG_EMPTY;
 507         }
 508         if (c != '>') return TAG_BAD;
 509         c = nextChar();         // skip '>'
 510
 511         return tagType;
 512 }
 513
 514 static char *
 515 getString(parser_state_t *state)
 516 {
 517         int c = currentChar();
 518         int start, length, i, j;
 519         char * tempString;
 520
 521         start = state->parseBufferIndex;
 522         /* find end of string */
 523
 524         while (c != 0) {
 525                 if (c == '\n') state->lineNumber++;
 526                 if (c == '<') {
 527                         break;
 528                 }
 529                 c = nextChar();
 530         }
 531
 532         if (c != '<') return 0;
 533
 534         length = state->parseBufferIndex - start;
 535
 536         /* copy to null terminated buffer */
 537         tempString = (char *)malloc(length + 1);
 538         if (tempString == 0) {
 539                 printf("OSUnserializeXML: can't alloc temp memory\n");
 540                 goto error;
 541         }
 542
 543         // copy out string in tempString
 544         // "&amp;" -> '&', "&lt;" -> '<', "&gt;" -> '>'
 545
 546         i = j = 0;
 547         while (i < length) {
 548                 c = state->parseBuffer[start + i++];
 549                 if (c != '&') {
 550                         tempString[j++] = c;
 551                 } else {
 552                         if ((i+3) > length) goto error;
 553                         c = state->parseBuffer[start + i++];
 554                         if (c == 'l') {
 555                                 if (state->parseBuffer[start + i++] != 't') goto error;
 556                                 if (state->parseBuffer[start + i++] != ';') goto error;
 557                                 tempString[j++] = '<';
 558                                 continue;
 559                         }
 560                         if (c == 'g') {
 561                                 if (state->parseBuffer[start + i++] != 't') goto error;
 562                                 if (state->parseBuffer[start + i++] != ';') goto error;
 563                                 tempString[j++] = '>';
 564                                 continue;
 565                         }
 566                         if ((i+3) > length) goto error;
 567                         if (c == 'a') {
 568                                 if (state->parseBuffer[start + i++] != 'm') goto error;
 569                                 if (state->parseBuffer[start + i++] != 'p') goto error;
 570                                 if (state->parseBuffer[start + i++] != ';') goto error;
 571                                 tempString[j++] = '&';
 572                                 continue;
 573                         }
 574                         goto error;
 575                 }
 576         }
 577         tempString[j] = 0;
 578
 579 //      printf("string %s\n", tempString);
 580
 581         return tempString;
 582
 583 error:
 584         if (tempString) free(tempString);
 585         return 0;
 586 }
 587
 588 static long long
 589 getNumber(parser_state_t *state)
 590 {
 591         unsigned long long n = 0;
 592         int base = 10;
 593         bool negate = false;
 594         int c = currentChar();
 595
 596         if (c == '0') {
 597                 c = nextChar();
 598                 if (c == 'x') {
 599                         base = 16;
 600                         c = nextChar();
 601                 }
 602         }
 603         if (base == 10) {
 604                 if (c == '-') {
 605                         negate = true;
 606                         c = nextChar();
 607                 }
 608                 while(isDigit(c)) {
 609                         n = (n * base + c - '0');
 610                         c = nextChar();
 611                 }
 612                 if (negate) {
 613                         n = (unsigned long long)((long long)n * (long long)-1);
 614                 }
 615         } else {
 616                 while(isHexDigit(c)) {
 617                         if (isDigit(c)) {
 618                                 n = (n * base + c - '0');
 619                         } else {
 620                                 n = (n * base + 0xa + c - 'a');
 621                         }
 622                         c = nextChar();
 623                 }
 624         }
 625 //      printf("number 0x%x\n", (unsigned long)n);
 626         return n;
 627 }
 628
 629 // taken from CFXMLParsing/CFPropertyList.c
 630
 631 static const signed char __CFPLDataDecodeTable[128] = {
 632     /* 000 */ -1, -1, -1, -1, -1, -1, -1, -1,
 633     /* 010 */ -1, -1, -1, -1, -1, -1, -1, -1,
 634     /* 020 */ -1, -1, -1, -1, -1, -1, -1, -1,
 635     /* 030 */ -1, -1, -1, -1, -1, -1, -1, -1,
 636     /* ' ' */ -1, -1, -1, -1, -1, -1, -1, -1,
 637     /* '(' */ -1, -1, -1, 62, -1, -1, -1, 63,
 638     /* '0' */ 52, 53, 54, 55, 56, 57, 58, 59,
 639     /* '8' */ 60, 61, -1, -1, -1,  0, -1, -1,
 640     /* '@' */ -1,  0,  1,  2,  3,  4,  5,  6,
 641     /* 'H' */  7,  8,  9, 10, 11, 12, 13, 14,
 642     /* 'P' */ 15, 16, 17, 18, 19, 20, 21, 22,
 643     /* 'X' */ 23, 24, 25, -1, -1, -1, -1, -1,
 644     /* '`' */ -1, 26, 27, 28, 29, 30, 31, 32,
 645     /* 'h' */ 33, 34, 35, 36, 37, 38, 39, 40,
 646     /* 'p' */ 41, 42, 43, 44, 45, 46, 47, 48,
 647     /* 'x' */ 49, 50, 51, -1, -1, -1, -1, -1
 648 };
 649
 650 #define DATA_ALLOC_SIZE 4096
 651
 652 static void *
 653 getCFEncodedData(parser_state_t *state, unsigned int *size)
 654 {
 655     int numeq = 0, acc = 0, cntr = 0;
 656     int tmpbufpos = 0, tmpbuflen = 0;
 657     unsigned char *tmpbuf = (unsigned char *)malloc(DATA_ALLOC_SIZE);
 658
 659     int c = currentChar();
 660     *size = 0;
 661
 662     while (c != '<') {
 663         c &= 0x7f;
 664         if (c == 0) {
 665                 free(tmpbuf);
 666                 return 0;
 667         }
 668         if (c == '=') numeq++; else numeq = 0;
 669         if (c == '\n') state->lineNumber++;
 670         if (__CFPLDataDecodeTable[c] < 0) {
 671             c = nextChar();
 672             continue;
 673         }
 674         cntr++;
 675         acc <<= 6;
 676         acc += __CFPLDataDecodeTable[c];
 677         if (0 == (cntr & 0x3)) {
 678             if (tmpbuflen <= tmpbufpos + 2) {
 679                 tmpbuflen += DATA_ALLOC_SIZE;
 680                 tmpbuf = (unsigned char *)realloc(tmpbuf, tmpbuflen);
 681             }
 682             tmpbuf[tmpbufpos++] = (acc >> 16) & 0xff;
 683             if (numeq < 2)
 684                 tmpbuf[tmpbufpos++] = (acc >> 8) & 0xff;
 685             if (numeq < 1)
 686                 tmpbuf[tmpbufpos++] = acc & 0xff;
 687         }
 688         c = nextChar();
 689     }
 690     *size = tmpbufpos;
 691     if (*size == 0) {
 692         free(tmpbuf);
 693         return 0;
 694     }
 695     return tmpbuf;
 696 }
 697
 698 static void *
 699 getHexData(parser_state_t *state, unsigned int *size)
 700 {
 701     int c;
 702     unsigned char *d, *start, *lastStart;
 703
 704     start = lastStart = d = (unsigned char *)malloc(DATA_ALLOC_SIZE);
 705     c = currentChar();
 706
 707     while (c != '<') {
 708
 709         if (isSpace(c)) while ((c = nextChar()) != 0 && isSpace(c)) {};
 710         if (c == '\n') {
 711             state->lineNumber++;
 712             c = nextChar();
 713             continue;
 714         }
 715
 716         // get high nibble
 717         if (isDigit(c)) {
 718             *d = (c - '0') << 4;
 719         } else if (isAlphaDigit(c)) {
 720             *d =  (0xa + (c - 'a')) << 4;
 721         } else {
 722             goto error;
 723         }
 724
 725         // get low nibble
 726         c = nextChar();
 727         if (isDigit(c)) {
 728             *d |= c - '0';
 729         } else if (isAlphaDigit(c)) {
 730             *d |= 0xa + (c - 'a');
 731         } else {
 732             goto error;
 733         }
 734
 735         d++;
 736         if ((d - lastStart) >= DATA_ALLOC_SIZE) {
 737             int oldsize = d - start;
 738             start = (unsigned char *)realloc(start, oldsize + DATA_ALLOC_SIZE);
 739             d = lastStart = start + oldsize;
 740         }
 741         c = nextChar();
 742     }
 743
 744     *size = d - start;
 745     return start;
 746
 747  error:
 748
 749     *size = 0;
 750     free(start);
 751     return 0;
 752 }
 753
 754 static int
 755 yylex(YYSTYPE *lvalp, parser_state_t *state)
 756 {
 757         int c, i;
 758         int tagType;
 759         char tag[TAG_MAX_LENGTH];
 760         int attributeCount;
 761         char attributes[TAG_MAX_ATTRIBUTES][TAG_MAX_LENGTH];
 762         char values[TAG_MAX_ATTRIBUTES][TAG_MAX_LENGTH];
 763         object_t *object;
 764
 765  top:
 766         c = currentChar();
 767
 768         /* skip white space  */
 769         if (isSpace(c)) while ((c = nextChar()) != 0 && isSpace(c)) {};
 770
 771         /* keep track of line number, don't return \n's */
 772         if (c == '\n') {
 773                 STATE->lineNumber++;
 774                 (void)nextChar();
 775                 goto top;
 776         }
 777
 778         // end of the buffer?
 779         if (!c) return 0;
 780
 781         tagType = getTag(STATE, tag, &attributeCount, attributes, values);
 782         if (tagType == TAG_BAD) return SYNTAX_ERROR;
 783         if (tagType == TAG_IGNORE) goto top;
 784
 785         // handle allocation and check for "ID" and "IDREF" tags up front
 786         *lvalp = object = newObject(STATE);
 787         object->idref = -1;
 788         for (i=0; i < attributeCount; i++) {
 789             if (attributes[i][0] == 'I' && attributes[i][1] == 'D') {
 790                 // check for idref's, note: we ignore the tag, for
 791                 // this to work correctly, all idrefs must be unique
 792                 // across the whole serialization
 793                 if (attributes[i][2] == 'R' && attributes[i][3] == 'E' &&
 794                     attributes[i][4] == 'F' && !attributes[i][5]) {
 795                     if (tagType != TAG_EMPTY) return SYNTAX_ERROR;
 796                     object->idref = strtol(values[i], NULL, 0);
 797                     return IDREF;
 798                 }
 799                 // check for id's
 800                 if (!attributes[i][2]) {
 801                     object->idref = strtol(values[i], NULL, 0);
 802                 } else {
 803                     return SYNTAX_ERROR;
 804                 }
 805             }
 806         }
 807
 808         switch (*tag) {
 809         case 'a':
 810                 if (!strcmp(tag, "array")) {
 811                         if (tagType == TAG_EMPTY) {
 812                                 object->elements = NULL;
 813                                 return ARRAY;
 814                         }
 815                         return (tagType == TAG_START) ? '(' : ')';
 816                 }
 817                 break;
 818         case 'd':
 819                 if (!strcmp(tag, "dict")) {
 820                         if (tagType == TAG_EMPTY) {
 821                                 object->elements = NULL;
 822                                 return DICTIONARY;
 823                         }
 824                         return (tagType == TAG_START) ? '{' : '}';
 825                 }
 826                 if (!strcmp(tag, "data")) {
 827                         unsigned int size;
 828                         if (tagType == TAG_EMPTY) {
 829                                 object->data = NULL;
 830                                 object->size = 0;
 831                                 return DATA;
 832                         }
 833
 834                         bool isHexFormat = false;
 835                         for (i=0; i < attributeCount; i++) {
 836                                 if (!strcmp(attributes[i], "format") && !strcmp(values[i], "hex")) {
 837                                         isHexFormat = true;
 838                                         break;
 839                                 }
 840                         }
 841                         // CF encoded is the default form
 842                         if (isHexFormat) {
 843                             object->data = getHexData(STATE, &size);
 844                         } else {
 845                             object->data = getCFEncodedData(STATE, &size);
 846                         }
 847                         object->size = size;
 848                         if ((getTag(STATE, tag, &attributeCount, attributes, values) != TAG_END) || strcmp(tag, "data")) {
 849                                 return SYNTAX_ERROR;
 850                         }
 851                         return DATA;
 852                 }
 853                 break;
 854         case 'f':
 855                 if (!strcmp(tag, "false")) {
 856                         if (tagType == TAG_EMPTY) {
 857                                 object->number = 0;
 858                                 return BOOLEAN;
 859                         }
 860                 }
 861                 break;
 862         case 'i':
 863                 if (!strcmp(tag, "integer")) {
 864                         object->size = 64;      // default
 865                         for (i=0; i < attributeCount; i++) {
 866                                 if (!strcmp(attributes[i], "size")) {
 867                                         object->size = strtoul(values[i], NULL, 0);
 868                                 }
 869                         }
 870                         if (tagType == TAG_EMPTY) {
 871                                 object->number = 0;
 872                                 return NUMBER;
 873                         }
 874                         object->number = getNumber(STATE);
 875                         if ((getTag(STATE, tag, &attributeCount, attributes, values) != TAG_END) || strcmp(tag, "integer")) {
 876                                 return SYNTAX_ERROR;
 877                         }
 878                         return NUMBER;
 879                 }
 880                 break;
 881         case 'k':
 882                 if (!strcmp(tag, "key")) {
 883                         if (tagType == TAG_EMPTY) return SYNTAX_ERROR;
 884                         object->string = getString(STATE);
 885                         if (!object->string) {
 886                                 return SYNTAX_ERROR;
 887                         }
 888                         if ((getTag(STATE, tag, &attributeCount, attributes, values) != TAG_END)
 889                            || strcmp(tag, "key")) {
 890                                 return SYNTAX_ERROR;
 891                         }
 892                         return KEY;
 893                 }
 894                 break;
 895         case 'p':
 896                 if (!strcmp(tag, "plist")) {
 897                         freeObject(STATE, object);
 898                         goto top;
 899                 }
 900                 break;
 901         case 's':
 902                 if (!strcmp(tag, "string")) {
 903                         if (tagType == TAG_EMPTY) {
 904                                 object->string = (char *)malloc(1);
 905                                 object->string[0] = 0;
 906                                 return STRING;
 907                         }
 908                         object->string = getString(STATE);
 909                         if (!object->string) {
 910                                 return SYNTAX_ERROR;
 911                         }
 912                         if ((getTag(STATE, tag, &attributeCount, attributes, values) != TAG_END)
 913                            || strcmp(tag, "string")) {
 914                                 return SYNTAX_ERROR;
 915                         }
 916                         return STRING;
 917                 }
 918                 if (!strcmp(tag, "set")) {
 919                         if (tagType == TAG_EMPTY) {
 920                                 object->elements = NULL;
 921                                 return SET;;
 922                         }
 923                         if (tagType == TAG_START) {
 924                                 return '[';
 925                         } else {
 926                                 return ']';
 927                         }
 928                 }
 929                 break;
 930         case 't':
 931                 if (!strcmp(tag, "true")) {
 932                         if (tagType == TAG_EMPTY) {
 933                                 object->number = 1;
 934                                 return BOOLEAN;
 935                         }
 936                 }
 937                 break;
 938         }
 939
 940         return SYNTAX_ERROR;
 941 }
 942
 943 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
 944 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
 945 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
 946
 947 // "java" like allocation, if this code hits a syntax error in the
 948 // the middle of the parsed string we just bail with pointers hanging
 949 // all over place, this code helps keeps it all together
 950
 951 //static int object_count = 0;
 952
 953 object_t *
 954 newObject(parser_state_t *state)
 955 {
 956         object_t *o;
 957
 958         if (state->freeObjects) {
 959                 o = state->freeObjects;
 960                 state->freeObjects = state->freeObjects->next;
 961         } else {
 962                 o = (object_t *)malloc(sizeof(object_t));
 963 //              object_count++;
 964                 bzero(o, sizeof(object_t));
 965                 o->free = state->objects;
 966                 state->objects = o;
 967         }
 968
 969         return o;
 970 }
 971
 972 void
 973 freeObject(parser_state_t * state, object_t *o)
 974 {
 975         o->next = state->freeObjects;
 976         state->freeObjects = o;
 977 }
 978
 979 void
 980 cleanupObjects(parser_state_t *state)
 981 {
 982         object_t *t, *o = state->objects;
 983
 984         while (o) {
 985                 if (o->object) {
 986 //                      printf("OSUnserializeXML: releasing object o=%x object=%x\n", (int)o, (int)o->object);
 987                         o->object->release();
 988                 }
 989                 if (o->data) {
 990 //                      printf("OSUnserializeXML: freeing   object o=%x data=%x\n", (int)o, (int)o->data);
 991                         free(o->data);
 992                 }
 993                 if (o->key) {
 994 //                      printf("OSUnserializeXML: releasing object o=%x key=%x\n", (int)o, (int)o->key);
 995                         o->key->release();
 996                 }
 997                 if (o->string) {
 998 //                      printf("OSUnserializeXML: freeing   object o=%x string=%x\n", (int)o, (int)o->string);
 999                         free(o->string);
1000                 }
1001
1002                 t = o;
1003                 o = o->free;
1004                 free(t);
1005 //              object_count--;
1006         }
1007 //      printf("object_count = %d\n", object_count);
1008 }
1009
1010 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
1011 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
1012 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
1013
1014 static void
1015 rememberObject(parser_state_t *state, int tag, OSObject *o)
1016 {
1017         char key[16];
1018         snprintf(key, 16, "%u", tag);
1019
1020 //      printf("remember key %s\n", key);
1021
1022         state->tags->setObject(key, o);
1023 }
1024
1025 static object_t *
1026 retrieveObject(parser_state_t *state, int tag)
1027 {
1028         OSObject *ref;
1029         object_t *o;
1030         char key[16];
1031         snprintf(key, 16, "%u", tag);
1032
1033 //      printf("retrieve key '%s'\n", key);
1034
1035         ref = state->tags->getObject(key);
1036         if (!ref) return 0;
1037
1038         o = newObject(state);
1039         o->object = ref;
1040         return o;
1041 }
1042
1043 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
1044 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
1045 // !@$&)(^Q$&*^!$(*!@$_(^%_(*Q#$(_*&!$_(*&!$_(*&!#$(*!@&^!@#%!_!#
1046
1047 object_t *
1048 buildDictionary(parser_state_t *state, object_t * header)
1049 {
1050         object_t *o, *t;
1051         int count = 0;
1052         OSDictionary *dict;
1053
1054         // get count and reverse order
1055         o = header->elements;
1056         header->elements = 0;
1057         while (o) {
1058                 count++;
1059                 t = o;
1060                 o = o->next;
1061
1062                 t->next = header->elements;
1063                 header->elements = t;
1064         }
1065
1066         dict = OSDictionary::withCapacity(count);
1067         if (header->idref >= 0) rememberObject(state, header->idref, dict);
1068
1069         o = header->elements;
1070         while (o) {
1071                 dict->setObject(o->key, o->object);
1072
1073                 o->key->release();
1074                 o->object->release();
1075                 o->key = 0;
1076                 o->object = 0;
1077
1078                 t = o;
1079                 o = o->next;
1080                 freeObject(state, t);
1081         }
1082         o = header;
1083         o->object = dict;
1084         return o;
1085 };
1086
1087 object_t *
1088 buildArray(parser_state_t *state, object_t * header)
1089 {
1090         object_t *o, *t;
1091         int count = 0;
1092         OSArray *array;
1093
1094         // get count and reverse order
1095         o = header->elements;
1096         header->elements = 0;
1097         while (o) {
1098                 count++;
1099                 t = o;
1100                 o = o->next;
1101
1102                 t->next = header->elements;
1103                 header->elements = t;
1104         }
1105
1106         array = OSArray::withCapacity(count);
1107         if (header->idref >= 0) rememberObject(state, header->idref, array);
1108
1109         o = header->elements;
1110         while (o) {
1111                 array->setObject(o->object);
1112
1113                 o->object->release();
1114                 o->object = 0;
1115
1116                 t = o;
1117                 o = o->next;
1118                 freeObject(state, t);
1119         }
1120         o = header;
1121         o->object = array;
1122         return o;
1123 };
1124
1125 object_t *
1126 buildSet(parser_state_t *state, object_t *header)
1127 {
1128         object_t *o = buildArray(state, header);
1129
1130         OSArray *array = (OSArray *)o->object;
1131         OSSet *set = OSSet::withArray(array, array->getCapacity());
1132
1133         // write over the reference created in buildArray
1134         if (header->idref >= 0) rememberObject(state, header->idref, set);
1135
1136         array->release();
1137         o->object = set;
1138         return o;
1139 };
1140
1141 object_t *
1142 buildString(parser_state_t *state, object_t *o)
1143 {
1144         OSString *string;
1145
1146         string = OSString::withCString(o->string);
1147         if (o->idref >= 0) rememberObject(state, o->idref, string);
1148
1149         free(o->string);
1150         o->string = 0;
1151         o->object = string;
1152
1153         return o;
1154 };
1155
1156 object_t *
1157 buildSymbol(parser_state_t *state, object_t *o)
1158 {
1159         OSSymbol *symbol;
1160
1161         symbol = (OSSymbol *)OSSymbol::withCString(o->string);
1162         if (o->idref >= 0) rememberObject(state, o->idref, symbol);
1163
1164         free(o->string);
1165         o->string = 0;
1166         o->object = symbol;
1167
1168         return o;
1169 };
1170
1171 object_t *
1172 buildData(parser_state_t *state, object_t *o)
1173 {
1174         OSData *data;
1175
1176         if (o->size) {
1177                 data = OSData::withBytes(o->data, o->size);
1178         } else {
1179                 data = OSData::withCapacity(0);
1180         }
1181         if (o->idref >= 0) rememberObject(state, o->idref, data);
1182
1183         if (o->size) free(o->data);
1184         o->data = 0;
1185         o->object = data;
1186         return o;
1187 };
1188
1189 object_t *
1190 buildNumber(parser_state_t *state, object_t *o)
1191 {
1192         OSNumber *number = OSNumber::withNumber(o->number, o->size);
1193
1194         if (o->idref >= 0) rememberObject(state, o->idref, number);
1195
1196         o->object = number;
1197         return o;
1198 };
1199
1200 object_t *
1201 buildBoolean(parser_state_t *state __unused, object_t *o)
1202 {
1203         o->object = ((o->number == 0) ? kOSBooleanFalse : kOSBooleanTrue);
1204         o->object->retain();
1205         return o;
1206 };
1207
1208 OSObject*
1209 OSUnserializeXML(const char *buffer, OSString **errorString)
1210 {
1211         OSObject *object;
1212
1213         if (!buffer) return 0;
1214         parser_state_t *state = (parser_state_t *)malloc(sizeof(parser_state_t));
1215         if (!state) return 0;
1216
1217         // just in case
1218         if (errorString) *errorString = NULL;
1219
1220         state->parseBuffer = buffer;
1221         state->parseBufferIndex = 0;
1222         state->lineNumber = 1;
1223         state->objects = 0;
1224         state->freeObjects = 0;
1225         state->tags = OSDictionary::withCapacity(128);
1226         state->errorString = errorString;
1227         state->parsedObject = 0;
1228         state->parsedObjectCount = 0;
1229
1230         (void)yyparse((void *)state);
1231
1232         object = state->parsedObject;
1233
1234         cleanupObjects(state);
1235         state->tags->release();
1236         free(state);
1237
1238         return object;
1239 }
1240
1241 #include <libkern/OSSerializeBinary.h>
1242
1243 OSObject*
1244 OSUnserializeXML(const char *buffer, size_t bufferSize, OSString **errorString)
1245 {
1246         if (!buffer) return (0);
1247     if (bufferSize < sizeof(kOSSerializeBinarySignature)) return (0);
1248
1249         if (!strcmp(kOSSerializeBinarySignature, buffer)) return OSUnserializeBinary(buffer, bufferSize, errorString);
1250
1251         // XML must be null terminated
1252         if (buffer[bufferSize - 1]) return 0;
1253
1254         return OSUnserializeXML(buffer, errorString);
1255 }
1256
1257
1258 //
1259 //
1260 //
1261 //
1262 //
1263 //               DO NOT EDIT OSUnserializeXML.cpp!
1264 //
1265 //                      this means you!
1266 //
1267 //
1268 //
1269 //
1270 //