sherlock/xml/xml.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 /* TODO:
  11  * - iface
  12  * - stack-like memory handling where possible
  13  */
  14
  15 #define LOCAL_DEBUG
  16
  17 #include "lib/lib.h"
  18 #include "lib/mempool.h"
  19 #include "lib/fastbuf.h"
  20 #include "lib/ff-unicode.h"
  21 #include "lib/ff-binary.h"
  22 #include "lib/chartype.h"
  23 #include "lib/unicode.h"
  24 #include "lib/hashfunc.h"
  25 #include "lib/stkstring.h"
  26 #include "lib/unaligned.h"
  27 #include "charset/charconv.h"
  28 #include "charset/fb-charconv.h"
  29 #include "sherlock/xml/xml.h"
  30
  31 #include <setjmp.h>
  32
  33 /*** Debugging ***/
  34
  35 #ifdef LOCAL_DEBUG
  36 #define TRACE(c, f, p...) do { DBG("XML %u: " f, xml_row(c), ##p); } while(0)
  37 #else
  38 #define TRACE(c, f, p...) do {} while(0)
  39 #endif
  40
  41 static uns xml_row(struct xml_context *ctx);
  42
  43 /*** Error handling ***/
  44
  45 static void NONRET
  46 xml_throw(struct xml_context *ctx)
  47 {
  48   ASSERT(ctx->err_code && ctx->throw_buf);
  49   longjmp(*(jmp_buf *)ctx->throw_buf, ctx->err_code);
  50 }
  51
  52 static void
  53 xml_warn(struct xml_context *ctx, const char *format, ...)
  54 {
  55   if (ctx->h_warn)
  56     {
  57       va_list args;
  58       va_start(args, format);
  59       ctx->err_msg = stk_vprintf(format, args);
  60       ctx->err_code = XML_ERR_WARN;
  61       va_end(args);
  62       ctx->h_warn(ctx);
  63       ctx->err_msg = NULL;
  64       ctx->err_code = XML_ERR_OK;
  65     }
  66 }
  67
  68 static void
  69 xml_error(struct xml_context *ctx, const char *format, ...)
  70 {
  71   if (ctx->h_error)
  72     {
  73       va_list args;
  74       va_start(args, format);
  75       ctx->err_msg = stk_vprintf(format, args);
  76       ctx->err_code = XML_ERR_ERROR;
  77       va_end(args);
  78       ctx->h_error(ctx);
  79       ctx->err_msg = NULL;
  80       ctx->err_code = XML_ERR_OK;
  81     }
  82 }
  83
  84 static void NONRET
  85 xml_fatal(struct xml_context *ctx, const char *format, ...)
  86 {
  87   va_list args;
  88   va_start(args, format);
  89   ctx->err_msg = mp_vprintf(ctx->pool, format, args);
  90   ctx->err_code = XML_ERR_FATAL;
  91   ctx->state = XML_STATE_FATAL;
  92   va_end(args);
  93   if (ctx->h_fatal)
  94     ctx->h_fatal(ctx);
  95   xml_throw(ctx);
  96 }
  97
  98 /*** Charecter categorization ***/
  99
 100 #include "obj/sherlock/xml/xml-ucat.h"
 101
 102 static inline uns
 103 xml_char_cat(uns c)
 104 {
 105   if (c < 0x10000)
 106     return 1U << xml_char_tab2[(c & 0xff) + xml_char_tab1[c >> 8]];
 107   else if (likely(c < 0x110000))
 108     return 1U << xml_char_tab3[c >> 16];
 109   else
 110     return 1;
 111 }
 112
 113 /*** Generic UTF decoding ***/
 114
 115 static uns
 116 bget_utf16_le_slow(struct fastbuf *fb, uns repl)
 117 {
 118   if ((int)bpeekc(fb) < 0)
 119     return ~0U;
 120   uns u = bgetw_le(fb), x, y;
 121   if ((int)u < 0)
 122     return repl;
 123   if ((x = u - 0xd800) >= 0x800)
 124     return u;
 125   if (x >= 0x400 || (int)bpeekc(fb) < 0 || (y = bgetw_le(fb) - 0xdc00) >= 0x400)
 126     return repl;
 127   return 0x10000 + (x << 10) + y;
 128 }
 129
 130 static uns
 131 bget_utf16_be_slow(struct fastbuf *fb, uns repl)
 132 {
 133   if ((int)bpeekc(fb) < 0)
 134     return ~0U;
 135   uns u = bgetw_be(fb), x, y;
 136   if ((int)u < 0)
 137     return repl;
 138   if ((x = u - 0xd800) >= 0x800)
 139     return u;
 140   if (x >= 0x400 || (int)bpeekc(fb) < 0 || (y = bgetw_be(fb) - 0xdc00) >= 0x400)
 141     return repl;
 142   return 0x10000 + (x << 10) + y;
 143 }
 144
 145 static inline uns
 146 bget_utf16_le_repl(struct fastbuf *fb, uns repl)
 147 {
 148   uns u;
 149   if (bavailr(fb) >= 4)
 150     {
 151       fb->bptr = utf16_le_get_repl(fb->bptr, &u, repl);
 152       return u;
 153     }
 154   else
 155     return bget_utf16_le_slow(fb, repl);
 156 }
 157
 158 static inline uns
 159 bget_utf16_be_repl(struct fastbuf *fb, uns repl)
 160 {
 161   uns u;
 162   if (bavailr(fb) >= 4)
 163     {
 164       fb->bptr = utf16_be_get_repl(fb->bptr, &u, repl);
 165       return u;
 166     }
 167   else
 168     return bget_utf16_be_slow(fb, repl);
 169 }
 170
 171 /*** Memory management ***/
 172
 173 static void NONRET
 174 xml_fatal_nested(struct xml_context *ctx)
 175 {
 176   xml_fatal(ctx, "Entity not nested correctly");
 177 }
 178
 179 static inline void
 180 xml_inc(struct xml_context *ctx)
 181 {
 182   /* Called after the first character of a block */
 183   TRACE(ctx, "inc");
 184   ctx->depth++;
 185 }
 186
 187 static inline void
 188 xml_dec(struct xml_context *ctx)
 189 {
 190   /* Called after the last character of a block */
 191   TRACE(ctx, "dec");
 192   if (unlikely(!ctx->depth--))
 193     xml_fatal_nested(ctx);
 194 }
 195
 196 static inline void
 197 xml_push(struct xml_context *ctx)
 198 {
 199   TRACE(ctx, "push");
 200   struct xml_stack *s = mp_alloc(ctx->pool, sizeof(*s));
 201   mp_save(ctx->pool, &s->saved_pool);
 202   s->saved_flags = ctx->flags;
 203   s->next = ctx->stack;
 204   ctx->stack = s;
 205   xml_inc(ctx);
 206 }
 207
 208 static inline void
 209 xml_pop(struct xml_context *ctx)
 210 {
 211   TRACE(ctx, "pop");
 212   xml_dec(ctx);
 213   struct xml_stack *s = ctx->stack;
 214   ASSERT(s);
 215   ctx->stack = s->next;
 216   ctx->flags = s->saved_flags;
 217   mp_restore(ctx->pool, &s->saved_pool);
 218 }
 219
 220 #define XML_HASH_HDR_SIZE ALIGN_TO(sizeof(void *), CPU_STRUCT_ALIGN)
 221 #define XML_HASH_GIVE_ALLOC struct HASH_PREFIX(table); \
 222   static inline void *HASH_PREFIX(alloc)(struct HASH_PREFIX(table) *t, uns size) \
 223   { return mp_alloc(*(void **)((void *)t - XML_HASH_HDR_SIZE), size); } \
 224   static inline void HASH_PREFIX(free)(struct HASH_PREFIX(table) *t UNUSED, void *p UNUSED) {}
 225
 226 static void *
 227 xml_hash_new(struct mempool *pool, uns size)
 228 {
 229   void *tab = mp_alloc_zero(pool, size + XML_HASH_HDR_SIZE);
 230   *(void **)tab = pool;
 231   return tab + XML_HASH_HDR_SIZE;
 232 }
 233
 234 /*** Reading of document/external entities ***/
 235
 236 static void NONRET
 237 xml_eof(struct xml_context *ctx)
 238 {
 239   ctx->err_msg = "Unexpected EOF";
 240   ctx->err_code = XML_ERR_EOF;
 241   xml_throw(ctx);
 242 }
 243
 244 static inline void
 245 xml_add_char(u32 **bstop, uns c)
 246 {
 247   *(*bstop)++ = c;
 248   *(*bstop)++ = xml_char_cat(c);
 249 }
 250
 251 static struct xml_source *
 252 xml_push_source(struct xml_context *ctx, uns flags)
 253 {
 254   xml_push(ctx);
 255   struct xml_source *src = ctx->src;
 256   if (src)
 257     {
 258       src->bptr = ctx->bptr;
 259       src->bstop = ctx->bstop;
 260     }
 261   src = mp_alloc_zero(ctx->pool, sizeof(*src));
 262   src->next = ctx->src;
 263   src->saved_depth = ctx->depth;
 264   ctx->src = src;
 265   ctx->flags = (ctx->flags & ~(XML_FLAG_SRC_EOF | XML_FLAG_SRC_EXPECTED_DECL | XML_FLAG_SRC_NEW_LINE | XML_FLAG_SRC_SURROUND | XML_FLAG_SRC_DOCUMENT)) | flags;
 266   ctx->bstop = ctx->bptr = src->buf;
 267   ctx->depth = 0;
 268   if (flags & XML_FLAG_SRC_SURROUND)
 269     xml_add_char(&ctx->bstop, 0x20);
 270   return src;
 271 }
 272
 273 static void
 274 xml_pop_source(struct xml_context *ctx)
 275 {
 276   TRACE(ctx, "xml_pop_source");
 277   if (unlikely(ctx->depth != 0))
 278     xml_fatal_nested(ctx);
 279   struct xml_source *src = ctx->src;
 280   ASSERT(src);
 281   bclose(src->fb);
 282   ctx->depth = src->saved_depth;
 283   ctx->src = src = src->next;
 284   if (src)
 285     {
 286       ctx->bptr = src->bptr;
 287       ctx->bstop = src->bstop;
 288     }
 289   xml_pop(ctx);
 290   if (unlikely(!src))
 291     xml_eof(ctx);
 292 }
 293
 294 static void xml_refill_utf8(struct xml_context *ctx);
 295
 296 static void
 297 xml_push_entity(struct xml_context *ctx, struct xml_dtd_ent *ent)
 298 {
 299   TRACE(ctx, "xml_push_entity");
 300   uns cat1 = ctx->src->refill_cat1;
 301   uns cat2 = ctx->src->refill_cat2;
 302   struct xml_source *src = xml_push_source(ctx, 0);
 303   src->refill_cat1 = cat1;
 304   src->refill_cat2 = cat2;
 305   if (ent->flags & XML_DTD_ENT_EXTERNAL)
 306     xml_fatal(ctx, "External entities not implemented"); // FIXME
 307   else
 308     {
 309       fbbuf_init_read(src->fb = &src->wrap_fb, ent->text, ent->len, 0);
 310       src->refill = xml_refill_utf8;
 311     }
 312 }
 313
 314 void
 315 xml_set_source(struct xml_context *ctx, struct fastbuf *fb)
 316 {
 317   TRACE(ctx, "xml_set_source");
 318   ASSERT(!ctx->src);
 319   struct xml_source *src = xml_push_source(ctx, XML_FLAG_SRC_DOCUMENT | XML_FLAG_SRC_EXPECTED_DECL);
 320   src->fb = fb;
 321 }
 322
 323 static uns
 324 xml_error_restricted(struct xml_context *ctx, uns c)
 325 {
 326   xml_error(ctx, "Restricted char U+%04X", c);
 327   return UNI_REPLACEMENT;
 328 }
 329
 330 static void xml_parse_decl(struct xml_context *ctx);
 331
 332 #define REFILL(ctx, func, params...)                                                    \
 333   struct xml_source *src = ctx->src;                                                    \
 334   struct fastbuf *fb = src->fb;                                                         \
 335   if (ctx->bptr == ctx->bstop)                                                          \
 336     ctx->bptr = ctx->bstop = src->buf;                                                  \
 337   uns f = ctx->flags, c, t1 = src->refill_cat1, t2 = src->refill_cat2, row = src->row;  \
 338   u32 *bend = src->buf + ARRAY_SIZE(src->buf), *bstop = ctx->bstop,                     \
 339       *last_0xd = (f & XML_FLAG_SRC_NEW_LINE) ? bstop : bend;                           \
 340   do                                                                                    \
 341     {                                                                                   \
 342       c = func(fb, ##params);                                                           \
 343       uns t = xml_char_cat(c);                                                          \
 344       if (t & t1)                                                                       \
 345         /* Typical branch */                                                            \
 346         *bstop++ = c, *bstop++ = t;                                                     \
 347       else if (t & t2)                                                                  \
 348         {                                                                               \
 349           /* New line */                                                                \
 350           /* XML 1.0: 0xA | 0xD | 0xD 0xA */                                            \
 351           /* XML 1.1: 0xA | 0xD | 0xD 0xA | 0x85 | 0xD 0x85 | 0x2028 */                 \
 352           if (c == 0xd)                                                                 \
 353             last_0xd = bstop + 2;                                                       \
 354           else if (c != 0x2028 && last_0xd == bstop)                                    \
 355             {                                                                           \
 356               last_0xd = bend;                                                          \
 357               continue;                                                                 \
 358             }                                                                           \
 359           xml_add_char(&bstop, 0xa), row++;                                             \
 360         }                                                                               \
 361       else if (c == '>')                                                                \
 362         {                                                                               \
 363           /* Used only in XML/TextDecl to switch the encoding */                        \
 364           *bstop++ = c, *bstop++ = t;                                                   \
 365           break;                                                                        \
 366         }                                                                               \
 367       else if ((int)c >= 0)                                                             \
 368         /* Restricted character */                                                      \
 369         xml_add_char(&bstop, xml_error_restricted(ctx, c));                             \
 370       else                                                                              \
 371         {                                                                               \
 372           /* EOF */                                                                     \
 373           if (f & XML_FLAG_SRC_SURROUND)                                                \
 374             xml_add_char(&bstop, 0x20);                                                 \
 375           f |= XML_FLAG_SRC_EOF;                                                        \
 376           break;                                                                        \
 377         }                                                                               \
 378     }                                                                                   \
 379   while (bstop < bend);                                                                 \
 380   ctx->flags = (last_0xd == bstop) ? f | XML_FLAG_SRC_NEW_LINE : f & ~XML_FLAG_SRC_NEW_LINE; \
 381   ctx->bstop = bstop;                                                                   \
 382   src->row = row;
 383
 384 static void
 385 xml_refill_utf8(struct xml_context *ctx)
 386 {
 387   // FIXME: report corrupted encoding
 388   REFILL(ctx, bget_utf8);
 389 }
 390
 391 static void
 392 xml_refill_utf16_le(struct xml_context *ctx)
 393 {
 394   REFILL(ctx, bget_utf16_le_repl, 0);
 395 }
 396
 397 static void
 398 xml_refill_utf16_be(struct xml_context *ctx)
 399 {
 400   REFILL(ctx, bget_utf16_be_repl, 0);
 401 }
 402
 403 #if 0
 404 static inline uns
 405 xml_refill_libcharset_bget(struct fastbuf *fb, unsigned short int *in_to_x)
 406 {
 407   // FIXME: slow
 408   int c;
 409   return (unlikely(c = bgetc(fb) < 0)) ? c : (int)conv_x_to_ucs(in_to_x[c]);
 410 }
 411
 412 static void
 413 xml_refill_libcharset(struct xml_context *ctx)
 414 {
 415   unsigned short int *in_to_x = ctx->src->refill_in_to_x;
 416   REFILL(ctx, xml_refill_libcharset_bget, in_to_x);
 417 }
 418 #endif
 419
 420 #undef REFILL
 421
 422 static void
 423 xml_refill(struct xml_context *ctx)
 424 {
 425   do
 426     {
 427       if (ctx->flags & XML_FLAG_SRC_EOF)
 428         xml_pop_source(ctx);
 429       else if (ctx->flags & XML_FLAG_SRC_EXPECTED_DECL)
 430         xml_parse_decl(ctx);
 431       else
 432         {
 433           ctx->src->refill(ctx);
 434           TRACE(ctx, "refilled %u characters", (uns)((ctx->bstop - ctx->bptr) / 2));
 435         }
 436     }
 437   while (ctx->bptr == ctx->bstop);
 438 }
 439
 440 static inline uns
 441 xml_peek_char(struct xml_context *ctx)
 442 {
 443   if (ctx->bptr == ctx->bstop)
 444     xml_refill(ctx);
 445   return ctx->bptr[0];
 446 }
 447
 448 static inline uns
 449 xml_peek_cat(struct xml_context *ctx)
 450 {
 451   if (ctx->bptr == ctx->bstop)
 452     xml_refill(ctx);
 453   return ctx->bptr[1];
 454 }
 455
 456 static inline uns
 457 xml_get_char(struct xml_context *ctx)
 458 {
 459   uns c = xml_peek_char(ctx);
 460   ctx->bptr += 2;
 461   return c;
 462 }
 463
 464 static inline uns
 465 xml_get_cat(struct xml_context *ctx)
 466 {
 467   uns c = xml_peek_cat(ctx);
 468   ctx->bptr += 2;
 469   return c;
 470 }
 471
 472 static inline uns
 473 xml_last_char(struct xml_context *ctx)
 474 {
 475   return ctx->bptr[-2];
 476 }
 477
 478 static inline uns
 479 xml_last_cat(struct xml_context *ctx)
 480 {
 481   return ctx->bptr[-1];
 482 }
 483
 484 static inline uns
 485 xml_skip_char(struct xml_context *ctx)
 486 {
 487   uns c = ctx->bptr[0];
 488   ctx->bptr += 2;
 489   return c;
 490 }
 491
 492 static inline uns
 493 xml_unget_char(struct xml_context *ctx)
 494 {
 495   return *(ctx->bptr -= 2);
 496 }
 497
 498 static uns
 499 xml_row(struct xml_context *ctx)
 500 {
 501   struct xml_source *src = ctx->src;
 502   if (!src)
 503     return 0;
 504   uns row = src->row;
 505   for (u32 *p = ctx->bstop; p != ctx->bptr; p -= 2)
 506     if (p[-1] & src->refill_cat2)
 507       row--;
 508   return row + 1;
 509 }
 510
 511 /*** Basic parsing ***/
 512
 513 static void NONRET
 514 xml_fatal_expected(struct xml_context *ctx, uns c)
 515 {
 516   xml_fatal(ctx, "Expected '%c'", c);
 517 }
 518
 519 static void NONRET
 520 xml_fatal_expected_white(struct xml_context *ctx)
 521 {
 522   xml_fatal(ctx, "Expected a white space");
 523 }
 524
 525 static void NONRET
 526 xml_fatal_expected_quot(struct xml_context *ctx)
 527 {
 528   xml_fatal(ctx, "Expected a quotation mark");
 529 }
 530
 531 static inline uns
 532 xml_parse_white(struct xml_context *ctx, uns mandatory)
 533 {
 534   /* mandatory=1 -> S ::= (#x20 | #x9 | #xD | #xA)+
 535    * mandatory=0 -> S? */
 536   uns cnt = 0;
 537   while (xml_peek_cat(ctx) & XML_CHAR_WHITE)
 538     {
 539       xml_skip_char(ctx);
 540       cnt++;
 541     }
 542   if (unlikely(mandatory && !cnt))
 543     xml_fatal_expected_white(ctx);
 544   return cnt;
 545 }
 546
 547 static inline void
 548 xml_parse_char(struct xml_context *ctx, uns c)
 549 {
 550   /* Consumes a given Unicode character */
 551   if (unlikely(c != xml_get_char(ctx)))
 552     xml_fatal_expected(ctx, c);
 553 }
 554
 555 static inline void
 556 xml_parse_seq(struct xml_context *ctx, const char *seq)
 557 {
 558   /* Consumes a given sequence of ASCII characters */
 559   while (*seq)
 560     xml_parse_char(ctx, *seq++);
 561 }
 562
 563 static void
 564 xml_parse_eq(struct xml_context *ctx)
 565 {
 566   /* Eq ::= S? '=' S? */
 567   xml_parse_white(ctx, 0);
 568   xml_parse_char(ctx, '=');
 569   xml_parse_white(ctx, 0);
 570 }
 571
 572 static inline uns
 573 xml_parse_quote(struct xml_context *ctx)
 574 {
 575   /* "'" | '"' */
 576   uns c = xml_get_char(ctx);
 577   if (unlikely(c != '\'' && c != '\"'))
 578     xml_fatal_expected_quot(ctx);
 579   return c;
 580 }
 581
 582 /* Names and nmtokens */
 583
 584 static char *
 585 xml_parse_string(struct xml_context *ctx, uns first_cat, uns next_cat, char *err)
 586 {
 587   char *p = mp_start_noalign(ctx->pool, 1);
 588   if (unlikely(!(xml_peek_cat(ctx) & first_cat)))
 589     xml_fatal(ctx, "%s", err);
 590   do
 591     {
 592       p = mp_spread(ctx->pool, p, 5);
 593       p = utf8_32_put(p, xml_skip_char(ctx));
 594     }
 595   while (xml_peek_cat(ctx) & next_cat);
 596   *p++ = 0;
 597   return mp_end(ctx->pool, p);
 598 }
 599
 600 static void
 601 xml_skip_string(struct xml_context *ctx, uns first_cat, uns next_cat, char *err)
 602 {
 603   if (unlikely(!(xml_get_cat(ctx) & first_cat)))
 604     xml_fatal(ctx, "%s", err);
 605   while (xml_peek_cat(ctx) & next_cat)
 606     xml_skip_char(ctx);
 607 }
 608
 609 static char *
 610 xml_parse_name(struct xml_context *ctx)
 611 {
 612   /* Name ::= NameStartChar (NameChar)* */
 613   return xml_parse_string(ctx,
 614     !(ctx->flags & XML_FLAG_VERSION_1_1) ? XML_CHAR_SNAME_1_0 : XML_CHAR_SNAME_1_1,
 615     !(ctx->flags & XML_FLAG_VERSION_1_1) ? XML_CHAR_NAME_1_0 : XML_CHAR_NAME_1_1,
 616     "Expected a name");
 617 }
 618
 619 static void
 620 xml_skip_name(struct xml_context *ctx)
 621 {
 622   xml_skip_string(ctx,
 623     !(ctx->flags & XML_FLAG_VERSION_1_1) ? XML_CHAR_SNAME_1_0 : XML_CHAR_SNAME_1_1,
 624     !(ctx->flags & XML_FLAG_VERSION_1_1) ? XML_CHAR_NAME_1_0 : XML_CHAR_NAME_1_1,
 625     "Expected a name");
 626 }
 627
 628 static char *
 629 xml_parse_nmtoken(struct xml_context *ctx)
 630 {
 631   /* Nmtoken ::= (NameChar)+ */
 632   uns cat = !(ctx->flags & XML_FLAG_VERSION_1_1) ? XML_CHAR_NAME_1_0 : XML_CHAR_NAME_1_1;
 633   return xml_parse_string(ctx, cat, cat, "Expected a nmtoken");
 634 }
 635
 636 /* Simple literals */
 637
 638 static char *
 639 xml_parse_system_literal(struct xml_context *ctx)
 640 {
 641   /* SystemLiteral ::= ('"' [^"]* '"') | ("'" [^']* "'") */
 642   char *p = mp_start_noalign(ctx->pool, 1);
 643   uns q = xml_parse_quote(ctx), c;
 644   while ((c = xml_get_char(ctx)) != q)
 645     {
 646       p = mp_spread(ctx->pool, p, 5);
 647       p = utf8_32_put(p, c);
 648     }
 649   *p++ = 0;
 650   return mp_end(ctx->pool, p);
 651 }
 652
 653 static char *
 654 xml_parse_pubid_literal(struct xml_context *ctx)
 655 {
 656   /* PubidLiteral ::= '"' PubidChar* '"' | "'" (PubidChar - "'")* "'" */
 657   char *p = mp_start_noalign(ctx->pool, 1);
 658   uns q = xml_parse_quote(ctx), c;
 659   while ((c = xml_get_char(ctx)) != q)
 660     {
 661       if (unlikely(!(xml_last_cat(ctx) & XML_CHAR_PUBID)))
 662         xml_fatal(ctx, "Expected a pubid character");
 663       p = mp_spread(ctx->pool, p, 2);
 664       *p++ = c;
 665     }
 666   *p++ = 0;
 667   return mp_end(ctx->pool, p);
 668 }
 669
 670 static char *
 671 xml_parse_encoding_name(struct xml_context *ctx)
 672 {
 673   /* EncName ::= '"' [A-Za-z] ([A-Za-z0-9._] | '-')* '"' | "'" [A-Za-z] ([A-Za-z0-9._] | '-')* "'" */
 674   char *p = mp_start_noalign(ctx->pool, 1);
 675   uns q = xml_parse_quote(ctx);
 676   if (unlikely(!(xml_get_cat(ctx) & XML_CHAR_ENC_SNAME)))
 677     xml_fatal(ctx, "Invalid character in the encoding name");
 678   while (1)
 679     {
 680       p = mp_spread(ctx->pool, p, 2);
 681       *p++ = xml_last_char(ctx);
 682       if (xml_get_char(ctx) == q)
 683         break;
 684       if (unlikely(!(xml_last_cat(ctx) & XML_CHAR_ENC_NAME)))
 685         xml_fatal(ctx, "Invalid character in the encoding name");
 686     }
 687   *p++ = 0;
 688   return mp_end(ctx->pool, p);
 689 }
 690
 691 /* Document/external entity header */
 692
 693 static inline void
 694 xml_init_cats(struct xml_context *ctx, uns mask)
 695 {
 696   if (!(ctx->flags & XML_FLAG_VERSION_1_1))
 697     {
 698       ctx->src->refill_cat1 = XML_CHAR_VALID_1_0 & ~XML_CHAR_NEW_LINE_1_0 & ~mask;
 699       ctx->src->refill_cat2 = XML_CHAR_NEW_LINE_1_0;
 700     }
 701   else
 702     {
 703       ctx->src->refill_cat1 = XML_CHAR_UNRESTRICTED_1_1 & ~XML_CHAR_NEW_LINE_1_1 & ~mask;
 704       ctx->src->refill_cat2 = XML_CHAR_NEW_LINE_1_1;
 705     }
 706 }
 707
 708 static void
 709 xml_init_charconv(struct xml_context *ctx, int cs)
 710 {
 711   // FIXME: hack
 712   struct xml_source *src = ctx->src;
 713   TRACE(ctx, "wrapping charset %s", charset_name(cs));
 714 #if 0
 715   struct conv_context conv;
 716   conv_set_charset(&conv, cs, CONV_CHARSET_UTF8);
 717   src->refill = xml_refill_libcharset;
 718   src->refill_in_to_x = conv.in_to_x;
 719 #else
 720   src->fb = fb_wrap_charconv_in(src->fb, cs, CONV_CHARSET_UTF8);
 721   // FIXME: memory leak
 722 #endif
 723 }
 724
 725 static void
 726 xml_parse_decl(struct xml_context *ctx)
 727 {
 728   TRACE(ctx, "xml_parse_decl");
 729   struct xml_source *src = ctx->src;
 730   ctx->flags &= ~XML_FLAG_SRC_EXPECTED_DECL;
 731
 732   /* Setup valid Unicode ranges and force the reader to abort refill() after each '>', where we can switch encoding or XML version */
 733   xml_init_cats(ctx, XML_CHAR_GT);
 734
 735   /* Initialize the supplied charset (if any) or try to guess it */
 736   char *expected_encoding = src->expected_encoding ? : src->fb_encoding;
 737   src->refill = xml_refill_utf8;
 738   int bom = bpeekc(src->fb);
 739   if (bom < 0)
 740     ctx->flags |= XML_FLAG_SRC_EOF;
 741   if (!src->fb_encoding)
 742     {
 743       if (bom == 0xfe)
 744         src->refill = xml_refill_utf16_be;
 745       else if (bom == 0xff)
 746         src->refill = xml_refill_utf16_le;
 747     }
 748   else
 749     {
 750       int cs = find_charset_by_name(src->fb_encoding);
 751       if (cs == CONV_CHARSET_UTF8)
 752         {}
 753       else if (cs >= 0)
 754         {
 755           xml_init_charconv(ctx, cs);
 756           bom = 0;
 757         }
 758       else if (strcasecmp(src->fb_encoding, "UTF-16"))
 759         {
 760           src->refill = xml_refill_utf16_be;
 761           if (bom == 0xff)
 762             src->refill = xml_refill_utf16_le;
 763           if (!src->expected_encoding)
 764             expected_encoding = (bom == 0xff) ? "UTF-16LE" : "UTF-16BE";
 765         }
 766       else if (strcasecmp(src->fb_encoding, "UTF-16BE"))
 767         src->refill = xml_refill_utf16_be;
 768       else if (strcasecmp(src->fb_encoding, "UTF-16LE"))
 769         src->refill = xml_refill_utf16_le;
 770       else
 771         {
 772           xml_error(ctx, "Unknown encoding '%s'", src->fb_encoding);
 773           expected_encoding = NULL;
 774         }
 775     }
 776   uns utf16 = src->refill == xml_refill_utf16_le || src->refill == xml_refill_utf16_be;
 777   if (bom > 0 && xml_peek_char(ctx) == 0xfeff)
 778     xml_skip_char(ctx);
 779   else if (utf16)
 780     xml_error(ctx, "Missing or corrupted BOM");
 781
 782   /* Look ahead for presence of XMLDecl or optional TextDecl */
 783   if (!(ctx->flags & XML_FLAG_SRC_EOF) && ctx->bstop != src->buf + ARRAY_SIZE(src->buf))
 784     xml_refill(ctx);
 785   uns doc = ctx->flags & XML_FLAG_SRC_DOCUMENT;
 786   u32 *bptr = ctx->bptr;
 787   uns have_decl = (12 <= ctx->bstop - ctx->bptr && (bptr[11] & XML_CHAR_WHITE) &&
 788     bptr[0] == '<' && bptr[2] == '?' && (bptr[4] & 0xdf) == 'X' && (bptr[6] & 0xdf) == 'M' && (bptr[8] & 0xdf) == 'L');
 789   if (!have_decl)
 790     {
 791       if (doc)
 792         xml_fatal(ctx, "Missing or corrupted XML header");
 793       else if (expected_encoding && strcasecmp(src->expected_encoding, "UTF-8") && !utf16)
 794         xml_error(ctx, "Missing or corrupted entity header");
 795       goto exit;
 796     }
 797   ctx->bptr = bptr + 12;
 798   xml_parse_white(ctx, 0);
 799
 800   /* Parse version string (mandatory in XMLDecl, optional in TextDecl) */
 801   if (xml_peek_char(ctx) == 'v')
 802     {
 803       xml_parse_seq(ctx, "version");
 804       xml_parse_eq(ctx);
 805       char *version = xml_parse_pubid_literal(ctx);
 806       TRACE(ctx, "version=%s", version);
 807       uns v = 0;
 808       if (!strcmp(version, "1.1"))
 809         v = XML_FLAG_VERSION_1_1;
 810       else if (strcmp(version, "1.0"))
 811         {
 812           xml_error(ctx, "Unknown XML version string '%s'", version);
 813           version = "1.0";
 814         }
 815       if (doc)
 816         {
 817           ctx->version_str = version;
 818           ctx->flags |= v;
 819         }
 820       else if (v > (ctx->flags & XML_FLAG_VERSION_1_1))
 821         xml_error(ctx, "XML 1.1 external entity included from XML 1.0 document");
 822       if (!xml_parse_white(ctx, !doc))
 823         goto end;
 824     }
 825   else if (doc)
 826     {
 827       xml_error(ctx, "Expected XML version");
 828       ctx->version_str = "1.0";
 829     }
 830
 831   /* Parse encoding string (optional in XMLDecl, mandatory in TextDecl) */
 832   if (xml_peek_char(ctx) == 'e')
 833     {
 834       xml_parse_seq(ctx, "encoding");
 835       xml_parse_eq(ctx);
 836       src->decl_encoding = xml_parse_encoding_name(ctx);
 837       TRACE(ctx, "encoding=%s", src->decl_encoding);
 838       if (!xml_parse_white(ctx, 0))
 839         goto end;
 840     }
 841   else if (!doc)
 842     xml_error(ctx, "Expected XML encoding");
 843
 844   /* Parse whether the document is standalone (optional in XMLDecl) */
 845   if (doc && xml_peek_char(ctx) == 's')
 846     {
 847       xml_parse_seq(ctx, "standalone");
 848       xml_parse_eq(ctx);
 849       uns c = xml_parse_quote(ctx);
 850       if (ctx->standalone = (xml_peek_char(ctx) == 'y'))
 851         xml_parse_seq(ctx, "yes");
 852       else
 853         xml_parse_seq(ctx, "no");
 854       xml_parse_char(ctx, c);
 855       TRACE(ctx, "standalone=%d", ctx->standalone);
 856       xml_parse_white(ctx, 0);
 857     }
 858 end:
 859   xml_parse_seq(ctx, "?>");
 860
 861   /* Switch to the final encoding */
 862   if (src->decl_encoding)
 863     {
 864       int cs = find_charset_by_name(src->decl_encoding);
 865       if (cs < 0 && !expected_encoding)
 866         xml_error(ctx, "Unknown encoding '%s'", src->decl_encoding);
 867       else if (!src->fb_encoding && cs >= 0 && cs != CONV_CHARSET_UTF8)
 868         xml_init_charconv(ctx, cs);
 869       else if (expected_encoding && strcasecmp(src->decl_encoding, expected_encoding) && (!utf16 ||
 870         !(!strcasecmp(src->decl_encoding, "UTF-16") ||
 871          (!strcasecmp(src->decl_encoding, "UTF-16BE") && strcasecmp(expected_encoding, "UTF-16LE")) ||
 872          (!strcasecmp(src->decl_encoding, "UTF-16LE") && strcasecmp(expected_encoding, "UTF-16BE")))))
 873         xml_error(ctx, "The header contains encoding '%s' instead of expected '%s'", src->decl_encoding, expected_encoding);
 874     }
 875
 876 exit:
 877   /* Update valid Unicode ranges */
 878   xml_init_cats(ctx, 0);
 879 }
 880
 881 /*** Document Type Definition (DTD) ***/
 882
 883 /* Notations */
 884
 885 #define HASH_PREFIX(x) xml_dtd_notns_##x
 886 #define HASH_NODE struct xml_dtd_notn
 887 #define HASH_KEY_STRING name
 888 #define HASH_ZERO_FILL
 889 #define HASH_TABLE_DYNAMIC
 890 #define HASH_WANT_FIND
 891 #define HASH_WANT_LOOKUP
 892 #define HASH_GIVE_ALLOC
 893 #define HASH_TABLE_ALLOC
 894 XML_HASH_GIVE_ALLOC
 895 #include "lib/hashtable.h"
 896
 897 /* General entities */
 898
 899 #define HASH_PREFIX(x) xml_dtd_ents_##x
 900 #define HASH_NODE struct xml_dtd_ent
 901 #define HASH_KEY_STRING name
 902 #define HASH_ZERO_FILL
 903 #define HASH_TABLE_DYNAMIC
 904 #define HASH_WANT_FIND
 905 #define HASH_WANT_LOOKUP
 906 #define HASH_GIVE_ALLOC
 907 #define HASH_TABLE_ALLOC
 908 XML_HASH_GIVE_ALLOC
 909 #include "lib/hashtable.h"
 910
 911 static struct xml_dtd_ent *
 912 xml_dtd_declare_trivial_gent(struct xml_context *ctx, char *name, char *text)
 913 {
 914   struct xml_dtd *dtd = ctx->dtd;
 915   struct xml_dtd_ent *ent = xml_dtd_ents_lookup(dtd->tab_gents, name);
 916   if (ent->flags & XML_DTD_ENT_DECLARED)
 917     {
 918       xml_warn(ctx, "Entity &%s; already declared", name);
 919       return NULL;
 920     }
 921   slist_add_tail(&dtd->gents, &ent->n);
 922   ent->flags = XML_DTD_ENT_DECLARED | XML_DTD_ENT_TRIVIAL;
 923   ent->text = text;
 924   ent->len = strlen(text);
 925   return ent;
 926 }
 927
 928 static void
 929 xml_dtd_declare_default_gents(struct xml_context *ctx)
 930 {
 931   xml_dtd_declare_trivial_gent(ctx, "lt", "<");
 932   xml_dtd_declare_trivial_gent(ctx, "gt", ">");
 933   xml_dtd_declare_trivial_gent(ctx, "amp", "&");
 934   xml_dtd_declare_trivial_gent(ctx, "apos", "'");
 935   xml_dtd_declare_trivial_gent(ctx, "quot", "\"");
 936 }
 937
 938 static struct xml_dtd_ent *
 939 xml_dtd_find_gent(struct xml_context *ctx, char *name)
 940 {
 941   struct xml_dtd *dtd = ctx->dtd;
 942   if (dtd)
 943     {
 944       struct xml_dtd_ent *ent = xml_dtd_ents_find(dtd->tab_gents, name);
 945       return !ent ? NULL : (ent->flags & XML_DTD_ENT_DECLARED) ? ent : NULL;
 946     }
 947   else
 948     {
 949 #define ENT(n, t) ent_##n = { .name = #n, .text = t, .len = 1, .flags = XML_DTD_ENT_DECLARED | XML_DTD_ENT_TRIVIAL }
 950       static struct xml_dtd_ent ENT(lt, "<"), ENT(gt, ">"), ENT(amp, "&"), ENT(apos, "'"), ENT(quot, "\"");
 951 #undef ENT
 952       switch (name[0])
 953         {
 954           case 'l':
 955             if (!strcmp(name, "lt"))
 956               return &ent_lt;
 957             break;
 958           case 'g':
 959             if (!strcmp(name, "gt"))
 960               return &ent_gt;
 961             break;
 962           case 'a':
 963             if (!strcmp(name, "amp"))
 964               return &ent_amp;
 965             if (!strcmp(name, "apos"))
 966               return &ent_apos;
 967             break;
 968           case 'q':
 969             if (!strcmp(name, "quot"))
 970               return &ent_quot;
 971             break;
 972         }
 973       return NULL;
 974     }
 975 }
 976
 977 /* Parameter entities */
 978
 979 static struct xml_dtd_ent *
 980 xml_dtd_find_pent(struct xml_context *ctx, char *name)
 981 {
 982   struct xml_dtd *dtd = ctx->dtd;
 983   struct xml_dtd_ent *ent = xml_dtd_ents_find(dtd->tab_pents, name);
 984   return !ent ? NULL : (ent->flags & XML_DTD_ENT_DECLARED) ? ent : NULL;
 985 }
 986
 987 /* Elements */
 988
 989 #define HASH_PREFIX(x) xml_dtd_elems_##x
 990 #define HASH_NODE struct xml_dtd_elem
 991 #define HASH_KEY_STRING name
 992 #define HASH_TABLE_DYNAMIC
 993 #define HASH_ZERO_FILL
 994 #define HASH_WANT_LOOKUP
 995 #define HASH_GIVE_ALLOC
 996 #define HASH_TABLE_ALLOC
 997 XML_HASH_GIVE_ALLOC
 998 #include "lib/hashtable.h"
 999
1000 /* Element attributes */
1001
1002 struct xml_dtd_attrs_table;
1003
1004 static inline uns
1005 xml_dtd_attrs_hash(struct xml_dtd_attrs_table *tab UNUSED, struct xml_dtd_elem *elem, char *name)
1006 {
1007   return hash_pointer(elem) ^ hash_string(name);
1008 }
1009
1010 static inline int
1011 xml_dtd_attrs_eq(struct xml_dtd_attrs_table *tab UNUSED, struct xml_dtd_elem *elem1, char *name1, struct xml_dtd_elem *elem2, char *name2)
1012 {
1013   return (elem1 == elem2) && !strcmp(name1, name2);
1014 }
1015
1016 static inline void
1017 xml_dtd_attrs_init_key(struct xml_dtd_attrs_table *tab UNUSED, struct xml_dtd_attr *attr, struct xml_dtd_elem *elem, char *name)
1018 {
1019   attr->elem = elem;
1020   attr->name = name;
1021 }
1022
1023 #define HASH_PREFIX(x) xml_dtd_attrs_##x
1024 #define HASH_NODE struct xml_dtd_attr
1025 #define HASH_ZERO_FILL
1026 #define HASH_TABLE_DYNAMIC
1027 #define HASH_KEY_COMPLEX(x) x elem, x name
1028 #define HASH_KEY_DECL struct xml_dtd_elem *elem, char *name
1029 #define HASH_GIVE_HASHFN
1030 #define HASH_GIVE_EQ
1031 #define HASH_GIVE_INIT_KEY
1032 #define HASH_WANT_FIND
1033 #define HASH_WANT_NEW
1034 #define HASH_GIVE_ALLOC
1035 #define HASH_TABLE_ALLOC
1036 XML_HASH_GIVE_ALLOC
1037 #include "lib/hashtable.h"
1038
1039 /* Enumerated attribute values */
1040
1041 struct xml_dtd_evals_table;
1042
1043 static inline uns
1044 xml_dtd_evals_hash(struct xml_dtd_evals_table *tab UNUSED, struct xml_dtd_attr *attr, char *val)
1045 {
1046   return hash_pointer(attr) ^ hash_string(val);
1047 }
1048
1049 static inline int
1050 xml_dtd_evals_eq(struct xml_dtd_evals_table *tab UNUSED, struct xml_dtd_attr *attr1, char *val1, struct xml_dtd_attr *attr2, char *val2)
1051 {
1052   return (attr1 == attr2) && !strcmp(val1, val2);
1053 }
1054
1055 static inline void
1056 xml_dtd_evals_init_key(struct xml_dtd_evals_table *tab UNUSED, struct xml_dtd_eval *eval, struct xml_dtd_attr *attr, char *val)
1057 {
1058   eval->attr = attr;
1059   eval->val = val;
1060 }
1061
1062 #define HASH_PREFIX(x) xml_dtd_evals_##x
1063 #define HASH_NODE struct xml_dtd_eval
1064 #define HASH_TABLE_DYNAMIC
1065 #define HASH_KEY_COMPLEX(x) x attr, x val
1066 #define HASH_KEY_DECL struct xml_dtd_attr *attr, char *val
1067 #define HASH_GIVE_HASHFN
1068 #define HASH_GIVE_EQ
1069 #define HASH_GIVE_INIT_KEY
1070 #define HASH_WANT_FIND
1071 #define HASH_WANT_NEW
1072 #define HASH_GIVE_ALLOC
1073 #define HASH_TABLE_ALLOC
1074 XML_HASH_GIVE_ALLOC
1075 #include "lib/hashtable.h"
1076
1077 /* Enumerated attribute notations */
1078
1079 struct xml_dtd_enotns_table;
1080
1081 static inline uns
1082 xml_dtd_enotns_hash(struct xml_dtd_enotns_table *tab UNUSED, struct xml_dtd_attr *attr, struct xml_dtd_notn *notn)
1083 {
1084   return hash_pointer(attr) ^ hash_pointer(notn);
1085 }
1086
1087 static inline int
1088 xml_dtd_enotns_eq(struct xml_dtd_enotns_table *tab UNUSED, struct xml_dtd_attr *attr1, struct xml_dtd_notn *notn1, struct xml_dtd_attr *attr2, struct xml_dtd_notn *notn2)
1089 {
1090   return (attr1 == attr2) && (notn1 == notn2);
1091 }
1092
1093 static inline void
1094 xml_dtd_enotns_init_key(struct xml_dtd_enotns_table *tab UNUSED, struct xml_dtd_enotn *enotn, struct xml_dtd_attr *attr, struct xml_dtd_notn *notn)
1095 {
1096   enotn->attr = attr;
1097   enotn->notn = notn;
1098 }
1099
1100 #define HASH_PREFIX(x) xml_dtd_enotns_##x
1101 #define HASH_NODE struct xml_dtd_enotn
1102 #define HASH_TABLE_DYNAMIC
1103 #define HASH_KEY_COMPLEX(x) x attr, x notn
1104 #define HASH_KEY_DECL struct xml_dtd_attr *attr, struct xml_dtd_notn *notn
1105 #define HASH_GIVE_HASHFN
1106 #define HASH_GIVE_EQ
1107 #define HASH_GIVE_INIT_KEY
1108 #define HASH_WANT_FIND
1109 #define HASH_WANT_NEW
1110 #define HASH_GIVE_ALLOC
1111 #define HASH_TABLE_ALLOC
1112 XML_HASH_GIVE_ALLOC
1113 #include "lib/hashtable.h"
1114
1115 /* DTD initialization/cleanup */
1116
1117 static void
1118 xml_dtd_init(struct xml_context *ctx)
1119 {
1120   if (ctx->dtd)
1121     return;
1122   struct mempool *pool = mp_new(4096);
1123   struct xml_dtd *dtd = ctx->dtd = mp_alloc_zero(pool, sizeof(*ctx->dtd));
1124   dtd->pool = pool;
1125   xml_dtd_ents_init(dtd->tab_gents = xml_hash_new(pool, sizeof(struct xml_dtd_ents_table)));
1126   xml_dtd_ents_init(dtd->tab_pents = xml_hash_new(pool, sizeof(struct xml_dtd_ents_table)));
1127   xml_dtd_notns_init(dtd->tab_notns = xml_hash_new(pool, sizeof(struct xml_dtd_notns_table)));
1128   xml_dtd_elems_init(dtd->tab_elems = xml_hash_new(pool, sizeof(struct xml_dtd_elems_table)));
1129   xml_dtd_attrs_init(dtd->tab_attrs = xml_hash_new(pool, sizeof(struct xml_dtd_attrs_table)));
1130   xml_dtd_evals_init(dtd->tab_evals = xml_hash_new(pool, sizeof(struct xml_dtd_evals_table)));
1131   xml_dtd_enotns_init(dtd->tab_enotns = xml_hash_new(pool, sizeof(struct xml_dtd_enotns_table)));
1132   xml_dtd_declare_default_gents(ctx);
1133 }
1134
1135 static void
1136 xml_dtd_cleanup(struct xml_context *ctx)
1137 {
1138   if (!ctx->dtd)
1139     return;
1140   mp_delete(ctx->dtd->pool);
1141   ctx->dtd = NULL;
1142 }
1143
1144 static void
1145 xml_dtd_finish(struct xml_context *ctx)
1146 {
1147   if (!ctx->dtd)
1148     return;
1149   // FIXME
1150 }
1151
1152 /*** Parsing functions ***/
1153
1154 /* Comments */
1155
1156 static void
1157 xml_push_comment(struct xml_context *ctx)
1158 {
1159   /* Parse a comment to ctx->value:
1160    *   Comment ::= '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'
1161    * Already parsed: '<!-' */
1162   struct fastbuf *out = ctx->value;
1163   uns c;
1164   xml_parse_char(ctx, '-');
1165   while (1)
1166     {
1167       if ((c = xml_get_char(ctx)) == '-')
1168         if ((c = xml_get_char(ctx)) == '-')
1169           break;
1170         else
1171           bputc(out, '-');
1172       bput_utf8_32(out, c);
1173     }
1174   xml_parse_char(ctx, '>');
1175   xml_dec(ctx);
1176   fbgrow_rewind(out);
1177   if (ctx->h_comment)
1178     ctx->h_comment(ctx);
1179 }
1180
1181 static void
1182 xml_pop_comment(struct xml_context *ctx)
1183 {
1184   fbgrow_rewind(ctx->value);
1185 }
1186
1187 static void
1188 xml_skip_comment(struct xml_context *ctx)
1189 {
1190   xml_parse_char(ctx, '-');
1191   while (xml_get_char(ctx) != '-' || xml_get_char(ctx) != '-');
1192   xml_parse_char(ctx, '>');
1193   xml_dec(ctx);
1194 }
1195
1196 /* Processing instructions */
1197
1198 static void
1199 xml_push_pi(struct xml_context *ctx)
1200 {
1201   /* Parses a PI to ctx->value and ctx->name:
1202    *   PI       ::= '<?' PITarget (S (Char* - (Char* '?>' Char*)))? '?>'
1203    *   PITarget ::= Name - (('X' | 'x') ('M' | 'm') ('L' | 'l'))
1204    * Already parsed: '<?' */
1205
1206   ctx->name = xml_parse_name(ctx);
1207   if (unlikely(!strcasecmp(ctx->name, "xml")))
1208     xml_fatal(ctx, "Reserved PI target");
1209   struct fastbuf *out = ctx->value;
1210   if (xml_parse_white(ctx, 0))
1211     xml_parse_seq(ctx, "?>");
1212   else
1213     {
1214       while (1)
1215         {
1216           uns c;
1217           if ((c = xml_get_char(ctx)) == '?')
1218             if (xml_get_char(ctx) == '>')
1219               break;
1220             else
1221               {
1222                 xml_unget_char(ctx);
1223                 bputc(out, '?');
1224               }
1225           else
1226             bput_utf8_32(out, c);
1227         }
1228       fbgrow_rewind(out);
1229     }
1230   xml_dec(ctx);
1231   if (ctx->h_pi)
1232     ctx->h_pi(ctx);
1233 }
1234
1235 static void
1236 xml_pop_pi(struct xml_context *ctx)
1237 {
1238   fbgrow_reset(ctx->value);
1239 }
1240
1241 static void
1242 xml_skip_pi(struct xml_context *ctx)
1243 {
1244   if (ctx->flags & XML_FLAG_VALIDATING)
1245     {
1246       mp_push(ctx->pool);
1247       if (unlikely(!strcasecmp(xml_parse_name(ctx), "xml")))
1248         xml_fatal(ctx, "Reserved PI target");
1249       mp_pop(ctx->pool);
1250       if (!xml_parse_white(ctx, 0))
1251         {
1252           xml_parse_seq(ctx, "?>");
1253           xml_dec(ctx);
1254           return;
1255         }
1256     }
1257   while (1)
1258     if (xml_get_char(ctx) == '?')
1259       if (xml_get_char(ctx) == '>')
1260         break;
1261       else
1262         xml_unget_char(ctx);
1263   xml_dec(ctx);
1264 }
1265
1266 /* Character references */
1267
1268 static uns
1269 xml_parse_char_ref(struct xml_context *ctx)
1270 {
1271   TRACE(ctx, "parse_char_ref");
1272   /* CharRef ::= '&#' [0-9]+ ';' | '&#x' [0-9a-fA-F]+ ';'
1273    * Already parsed: '&#' */
1274   uns v = 0;
1275   if (xml_get_char(ctx) == 'x')
1276     {
1277       if (!(xml_get_cat(ctx) & XML_CHAR_XDIGIT))
1278         {
1279           xml_error(ctx, "Expected a hexadecimal value of character reference");
1280           goto recover;
1281         }
1282       do
1283         {
1284           v = (v << 4) + Cxvalue(xml_last_char(ctx));
1285         }
1286       while (v < 0x110000 && (xml_get_cat(ctx) & XML_CHAR_XDIGIT));
1287     }
1288   else
1289     {
1290       if (!(xml_last_cat(ctx) & XML_CHAR_DIGIT))
1291         {
1292           xml_error(ctx, "Expected a numeric value of character reference");
1293           goto recover;
1294         }
1295       do
1296         {
1297           v = v * 10 + xml_last_char(ctx) - '0';
1298         }
1299       while (v < 0x110000 && (xml_get_cat(ctx) & XML_CHAR_DIGIT));
1300     }
1301   uns cat = xml_char_cat(v);
1302   if (!(cat & XML_CHAR_UNRESTRICTED_1_1) && ((ctx->flags & XML_FLAG_VERSION_1_1) || !(cat & XML_CHAR_VALID_1_0)))
1303     {
1304       xml_error(ctx, "Character reference out of range");
1305       goto recover;
1306     }
1307   if (xml_last_char(ctx) == ';')
1308     {
1309       xml_dec(ctx);
1310       return v;
1311     }
1312   xml_error(ctx, "Expected ';'");
1313 recover:
1314   while (xml_last_char(ctx) != ';')
1315     xml_get_char(ctx);
1316   xml_dec(ctx);
1317   return UNI_REPLACEMENT;
1318 }
1319
1320 /* References to general entities */
1321
1322 static void
1323 xml_parse_ge_ref(struct xml_context *ctx, struct fastbuf *out)
1324 {
1325   /* Reference ::= EntityRef | CharRef
1326    * EntityRef ::= '&' Name ';'
1327    * Already parsed: '&' */
1328   if (xml_peek_char(ctx) == '#')
1329     {
1330       xml_skip_char(ctx);
1331       uns c = xml_parse_char_ref(ctx);
1332       bput_utf8_32(out, c);
1333     }
1334   else
1335     {
1336       struct mempool_state state;
1337       mp_save(ctx->pool, &state);
1338       char *name = xml_parse_name(ctx);
1339       xml_parse_char(ctx, ';');
1340       struct xml_dtd_ent *ent = xml_dtd_find_gent(ctx, name);
1341       if (!ent)
1342         {
1343           xml_error(ctx, "Unknown entity &%s;", name);
1344           bputc(out, '&');
1345           bputs(out, name);
1346           bputc(out, ';');
1347         }
1348       else if (ent->flags & XML_DTD_ENT_TRIVIAL)
1349         {
1350           TRACE(ctx, "Trivial entity &%s;", name);
1351           bwrite(out, ent->text, ent->len);
1352         }
1353       else
1354         {
1355           TRACE(ctx, "Pushed entity &%s;", name);
1356           mp_restore(ctx->pool, &state);
1357           xml_dec(ctx);
1358           xml_push_entity(ctx, ent);
1359           return;
1360         }
1361       mp_restore(ctx->pool, &state);
1362       xml_dec(ctx);
1363     }
1364 }
1365
1366 /* References to parameter entities */
1367
1368 static void
1369 xml_parse_pe_ref(struct xml_context *ctx)
1370 {
1371   /* PEReference ::= '%' Name ';'
1372    * Already parsed: '%' */
1373   struct mempool_state state;
1374   mp_save(ctx->pool, &state);
1375   char *name = xml_parse_name(ctx);
1376   xml_parse_char(ctx, ';');
1377   struct xml_dtd_ent *ent = xml_dtd_find_pent(ctx, name);
1378   if (!ent)
1379     xml_error(ctx, "Unknown entity %%%s;", name);
1380   else
1381     {
1382       TRACE(ctx, "Pushed entity %%%s;", name);
1383       mp_restore(ctx->pool, &state);
1384       xml_dec(ctx);
1385       xml_push_entity(ctx, ent);
1386       return;
1387     }
1388   mp_restore(ctx->pool, &state);
1389   xml_dec(ctx);
1390 }
1391
1392 static void
1393 xml_parse_dtd_pe(struct xml_context *ctx)
1394 {
1395   do
1396     {
1397       xml_skip_char(ctx);
1398       xml_inc(ctx);
1399       while (xml_peek_cat(ctx) & XML_CHAR_WHITE)
1400         xml_skip_char(ctx);
1401       xml_parse_pe_ref(ctx);
1402     }
1403   while (xml_peek_char(ctx) != '%');
1404 }
1405
1406 static inline uns
1407 xml_parse_dtd_white(struct xml_context *ctx, uns mandatory)
1408 {
1409   /* Whitespace or parameter entity */
1410   uns cnt = 0;
1411   while (xml_peek_cat(ctx) & XML_CHAR_WHITE)
1412     {
1413       xml_skip_char(ctx);
1414       cnt = 1;
1415     }
1416   if (xml_peek_char(ctx) == '%')
1417     {
1418       xml_parse_dtd_pe(ctx);
1419       return 1;
1420     }
1421   else if (unlikely(mandatory && !cnt))
1422     xml_fatal_expected_white(ctx);
1423   return cnt;
1424 }
1425
1426 static inline uns
1427 xml_check_dtd_pe(struct xml_context *ctx)
1428 {
1429   if (xml_peek_char(ctx) == '%')
1430     {
1431       xml_parse_dtd_pe(ctx);
1432       return 1;
1433     }
1434   return 0;
1435 }
1436
1437 /* External ID */
1438
1439 static void
1440 xml_parse_external_id(struct xml_context *ctx, struct xml_ext_id *eid, uns allow_public, uns dtd)
1441 {
1442   bzero(eid, sizeof(*eid));
1443   if (dtd)
1444     xml_check_dtd_pe(ctx);
1445   uns c = xml_peek_char(ctx);
1446   if (c == 'S')
1447     {
1448       xml_parse_seq(ctx, "SYSTEM");
1449       if (dtd)
1450         xml_parse_dtd_white(ctx, 1);
1451       else
1452         xml_parse_white(ctx, 1);
1453       eid->system_id = xml_parse_system_literal(ctx);
1454     }
1455   else if (c == 'P')
1456     {
1457       xml_parse_seq(ctx, "PUBLIC");
1458       if (dtd)
1459         xml_parse_dtd_white(ctx, 1);
1460       else
1461         xml_parse_white(ctx, 1);
1462       eid->public_id = xml_parse_pubid_literal(ctx);
1463       if (dtd ? xml_parse_dtd_white(ctx, 0) : xml_parse_white(ctx, 0))
1464         if ((c = xml_peek_char(ctx)) == '\'' || c == '"' || !allow_public)
1465           eid->system_id = xml_parse_system_literal(ctx);
1466     }
1467   else
1468     xml_fatal(ctx, "Expected an external ID");
1469 }
1470
1471 /* DTD: Notation declaration */
1472
1473 static void
1474 xml_parse_notation_decl(struct xml_context *ctx)
1475 {
1476   /* NotationDecl ::= '<!NOTATION' S Name S (ExternalID | PublicID) S? '>'
1477    * Already parsed: '<!NOTATION' */
1478   TRACE(ctx, "parse_notation_decl");
1479   struct xml_dtd *dtd = ctx->dtd;
1480   xml_parse_dtd_white(ctx, 1);
1481
1482   struct xml_dtd_notn *notn = xml_dtd_notns_lookup(dtd->tab_notns, xml_parse_name(ctx));
1483   xml_parse_dtd_white(ctx, 1);
1484   struct xml_ext_id eid;
1485   xml_parse_external_id(ctx, &eid, 1, 1);
1486   xml_parse_dtd_white(ctx, 0);
1487   xml_parse_char(ctx, '>');
1488
1489   if (notn->flags & XML_DTD_NOTN_DECLARED)
1490     xml_warn(ctx, "Notation %s already declared", notn->name);
1491   else
1492     {
1493       notn->flags = XML_DTD_NOTN_DECLARED;
1494       notn->eid = eid;
1495       slist_add_tail(&dtd->notns, &notn->n);
1496     }
1497   xml_dec(ctx);
1498 }
1499
1500 static void
1501 xml_parse_entity_decl(struct xml_context *ctx)
1502 {
1503   /* Already parsed: '<!ENTITY' */
1504   TRACE(ctx, "parse_entity_decl");
1505   struct xml_dtd *dtd = ctx->dtd;
1506   xml_parse_dtd_white(ctx, 1);
1507
1508   uns flags = (xml_get_char(ctx) == '%') ? XML_DTD_ENT_PARAMETER : 0;
1509   if (flags)
1510     xml_parse_dtd_white(ctx, 1);
1511   else
1512     xml_unget_char(ctx);
1513
1514   struct xml_dtd_ent *ent = xml_dtd_ents_lookup(flags ? dtd->tab_pents : dtd->tab_gents, xml_parse_name(ctx));
1515   slist *list = flags ? &dtd->pents : &dtd->gents;
1516   xml_parse_white(ctx, 1);
1517   if (ent->flags & XML_DTD_ENT_DECLARED)
1518     {
1519        xml_fatal(ctx, "Entity &%s; already declared, skipping not implemented", ent->name);
1520        // FIXME: should be only warning
1521     }
1522
1523   uns c, sep = xml_get_char(ctx);
1524   if (sep == '\'' || sep == '"')
1525     {
1526       /* Internal entity:
1527        * EntityValue ::= '"' ([^%&"] | PEReference | Reference)* '"' | "'" ([^%&'] | PEReference | Reference)* "'" */
1528       struct fastbuf *out = ctx->value;
1529       while (1)
1530         {
1531           if ((c = xml_get_char(ctx)) == sep)
1532             break;
1533           else if (c == '%')
1534             {
1535               // FIXME
1536               ASSERT(0);
1537               //xml_parse_parameter_ref(ctx);
1538             }
1539           else if (c != '&')
1540             bput_utf8_32(out, c);
1541           else if ((c = xml_get_char(ctx)) == '#')
1542             c = xml_parse_char_ref(ctx);
1543           else
1544             {
1545               /* Bypass references to general entities */
1546               mp_push(ctx->pool);
1547               bputc(out, '&');
1548               xml_unget_char(ctx);
1549               bputs(out, xml_parse_name(ctx));
1550               xml_parse_char(ctx, ';');
1551               bputc(out, ';');
1552               mp_pop(ctx->pool);
1553             }
1554         }
1555       bputc(out, 0);
1556       fbgrow_rewind(out);
1557       slist_add_tail(list, &ent->n);
1558       ent->flags = flags | XML_DTD_ENT_DECLARED;
1559       ent->len = out->bstop - out->bptr - 1;
1560       ent->text = mp_memdup(ctx->pool, out->bptr, ent->len + 1);
1561       fbgrow_reset(out);
1562     }
1563   else
1564     {
1565       /* External entity */
1566       struct xml_ext_id eid;
1567       struct xml_dtd_notn *notn = NULL;
1568       xml_parse_external_id(ctx, &eid, 0, 0);
1569       if (!xml_parse_white(ctx, 0) || !flags)
1570         xml_parse_char(ctx, '>');
1571       else if (xml_get_char(ctx) != '>')
1572         {
1573           /* General external unparsed entity */
1574           flags |= XML_DTD_ENT_UNPARSED;
1575           xml_parse_seq(ctx, "NDATA");
1576           xml_parse_white(ctx, 1);
1577           notn = xml_dtd_notns_lookup(dtd->tab_notns, xml_parse_name(ctx));
1578         }
1579       slist_add_tail(list, &ent->n);
1580       ent->flags = flags | XML_DTD_ENT_DECLARED | XML_DTD_ENT_EXTERNAL;
1581       ent->eid = eid;
1582       ent->notn = notn;
1583     }
1584   xml_parse_dtd_white(ctx, 0);
1585   xml_parse_char(ctx, '>');
1586   xml_dec(ctx);
1587 }
1588
1589 /* DTD: Internal subset */
1590
1591 static void
1592 xml_parse_internal_subset(struct xml_context *ctx)
1593 {
1594   // FIXME: comments/pi have no parent
1595   /* '[' intSubset ']'
1596    * intSubset :== (markupdecl | DeclSep)
1597    * Already parsed: ']' */
1598   while (1)
1599     {
1600       xml_parse_white(ctx, 0);
1601       uns c = xml_get_char(ctx);
1602       xml_inc(ctx);
1603       if (c == '<')
1604         if ((c = xml_get_char(ctx)) == '!')
1605           switch (c = xml_get_char(ctx))
1606             {
1607               case '-':
1608                 xml_push_comment(ctx);
1609                 xml_pop_comment(ctx);
1610                 break;
1611               case 'N':
1612                 xml_parse_seq(ctx, "OTATION");
1613                 xml_parse_notation_decl(ctx);
1614                 break;
1615               case 'E':
1616                 if ((c = xml_get_char(ctx)) == 'N')
1617                   {
1618                     xml_parse_seq(ctx, "TITY");
1619                     xml_parse_entity_decl(ctx);
1620                   }
1621                 else if (c == 'L')
1622                   {
1623                     xml_parse_seq(ctx, "EMENT");
1624                     // FIXME: Element
1625                   }
1626                 else
1627                   goto invalid_markup;
1628                 break;
1629               case 'A':
1630                 xml_parse_seq(ctx, "TTLIST");
1631                 // FIXME: AttList
1632                 break;
1633               default:
1634                 goto invalid_markup;
1635             }
1636         else if (c == '?')
1637           {
1638             xml_push_pi(ctx);
1639             xml_pop_pi(ctx);
1640           }
1641         else
1642           goto invalid_markup;
1643       else if (c == '%')
1644         xml_parse_dtd_pe(ctx);
1645       else if (c == ']')
1646         break;
1647       else
1648         goto invalid_markup;
1649     }
1650   xml_dec(ctx);
1651   xml_dec(ctx);
1652   return;
1653 invalid_markup:
1654   xml_fatal(ctx, "Invalid markup in the internal subset");
1655 }
1656
1657 ///////////////////////////////////////////////////////////////////////////////////////////////////////////
1658
1659 static void
1660 xml_parse_cdata(struct xml_context *ctx)
1661 {
1662   struct fastbuf *out = ctx->chars;
1663   xml_parse_seq(ctx, "CDATA[");
1664   while (1)
1665     {
1666       uns c;
1667       if ((c = xml_get_char(ctx)) == ']')
1668         {
1669           if ((c = xml_get_char(ctx)) == ']')
1670             if ((c = xml_get_char(ctx)) == '>')
1671               break;
1672             else
1673               bputc(out, ']');
1674           bputc(out, ']');
1675         }
1676       bput_utf8_32(out, c);
1677     }
1678 }
1679
1680 static void
1681 xml_skip_cdata(struct xml_context *ctx)
1682 {
1683   xml_parse_cdata(ctx);
1684 }
1685
1686 static void
1687 xml_parse_chars(struct xml_context *ctx)
1688 {
1689   TRACE(ctx, "parse_chars");
1690   struct fastbuf *out = ctx->chars;
1691   uns c;
1692   while ((c = xml_get_char(ctx)) != '<')
1693     if (c == '&')
1694       {
1695         xml_inc(ctx);
1696         xml_parse_ge_ref(ctx, out);
1697       }
1698     else
1699       bput_utf8_32(out, c);
1700   xml_unget_char(ctx);
1701 }
1702
1703 /*----------------------------------------------*/
1704
1705 struct xml_attrs_table;
1706
1707 static inline uns
1708 xml_attrs_hash(struct xml_attrs_table *t UNUSED, struct xml_elem *e, char *n)
1709 {
1710   return hash_pointer(e) ^ hash_string(n);
1711 }
1712
1713 static inline int
1714 xml_attrs_eq(struct xml_attrs_table *t UNUSED, struct xml_elem *e1, char *n1, struct xml_elem *e2, char *n2)
1715 {
1716   return (e1 == e2) && !strcmp(n1, n2);
1717 }
1718
1719 static inline void
1720 xml_attrs_init_key(struct xml_attrs_table *t UNUSED, struct xml_attr *a, struct xml_elem *e, char *name)
1721 {
1722   a->elem = e;
1723   a->name = name;
1724   a->val = NULL;
1725   slist_add_tail(&e->attrs, &a->n);
1726 }
1727
1728 #define HASH_PREFIX(x) xml_attrs_##x
1729 #define HASH_NODE struct xml_attr
1730 #define HASH_KEY_COMPLEX(x) x elem, x name
1731 #define HASH_KEY_DECL struct xml_elem *elem, char *name
1732 #define HASH_TABLE_DYNAMIC
1733 #define HASH_GIVE_EQ
1734 #define HASH_GIVE_HASHFN
1735 #define HASH_GIVE_INIT_KEY
1736 #define HASH_WANT_CLEANUP
1737 #define HASH_WANT_REMOVE
1738 #define HASH_WANT_LOOKUP
1739 #define HASH_WANT_FIND
1740 #define HASH_GIVE_ALLOC
1741 XML_HASH_GIVE_ALLOC
1742 #include "lib/hashtable.h"
1743
1744 void
1745 xml_init(struct xml_context *ctx)
1746 {
1747   bzero(ctx, sizeof(*ctx));
1748   ctx->pool = mp_new(65536);
1749   ctx->chars = fbgrow_create(4096);
1750   ctx->value = fbgrow_create(4096);
1751   xml_dtd_init(ctx);
1752   xml_attrs_init(ctx->tab_attrs = xml_hash_new(ctx->pool, sizeof(struct xml_attrs_table)));
1753 }
1754
1755 void
1756 xml_cleanup(struct xml_context *ctx)
1757 {
1758   xml_attrs_cleanup(ctx->tab_attrs);
1759   xml_dtd_cleanup(ctx);
1760   bclose(ctx->value);
1761   bclose(ctx->chars);
1762   mp_delete(ctx->pool);
1763 }
1764
1765 static void
1766 xml_parse_attr(struct xml_context *ctx)
1767 {
1768   // FIXME: memory management, dtd, literal
1769   TRACE(ctx, "parse_attr");
1770   struct xml_elem *e = ctx->elem;
1771   char *name = xml_parse_name(ctx);
1772   struct xml_attr *a = xml_attrs_lookup(ctx->tab_attrs, e, name);
1773   xml_parse_eq(ctx);
1774   char *val =xml_parse_system_literal(ctx);
1775   if (a->val)
1776     xml_error(ctx, "Attribute is not unique");
1777   else
1778     a->val = val;
1779 }
1780
1781 static void
1782 xml_parse_stag(struct xml_context *ctx)
1783 {
1784   // FIXME: dtd
1785   TRACE(ctx, "parse_stag");
1786   xml_push(ctx);
1787   struct xml_elem *e = mp_alloc_zero(ctx->pool, sizeof(*e));
1788   struct xml_elem *parent = ctx->elem;
1789   clist_init(&e->sons);
1790   e->node.parent = (void *)parent;
1791   ctx->elem = e;
1792   e->name = xml_parse_name(ctx);
1793   if (parent)
1794     clist_add_tail(&parent->sons, &e->node.n);
1795   else
1796     {
1797       ctx->root = e;
1798       if (ctx->document_type && strcmp(e->name, ctx->document_type))
1799         xml_error(ctx, "The root element does not match the document type");
1800     }
1801   while (1)
1802     {
1803       uns white = xml_parse_white(ctx, 0);
1804       uns c = xml_get_char(ctx);
1805       if (c == '/')
1806         {
1807           xml_parse_char(ctx, '>');
1808           ctx->flags |= XML_FLAG_EMPTY_ELEM;
1809           break;
1810         }
1811       else if (c == '>')
1812         break;
1813       else if (!white)
1814         xml_fatal_expected_white(ctx);
1815       xml_unget_char(ctx);
1816       xml_parse_attr(ctx);
1817     }
1818   if (ctx->h_element_start)
1819     ctx->h_element_start(ctx);
1820 }
1821
1822 static void
1823 xml_parse_etag(struct xml_context *ctx)
1824 {
1825   TRACE(ctx, "parse_etag");
1826   struct xml_elem *e = ctx->elem;
1827   ASSERT(e);
1828   char *name = xml_parse_name(ctx);
1829   if (strcmp(name, e->name))
1830     xml_fatal(ctx, "Invalid ETag, expected '%s'", e->name);
1831   xml_parse_white(ctx, 0);
1832   xml_parse_char(ctx, '>');
1833   xml_dec(ctx);
1834 }
1835
1836 static void
1837 xml_pop_element(struct xml_context *ctx)
1838 {
1839   TRACE(ctx, "pop_element");
1840   if (ctx->h_element_end)
1841     ctx->h_element_end(ctx);
1842   struct xml_elem *e = ctx->elem;
1843   if (ctx->flags & XML_DOM_FREE)
1844     {
1845       if (e->node.parent)
1846         clist_remove(&e->node.n);
1847       else
1848         ctx->root = NULL;
1849       SLIST_FOR_EACH(struct xml_attr *, a, e->attrs)
1850         xml_attrs_remove(ctx->tab_attrs, a);
1851       struct xml_node *n;
1852       while (n = clist_head(&e->sons))
1853         {
1854           if (n->type == XML_NODE_ELEM)
1855             {
1856               SLIST_FOR_EACH(struct xml_attr *, a, ((struct xml_elem *)n)->attrs)
1857                 xml_attrs_remove(ctx->tab_attrs, a);
1858               clist_insert_list_after(&((struct xml_elem *)n)->sons, &n->n);
1859             }
1860           clist_remove(&n->n);
1861         }
1862     }
1863   ctx->node = e->node.parent;
1864   xml_pop(ctx); // FIXME: memory management without XML_DOM_FREE
1865   xml_dec(ctx);
1866 #if 0
1867   for (struct xml_attribute *a = e->attrs; a; a = a->next)
1868     xml_attribute_remove(ctx->attribute_table, a);
1869 #endif
1870 }
1871
1872 static void
1873 xml_parse_element_decl(struct xml_context *ctx)
1874 {
1875   // FIXME
1876   mp_push(ctx->pool);
1877   xml_parse_seq(ctx, "<!ELEMENT");
1878   xml_parse_white(ctx, 1);
1879   xml_parse_name(ctx);
1880   xml_parse_white(ctx, 1);
1881
1882   uns c = xml_get_char(ctx);
1883   if (c == 'E')
1884     {
1885       xml_parse_seq(ctx, "MPTY");
1886       // FIXME
1887     }
1888   else if (c == 'A')
1889     {
1890       xml_parse_seq(ctx, "NY");
1891       // FIXME
1892     }
1893   else if (c == '(')
1894     {
1895       xml_parse_white(ctx, 0);
1896       if (xml_get_char(ctx) == '#')
1897         {
1898           xml_parse_seq(ctx, "PCDATA");
1899           while (1)
1900             {
1901               xml_parse_white(ctx, 0);
1902               if ((c = xml_get_char(ctx)) == ')')
1903                 break;
1904               else if (c != '|')
1905                 xml_fatal_expected(ctx, ')');
1906               xml_parse_white(ctx, 0);
1907               xml_parse_name(ctx);
1908               // FIXME
1909             }
1910         }
1911       else
1912         {
1913           xml_unget_char(ctx);
1914           uns depth = 1;
1915           while (1)
1916             {
1917               xml_parse_white(ctx, 0);
1918               if ((c = xml_get_char(ctx)) == '(')
1919                 {
1920                   depth++;
1921                 }
1922               else if (c == ')')
1923                 {
1924                   if ((c = xml_get_char(ctx)) == '?' || c == '*' || c == '+')
1925                     {
1926                     }
1927                   else
1928                     xml_unget_char(ctx);
1929                   if (!--depth)
1930                     break;
1931                 }
1932               else if (c == '|')
1933                 {
1934                 }
1935               else if (c == ',')
1936                 {
1937                 }
1938               else
1939                 {
1940                   xml_unget_char(ctx);
1941                   xml_parse_name(ctx);
1942                 }
1943             }
1944         }
1945     }
1946   else
1947     xml_fatal(ctx, "Expected element content specification");
1948
1949   xml_parse_white(ctx, 0);
1950   xml_parse_char(ctx, '>');
1951   mp_pop(ctx->pool);
1952 }
1953
1954 #if 0
1955 static void
1956 xml_parse_attr_list_decl(struct xml_context *ctx)
1957 {
1958   /* AttlistDecl ::= '<!ATTLIST' S Name AttDef* S? '>'
1959    * AttDef ::= S Name S AttType S DefaultDecl */
1960   xml_parse_seq(ctx, "ATTLIST");
1961   xml_parse_white(ctx, 1);
1962   struct xml_dtd_elem *e = xml_dtd_elems_lookup(ctx->dtd->tab_elems, xml_parse_name(ctx));
1963   e->attlist_declared = 1;
1964
1965   while (xml_parse_white(ctx, 0) && xml_get_char(ctx) != '>')
1966     {
1967       xml_unget_char(ctx);
1968       char *name = xml_parse_name(ctx);
1969       struct xml_dtd_attr *a = xml_dtd_attrs_find(ctx->dtd->tab_attrs, e, name);
1970       uns ignored = 0;
1971       if (a)
1972         {
1973           xml_warn(ctx, "Duplicate attribute definition");
1974           ignored++;
1975         }
1976       else
1977         a = xml_dtd_attrs_new(ctx->dtd->tab_attrs, e, name);
1978       xml_parse_white(ctx, 1);
1979       if (xml_get_char(ctx) == '(')
1980         {
1981           if (!ignored)
1982             a->type = XML_ATTR_ENUM;
1983           do
1984             {
1985               xml_parse_white(ctx, 0);
1986               char *value = xml_parse_nmtoken(ctx);
1987               if (!ignored)
1988                 if (xml_dtd_evals_find(ctx->dtd->tab_evals, a, value))
1989                   xml_error(ctx, "Duplicate enumeration value");
1990                 else
1991                   xml_dtd_evals_new(ctx->dtd->tab_evals, a, value);
1992               xml_parse_white(ctx, 0);
1993             }
1994           while (xml_get_char(ctx) == '|');
1995           xml_unget_char(ctx);
1996           xml_parse_char(ctx, ')');
1997         }
1998       else
1999         {
2000           xml_unget_char(ctx);
2001           char *type = xml_parse_name(ctx);
2002           enum xml_dtd_attribute_type t;
2003           if (!strcmp(type, "CDATA"))
2004             t = XML_ATTR_CDATA;
2005           else if (!strcmp(type, "ID"))
2006             t = XML_ATTR_ID;
2007           else if (!strcmp(type, "IDREF"))
2008             t = XML_ATTR_IDREF;
2009           else if (!strcmp(type, "IDREFS"))
2010             t = XML_ATTR_IDREFS;
2011           else if (!strcmp(type, "ENTITY"))
2012             t = XML_ATTR_ENTITY;
2013           else if (!strcmp(type, "ENTITIES"))
2014             t = XML_ATTR_ENTITIES;
2015           else if (!strcmp(type, "NMTOKEN"))
2016             t = XML_ATTR_NMTOKEN;
2017           else if (!strcmp(type, "NMTOKENS"))
2018             t = XML_ATTR_NMTOKENS;
2019           else if (!strcmp(type, "NOTATION"))
2020             {
2021               t = XML_ATTR_NOTATION;
2022               xml_parse_white(ctx, 1);
2023               xml_parse_char(ctx, '(');
2024               do
2025                 {
2026                   xml_parse_white(ctx, 0);
2027                   struct xml_dtd_notn *n = xml_dtd_notns_lookup(ctx->dtd->tab_notns, xml_parse_name(ctx));
2028                   if (!ignored)
2029                     if (xml_dtd_enotns_find(ctx->dtd->tab_enotns, a, n))
2030                       xml_error(ctx, "Duplicate enumerated notation");
2031                     else
2032                       xml_dtd_enotns_new(ctx->dtd->tab_enotns, a, n);
2033                   xml_parse_white(ctx, 0);
2034                 }
2035               while (xml_get_char(ctx) == '|');
2036               xml_unget_char(ctx);
2037               xml_parse_char(ctx, ')');
2038             }
2039           else
2040             xml_fatal(ctx, "Unknown attribute type");
2041           if (!ignored)
2042             a->type = t;
2043         }
2044       xml_parse_white(ctx, 1);
2045       enum xml_dtd_attribute_default def = XML_ATTR_NONE;
2046       if (xml_get_char(ctx) == '#')
2047         switch (xml_get_char(ctx))
2048           {
2049             case 'R':
2050               xml_parse_seq(ctx, "EQUIRED");
2051               def = XML_ATTR_REQUIRED;
2052               break;
2053             case 'I':
2054               xml_parse_seq(ctx, "MPLIED");
2055               def = XML_ATTR_IMPLIED;
2056               break;
2057             case 'F':
2058               xml_parse_seq(ctx, "IXED");
2059               def = XML_ATTR_FIXED;
2060               break;
2061             default:
2062               xml_fatal(ctx, "Expected a modifier for default attribute value");
2063           }
2064       else
2065         xml_unget_char(ctx);
2066       if (def != XML_ATTR_REQUIRED && def != XML_ATTR_IMPLIED)
2067         {
2068           xml_parse_system_literal(ctx);
2069           // FIXME
2070         }
2071     }
2072 }
2073 #endif
2074
2075 static void
2076 xml_parse_doctype_decl(struct xml_context *ctx)
2077 {
2078   if (ctx->document_type)
2079     xml_fatal(ctx, "Multiple document types not allowed");
2080   xml_parse_seq(ctx, "DOCTYPE");
2081   xml_parse_white(ctx, 1);
2082   ctx->document_type = xml_parse_name(ctx);
2083   TRACE(ctx, "doctyype=%s", ctx->document_type);
2084   uns white = xml_parse_white(ctx, 0);
2085   uns c = xml_peek_char(ctx);
2086   if (c != '>' && c != '[' && white)
2087     {
2088       xml_parse_external_id(ctx, &ctx->eid, 0, 0);
2089       xml_parse_white(ctx, 0);
2090       ctx->flags |= XML_FLAG_HAS_EXTERNAL_SUBSET;
2091     }
2092   if (xml_peek_char(ctx) == '[')
2093     ctx->flags |= XML_FLAG_HAS_INTERNAL_SUBSET;
2094   if (ctx->h_doctype_decl)
2095     ctx->h_doctype_decl(ctx);
2096 }
2097
2098 int
2099 xml_next(struct xml_context *ctx)
2100 {
2101   /* A nasty state machine */
2102
2103   TRACE(ctx, "xml_next (state=%u)", ctx->state);
2104   jmp_buf throw_buf;
2105   ctx->throw_buf = &throw_buf;
2106   if (setjmp(throw_buf))
2107     {
2108 error:
2109       if (ctx->err_code == XML_ERR_EOF && ctx->h_fatal)
2110         ctx->h_fatal(ctx);
2111       ctx->state = XML_STATE_FATAL;
2112       TRACE(ctx, "raised fatal error");
2113       return -1;
2114     }
2115   uns c;
2116   switch (ctx->state)
2117     {
2118       case XML_STATE_FATAL:
2119         return -1;
2120
2121       case XML_STATE_START:
2122         TRACE(ctx, "entering prolog");
2123         if (ctx->h_document_start)
2124           ctx->h_document_start(ctx);
2125         /* XMLDecl */
2126         xml_refill(ctx);
2127         if (ctx->h_xml_decl)
2128           ctx->h_xml_decl(ctx);
2129         if (ctx->want & XML_WANT_DECL)
2130           return ctx->state = XML_STATE_DECL;
2131       case XML_STATE_DECL:
2132
2133         /* Misc* (doctypedecl Misc*)? */
2134         while (1)
2135           {
2136             xml_parse_white(ctx, 0);
2137             xml_parse_char(ctx, '<');
2138             if ((c = xml_get_char(ctx)) == '?')
2139               /* Processing intruction */
2140               if (!(ctx->want & XML_WANT_PI))
2141                 xml_skip_pi(ctx);
2142               else
2143                 {
2144                   xml_push_pi(ctx);
2145                   ctx->state = XML_STATE_PROLOG_PI;
2146                   return XML_STATE_PI;
2147       case XML_STATE_PROLOG_PI:
2148                   xml_pop_pi(ctx);
2149                 }
2150             else if (c != '!')
2151               {
2152                 /* Found the root tag */
2153                 xml_unget_char(ctx);
2154                 goto first_tag;
2155               }
2156             else if (xml_get_char(ctx) == '-')
2157               if (!(ctx->want & XML_WANT_COMMENT))
2158                 xml_skip_comment(ctx);
2159               else
2160                 {
2161                   xml_push_comment(ctx);
2162                   ctx->state = XML_STATE_PROLOG_COMMENT;
2163                   return XML_STATE_COMMENT;
2164       case XML_STATE_PROLOG_COMMENT:
2165                   xml_pop_comment(ctx);
2166                 }
2167             else
2168               {
2169                 /* DocTypeDecl */
2170                 xml_unget_char(ctx);
2171                 xml_parse_doctype_decl(ctx);
2172                 if (ctx->want & XML_WANT_DOCUMENT_TYPE)
2173                   return ctx->state = XML_STATE_DOCUMENT_TYPE;
2174       case XML_STATE_DOCUMENT_TYPE:
2175                 if (xml_peek_char(ctx) == '[')
2176                   {
2177                     xml_skip_char(ctx);
2178                     xml_inc(ctx);
2179                     xml_parse_internal_subset(ctx);
2180                     xml_parse_white(ctx, 0);
2181                   }
2182                 xml_parse_char(ctx, '>');
2183               }
2184           }
2185
2186       case XML_STATE_PI:
2187         mp_pop(ctx->pool);
2188       case XML_STATE_COMMENT:
2189         fbgrow_reset(ctx->value);
2190
2191       case XML_STATE_CHARS:
2192
2193         while (1)
2194           {
2195             if (xml_peek_char(ctx) != '<')
2196               {
2197                 /* CharData */
2198                 xml_parse_chars(ctx);
2199                 continue;
2200               }
2201             else
2202               xml_skip_char(ctx);
2203 first_tag: ;
2204
2205             xml_inc(ctx);
2206             if ((c = xml_get_char(ctx)) == '?')
2207               {
2208                 /* PI */
2209                 if (!(ctx->want & XML_WANT_PI))
2210                   xml_skip_pi(ctx);
2211                 else
2212                   {
2213                     if (btell(ctx->chars))
2214                       {
2215                         fbgrow_rewind(ctx->chars);
2216                         ctx->state = XML_STATE_CHARS_BEFORE_PI;
2217                         return XML_STATE_PI;
2218       case XML_STATE_CHARS_BEFORE_PI:
2219                         fbgrow_reset(ctx->chars);
2220                       }
2221                     xml_push_pi(ctx);
2222                     return ctx->state = XML_STATE_PI;
2223                   }
2224               }
2225
2226             else if (c == '!')
2227               if ((c = xml_get_char(ctx)) == '-')
2228                 {
2229                   /* Comment */
2230                   if (!(ctx->want & XML_WANT_COMMENT))
2231                     xml_skip_comment(ctx);
2232                   else
2233                     {
2234                       if (btell(ctx->chars))
2235                         {
2236                           fbgrow_rewind(ctx->chars);
2237                           ctx->state = XML_STATE_CHARS_BEFORE_COMMENT;
2238                           return XML_STATE_CHARS;
2239       case XML_STATE_CHARS_BEFORE_COMMENT:
2240                           fbgrow_reset(ctx->chars);
2241                         }
2242                       xml_push_comment(ctx);
2243                       return ctx->state = XML_STATE_COMMENT;
2244                     }
2245                 }
2246               else if (c == '[')
2247                 {
2248                   /* CDATA */
2249                   if (!(ctx->want & XML_WANT_CDATA))
2250                     xml_skip_cdata(ctx);
2251                   else
2252                     {
2253                       if (btell(ctx->chars))
2254                         {
2255                           fbgrow_rewind(ctx->chars);
2256                           ctx->state = XML_STATE_CHARS_BEFORE_CDATA;
2257                           return XML_STATE_CHARS;
2258       case XML_STATE_CHARS_BEFORE_CDATA:
2259                           fbgrow_reset(ctx->chars);
2260                         }
2261                       xml_parse_cdata(ctx);
2262                       if (btell(ctx->chars))
2263                         {
2264                           fbgrow_rewind(ctx->chars);
2265                           return ctx->state = XML_STATE_CDATA;
2266                         }
2267       case XML_STATE_CDATA:
2268                       fbgrow_reset(ctx->chars);
2269                     }
2270                 }
2271               else
2272                 xml_fatal(ctx, "Unexpected character after '<!'");
2273
2274             else if (c != '/')
2275               {
2276                 /* STag | EmptyElemTag */
2277                 xml_unget_char(ctx);
2278                 if (btell(ctx->chars))
2279                   {
2280                     fbgrow_rewind(ctx->chars);
2281                     ctx->state = XML_STATE_CHARS_BEFORE_STAG;
2282                     return XML_STATE_CHARS;
2283       case XML_STATE_CHARS_BEFORE_STAG:
2284                     fbgrow_reset(ctx->chars);
2285                   }
2286
2287                 xml_parse_stag(ctx);
2288                 if (ctx->want & XML_WANT_STAG)
2289                   return ctx->state = XML_STATE_STAG;
2290       case XML_STATE_STAG:
2291                 if (ctx->flags & XML_FLAG_EMPTY_ELEM)
2292                   goto pop_element;
2293               }
2294
2295             else
2296               {
2297                 /* ETag */
2298                 if (btell(ctx->chars))
2299                   {
2300                     fbgrow_rewind(ctx->chars);
2301                     ctx->state = XML_STATE_CHARS_BEFORE_ETAG;
2302                     return XML_STATE_CHARS;
2303       case XML_STATE_CHARS_BEFORE_ETAG:
2304                     fbgrow_reset(ctx->chars);
2305                   }
2306
2307                 xml_parse_etag(ctx);
2308 pop_element:
2309                 if (ctx->want & XML_WANT_ETAG)
2310                   return ctx->state = XML_STATE_ETAG;
2311       case XML_STATE_ETAG:
2312                 xml_pop_element(ctx);
2313                 if (!ctx->elem)
2314                   goto epilog;
2315               }
2316           }
2317
2318 epilog:
2319         /* Misc* */
2320         TRACE(ctx, "entering epilog");
2321         while (1)
2322           {
2323             /* Epilog whitespace is the only place, where a valid document can reach EOF */
2324             if (setjmp(throw_buf))
2325               if (ctx->err_code == XML_ERR_EOF)
2326                 {
2327                   TRACE(ctx, "reached EOF");
2328                   ctx->state = XML_STATE_EOF;
2329                   if (ctx->h_document_end)
2330                     ctx->h_document_end(ctx);
2331       case XML_STATE_EOF:
2332                   return XML_STATE_EOF;
2333                 }
2334               else
2335                 goto error;
2336             xml_parse_white(ctx, 0);
2337             if (setjmp(throw_buf))
2338               goto error;
2339
2340             /* Misc */
2341             xml_parse_char(ctx, '<');
2342             if ((c = xml_get_char(ctx)) == '?')
2343               /* Processing instruction */
2344               if (!(ctx->want & XML_WANT_PI))
2345                 xml_skip_pi(ctx);
2346               else
2347                 {
2348                   xml_push_pi(ctx);
2349                   return ctx->state = XML_STATE_EPILOG_PI, XML_STATE_PI;
2350       case XML_STATE_EPILOG_PI:
2351                   xml_pop_pi(ctx);
2352                 }
2353             else if (c == '!')
2354               /* Comment */
2355               if (!(ctx->want & XML_WANT_COMMENT))
2356                 xml_skip_comment(ctx);
2357               else
2358                 {
2359                   xml_push_comment(ctx);
2360                   return ctx->state = XML_STATE_EPILOG_COMMENT, XML_STATE_COMMENT;
2361       case XML_STATE_EPILOG_COMMENT:
2362                   xml_pop_comment(ctx);
2363                 }
2364             else
2365               xml_fatal(ctx, "Syntax error in the epilog");
2366           }
2367
2368     }
2369   return -1;
2370 }
2371
2372 #ifdef TEST
2373
2374 static void
2375 error(struct xml_context *ctx)
2376 {
2377   msg((ctx->err_code < XML_ERR_ERROR) ? L_WARN_R : L_ERROR_R, "XML %u: %s", xml_row(ctx), ctx->err_msg);
2378 }
2379
2380 static void
2381 test(struct fastbuf *in, struct fastbuf *out)
2382 {
2383   struct xml_context ctx;
2384   xml_init(&ctx);
2385   ctx.h_warn = ctx.h_error = ctx.h_fatal = error;
2386   ctx.want = XML_WANT_ALL;
2387   ctx.flags |= XML_DOM_FREE;
2388   xml_set_source(&ctx, in);
2389   int state;
2390   while ((state = xml_next(&ctx)) >= 0)
2391     switch (state)
2392       {
2393         case XML_STATE_CHARS:
2394           bprintf(out, "CHARS [%.*s]\n", (int)(ctx.chars->bstop - ctx.chars->buffer), ctx.chars->buffer);
2395           break;
2396         case XML_STATE_STAG:
2397           bprintf(out, "STAG <%s>\n", ctx.elem->name);
2398           SLIST_FOR_EACH(struct xml_attr *, a, ctx.elem->attrs)
2399             bprintf(out, "  ATTR %s=[%s]\n", a->name, a->val);
2400           break;
2401         case XML_STATE_ETAG:
2402           bprintf(out, "ETAG </%s>\n", ctx.elem->name);
2403           break;
2404         case XML_STATE_COMMENT:
2405           bprintf(out, "COMMENT [%.*s]\n", (int)(ctx.value->bstop - ctx.value->buffer), ctx.value->buffer);
2406           break;
2407         case XML_STATE_PI:
2408           bprintf(out, "PI [%s] [%.*s]\n", ctx.name, (int)(ctx.value->bstop - ctx.value->buffer), ctx.value->buffer);
2409           break;
2410         case XML_STATE_CDATA:
2411           bprintf(out, "CDATA [%.*s]\n", (int)(ctx.chars->bstop - ctx.chars->buffer), ctx.chars->buffer);
2412           break;
2413         case XML_STATE_EOF:
2414           bprintf(out, "EOF\n");
2415           goto end;
2416           break;
2417       }
2418 end:
2419   xml_cleanup(&ctx);
2420 }
2421
2422 int
2423 main(void)
2424 {
2425   struct fastbuf *in = bfdopen_shared(0, 1024);
2426   struct fastbuf *out = bfdopen_shared(1, 1024);
2427   test(in, out);
2428   bclose(out);
2429   return 0;
2430 }
2431
2432 #endif