xmlparse.c

/* 5de44e6750c6cc78818f06ed552f522a1241df0299395250e1792cb339389daf (2.8.2+)
                            __  __            _
                         ___\ \/ /_ __   __ _| |_
                        / _ \\  /| '_ \ / _` | __|
                       |  __//  \| |_) | (_| | |_
                        \___/_/\_\ .__/ \__,_|\__|
                                 |_| XML parser

   Copyright (c) 1997-2000 Thai Open Source Software Center Ltd
   Copyright (c) 2000      Clark Cooper <coopercc@users.sourceforge.net>
   Copyright (c) 2000-2006 Fred L. Drake, Jr. <fdrake@users.sourceforge.net>
   Copyright (c) 2001-2002 Greg Stein <gstein@users.sourceforge.net>
   Copyright (c) 2002-2016 Karl Waclawek <karl@waclawek.net>
   Copyright (c) 2005-2009 Steven Solie <steven@solie.ca>
   Copyright (c) 2016      Eric Rahm <erahm@mozilla.com>
   Copyright (c) 2016-2026 Sebastian Pipping <sebastian@pipping.org>
   Copyright (c) 2016      Gaurav <g.gupta@samsung.com>
   Copyright (c) 2016      Thomas Beutlich <tc@tbeu.de>
   Copyright (c) 2016      Gustavo Grieco <gustavo.grieco@imag.fr>
   Copyright (c) 2016      Pascal Cuoq <cuoq@trust-in-soft.com>
   Copyright (c) 2016      Ed Schouten <ed@nuxi.nl>
   Copyright (c) 2017-2022 Rhodri James <rhodri@wildebeest.org.uk>
   Copyright (c) 2017      Václav Slavík <vaclav@slavik.io>
   Copyright (c) 2017      Viktor Szakats <commit@vsz.me>
   Copyright (c) 2017      Chanho Park <chanho61.park@samsung.com>
   Copyright (c) 2017      Rolf Eike Beer <eike@sf-mail.de>
   Copyright (c) 2017      Hans Wennborg <hans@chromium.org>
   Copyright (c) 2018      Anton Maklakov <antmak.pub@gmail.com>
   Copyright (c) 2018      Benjamin Peterson <benjamin@python.org>
   Copyright (c) 2018      Marco Maggi <marco.maggi-ipsu@poste.it>
   Copyright (c) 2018      Mariusz Zaborski <oshogbo@vexillium.org>
   Copyright (c) 2019      David Loffredo <loffredo@steptools.com>
   Copyright (c) 2019-2020 Ben Wagner <bungeman@chromium.org>
   Copyright (c) 2019      Vadim Zeitlin <vadim@zeitlins.org>
   Copyright (c) 2021      Donghee Na <donghee.na@python.org>
   Copyright (c) 2022      Samanta Navarro <ferivoz@riseup.net>
   Copyright (c) 2022      Jeffrey Walton <noloader@gmail.com>
   Copyright (c) 2022      Jann Horn <jannh@google.com>
   Copyright (c) 2022      Sean McBride <sean@rogue-research.com>
   Copyright (c) 2023      Owain Davies <owaind@bath.edu>
   Copyright (c) 2023-2024 Sony Corporation / Snild Dolkow <snild@sony.com>
   Copyright (c) 2024-2025 Berkay Eren Ürün <berkay.ueruen@siemens.com>
   Copyright (c) 2024      Hanno Böck <hanno@gentoo.org>
   Copyright (c) 2025-2026 Matthew Fernandez <matthew.fernandez@gmail.com>
   Copyright (c) 2025      Atrem Borovik <polzovatellllk@gmail.com>
   Copyright (c) 2025      Alfonso Gregory <gfunni234@gmail.com>
   Copyright (c) 2026      Rosen Penev <rosenp@gmail.com>
   Copyright (c) 2026      Francesco Bertolaccini
   Copyright (c) 2026      Christian Ng <christianrng@berkeley.edu>
   Copyright (c) 2026      Nick Begg <nick@stunttruck.net>
   Copyright (c) 2026      Kartik Kenchi <netliomax25@gmail.com>
   Copyright (c) 2026      Haris Hussain <hextheshadow0x@gmail.com>
   Licensed under the MIT license:

   Permission is  hereby granted,  free of charge,  to any  person obtaining
   a  copy  of  this  software   and  associated  documentation  files  (the
   "Software"),  to  deal in  the  Software  without restriction,  including
   without  limitation the  rights  to use,  copy,  modify, merge,  publish,
   distribute, sublicense, and/or sell copies of the Software, and to permit
   persons  to whom  the Software  is  furnished to  do so,  subject to  the
   following conditions:

   The above copyright  notice and this permission notice  shall be included
   in all copies or substantial portions of the Software.

   THE  SOFTWARE  IS  PROVIDED  "AS  IS",  WITHOUT  WARRANTY  OF  ANY  KIND,
   EXPRESS  OR IMPLIED,  INCLUDING  BUT  NOT LIMITED  TO  THE WARRANTIES  OF
   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
   NO EVENT SHALL THE AUTHORS OR  COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
   DAMAGES OR  OTHER LIABILITY, WHETHER  IN AN  ACTION OF CONTRACT,  TORT OR
   OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
   USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#define XML_BUILDING_EXPAT 1

#include "expat_config.h"

#if ! defined(XML_GE) || (1 - XML_GE - 1 == 2) || (XML_GE < 0) || (XML_GE > 1)
#  error XML_GE (for general entities) must be defined, non-empty, either 1 or 0 (0 to disable, 1 to enable; 1 is a common default)
#endif

#if defined(XML_DTD) && XML_GE == 0
#  error Either undefine XML_DTD or define XML_GE to 1.
#endif

#if ! defined(XML_CONTEXT_BYTES) || (1 - XML_CONTEXT_BYTES - 1 == 2)           \
    || (XML_CONTEXT_BYTES + 0 < 0)
#  error XML_CONTEXT_BYTES must be defined, non-empty and >=0 (0 to disable, >=1 to enable; 1024 is a common default)
#endif

#include <stdbool.h>
#include <stddef.h>
#include <string.h> /* memset(), memcpy() */
#include <assert.h>
#include <limits.h> /* INT_MAX, LLONG_MAX, LONG_MAX, UINT_MAX */
#include <stdio.h>  /* fprintf */
#include <stdlib.h> /* getenv */
#include <stdint.h> /* SIZE_MAX, uintptr_t */
#include <math.h>   /* isnan */
#include <errno.h>

