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