sherlock/xml/parse.c

   1 /*
   2  *      Sherlock Library -- A simple XML parser
   3  *
   4  *      (c) 2007--2008 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/internals.h"
  16 #include "ucw/fastbuf.h"
  17 #include "ucw/ff-unicode.h"
  18 #include "ucw/unicode.h"
  19 #include "ucw/chartype.h"
  20 #include "ucw/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, ctx->cat_sname, ctx->cat_name, "Expected a name");
  88 }
  89
  90 void
  91 xml_skip_name(struct xml_context *ctx)
  92 {
  93   xml_skip_string(ctx, ctx->cat_sname, ctx->cat_name, "Expected a name");
  94 }
  95
  96 char *
  97 xml_parse_nmtoken(struct xml_context *ctx, struct mempool *pool)
  98 {
  99   /* Nmtoken ::= (NameChar)+ */
 100   return xml_parse_string(ctx, pool, ctx->cat_name, ctx->cat_name, "Expected a nmtoken");
 101 }
 102
 103 /*** Simple literals ***/
 104
 105 char *
 106 xml_parse_system_literal(struct xml_context *ctx, struct mempool *pool)
 107 {
 108   /* SystemLiteral ::= ('"' [^"]* '"') | ("'" [^']* "'") */
 109   char *p = mp_start_noalign(pool, 1);
 110   uns q = xml_parse_quote(ctx), c;
 111   while ((c = xml_get_char(ctx)) != q)
 112     {
 113       p = mp_spread(pool, p, 5);
 114       p = utf8_32_put(p, c);
 115     }
 116   *p++ = 0;
 117   return mp_end(pool, p);
 118 }
 119
 120 char *
 121 xml_parse_pubid_literal(struct xml_context *ctx, struct mempool *pool)
 122 {
 123   /* PubidLiteral ::= '"' PubidChar* '"' | "'" (PubidChar - "'")* "'" */
 124   char *p = mp_start_noalign(pool, 1);
 125   uns q = xml_parse_quote(ctx), c;
 126   while ((c = xml_get_char(ctx)) != q)
 127     {
 128       if (unlikely(!(xml_last_cat(ctx) & XML_CHAR_PUBID)))
 129         xml_fatal(ctx, "Expected a pubid character");
 130       p = mp_spread(pool, p, 2);
 131       *p++ = c;
 132     }
 133   *p++ = 0;
 134   return mp_end(pool, p);
 135 }
 136
 137 /*** Comments ***/
 138
 139 void
 140 xml_push_comment(struct xml_context *ctx)
 141 {
 142   TRACE(ctx, "push_comment");
 143   /* Comment ::= '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'
 144    * Already parsed: '<!-' */
 145   xml_parse_char(ctx, '-');
 146   struct xml_node *n = xml_push_dom(ctx, NULL);
 147   n->type = XML_NODE_COMMENT;
 148   char *p = mp_start_noalign(ctx->pool, 6);
 149   while (1)
 150     {
 151       if (xml_get_char(ctx) == '-')
 152         if (xml_get_char(ctx) == '-')
 153           break;
 154         else
 155           *p++ = '-';
 156       p = utf8_32_put(p, xml_last_char(ctx));
 157       p = mp_spread(ctx->pool, p, 6);
 158     }
 159   xml_parse_char(ctx, '>');
 160   *p = 0;
 161   n->len = p - (char *)mp_ptr(ctx->pool);
 162   n->text = mp_end(ctx->pool, p + 1);
 163   if ((ctx->flags & XML_REPORT_COMMENTS) && ctx->h_comment)
 164     ctx->h_comment(ctx);
 165 }
 166
 167 void
 168 xml_pop_comment(struct xml_context *ctx)
 169 {
 170   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_COMMENTS));
 171   xml_dec(ctx);
 172   TRACE(ctx, "pop_comment");
 173 }
 174
 175 void
 176 xml_skip_comment(struct xml_context *ctx)
 177 {
 178   TRACE(ctx, "skip_comment");
 179   xml_parse_char(ctx, '-');
 180   while (xml_get_char(ctx) != '-' || xml_get_char(ctx) != '-');
 181   xml_parse_char(ctx, '>');
 182   xml_dec(ctx);
 183 }
 184
 185 /*** Processing instructions ***/
 186
 187 void
 188 xml_push_pi(struct xml_context *ctx)
 189 {
 190   TRACE(ctx, "push_pi");
 191   /* Parses a PI to ctx->value and ctx->name:
 192    *   PI ::= '<?' PITarget (S (Char* - (Char* '?>' Char*)))? '?>'
 193    *   PITarget ::= Name - (('X' | 'x') ('M' | 'm') ('L' | 'l'))
 194    * Already parsed: '<?' */
 195   struct xml_node *n = xml_push_dom(ctx, NULL);
 196   n->type = XML_NODE_PI;
 197   n->name = xml_parse_name(ctx, ctx->pool);
 198   if (unlikely(!strcasecmp(n->name, "xml")))
 199     xml_error(ctx, "Reserved PI target");
 200   char *p = mp_start_noalign(ctx->pool, 5);
 201   if (!xml_parse_white(ctx, 0))
 202     xml_parse_seq(ctx, "?>");
 203   else
 204     while (1)
 205       {
 206         if (xml_get_char(ctx) == '?')
 207           if (xml_peek_char(ctx) == '>')
 208             {
 209               xml_skip_char(ctx);
 210               break;
 211             }
 212           else
 213             *p++ = '?';
 214         else
 215           p = utf8_32_put(p, xml_last_char(ctx));
 216         p = mp_spread(ctx->pool, p, 5);
 217       }
 218   *p = 0;
 219   n->len = p - (char *)mp_ptr(ctx->pool);
 220   n->text = mp_end(ctx->pool, p + 1);
 221   if ((ctx->flags & XML_REPORT_PIS) && ctx->h_pi)
 222     ctx->h_pi(ctx);
 223 }
 224
 225 void
 226 xml_pop_pi(struct xml_context *ctx)
 227 {
 228   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_PIS));
 229   xml_dec(ctx);
 230   TRACE(ctx, "pop_pi");
 231 }
 232
 233 void
 234 xml_skip_pi(struct xml_context *ctx)
 235 {
 236   TRACE(ctx, "skip_pi");
 237   if (ctx->flags & XML_VALIDATING)
 238     {
 239       struct mempool_state state;
 240       mp_save(ctx->stack, &state);
 241       if (unlikely(!strcasecmp(xml_parse_name(ctx, ctx->stack), "xml")))
 242         xml_error(ctx, "Reserved PI target");
 243       mp_restore(ctx->stack, &state);
 244       if (!xml_parse_white(ctx, 0))
 245         {
 246           xml_parse_seq(ctx, "?>");
 247           xml_dec(ctx);
 248           return;
 249         }
 250     }
 251   while (1)
 252     if (xml_get_char(ctx) == '?')
 253       if (xml_peek_char(ctx) == '>')
 254         break;
 255   xml_skip_char(ctx);
 256   xml_dec(ctx);
 257 }
 258
 259 /*** Character references ***/
 260
 261 uns
 262 xml_parse_char_ref(struct xml_context *ctx)
 263 {
 264   TRACE(ctx, "parse_char_ref");
 265   /* CharRef ::= '&#' [0-9]+ ';' | '&#x' [0-9a-fA-F]+ ';'
 266    * Already parsed: '&#' */
 267   uns v = 0;
 268   if (xml_get_char(ctx) == 'x')
 269     {
 270       if (!(xml_get_cat(ctx) & XML_CHAR_XDIGIT))
 271         {
 272           xml_error(ctx, "Expected a hexadecimal value of character reference");
 273           goto recover;
 274         }
 275       do
 276         {
 277           v = (v << 4) + Cxvalue(xml_last_char(ctx));
 278         }
 279       while (v < 0x110000 && (xml_get_cat(ctx) & XML_CHAR_XDIGIT));
 280     }
 281   else
 282     {
 283       if (!(xml_last_cat(ctx) & XML_CHAR_DIGIT))
 284         {
 285           xml_error(ctx, "Expected a numeric value of character reference");
 286           goto recover;
 287         }
 288       do
 289         {
 290           v = v * 10 + xml_last_char(ctx) - '0';
 291         }
 292       while (v < 0x110000 && (xml_get_cat(ctx) & XML_CHAR_DIGIT));
 293     }
 294   uns cat = xml_char_cat(v);
 295   if (!(cat & ctx->cat_unrestricted))
 296     {
 297       xml_error(ctx, "Character reference out of range");
 298       goto recover;
 299     }
 300   if (xml_last_char(ctx) == ';')
 301     {
 302       xml_dec(ctx);
 303       return v;
 304     }
 305   xml_error(ctx, "Expected ';'");
 306 recover:
 307   while (xml_last_char(ctx) != ';')
 308     xml_get_char(ctx);
 309   xml_dec(ctx);
 310   return UNI_REPLACEMENT;
 311 }
 312
 313 /*** References to general entities ***/
 314
 315 static void
 316 xml_parse_ref(struct xml_context *ctx)
 317 {
 318   /* Reference ::= EntityRef | CharRef
 319    * EntityRef ::= '&' Name ';'
 320    * Already parsed: '&' */
 321   struct fastbuf *out = &ctx->chars;
 322   if (xml_peek_char(ctx) == '#')
 323     {
 324       xml_skip_char(ctx);
 325       bput_utf8_32(out, xml_parse_char_ref(ctx));
 326     }
 327   else
 328     {
 329       TRACE(ctx, "parse_ge_ref");
 330       struct mempool_state state;
 331       mp_save(ctx->stack, &state);
 332       char *name = xml_parse_name(ctx, ctx->stack);
 333       xml_parse_char(ctx, ';');
 334       struct xml_dtd_entity *ent = xml_dtd_find_entity(ctx, name);
 335       if (!ent)
 336         {
 337           xml_error(ctx, "Unknown entity &%s;", name);
 338           bputc(out, '&');
 339           bputs(out, name);
 340           bputc(out, ';');
 341         }
 342       else if (ent->flags & XML_DTD_ENTITY_TRIVIAL)
 343         {
 344           TRACE(ctx, "Trivial entity &%s;", name);
 345           bputs(out, ent->text);
 346         }
 347       else
 348         {
 349           TRACE(ctx, "Pushed entity &%s;", name);
 350           mp_restore(ctx->stack, &state);
 351           xml_dec(ctx);
 352           xml_push_entity(ctx, ent);
 353           return;
 354         }
 355       mp_restore(ctx->stack, &state);
 356       xml_dec(ctx);
 357     }
 358 }
 359
 360 /*** Character data ***/
 361
 362 void
 363 xml_spout_chars(struct fastbuf *fb)
 364 {
 365   if (fb->bptr < fb->bufend)
 366     return;
 367   struct xml_context *ctx = SKIP_BACK(struct xml_context, chars, fb);
 368   struct mempool *pool = ctx->pool;
 369   if (fb->bufend != fb->buffer)
 370     {
 371       TRACE(ctx, "growing chars");
 372       uns len = fb->bufend - fb->buffer;
 373       uns reported = fb->bstop - fb->buffer;
 374       fb->buffer = mp_expand(pool);
 375       fb->bufend = fb->buffer + mp_avail(pool);
 376       fb->bptr = fb->buffer + len;
 377       fb->bstop = fb->buffer + reported;
 378     }
 379   else
 380     {
 381       TRACE(ctx, "starting chars");
 382       mp_save(pool, &ctx->chars_state);
 383       fb->bptr = fb->buffer = fb->bstop = mp_start_noalign(pool, 2);
 384       fb->bufend = fb->buffer + mp_avail(pool) - 1;
 385     }
 386 }
 387
 388 static inline uns
 389 xml_end_chars(struct xml_context *ctx, char **out)
 390 {
 391   struct fastbuf *fb = &ctx->chars;
 392   uns len = fb->bptr - fb->buffer;
 393   if (len)
 394     {
 395       TRACE(ctx, "ending chars");
 396       *fb->bptr = 0;
 397       *out = mp_end(ctx->pool, fb->bptr + 1);
 398       fb->bufend = fb->bstop = fb->bptr = fb->buffer;
 399     }
 400   return len;
 401 }
 402
 403 static inline uns
 404 xml_report_chars(struct xml_context *ctx, char **out)
 405 {
 406   struct fastbuf *fb = &ctx->chars;
 407   uns len = fb->bptr - fb->buffer;
 408   if (len)
 409     {
 410       *fb->bptr = 0;
 411       *out = fb->bstop;
 412       fb->bstop = fb->bptr;
 413     }
 414   return len;
 415 }
 416
 417 static inline uns
 418 xml_flush_chars(struct xml_context *ctx)
 419 {
 420   char *text, *rtext;
 421   uns len = xml_end_chars(ctx, &text), rlen;
 422   if (len)
 423     {
 424       if (ctx->flags & XML_NO_CHARS)
 425         {
 426           if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_ignorable)
 427             ctx->h_ignorable(ctx, text, len);
 428           mp_restore(ctx->pool, &ctx->chars_state);
 429           return 0;
 430         }
 431       if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_block && (rlen = xml_report_chars(ctx, &rtext)))
 432         ctx->h_block(ctx, rtext, rlen);
 433       if (!(ctx->flags & XML_ALLOC_CHARS) && !(ctx->flags & XML_REPORT_CHARS))
 434         {
 435           mp_restore(ctx->pool, &ctx->chars_state);
 436           return 0;
 437         }
 438       struct xml_node *n = xml_push_dom(ctx, &ctx->chars_state);
 439       n->type = XML_NODE_CHARS;
 440       n->text = text;
 441       n->len = len;
 442       if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_chars)
 443         ctx->h_chars(ctx);
 444     }
 445   return len;
 446 }
 447
 448 static inline void
 449 xml_pop_chars(struct xml_context *ctx)
 450 {
 451   xml_pop_dom(ctx, !(ctx->flags & XML_ALLOC_CHARS));
 452   TRACE(ctx, "pop_chars");
 453 }
 454
 455 static inline void
 456 xml_append_chars(struct xml_context *ctx)
 457 {
 458   TRACE(ctx, "append_chars");
 459   struct fastbuf *out = &ctx->chars;
 460   if (ctx->flags & XML_NO_CHARS)
 461     while (xml_get_char(ctx) != '<')
 462       if (xml_last_cat(ctx) & XML_CHAR_WHITE)
 463         bput_utf8_32(out, xml_last_char(ctx));
 464       else
 465         {
 466           xml_error(ctx, "This element must not contain character data");
 467           while (xml_get_char(ctx) != '<');
 468           break;
 469         }
 470   else
 471     while (xml_get_char(ctx) != '<')
 472       if (xml_last_char(ctx) == '&')
 473         {
 474           xml_inc(ctx);
 475           xml_parse_ref(ctx);
 476         }
 477       else
 478         bput_utf8_32(out, xml_last_char(ctx));
 479   xml_unget_char(ctx);
 480 }
 481
 482 /*** CDATA sections ***/
 483
 484 static void
 485 xml_skip_cdata(struct xml_context *ctx)
 486 {
 487   TRACE(ctx, "skip_cdata");
 488   xml_parse_seq(ctx, "CDATA[");
 489   while (xml_get_char(ctx) != ']' || xml_get_char(ctx) != ']' || xml_get_char(ctx) != '>');
 490   xml_dec(ctx);
 491 }
 492
 493 static void
 494 xml_append_cdata(struct xml_context *ctx)
 495 {
 496   /* CDSect :== '<![CDATA[' (Char* - (Char* ']]>' Char*)) ']]>'
 497    * Already parsed: '<![' */
 498   TRACE(ctx, "append_cdata");
 499   if (ctx->flags & XML_NO_CHARS)
 500     {
 501       xml_error(ctx, "This element must not contain CDATA");
 502       xml_skip_cdata(ctx);
 503       return;
 504     }
 505   xml_parse_seq(ctx, "CDATA[");
 506   struct fastbuf *out = &ctx->chars;
 507   uns rlen;
 508   char *rtext;
 509   if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_block && (rlen = xml_report_chars(ctx, &rtext)))
 510     ctx->h_block(ctx, rtext, rlen);
 511   while (1)
 512     {
 513       if (xml_get_char(ctx) == ']')
 514         {
 515           if (xml_get_char(ctx) == ']')
 516             if (xml_get_char(ctx) == '>')
 517               break;
 518             else
 519               bputc(out, ']');
 520           bputc(out, ']');
 521         }
 522       bput_utf8_32(out, xml_last_char(ctx));
 523     }
 524   if ((ctx->flags & XML_REPORT_CHARS) && ctx->h_cdata && (rlen = xml_report_chars(ctx, &rtext)))
 525     ctx->h_cdata(ctx, rtext, rlen);
 526   xml_dec(ctx);
 527 }
 528
 529 /*** Attribute values ***/
 530
 531 char *
 532 xml_parse_attr_value(struct xml_context *ctx, struct xml_dtd_attr *attr UNUSED)
 533 {
 534   TRACE(ctx, "parse_attr_value");
 535   /* AttValue ::= '"' ([^<&"] | Reference)* '"' | "'" ([^<&'] | Reference)* "'" */
 536   /* FIXME: -- check value constrains / normalize leading/trailing WS and repeated WS */
 537   struct mempool_state state;
 538   uns quote = xml_parse_quote(ctx);
 539   mp_save(ctx->stack, &state);
 540   struct fastbuf *out = &ctx->chars;
 541   struct xml_source *src = ctx->src;
 542   while (1)
 543     {
 544       uns c = xml_get_char(ctx);
 545       if (c == '&')
 546         {
 547           xml_inc(ctx);
 548           xml_parse_ref(ctx);
 549         }
 550       else if (c == quote && src == ctx->src)
 551         break;
 552       else if (c == '<')
 553         xml_error(ctx, "Attribute value must not contain '<'");
 554       else if (xml_last_cat(ctx) & XML_CHAR_WHITE)
 555         bputc(out, ' ');
 556       else
 557         bput_utf8_32(out, c);
 558     }
 559   mp_restore(ctx->stack, &state);
 560   char *text;
 561   return xml_end_chars(ctx, &text) ? text : "";
 562 }
 563
 564 uns
 565 xml_normalize_white(struct xml_context *ctx UNUSED, char *text)
 566 {
 567   char *s = text, *d = text;
 568   while (*s == 0x20)
 569     s++;
 570   while (1)
 571     {
 572       while (*s & ~0x20)
 573         *d++ = *s++;
 574       if (!*s)
 575         break;
 576       while (*++s == 0x20);
 577       *d++ = 0x20;
 578     }
 579   if (d != text && d[-1] == 0x20)
 580     d--;
 581   *d = 0;
 582   return d - text;
 583 }
 584
 585 /*** Attributes ***/
 586
 587 struct xml_attrs_table;
 588
 589 static inline uns
 590 xml_attrs_hash(struct xml_attrs_table *t UNUSED, struct xml_node *e, char *n)
 591 {
 592   return hash_pointer(e) ^ hash_string(n);
 593 }
 594
 595 static inline int
 596 xml_attrs_eq(struct xml_attrs_table *t UNUSED, struct xml_node *e1, char *n1, struct xml_node *e2, char *n2)
 597 {
 598   return (e1 == e2) && !strcmp(n1, n2);
 599 }
 600
 601 static inline void
 602 xml_attrs_init_key(struct xml_attrs_table *t UNUSED, struct xml_attr *a, struct xml_node *e, char *name)
 603 {
 604   a->elem = e;
 605   a->name = name;
 606   a->val = NULL;
 607   a->user = NULL;
 608   slist_add_tail(&e->attrs, &a->n);
 609 }
 610
 611 #define HASH_PREFIX(x) xml_attrs_##x
 612 #define HASH_NODE struct xml_attr
 613 #define HASH_KEY_COMPLEX(x) x elem, x name
 614 #define HASH_KEY_DECL struct xml_node *elem, char *name
 615 #define HASH_TABLE_DYNAMIC
 616 #define HASH_GIVE_EQ
 617 #define HASH_GIVE_HASHFN
 618 #define HASH_GIVE_INIT_KEY
 619 #define HASH_WANT_CLEANUP
 620 #define HASH_WANT_REMOVE
 621 #define HASH_WANT_LOOKUP
 622 #define HASH_WANT_FIND
 623 #define HASH_GIVE_ALLOC
 624 XML_HASH_GIVE_ALLOC
 625 #include "ucw/hashtable.h"
 626
 627 static void
 628 xml_parse_attr(struct xml_context *ctx)
 629 {
 630   TRACE(ctx, "parse_attr");
 631   /* Attribute ::= Name Eq AttValue */
 632   struct xml_node *e = ctx->node;
 633   char *n = xml_parse_name(ctx, ctx->pool);
 634   struct xml_attr *a = xml_attrs_lookup(ctx->tab_attrs, e, n);
 635   xml_parse_eq(ctx);
 636   char *v = xml_parse_attr_value(ctx, NULL);
 637   if (a->val)
 638     {
 639       xml_error(ctx, "Attribute %s is not unique in element <%s>", n, e->name);
 640       return;
 641     }
 642   a->val = v;
 643   if (!e->dtd)
 644     a->dtd = NULL;
 645   else if (!(a->dtd = xml_dtd_find_attr(ctx, e->dtd, a->name)))
 646     xml_error(ctx, "Undefined attribute %s in element <%s>", n, e->name);
 647   else
 648     xml_validate_attr(ctx, a->dtd, a->val);
 649 }
 650
 651 struct xml_attr *
 652 xml_attr_find(struct xml_context *ctx, struct xml_node *node, char *name)
 653 {
 654   return xml_attrs_find(ctx->tab_attrs, node, name);
 655 }
 656
 657 char *
 658 xml_attr_value(struct xml_context *ctx, struct xml_node *node, char *name)
 659 {
 660   struct xml_attr *attr = xml_attrs_find(ctx->tab_attrs, node, name);
 661   if (attr)
 662     return attr->val;
 663   if (!node->dtd)
 664     return NULL;
 665   struct xml_dtd_attr *dtd = xml_dtd_find_attr(ctx, node->dtd, name);
 666   return dtd ? dtd->default_value : NULL;
 667 }
 668
 669 void
 670 xml_attrs_table_init(struct xml_context *ctx)
 671 {
 672   xml_attrs_init(ctx->tab_attrs = xml_hash_new(ctx->pool, sizeof(struct xml_attrs_table)));
 673 }
 674
 675 void
 676 xml_attrs_table_cleanup(struct xml_context *ctx)
 677 {
 678   xml_attrs_cleanup(ctx->tab_attrs);
 679 }
 680
 681 /*** Elements ***/
 682
 683 static uns
 684 xml_validate_element(struct xml_dtd_elem_node *root, struct xml_dtd_elem *elem)
 685 {
 686   if (root->elem)
 687     return elem == root->elem;
 688   else
 689     SLIST_FOR_EACH(struct xml_dtd_elem_node *, son, root->sons)
 690       if (xml_validate_element(son, elem))
 691         return 1;
 692   return 0;
 693 }
 694
 695 static void
 696 xml_push_element(struct xml_context *ctx)
 697 {
 698   TRACE(ctx, "push_element");
 699   /* EmptyElemTag | STag
 700    * EmptyElemTag ::= '<' Name (S  Attribute)* S? '/>'
 701    * STag ::= '<' Name (S  Attribute)* S? '>'
 702    * Already parsed: '<' */
 703   struct xml_node *e = xml_push_dom(ctx, NULL);
 704   clist_init(&e->sons);
 705   e->type = XML_NODE_ELEM;
 706   e->name = xml_parse_name(ctx, ctx->pool);
 707   slist_init(&e->attrs);
 708   if (!e->parent)
 709     {
 710       ctx->dom = e;
 711       if (ctx->doctype && strcmp(e->name, ctx->doctype))
 712         xml_error(ctx, "The root element <%s> does not match the document type <%s>", e->name, ctx->doctype);
 713     }
 714   if (!ctx->dtd)
 715     e->dtd = NULL;
 716   else if (!(e->dtd = xml_dtd_find_elem(ctx, e->name)))
 717     xml_error(ctx, "Undefined element <%s>", e->name);
 718   else
 719     {
 720       struct xml_dtd_elem *dtd = e->dtd, *parent_dtd = e->parent ? e->parent->dtd : NULL;
 721       if (dtd->type == XML_DTD_ELEM_MIXED)
 722         ctx->flags &= ~XML_NO_CHARS;
 723       else
 724         ctx->flags |= XML_NO_CHARS;
 725       if (parent_dtd)
 726         if (parent_dtd->type == XML_DTD_ELEM_EMPTY)
 727           xml_error(ctx, "Empty element must not contain children");
 728         else if (parent_dtd->type != XML_DTD_ELEM_ANY)
 729           {
 730             // FIXME: validate regular expressions
 731             if (!xml_validate_element(parent_dtd->node, dtd))
 732               xml_error(ctx, "Unexpected element <%s>", e->name);
 733           }
 734     }
 735   while (1)
 736     {
 737       uns white = xml_parse_white(ctx, 0);
 738       uns c = xml_get_char(ctx);
 739       if (c == '/')
 740         {
 741           xml_parse_char(ctx, '>');
 742           ctx->flags |= XML_EMPTY_ELEM_TAG;
 743           break;
 744         }
 745       else if (c == '>')
 746         break;
 747       else if (!white)
 748         xml_fatal_expected_white(ctx);
 749       xml_unget_char(ctx);
 750       xml_parse_attr(ctx);
 751     }
 752   if (e->dtd)
 753     SLIST_FOR_EACH(struct xml_dtd_attr *, a, e->dtd->attrs)
 754       if (a->default_mode == XML_ATTR_REQUIRED)
 755         {
 756           if (!xml_attrs_find(ctx->tab_attrs, e, a->name))
 757             xml_error(ctx, "Missing required attribute %s in element <%s>", a->name, e->name);
 758         }
 759       else if (a->default_mode != XML_ATTR_IMPLIED && ctx->flags & XML_ALLOC_DEFAULT_ATTRS)
 760         {
 761           struct xml_attr *attr = xml_attrs_lookup(ctx->tab_attrs, e, a->name);
 762           if (!attr->val)
 763             attr->val = a->default_value;
 764         }
 765   if ((ctx->flags & XML_REPORT_TAGS) && ctx->h_stag)
 766     ctx->h_stag(ctx);
 767 }
 768
 769 static void
 770 xml_pop_element(struct xml_context *ctx)
 771 {
 772   TRACE(ctx, "pop_element");
 773   if ((ctx->flags & XML_REPORT_TAGS) && ctx->h_etag)
 774     ctx->h_etag(ctx);
 775   struct xml_node *e = ctx->node;
 776   uns free = !(ctx->flags & XML_ALLOC_TAGS);
 777   if (free)
 778     {
 779       if (!e->parent)
 780         ctx->dom = NULL;
 781       /* Restore hash table of attributes */
 782       SLIST_FOR_EACH(struct xml_attr *, a, e->attrs)
 783         xml_attrs_remove(ctx->tab_attrs, a);
 784       struct xml_node *n;
 785       while (n = clist_head(&e->sons))
 786         {
 787           if (n->type == XML_NODE_ELEM)
 788             {
 789               SLIST_FOR_EACH(struct xml_attr *, a, n->attrs)
 790                 xml_attrs_remove(ctx->tab_attrs, a);
 791               clist_insert_list_after(&n->sons, &n->n);
 792             }
 793           clist_remove(&n->n);
 794         }
 795     }
 796   xml_pop_dom(ctx, free);
 797   xml_dec(ctx);
 798 }
 799
 800 static void
 801 xml_parse_etag(struct xml_context *ctx)
 802 {
 803  /* ETag ::= '</' Name S? '>'
 804   * Already parsed: '<' */
 805   struct xml_node *e = ctx->node;
 806   ASSERT(e);
 807   char *n = e->name;
 808   while (*n)
 809     {
 810       uns c;
 811       n = utf8_32_get(n, &c);
 812       if (xml_get_char(ctx) != c)
 813         goto recover;
 814     }
 815   xml_parse_white(ctx, 0);
 816   if (xml_get_char(ctx) != '>')
 817     {
 818 recover:
 819       xml_error(ctx, "Invalid ETag, expected </%s>", e->name);
 820       while (xml_get_char(ctx) != '>');
 821     }
 822   xml_dec(ctx);
 823 }
 824
 825 /*** Document type declaration ***/
 826
 827 static void
 828 xml_parse_doctype_decl(struct xml_context *ctx)
 829 {
 830   TRACE(ctx, "parse_doctype_decl");
 831   /* doctypedecl ::= '<!DOCTYPE' S  Name (S  ExternalID)? S? ('[' intSubset ']' S?)? '>'
 832    * Already parsed: '<!'
 833    * Terminated before '[' or '>' */
 834   if (ctx->doctype)
 835     xml_fatal(ctx, "Multiple document types not allowed");
 836   xml_parse_seq(ctx, "DOCTYPE");
 837   xml_parse_white(ctx, 1);
 838   ctx->doctype = xml_parse_name(ctx, ctx->pool);
 839   TRACE(ctx, "doctype=%s", ctx->doctype);
 840   uns c;
 841   if (xml_parse_white(ctx, 0) && ((c = xml_peek_char(ctx)) == 'S' || c == 'P'))
 842     {
 843       if (c == 'S')
 844         {
 845           xml_parse_seq(ctx, "SYSTEM");
 846           xml_parse_white(ctx, 1);
 847           ctx->system_id = xml_parse_system_literal(ctx, ctx->pool);
 848         }
 849       else
 850         {
 851           xml_parse_seq(ctx, "PUBLIC");
 852           xml_parse_white(ctx, 1);
 853           ctx->public_id = xml_parse_pubid_literal(ctx, ctx->pool);
 854           xml_parse_white(ctx, 1);
 855           ctx->system_id = xml_parse_system_literal(ctx, ctx->pool);
 856         }
 857       xml_parse_white(ctx, 0);
 858       ctx->flags |= XML_HAS_EXTERNAL_SUBSET;
 859     }
 860   if (xml_peek_char(ctx) == '[')
 861     {
 862       ctx->flags |= XML_HAS_INTERNAL_SUBSET;
 863       xml_skip_char(ctx);
 864       xml_inc(ctx);
 865     }
 866   if (ctx->h_doctype_decl)
 867     ctx->h_doctype_decl(ctx);
 868 }
 869
 870
 871
 872 ///////////////////////////////////////////////////////////////////////////////////////////////////////////
 873
 874 /* DTD: Internal subset */
 875
 876 static void
 877 xml_parse_subset(struct xml_context *ctx, uns external)
 878 {
 879   // FIXME:
 880   // -- comments/pi have no parent
 881   // -- conditional sections in external subset
 882   // -- check corectness of parameter entities
 883
 884   /* '[' intSubset ']'
 885    * intSubset :== (markupdecl | DeclSep)
 886    * Already parsed: '['
 887    *
 888    * extSubsetDecl ::= ( markupdecl | conditionalSect | DeclSep)*
 889    */
 890   while (1)
 891     {
 892       xml_parse_white(ctx, 0);
 893       uns c = xml_get_char(ctx);
 894       xml_inc(ctx);
 895       if (c == '<')
 896         if ((c = xml_get_char(ctx)) == '!')
 897           switch (c = xml_get_char(ctx))
 898             {
 899               case '-':
 900                 xml_push_comment(ctx);
 901                 xml_pop_comment(ctx);
 902                 break;
 903               case 'N':
 904                 xml_parse_seq(ctx, "OTATION");
 905                 xml_parse_notation_decl(ctx);
 906                 break;
 907               case 'E':
 908                 if ((c = xml_get_char(ctx)) == 'N')
 909                   {
 910                     xml_parse_seq(ctx, "TITY");
 911                     xml_parse_entity_decl(ctx);
 912                   }
 913                 else if (c == 'L')
 914                   {
 915                     xml_parse_seq(ctx, "EMENT");
 916                     xml_parse_element_decl(ctx);
 917                   }
 918                 else
 919                   goto invalid_markup;
 920                 break;
 921               case 'A':
 922                 xml_parse_seq(ctx, "TTLIST");
 923                 xml_parse_attr_list_decl(ctx);
 924                 break;
 925               default:
 926                 goto invalid_markup;
 927             }
 928         else if (c == '?')
 929           {
 930             xml_push_pi(ctx);
 931             xml_pop_pi(ctx);
 932           }
 933         else
 934           goto invalid_markup;
 935       else if (c == '%')
 936         xml_parse_pe_ref(ctx);
 937       else if (c == ']' && !external)
 938         {
 939           break;
 940         }
 941       else if (c == '>' && external)
 942         {
 943           break;
 944         }
 945       else
 946         goto invalid_markup;
 947     }
 948   xml_dec(ctx);
 949   return;
 950 invalid_markup: ;
 951   xml_fatal(ctx, "Invalid markup in the %s subset", external ? "external" : "internal");
 952 }
 953
 954 /*** The State Machine ***/
 955
 956 uns
 957 xml_next(struct xml_context *ctx)
 958 {
 959   /* A nasty state machine */
 960
 961 #define PULL(x) do { if (ctx->pull & XML_PULL_##x) return ctx->state = XML_STATE_##x; case XML_STATE_##x: ; } while (0)
 962 #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)
 963
 964   TRACE(ctx, "xml_next (state=%u)", ctx->state);
 965   jmp_buf throw_buf;
 966   ctx->throw_buf = &throw_buf;
 967   if (setjmp(throw_buf))
 968     {
 969 error:
 970       if (ctx->err_code == XML_ERR_EOF && ctx->h_fatal)
 971         ctx->h_fatal(ctx);
 972       TRACE(ctx, "raised fatal error");
 973       return ctx->state = XML_STATE_EOF;
 974     }
 975   uns c;
 976   switch (ctx->state)
 977     {
 978       case XML_STATE_START:
 979         TRACE(ctx, "entering prolog");
 980         ctx->flags |= XML_SRC_DOCUMENT | XML_SRC_EXPECTED_DECL;
 981         if (ctx->h_document_start)
 982           ctx->h_document_start(ctx);
 983         /* XMLDecl */
 984         xml_refill(ctx);
 985         if (ctx->h_xml_decl)
 986           ctx->h_xml_decl(ctx);
 987         PULL(XML_DECL);
 988
 989         /* Misc* (doctypedecl Misc*)? */
 990         while (1)
 991           {
 992             xml_parse_white(ctx, 0);
 993             xml_parse_char(ctx, '<');
 994             xml_inc(ctx);
 995             if ((c = xml_get_char(ctx)) == '?')
 996               /* Processing intruction */
 997               if (!(ctx->flags & XML_REPORT_PIS))
 998                 xml_skip_pi(ctx);
 999               else
1000                 {
1001                   xml_push_pi(ctx);
1002                   PULL_STATE(PI, PROLOG_PI);
1003                   xml_pop_pi(ctx);
1004                 }
1005             else if (c != '!')
1006               {
1007                 /* Found the root tag */
1008                 xml_unget_char(ctx);
1009                 goto first_tag;
1010               }
1011             else if (xml_get_char(ctx) == '-')
1012               if (!(ctx->flags & XML_REPORT_COMMENTS))
1013                 xml_skip_comment(ctx);
1014               else
1015                 {
1016                   xml_push_comment(ctx);
1017                   PULL_STATE(COMMENT, PROLOG_COMMENT);
1018                   xml_pop_comment(ctx);
1019                 }
1020             else
1021               {
1022                 /* DocTypeDecl */
1023                 xml_unget_char(ctx);
1024                 xml_parse_doctype_decl(ctx);
1025                 PULL(DOCTYPE_DECL);
1026                 if (ctx->flags & XML_HAS_DTD)
1027                   if (ctx->flags & XML_PARSE_DTD)
1028                     {
1029                       xml_dtd_init(ctx);
1030                       if (ctx->h_dtd_start)
1031                         ctx->h_dtd_start(ctx);
1032                       if (ctx->flags & XML_HAS_INTERNAL_SUBSET)
1033                         {
1034                           xml_parse_subset(ctx, 0);
1035                           xml_dec(ctx);
1036                         }
1037                       if (ctx->flags & XML_HAS_EXTERNAL_SUBSET)
1038                         {
1039                           struct xml_dtd_entity ent = {
1040                             .system_id = ctx->system_id,
1041                             .public_id = ctx->public_id,
1042                           };
1043                           xml_parse_white(ctx, 0);
1044                           xml_parse_char(ctx, '>');
1045                           xml_unget_char(ctx);
1046                           ASSERT(ctx->h_resolve_entity);
1047                           ctx->h_resolve_entity(ctx, &ent);
1048                           ctx->flags |= XML_SRC_EXPECTED_DECL;
1049                           xml_parse_subset(ctx, 1);
1050                           xml_unget_char(ctx);;
1051                         }
1052                       if (ctx->h_dtd_end)
1053                         ctx->h_dtd_end(ctx);
1054                     }
1055                   else if (ctx->flags & XML_HAS_INTERNAL_SUBSET)
1056                     xml_skip_internal_subset(ctx);
1057                 xml_parse_white(ctx, 0);
1058                 xml_parse_char(ctx, '>');
1059                 xml_dec(ctx);
1060               }
1061           }
1062
1063       case XML_STATE_CHARS:
1064
1065         while (1)
1066           {
1067             if (xml_peek_char(ctx) != '<')
1068               {
1069                 /* CharData */
1070                 xml_append_chars(ctx);
1071                 continue;
1072               }
1073             else
1074               xml_skip_char(ctx);
1075             xml_inc(ctx);
1076 first_tag:
1077
1078             if ((c = xml_get_char(ctx)) == '?')
1079               {
1080                 /* PI */
1081                 if (!(ctx->flags & (XML_REPORT_PIS | XML_ALLOC_PIS)))
1082                   xml_skip_pi(ctx);
1083                 else
1084                   {
1085                     if (xml_flush_chars(ctx))
1086                       {
1087                         PULL_STATE(CHARS, CHARS_BEFORE_PI);
1088                         xml_pop_chars(ctx);
1089                       }
1090                     xml_push_pi(ctx);
1091                     PULL(PI);
1092                     xml_pop_pi(ctx);
1093                   }
1094               }
1095
1096             else if (c == '!')
1097               if ((c = xml_get_char(ctx)) == '-')
1098                 {
1099                   /* Comment */
1100                   if (!(ctx->flags & (XML_REPORT_COMMENTS | XML_ALLOC_COMMENTS)))
1101                     xml_skip_comment(ctx);
1102                   else
1103                     {
1104                       if (xml_flush_chars(ctx))
1105                         {
1106                           PULL_STATE(CHARS, CHARS_BEFORE_COMMENT);
1107                           xml_pop_chars(ctx);
1108                         }
1109                       xml_push_comment(ctx);
1110                       PULL(COMMENT);
1111                       xml_pop_comment(ctx);
1112                     }
1113                 }
1114               else if (c == '[')
1115                 {
1116                   /* CDATA */
1117                   xml_append_cdata(ctx);
1118                 }
1119               else
1120                 xml_fatal(ctx, "Unexpected character after '<!'");
1121
1122             else if (c != '/')
1123               {
1124                 /* STag | EmptyElemTag */
1125                 xml_unget_char(ctx);
1126                 if (xml_flush_chars(ctx))
1127                   {
1128                     PULL_STATE(CHARS, CHARS_BEFORE_STAG);
1129                     xml_pop_chars(ctx);
1130                   }
1131
1132                 xml_push_element(ctx);
1133                 PULL(STAG);
1134                 if (ctx->flags & XML_EMPTY_ELEM_TAG)
1135                   goto pop_element;
1136               }
1137
1138             else
1139               {
1140                 /* ETag */
1141                 if (xml_flush_chars(ctx))
1142                   {
1143                     PULL_STATE(CHARS, CHARS_BEFORE_ETAG);
1144                     xml_pop_chars(ctx);
1145                   }
1146
1147                 xml_parse_etag(ctx);
1148 pop_element:
1149                 PULL(ETAG);
1150                 xml_pop_element(ctx);
1151                 if (!ctx->node)
1152                   goto epilog;
1153               }
1154           }
1155
1156 epilog:
1157         /* Misc* */
1158         TRACE(ctx, "entering epilog");
1159         while (1)
1160           {
1161             /* Epilog whitespace is the only place, where a valid document can reach EOF */
1162             if (setjmp(throw_buf))
1163               if (ctx->err_code == XML_ERR_EOF)
1164                 {
1165                   TRACE(ctx, "reached EOF");
1166                   ctx->state = XML_STATE_EOF;
1167                   if (ctx->h_document_end)
1168                     ctx->h_document_end(ctx);
1169       case XML_STATE_EOF:
1170                   ctx->err_code = 0;
1171                   ctx->err_msg = NULL;
1172                   return XML_STATE_EOF;
1173                 }
1174               else
1175                 goto error;
1176             xml_parse_white(ctx, 0);
1177             if (setjmp(throw_buf))
1178               goto error;
1179
1180             /* Misc */
1181             xml_parse_char(ctx, '<');
1182             xml_inc(ctx);
1183             if ((c = xml_get_char(ctx)) == '?')
1184               /* Processing instruction */
1185               if (!(ctx->flags & XML_REPORT_PIS))
1186                 xml_skip_pi(ctx);
1187               else
1188                 {
1189                   xml_push_pi(ctx);
1190                   PULL_STATE(PI, EPILOG_PI);
1191                   xml_pop_pi(ctx);
1192                 }
1193             else if (c == '!')
1194               {
1195                 xml_parse_char(ctx, '-');
1196                 /* Comment */
1197                 if (!(ctx->flags & XML_REPORT_COMMENTS))
1198                   xml_skip_comment(ctx);
1199                 else
1200                   {
1201                     xml_push_comment(ctx);
1202                     PULL_STATE(COMMENT, EPILOG_COMMENT);
1203                     xml_pop_comment(ctx);
1204                   }
1205               }
1206             else
1207               xml_fatal(ctx, "Syntax error in the epilog");
1208           }
1209
1210     }
1211   ASSERT(0);
1212 }
1213
1214 uns
1215 xml_next_state(struct xml_context *ctx, uns pull)
1216 {
1217   uns saved = ctx->pull;
1218   ctx->pull = pull;
1219   uns res = xml_next(ctx);
1220   ctx->pull = saved;
1221   return res;
1222 }
1223
1224 uns
1225 xml_skip_element(struct xml_context *ctx)
1226 {
1227   ASSERT(ctx->state == XML_STATE_STAG);
1228   struct xml_node *node = ctx->node;
1229   uns saved = ctx->pull, res;
1230   ctx->pull = XML_PULL_ETAG;
1231   while ((res = xml_next(ctx)) && ctx->node != node);
1232   ctx->pull = saved;
1233   return res;
1234 }
1235
1236 uns
1237 xml_parse(struct xml_context *ctx)
1238 {
1239   /* This cycle should run only once unless the user overrides the value of ctx->pull in a SAX handler */
1240   do
1241     {
1242       ctx->pull = 0;
1243     }
1244   while (xml_next(ctx));
1245   return ctx->err_code;
1246 }
1247
1248 char *
1249 xml_merge_chars(struct xml_context *ctx UNUSED, struct xml_node *node, struct mempool *pool)
1250 {
1251   ASSERT(node->type == XML_NODE_ELEM);
1252   char *p = mp_start_noalign(pool, 1);
1253   XML_NODE_FOR_EACH(son, node)
1254     if (son->type == XML_NODE_CHARS)
1255       {
1256         p = mp_spread(pool, p, son->len + 1);
1257         memcpy(p, son->text, son->len);
1258         p += son->len;
1259       }
1260   *p++ = 0;
1261   return mp_end(pool, p);
1262 }
1263
1264 static char *
1265 xml_append_dom_chars(char *p, struct mempool *pool, struct xml_node *node)
1266 {
1267   XML_NODE_FOR_EACH(son, node)
1268     if (son->type == XML_NODE_CHARS)
1269       {
1270         p = mp_spread(pool, p, son->len + 1);
1271         memcpy(p, son->text, son->len);
1272         p += son->len;
1273       }
1274     else if (son->type == XML_NODE_ELEM)
1275       p = xml_append_dom_chars(p, pool, son);
1276   return p;
1277 }
1278
1279 char *
1280 xml_merge_dom_chars(struct xml_context *ctx UNUSED, struct xml_node *node, struct mempool *pool)
1281 {
1282   ASSERT(node->type == XML_NODE_ELEM);
1283   char *p = mp_start_noalign(pool, 1);
1284   p = xml_append_dom_chars(p, pool, node);
1285   *p++ = 0;
1286   return mp_end(pool, p);
1287 }