#ifdef _WIN32
#  define getpid GetCurrentProcessId
#else
#  include <sys/time.h>  /* gettimeofday() */
#  include <sys/types.h> /* getpid() */
#  include <unistd.h>    /* getpid() */
#  include <fcntl.h>     /* O_RDONLY */
#  include <errno.h>
#endif

#ifdef _WIN32
#  include "winconfig.h"
#endif

#include "ascii.h"
#include "expat.h"
#include "siphash.h"
#include "xcsinc.c"

#if defined(HAVE_ARC4RANDOM)
#  include "random_arc4random.h"
#endif /* defined(HAVE_ARC4RANDOM) */

#if defined(HAVE_ARC4RANDOM_BUF)
#  include "random_arc4random_buf.h"
#endif // defined(HAVE_ARC4RANDOM_BUF)

#if defined(XML_DEV_URANDOM)
#  include "random_dev_urandom.h"
#endif /* defined(XML_DEV_URANDOM) */

#if defined(HAVE_GETENTROPY)
#  include "random_getentropy.h"
#endif // defined(HAVE_GETENTROPY)

#if defined(HAVE_GETRANDOM) || defined(HAVE_SYSCALL_GETRANDOM)
#  include "random_getrandom.h"
#endif /* defined(HAVE_GETRANDOM) || defined(HAVE_SYSCALL_GETRANDOM) */

#if defined(_WIN32) && ! defined(XML_POOR_ENTROPY)
#  include "random_rand_s.h"
#endif /* defined(_WIN32) && ! defined(XML_POOR_ENTROPY) */

#if ! defined(HAVE_GETRANDOM) && ! defined(HAVE_SYSCALL_GETRANDOM)             \
    && ! defined(HAVE_ARC4RANDOM_BUF) && ! defined(HAVE_ARC4RANDOM)            \
    && ! defined(HAVE_GETENTROPY) && ! defined(XML_DEV_URANDOM)                \
    && ! defined(_WIN32) && ! defined(XML_POOR_ENTROPY)
#  error You do not have support for any sources of high quality entropy \
    enabled.  For end user security, that is probably not what you want. \
    \
    Your options include: \
      * Linux >=3.17 + glibc >=2.25 (getrandom): HAVE_GETRANDOM, \
      * Linux >=3.17 + glibc (including <2.25) (syscall SYS_getrandom): HAVE_SYSCALL_GETRANDOM, \
      * BSD / macOS >=10.7 / glibc >=2.36 (arc4random_buf): HAVE_ARC4RANDOM_BUF, \
      * BSD / macOS (including <10.7) / glibc >=2.36 (arc4random): HAVE_ARC4RANDOM, \
      * BSD / macOS >=10.12 / glibc >=2.25 (getentropy): HAVE_GETENTROPY, \
      * Linux (including <3.17) / BSD / macOS (including <10.7) / Solaris >=8 (/dev/urandom): XML_DEV_URANDOM, \
      * Windows >=Vista (rand_s): _WIN32. \
    \
    If you insist on not using any of these, bypass this error by defining \
    XML_POOR_ENTROPY and be vulnerable to hash flooding; you have been warned. \
    \
    If you have reasons to patch this detection code away or need changes \
    to the build system, please open a bug.  Thank you!
#endif

#ifdef XML_UNICODE
#  define XML_ENCODE_MAX XML_UTF16_ENCODE_MAX
#  define XmlConvert XmlUtf16Convert
#  define XmlGetInternalEncoding XmlGetUtf16InternalEncoding
#  define XmlGetInternalEncodingNS XmlGetUtf16InternalEncodingNS
#  define XmlEncode XmlUtf16Encode
#  define MUST_CONVERT(enc, s) (! (enc)->isUtf16 || (((uintptr_t)(s)) & 1))
typedef unsigned short ICHAR;
#else
#  define XML_ENCODE_MAX XML_UTF8_ENCODE_MAX
#  define XmlConvert XmlUtf8Convert
#  define XmlGetInternalEncoding XmlGetUtf8InternalEncoding
#  define XmlGetInternalEncodingNS XmlGetUtf8InternalEncodingNS
#  define XmlEncode XmlUtf8Encode
#  define MUST_CONVERT(enc, s) (! (enc)->isUtf8)
typedef char ICHAR;
#endif

#ifndef XML_NS

