sherlock/xml/parse.c

   1 /*
   2  *      Sherlock Library -- A simple XML parser
   3  *
   4  *      (c) 2007 Pavel Charvat <pchar@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #undef LOCAL_DEBUG
  11
  12 #include "sherlock/sherlock.h"
  13 #include "sherlock/xml/xml.h"
  14 #include "sherlock/xml/dtd.h"
  15 #include "sherlock/xml/common.h"
  16 #include "lib/fastbuf.h"
  17 #include "lib/ff-unicode.h"
  18 #include "lib/unicode.h"
  19 #include "lib/chartype.h"
  20 #include "lib/hashfunc.h"
  21
  22 #include <setjmp.h>
  23
  24 /*** Basic parsing ***/
  25
  26 void NONRET
  27 xml_fatal_expected(struct xml_context *ctx, uns c)
  28 {
  29   if (c >= 32 && c < 128)
  30     xml_fatal(ctx, "Expected '%c'", c);
  31   else
  32     xml_fatal(ctx, "Expected U+%04x", c);
  33 }
  34
  35 void NONRET
  36 xml_fatal_expected_white(struct xml_context *ctx)
  37 {
  38   xml_fatal(ctx, "Expected a white space");
  39 }
  40
  41 void NONRET
  42 xml_fatal_expected_quot(struct xml_context *ctx)
  43 {
  44   xml_fatal(ctx, "Expected a quotation mark");
  45 }
  46
  47 void
  48 xml_parse_eq(struct xml_context *ctx)
  49 {
  50   /* Eq ::= S? '=' S? */
  51   xml_parse_white(ctx, 0);
  52   xml_parse_char(ctx, '=');
  53   xml_parse_white(ctx, 0);
  54 }
  55
  56 /*** Names and nmtokens ***/
  57
  58 static char *
  59 xml_parse_string(struct xml_context *ctx, struct mempool *pool, uns first_cat, uns next_cat, char *err)
  60 {
  61   char *p = mp_start_noalign(pool, 1);
  62   if (unlikely(!(xml_peek_cat(ctx) & first_cat)))
  63     xml_fatal(ctx, "%s", err);
  64   do
  65     {
  66       p = mp_spread(pool, p, 5);
  67       p = utf8_32_put(p, xml_skip_char(ctx));
  68     }
  69   while (xml_peek_cat(ctx) & next_cat);
  70   *p++ = 0;
  71   return mp_end(pool, p);
  72 }
  73
  74 static void
  75 xml_skip_string(struct xml_context *ctx, uns first_cat, uns next_cat, char *err)
  76 {
  77   if (unlikely(!(xml_get_cat(ctx) & first_cat)))
  78     xml_fatal(ctx, "%s", err);
  79   while (xml_peek_cat(ctx) & next_cat)
  80     xml_skip_char(ctx);
  81 }
  82
  83 char *
  84 xml_parse_name(struct xml_context *ctx, struct mempool *pool)
  85 {
  86   /* Name ::= NameStartChar (NameChar)* */
  87   return xml_parse_string(ctx, pool,
  88       !(ctx->flags & XML_VERSION_1_1) ? XML_CHAR_SNAME_1_0 : XML_CHAR_SNAME_1_1,
  89       !(ctx->flags & XML_VERSION_1_1) ? XML_CHAR_NAME_1_0 : XML_CHAR_NAME_1_1,
  90       "Expected a name");
  91 }
  92
  93 void
  94 xml_skip_name(struct xml_context *ctx)
  95 {
  96   xml_skip_string(ctx,
  97       !(ctx->flags & XML_VERSION_1_1) ? XML_CHAR_SNAME_1_0 : XML_CHAR_SNAME_1_1,
  98       !(ctx->flags & XML_VERSION_1_1) ? XML_CHAR_NAME_1_0 : XML_CHAR_NAME_1_1,
  99       "Expected a name");
 100 }
 101
 102 char *
 103 xml_parse_nmtoken(struct xml_context *ctx, struct mempool *pool)
 104 {
 105   /* Nmtoken ::= (NameChar)+ */
 106   uns cat = !(ctx->flags & XML_VERSION_1_1) ? XML_CHAR_NAME_1_0 : XML_CHAR_NAME_1_1;
 107   return xml_parse_string(ctx, pool, cat, cat, "Expected a nmtoken");
 108 }
 109
 110 /*** Simple literals ***/
 111
 112 char *
 113 xml_parse_system_literal(struct xml_context *ctx, struct mempool *pool)
 114 {
 115   /* SystemLiteral ::= ('"' [^"]* '"') | ("'" [^']* "'") */
 116   char *p = mp_start_noalign(pool, 1);
 117   uns q = xml_parse_quote(ctx), c;
 118   while ((c = xml_get_char(ctx)) != q)
 119     {
 120       p = mp_spread(pool, p, 5);
 121       p = utf8_32_put(p, c);
 122     }
 123   *p++ = 0;
 124   return mp_end(pool, p);
 125 }
 126
 127 char *
 128 xml_parse_pubid_literal(struct xml_context *ctx, struct mempool *pool)
 129 {
 130   /* PubidLiteral ::= '"' PubidChar* '"' | "'" (PubidChar - "'")* "'" */
 131   char *p = mp_start_noalign(pool, 1);
 132   uns q = xml_parse_quote(ctx), c;
 133   while ((c = xml_get_char(ctx)) != q)
 134     {
 135       if (unlikely(!(xml_last_cat(ctx) & XML_CHAR_PUBID)))
 136         xml_fatal(ctx, "Expected a pubid character");
 137       p = mp_spread(pool, p, 2);
 138       *p++ = c;
 139     }
 140   *p++ = 0;
 141   return mp_end(pool, p);
 142 }
 143
 144 /*** Comments ***/
 145
 146 void
 147 xml_push_comment(struct xml_context *ctx)
 148 {
 149   TRACE(ctx, "push_comment");
 150   /* Comment ::= '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'
 151    * Already parsed: '<!-' */
 152   xml_parse_char(ctx, '-');
 153   struct xml_node *n = xml_push_dom(ctx);
 154   n->type = XML_NODE_COMMENT;
 155   char *p = mp_start_noalign(ctx->pool, 6);
 156   while (1)
 157     {
 158       if (xml_get_char(ctx) == '-')
 159         if (xml_get_char(ctx) == '-')
 160           break;
 161         else
 162           *p++ = '-';
 163       p = utf8_32_put(p, xml_last_char(ctx));
 164       p = mp_spread(ctx->pool, p, 6);
 165     }
 166   xml_parse_char(ctx, '>');
 167   *p = 0;
 168   n->len = p - (char *)mp_ptr(ctx->pool);
 169   n->text = mp_end(ctx->pool, p + 1);
 170   if ((ctx->flags & XML_REPORT_COMMENTS) && ctx->h_comment)
 171     ctx->h_comment(ctx);
 172 }
 173
 174 void
 175 xml_pop_comment(struct xml_context *ctx)
 176 {
 177   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_COMMENTS));
 178   xml_dec(ctx);
 179   TRACE(ctx, "pop_comment");
 180 }
 181
 182 void
 183 xml_skip_comment(struct xml_context *ctx)
 184 {
 185   TRACE(ctx, "skip_comment");
 186   xml_parse_char(ctx, '-');
 187   while (xml_get_char(ctx) != '-' || xml_get_char(ctx) != '-');
 188   xml_parse_char(ctx, '>');
 189   xml_dec(ctx);
 190 }
 191
 192 /*** Processing instructions ***/
 193
 194 void
 195 xml_push_pi(struct xml_context *ctx)
 196 {
 197   TRACE(ctx, "push_pi");
 198   /* Parses a PI to ctx->value and ctx->name:
 199    *   PI ::= '<?' PITarget (S (Char* - (Char* '?>' Char*)))? '?>'
 200    *   PITarget ::= Name - (('X' | 'x') ('M' | 'm') ('L' | 'l'))
 201    * Already parsed: '<?' */
 202   struct xml_node *n = xml_push_dom(ctx);
 203   n->type = XML_NODE_PI;
 204   n->name = xml_parse_name(ctx, ctx->pool);
 205   if (unlikely(!strcasecmp(n->name, "xml")))
 206     xml_error(ctx, "Reserved PI target");
 207   char *p = mp_start_noalign(ctx->pool, 5);
 208   if (!xml_parse_white(ctx, 0))
 209     xml_parse_seq(ctx, "?>");
 210   else
 211     while (1)
 212       {
 213         if (xml_get_char(ctx) == '?')
 214           if (xml_peek_char(ctx) == '>')
 215             {
 216               xml_skip_char(ctx);
 217               break;
 218             }
 219           else
 220             *p++ = '?';
 221         else
 222           p = utf8_32_put(p, xml_last_char(ctx));
 223         p = mp_spread(ctx->pool, p, 5);
 224       }
 225   *p = 0;
 226   n->len = p - (char *)mp_ptr(ctx->pool);
 227   n->text = mp_end(ctx->pool, p + 1);
 228   if ((ctx->flags & XML_REPORT_PIS) && ctx->h_pi)
 229     ctx->h_pi(ctx);
 230 }
 231
 232 void
 233 xml_pop_pi(struct xml_context *ctx)
 234 {
 235   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_PIS));
 236   xml_dec(ctx);
 237   TRACE(ctx, "pop_pi");
 238 }
 239
 240 void
 241 xml_skip_pi(struct xml_context *ctx)
 242 {
 243   TRACE(ctx, "skip_pi");
 244   if (ctx->flags & XML_VALIDATING)
 245     {
 246       struct mempool_state state;
 247       mp_save(ctx->stack, &state);
 248       if (unlikely(!strcasecmp(xml_parse_name(ctx, ctx->stack), "xml")))
 249         xml_error(ctx, "Reserved PI target");
 250       mp_restore(ctx->stack, &state);
 251       if (!xml_parse_white(ctx, 0))
 252         {
 253           xml_parse_seq(ctx, "?>");
 254           xml_dec(ctx);
 255           return;
 256         }
 257     }
 258   while (1)
 259     if (xml_get_char(ctx) == '?')
 260       if (xml_peek_char(ctx) == '>')
 261         break;
 262   xml_skip_char(ctx);
 263   xml_dec(ctx);
 264 }
 265
 266 /*** Character data ***/
 267
 268 static inline uns
 269 xml_flush_chars(struct xml_context *ctx)
 270 {
 271   struct fastbuf *fb = &ctx->chars;
 272   if (fb->bufend == fb->buffer)
 273     return 0;
 274   TRACE(ctx, "flush_chars");
 275   struct xml_node *n = ctx->node;
 276   n->text = xml_end_chars(ctx, &n->len);
 277   n->len = fb->bufend - fb->buffer;
 278   if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_chars)
 279     ctx->h_chars(ctx);
 280   return 1;
 281 }
 282
 283 static inline void
 284 xml_pop_chars(struct xml_context *ctx)
 285 {
 286   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_CHARS));
 287   TRACE(ctx, "pop_chars");
 288 }
 289
 290 static inline void
 291 xml_append_chars(struct xml_context *ctx)
 292 {
 293   TRACE(ctx, "append_chars");
 294   struct fastbuf *out = &ctx->chars;
 295   while (xml_get_char(ctx) != '<')
 296     if (xml_last_char(ctx) == '&')
 297       {
 298         xml_inc(ctx);
 299         xml_parse_ref(ctx);
 300       }
 301     else
 302       bput_utf8_32(out, xml_last_char(ctx));
 303   xml_unget_char(ctx);
 304 }
 305
 306 /*** CDATA sections ***/
 307
 308 static void
 309 xml_push_cdata(struct xml_context *ctx)
 310 {
 311   TRACE(ctx, "push_cdata");
 312   /* CDSect :== '<![CDATA[' (Char* - (Char* ']]>' Char*)) ']]>'
 313    * Already parsed: '<![' */
 314   xml_parse_seq(ctx, "CDATA[");
 315   struct xml_node *n = xml_push_dom(ctx);
 316   n->type = XML_NODE_CHARS;
 317   char *p = mp_start_noalign(ctx->pool, 7);
 318   while (1)
 319     {
 320       if (xml_get_char(ctx) == ']')
 321         {
 322           if (xml_get_char(ctx) == ']')
 323             if (xml_get_char(ctx) == '>')
 324               break;
 325             else
 326               *p++ = ']';
 327           *p++ = ']';
 328         }
 329       p = utf8_32_put(p, xml_last_char(ctx));
 330       p = mp_spread(ctx->pool, p, 7);
 331     }
 332   *p = 0;
 333   n->len = p - (char *)mp_ptr(ctx->pool);
 334   n->text = mp_end(ctx->pool, p + 1);
 335   if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_cdata)
 336     ctx->h_cdata(ctx);
 337 }
 338
 339 static void
 340 xml_pop_cdata(struct xml_context *ctx)
 341 {
 342   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_CHARS));
 343   xml_dec(ctx);
 344   TRACE(ctx, "pop_cdata");
 345 }
 346
 347 static void
 348 xml_append_cdata(struct xml_context *ctx)
 349 {
 350   TRACE(ctx, "append_cdata");
 351   xml_parse_seq(ctx, "CDATA[");
 352   struct fastbuf *out = &ctx->chars;
 353   while (1)
 354     {
 355       if (xml_get_char(ctx) == ']')
 356         {
 357           if (xml_get_char(ctx) == ']')
 358             if (xml_get_char(ctx) == '>')
 359               break;
 360             else
 361               bputc(out, ']');
 362           bputc(out, ']');
 363         }
 364       bput_utf8_32(out, xml_last_char(ctx));
 365     }
 366   xml_dec(ctx);
 367 }
 368
 369 static void UNUSED
 370 xml_skip_cdata(struct xml_context *ctx)
 371 {
 372   TRACE(ctx, "skip_cdata");
 373   xml_parse_seq(ctx, "CDATA[");
 374   while (xml_get_char(ctx) != ']' || xml_get_char(ctx) != ']' || xml_get_char(ctx) != '>');
 375   xml_dec(ctx);
 376 }
 377
 378 /*** Character references ***/
 379
 380 uns
 381 xml_parse_char_ref(struct xml_context *ctx)
 382 {
 383   TRACE(ctx, "parse_char_ref");
 384   /* CharRef ::= '&#' [0-9]+ ';' | '&#x' [0-9a-fA-F]+ ';'
 385    * Already parsed: '&#' */
 386   uns v = 0;
 387   if (xml_get_char(ctx) == 'x')
 388     {
 389       if (!(xml_get_cat(ctx) & XML_CHAR_XDIGIT))
 390         {
 391           xml_error(ctx, "Expected a hexadecimal value of character reference");
 392           goto recover;
 393         }
 394       do
 395         {
 396           v = (v << 4) + Cxvalue(xml_last_char(ctx));
 397         }
 398       while (v < 0x110000 && (xml_get_cat(ctx) & XML_CHAR_XDIGIT));
 399     }
 400   else
 401     {
 402       if (!(xml_last_cat(ctx) & XML_CHAR_DIGIT))
 403         {
 404           xml_error(ctx, "Expected a numeric value of character reference");
 405           goto recover;
 406         }
 407       do
 408         {
 409           v = v * 10 + xml_last_char(ctx) - '0';
 410         }
 411       while (v < 0x110000 && (xml_get_cat(ctx) & XML_CHAR_DIGIT));
 412     }
 413   uns cat = xml_char_cat(v);
 414   if (!(cat & XML_CHAR_UNRESTRICTED_1_1) && ((ctx->flags & XML_VERSION_1_1) || !(cat & XML_CHAR_VALID_1_0)))
 415     {
 416       xml_error(ctx, "Character reference out of range");
 417       goto recover;
 418     }
 419   if (xml_last_char(ctx) == ';')
 420     {
 421       xml_dec(ctx);
 422       return v;
 423     }
 424   xml_error(ctx, "Expected ';'");
 425 recover:
 426   while (xml_last_char(ctx) != ';')
 427     xml_get_char(ctx);
 428   xml_dec(ctx);
 429   return UNI_REPLACEMENT;
 430 }
 431
 432 /*** References to general entities ***/
 433
 434 void
 435 xml_parse_ref(struct xml_context *ctx)
 436 {
 437   /* Reference ::= EntityRef | CharRef
 438    * EntityRef ::= '&' Name ';'
 439    * Already parsed: '&' */
 440   struct fastbuf *out = &ctx->chars;
 441   if (xml_peek_char(ctx) == '#')
 442     {
 443       xml_skip_char(ctx);
 444       bput_utf8_32(out, xml_parse_char_ref(ctx));
 445     }
 446   else
 447     {
 448       TRACE(ctx, "parse_ge_ref");
 449       struct mempool_state state;
 450       mp_save(ctx->stack, &state);
 451       char *name = xml_parse_name(ctx, ctx->stack);
 452       xml_parse_char(ctx, ';');
 453       struct xml_dtd_ent *ent = xml_dtd_find_ent(ctx, name);
 454       if (!ent)
 455         {
 456           xml_error(ctx, "Unknown entity &%s;", name);
 457           bputc(out, '&');
 458           bputs(out, name);
 459           bputc(out, ';');
 460         }
 461       else if (ent->flags & XML_DTD_ENT_TRIVIAL)
 462         {
 463           TRACE(ctx, "Trivial entity &%s;", name);
 464           bwrite(out, ent->text, ent->len);
 465         }
 466       else
 467         {
 468           TRACE(ctx, "Pushed entity &%s;", name);
 469           mp_restore(ctx->stack, &state);
 470           xml_dec(ctx);
 471           xml_push_entity(ctx, ent);
 472           return;
 473         }
 474       mp_restore(ctx->stack, &state);
 475       xml_dec(ctx);
 476     }
 477 }
 478
 479 /*** Attribute values ***/
 480
 481 char *
 482 xml_parse_attr_value(struct xml_context *ctx, struct xml_dtd_attr *attr UNUSED)
 483 {
 484   TRACE(ctx, "parse_attr_value");
 485   /* AttValue ::= '"' ([^<&"] | Reference)* '"' | "'" ([^<&'] | Reference)* "'" */
 486   /* FIXME:
 487    * -- copying from ctx->chars to ctx->pool is not necessary, we could directly write to ctx->pool
 488    * -- berare quotes inside parased entities
 489    * -- check value constrains / normalize value */
 490   struct mempool_state state;
 491   uns quote = xml_parse_quote(ctx);
 492   mp_save(ctx->stack, &state);
 493   xml_start_chars(ctx);
 494   struct fastbuf *out = &ctx->chars;
 495   while (1)
 496     {
 497       uns c = xml_get_char(ctx);
 498       if (c == '&')
 499         {
 500           xml_inc(ctx);
 501           xml_parse_ref(ctx);
 502         }
 503       else if (c == quote) // FIXME: beware quotes inside parsed entities
 504         break;
 505       else if (c == '<')
 506         xml_error(ctx, "Attribute value must not contain '<'");
 507       else if (xml_last_cat(ctx) & XML_CHAR_WHITE)
 508         bputc(out, ' ');
 509       else
 510         bput_utf8_32(out, c);
 511     }
 512   mp_restore(ctx->stack, &state);
 513   uns len;
 514   return xml_end_chars(ctx, &len);
 515 }
 516
 517 /*** Attributes ***/
 518
 519 struct xml_attrs_table;
 520
 521 static inline uns
 522 xml_attrs_hash(struct xml_attrs_table *t UNUSED, struct xml_node *e, char *n)
 523 {
 524   return hash_pointer(e) ^ hash_string(n);
 525 }
 526
 527 static inline int
 528 xml_attrs_eq(struct xml_attrs_table *t UNUSED, struct xml_node *e1, char *n1, struct xml_node *e2, char *n2)
 529 {
 530   return (e1 == e2) && !strcmp(n1, n2);
 531 }
 532
 533 static inline void
 534 xml_attrs_init_key(struct xml_attrs_table *t UNUSED, struct xml_attr *a, struct xml_node *e, char *name)
 535 {
 536   a->elem = e;
 537   a->name = name;
 538   a->val = NULL;
 539   slist_add_tail(&e->attrs, &a->n);
 540 }
 541
 542 #define HASH_PREFIX(x) xml_attrs_##x
 543 #define HASH_NODE struct xml_attr
 544 #define HASH_KEY_COMPLEX(x) x elem, x name
 545 #define HASH_KEY_DECL struct xml_node *elem, char *name
 546 #define HASH_TABLE_DYNAMIC
 547 #define HASH_GIVE_EQ
 548 #define HASH_GIVE_HASHFN
 549 #define HASH_GIVE_INIT_KEY
 550 #define HASH_WANT_CLEANUP
 551 #define HASH_WANT_REMOVE
 552 #define HASH_WANT_LOOKUP
 553 #define HASH_WANT_FIND
 554 #define HASH_GIVE_ALLOC
 555 XML_HASH_GIVE_ALLOC
 556 #include "lib/hashtable.h"
 557
 558 static void
 559 xml_parse_attr(struct xml_context *ctx)
 560 {
 561   TRACE(ctx, "parse_attr");
 562   /* Attribute ::= Name Eq AttValue */
 563   /* FIXME:
 564    * -- memory management
 565    * -- DTD */
 566   struct xml_node *e = ctx->node;
 567   char *n = xml_parse_name(ctx, ctx->pool);
 568   struct xml_attr *a = xml_attrs_lookup(ctx->tab_attrs, e, n);
 569   xml_parse_eq(ctx);
 570   char *v = xml_parse_attr_value(ctx, NULL);
 571   if (a->val)
 572     xml_error(ctx, "Attribute %s is not unique", n);
 573   else
 574     a->val = v;
 575 }
 576
 577 struct xml_attr *
 578 xml_attr_find(struct xml_context *ctx, struct xml_node *node, char *name)
 579 {
 580   return xml_attrs_find(ctx->tab_attrs, node, name);
 581 }
 582
 583 void
 584 xml_attrs_table_init(struct xml_context *ctx)
 585 {
 586   xml_attrs_init(ctx->tab_attrs = xml_hash_new(ctx->pool, sizeof(struct xml_attrs_table)));
 587 }
 588
 589 void
 590 xml_attrs_table_cleanup(struct xml_context *ctx)
 591 {
 592   xml_attrs_cleanup(ctx->tab_attrs);
 593 }
 594
 595 /*** Elements ***/
 596
 597 static void
 598 xml_push_element(struct xml_context *ctx)
 599 {
 600   TRACE(ctx, "push_element");
 601   /* EmptyElemTag | STag
 602    * EmptyElemTag ::= '<' Name (S  Attribute)* S? '/>'
 603    * STag ::= '<' Name (S  Attribute)* S? '>'
 604    * Already parsed: '<' */
 605   struct xml_node *e = xml_push_dom(ctx);
 606   clist_init(&e->sons);
 607   e->type = XML_NODE_ELEM;
 608   e->name = xml_parse_name(ctx, ctx->pool);
 609   slist_init(&e->attrs);
 610   if (!e->parent)
 611     {
 612       ctx->root = e;
 613       if (ctx->doctype && strcmp(e->name, ctx->doctype))
 614         xml_error(ctx, "The root element %s does not match the document type %s", e->name, ctx->doctype);
 615     }
 616   while (1)
 617     {
 618       uns white = xml_parse_white(ctx, 0);
 619       uns c = xml_get_char(ctx);
 620       if (c == '/')
 621         {
 622           xml_parse_char(ctx, '>');
 623           ctx->flags |= XML_EMPTY_ELEM_TAG;
 624           break;
 625         }
 626       else if (c == '>')
 627         break;
 628       else if (!white)
 629         xml_fatal_expected_white(ctx);
 630       xml_unget_char(ctx);
 631       xml_parse_attr(ctx);
 632     }
 633   if ((ctx->flags & XML_REPORT_TAGS) && ctx->h_stag)
 634     ctx->h_stag(ctx);
 635 }
 636
 637 static void
 638 xml_pop_element(struct xml_context *ctx)
 639 {
 640   TRACE(ctx, "pop_element");
 641   if ((ctx->flags & XML_REPORT_TAGS) && ctx->h_etag)
 642     ctx->h_etag(ctx);
 643   struct xml_node *e = ctx->node;
 644   uns free = !(ctx->flags & XML_ALLOC_TAGS);
 645   if (free)
 646     {
 647       if (!e->parent)
 648         ctx->root = NULL;
 649       /* Restore hash table of attributes */
 650       SLIST_FOR_EACH(struct xml_attr *, a, e->attrs)
 651         xml_attrs_remove(ctx->tab_attrs, a);
 652       struct xml_node *n;
 653       while (n = clist_head(&e->sons))
 654         {
 655           if (n->type == XML_NODE_ELEM)
 656             {
 657               SLIST_FOR_EACH(struct xml_attr *, a, n->attrs)
 658                 xml_attrs_remove(ctx->tab_attrs, a);
 659               clist_insert_list_after(&n->sons, &n->n);
 660             }
 661           clist_remove(&n->n);
 662         }
 663     }
 664   xml_pop_dom(ctx, free);
 665   xml_dec(ctx);
 666 }
 667
 668 static void
 669 xml_parse_etag(struct xml_context *ctx)
 670 {
 671  /* ETag ::= '</' Name S? '>'
 672   * Already parsed: '<' */
 673   struct xml_node *e = ctx->node;
 674   ASSERT(e);
 675   char *n = e->name;
 676   while (*n)
 677     {
 678       uns c;
 679       n = utf8_32_get(n, &c);
 680       if (xml_get_char(ctx) != c)
 681         goto recover;
 682     }
 683   xml_parse_white(ctx, 0);
 684   if (xml_get_char(ctx) != '>')
 685     {
 686 recover:
 687       xml_error(ctx, "Invalid ETag, expected </%s>", e->name);
 688       while (xml_get_char(ctx) != '>');
 689     }
 690   xml_dec(ctx);
 691 }
 692
 693 /*** Document type declaration ***/
 694
 695 static void
 696 xml_parse_doctype_decl(struct xml_context *ctx)
 697 {
 698   TRACE(ctx, "parse_doctype_decl");
 699   /* doctypedecl ::= '<!DOCTYPE' S  Name (S  ExternalID)? S? ('[' intSubset ']' S?)? '>'
 700    * Already parsed: '<!'
 701    * Terminated before '[' or '>' */
 702   if (ctx->doctype)
 703     xml_fatal(ctx, "Multiple document types not allowed");
 704   xml_parse_seq(ctx, "DOCTYPE");
 705   xml_parse_white(ctx, 1);
 706   ctx->doctype = xml_parse_name(ctx, ctx->pool);
 707   TRACE(ctx, "doctype=%s", ctx->doctype);
 708   uns c;
 709   if (xml_parse_white(ctx, 0) && ((c = xml_peek_char(ctx)) == 'S' || c == 'P'))
 710     {
 711       if (c == 'S')
 712         {
 713           xml_parse_seq(ctx, "SYSTEM");
 714           xml_parse_white(ctx, 1);
 715           ctx->system_id = xml_parse_system_literal(ctx, ctx->pool);
 716         }
 717       else
 718         {
 719           xml_parse_seq(ctx, "PUBLIC");
 720           xml_parse_white(ctx, 1);
 721           ctx->public_id = xml_parse_pubid_literal(ctx, ctx->pool);
 722           xml_parse_white(ctx, 1);
 723           ctx->system_id = xml_parse_system_literal(ctx, ctx->pool);
 724         }
 725       xml_parse_white(ctx, 0);
 726       ctx->flags |= XML_HAS_EXTERNAL_SUBSET;
 727     }
 728   if (xml_peek_char(ctx) == '[')
 729     ctx->flags |= XML_HAS_INTERNAL_SUBSET;
 730   if (ctx->h_doctype_decl)
 731     ctx->h_doctype_decl(ctx);
 732 }
 733
 734
 735
 736 ///////////////////////////////////////////////////////////////////////////////////////////////////////////
 737
 738 /* DTD: Internal subset */
 739
 740 static void
 741 xml_parse_internal_subset(struct xml_context *ctx)
 742 {
 743   // FIXME: comments/pi have no parent
 744   /* '[' intSubset ']'
 745    * intSubset :== (markupdecl | DeclSep)
 746    * Already parsed: ']' */
 747   while (1)
 748     {
 749       xml_parse_white(ctx, 0);
 750       uns c = xml_get_char(ctx);
 751       xml_inc(ctx);
 752       if (c == '<')
 753         if ((c = xml_get_char(ctx)) == '!')
 754           switch (c = xml_get_char(ctx))
 755             {
 756               case '-':
 757                 xml_push_comment(ctx);
 758                 xml_pop_comment(ctx);
 759                 break;
 760               case 'N':
 761                 xml_parse_seq(ctx, "OTATION");
 762                 xml_parse_notation_decl(ctx);
 763                 break;
 764               case 'E':
 765                 if ((c = xml_get_char(ctx)) == 'N')
 766                   {
 767                     xml_parse_seq(ctx, "TITY");
 768                     xml_parse_entity_decl(ctx);
 769                   }
 770                 else if (c == 'L')
 771                   {
 772                     xml_parse_seq(ctx, "EMENT");
 773                     xml_parse_element_decl(ctx);
 774                   }
 775                 else
 776                   goto invalid_markup;
 777                 break;
 778               case 'A':
 779                 xml_parse_seq(ctx, "TTLIST");
 780                 xml_parse_attr_list_decl(ctx);
 781                 break;
 782               default:
 783                 goto invalid_markup;
 784             }
 785         else if (c == '?')
 786           {
 787             xml_push_pi(ctx);
 788             xml_pop_pi(ctx);
 789           }
 790         else
 791           goto invalid_markup;
 792       else if (c == '%')
 793         xml_parse_pe_ref(ctx);
 794       else if (c == ']')
 795         break;
 796       else
 797         goto invalid_markup;
 798     }
 799   xml_dec(ctx);
 800   xml_dec(ctx);
 801   return;
 802 invalid_markup:
 803   xml_fatal(ctx, "Invalid markup in the internal subset");
 804 }
 805
 806 /*** The State Machine ***/
 807
 808 uns
 809 xml_next(struct xml_context *ctx)
 810 {
 811   /* A nasty state machine */
 812
 813 #define PULL(x) do { if (ctx->pull & XML_PULL_##x) return ctx->state = XML_STATE_##x; case XML_STATE_##x: ; } while (0)
 814 #define PULL_STATE(x, s) do { if (ctx->pull & XML_PULL_##x) return ctx->state = XML_STATE_##s, XML_STATE_##x; case XML_STATE_##s: ; } while (0)
 815
 816   TRACE(ctx, "xml_next (state=%u)", ctx->state);
 817   jmp_buf throw_buf;
 818   ctx->throw_buf = &throw_buf;
 819   if (setjmp(throw_buf))
 820     {
 821 error:
 822       if (ctx->err_code == XML_ERR_EOF && ctx->h_fatal)
 823         ctx->h_fatal(ctx);
 824       TRACE(ctx, "raised fatal error");
 825       return ctx->state = XML_STATE_EOF;
 826     }
 827   uns c;
 828   switch (ctx->state)
 829     {
 830       case XML_STATE_START:
 831         TRACE(ctx, "entering prolog");
 832         if (ctx->h_document_start)
 833           ctx->h_document_start(ctx);
 834         /* XMLDecl */
 835         xml_refill(ctx);
 836         if (ctx->h_xml_decl)
 837           ctx->h_xml_decl(ctx);
 838         PULL(XML_DECL);
 839
 840         /* Misc* (doctypedecl Misc*)? */
 841         while (1)
 842           {
 843             xml_parse_white(ctx, 0);
 844             xml_parse_char(ctx, '<');
 845             if ((c = xml_get_char(ctx)) == '?')
 846               /* Processing intruction */
 847               if (!(ctx->flags & XML_REPORT_PIS))
 848                 xml_skip_pi(ctx);
 849               else
 850                 {
 851                   xml_push_pi(ctx);
 852                   PULL_STATE(PI, PROLOG_PI);
 853                   xml_pop_pi(ctx);
 854                 }
 855             else if (c != '!')
 856               {
 857                 /* Found the root tag */
 858                 xml_unget_char(ctx);
 859                 goto first_tag;
 860               }
 861             else if (xml_get_char(ctx) == '-')
 862               if (!(ctx->flags & XML_REPORT_COMMENTS))
 863                 xml_skip_comment(ctx);
 864               else
 865                 {
 866                   xml_push_comment(ctx);
 867                   PULL_STATE(COMMENT, PROLOG_COMMENT);
 868                   xml_pop_comment(ctx);
 869                 }
 870             else
 871               {
 872                 /* DocTypeDecl */
 873                 xml_unget_char(ctx);
 874                 xml_parse_doctype_decl(ctx);
 875                 PULL(DOCTYPE_DECL);
 876                 if (xml_peek_char(ctx) == '[')
 877                   {
 878                     // FIXME: ability to skip the subset
 879                     xml_skip_char(ctx);
 880                     xml_inc(ctx);
 881                     xml_dtd_init(ctx);
 882                     if (ctx->h_dtd_start)
 883                       ctx->h_dtd_start(ctx);
 884                     xml_parse_internal_subset(ctx);
 885                     // FIXME: external subset
 886                     if (ctx->h_dtd_end)
 887                       ctx->h_dtd_end(ctx);
 888                     xml_parse_white(ctx, 0);
 889                   }
 890                 xml_parse_char(ctx, '>');
 891               }
 892           }
 893
 894       case XML_STATE_CHARS:
 895
 896         while (1)
 897           {
 898             if (xml_peek_char(ctx) != '<')
 899               {
 900                 /* CharData */
 901                 xml_append_chars(ctx);
 902                 continue;
 903               }
 904             else
 905               xml_skip_char(ctx);
 906 first_tag: ;
 907
 908             xml_inc(ctx);
 909             if ((c = xml_get_char(ctx)) == '?')
 910               {
 911                 /* PI */
 912                 if (!(ctx->flags & (XML_REPORT_PIS | XML_ALLOC_PIS)))
 913                   xml_skip_pi(ctx);
 914                 else
 915                   {
 916                     if (xml_flush_chars(ctx))
 917                       {
 918                         PULL_STATE(CHARS, CHARS_BEFORE_PI);
 919                         xml_pop_chars(ctx);
 920                       }
 921                     xml_push_pi(ctx);
 922                     PULL(PI);
 923                     xml_pop_pi(ctx);
 924                   }
 925               }
 926
 927             else if (c == '!')
 928               if ((c = xml_get_char(ctx)) == '-')
 929                 {
 930                   /* Comment */
 931                   if (!(ctx->flags & (XML_REPORT_COMMENTS | XML_ALLOC_COMMENTS)))
 932                     xml_skip_comment(ctx);
 933                   else
 934                     {
 935                       if (xml_flush_chars(ctx))
 936                         {
 937                           PULL_STATE(CHARS, CHARS_BEFORE_COMMENT);
 938                           xml_pop_chars(ctx);
 939                         }
 940                       xml_push_comment(ctx);
 941                       PULL(COMMENT);
 942                       xml_pop_comment(ctx);
 943                     }
 944                 }
 945               else if (c == '[')
 946                 {
 947                   /* CDATA */
 948                   if (!(ctx->flags & XML_UNFOLD_CDATA))
 949                     xml_append_cdata(ctx);
 950                   else
 951                     {
 952                       if (xml_flush_chars(ctx))
 953                         {
 954                           PULL_STATE(CHARS, CHARS_BEFORE_CDATA);
 955                           xml_pop_chars(ctx);
 956                         }
 957                       xml_push_cdata(ctx);
 958                       PULL(CDATA);
 959                       xml_pop_cdata(ctx);
 960                     }
 961                 }
 962               else
 963                 xml_fatal(ctx, "Unexpected character after '<!'");
 964
 965             else if (c != '/')
 966               {
 967                 /* STag | EmptyElemTag */
 968                 xml_unget_char(ctx);
 969                 if (xml_flush_chars(ctx))
 970                   {
 971                     PULL_STATE(CHARS, CHARS_BEFORE_STAG);
 972                     xml_pop_chars(ctx);
 973                   }
 974
 975                 xml_push_element(ctx);
 976                 PULL(STAG);
 977                 if (ctx->flags & XML_EMPTY_ELEM_TAG)
 978                   goto pop_element;
 979               }
 980
 981             else
 982               {
 983                 /* ETag */
 984                 if (xml_flush_chars(ctx))
 985                   {
 986                     PULL_STATE(CHARS, CHARS_BEFORE_ETAG);
 987                     xml_pop_chars(ctx);
 988                   }
 989
 990                 xml_parse_etag(ctx);
 991 pop_element:
 992                 PULL(ETAG);
 993                 xml_pop_element(ctx);
 994                 if (!ctx->node)
 995                   goto epilog;
 996               }
 997           }
 998
 999 epilog:
1000         /* Misc* */
1001         TRACE(ctx, "entering epilog");
1002         while (1)
1003           {
1004             /* Epilog whitespace is the only place, where a valid document can reach EOF */
1005             if (setjmp(throw_buf))
1006               if (ctx->err_code == XML_ERR_EOF)
1007                 {
1008                   TRACE(ctx, "reached EOF");
1009                   ctx->state = XML_STATE_EOF;
1010                   if (ctx->h_document_end)
1011                     ctx->h_document_end(ctx);
1012       case XML_STATE_EOF:
1013                   ctx->err_code = 0;
1014                   ctx->err_msg = NULL;
1015                   return XML_STATE_EOF;
1016                 }
1017               else
1018                 goto error;
1019             xml_parse_white(ctx, 0);
1020             if (setjmp(throw_buf))
1021               goto error;
1022
1023             /* Misc */
1024             xml_parse_char(ctx, '<');
1025             xml_inc(ctx);
1026             if ((c = xml_get_char(ctx)) == '?')
1027               /* Processing instruction */
1028               if (!(ctx->flags & XML_REPORT_PIS))
1029                 xml_skip_pi(ctx);
1030               else
1031                 {
1032                   xml_push_pi(ctx);
1033                   PULL_STATE(PI, EPILOG_PI);
1034                   xml_pop_pi(ctx);
1035                 }
1036             else if (c == '!')
1037               {
1038                 xml_parse_char(ctx, '-');
1039                 /* Comment */
1040                 if (!(ctx->flags & XML_REPORT_COMMENTS))
1041                   xml_skip_comment(ctx);
1042                 else
1043                   {
1044                     xml_push_comment(ctx);
1045                     PULL_STATE(COMMENT, EPILOG_COMMENT);
1046                     xml_pop_comment(ctx);
1047                   }
1048               }
1049             else
1050               xml_fatal(ctx, "Syntax error in the epilog");
1051           }
1052
1053     }
1054   ASSERT(0);
1055 }
1056
1057 uns
1058 xml_parse(struct xml_context *ctx)
1059 {
1060   ctx->pull = 0;
1061   xml_next(ctx);
1062   return ctx->err_code;
1063 }