ucw-xml/parse.c

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