#  define XmlInitEncodingNS XmlInitEncoding
#  define XmlInitUnknownEncodingNS XmlInitUnknownEncoding
#  undef XmlGetInternalEncodingNS
#  define XmlGetInternalEncodingNS XmlGetInternalEncoding
#  define XmlParseXmlDeclNS XmlParseXmlDecl

#endif

#ifdef XML_UNICODE

#  ifdef XML_UNICODE_WCHAR_T
#    define XML_T(x) (const wchar_t) x
#    define XML_L(x) L##x
#  else
#    define XML_T(x) (const unsigned short)x
#    define XML_L(x) x
#  endif

#else

#  define XML_T(x) x
#  define XML_L(x) x

#endif

#ifdef XML_LARGE_SIZE
#  define XML_INDEX_MAX LLONG_MAX
#else
#  define XML_INDEX_MAX LONG_MAX
#endif

/* Round up n to be a multiple of sz, where sz is a power of 2. */
#define ROUND_UP(n, sz) (((n) + ((sz) - 1)) & ~((sz) - 1))

/* Do safe (NULL-aware) pointer arithmetic */
#define EXPAT_SAFE_PTR_DIFF(p, q) (((p) && (q)) ? ((p) - (q)) : 0)

#define EXPAT_MIN(a, b) (((a) < (b)) ? (a) : (b))

#include "internal.h"
#include "xmltok.h"
#include "xmlrole.h"

typedef const XML_Char *KEY;

typedef struct {
  KEY name;
} NAMED;

typedef struct {
  NAMED **v;
  unsigned char power;
  size_t size;
  size_t used;
  XML_Parser parser;
} HASH_TABLE;

static size_t keylen(KEY s);

static void copy_salt_to_sipkey(XML_Parser parser, struct sipkey *key);

/* For probing (after a collision) we need a step size relative prime
   to the hash table size, which is a power of 2. We use double-hashing,
   since we can calculate a second hash value cheaply by taking those bits
   of the first hash value that were discarded (masked out) when the table
   index was calculated: index = hash & mask, where mask = table->size - 1.
   We limit the maximum step size to table->size / 4 (mask >> 2) and make
   it odd, since odd numbers are always relative prime to a power of 2.
*/
#define SECOND_HASH(hash, mask, power)                                         \
  ((((hash) & ~(mask)) >> ((power) - 1)) & ((mask) >> 2))
#define PROBE_STEP(hash, mask, power)                                          \
  ((unsigned char)((SECOND_HASH(hash, mask, power)) | 1))

typedef struct {
  NAMED **p;
  NAMED **end;
} HASH_TABLE_ITER;

#define INIT_TAG_BUF_SIZE 32 /* must be a multiple of sizeof(XML_Char) */
#define INIT_DATA_BUF_SIZE 1024
#define INIT_ATTS_SIZE 16
#define INIT_ATTS_VERSION 0xFFFFFFFF
#define INIT_BLOCK_SIZE 1024
#define INIT_BUFFER_SIZE 1024

#define EXPAND_SPARE 24

typedef struct binding {
  struct prefix *prefix;
  struct binding *nextTagBinding;
  struct binding *prevPrefixBinding;
  const struct attribute_id *attId;
  XML_Char *uri;
  size_t uriLen;
  size_t uriAlloc;
} BINDING;

typedef struct prefix {
  const XML_Char *name;
  BINDING *binding;
} PREFIX;

typedef struct {
  const XML_Char *str;
  const XML_Char *localPart;
  const XML_Char *prefix;
  size_t strLen;
  size_t uriLen;
  size_t prefixLen;
} TAG_NAME;

/* TAG represents an open element.
   The name of the element is stored in both the document and API
   encodings.  The memory buffer 'buf' is a separately-allocated
   memory area which stores the name.  During the XML_Parse()/
   XML_ParseBuffer() when the element is open, the memory for the 'raw'
   version of the name (in the document encoding) is shared with the
   document buffer.  If the element is open across calls to
   XML_Parse()/XML_ParseBuffer(), the buffer is re-allocated to
   contain the 'raw' name as well.

   A parser reuses these structures, maintaining a list of allocated
   TAG objects in a free list.
*/
typedef struct tag {
  struct tag *parent;  /* parent of this element */
  const char *rawName; /* tagName in the original encoding */
  int rawNameLength;
  TAG_NAME name; /* tagName in the API encoding */
  union {
    char *raw;     /* for byte-level access (rawName storage) */
    XML_Char *str; /* for character-level access (converted name) */
  } buf;           /* buffer for name components */
  char *bufEnd;    /* end of the buffer */
  BINDING *bindings;
} TAG;

typedef struct {
  const XML_Char *name;
  const XML_Char *textPtr;
  int textLen;   /* length in XML_Chars */
  int processed; /* # of processed bytes - when suspended */
  const XML_Char *systemId;
  const XML_Char *base;
  const XML_Char *publicId;
  const XML_Char *notation;
  XML_Bool open;
  XML_Bool hasMore; /* true if entity has not been completely processed */
  /* An entity can be open while being already completely processed (hasMore ==
    XML_FALSE). The reason is the delayed closing of entities until their inner
    entities are processed and closed */
  XML_Bool is_param;
  XML_Bool is_internal; /* true if declared in internal subset outside PE */
} ENTITY;

typedef struct {
  enum XML_Content_Type type;
  enum XML_Content_Quant quant;
  const XML_Char *name;
  int firstchild;
  int lastchild;
  int childcnt;
  int nextsib;
} CONTENT_SCAFFOLD;

