WDL/xmlparse.h

   1 /*
   2     WDL - xmlparse.h
   3     Copyright (C) 2016 and later, Cockos Incorporated
   4
   5     This software is provided 'as-is', without any express or implied
   6     warranty.  In no event will the authors be held liable for any damages
   7     arising from the use of this software.
   8
   9     Permission is granted to anyone to use this software for any purpose,
  10     including commercial applications, and to alter it and redistribute it
  11     freely, subject to the following restrictions:
  12
  13     1. The origin of this software must not be misrepresented; you must not
  14        claim that you wrote the original software. If you use this software
  15        in a product, an acknowledgment in the product documentation would be
  16        appreciated but is not required.
  17     2. Altered source versions must be plainly marked as such, and must not be
  18        misrepresented as being the original software.
  19     3. This notice may not be removed or altered from any source distribution.
  20
  21 very very very lightweight XML parser
  22
  23 reads: <?xml, <!DOCTYPE, <![CDATA[, &lt;&gt;&amp;&quot;&apos;&#xABC;&#123; ignores unknown <?tag blocks?>
  24 always uses 8-bit characters, uses UTF-8 encoding for &#xyz
  25 relatively strict. for overflow safety, enforces a token length limit of 512MB
  26
  27 */
  28
  29 #ifndef _WDL_XML_PARSE_H_
  30 #define _WDL_XML_PARSE_H_
  31 #include "ptrlist.h"
  32 #include "assocarray.h"
  33 #include "wdlstring.h"
  34 #include "wdlutf8.h"
  35
  36 class wdl_xml_element {
  37     static int attr_cmp(char **a, char **b) { return strcmp(*a,*b); }
  38     static void attr_free(char *a) { free(a); }
  39   public:
  40     wdl_xml_element(const char *_name, int _line, int _col, bool _sort_attr=true) :
  41       attributes(attr_cmp,NULL,attr_free,attr_free), name(strdup(_name)), line(_line), col(_col),
  42       m_sort_attributes(_sort_attr), m_has_discrete_close(false) { }
  43     ~wdl_xml_element() { free(name); elements.Empty(true); }
  44
  45     WDL_PtrList<wdl_xml_element> elements;
  46     WDL_AssocArray<char *, char *> attributes;
  47     WDL_FastString value; // value excluding any leading whitespace and excluding any elements
  48
  49     char *name;
  50     int line, col;
  51     bool m_sort_attributes;
  52     bool m_has_discrete_close;
  53
  54     const char *get_attribute(const char *v, const char *def=NULL) const
  55     {
  56       if (!m_sort_attributes)
  57       {
  58         const int n = attributes.GetSize();
  59         for (int x = 0; x < n; x ++)
  60         {
  61           char *key = NULL;
  62           const char *val = attributes.Enumerate(x,&key);
  63           if (key && !strcmp(key,v)) return val;
  64         }
  65       }
  66       return attributes.Get((char*)v,(char*)def);
  67     }
  68 };
  69
  70 class wdl_xml_parser {
  71   public:
  72     wdl_xml_parser(const char *rdptr, int rdptr_len, bool sort_attributes=true) :
  73       element_xml(NULL), element_root(NULL),
  74       m_rdptr((const unsigned char *)rdptr), m_err(NULL),
  75       m_rdptr_len(rdptr_len), m_line(1), m_col(0), m_lastchar(0),
  76       m_last_line(1),m_last_col(0),
  77       m_sort_attributes(sort_attributes)
  78     {
  79     }
  80     virtual ~wdl_xml_parser()
  81     {
  82       delete element_xml;
  83       delete element_root;
  84       element_doctype_tokens.Empty(true,free);
  85     }
  86
  87     const char *parse() // call only once, returns NULL on success, error message on failure
  88     {
  89       m_lastchar = nextchar();
  90
  91       if (!m_tok.ResizeOK(256)) return "token buffer malloc fail";
  92
  93       const char *p = parse_element_body(NULL);
  94       if (m_err) return m_err;
  95       if (p) return p;
  96       if (get_tok()) return "document: extra characters following root element";
  97
  98       return NULL;
  99     }
 100
 101     // output
 102     WDL_PtrList<char> element_doctype_tokens; // tokens after <!DOCTYPE
 103     wdl_xml_element *element_xml, *element_root;
 104
 105     // get location  after parse() returns error
 106     int getLine() const { return m_last_line; }
 107     int getCol() const { return m_last_col; }
 108
 109
 110   private:
 111
 112     WDL_HeapBuf m_tok;
 113     const unsigned char *m_rdptr;
 114     const char *m_err;
 115     int m_rdptr_len, m_line, m_col, m_lastchar, m_last_line,m_last_col;
 116     bool m_sort_attributes;
 117
 118     virtual int moredata(const char **dataOut) { return 0; }
 119
 120     int nextchar()
 121     {
 122       if (m_rdptr_len < 1 && (m_rdptr_len = moredata((const char **)&m_rdptr)) < 1) return -1;
 123
 124       m_rdptr_len--;
 125       const int ret = (int)*m_rdptr++;
 126
 127       if (ret == '\n') { m_line++; m_col=0; }
 128       else m_col++;
 129
 130       return ret;
 131     }
 132
 133     int skip_whitespace()
 134     {
 135       int rv=0, lc = m_lastchar;
 136       while (char_type(lc) < 0) { lc = nextchar(); rv++; }
 137       m_lastchar = lc;
 138       return rv;
 139     }
 140
 141     static int char_type(int c)
 142     {
 143       switch (c)
 144       {
 145         case ' ': case '\r': case '\n': case '\t':
 146           return -1;
 147
 148         case '/': case '!': case '\\': case '\'': case '"': case '#': case '$':
 149         case '%': case '(': case ')': case '*': case '+': case ',': case ';':
 150         case '=': case '>': case '?': case '@': case '[': case ']': case '^':
 151         case '`': case '{': case '|': case '}': case '~':
 152           return 1;
 153
 154         case '<': case '&':
 155           return 2;
 156
 157         case '-': case '.':
 158           return 4;
 159       }
 160       return 0;
 161     }
 162
 163     unsigned char *realloc_tok(int &tok_sz)
 164     {
 165       tok_sz += tok_sz + tok_sz / 4;
 166       if (tok_sz >= (1<<29))
 167       {
 168         m_err="token buffer tried to malloc() more than 512MB, probably unsafe and invalid XML";
 169         return NULL;
 170       }
 171       unsigned char *t = (unsigned char *) m_tok.ResizeOK(tok_sz);
 172       if (!t) m_err="token buffer malloc fail";
 173       return t;
 174     }
 175
 176     // gets a token, normally skipping whitespace, but if get_tok(true), then return NULL on whitespace
 177     const char *get_tok(bool no_skip_whitespace=false)
 178     {
 179       if (!no_skip_whitespace) skip_whitespace();
 180
 181       m_last_line = m_line;
 182       m_last_col = m_col;
 183
 184       int wrpos=0, lc = m_lastchar, tok_sz = m_tok.GetSize();
 185       unsigned char *tok_buf = (unsigned char *)m_tok.Get();
 186       switch (lc > 0 ? char_type(lc) : -2)
 187       {
 188         case 0:
 189           do
 190           {
 191             tok_buf[wrpos++] = lc;
 192             if (WDL_unlikely(wrpos >= tok_sz) && WDL_unlikely(!(tok_buf=realloc_tok(tok_sz)))) return NULL;
 193             lc = nextchar();
 194           }
 195           while (lc > 0 && !(char_type(lc)&~4));
 196         break;
 197
 198         case 1:
 199         case 2:
 200         case 4:
 201           if (lc == '\'' || lc == '\"')
 202           {
 203             const int endc = lc;
 204             tok_buf[wrpos++] = lc;
 205             lc = nextchar();
 206             while (lc > 0)
 207             {
 208               if (lc == '<')
 209               {
 210                 m_last_line=m_line; m_last_col=m_col;
 211                 m_err="illegal '<' character in quoted string";
 212                 m_lastchar = lc;
 213                 return NULL;
 214               }
 215
 216               if (lc == '&')
 217               {
 218                 m_lastchar = lc;
 219                 if (WDL_unlikely(wrpos+8 >= tok_sz) && WDL_unlikely(!(tok_buf=realloc_tok(tok_sz)))) return NULL;
 220
 221                 const int tmp[2]={m_line,m_col};
 222                 if (!decode_entity((char*)tok_buf+wrpos))
 223                 {
 224                   m_last_line=tmp[0]; m_last_col=tmp[1];
 225                   m_err="unknown entity in quoted string";
 226                   return NULL;
 227                 }
 228                 lc = m_lastchar;
 229                 while (tok_buf[wrpos]) wrpos++;
 230               }
 231               else
 232               {
 233                 const int llc = lc;
 234                 tok_buf[wrpos++] = lc;
 235                 if (WDL_unlikely(wrpos >= tok_sz) && WDL_unlikely(!(tok_buf=realloc_tok(tok_sz)))) return NULL;
 236                 lc = nextchar();
 237
 238                 if (llc == endc) break;
 239               }
 240             }
 241           }
 242           else
 243           {
 244             tok_buf[wrpos++] = lc;
 245             if (WDL_unlikely(wrpos >= tok_sz) && WDL_unlikely(!(tok_buf=realloc_tok(tok_sz)))) return NULL;
 246
 247             lc = nextchar();
 248           }
 249         break;
 250         case -1:
 251           m_err="unexpected whitespace";
 252         return NULL;
 253         default:
 254           m_err="unexpected end of file";
 255         return NULL;
 256       }
 257       tok_buf[wrpos]=0;
 258       m_lastchar = lc;
 259       return (char *)tok_buf;
 260     }
 261
 262     bool decode_entity(char *wr) // will never write more than 8 bytes
 263     {
 264       char tmp[32];
 265       int i=0;
 266       while (i < 31 && (m_lastchar = nextchar()) > 0 && m_lastchar != ';')
 267       {
 268         if (char_type(m_lastchar) && m_lastchar != '#') break;
 269         tmp[i++] = m_lastchar;
 270       }
 271       int byteval = 0;
 272       if (m_lastchar == ';')
 273       {
 274         tmp[i]=0;
 275         if (!strcmp(tmp,"lt")) byteval = '<';
 276         else if (!strcmp(tmp,"gt")) byteval = '>';
 277         else if (!strcmp(tmp,"amp")) byteval = '&';
 278         else if (!strcmp(tmp,"apos")) byteval = '\'';
 279         else if (!strcmp(tmp,"quot")) byteval = '"';
 280         else if (tmp[0] == '#')
 281         {
 282           if (tmp[1] >= '0' && tmp[1] <= '9') byteval = atoi(tmp+1);
 283           if (tmp[1] == 'x') byteval = strtol(tmp+1,NULL,16);
 284         }
 285       }
 286       if (!byteval) return false;
 287       WDL_MakeUTFChar((char*)wr,byteval,8);
 288       m_lastchar = nextchar();
 289       return true;
 290     }
 291
 292     bool skip_until(const char *tok, const char *a, const char *b)
 293     {
 294       bool state=false;
 295       if (!tok) tok = get_tok();
 296       while (tok)
 297       {
 298         if (state && !strcmp(b,tok)) return true;
 299         state = !strcmp(a,tok);
 300         if (state && !b) return true;
 301
 302         if (skip_whitespace()) state=false;
 303         tok = get_tok(true);
 304       }
 305
 306       return false;
 307     }
 308
 309     const char *parse_element_attributes(wdl_xml_element *elem)
 310     {
 311       char *attr_name=NULL;
 312       for (;;)
 313       {
 314         const char *tok = get_tok();
 315         if (!tok) break;
 316
 317         if (*tok == '-' || *tok == '.' || (*tok >= '0' && *tok <= '9')) { m_err="attribute must not begin with .- or number"; break; }
 318
 319         if (char_type(*tok)) return tok;
 320
 321         char *attr_name = strdup(tok);
 322         if (!attr_name) { m_err="malloc fail"; break; }
 323
 324         if (m_sort_attributes &&
 325             elem->attributes.Get(attr_name))
 326         {
 327           m_err="attribute specified more than once";
 328           break;
 329         }
 330
 331         tok = get_tok();
 332         if (!tok) break;
 333         if (*tok != '=') { m_err="attribute name must be followed by '='"; break; }
 334
 335         tok = get_tok();
 336         if (!tok) break;
 337         if (*tok != '\'' && *tok != '"') { m_err="attribute value must be quoted string"; break; }
 338
 339         const size_t tok_len = strlen(tok);
 340         if (tok_len < 2 || tok[tok_len-1] != tok[0]) { m_err="attribute value missing trailing quote"; break;  }
 341
 342         char *value = (char *)malloc(tok_len-2+1);
 343         if (!value) { m_err="malloc fail"; break; }
 344
 345         memcpy(value,tok+1,tok_len-2);
 346         value[tok_len-2]=0;
 347
 348         if (m_sort_attributes)
 349           elem->attributes.Insert(attr_name,value);
 350         else
 351           elem->attributes.AddUnsorted(attr_name,value);
 352
 353         attr_name = NULL;
 354       }
 355       free(attr_name);
 356       return NULL;
 357     }
 358
 359     const char *parse_element_body(wdl_xml_element *elem) // return NULL on success, error message on failure
 360     {
 361       int cnt=0;
 362       for (;;)
 363       {
 364         if (elem)
 365         {
 366           bool want_add = elem->value.GetLength() > 0;
 367           while (m_lastchar != '<' && m_lastchar > 0)
 368           {
 369             if (!want_add && char_type(m_lastchar)>=0) want_add=true;
 370
 371             bool adv=true;
 372             if (m_lastchar == '&')
 373             {
 374               m_last_line=m_line; m_last_col=m_col;
 375               char buf[8];
 376               if (!decode_entity(buf)) return "unknown entity in element body";
 377               elem->value.Append(buf);
 378               adv=false;
 379             }
 380             else if (want_add)
 381             {
 382               unsigned char c = (unsigned char)m_lastchar;
 383               elem->value.Append((const char *)&c,1);
 384             }
 385
 386             if (adv) m_lastchar = nextchar();
 387           }
 388         }
 389
 390         const char *tok = get_tok(elem != NULL);
 391         const int start_line = m_last_line, start_col = m_last_col;
 392         if (!tok) return elem ? "unterminated block" : NULL;
 393         if (*tok != '<') return "expected < tag";
 394
 395         tok = get_tok(true);
 396         if (!tok) return "expected token after <";
 397
 398         if (tok[0] == '!')
 399         {
 400           tok = get_tok(true);
 401           if (!tok) return "expected token following <!";
 402
 403           if (*tok == '-')
 404           {
 405             tok = get_tok(true);
 406             if (!tok) return "expected token following <!-";
 407             if (*tok != '-') return "unknown token following <!-";
 408             if (!skip_until(NULL,"-","-"))
 409             {
 410               m_last_line=start_line;
 411               m_last_col=start_col;
 412               return m_err = "unterminated comment";
 413             }
 414             tok = get_tok(true);
 415             if (!tok || tok[0] != '>') return "-- not allowed in comment";
 416           }
 417           else if (*tok == '[')
 418           {
 419             if (!elem) return "<![ not allowed at document level";
 420             tok = get_tok(true);
 421             if (!tok || strcmp(tok,"CDATA")) return "unknown token beginning <![";
 422             tok=get_tok(true);
 423             if (!tok || tok[0] != '[') return "unknown token beginning <![CDATA but without trailing [";
 424
 425             // add content literally until ]]>
 426             int lc=m_lastchar, last1=0,last2=0;
 427             for (;;)
 428             {
 429               if (lc == '>' && last1 == ']' && last2 == ']') break;
 430
 431               unsigned char c = (unsigned char)lc;
 432               elem->value.Append((const char *)&c,1);
 433               last2 = last1;
 434               last1 = lc;
 435
 436               lc = nextchar();
 437               if (lc <= 0)
 438               {
 439                 m_lastchar = -1;
 440                 m_last_line=start_line;
 441                 m_last_col=start_col;
 442                 return m_err = "unterminated <![CDATA[";
 443               }
 444             }
 445             elem->value.SetLen(elem->value.GetLength()-2); // remove ]]
 446             m_lastchar = nextchar();
 447
 448           }
 449           else if (!strcmp(tok,"DOCTYPE"))
 450           {
 451             if (elem) return "<!DOCTYPE must be at top level";
 452             if (element_doctype_tokens.GetSize()) return "<!DOCTYPE already specified";
 453
 454             tok = get_tok();
 455             if (!tok || char_type(*tok)) return "expected document type token following <!DOCTYPE";
 456             do
 457             {
 458               element_doctype_tokens.Add(strdup(tok));
 459               tok = get_tok();
 460               if (!tok)
 461               {
 462                 m_last_line=start_line;
 463                 m_last_col=start_col;
 464                 return m_err = "unterminated <!DOCTYPE";
 465               }
 466             } while (tok[0] != '>');
 467           }
 468           else return "unknown token following <!";
 469         }
 470         else if (tok[0] == '?')
 471         {
 472           tok = get_tok(true);
 473           if (!tok) return "expected token following <?";
 474
 475           if (!strcmp(tok,"xml"))
 476           {
 477             if (elem || cnt || element_xml) return "<?xml must begin document";
 478
 479             element_xml = new wdl_xml_element("xml",start_line,start_col,m_sort_attributes);
 480             tok = parse_element_attributes(element_xml);
 481             if (!tok || tok[0] != '?' || !(tok=get_tok(true)) || tok[0] != '>')
 482               return "<?xml not terminated";
 483           }
 484           else
 485           {
 486             if (!skip_until(tok, "?",">"))
 487             {
 488               m_last_line=start_line;
 489               m_last_col=start_col;
 490               return m_err = "unterminated <? block";
 491             }
 492           }
 493         }
 494         else if (tok[0] == '/')
 495         {
 496           if (!elem) return "unexpected </ at root level";
 497
 498           tok = get_tok(true);
 499           if (strcmp(tok,elem->name))
 500           {
 501             return "mismatched </ tag name";
 502           }
 503
 504           tok = get_tok();
 505           if (!tok || tok[0] != '>') return "expected > following </tag";
 506           // done!
 507           elem->m_has_discrete_close = true;
 508           return NULL;
 509         }
 510         else
 511         {
 512           if (*tok == '-' || *tok == '.' || (*tok >= '0' && *tok <= '9'))
 513             return "element name must not begin with .- or number";
 514
 515           wdl_xml_element *sub = new wdl_xml_element(tok,start_line,start_col,m_sort_attributes);
 516           if (elem) elem->elements.Add(sub);
 517           else element_root = sub;
 518
 519           tok = parse_element_attributes(sub);
 520           if (!tok) return "unterminated element";
 521
 522           if (*tok == '/')
 523           {
 524             tok = get_tok(true);
 525             if (!tok || *tok != '>') return "expected > following / to end element";
 526           }
 527           else if (*tok == '>')
 528           {
 529             const char *ret = parse_element_body(sub);
 530             if (ret) return ret;
 531           }
 532           else
 533           {
 534             return "unknown token in element";
 535           }
 536           if (!elem) return NULL; // finish after parsing a top level block
 537         }
 538         cnt++;
 539       }
 540     }
 541 };
 542
 543 class wdl_xml_fileread : public wdl_xml_parser {
 544   FILE *m_fp;
 545   char m_buf[1024];
 546   int m_charset;
 547
 548   virtual int moredata(const char **dataptr)
 549   {
 550     *dataptr = m_buf;
 551     const int cs = m_charset;
 552     if (m_fp) switch (cs)
 553     {
 554       case 0:
 555         return (int) fread(m_buf,1,sizeof(m_buf),m_fp);
 556       case 1:
 557       case 2:
 558         {
 559           unsigned char tmp[128];
 560           const int l = (int) fread(tmp,1,sizeof(tmp),m_fp);
 561           int rd=0, wpos=0;
 562           while (rd+1 < l)
 563           {
 564             const int amt=wdl_utf8_makechar(cs==1 ? ((tmp[rd]<<8)|tmp[rd+1]) : (tmp[rd]|(tmp[rd+1]<<8)),
 565                 m_buf+wpos,
 566                 (int)sizeof(m_buf)-wpos);
 567             if (amt>0) wpos += amt;
 568
 569             rd+=2;
 570           }
 571           return wpos;
 572         }
 573     }
 574     return 0;
 575   }
 576 public:
 577   wdl_xml_fileread(FILE *fp) : wdl_xml_parser(NULL,0)
 578   {
 579     m_fp=fp;
 580     m_charset=0; // default to utf-8
 581     if (fp)
 582     {
 583       unsigned char bom[2];
 584       if (fread(bom,1,2,fp)==2)
 585       {
 586         if (bom[0] == 0xEF && bom[1] == 0xBB && fgetc(fp) == 0xBF) m_charset=0;
 587         else if (bom[0] == 0xFE && bom[1] == 0xFF) m_charset=1; // utf-16 BE
 588         else if (bom[0] == 0xFF && bom[1] == 0xFE) m_charset=2; // utf-16 LE
 589         else fseek(fp,0,SEEK_SET); // rewind
 590       }
 591     }
 592   }
 593   virtual ~wdl_xml_fileread() { if (m_fp) fclose(m_fp); }
 594 };
 595
 596 #endif
 597