#define INIT_SCAFFOLD_ELEMENTS 32

typedef struct block {
  struct block *next;
  int size;
  XML_Char s[];
} BLOCK;

typedef struct {
  BLOCK *blocks;
  BLOCK *freeBlocks;
  const XML_Char *end;
  XML_Char *ptr;
  XML_Char *start;
  XML_Parser parser;
} STRING_POOL;

/* The XML_Char before the name is used to determine whether
   an attribute has been specified. */
typedef struct attribute_id {
  XML_Char *name;
  PREFIX *prefix;
  XML_Bool maybeTokenized;
  XML_Bool xmlns;
} ATTRIBUTE_ID;

typedef struct {
  const ATTRIBUTE_ID *id;
  XML_Bool isCdata;
  const XML_Char *value;
} DEFAULT_ATTRIBUTE;

typedef struct {
  unsigned long version;
  unsigned long hash;
  const XML_Char *uriName;
} NS_ATT;

typedef struct {
  const XML_Char *name;
  PREFIX *prefix;
  const ATTRIBUTE_ID *idAtt;
  size_t nDefaultAtts;
  size_t allocDefaultAtts;
  DEFAULT_ATTRIBUTE *defaultAtts;
  HASH_TABLE defaultAttsNames;
} ELEMENT_TYPE;

typedef struct {
  HASH_TABLE generalEntities;
  HASH_TABLE elementTypes;
  HASH_TABLE attributeIds;
  HASH_TABLE prefixes;
  STRING_POOL pool;
  STRING_POOL entityValuePool;
  /* false once a parameter entity reference has been skipped */
  XML_Bool keepProcessing;
  /* true once an internal or external PE reference has been encountered;
     this includes the reference to an external subset */
  XML_Bool hasParamEntityRefs;
  XML_Bool standalone;
#ifdef XML_DTD
  /* indicates if external PE has been read */
  XML_Bool paramEntityRead;
  HASH_TABLE paramEntities;
#endif /* XML_DTD */
  PREFIX defaultPrefix;
  /* === scaffolding for building content model === */
  XML_Bool in_eldecl;
  CONTENT_SCAFFOLD *scaffold;
  unsigned contentStringLen;
  unsigned scaffSize;
  unsigned scaffCount;
  int scaffLevel;
  int *scaffIndex;
  size_t scaffIndexSize;
} DTD;

enum EntityType {
  ENTITY_INTERNAL,
  ENTITY_ATTRIBUTE,
  ENTITY_VALUE,
};

typedef struct open_internal_entity {
  const char *internalEventPtr;
  const char *internalEventEndPtr;
  struct open_internal_entity *next;
  ENTITY *entity;
  int startTagLevel;
  XML_Bool betweenDecl; /* WFC: PE Between Declarations */
  enum EntityType type;
} OPEN_INTERNAL_ENTITY;

enum XML_Account {
  XML_ACCOUNT_DIRECT,           /* bytes directly passed to the Expat parser */
  XML_ACCOUNT_ENTITY_EXPANSION, /* intermediate bytes produced during entity
                                   expansion */
  XML_ACCOUNT_NONE              /* i.e. do not account, was accounted already */
};

#if XML_GE == 1
typedef unsigned long long XmlBigCount;
typedef struct accounting {
  XmlBigCount countBytesDirect;
  XmlBigCount countBytesIndirect;
  unsigned long debugLevel;
  float maximumAmplificationFactor; // >=1.0
  unsigned long long activationThresholdBytes;
} ACCOUNTING;

typedef struct MALLOC_TRACKER {
  XmlBigCount bytesAllocated;
  XmlBigCount peakBytesAllocated; // updated live only for debug level >=2
  unsigned long debugLevel;
  float maximumAmplificationFactor; // >=1.0
  XmlBigCount activationThresholdBytes;
} MALLOC_TRACKER;

typedef struct entity_stats {
  unsigned int countEverOpened;
  unsigned int currentDepth;
  unsigned int maximumDepthSeen;
  unsigned long debugLevel;
} ENTITY_STATS;
#endif /* XML_GE == 1 */

typedef enum XML_Error PTRCALL Processor(XML_Parser parser, const char *start,
                                         const char *end, const char **endPtr);

static Processor prologProcessor;
static Processor prologInitProcessor;
static Processor contentProcessor;
static Processor cdataSectionProcessor;
#ifdef XML_DTD
static Processor ignoreSectionProcessor;
static Processor externalParEntProcessor;
static Processor externalParEntInitProcessor;
static Processor entityValueProcessor;
static Processor entityValueInitProcessor;
#endif /* XML_DTD */
static Processor epilogProcessor;
static Processor errorProcessor;
static Processor externalEntityInitProcessor;
static Processor externalEntityInitProcessor2;
static Processor externalEntityInitProcessor3;
static Processor externalEntityContentProcessor;
static Processor internalEntityProcessor;

static enum XML_Error handleUnknownEncoding(XML_Parser parser,
                                            const XML_Char *encodingName);
static enum XML_Error processXmlDecl(XML_Parser parser, int isGeneralTextEntity,
                                     const char *s, const char *next);
static enum XML_Error initializeEncoding(XML_Parser parser);
static enum XML_Error doProlog(XML_Parser parser, const ENCODING *enc,
                               const char *s, const char *end, int tok,
                               const char *next, const char **nextPtr,
                               XML_Bool haveMore, XML_Bool allowClosingDoctype,
                               enum XML_Account account);
static enum XML_Error processEntity(XML_Parser parser, ENTITY *entity,
                                    XML_Bool betweenDecl, enum EntityType type);
static enum XML_Error doContent(XML_Parser parser, int startTagLevel,
                                const ENCODING *enc, const char *start,
                                const char *end, const char **endPtr,
                                XML_Bool haveMore, enum XML_Account account);
static enum XML_Error doCdataSection(XML_Parser parser, const ENCODING *enc,
                                     const char **startPtr, const char *end,
                                     const char **nextPtr, XML_Bool haveMore,
                                     enum XML_Account account);
#ifdef XML_DTD
static enum XML_Error doIgnoreSection(XML_Parser parser, const ENCODING *enc,
                                      const char **startPtr, const char *end,
                                      const char **nextPtr, XML_Bool haveMore);
#endif /* XML_DTD */

static void freeBindings(XML_Parser parser, BINDING *bindings);
static enum XML_Error storeAtts(XML_Parser parser, const ENCODING *enc,
                                const char *attStr, TAG_NAME *tagNamePtr,
                                BINDING **bindingsPtr,
                                enum XML_Account account);
static enum XML_Error addBinding(XML_Parser parser, PREFIX *prefix,
                                 const ATTRIBUTE_ID *attId, const XML_Char *uri,
                                 BINDING **bindingsPtr);
static int defineAttribute(ELEMENT_TYPE *type, ATTRIBUTE_ID *attId,
                           XML_Bool isCdata, XML_Bool isId,
                           const XML_Char *value, XML_Parser parser);
static enum XML_Error storeAttributeValue(XML_Parser parser,
                                          const ENCODING *enc, XML_Bool isCdata,
                                          const char *ptr, const char *end,
                                          STRING_POOL *pool,
                                          enum XML_Account account);
static enum XML_Error
appendAttributeValue(XML_Parser parser, const ENCODING *enc, XML_Bool isCdata,
                     const char *ptr, const char *end, STRING_POOL *pool,
                     enum XML_Account account, const char **nextPtr);
static ATTRIBUTE_ID *getAttributeId(XML_Parser parser, const ENCODING *enc,
                                    const char *start, const char *end);
static int setElementTypePrefix(XML_Parser parser, ELEMENT_TYPE *elementType);
#if XML_GE == 1
static enum XML_Error storeEntityValue(XML_Parser parser, const ENCODING *enc,
                                       const char *start, const char *end,
                                       enum XML_Account account,
                                       const char **nextPtr);
static enum XML_Error callStoreEntityValue(XML_Parser parser,
                                           const ENCODING *enc,
                                           const char *start, const char *end,
                                           enum XML_Account account);
#else
static enum XML_Error storeSelfEntityValue(XML_Parser parser, ENTITY *entity);
#endif
static int reportProcessingInstruction(XML_Parser parser, const ENCODING *enc,
                                       const char *start, const char *end);
static int reportComment(XML_Parser parser, const ENCODING *enc,
                         const char *start, const char *end);
static void reportDefault(XML_Parser parser, const ENCODING *enc,
                          const char *start, const char *end);

static const XML_Char *getContext(XML_Parser parser);
static XML_Bool setContext(XML_Parser parser, const XML_Char *context);

static void FASTCALL normalizePublicId(XML_Char *s);

static DTD *dtdCreate(XML_Parser parser);
/* do not call if m_parentParser != NULL */
static void dtdReset(DTD *p, XML_Parser parser);
static void dtdDestroy(DTD *p, XML_Bool isDocEntity, XML_Parser parser);
static int dtdCopy(XML_Parser oldParser, DTD *newDtd, const DTD *oldDtd,
                   XML_Parser parser);
static int copyEntityTable(XML_Parser oldParser, HASH_TABLE *newTable,
                           STRING_POOL *newPool, const HASH_TABLE *oldTable);
static NAMED *lookup(XML_Parser parser, HASH_TABLE *table, KEY name,
                     size_t createSize);
static void FASTCALL hashTableInit(HASH_TABLE *table, XML_Parser parser);
static void FASTCALL hashTableClear(HASH_TABLE *table);
static void FASTCALL hashTableDestroy(HASH_TABLE *table);
static void FASTCALL hashTableIterInit(HASH_TABLE_ITER *iter,
                                       const HASH_TABLE *table);
static NAMED *FASTCALL hashTableIterNext(HASH_TABLE_ITER *iter);

static void FASTCALL poolInit(STRING_POOL *pool, XML_Parser parser);
static void FASTCALL poolClear(STRING_POOL *pool);
static void FASTCALL poolDestroy(STRING_POOL *pool);
static XML_Char *poolAppend(STRING_POOL *pool, const ENCODING *enc,
                            const char *ptr, const char *end);
static XML_Char *poolStoreString(STRING_POOL *pool, const ENCODING *enc,
                                 const char *ptr, const char *end);
static XML_Bool FASTCALL poolGrow(STRING_POOL *pool);
static bool FASTCALL poolGrowUntil(STRING_POOL *pool, size_t needed);
static const XML_Char *FASTCALL poolCopyString(STRING_POOL *pool,
                                               const XML_Char *s);
static const XML_Char *FASTCALL poolCopyStringNoFinish(STRING_POOL *pool,
                                                       const XML_Char *s);
static const XML_Char *poolCopyStringN(STRING_POOL *pool, const XML_Char *s,
                                       int n);
static const XML_Char *FASTCALL poolAppendString(STRING_POOL *pool,
                                                 const XML_Char *s);

static int FASTCALL nextScaffoldPart(XML_Parser parser);
static XML_Content *build_model(XML_Parser parser);
static ELEMENT_TYPE *getElementType(XML_Parser parser, const ENCODING *enc,
                                    const char *ptr, const char *end);

static XML_Char *copyString(const XML_Char *s, XML_Parser parser);

static struct sipkey generate_hash_secret_salt(void);
static XML_Bool startParsing(XML_Parser parser);

static XML_Parser parserCreate(const XML_Char *encodingName,
                               const XML_Memory_Handling_Suite *memsuite,
                               const XML_Char *nameSep, DTD *dtd,
                               XML_Parser parentParser);

static void parserInit(XML_Parser parser, const XML_Char *encodingName);

#if XML_GE == 1
static float accountingGetCurrentAmplification(XML_Parser rootParser);
static void accountingReportStats(XML_Parser originParser, const char *epilog);
static void accountingOnAbort(XML_Parser originParser);
static void accountingReportDiff(XML_Parser rootParser,
                                 unsigned int levelsAwayFromRootParser,
                                 const char *before, const char *after,
                                 ptrdiff_t bytesMore, int source_line,
                                 enum XML_Account account);
static XML_Bool accountingDiffTolerated(XML_Parser originParser, int tok,
                                        const char *before, const char *after,
                                        int source_line,
                                        enum XML_Account account);

static void entityTrackingReportStats(XML_Parser parser, ENTITY *entity,
                                      const char *action, int sourceLine);
static void entityTrackingOnOpen(XML_Parser parser, ENTITY *entity,
                                 int sourceLine);
static void entityTrackingOnClose(XML_Parser parser, ENTITY *entity,
                                  int sourceLine);
#endif /* XML_GE == 1 */

static XML_Parser getRootParserOf(XML_Parser parser,
                                  unsigned int *outLevelDiff);

static unsigned long getDebugLevel(const char *variableName,
                                   unsigned long defaultDebugLevel);

static bool poolAppendChar(STRING_POOL *pool, XML_Char c);

static bool poolAppendChars(STRING_POOL *pool, const XML_Char *s, size_t len);

#define poolStart(pool) ((pool)->start)
#define poolLength(pool) ((pool)->ptr - (pool)->start)
#define poolChop(pool) ((void)--(pool->ptr))
#define poolLastChar(pool) (((pool)->ptr)[-1])
#define poolDiscard(pool) ((pool)->ptr = (pool)->start)
#define poolFinish(pool) ((pool)->start = (pool)->ptr)

bool
poolAppendChar(STRING_POOL *pool, XML_Char c) {
  if (pool->ptr == pool->end && ! poolGrow(pool))
    return false;

  *(pool->ptr)++ = c;
  return true;
}

bool
poolAppendChars(STRING_POOL *pool, const XML_Char *s, size_t len) {
  // Detect and prevent integer overflow
  if (len > SIZE_MAX / sizeof(XML_Char))
    return false;

  if (! poolGrowUntil(pool, len))
    return false;

  memcpy(pool->ptr, s, len * sizeof(XML_Char));
  pool->ptr += len;

  return true;
}

#if ! defined(XML_TESTING)
const
#endif
    XML_Bool g_reparseDeferralEnabledDefault
    = XML_TRUE; // write ONLY in runtests.c
#if defined(XML_TESTING)
unsigned int g_bytesScanned = 0; // used for testing only
#endif

struct XML_ParserStruct {
  /* The first member must be m_userData so that the XML_GetUserData
     macro works. */
  void *m_userData;
  void *m_handlerArg;

  // How the four parse buffer pointers below relate in time and space:
  //
  //   m_buffer <= m_bufferPtr <= m_bufferEnd  <= m_bufferLim
  //   |           |              |               |
  //   <--parsed-->|              |               |
  //               <---parsing--->|               |
  //                              <--unoccupied-->|
  //   <---------total-malloced/realloced-------->|

  char *m_buffer; // malloc/realloc base pointer of parse buffer
  const XML_Memory_Handling_Suite m_mem;
  const char *m_bufferPtr; // first character to be parsed
  char *m_bufferEnd;       // past last character to be parsed
  const char *m_bufferLim; // allocated end of m_buffer

  XML_Index m_parseEndByteIndex;
  const char *m_parseEndPtr;
  size_t m_partialTokenBytesBefore; /* used in heuristic to avoid O(n^2) */
  XML_Bool m_reparseDeferralEnabled;
  int m_lastBufferRequestSize;
  XML_Char *m_dataBuf;
  XML_Char *m_dataBufEnd;
  XML_StartElementHandler m_startElementHandler;
  XML_EndElementHandler m_endElementHandler;
  XML_CharacterDataHandler m_characterDataHandler;
  XML_ProcessingInstructionHandler m_processingInstructionHandler;
  XML_CommentHandler m_commentHandler;
  XML_StartCdataSectionHandler m_startCdataSectionHandler;
  XML_EndCdataSectionHandler m_endCdataSectionHandler;
  XML_DefaultHandler m_defaultHandler;
  XML_StartDoctypeDeclHandler m_startDoctypeDeclHandler;
  XML_EndDoctypeDeclHandler m_endDoctypeDeclHandler;
  XML_UnparsedEntityDeclHandler m_unparsedEntityDeclHandler;
  XML_NotationDeclHandler m_notationDeclHandler;
  XML_StartNamespaceDeclHandler m_startNamespaceDeclHandler;
  XML_EndNamespaceDeclHandler m_endNamespaceDeclHandler;
  XML_NotStandaloneHandler m_notStandaloneHandler;
  XML_ExternalEntityRefHandler m_externalEntityRefHandler;
  XML_Parser m_externalEntityRefHandlerArg;
  XML_SkippedEntityHandler m_skippedEntityHandler;
  XML_UnknownEncodingHandler m_unknownEncodingHandler;
  XML_ElementDeclHandler m_elementDeclHandler;
  XML_AttlistDeclHandler m_attlistDeclHandler;
  XML_EntityDeclHandler m_entityDeclHandler;
  XML_XmlDeclHandler m_xmlDeclHandler;
  const ENCODING *m_encoding;
  INIT_ENCODING m_initEncoding;
  const ENCODING *m_internalEncoding;
  const XML_Char *m_protocolEncodingName;
  XML_Bool m_ns;
  XML_Bool m_ns_triplets;
  void *m_unknownEncodingMem;
  void *m_unknownEncodingData;
  void *m_unknownEncodingHandlerData;
  void(XMLCALL *m_unknownEncodingRelease)(void *);
  PROLOG_STATE m_prologState;
  Processor *m_processor;
  enum XML_Error m_errorCode;
  const char *m_eventPtr;
  const char *m_eventEndPtr;
  const char *m_positionPtr;
  OPEN_INTERNAL_ENTITY *m_openInternalEntities;
  OPEN_INTERNAL_ENTITY *m_openAttributeEntities;
  OPEN_INTERNAL_ENTITY *m_openValueEntities;
  OPEN_INTERNAL_ENTITY *m_freeEntities;
  XML_Bool m_defaultExpandInternalEntities;
  int m_tagLevel;
  ENTITY *m_declEntity;
  const XML_Char *m_doctypeName;
  const XML_Char *m_doctypeSysid;
  const XML_Char *m_doctypePubid;
  const XML_Char *m_declAttributeType;
  const XML_Char *m_declNotationName;
  const XML_Char *m_declNotationPublicId;
  ELEMENT_TYPE *m_declElementType;
  ATTRIBUTE_ID *m_declAttributeId;
  XML_Bool m_declAttributeIsCdata;
  XML_Bool m_declAttributeIsId;
  DTD *m_dtd;
  const XML_Char *m_curBase;
  TAG *m_tagStack;
  TAG *m_freeTagList;
  BINDING *m_inheritedBindings;
  BINDING *m_freeBindingList;
  size_t m_attsSize;
  int m_nSpecifiedAtts;
  int m_idAttIndex;
  ATTRIBUTE *m_atts;
  NS_ATT *m_nsAtts;
  unsigned long m_nsAttsVersion;
  unsigned char m_nsAttsPower;
#ifdef XML_ATTR_INFO
  XML_AttrInfo *m_attInfo;
#endif
  POSITION m_position;
  STRING_POOL m_tempPool;
  STRING_POOL m_temp2Pool;
  char *m_groupConnector;
  size_t m_groupSize;
  XML_Char m_namespaceSeparator;
  XML_Parser m_parentParser;
  XML_ParsingStatus m_parsingStatus;
#ifdef XML_DTD
  XML_Bool m_isParamEntity;
  XML_Bool m_useForeignDTD;
  enum XML_ParamEntityParsing m_paramEntityParsing;
#endif
  struct sipkey m_hash_secret_salt_128;
  XML_Bool m_hash_secret_salt_set;
#if XML_GE == 1
  ACCOUNTING m_accounting;
  MALLOC_TRACKER m_alloc_tracker;
  ENTITY_STATS m_entity_stats;
#endif
  XML_Bool m_reenter;
  unsigned m_handlerCallDepth;
};

#if XML_GE == 1
#  define MALLOC(parser, s) (expat_malloc((parser), (s), __LINE__))
#  define REALLOC(parser, p, s) (expat_realloc((parser), (p), (s), __LINE__))
#  define FREE(parser, p) (expat_free((parser), (p), __LINE__))
#else
#  define MALLOC(parser, s) (parser->m_mem.malloc_fcn((s)))
#  define REALLOC(parser, p, s) (parser->m_mem.realloc_fcn((p), (s)))
#  define FREE(parser, p) (parser->m_mem.free_fcn((p)))
#endif

#if XML_GE == 1
static void
expat_heap_stat(XML_Parser rootParser, char operator, XmlBigCount absDiff,
                XmlBigCount newTotal, XmlBigCount peakTotal, int sourceLine) {
  // NOTE: This can be +infinity or -nan
  const float amplification
      = (float)newTotal / (float)rootParser->m_accounting.countBytesDirect;
  fprintf(
      stderr,
      "expat: Allocations(%p): Direct " EXPAT_FMT_ULL("10") ", allocated %c" EXPAT_FMT_ULL(
          "10") " to " EXPAT_FMT_ULL("10") " (" EXPAT_FMT_ULL("10") " peak), amplification %8.2f (xmlparse.c:%d)\n",
      (void *)rootParser, rootParser->m_accounting.countBytesDirect, operator,
      absDiff, newTotal, peakTotal, (double)amplification, sourceLine);
}

static bool
expat_heap_increase_tolerable(XML_Parser rootParser, XmlBigCount increase,
                              int sourceLine) {
  assert(rootParser != NULL);
  assert(increase > 0);

  XmlBigCount newTotal = 0;
  bool tolerable = true;

  // Detect integer overflow
  if ((XmlBigCount)-1 - rootParser->m_alloc_tracker.bytesAllocated < increase) {
    tolerable = false;
  } else {
    newTotal = rootParser->m_alloc_tracker.bytesAllocated + increase;

    if (newTotal >= rootParser->m_alloc_tracker.activationThresholdBytes) {
      assert(newTotal > 0);
      // NOTE: This can be +infinity when dividing by zero but not -nan
      const float amplification
          = (float)newTotal / (float)rootParser->m_accounting.countBytesDirect;
      if (amplification
          > rootParser->m_alloc_tracker.maximumAmplificationFactor) {
        tolerable = false;
      }
    }
  }

  if (! tolerable && (rootParser->m_alloc_tracker.debugLevel >= 1)) {
    expat_heap_stat(rootParser, '+', increase, newTotal, newTotal, sourceLine);
  }

  return tolerable;
}

#  if defined(XML_TESTING)
void *
#  else
static void *
#  endif
expat_malloc(XML_Parser parser, size_t size, int sourceLine) {
  // Detect integer overflow
  if (SIZE_MAX - size < sizeof(size_t) + EXPAT_MALLOC_PADDING) {
    return NULL;
  }

  const XML_Parser rootParser = getRootParserOf(parser, NULL);
  assert(rootParser->m_parentParser == NULL);

  const size_t bytesToAllocate = sizeof(size_t) + EXPAT_MALLOC_PADDING + size;

  if ((XmlBigCount)-1 - rootParser->m_alloc_tracker.bytesAllocated
      < bytesToAllocate) {
    return NULL; // i.e. signal integer overflow as out-of-memory
  }

  if (! expat_heap_increase_tolerable(rootParser, bytesToAllocate,
                                      sourceLine)) {
    return NULL; // i.e. signal violation as out-of-memory
  }

  // Actually allocate
  void *const mallocedPtr = parser->m_mem.malloc_fcn(bytesToAllocate);

  if (mallocedPtr == NULL) {
    return NULL;
  }

  // Update in-block recorded size
  *(size_t *)mallocedPtr = size;

  // Update accounting
  rootParser->m_alloc_tracker.bytesAllocated += bytesToAllocate;

  // Report as needed
  if (rootParser->m_alloc_tracker.debugLevel >= 2) {
    if (rootParser->m_alloc_tracker.bytesAllocated
        > rootParser->m_alloc_tracker.peakBytesAllocated) {
      rootParser->m_alloc_tracker.peakBytesAllocated
          = rootParser->m_alloc_tracker.bytesAllocated;
    }
    expat_heap_stat(rootParser, '+', bytesToAllocate,
                    rootParser->m_alloc_tracker.bytesAllocated,
                    rootParser->m_alloc_tracker.peakBytesAllocated, sourceLine);
  }

  return (char *)mallocedPtr + sizeof(size_t) + EXPAT_MALLOC_PADDING;
}

#  if defined(XML_TESTING)
void
#  else
static void
#  endif
expat_free(XML_Parser parser, void *ptr, int sourceLine) {
  assert(parser != NULL);

  if (ptr == NULL) {
    return;
  }

  const XML_Parser rootParser = getRootParserOf(parser, NULL);
  assert(rootParser->m_parentParser == NULL);

  // Extract size (to the eyes of malloc_fcn/realloc_fcn) and
  // the original pointer returned by malloc/realloc
  void *const mallocedPtr = (char *)ptr - EXPAT_MALLOC_PADDING - sizeof(size_t);
  const size_t bytesAllocated
      = sizeof(size_t) + EXPAT_MALLOC_PADDING + *(size_t *)mallocedPtr;

  // Update accounting
  assert(rootParser->m_alloc_tracker.bytesAllocated >= bytesAllocated);
  rootParser->m_alloc_tracker.bytesAllocated -= bytesAllocated;

  // Report as needed
  if (rootParser->m_alloc_tracker.debugLevel >= 2) {
    expat_heap_stat(rootParser, '-', bytesAllocated,
                    rootParser->m_alloc_tracker.bytesAllocated,
                    rootParser->m_alloc_tracker.peakBytesAllocated, sourceLine);
  }

  // NOTE: This may be freeing rootParser, so freeing has to come last
  parser->m_mem.free_fcn(mallocedPtr);
}

#  if defined(XML_TESTING)
void *
#  else
static void *
#  endif
expat_realloc(XML_Parser parser, void *ptr, size_t size, int sourceLine) {
  assert(parser != NULL);

  if (ptr == NULL) {
    return expat_malloc(parser, size, sourceLine);
  }

  if (size == 0) {
    expat_free(parser, ptr, sourceLine);
    return NULL;
  }

  const XML_Parser rootParser = getRootParserOf(parser, NULL);
  assert(rootParser->m_parentParser == NULL);

  // Extract original size (to the eyes of the caller) and the original
  // pointer returned by malloc/realloc
  void *mallocedPtr = (char *)ptr - EXPAT_MALLOC_PADDING - sizeof(size_t);
  const size_t prevSize = *(size_t *)mallocedPtr;

  // Classify upcoming change
  const bool isIncrease = (size > prevSize);