libxml2/valid.c

   1 /*
   2  * valid.c : part of the code use to do the DTD handling and the validity
   3  *           checking
   4  *
   5  * See Copyright for the status of this software.
   6  *
   7  * daniel@veillard.com
   8  */
   9
  10 #define IN_LIBXML
  11 #include "libxml.h"
  12
  13 #include <string.h>
  14
  15 #ifdef HAVE_STDLIB_H
  16 #include <stdlib.h>
  17 #endif
  18
  19 #include <libxml/xmlmemory.h>
  20 #include <libxml/hash.h>
  21 #include <libxml/valid.h>
  22 #include <libxml/parser.h>
  23 #include <libxml/parserInternals.h>
  24 #include <libxml/xmlerror.h>
  25 #include <libxml/list.h>
  26 #include <libxml/globals.h>
  27
  28 /* #define DEBUG_VALID_ALGO */
  29 /* #define DEBUG_REGEXP_ALGO */
  30
  31 #define TODO                                                            \
  32     xmlGenericError(xmlGenericErrorContext,                             \
  33             "Unimplemented block at %s:%d\n",                           \
  34             __FILE__, __LINE__);
  35
  36 #define VERROR                                                  \
  37    if ((ctxt != NULL) && (ctxt->error != NULL)) ctxt->error
  38
  39 #define VWARNING                                                \
  40    if ((ctxt != NULL) && (ctxt->warning != NULL)) ctxt->warning
  41
  42
  43 #ifdef LIBXML_REGEXP_ENABLED
  44 /*
  45  * If regexp are enabled we can do continuous validation without the
  46  * need of a tree to validate the content model. this is done in each
  47  * callbacks.
  48  * Each xmlValidState represent the validation state associated to the
  49  * set of nodes currently open from the document root to the current element.
  50  */
  51
  52
  53 typedef struct _xmlValidState {
  54     xmlElementPtr        elemDecl;      /* pointer to the content model */
  55     xmlNodePtr           node;          /* pointer to the current node */
  56     xmlRegExecCtxtPtr    exec;          /* regexp runtime */
  57 } _xmlValidState;
  58
  59
  60 static int
  61 vstateVPush(xmlValidCtxtPtr ctxt, xmlElementPtr elemDecl, xmlNodePtr node) {
  62     if ((ctxt->vstateMax == 0) || (ctxt->vstateTab == NULL)) {
  63         ctxt->vstateMax = 10;
  64         ctxt->vstateTab = (xmlValidState *) xmlMalloc(ctxt->vstateMax *
  65                               sizeof(ctxt->vstateTab[0]));
  66         if (ctxt->vstateTab == NULL) {
  67             VERROR(ctxt->userData, "malloc failed !n");
  68             return(-1);
  69         }
  70     }
  71
  72     if (ctxt->vstateNr >= ctxt->vstateMax) {
  73         xmlValidState *tmp;
  74
  75         tmp = (xmlValidState *) xmlRealloc(ctxt->vstateTab,
  76                      2 * ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
  77         if (tmp == NULL) {
  78             VERROR(ctxt->userData, "realloc failed !n");
  79             return(-1);
  80         }
  81         ctxt->vstateMax *= 2;
  82         ctxt->vstateTab = tmp;
  83     }
  84     ctxt->vstate = &ctxt->vstateTab[ctxt->vstateNr];
  85     ctxt->vstateTab[ctxt->vstateNr].elemDecl = elemDecl;
  86     ctxt->vstateTab[ctxt->vstateNr].node = node;
  87     if ((elemDecl != NULL) && (elemDecl->etype == XML_ELEMENT_TYPE_ELEMENT)) {
  88         if (elemDecl->contModel == NULL)
  89             xmlValidBuildContentModel(ctxt, elemDecl);
  90         if (elemDecl->contModel != NULL) {
  91             ctxt->vstateTab[ctxt->vstateNr].exec =
  92                 xmlRegNewExecCtxt(elemDecl->contModel, NULL, NULL);
  93         } else {
  94             ctxt->vstateTab[ctxt->vstateNr].exec = NULL;
  95             VERROR(ctxt->userData,
  96                    "Failed to build content model regexp for %s", node->name);
  97         }
  98     }
  99     return(ctxt->vstateNr++);
 100 }
 101
 102 static int
 103 vstateVPop(xmlValidCtxtPtr ctxt) {
 104     xmlElementPtr elemDecl;
 105
 106     if (ctxt->vstateNr < 1) return(-1);
 107     ctxt->vstateNr--;
 108     elemDecl = ctxt->vstateTab[ctxt->vstateNr].elemDecl;
 109     ctxt->vstateTab[ctxt->vstateNr].elemDecl = NULL;
 110     ctxt->vstateTab[ctxt->vstateNr].node = NULL;
 111     if ((elemDecl != NULL) && (elemDecl->etype == XML_ELEMENT_TYPE_ELEMENT)) {
 112         xmlRegFreeExecCtxt(ctxt->vstateTab[ctxt->vstateNr].exec);
 113     }
 114     ctxt->vstateTab[ctxt->vstateNr].exec = NULL;
 115     if (ctxt->vstateNr >= 1)
 116         ctxt->vstate = &ctxt->vstateTab[ctxt->vstateNr - 1];
 117     else
 118         ctxt->vstate = NULL;
 119     return(ctxt->vstateNr);
 120 }
 121
 122 #else /* not LIBXML_REGEXP_ENABLED */
 123 /*
 124  * If regexp are not enabled, it uses a home made algorithm less
 125  * complex and easier to
 126  * debug/maintain than a generic NFA -> DFA state based algo. The
 127  * only restriction is on the deepness of the tree limited by the
 128  * size of the occurs bitfield
 129  *
 130  * this is the content of a saved state for rollbacks
 131  */
 132
 133 #define ROLLBACK_OR     0
 134 #define ROLLBACK_PARENT 1
 135
 136 typedef struct _xmlValidState {
 137     xmlElementContentPtr cont;  /* pointer to the content model subtree */
 138     xmlNodePtr           node;  /* pointer to the current node in the list */
 139     long                 occurs;/* bitfield for multiple occurrences */
 140     unsigned char        depth; /* current depth in the overall tree */
 141     unsigned char        state; /* ROLLBACK_XXX */
 142 } _xmlValidState;
 143
 144 #define MAX_RECURSE 25000
 145 #define MAX_DEPTH ((sizeof(_xmlValidState.occurs)) * 8)
 146 #define CONT ctxt->vstate->cont
 147 #define NODE ctxt->vstate->node
 148 #define DEPTH ctxt->vstate->depth
 149 #define OCCURS ctxt->vstate->occurs
 150 #define STATE ctxt->vstate->state
 151
 152 #define OCCURRENCE (ctxt->vstate->occurs & (1 << DEPTH))
 153 #define PARENT_OCCURRENCE (ctxt->vstate->occurs & ((1 << DEPTH) - 1))
 154
 155 #define SET_OCCURRENCE ctxt->vstate->occurs |= (1 << DEPTH)
 156 #define RESET_OCCURRENCE ctxt->vstate->occurs &= ((1 << DEPTH) - 1)
 157
 158 static int
 159 vstateVPush(xmlValidCtxtPtr ctxt, xmlElementContentPtr cont,
 160             xmlNodePtr node, unsigned char depth, long occurs,
 161             unsigned char state) {
 162     int i = ctxt->vstateNr - 1;
 163
 164     if (ctxt->vstateNr > MAX_RECURSE) {
 165         return(-1);
 166     }
 167     if (ctxt->vstateTab == NULL) {
 168         ctxt->vstateMax = 8;
 169         ctxt->vstateTab = (xmlValidState *) xmlMalloc(
 170                      ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
 171         if (ctxt->vstateTab == NULL) {
 172             xmlGenericError(xmlGenericErrorContext,
 173                     "malloc failed !n");
 174             return(-1);
 175         }
 176     }
 177     if (ctxt->vstateNr >= ctxt->vstateMax) {
 178         xmlValidState *tmp;
 179
 180         tmp = (xmlValidState *) xmlRealloc(ctxt->vstateTab,
 181                      2 * ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
 182         if (tmp == NULL) {
 183             xmlGenericError(xmlGenericErrorContext,
 184                     "realloc failed !n");
 185             return(-1);
 186         }
 187         ctxt->vstateMax *= 2;
 188         ctxt->vstateTab = tmp;
 189         ctxt->vstate = &ctxt->vstateTab[0];
 190     }
 191     /*
 192      * Don't push on the stack a state already here
 193      */
 194     if ((i >= 0) && (ctxt->vstateTab[i].cont == cont) &&
 195         (ctxt->vstateTab[i].node == node) &&
 196         (ctxt->vstateTab[i].depth == depth) &&
 197         (ctxt->vstateTab[i].occurs == occurs) &&
 198         (ctxt->vstateTab[i].state == state))
 199         return(ctxt->vstateNr);
 200     ctxt->vstateTab[ctxt->vstateNr].cont = cont;
 201     ctxt->vstateTab[ctxt->vstateNr].node = node;
 202     ctxt->vstateTab[ctxt->vstateNr].depth = depth;
 203     ctxt->vstateTab[ctxt->vstateNr].occurs = occurs;
 204     ctxt->vstateTab[ctxt->vstateNr].state = state;
 205     return(ctxt->vstateNr++);
 206 }
 207
 208 static int
 209 vstateVPop(xmlValidCtxtPtr ctxt) {
 210     if (ctxt->vstateNr <= 1) return(-1);
 211     ctxt->vstateNr--;
 212     ctxt->vstate = &ctxt->vstateTab[0];
 213     ctxt->vstate->cont =  ctxt->vstateTab[ctxt->vstateNr].cont;
 214     ctxt->vstate->node = ctxt->vstateTab[ctxt->vstateNr].node;
 215     ctxt->vstate->depth = ctxt->vstateTab[ctxt->vstateNr].depth;
 216     ctxt->vstate->occurs = ctxt->vstateTab[ctxt->vstateNr].occurs;
 217     ctxt->vstate->state = ctxt->vstateTab[ctxt->vstateNr].state;
 218     return(ctxt->vstateNr);
 219 }
 220
 221 #endif /* LIBXML_REGEXP_ENABLED */
 222
 223 static int
 224 nodeVPush(xmlValidCtxtPtr ctxt, xmlNodePtr value)
 225 {
 226     if (ctxt->nodeMax <= 0) {
 227         ctxt->nodeMax = 4;
 228         ctxt->nodeTab =
 229             (xmlNodePtr *) xmlMalloc(ctxt->nodeMax *
 230                                      sizeof(ctxt->nodeTab[0]));
 231         if (ctxt->nodeTab == NULL) {
 232             xmlGenericError(xmlGenericErrorContext, "malloc failed !\n");
 233             ctxt->nodeMax = 0;
 234             return (0);
 235         }
 236     }
 237     if (ctxt->nodeNr >= ctxt->nodeMax) {
 238         xmlNodePtr *tmp;
 239         tmp = (xmlNodePtr *) xmlRealloc(ctxt->nodeTab,
 240                               ctxt->nodeMax * 2 * sizeof(ctxt->nodeTab[0]));
 241         if (tmp == NULL) {
 242             xmlGenericError(xmlGenericErrorContext, "realloc failed !\n");
 243             return (0);
 244         }
 245         ctxt->nodeMax *= 2;
 246         ctxt->nodeTab = tmp;
 247     }
 248     ctxt->nodeTab[ctxt->nodeNr] = value;
 249     ctxt->node = value;
 250     return (ctxt->nodeNr++);
 251 }
 252 static xmlNodePtr
 253 nodeVPop(xmlValidCtxtPtr ctxt)
 254 {
 255     xmlNodePtr ret;
 256
 257     if (ctxt->nodeNr <= 0)
 258         return (0);
 259     ctxt->nodeNr--;
 260     if (ctxt->nodeNr > 0)
 261         ctxt->node = ctxt->nodeTab[ctxt->nodeNr - 1];
 262     else
 263         ctxt->node = NULL;
 264     ret = ctxt->nodeTab[ctxt->nodeNr];
 265     ctxt->nodeTab[ctxt->nodeNr] = 0;
 266     return (ret);
 267 }
 268
 269 #ifdef DEBUG_VALID_ALGO
 270 static void
 271 xmlValidPrintNode(xmlNodePtr cur) {
 272     if (cur == NULL) {
 273         xmlGenericError(xmlGenericErrorContext, "null");
 274         return;
 275     }
 276     switch (cur->type) {
 277         case XML_ELEMENT_NODE:
 278             xmlGenericError(xmlGenericErrorContext, "%s ", cur->name);
 279             break;
 280         case XML_TEXT_NODE:
 281             xmlGenericError(xmlGenericErrorContext, "text ");
 282             break;
 283         case XML_CDATA_SECTION_NODE:
 284             xmlGenericError(xmlGenericErrorContext, "cdata ");
 285             break;
 286         case XML_ENTITY_REF_NODE:
 287             xmlGenericError(xmlGenericErrorContext, "&%s; ", cur->name);
 288             break;
 289         case XML_PI_NODE:
 290             xmlGenericError(xmlGenericErrorContext, "pi(%s) ", cur->name);
 291             break;
 292         case XML_COMMENT_NODE:
 293             xmlGenericError(xmlGenericErrorContext, "comment ");
 294             break;
 295         case XML_ATTRIBUTE_NODE:
 296             xmlGenericError(xmlGenericErrorContext, "?attr? ");
 297             break;
 298         case XML_ENTITY_NODE:
 299             xmlGenericError(xmlGenericErrorContext, "?ent? ");
 300             break;
 301         case XML_DOCUMENT_NODE:
 302             xmlGenericError(xmlGenericErrorContext, "?doc? ");
 303             break;
 304         case XML_DOCUMENT_TYPE_NODE:
 305             xmlGenericError(xmlGenericErrorContext, "?doctype? ");
 306             break;
 307         case XML_DOCUMENT_FRAG_NODE:
 308             xmlGenericError(xmlGenericErrorContext, "?frag? ");
 309             break;
 310         case XML_NOTATION_NODE:
 311             xmlGenericError(xmlGenericErrorContext, "?nota? ");
 312             break;
 313         case XML_HTML_DOCUMENT_NODE:
 314             xmlGenericError(xmlGenericErrorContext, "?html? ");
 315             break;
 316 #ifdef LIBXML_DOCB_ENABLED
 317         case XML_DOCB_DOCUMENT_NODE:
 318             xmlGenericError(xmlGenericErrorContext, "?docb? ");
 319             break;
 320 #endif
 321         case XML_DTD_NODE:
 322             xmlGenericError(xmlGenericErrorContext, "?dtd? ");
 323             break;
 324         case XML_ELEMENT_DECL:
 325             xmlGenericError(xmlGenericErrorContext, "?edecl? ");
 326             break;
 327         case XML_ATTRIBUTE_DECL:
 328             xmlGenericError(xmlGenericErrorContext, "?adecl? ");
 329             break;
 330         case XML_ENTITY_DECL:
 331             xmlGenericError(xmlGenericErrorContext, "?entdecl? ");
 332             break;
 333         case XML_NAMESPACE_DECL:
 334             xmlGenericError(xmlGenericErrorContext, "?nsdecl? ");
 335             break;
 336         case XML_XINCLUDE_START:
 337             xmlGenericError(xmlGenericErrorContext, "incstart ");
 338             break;
 339         case XML_XINCLUDE_END:
 340             xmlGenericError(xmlGenericErrorContext, "incend ");
 341             break;
 342     }
 343 }
 344
 345 static void
 346 xmlValidPrintNodeList(xmlNodePtr cur) {
 347     if (cur == NULL)
 348         xmlGenericError(xmlGenericErrorContext, "null ");
 349     while (cur != NULL) {
 350         xmlValidPrintNode(cur);
 351         cur = cur->next;
 352     }
 353 }
 354
 355 static void
 356 xmlValidDebug(xmlNodePtr cur, xmlElementContentPtr cont) {
 357     char expr[5000];
 358
 359     expr[0] = 0;
 360     xmlGenericError(xmlGenericErrorContext, "valid: ");
 361     xmlValidPrintNodeList(cur);
 362     xmlGenericError(xmlGenericErrorContext, "against ");
 363     xmlSnprintfElementContent(expr, 5000, cont, 1);
 364     xmlGenericError(xmlGenericErrorContext, "%s\n", expr);
 365 }
 366
 367 static void
 368 xmlValidDebugState(xmlValidStatePtr state) {
 369     xmlGenericError(xmlGenericErrorContext, "(");
 370     if (state->cont == NULL)
 371         xmlGenericError(xmlGenericErrorContext, "null,");
 372     else
 373         switch (state->cont->type) {
 374             case XML_ELEMENT_CONTENT_PCDATA:
 375                 xmlGenericError(xmlGenericErrorContext, "pcdata,");
 376                 break;
 377             case XML_ELEMENT_CONTENT_ELEMENT:
 378                 xmlGenericError(xmlGenericErrorContext, "%s,",
 379                                 state->cont->name);
 380                 break;
 381             case XML_ELEMENT_CONTENT_SEQ:
 382                 xmlGenericError(xmlGenericErrorContext, "seq,");
 383                 break;
 384             case XML_ELEMENT_CONTENT_OR:
 385                 xmlGenericError(xmlGenericErrorContext, "or,");
 386                 break;
 387         }
 388     xmlValidPrintNode(state->node);
 389     xmlGenericError(xmlGenericErrorContext, ",%d,%X,%d)",
 390             state->depth, state->occurs, state->state);
 391 }
 392
 393 static void
 394 xmlValidStateDebug(xmlValidCtxtPtr ctxt) {
 395     int i, j;
 396
 397     xmlGenericError(xmlGenericErrorContext, "state: ");
 398     xmlValidDebugState(ctxt->vstate);
 399     xmlGenericError(xmlGenericErrorContext, " stack: %d ",
 400             ctxt->vstateNr - 1);
 401     for (i = 0, j = ctxt->vstateNr - 1;(i < 3) && (j > 0);i++,j--)
 402         xmlValidDebugState(&ctxt->vstateTab[j]);
 403     xmlGenericError(xmlGenericErrorContext, "\n");
 404 }
 405
 406 /*****
 407 #define DEBUG_VALID_STATE(n,c) xmlValidDebug(n,c);
 408  *****/
 409
 410 #define DEBUG_VALID_STATE(n,c) xmlValidStateDebug(ctxt);
 411 #define DEBUG_VALID_MSG(m)                                      \
 412     xmlGenericError(xmlGenericErrorContext, "%s\n", m);
 413
 414 #else
 415 #define DEBUG_VALID_STATE(n,c)
 416 #define DEBUG_VALID_MSG(m)
 417 #endif
 418
 419 /* TODO: use hash table for accesses to elem and attribute definitions */
 420
 421 #define VECTXT(ctxt, node)                                      \
 422    if ((ctxt != NULL) && (ctxt->error != NULL) &&               \
 423        (node != NULL)) {                                        \
 424        xmlChar *base = xmlNodeGetBase(NULL,node);               \
 425        if (base != NULL) {                                      \
 426            ctxt->error(ctxt->userData, "%s:%d: ", base,         \
 427                        (int) (long) node->content);             \
 428            xmlFree(base);                                       \
 429        } else                                                   \
 430            ctxt->error(ctxt->userData, ":%d: ",                 \
 431                        (int) (long) node->content);             \
 432    }
 433
 434 #define VWCTXT(ctxt, node)                                      \
 435    if ((ctxt != NULL) && (ctxt->warning != NULL) &&             \
 436        (node != NULL)) {                                        \
 437        xmlChar *base = xmlNodeGetBase(NULL,node);               \
 438        if (base != NULL) {                                      \
 439            ctxt->warning(ctxt->userData, "%s:%d: ", base,       \
 440                        (int) (long) node->content);             \
 441            xmlFree(base);                                       \
 442        } else                                                   \
 443            ctxt->warning(ctxt->userData, ":%d: ",               \
 444                        (int) (long) node->content);             \
 445    }
 446
 447 #define CHECK_DTD                                               \
 448    if (doc == NULL) return(0);                                  \
 449    else if ((doc->intSubset == NULL) &&                         \
 450             (doc->extSubset == NULL)) return(0)
 451
 452 static xmlElementPtr xmlGetDtdElementDesc2(xmlDtdPtr dtd, const xmlChar *name,
 453                                    int create);
 454 xmlAttributePtr xmlScanAttributeDecl(xmlDtdPtr dtd, const xmlChar *elem);
 455
 456 #ifdef LIBXML_REGEXP_ENABLED
 457
 458 /************************************************************************
 459  *                                                                      *
 460  *              Content model validation based on the regexps           *
 461  *                                                                      *
 462  ************************************************************************/
 463
 464 /**
 465  * xmlValidBuildAContentModel:
 466  * @content:  the content model
 467  * @ctxt:  the schema parser context
 468  * @name:  the element name whose content is being built
 469  *
 470  * Generate the automata sequence needed for that type
 471  *
 472  * Returns 1 if successful or 0 in case of error.
 473  */
 474 static int
 475 xmlValidBuildAContentModel(xmlElementContentPtr content,
 476                            xmlValidCtxtPtr ctxt,
 477                            const xmlChar *name) {
 478     if (content == NULL) {
 479         VERROR(ctxt->userData,
 480                "Found unexpected type = NULL in %s content model\n", name);
 481         return(0);
 482     }
 483     switch (content->type) {
 484         case XML_ELEMENT_CONTENT_PCDATA:
 485             VERROR(ctxt->userData, "ContentModel found PCDATA for element %s\n",
 486                    name);
 487             return(0);
 488             break;
 489         case XML_ELEMENT_CONTENT_ELEMENT: {
 490             xmlAutomataStatePtr oldstate = ctxt->state;
 491             xmlChar fn[50];
 492             xmlChar *fullname;
 493
 494             fullname = xmlBuildQName(content->name, content->prefix, fn, 50);
 495             if (fullname == NULL) {
 496                 VERROR(ctxt->userData, "Out of memory\n");
 497                 return(0);
 498             }
 499
 500             switch (content->ocur) {
 501                 case XML_ELEMENT_CONTENT_ONCE:
 502                     ctxt->state = xmlAutomataNewTransition(ctxt->am,
 503                             ctxt->state, NULL, fullname, NULL);
 504                     break;
 505                 case XML_ELEMENT_CONTENT_OPT:
 506                     ctxt->state = xmlAutomataNewTransition(ctxt->am,
 507                             ctxt->state, NULL, fullname, NULL);
 508                     xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
 509                     break;
 510                 case XML_ELEMENT_CONTENT_PLUS:
 511                     ctxt->state = xmlAutomataNewTransition(ctxt->am,
 512                             ctxt->state, NULL, fullname, NULL);
 513                     xmlAutomataNewTransition(ctxt->am, ctxt->state,
 514                                              ctxt->state, fullname, NULL);
 515                     break;
 516                 case XML_ELEMENT_CONTENT_MULT:
 517                     xmlAutomataNewTransition(ctxt->am, ctxt->state,
 518                                              ctxt->state, fullname, NULL);
 519                     ctxt->state = xmlAutomataNewEpsilon(ctxt->am, ctxt->state,
 520                                              NULL);
 521                     break;
 522             }
 523             if ((fullname != fn) && (fullname != content->name))
 524                 xmlFree(fullname);
 525             break;
 526         }
 527         case XML_ELEMENT_CONTENT_SEQ: {
 528             xmlAutomataStatePtr oldstate, oldend;
 529             xmlElementContentOccur ocur;
 530
 531             /*
 532              * Simply iterate over the content
 533              */
 534             oldstate = ctxt->state;
 535             ocur = content->ocur;
 536             if (ocur != XML_ELEMENT_CONTENT_ONCE) {
 537                 ctxt->state = xmlAutomataNewEpsilon(ctxt->am, oldstate, NULL);
 538                 oldstate = ctxt->state;
 539             }
 540             do {
 541                 xmlValidBuildAContentModel(content->c1, ctxt, name);
 542                 content = content->c2;
 543             } while ((content->type == XML_ELEMENT_CONTENT_SEQ) &&
 544                      (content->ocur == XML_ELEMENT_CONTENT_ONCE));
 545             xmlValidBuildAContentModel(content, ctxt, name);
 546             oldend = ctxt->state;
 547             ctxt->state = xmlAutomataNewEpsilon(ctxt->am, oldend, NULL);
 548             switch (ocur) {
 549                 case XML_ELEMENT_CONTENT_ONCE:
 550                     break;
 551                 case XML_ELEMENT_CONTENT_OPT:
 552                     xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
 553                     break;
 554                 case XML_ELEMENT_CONTENT_MULT:
 555                     xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
 556                     xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
 557                     break;
 558                 case XML_ELEMENT_CONTENT_PLUS:
 559                     xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
 560                     break;
 561             }
 562             break;
 563         }
 564         case XML_ELEMENT_CONTENT_OR: {
 565             xmlAutomataStatePtr oldstate, oldend;
 566             xmlElementContentOccur ocur;
 567
 568             ocur = content->ocur;
 569             if ((ocur == XML_ELEMENT_CONTENT_PLUS) ||
 570                 (ocur == XML_ELEMENT_CONTENT_MULT)) {
 571                 ctxt->state = xmlAutomataNewEpsilon(ctxt->am,
 572                         ctxt->state, NULL);
 573             }
 574             oldstate = ctxt->state;
 575             oldend = xmlAutomataNewState(ctxt->am);
 576
 577             /*
 578              * iterate over the subtypes and remerge the end with an
 579              * epsilon transition
 580              */
 581             do {
 582                 ctxt->state = oldstate;
 583                 xmlValidBuildAContentModel(content->c1, ctxt, name);
 584                 xmlAutomataNewEpsilon(ctxt->am, ctxt->state, oldend);
 585                 content = content->c2;
 586             } while ((content->type == XML_ELEMENT_CONTENT_OR) &&
 587                      (content->ocur == XML_ELEMENT_CONTENT_ONCE));
 588             ctxt->state = oldstate;
 589             xmlValidBuildAContentModel(content, ctxt, name);
 590             xmlAutomataNewEpsilon(ctxt->am, ctxt->state, oldend);
 591             ctxt->state = xmlAutomataNewEpsilon(ctxt->am, oldend, NULL);
 592             switch (ocur) {
 593                 case XML_ELEMENT_CONTENT_ONCE:
 594                     break;
 595                 case XML_ELEMENT_CONTENT_OPT:
 596                     xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
 597                     break;
 598                 case XML_ELEMENT_CONTENT_MULT:
 599                     xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
 600                     xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
 601                     break;
 602                 case XML_ELEMENT_CONTENT_PLUS:
 603                     xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
 604                     break;
 605             }
 606             break;
 607         }
 608         default:
 609             VERROR(ctxt->userData, "ContentModel broken for element %s\n",
 610                    name);
 611             return(0);
 612     }
 613     return(1);
 614 }
 615 /**
 616  * xmlValidBuildContentModel:
 617  * @ctxt:  a validation context
 618  * @elem:  an element declaration node
 619  *
 620  * (Re)Build the automata associated to the content model of this
 621  * element
 622  *
 623  * Returns 1 in case of success, 0 in case of error
 624  */
 625 int
 626 xmlValidBuildContentModel(xmlValidCtxtPtr ctxt, xmlElementPtr elem) {
 627
 628     if ((ctxt == NULL) || (elem == NULL))
 629         return(0);
 630     if (elem->type != XML_ELEMENT_DECL)
 631         return(0);
 632     if (elem->etype != XML_ELEMENT_TYPE_ELEMENT)
 633         return(1);
 634     /* TODO: should we rebuild in this case ? */
 635     if (elem->contModel != NULL) {
 636         if (!xmlRegexpIsDeterminist(elem->contModel)) {
 637             ctxt->valid = 0;
 638             return(0);
 639         }
 640         return(1);
 641     }
 642
 643     ctxt->am = xmlNewAutomata();
 644     if (ctxt->am == NULL) {
 645         VERROR(ctxt->userData, "Cannot create automata for element %s\n",
 646                elem->name);
 647         return(0);
 648     }
 649     ctxt->state = xmlAutomataGetInitState(ctxt->am);
 650     xmlValidBuildAContentModel(elem->content, ctxt, elem->name);
 651     xmlAutomataSetFinalState(ctxt->am, ctxt->state);
 652     elem->contModel = xmlAutomataCompile(ctxt->am);
 653     if (xmlRegexpIsDeterminist(elem->contModel) != 1) {
 654         char expr[5000];
 655         expr[0] = 0;
 656         xmlSnprintfElementContent(expr, 5000, elem->content, 1);
 657         VERROR(ctxt->userData, "Content model of %s is not determinist: %s\n",
 658                elem->name, expr);
 659 #ifdef DEBUG_REGEXP_ALGO
 660         xmlRegexpPrint(stderr, elem->contModel);
 661 #endif
 662         ctxt->valid = 0;
 663         ctxt->state = NULL;
 664         xmlFreeAutomata(ctxt->am);
 665         ctxt->am = NULL;
 666         return(0);
 667     }
 668     ctxt->state = NULL;
 669     xmlFreeAutomata(ctxt->am);
 670     ctxt->am = NULL;
 671     return(1);
 672 }
 673
 674 #endif /* LIBXML_REGEXP_ENABLED */
 675
 676 /****************************************************************
 677  *                                                              *
 678  *      Util functions for data allocation/deallocation         *
 679  *                                                              *
 680  ****************************************************************/
 681
 682 /**
 683  * xmlNewValidCtxt:
 684  *
 685  * Allocate a validation context structure.
 686  *
 687  * Returns NULL if not, otherwise the new validation context structure
 688  */
 689 xmlValidCtxtPtr
 690 xmlNewValidCtxt(void) {
 691     xmlValidCtxtPtr ret;
 692
 693     if ((ret = xmlMalloc(sizeof (xmlValidCtxt))) == NULL)
 694         return (NULL);
 695
 696     (void) memset(ret, 0, sizeof (xmlValidCtxt));
 697
 698     return (ret);
 699 }
 700
 701 /**
 702  * xmlFreeValidCtxt:
 703  * @cur:  the validation context to free
 704  *
 705  * Free a validation context structure.
 706  */
 707 void
 708 xmlFreeValidCtxt(xmlValidCtxtPtr cur) {
 709     xmlFree(cur);
 710 }
 711
 712 /**
 713  * xmlNewElementContent:
 714  * @name:  the subelement name or NULL
 715  * @type:  the type of element content decl
 716  *
 717  * Allocate an element content structure.
 718  *
 719  * Returns NULL if not, otherwise the new element content structure
 720  */
 721 xmlElementContentPtr
 722 xmlNewElementContent(xmlChar *name, xmlElementContentType type) {
 723     xmlElementContentPtr ret;
 724
 725     switch(type) {
 726         case XML_ELEMENT_CONTENT_ELEMENT:
 727             if (name == NULL) {
 728                 xmlGenericError(xmlGenericErrorContext,
 729                         "xmlNewElementContent : name == NULL !\n");
 730             }
 731             break;
 732         case XML_ELEMENT_CONTENT_PCDATA:
 733         case XML_ELEMENT_CONTENT_SEQ:
 734         case XML_ELEMENT_CONTENT_OR:
 735             if (name != NULL) {
 736                 xmlGenericError(xmlGenericErrorContext,
 737                         "xmlNewElementContent : name != NULL !\n");
 738             }
 739             break;
 740         default:
 741             xmlGenericError(xmlGenericErrorContext,
 742                     "xmlNewElementContent: unknown type %d\n", type);
 743             return(NULL);
 744     }
 745     ret = (xmlElementContentPtr) xmlMalloc(sizeof(xmlElementContent));
 746     if (ret == NULL) {
 747         xmlGenericError(xmlGenericErrorContext,
 748                 "xmlNewElementContent : out of memory!\n");
 749         return(NULL);
 750     }
 751     memset(ret, 0, sizeof(xmlElementContent));
 752     ret->type = type;
 753     ret->ocur = XML_ELEMENT_CONTENT_ONCE;
 754     if (name != NULL) {
 755         xmlChar *prefix = NULL;
 756         ret->name = xmlSplitQName2(name, &prefix);
 757         if (ret->name == NULL)
 758             ret->name = xmlStrdup(name);
 759         ret->prefix = prefix;
 760     } else {
 761         ret->name = NULL;
 762         ret->prefix = NULL;
 763     }
 764     ret->c1 = ret->c2 = ret->parent = NULL;
 765     return(ret);
 766 }
 767
 768 /**
 769  * xmlCopyElementContent:
 770  * @cur:  An element content pointer.
 771  *
 772  * Build a copy of an element content description.
 773  *
 774  * Returns the new xmlElementContentPtr or NULL in case of error.
 775  */
 776 xmlElementContentPtr
 777 xmlCopyElementContent(xmlElementContentPtr cur) {
 778     xmlElementContentPtr ret;
 779
 780     if (cur == NULL) return(NULL);
 781     ret = xmlNewElementContent((xmlChar *) cur->name, cur->type);
 782     if (ret == NULL) {
 783         xmlGenericError(xmlGenericErrorContext,
 784                 "xmlCopyElementContent : out of memory\n");
 785         return(NULL);
 786     }
 787     if (cur->prefix != NULL)
 788         ret->prefix = xmlStrdup(cur->prefix);
 789     ret->ocur = cur->ocur;
 790     if (cur->c1 != NULL) ret->c1 = xmlCopyElementContent(cur->c1);
 791     if (ret->c1 != NULL)
 792         ret->c1->parent = ret;
 793     if (cur->c2 != NULL) ret->c2 = xmlCopyElementContent(cur->c2);
 794     if (ret->c2 != NULL)
 795         ret->c2->parent = ret;
 796     return(ret);
 797 }
 798
 799 /**
 800  * xmlFreeElementContent:
 801  * @cur:  the element content tree to free
 802  *
 803  * Free an element content structure. This is a recursive call !
 804  */
 805 void
 806 xmlFreeElementContent(xmlElementContentPtr cur) {
 807     if (cur == NULL) return;
 808     switch (cur->type) {
 809         case XML_ELEMENT_CONTENT_PCDATA:
 810         case XML_ELEMENT_CONTENT_ELEMENT:
 811         case XML_ELEMENT_CONTENT_SEQ:
 812         case XML_ELEMENT_CONTENT_OR:
 813             break;
 814         default:
 815             xmlGenericError(xmlGenericErrorContext,
 816                     "xmlFreeElementContent : type %d\n", cur->type);
 817             return;
 818     }
 819     if (cur->c1 != NULL) xmlFreeElementContent(cur->c1);
 820     if (cur->c2 != NULL) xmlFreeElementContent(cur->c2);
 821     if (cur->name != NULL) xmlFree((xmlChar *) cur->name);
 822     if (cur->prefix != NULL) xmlFree((xmlChar *) cur->prefix);
 823     xmlFree(cur);
 824 }
 825
 826 /**
 827  * xmlDumpElementContent:
 828  * @buf:  An XML buffer
 829  * @content:  An element table
 830  * @glob: 1 if one must print the englobing parenthesis, 0 otherwise
 831  *
 832  * This will dump the content of the element table as an XML DTD definition
 833  */
 834 static void
 835 xmlDumpElementContent(xmlBufferPtr buf, xmlElementContentPtr content, int glob) {
 836     if (content == NULL) return;
 837
 838     if (glob) xmlBufferWriteChar(buf, "(");
 839     switch (content->type) {
 840         case XML_ELEMENT_CONTENT_PCDATA:
 841             xmlBufferWriteChar(buf, "#PCDATA");
 842             break;
 843         case XML_ELEMENT_CONTENT_ELEMENT:
 844             if (content->prefix != NULL) {
 845                 xmlBufferWriteCHAR(buf, content->prefix);
 846                 xmlBufferWriteChar(buf, ":");
 847             }
 848             xmlBufferWriteCHAR(buf, content->name);
 849             break;
 850         case XML_ELEMENT_CONTENT_SEQ:
 851             if ((content->c1->type == XML_ELEMENT_CONTENT_OR) ||
 852                 (content->c1->type == XML_ELEMENT_CONTENT_SEQ))
 853                 xmlDumpElementContent(buf, content->c1, 1);
 854             else
 855                 xmlDumpElementContent(buf, content->c1, 0);
 856             xmlBufferWriteChar(buf, " , ");
 857             if (content->c2->type == XML_ELEMENT_CONTENT_OR)
 858                 xmlDumpElementContent(buf, content->c2, 1);
 859             else
 860                 xmlDumpElementContent(buf, content->c2, 0);
 861             break;
 862         case XML_ELEMENT_CONTENT_OR:
 863             if ((content->c1->type == XML_ELEMENT_CONTENT_OR) ||
 864                 (content->c1->type == XML_ELEMENT_CONTENT_SEQ))
 865                 xmlDumpElementContent(buf, content->c1, 1);
 866             else
 867                 xmlDumpElementContent(buf, content->c1, 0);
 868             xmlBufferWriteChar(buf, " | ");
 869             if (content->c2->type == XML_ELEMENT_CONTENT_SEQ)
 870                 xmlDumpElementContent(buf, content->c2, 1);
 871             else
 872                 xmlDumpElementContent(buf, content->c2, 0);
 873             break;
 874         default:
 875             xmlGenericError(xmlGenericErrorContext,
 876                     "xmlDumpElementContent: unknown type %d\n",
 877                     content->type);
 878     }
 879     if (glob)
 880         xmlBufferWriteChar(buf, ")");
 881     switch (content->ocur) {
 882         case XML_ELEMENT_CONTENT_ONCE:
 883             break;
 884         case XML_ELEMENT_CONTENT_OPT:
 885             xmlBufferWriteChar(buf, "?");
 886             break;
 887         case XML_ELEMENT_CONTENT_MULT:
 888             xmlBufferWriteChar(buf, "*");
 889             break;
 890         case XML_ELEMENT_CONTENT_PLUS:
 891             xmlBufferWriteChar(buf, "+");
 892             break;
 893     }
 894 }
 895
 896 /**
 897  * xmlSprintfElementContent:
 898  * @buf:  an output buffer
 899  * @content:  An element table
 900  * @glob: 1 if one must print the englobing parenthesis, 0 otherwise
 901  *
 902  * Deprecated, unsafe, use xmlSnprintfElementContent
 903  */
 904 void
 905 xmlSprintfElementContent(char *buf ATTRIBUTE_UNUSED,
 906                          xmlElementContentPtr content ATTRIBUTE_UNUSED,
 907                          int glob ATTRIBUTE_UNUSED) {
 908 }
 909
 910 /**
 911  * xmlSnprintfElementContent:
 912  * @buf:  an output buffer
 913  * @size:  the buffer size
 914  * @content:  An element table
 915  * @glob: 1 if one must print the englobing parenthesis, 0 otherwise
 916  *
 917  * This will dump the content of the element content definition
 918  * Intended just for the debug routine
 919  */
 920 void
 921 xmlSnprintfElementContent(char *buf, int size, xmlElementContentPtr content, int glob) {
 922     int len;
 923
 924     if (content == NULL) return;
 925     len = strlen(buf);
 926     if (size - len < 50) {
 927         if ((size - len > 4) && (buf[len - 1] != '.'))
 928             strcat(buf, " ...");
 929         return;
 930     }
 931     if (glob) strcat(buf, "(");
 932     switch (content->type) {
 933         case XML_ELEMENT_CONTENT_PCDATA:
 934             strcat(buf, "#PCDATA");
 935             break;
 936         case XML_ELEMENT_CONTENT_ELEMENT:
 937             if (content->prefix != NULL) {
 938                 if (size - len < xmlStrlen(content->prefix) + 10) {
 939                     strcat(buf, " ...");
 940                     return;
 941                 }
 942                 strcat(buf, (char *) content->prefix);
 943                 strcat(buf, ":");
 944             }
 945             if (size - len < xmlStrlen(content->name) + 10) {
 946                 strcat(buf, " ...");
 947                 return;
 948             }
 949             if (content->name != NULL)
 950                 strcat(buf, (char *) content->name);
 951             break;
 952         case XML_ELEMENT_CONTENT_SEQ:
 953             if ((content->c1->type == XML_ELEMENT_CONTENT_OR) ||
 954                 (content->c1->type == XML_ELEMENT_CONTENT_SEQ))
 955                 xmlSnprintfElementContent(buf, size, content->c1, 1);
 956             else
 957                 xmlSnprintfElementContent(buf, size, content->c1, 0);
 958             len = strlen(buf);
 959             if (size - len < 50) {
 960                 if ((size - len > 4) && (buf[len - 1] != '.'))
 961                     strcat(buf, " ...");
 962                 return;
 963             }
 964             strcat(buf, " , ");
 965             if (((content->c2->type == XML_ELEMENT_CONTENT_OR) ||
 966                  (content->c2->ocur != XML_ELEMENT_CONTENT_ONCE)) &&
 967                 (content->c2->type != XML_ELEMENT_CONTENT_ELEMENT))
 968                 xmlSnprintfElementContent(buf, size, content->c2, 1);
 969             else
 970                 xmlSnprintfElementContent(buf, size, content->c2, 0);
 971             break;
 972         case XML_ELEMENT_CONTENT_OR:
 973             if ((content->c1->type == XML_ELEMENT_CONTENT_OR) ||
 974                 (content->c1->type == XML_ELEMENT_CONTENT_SEQ))
 975                 xmlSnprintfElementContent(buf, size, content->c1, 1);
 976             else
 977                 xmlSnprintfElementContent(buf, size, content->c1, 0);
 978             len = strlen(buf);
 979             if (size - len < 50) {
 980                 if ((size - len > 4) && (buf[len - 1] != '.'))
 981                     strcat(buf, " ...");
 982                 return;
 983             }
 984             strcat(buf, " | ");
 985             if (((content->c2->type == XML_ELEMENT_CONTENT_SEQ) ||
 986                  (content->c2->ocur != XML_ELEMENT_CONTENT_ONCE)) &&
 987                 (content->c2->type != XML_ELEMENT_CONTENT_ELEMENT))
 988                 xmlSnprintfElementContent(buf, size, content->c2, 1);
 989             else
 990                 xmlSnprintfElementContent(buf, size, content->c2, 0);
 991             break;
 992     }
 993     if (glob)
 994         strcat(buf, ")");
 995     switch (content->ocur) {
 996         case XML_ELEMENT_CONTENT_ONCE:
 997             break;
 998         case XML_ELEMENT_CONTENT_OPT:
 999             strcat(buf, "?");
1000             break;
1001         case XML_ELEMENT_CONTENT_MULT:
1002             strcat(buf, "*");
1003             break;
1004         case XML_ELEMENT_CONTENT_PLUS:
1005             strcat(buf, "+");
1006             break;
1007     }
1008 }
1009
1010 /****************************************************************
1011  *                                                              *
1012  *      Registration of DTD declarations                        *
1013  *                                                              *
1014  ****************************************************************/
1015
1016 /**
1017  * xmlCreateElementTable:
1018  *
1019  * create and initialize an empty element hash table.
1020  *
1021  * Returns the xmlElementTablePtr just created or NULL in case of error.
1022  */
1023 static xmlElementTablePtr
1024 xmlCreateElementTable(void) {
1025     return(xmlHashCreate(0));
1026 }
1027
1028 /**
1029  * xmlFreeElement:
1030  * @elem:  An element
1031  *
1032  * Deallocate the memory used by an element definition
1033  */
1034 static void
1035 xmlFreeElement(xmlElementPtr elem) {
1036     if (elem == NULL) return;
1037     xmlUnlinkNode((xmlNodePtr) elem);
1038     xmlFreeElementContent(elem->content);
1039     if (elem->name != NULL)
1040         xmlFree((xmlChar *) elem->name);
1041     if (elem->prefix != NULL)
1042         xmlFree((xmlChar *) elem->prefix);
1043 #ifdef LIBXML_REGEXP_ENABLED
1044     if (elem->contModel != NULL)
1045         xmlRegFreeRegexp(elem->contModel);
1046 #endif
1047     xmlFree(elem);
1048 }
1049
1050
1051 /**
1052  * xmlAddElementDecl:
1053  * @ctxt:  the validation context
1054  * @dtd:  pointer to the DTD
1055  * @name:  the entity name
1056  * @type:  the element type
1057  * @content:  the element content tree or NULL
1058  *
1059  * Register a new element declaration
1060  *
1061  * Returns NULL if not, otherwise the entity
1062  */
1063 xmlElementPtr
1064 xmlAddElementDecl(xmlValidCtxtPtr ctxt, xmlDtdPtr dtd, const xmlChar *name,
1065                   xmlElementTypeVal type,
1066                   xmlElementContentPtr content) {
1067     xmlElementPtr ret;
1068     xmlElementTablePtr table;
1069     xmlAttributePtr oldAttributes = NULL;
1070     xmlChar *ns, *uqname;
1071
1072     if (dtd == NULL) {
1073         xmlGenericError(xmlGenericErrorContext,
1074                 "xmlAddElementDecl: dtd == NULL\n");
1075         return(NULL);
1076     }
1077     if (name == NULL) {
1078         xmlGenericError(xmlGenericErrorContext,
1079                 "xmlAddElementDecl: name == NULL\n");
1080         return(NULL);
1081     }
1082     switch (type) {
1083         case XML_ELEMENT_TYPE_EMPTY:
1084             if (content != NULL) {
1085                 xmlGenericError(xmlGenericErrorContext,
1086                         "xmlAddElementDecl: content != NULL for EMPTY\n");
1087                 return(NULL);
1088             }
1089             break;
1090         case XML_ELEMENT_TYPE_ANY:
1091             if (content != NULL) {
1092                 xmlGenericError(xmlGenericErrorContext,
1093                         "xmlAddElementDecl: content != NULL for ANY\n");
1094                 return(NULL);
1095             }
1096             break;
1097         case XML_ELEMENT_TYPE_MIXED:
1098             if (content == NULL) {
1099                 xmlGenericError(xmlGenericErrorContext,
1100                         "xmlAddElementDecl: content == NULL for MIXED\n");
1101                 return(NULL);
1102             }
1103             break;
1104         case XML_ELEMENT_TYPE_ELEMENT:
1105             if (content == NULL) {
1106                 xmlGenericError(xmlGenericErrorContext,
1107                         "xmlAddElementDecl: content == NULL for ELEMENT\n");
1108                 return(NULL);
1109             }
1110             break;
1111         default:
1112             xmlGenericError(xmlGenericErrorContext,
1113                     "xmlAddElementDecl: unknown type %d\n", type);
1114             return(NULL);
1115     }
1116
1117     /*
1118      * check if name is a QName
1119      */
1120     uqname = xmlSplitQName2(name, &ns);
1121     if (uqname != NULL)
1122         name = uqname;
1123
1124     /*
1125      * Create the Element table if needed.
1126      */
1127     table = (xmlElementTablePtr) dtd->elements;
1128     if (table == NULL) {
1129         table = xmlCreateElementTable();
1130         dtd->elements = (void *) table;
1131     }
1132     if (table == NULL) {
1133         xmlGenericError(xmlGenericErrorContext,
1134                 "xmlAddElementDecl: Table creation failed!\n");
1135         if (uqname != NULL)
1136             xmlFree(uqname);
1137         if (ns != NULL)
1138             xmlFree(ns);
1139         return(NULL);
1140     }
1141
1142     /*
1143      * lookup old attributes inserted on an undefined element in the
1144      * internal subset.
1145      */
1146     if ((dtd->doc != NULL) && (dtd->doc->intSubset != NULL)) {
1147         ret = xmlHashLookup2(dtd->doc->intSubset->elements, name, ns);
1148         if ((ret != NULL) && (ret->etype == XML_ELEMENT_TYPE_UNDEFINED)) {
1149             oldAttributes = ret->attributes;
1150             ret->attributes = NULL;
1151             xmlHashRemoveEntry2(dtd->doc->intSubset->elements, name, ns, NULL);
1152             xmlFreeElement(ret);
1153         }
1154     }
1155
1156     /*
1157      * The element may already be present if one of its attribute
1158      * was registered first
1159      */
1160     ret = xmlHashLookup2(table, name, ns);
1161     if (ret != NULL) {
1162         if (ret->etype != XML_ELEMENT_TYPE_UNDEFINED) {
1163             /*
1164              * The element is already defined in this DTD.
1165              */
1166             VERROR(ctxt->userData, "Redefinition of element %s\n", name);
1167             if (uqname != NULL)
1168                 xmlFree(uqname);
1169             if (ns != NULL)
1170                 xmlFree(ns);
1171             return(NULL);
1172         }
1173     } else {
1174         ret = (xmlElementPtr) xmlMalloc(sizeof(xmlElement));
1175         if (ret == NULL) {
1176             xmlGenericError(xmlGenericErrorContext,
1177                     "xmlAddElementDecl: out of memory\n");
1178             if (uqname != NULL)
1179                 xmlFree(uqname);
1180             if (ns != NULL)
1181                 xmlFree(ns);
1182             return(NULL);
1183         }
1184         memset(ret, 0, sizeof(xmlElement));
1185         ret->type = XML_ELEMENT_DECL;
1186
1187         /*
1188          * fill the structure.
1189          */
1190         ret->name = xmlStrdup(name);
1191         if (ret->name == NULL) {
1192             xmlGenericError(xmlGenericErrorContext,
1193                     "xmlAddElementDecl: out of memory\n");
1194             if (uqname != NULL)
1195                 xmlFree(uqname);
1196             if (ns != NULL)
1197                 xmlFree(ns);
1198             xmlFree(ret);
1199             return(NULL);
1200         }
1201         ret->prefix = ns;
1202
1203         /*
1204          * Validity Check:
1205          * Insertion must not fail
1206          */
1207         if (xmlHashAddEntry2(table, name, ns, ret)) {
1208             /*
1209              * The element is already defined in this DTD.
1210              */
1211             VERROR(ctxt->userData, "Redefinition of element %s\n", name);
1212             xmlFreeElement(ret);
1213             if (uqname != NULL)
1214                 xmlFree(uqname);
1215             return(NULL);
1216         }
1217     }
1218
1219     /*
1220      * Finish to fill the structure.
1221      */
1222     ret->etype = type;
1223     ret->content = xmlCopyElementContent(content);
1224     ret->attributes = oldAttributes;
1225
1226     /*
1227      * Link it to the DTD
1228      */
1229     ret->parent = dtd;
1230     ret->doc = dtd->doc;
1231     if (dtd->last == NULL) {
1232         dtd->children = dtd->last = (xmlNodePtr) ret;
1233     } else {
1234         dtd->last->next = (xmlNodePtr) ret;
1235         ret->prev = dtd->last;
1236         dtd->last = (xmlNodePtr) ret;
1237     }
1238     if (uqname != NULL)
1239         xmlFree(uqname);
1240     return(ret);
1241 }
1242
1243 /**
1244  * xmlFreeElementTable:
1245  * @table:  An element table
1246  *
1247  * Deallocate the memory used by an element hash table.
1248  */
1249 void
1250 xmlFreeElementTable(xmlElementTablePtr table) {
1251     xmlHashFree(table, (xmlHashDeallocator) xmlFreeElement);
1252 }
1253
1254 /**
1255  * xmlCopyElement:
1256  * @elem:  An element
1257  *
1258  * Build a copy of an element.
1259  *
1260  * Returns the new xmlElementPtr or NULL in case of error.
1261  */
1262 static xmlElementPtr
1263 xmlCopyElement(xmlElementPtr elem) {
1264     xmlElementPtr cur;
1265
1266     cur = (xmlElementPtr) xmlMalloc(sizeof(xmlElement));
1267     if (cur == NULL) {
1268         xmlGenericError(xmlGenericErrorContext,
1269                 "xmlCopyElement: out of memory !\n");
1270         return(NULL);
1271     }
1272     memset(cur, 0, sizeof(xmlElement));
1273     cur->type = XML_ELEMENT_DECL;
1274     cur->etype = elem->etype;
1275     if (elem->name != NULL)
1276         cur->name = xmlStrdup(elem->name);
1277     else
1278         cur->name = NULL;
1279     if (elem->prefix != NULL)
1280         cur->prefix = xmlStrdup(elem->prefix);
1281     else
1282         cur->prefix = NULL;
1283     cur->content = xmlCopyElementContent(elem->content);
1284     /* TODO : rebuild the attribute list on the copy */
1285     cur->attributes = NULL;
1286     return(cur);
1287 }
1288
1289 /**
1290  * xmlCopyElementTable:
1291  * @table:  An element table
1292  *
1293  * Build a copy of an element table.
1294  *
1295  * Returns the new xmlElementTablePtr or NULL in case of error.
1296  */
1297 xmlElementTablePtr
1298 xmlCopyElementTable(xmlElementTablePtr table) {
1299     return((xmlElementTablePtr) xmlHashCopy(table,
1300                                             (xmlHashCopier) xmlCopyElement));
1301 }
1302
1303 /**
1304  * xmlDumpElementDecl:
1305  * @buf:  the XML buffer output
1306  * @elem:  An element table
1307  *
1308  * This will dump the content of the element declaration as an XML
1309  * DTD definition
1310  */
1311 void
1312 xmlDumpElementDecl(xmlBufferPtr buf, xmlElementPtr elem) {
1313     switch (elem->etype) {
1314         case XML_ELEMENT_TYPE_EMPTY:
1315             xmlBufferWriteChar(buf, "<!ELEMENT ");
1316             if (elem->prefix != NULL) {
1317                 xmlBufferWriteCHAR(buf, elem->prefix);
1318                 xmlBufferWriteChar(buf, ":");
1319             }
1320             xmlBufferWriteCHAR(buf, elem->name);
1321             xmlBufferWriteChar(buf, " EMPTY>\n");
1322             break;
1323         case XML_ELEMENT_TYPE_ANY:
1324             xmlBufferWriteChar(buf, "<!ELEMENT ");
1325             if (elem->prefix != NULL) {
1326                 xmlBufferWriteCHAR(buf, elem->prefix);
1327                 xmlBufferWriteChar(buf, ":");
1328             }
1329             xmlBufferWriteCHAR(buf, elem->name);
1330             xmlBufferWriteChar(buf, " ANY>\n");
1331             break;
1332         case XML_ELEMENT_TYPE_MIXED:
1333             xmlBufferWriteChar(buf, "<!ELEMENT ");
1334             if (elem->prefix != NULL) {
1335                 xmlBufferWriteCHAR(buf, elem->prefix);
1336                 xmlBufferWriteChar(buf, ":");
1337             }
1338             xmlBufferWriteCHAR(buf, elem->name);
1339             xmlBufferWriteChar(buf, " ");
1340             xmlDumpElementContent(buf, elem->content, 1);
1341             xmlBufferWriteChar(buf, ">\n");
1342             break;
1343         case XML_ELEMENT_TYPE_ELEMENT:
1344             xmlBufferWriteChar(buf, "<!ELEMENT ");
1345             if (elem->prefix != NULL) {
1346                 xmlBufferWriteCHAR(buf, elem->prefix);
1347                 xmlBufferWriteChar(buf, ":");
1348             }
1349             xmlBufferWriteCHAR(buf, elem->name);
1350             xmlBufferWriteChar(buf, " ");
1351             xmlDumpElementContent(buf, elem->content, 1);
1352             xmlBufferWriteChar(buf, ">\n");
1353             break;
1354         default:
1355             xmlGenericError(xmlGenericErrorContext,
1356                 "xmlDumpElementDecl: internal: unknown type %d\n",
1357                     elem->etype);
1358     }
1359 }
1360
1361 /**
1362  * xmlDumpElementTable:
1363  * @buf:  the XML buffer output
1364  * @table:  An element table
1365  *
1366  * This will dump the content of the element table as an XML DTD definition
1367  */
1368 void
1369 xmlDumpElementTable(xmlBufferPtr buf, xmlElementTablePtr table) {
1370     xmlHashScan(table, (xmlHashScanner) xmlDumpElementDecl, buf);
1371 }
1372
1373 /**
1374  * xmlCreateEnumeration:
1375  * @name:  the enumeration name or NULL
1376  *
1377  * create and initialize an enumeration attribute node.
1378  *
1379  * Returns the xmlEnumerationPtr just created or NULL in case
1380  *                of error.
1381  */
1382 xmlEnumerationPtr
1383 xmlCreateEnumeration(xmlChar *name) {
1384     xmlEnumerationPtr ret;
1385
1386     ret = (xmlEnumerationPtr) xmlMalloc(sizeof(xmlEnumeration));
1387     if (ret == NULL) {
1388         xmlGenericError(xmlGenericErrorContext,
1389                 "xmlCreateEnumeration : xmlMalloc(%ld) failed\n",
1390                 (long)sizeof(xmlEnumeration));
1391         return(NULL);
1392     }
1393     memset(ret, 0, sizeof(xmlEnumeration));
1394
1395     if (name != NULL)
1396         ret->name = xmlStrdup(name);
1397     return(ret);
1398 }
1399
1400 /**
1401  * xmlFreeEnumeration:
1402  * @cur:  the tree to free.
1403  *
1404  * free an enumeration attribute node (recursive).
1405  */
1406 void
1407 xmlFreeEnumeration(xmlEnumerationPtr cur) {
1408     if (cur == NULL) return;
1409
1410     if (cur->next != NULL) xmlFreeEnumeration(cur->next);
1411
1412     if (cur->name != NULL) xmlFree((xmlChar *) cur->name);
1413     xmlFree(cur);
1414 }
1415
1416 /**
1417  * xmlCopyEnumeration:
1418  * @cur:  the tree to copy.
1419  *
1420  * Copy an enumeration attribute node (recursive).
1421  *
1422  * Returns the xmlEnumerationPtr just created or NULL in case
1423  *                of error.
1424  */
1425 xmlEnumerationPtr
1426 xmlCopyEnumeration(xmlEnumerationPtr cur) {
1427     xmlEnumerationPtr ret;
1428
1429     if (cur == NULL) return(NULL);
1430     ret = xmlCreateEnumeration((xmlChar *) cur->name);
1431
1432     if (cur->next != NULL) ret->next = xmlCopyEnumeration(cur->next);
1433     else ret->next = NULL;
1434
1435     return(ret);
1436 }
1437
1438 /**
1439  * xmlDumpEnumeration:
1440  * @buf:  the XML buffer output
1441  * @enum:  An enumeration
1442  *
1443  * This will dump the content of the enumeration
1444  */
1445 static void
1446 xmlDumpEnumeration(xmlBufferPtr buf, xmlEnumerationPtr cur) {
1447     if (cur == NULL)  return;
1448
1449     xmlBufferWriteCHAR(buf, cur->name);
1450     if (cur->next == NULL)
1451         xmlBufferWriteChar(buf, ")");
1452     else {
1453         xmlBufferWriteChar(buf, " | ");
1454         xmlDumpEnumeration(buf, cur->next);
1455     }
1456 }
1457
1458 /**
1459  * xmlCreateAttributeTable:
1460  *
1461  * create and initialize an empty attribute hash table.
1462  *
1463  * Returns the xmlAttributeTablePtr just created or NULL in case
1464  *                of error.
1465  */
1466 static xmlAttributeTablePtr
1467 xmlCreateAttributeTable(void) {
1468     return(xmlHashCreate(0));
1469 }
1470
1471 /**
1472  * xmlScanAttributeDeclCallback:
1473  * @attr:  the attribute decl
1474  * @list:  the list to update
1475  *
1476  * Callback called by xmlScanAttributeDecl when a new attribute
1477  * has to be entered in the list.
1478  */
1479 static void
1480 xmlScanAttributeDeclCallback(xmlAttributePtr attr, xmlAttributePtr *list,
1481                              const xmlChar* name ATTRIBUTE_UNUSED) {
1482     attr->nexth = *list;
1483     *list = attr;
1484 }
1485
1486 /**
1487  * xmlScanAttributeDecl:
1488  * @dtd:  pointer to the DTD
1489  * @elem:  the element name
1490  *
1491  * When inserting a new element scan the DtD for existing attributes
1492  * for that element and initialize the Attribute chain
1493  *
1494  * Returns the pointer to the first attribute decl in the chain,
1495  *         possibly NULL.
1496  */
1497 xmlAttributePtr
1498 xmlScanAttributeDecl(xmlDtdPtr dtd, const xmlChar *elem) {
1499     xmlAttributePtr ret = NULL;
1500     xmlAttributeTablePtr table;
1501
1502     if (dtd == NULL) {
1503         xmlGenericError(xmlGenericErrorContext,
1504                 "xmlScanAttributeDecl: dtd == NULL\n");
1505         return(NULL);
1506     }
1507     if (elem == NULL) {
1508         xmlGenericError(xmlGenericErrorContext,
1509                 "xmlScanAttributeDecl: elem == NULL\n");
1510         return(NULL);
1511     }
1512     table = (xmlAttributeTablePtr) dtd->attributes;
1513     if (table == NULL)
1514         return(NULL);
1515
1516     /* WRONG !!! */
1517     xmlHashScan3(table, NULL, NULL, elem,
1518                 (xmlHashScanner) xmlScanAttributeDeclCallback, &ret);
1519     return(ret);
1520 }
1521
1522 /**
1523  * xmlScanIDAttributeDecl:
1524  * @ctxt:  the validation context
1525  * @elem:  the element name
1526  *
1527  * Verify that the element don't have too many ID attributes
1528  * declared.
1529  *
1530  * Returns the number of ID attributes found.
1531  */
1532 static int
1533 xmlScanIDAttributeDecl(xmlValidCtxtPtr ctxt, xmlElementPtr elem) {
1534     xmlAttributePtr cur;
1535     int ret = 0;
1536
1537     if (elem == NULL) return(0);
1538     cur = elem->attributes;
1539     while (cur != NULL) {
1540         if (cur->atype == XML_ATTRIBUTE_ID) {
1541             ret ++;
1542             if (ret > 1)
1543                 VERROR(ctxt->userData,
1544                "Element %s has too many ID attributes defined : %s\n",
1545                        elem->name, cur->name);
1546         }
1547         cur = cur->nexth;
1548     }
1549     return(ret);
1550 }
1551
1552 /**
1553  * xmlFreeAttribute:
1554  * @elem:  An attribute
1555  *
1556  * Deallocate the memory used by an attribute definition
1557  */
1558 static void
1559 xmlFreeAttribute(xmlAttributePtr attr) {
1560     if (attr == NULL) return;
1561     xmlUnlinkNode((xmlNodePtr) attr);
1562     if (attr->tree != NULL)
1563         xmlFreeEnumeration(attr->tree);
1564     if (attr->elem != NULL)
1565         xmlFree((xmlChar *) attr->elem);
1566     if (attr->name != NULL)
1567         xmlFree((xmlChar *) attr->name);
1568     if (attr->defaultValue != NULL)
1569         xmlFree((xmlChar *) attr->defaultValue);
1570     if (attr->prefix != NULL)
1571         xmlFree((xmlChar *) attr->prefix);
1572     xmlFree(attr);
1573 }
1574
1575
1576 /**
1577  * xmlAddAttributeDecl:
1578  * @ctxt:  the validation context
1579  * @dtd:  pointer to the DTD
1580  * @elem:  the element name
1581  * @name:  the attribute name
1582  * @ns:  the attribute namespace prefix
1583  * @type:  the attribute type
1584  * @def:  the attribute default type
1585  * @defaultValue:  the attribute default value
1586  * @tree:  if it's an enumeration, the associated list
1587  *
1588  * Register a new attribute declaration
1589  * Note that @tree becomes the ownership of the DTD
1590  *
1591  * Returns NULL if not new, otherwise the attribute decl
1592  */
1593 xmlAttributePtr
1594 xmlAddAttributeDecl(xmlValidCtxtPtr ctxt, xmlDtdPtr dtd, const xmlChar *elem,
1595                     const xmlChar *name, const xmlChar *ns,
1596                     xmlAttributeType type, xmlAttributeDefault def,
1597                     const xmlChar *defaultValue, xmlEnumerationPtr tree) {
1598     xmlAttributePtr ret;
1599     xmlAttributeTablePtr table;
1600     xmlElementPtr elemDef;
1601
1602     if (dtd == NULL) {
1603         xmlGenericError(xmlGenericErrorContext,
1604                 "xmlAddAttributeDecl: dtd == NULL\n");
1605         xmlFreeEnumeration(tree);
1606         return(NULL);
1607     }
1608     if (name == NULL) {
1609         xmlGenericError(xmlGenericErrorContext,
1610                 "xmlAddAttributeDecl: name == NULL\n");
1611         xmlFreeEnumeration(tree);
1612         return(NULL);
1613     }
1614     if (elem == NULL) {
1615         xmlGenericError(xmlGenericErrorContext,
1616                 "xmlAddAttributeDecl: elem == NULL\n");
1617         xmlFreeEnumeration(tree);
1618         return(NULL);
1619     }
1620
1621     /*
1622      * Check the type and possibly the default value.
1623      */
1624     switch (type) {
1625         case XML_ATTRIBUTE_CDATA:
1626             break;
1627         case XML_ATTRIBUTE_ID:
1628             break;
1629         case XML_ATTRIBUTE_IDREF:
1630             break;
1631         case XML_ATTRIBUTE_IDREFS:
1632             break;
1633         case XML_ATTRIBUTE_ENTITY:
1634             break;
1635         case XML_ATTRIBUTE_ENTITIES:
1636             break;
1637         case XML_ATTRIBUTE_NMTOKEN:
1638             break;
1639         case XML_ATTRIBUTE_NMTOKENS:
1640             break;
1641         case XML_ATTRIBUTE_ENUMERATION:
1642             break;
1643         case XML_ATTRIBUTE_NOTATION:
1644             break;
1645         default:
1646             xmlGenericError(xmlGenericErrorContext,
1647                     "xmlAddAttributeDecl: unknown type %d\n", type);
1648             xmlFreeEnumeration(tree);
1649             return(NULL);
1650     }
1651     if ((defaultValue != NULL) &&
1652         (!xmlValidateAttributeValue(type, defaultValue))) {
1653         VERROR(ctxt->userData, "Attribute %s of %s: invalid default value\n",
1654                elem, name, defaultValue);
1655         defaultValue = NULL;
1656         ctxt->valid = 0;
1657     }
1658
1659     /*
1660      * Check first that an attribute defined in the external subset wasn't
1661      * already defined in the internal subset
1662      */
1663     if ((dtd->doc != NULL) && (dtd->doc->extSubset == dtd) &&
1664         (dtd->doc->intSubset != NULL) &&
1665         (dtd->doc->intSubset->attributes != NULL)) {
1666         ret = xmlHashLookup3(dtd->doc->intSubset->attributes, name, ns, elem);
1667         if (ret != NULL)
1668             return(NULL);
1669     }
1670
1671     /*
1672      * Create the Attribute table if needed.
1673      */
1674     table = (xmlAttributeTablePtr) dtd->attributes;
1675     if (table == NULL) {
1676         table = xmlCreateAttributeTable();
1677         dtd->attributes = (void *) table;
1678     }
1679     if (table == NULL) {
1680         xmlGenericError(xmlGenericErrorContext,
1681                 "xmlAddAttributeDecl: Table creation failed!\n");
1682         return(NULL);
1683     }
1684
1685
1686     ret = (xmlAttributePtr) xmlMalloc(sizeof(xmlAttribute));
1687     if (ret == NULL) {
1688         xmlGenericError(xmlGenericErrorContext,
1689                 "xmlAddAttributeDecl: out of memory\n");
1690         return(NULL);
1691     }
1692     memset(ret, 0, sizeof(xmlAttribute));
1693     ret->type = XML_ATTRIBUTE_DECL;
1694
1695     /*
1696      * fill the structure.
1697      */
1698     ret->atype = type;
1699     ret->name = xmlStrdup(name);
1700     ret->prefix = xmlStrdup(ns);
1701     ret->elem = xmlStrdup(elem);
1702     ret->def = def;
1703     ret->tree = tree;
1704     if (defaultValue != NULL)
1705         ret->defaultValue = xmlStrdup(defaultValue);
1706
1707     /*
1708      * Validity Check:
1709      * Search the DTD for previous declarations of the ATTLIST
1710      */
1711     if (xmlHashAddEntry3(table, name, ns, elem, ret) < 0) {
1712         /*
1713          * The attribute is already defined in this DTD.
1714          */
1715         VWARNING(ctxt->userData,
1716                  "Attribute %s of element %s: already defined\n",
1717                  name, elem);
1718         xmlFreeAttribute(ret);
1719         return(NULL);
1720     }
1721
1722     /*
1723      * Validity Check:
1724      * Multiple ID per element
1725      */
1726     elemDef = xmlGetDtdElementDesc2(dtd, elem, 1);
1727     if (elemDef != NULL) {
1728
1729         if ((type == XML_ATTRIBUTE_ID) &&
1730             (xmlScanIDAttributeDecl(NULL, elemDef) != 0)) {
1731             VERROR(ctxt->userData,
1732            "Element %s has too may ID attributes defined : %s\n",
1733                    elem, name);
1734             ctxt->valid = 0;
1735         }
1736
1737         /*
1738          * Insert namespace default def first they need to be
1739          * processed first.
1740          */
1741         if ((xmlStrEqual(ret->name, BAD_CAST "xmlns")) ||
1742             ((ret->prefix != NULL &&
1743              (xmlStrEqual(ret->prefix, BAD_CAST "xmlns"))))) {
1744             ret->nexth = elemDef->attributes;
1745             elemDef->attributes = ret;
1746         } else {
1747             xmlAttributePtr tmp = elemDef->attributes;
1748
1749             while ((tmp != NULL) &&
1750                    ((xmlStrEqual(tmp->name, BAD_CAST "xmlns")) ||
1751                     ((ret->prefix != NULL &&
1752                      (xmlStrEqual(ret->prefix, BAD_CAST "xmlns")))))) {
1753                 if (tmp->nexth == NULL)
1754                     break;
1755                 tmp = tmp->nexth;
1756             }
1757             if (tmp != NULL) {
1758                 ret->nexth = tmp->nexth;
1759                 tmp->nexth = ret;
1760             } else {
1761                 ret->nexth = elemDef->attributes;
1762                 elemDef->attributes = ret;
1763             }
1764         }
1765     }
1766
1767     /*
1768      * Link it to the DTD
1769      */
1770     ret->parent = dtd;
1771     ret->doc = dtd->doc;
1772     if (dtd->last == NULL) {
1773         dtd->children = dtd->last = (xmlNodePtr) ret;
1774     } else {
1775         dtd->last->next = (xmlNodePtr) ret;
1776         ret->prev = dtd->last;
1777         dtd->last = (xmlNodePtr) ret;
1778     }
1779     return(ret);
1780 }
1781
1782 /**
1783  * xmlFreeAttributeTable:
1784  * @table:  An attribute table
1785  *
1786  * Deallocate the memory used by an entities hash table.
1787  */
1788 void
1789 xmlFreeAttributeTable(xmlAttributeTablePtr table) {
1790     xmlHashFree(table, (xmlHashDeallocator) xmlFreeAttribute);
1791 }
1792
1793 /**
1794  * xmlCopyAttribute:
1795  * @attr:  An attribute
1796  *
1797  * Build a copy of an attribute.
1798  *
1799  * Returns the new xmlAttributePtr or NULL in case of error.
1800  */
1801 static xmlAttributePtr
1802 xmlCopyAttribute(xmlAttributePtr attr) {
1803     xmlAttributePtr cur;
1804
1805     cur = (xmlAttributePtr) xmlMalloc(sizeof(xmlAttribute));
1806     if (cur == NULL) {
1807         xmlGenericError(xmlGenericErrorContext,
1808                 "xmlCopyAttribute: out of memory !\n");
1809         return(NULL);
1810     }
1811     memset(cur, 0, sizeof(xmlAttribute));
1812     cur->type = XML_ATTRIBUTE_DECL;
1813     cur->atype = attr->atype;
1814     cur->def = attr->def;
1815     cur->tree = xmlCopyEnumeration(attr->tree);
1816     if (attr->elem != NULL)
1817         cur->elem = xmlStrdup(attr->elem);
1818     if (attr->name != NULL)
1819         cur->name = xmlStrdup(attr->name);
1820     if (attr->prefix != NULL)
1821         cur->prefix = xmlStrdup(attr->prefix);
1822     if (attr->defaultValue != NULL)
1823         cur->defaultValue = xmlStrdup(attr->defaultValue);
1824     return(cur);
1825 }
1826
1827 /**
1828  * xmlCopyAttributeTable:
1829  * @table:  An attribute table
1830  *
1831  * Build a copy of an attribute table.
1832  *
1833  * Returns the new xmlAttributeTablePtr or NULL in case of error.
1834  */
1835 xmlAttributeTablePtr
1836 xmlCopyAttributeTable(xmlAttributeTablePtr table) {
1837     return((xmlAttributeTablePtr) xmlHashCopy(table,
1838                                     (xmlHashCopier) xmlCopyAttribute));
1839 }
1840
1841 /**
1842  * xmlDumpAttributeDecl:
1843  * @buf:  the XML buffer output
1844  * @attr:  An attribute declaration
1845  *
1846  * This will dump the content of the attribute declaration as an XML
1847  * DTD definition
1848  */
1849 void
1850 xmlDumpAttributeDecl(xmlBufferPtr buf, xmlAttributePtr attr) {
1851     xmlBufferWriteChar(buf, "<!ATTLIST ");
1852     xmlBufferWriteCHAR(buf, attr->elem);
1853     xmlBufferWriteChar(buf, " ");
1854     if (attr->prefix != NULL) {
1855         xmlBufferWriteCHAR(buf, attr->prefix);
1856         xmlBufferWriteChar(buf, ":");
1857     }
1858     xmlBufferWriteCHAR(buf, attr->name);
1859     switch (attr->atype) {
1860         case XML_ATTRIBUTE_CDATA:
1861             xmlBufferWriteChar(buf, " CDATA");
1862             break;
1863         case XML_ATTRIBUTE_ID:
1864             xmlBufferWriteChar(buf, " ID");
1865             break;
1866         case XML_ATTRIBUTE_IDREF:
1867             xmlBufferWriteChar(buf, " IDREF");
1868             break;
1869         case XML_ATTRIBUTE_IDREFS:
1870             xmlBufferWriteChar(buf, " IDREFS");
1871             break;
1872         case XML_ATTRIBUTE_ENTITY:
1873             xmlBufferWriteChar(buf, " ENTITY");
1874             break;
1875         case XML_ATTRIBUTE_ENTITIES:
1876             xmlBufferWriteChar(buf, " ENTITIES");
1877             break;
1878         case XML_ATTRIBUTE_NMTOKEN:
1879             xmlBufferWriteChar(buf, " NMTOKEN");
1880             break;
1881         case XML_ATTRIBUTE_NMTOKENS:
1882             xmlBufferWriteChar(buf, " NMTOKENS");
1883             break;
1884         case XML_ATTRIBUTE_ENUMERATION:
1885             xmlBufferWriteChar(buf, " (");
1886             xmlDumpEnumeration(buf, attr->tree);
1887             break;
1888         case XML_ATTRIBUTE_NOTATION:
1889             xmlBufferWriteChar(buf, " NOTATION (");
1890             xmlDumpEnumeration(buf, attr->tree);
1891             break;
1892         default:
1893             xmlGenericError(xmlGenericErrorContext,
1894                 "xmlDumpAttributeDecl: internal: unknown type %d\n",
1895                     attr->atype);
1896     }
1897     switch (attr->def) {
1898         case XML_ATTRIBUTE_NONE:
1899             break;
1900         case XML_ATTRIBUTE_REQUIRED:
1901             xmlBufferWriteChar(buf, " #REQUIRED");
1902             break;
1903         case XML_ATTRIBUTE_IMPLIED:
1904             xmlBufferWriteChar(buf, " #IMPLIED");
1905             break;
1906         case XML_ATTRIBUTE_FIXED:
1907             xmlBufferWriteChar(buf, " #FIXED");
1908             break;
1909         default:
1910             xmlGenericError(xmlGenericErrorContext,
1911                 "xmlDumpAttributeDecl: internal: unknown default %d\n",
1912                     attr->def);
1913     }
1914     if (attr->defaultValue != NULL) {
1915         xmlBufferWriteChar(buf, " ");
1916         xmlBufferWriteQuotedString(buf, attr->defaultValue);
1917     }
1918     xmlBufferWriteChar(buf, ">\n");
1919 }
1920
1921 /**
1922  * xmlDumpAttributeTable:
1923  * @buf:  the XML buffer output
1924  * @table:  An attribute table
1925  *
1926  * This will dump the content of the attribute table as an XML DTD definition
1927  */
1928 void
1929 xmlDumpAttributeTable(xmlBufferPtr buf, xmlAttributeTablePtr table) {
1930     xmlHashScan(table, (xmlHashScanner) xmlDumpAttributeDecl, buf);
1931 }
1932
1933 /************************************************************************
1934  *                                                                      *
1935  *                              NOTATIONs                               *
1936  *                                                                      *
1937  ************************************************************************/
1938 /**
1939  * xmlCreateNotationTable:
1940  *
1941  * create and initialize an empty notation hash table.
1942  *
1943  * Returns the xmlNotationTablePtr just created or NULL in case
1944  *                of error.
1945  */
1946 static xmlNotationTablePtr
1947 xmlCreateNotationTable(void) {
1948     return(xmlHashCreate(0));
1949 }
1950
1951 /**
1952  * xmlFreeNotation:
1953  * @not:  A notation
1954  *
1955  * Deallocate the memory used by an notation definition
1956  */
1957 static void
1958 xmlFreeNotation(xmlNotationPtr nota) {
1959     if (nota == NULL) return;
1960     if (nota->name != NULL)
1961         xmlFree((xmlChar *) nota->name);
1962     if (nota->PublicID != NULL)
1963         xmlFree((xmlChar *) nota->PublicID);
1964     if (nota->SystemID != NULL)
1965         xmlFree((xmlChar *) nota->SystemID);
1966     xmlFree(nota);
1967 }
1968
1969
1970 /**
1971  * xmlAddNotationDecl:
1972  * @dtd:  pointer to the DTD
1973  * @ctxt:  the validation context
1974  * @name:  the entity name
1975  * @PublicID:  the public identifier or NULL
1976  * @SystemID:  the system identifier or NULL
1977  *
1978  * Register a new notation declaration
1979  *
1980  * Returns NULL if not, otherwise the entity
1981  */
1982 xmlNotationPtr
1983 xmlAddNotationDecl(xmlValidCtxtPtr ctxt ATTRIBUTE_UNUSED, xmlDtdPtr dtd,
1984                    const xmlChar *name,
1985                    const xmlChar *PublicID, const xmlChar *SystemID) {
1986     xmlNotationPtr ret;
1987     xmlNotationTablePtr table;
1988
1989     if (dtd == NULL) {
1990         xmlGenericError(xmlGenericErrorContext,
1991                 "xmlAddNotationDecl: dtd == NULL\n");
1992         return(NULL);
1993     }
1994     if (name == NULL) {
1995         xmlGenericError(xmlGenericErrorContext,
1996                 "xmlAddNotationDecl: name == NULL\n");
1997         return(NULL);
1998     }
1999     if ((PublicID == NULL) && (SystemID == NULL)) {
2000         xmlGenericError(xmlGenericErrorContext,
2001                 "xmlAddNotationDecl: no PUBLIC ID nor SYSTEM ID\n");
2002         return(NULL);
2003     }
2004
2005     /*
2006      * Create the Notation table if needed.
2007      */
2008     table = (xmlNotationTablePtr) dtd->notations;
2009     if (table == NULL)
2010         dtd->notations = table = xmlCreateNotationTable();
2011     if (table == NULL) {
2012         xmlGenericError(xmlGenericErrorContext,
2013                 "xmlAddNotationDecl: Table creation failed!\n");
2014         return(NULL);
2015     }
2016
2017     ret = (xmlNotationPtr) xmlMalloc(sizeof(xmlNotation));
2018     if (ret == NULL) {
2019         xmlGenericError(xmlGenericErrorContext,
2020                 "xmlAddNotationDecl: out of memory\n");
2021         return(NULL);
2022     }
2023     memset(ret, 0, sizeof(xmlNotation));
2024
2025     /*
2026      * fill the structure.
2027      */
2028     ret->name = xmlStrdup(name);
2029     if (SystemID != NULL)
2030         ret->SystemID = xmlStrdup(SystemID);
2031     if (PublicID != NULL)
2032         ret->PublicID = xmlStrdup(PublicID);
2033
2034     /*
2035      * Validity Check:
2036      * Check the DTD for previous declarations of the ATTLIST
2037      */
2038     if (xmlHashAddEntry(table, name, ret)) {
2039         xmlGenericError(xmlGenericErrorContext,
2040                 "xmlAddNotationDecl: %s already defined\n", name);
2041         xmlFreeNotation(ret);
2042         return(NULL);
2043     }
2044     return(ret);
2045 }
2046
2047 /**
2048  * xmlFreeNotationTable:
2049  * @table:  An notation table
2050  *
2051  * Deallocate the memory used by an entities hash table.
2052  */
2053 void
2054 xmlFreeNotationTable(xmlNotationTablePtr table) {
2055     xmlHashFree(table, (xmlHashDeallocator) xmlFreeNotation);
2056 }
2057
2058 /**
2059  * xmlCopyNotation:
2060  * @nota:  A notation
2061  *
2062  * Build a copy of a notation.
2063  *
2064  * Returns the new xmlNotationPtr or NULL in case of error.
2065  */
2066 static xmlNotationPtr
2067 xmlCopyNotation(xmlNotationPtr nota) {
2068     xmlNotationPtr cur;
2069
2070     cur = (xmlNotationPtr) xmlMalloc(sizeof(xmlNotation));
2071     if (cur == NULL) {
2072         xmlGenericError(xmlGenericErrorContext,
2073                 "xmlCopyNotation: out of memory !\n");
2074         return(NULL);
2075     }
2076     if (nota->name != NULL)
2077         cur->name = xmlStrdup(nota->name);
2078     else
2079         cur->name = NULL;
2080     if (nota->PublicID != NULL)
2081         cur->PublicID = xmlStrdup(nota->PublicID);
2082     else
2083         cur->PublicID = NULL;
2084     if (nota->SystemID != NULL)
2085         cur->SystemID = xmlStrdup(nota->SystemID);
2086     else
2087         cur->SystemID = NULL;
2088     return(cur);
2089 }
2090
2091 /**
2092  * xmlCopyNotationTable:
2093  * @table:  A notation table
2094  *
2095  * Build a copy of a notation table.
2096  *
2097  * Returns the new xmlNotationTablePtr or NULL in case of error.
2098  */
2099 xmlNotationTablePtr
2100 xmlCopyNotationTable(xmlNotationTablePtr table) {
2101     return((xmlNotationTablePtr) xmlHashCopy(table,
2102                                     (xmlHashCopier) xmlCopyNotation));
2103 }
2104
2105 /**
2106  * xmlDumpNotationDecl:
2107  * @buf:  the XML buffer output
2108  * @nota:  A notation declaration
2109  *
2110  * This will dump the content the notation declaration as an XML DTD definition
2111  */
2112 void
2113 xmlDumpNotationDecl(xmlBufferPtr buf, xmlNotationPtr nota) {
2114     xmlBufferWriteChar(buf, "<!NOTATION ");
2115     xmlBufferWriteCHAR(buf, nota->name);
2116     if (nota->PublicID != NULL) {
2117         xmlBufferWriteChar(buf, " PUBLIC ");
2118         xmlBufferWriteQuotedString(buf, nota->PublicID);
2119         if (nota->SystemID != NULL) {
2120             xmlBufferWriteChar(buf, " ");
2121             xmlBufferWriteCHAR(buf, nota->SystemID);
2122         }
2123     } else {
2124         xmlBufferWriteChar(buf, " SYSTEM ");
2125         xmlBufferWriteCHAR(buf, nota->SystemID);
2126     }
2127     xmlBufferWriteChar(buf, " >\n");
2128 }
2129
2130 /**
2131  * xmlDumpNotationTable:
2132  * @buf:  the XML buffer output
2133  * @table:  A notation table
2134  *
2135  * This will dump the content of the notation table as an XML DTD definition
2136  */
2137 void
2138 xmlDumpNotationTable(xmlBufferPtr buf, xmlNotationTablePtr table) {
2139     xmlHashScan(table, (xmlHashScanner) xmlDumpNotationDecl, buf);
2140 }
2141
2142 /************************************************************************
2143  *                                                                      *
2144  *                              IDs                                     *
2145  *                                                                      *
2146  ************************************************************************/
2147 /**
2148  * xmlCreateIDTable:
2149  *
2150  * create and initialize an empty id hash table.
2151  *
2152  * Returns the xmlIDTablePtr just created or NULL in case
2153  *                of error.
2154  */
2155 static xmlIDTablePtr
2156 xmlCreateIDTable(void) {
2157     return(xmlHashCreate(0));
2158 }
2159
2160 /**
2161  * xmlFreeID:
2162  * @not:  A id
2163  *
2164  * Deallocate the memory used by an id definition
2165  */
2166 static void
2167 xmlFreeID(xmlIDPtr id) {
2168     if (id == NULL) return;
2169     if (id->value != NULL)
2170         xmlFree((xmlChar *) id->value);
2171     if (id->name != NULL)
2172         xmlFree((xmlChar *) id->name);
2173     xmlFree(id);
2174 }
2175
2176 /**
2177  * xmlAddID:
2178  * @ctxt:  the validation context
2179  * @doc:  pointer to the document
2180  * @value:  the value name
2181  * @attr:  the attribute holding the ID
2182  *
2183  * Register a new id declaration
2184  *
2185  * Returns NULL if not, otherwise the new xmlIDPtr
2186  */
2187 xmlIDPtr
2188 xmlAddID(xmlValidCtxtPtr ctxt, xmlDocPtr doc, const xmlChar *value,
2189          xmlAttrPtr attr) {
2190     xmlIDPtr ret;
2191     xmlIDTablePtr table;
2192
2193     if (doc == NULL) {
2194         xmlGenericError(xmlGenericErrorContext,
2195                 "xmlAddID: doc == NULL\n");
2196         return(NULL);
2197     }
2198     if (value == NULL) {
2199         xmlGenericError(xmlGenericErrorContext,
2200                 "xmlAddID: value == NULL\n");
2201         return(NULL);
2202     }
2203     if (attr == NULL) {
2204         xmlGenericError(xmlGenericErrorContext,
2205                 "xmlAddID: attr == NULL\n");
2206         return(NULL);
2207     }
2208
2209     /*
2210      * Create the ID table if needed.
2211      */
2212     table = (xmlIDTablePtr) doc->ids;
2213     if (table == NULL)
2214         doc->ids = table = xmlCreateIDTable();
2215     if (table == NULL) {
2216         xmlGenericError(xmlGenericErrorContext,
2217                 "xmlAddID: Table creation failed!\n");
2218         return(NULL);
2219     }
2220
2221     ret = (xmlIDPtr) xmlMalloc(sizeof(xmlID));
2222     if (ret == NULL) {
2223         xmlGenericError(xmlGenericErrorContext,
2224                 "xmlAddID: out of memory\n");
2225         return(NULL);
2226     }
2227
2228     /*
2229      * fill the structure.
2230      */
2231     ret->value = xmlStrdup(value);
2232     if ((ctxt != NULL) && (ctxt->vstateNr != 0)) {
2233         /*
2234          * Operating in streaming mode, attr is gonna disapear
2235          */
2236         ret->name = xmlStrdup(attr->name);
2237         ret->attr = NULL;
2238     } else {
2239         ret->attr = attr;
2240         ret->name = NULL;
2241     }
2242     ret->lineno = xmlGetLineNo(attr->parent);
2243
2244     if (xmlHashAddEntry(table, value, ret) < 0) {
2245         /*
2246          * The id is already defined in this DTD.
2247          */
2248         if (ctxt != NULL) {
2249             VECTXT(ctxt, attr->parent);
2250             VERROR(ctxt->userData, "ID %s already defined\n", value);
2251         }
2252         xmlFreeID(ret);
2253         return(NULL);
2254     }
2255     if (attr != NULL)
2256         attr->atype = XML_ATTRIBUTE_ID;
2257     return(ret);
2258 }
2259
2260 /**
2261  * xmlFreeIDTable:
2262  * @table:  An id table
2263  *
2264  * Deallocate the memory used by an ID hash table.
2265  */
2266 void
2267 xmlFreeIDTable(xmlIDTablePtr table) {
2268     xmlHashFree(table, (xmlHashDeallocator) xmlFreeID);
2269 }
2270
2271 /**
2272  * xmlIsID:
2273  * @doc:  the document
2274  * @elem:  the element carrying the attribute
2275  * @attr:  the attribute
2276  *
2277  * Determine whether an attribute is of type ID. In case we have DTD(s)
2278  * then this is done if DTD loading has been requested. In the case
2279  * of HTML documents parsed with the HTML parser, then ID detection is
2280  * done systematically.
2281  *
2282  * Returns 0 or 1 depending on the lookup result
2283  */
2284 int
2285 xmlIsID(xmlDocPtr doc, xmlNodePtr elem, xmlAttrPtr attr) {
2286     if (doc == NULL) return(0);
2287     if (attr == NULL) return(0);
2288     if ((doc->intSubset == NULL) && (doc->extSubset == NULL)) {
2289         return(0);
2290     } else if (doc->type == XML_HTML_DOCUMENT_NODE) {
2291         if ((xmlStrEqual(BAD_CAST "id", attr->name)) ||
2292             (xmlStrEqual(BAD_CAST "name", attr->name)))
2293             return(1);
2294         return(0);
2295     } else {
2296         xmlAttributePtr attrDecl;
2297
2298         if (elem == NULL) return(0);
2299         if ((elem->ns != NULL) && (elem->ns->prefix != NULL)) {
2300             xmlChar fn[50];
2301             xmlChar *fullname;
2302
2303             fullname = xmlBuildQName(elem->name, elem->ns->prefix, fn, 50);
2304             if (fullname == NULL)
2305                 return(0);
2306             attrDecl = xmlGetDtdAttrDesc(doc->intSubset, fullname,
2307                                          attr->name);
2308             if ((attrDecl == NULL) && (doc->extSubset != NULL))
2309                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset, fullname,
2310                                              attr->name);
2311             if ((fullname != fn) && (fullname != elem->name))
2312                 xmlFree(fullname);
2313         } else {
2314             attrDecl = xmlGetDtdAttrDesc(doc->intSubset, elem->name,
2315                                          attr->name);
2316             if ((attrDecl == NULL) && (doc->extSubset != NULL))
2317                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset, elem->name,
2318                                              attr->name);
2319         }
2320
2321         if ((attrDecl != NULL) && (attrDecl->atype == XML_ATTRIBUTE_ID))
2322             return(1);
2323     }
2324     return(0);
2325 }
2326
2327 /**
2328  * xmlRemoveID:
2329  * @doc:  the document
2330  * @attr:  the attribute
2331  *
2332  * Remove the given attribute from the ID table maintained internally.
2333  *
2334  * Returns -1 if the lookup failed and 0 otherwise
2335  */
2336 int
2337 xmlRemoveID(xmlDocPtr doc, xmlAttrPtr attr) {
2338     xmlAttrPtr cur;
2339     xmlIDTablePtr table;
2340     xmlChar *ID;
2341
2342     if (doc == NULL) return(-1);
2343     if (attr == NULL) return(-1);
2344     table = (xmlIDTablePtr) doc->ids;
2345     if (table == NULL)
2346         return(-1);
2347
2348     if (attr == NULL)
2349         return(-1);
2350     ID = xmlNodeListGetString(doc, attr->children, 1);
2351     if (ID == NULL)
2352         return(-1);
2353     cur = xmlHashLookup(table, ID);
2354     if (cur != attr) {
2355         xmlFree(ID);
2356         return(-1);
2357     }
2358     xmlHashUpdateEntry(table, ID, NULL, (xmlHashDeallocator) xmlFreeID);
2359     xmlFree(ID);
2360     return(0);
2361 }
2362
2363 /**
2364  * xmlGetID:
2365  * @doc:  pointer to the document
2366  * @ID:  the ID value
2367  *
2368  * Search the attribute declaring the given ID
2369  *
2370  * Returns NULL if not found, otherwise the xmlAttrPtr defining the ID
2371  */
2372 xmlAttrPtr
2373 xmlGetID(xmlDocPtr doc, const xmlChar *ID) {
2374     xmlIDTablePtr table;
2375     xmlIDPtr id;
2376
2377     if (doc == NULL) {
2378         xmlGenericError(xmlGenericErrorContext, "xmlGetID: doc == NULL\n");
2379         return(NULL);
2380     }
2381
2382     if (ID == NULL) {
2383         xmlGenericError(xmlGenericErrorContext, "xmlGetID: ID == NULL\n");
2384         return(NULL);
2385     }
2386
2387     table = (xmlIDTablePtr) doc->ids;
2388     if (table == NULL)
2389         return(NULL);
2390
2391     id = xmlHashLookup(table, ID);
2392     if (id == NULL)
2393         return(NULL);
2394     if (id->attr == NULL) {
2395         /*
2396          * We are operating on a stream, return a well known reference
2397          * since the attribute node doesn't exist anymore
2398          */
2399         return((xmlAttrPtr) doc);
2400     }
2401     return(id->attr);
2402 }
2403
2404 /************************************************************************
2405  *                                                                      *
2406  *                              Refs                                    *
2407  *                                                                      *
2408  ************************************************************************/
2409 typedef struct xmlRemoveMemo_t
2410 {
2411         xmlListPtr l;
2412         xmlAttrPtr ap;
2413 } xmlRemoveMemo;
2414
2415 typedef xmlRemoveMemo *xmlRemoveMemoPtr;
2416
2417 typedef struct xmlValidateMemo_t
2418 {
2419     xmlValidCtxtPtr ctxt;
2420     const xmlChar *name;
2421 } xmlValidateMemo;
2422
2423 typedef xmlValidateMemo *xmlValidateMemoPtr;
2424
2425 /**
2426  * xmlCreateRefTable:
2427  *
2428  * create and initialize an empty ref hash table.
2429  *
2430  * Returns the xmlRefTablePtr just created or NULL in case
2431  *                of error.
2432  */
2433 static xmlRefTablePtr
2434 xmlCreateRefTable(void) {
2435     return(xmlHashCreate(0));
2436 }
2437
2438 /**
2439  * xmlFreeRef:
2440  * @lk:  A list link
2441  *
2442  * Deallocate the memory used by a ref definition
2443  */
2444 static void
2445 xmlFreeRef(xmlLinkPtr lk) {
2446     xmlRefPtr ref = (xmlRefPtr)xmlLinkGetData(lk);
2447     if (ref == NULL) return;
2448     if (ref->value != NULL)
2449         xmlFree((xmlChar *)ref->value);
2450     if (ref->name != NULL)
2451         xmlFree((xmlChar *)ref->name);
2452     xmlFree(ref);
2453 }
2454
2455 /**
2456  * xmlFreeRefList:
2457  * @list_ref:  A list of references.
2458  *
2459  * Deallocate the memory used by a list of references
2460  */
2461 static void
2462 xmlFreeRefList(xmlListPtr list_ref) {
2463     if (list_ref == NULL) return;
2464     xmlListDelete(list_ref);
2465 }
2466
2467 /**
2468  * xmlWalkRemoveRef:
2469  * @data:  Contents of current link
2470  * @user:  Value supplied by the user
2471  *
2472  * Returns 0 to abort the walk or 1 to continue
2473  */
2474 static int
2475 xmlWalkRemoveRef(const void *data, const void *user)
2476 {
2477     xmlAttrPtr attr0 = ((xmlRefPtr)data)->attr;
2478     xmlAttrPtr attr1 = ((xmlRemoveMemoPtr)user)->ap;
2479     xmlListPtr ref_list = ((xmlRemoveMemoPtr)user)->l;
2480
2481     if (attr0 == attr1) { /* Matched: remove and terminate walk */
2482         xmlListRemoveFirst(ref_list, (void *)data);
2483         return 0;
2484     }
2485     return 1;
2486 }
2487
2488 /**
2489  * xmlAddRef:
2490  * @ctxt:  the validation context
2491  * @doc:  pointer to the document
2492  * @value:  the value name
2493  * @attr:  the attribute holding the Ref
2494  *
2495  * Register a new ref declaration
2496  *
2497  * Returns NULL if not, otherwise the new xmlRefPtr
2498  */
2499 xmlRefPtr
2500 xmlAddRef(xmlValidCtxtPtr ctxt ATTRIBUTE_UNUSED, xmlDocPtr doc, const xmlChar *value,
2501     xmlAttrPtr attr) {
2502     xmlRefPtr ret;
2503     xmlRefTablePtr table;
2504     xmlListPtr ref_list;
2505
2506     if (doc == NULL) {
2507         xmlGenericError(xmlGenericErrorContext,
2508             "xmlAddRef: doc == NULL\n");
2509         return(NULL);
2510     }
2511     if (value == NULL) {
2512         xmlGenericError(xmlGenericErrorContext,
2513             "xmlAddRef: value == NULL\n");
2514         return(NULL);
2515     }
2516     if (attr == NULL) {
2517         xmlGenericError(xmlGenericErrorContext,
2518             "xmlAddRef: attr == NULL\n");
2519         return(NULL);
2520     }
2521
2522     /*
2523      * Create the Ref table if needed.
2524      */
2525     table = (xmlRefTablePtr) doc->refs;
2526     if (table == NULL)
2527         doc->refs = table = xmlCreateRefTable();
2528     if (table == NULL) {
2529         xmlGenericError(xmlGenericErrorContext,
2530             "xmlAddRef: Table creation failed!\n");
2531         return(NULL);
2532     }
2533
2534     ret = (xmlRefPtr) xmlMalloc(sizeof(xmlRef));
2535     if (ret == NULL) {
2536         xmlGenericError(xmlGenericErrorContext,
2537             "xmlAddRef: out of memory\n");
2538         return(NULL);
2539     }
2540
2541     /*
2542      * fill the structure.
2543      */
2544     ret->value = xmlStrdup(value);
2545     if ((ctxt != NULL) && (ctxt->vstateNr != 0)) {
2546         /*
2547          * Operating in streaming mode, attr is gonna disapear
2548          */
2549         ret->name = xmlStrdup(attr->name);
2550         ret->attr = NULL;
2551     } else {
2552         ret->name = NULL;
2553         ret->attr = attr;
2554     }
2555     ret->lineno = xmlGetLineNo(attr->parent);
2556
2557     /* To add a reference :-
2558      * References are maintained as a list of references,
2559      * Lookup the entry, if no entry create new nodelist
2560      * Add the owning node to the NodeList
2561      * Return the ref
2562      */
2563
2564     if (NULL == (ref_list = xmlHashLookup(table, value))) {
2565         if (NULL == (ref_list = xmlListCreate(xmlFreeRef, NULL))) {
2566             xmlGenericError(xmlGenericErrorContext,
2567                 "xmlAddRef: Reference list creation failed!\n");
2568             return(NULL);
2569         }
2570         if (xmlHashAddEntry(table, value, ref_list) < 0) {
2571             xmlListDelete(ref_list);
2572             xmlGenericError(xmlGenericErrorContext,
2573                 "xmlAddRef: Reference list insertion failed!\n");
2574             return(NULL);
2575         }
2576     }
2577     xmlListInsert(ref_list, ret);
2578     return(ret);
2579 }
2580
2581 /**
2582  * xmlFreeRefTable:
2583  * @table:  An ref table
2584  *
2585  * Deallocate the memory used by an Ref hash table.
2586  */
2587 void
2588 xmlFreeRefTable(xmlRefTablePtr table) {
2589     xmlHashFree(table, (xmlHashDeallocator) xmlFreeRefList);
2590 }
2591
2592 /**
2593  * xmlIsRef:
2594  * @doc:  the document
2595  * @elem:  the element carrying the attribute
2596  * @attr:  the attribute
2597  *
2598  * Determine whether an attribute is of type Ref. In case we have DTD(s)
2599  * then this is simple, otherwise we use an heuristic: name Ref (upper
2600  * or lowercase).
2601  *
2602  * Returns 0 or 1 depending on the lookup result
2603  */
2604 int
2605 xmlIsRef(xmlDocPtr doc, xmlNodePtr elem, xmlAttrPtr attr) {
2606     if ((doc->intSubset == NULL) && (doc->extSubset == NULL)) {
2607         return(0);
2608     } else if (doc->type == XML_HTML_DOCUMENT_NODE) {
2609         /* TODO @@@ */
2610         return(0);
2611     } else {
2612         xmlAttributePtr attrDecl;
2613
2614         attrDecl = xmlGetDtdAttrDesc(doc->intSubset, elem->name, attr->name);
2615         if ((attrDecl == NULL) && (doc->extSubset != NULL))
2616             attrDecl = xmlGetDtdAttrDesc(doc->extSubset,
2617                                          elem->name, attr->name);
2618
2619         if ((attrDecl != NULL) &&
2620             (attrDecl->atype == XML_ATTRIBUTE_IDREF ||
2621              attrDecl->atype == XML_ATTRIBUTE_IDREFS))
2622         return(1);
2623     }
2624     return(0);
2625 }
2626
2627 /**
2628  * xmlRemoveRef:
2629  * @doc:  the document
2630  * @attr:  the attribute
2631  *
2632  * Remove the given attribute from the Ref table maintained internally.
2633  *
2634  * Returns -1 if the lookup failed and 0 otherwise
2635  */
2636 int
2637 xmlRemoveRef(xmlDocPtr doc, xmlAttrPtr attr) {
2638     xmlListPtr ref_list;
2639     xmlRefTablePtr table;
2640     xmlChar *ID;
2641     xmlRemoveMemo target;
2642
2643     if (doc == NULL) return(-1);
2644     if (attr == NULL) return(-1);
2645     table = (xmlRefTablePtr) doc->refs;
2646     if (table == NULL)
2647         return(-1);
2648
2649     if (attr == NULL)
2650         return(-1);
2651     ID = xmlNodeListGetString(doc, attr->children, 1);
2652     if (ID == NULL)
2653         return(-1);
2654     ref_list = xmlHashLookup(table, ID);
2655
2656     if(ref_list == NULL) {
2657         xmlFree(ID);
2658         return (-1);
2659     }
2660     /* At this point, ref_list refers to a list of references which
2661      * have the same key as the supplied attr. Our list of references
2662      * is ordered by reference address and we don't have that information
2663      * here to use when removing. We'll have to walk the list and
2664      * check for a matching attribute, when we find one stop the walk
2665      * and remove the entry.
2666      * The list is ordered by reference, so that means we don't have the
2667      * key. Passing the list and the reference to the walker means we
2668      * will have enough data to be able to remove the entry.
2669      */
2670     target.l = ref_list;
2671     target.ap = attr;
2672
2673     /* Remove the supplied attr from our list */
2674     xmlListWalk(ref_list, xmlWalkRemoveRef, &target);
2675
2676     /*If the list is empty then remove the list entry in the hash */
2677     if (xmlListEmpty(ref_list))
2678         xmlHashUpdateEntry(table, ID, NULL, (xmlHashDeallocator)
2679         xmlFreeRefList);
2680     xmlFree(ID);
2681     return(0);
2682 }
2683
2684 /**
2685  * xmlGetRefs:
2686  * @doc:  pointer to the document
2687  * @ID:  the ID value
2688  *
2689  * Find the set of references for the supplied ID.
2690  *
2691  * Returns NULL if not found, otherwise node set for the ID.
2692  */
2693 xmlListPtr
2694 xmlGetRefs(xmlDocPtr doc, const xmlChar *ID) {
2695     xmlRefTablePtr table;
2696
2697     if (doc == NULL) {
2698         xmlGenericError(xmlGenericErrorContext, "xmlGetRefs: doc == NULL\n");
2699         return(NULL);
2700     }
2701
2702     if (ID == NULL) {
2703         xmlGenericError(xmlGenericErrorContext, "xmlGetRefs: ID == NULL\n");
2704         return(NULL);
2705     }
2706
2707     table = (xmlRefTablePtr) doc->refs;
2708     if (table == NULL)
2709         return(NULL);
2710
2711     return (xmlHashLookup(table, ID));
2712 }
2713
2714 /************************************************************************
2715  *                                                                      *
2716  *              Routines for validity checking                          *
2717  *                                                                      *
2718  ************************************************************************/
2719
2720 /**
2721  * xmlGetDtdElementDesc:
2722  * @dtd:  a pointer to the DtD to search
2723  * @name:  the element name
2724  *
2725  * Search the DTD for the description of this element
2726  *
2727  * returns the xmlElementPtr if found or NULL
2728  */
2729
2730 xmlElementPtr
2731 xmlGetDtdElementDesc(xmlDtdPtr dtd, const xmlChar *name) {
2732     xmlElementTablePtr table;
2733     xmlElementPtr cur;
2734     xmlChar *uqname = NULL, *prefix = NULL;
2735
2736     if ((dtd == NULL) || (name == NULL)) return(NULL);
2737     if (dtd->elements == NULL)
2738         return(NULL);
2739     table = (xmlElementTablePtr) dtd->elements;
2740
2741     uqname = xmlSplitQName2(name, &prefix);
2742     if (uqname != NULL)
2743         name = uqname;
2744     cur = xmlHashLookup2(table, name, prefix);
2745     if (prefix != NULL) xmlFree(prefix);
2746     if (uqname != NULL) xmlFree(uqname);
2747     return(cur);
2748 }
2749 /**
2750  * xmlGetDtdElementDesc2:
2751  * @dtd:  a pointer to the DtD to search
2752  * @name:  the element name
2753  * @create:  create an empty description if not found
2754  *
2755  * Search the DTD for the description of this element
2756  *
2757  * returns the xmlElementPtr if found or NULL
2758  */
2759
2760 static xmlElementPtr
2761 xmlGetDtdElementDesc2(xmlDtdPtr dtd, const xmlChar *name, int create) {
2762     xmlElementTablePtr table;
2763     xmlElementPtr cur;
2764     xmlChar *uqname = NULL, *prefix = NULL;
2765
2766     if (dtd == NULL) return(NULL);
2767     if (dtd->elements == NULL) {
2768         if (!create)
2769             return(NULL);
2770         /*
2771          * Create the Element table if needed.
2772          */
2773         table = (xmlElementTablePtr) dtd->elements;
2774         if (table == NULL) {
2775             table = xmlCreateElementTable();
2776             dtd->elements = (void *) table;
2777         }
2778         if (table == NULL) {
2779             xmlGenericError(xmlGenericErrorContext,
2780                     "xmlGetDtdElementDesc2: Table creation failed!\n");
2781             return(NULL);
2782         }
2783     }
2784     table = (xmlElementTablePtr) dtd->elements;
2785
2786     uqname = xmlSplitQName2(name, &prefix);
2787     if (uqname != NULL)
2788         name = uqname;
2789     cur = xmlHashLookup2(table, name, prefix);
2790     if ((cur == NULL) && (create)) {
2791         cur = (xmlElementPtr) xmlMalloc(sizeof(xmlElement));
2792         if (cur == NULL) {
2793             xmlGenericError(xmlGenericErrorContext,
2794                     "xmlGetDtdElementDesc2: out of memory\n");
2795             return(NULL);
2796         }
2797         memset(cur, 0, sizeof(xmlElement));
2798         cur->type = XML_ELEMENT_DECL;
2799
2800         /*
2801          * fill the structure.
2802          */
2803         cur->name = xmlStrdup(name);
2804         cur->prefix = xmlStrdup(prefix);
2805         cur->etype = XML_ELEMENT_TYPE_UNDEFINED;
2806
2807         xmlHashAddEntry2(table, name, prefix, cur);
2808     }
2809     if (prefix != NULL) xmlFree(prefix);
2810     if (uqname != NULL) xmlFree(uqname);
2811     return(cur);
2812 }
2813
2814 /**
2815  * xmlGetDtdQElementDesc:
2816  * @dtd:  a pointer to the DtD to search
2817  * @name:  the element name
2818  * @prefix:  the element namespace prefix
2819  *
2820  * Search the DTD for the description of this element
2821  *
2822  * returns the xmlElementPtr if found or NULL
2823  */
2824
2825 xmlElementPtr
2826 xmlGetDtdQElementDesc(xmlDtdPtr dtd, const xmlChar *name,
2827                       const xmlChar *prefix) {
2828     xmlElementTablePtr table;
2829
2830     if (dtd == NULL) return(NULL);
2831     if (dtd->elements == NULL) return(NULL);
2832     table = (xmlElementTablePtr) dtd->elements;
2833
2834     return(xmlHashLookup2(table, name, prefix));
2835 }
2836
2837 /**
2838  * xmlGetDtdAttrDesc:
2839  * @dtd:  a pointer to the DtD to search
2840  * @elem:  the element name
2841  * @name:  the attribute name
2842  *
2843  * Search the DTD for the description of this attribute on
2844  * this element.
2845  *
2846  * returns the xmlAttributePtr if found or NULL
2847  */
2848
2849 xmlAttributePtr
2850 xmlGetDtdAttrDesc(xmlDtdPtr dtd, const xmlChar *elem, const xmlChar *name) {
2851     xmlAttributeTablePtr table;
2852     xmlAttributePtr cur;
2853     xmlChar *uqname = NULL, *prefix = NULL;
2854
2855     if (dtd == NULL) return(NULL);
2856     if (dtd->attributes == NULL) return(NULL);
2857
2858     table = (xmlAttributeTablePtr) dtd->attributes;
2859     if (table == NULL)
2860         return(NULL);
2861
2862     uqname = xmlSplitQName2(name, &prefix);
2863
2864     if (uqname != NULL) {
2865         cur = xmlHashLookup3(table, uqname, prefix, elem);
2866         if (prefix != NULL) xmlFree(prefix);
2867         if (uqname != NULL) xmlFree(uqname);
2868     } else
2869         cur = xmlHashLookup3(table, name, NULL, elem);
2870     return(cur);
2871 }
2872
2873 /**
2874  * xmlGetDtdQAttrDesc:
2875  * @dtd:  a pointer to the DtD to search
2876  * @elem:  the element name
2877  * @name:  the attribute name
2878  * @prefix:  the attribute namespace prefix
2879  *
2880  * Search the DTD for the description of this qualified attribute on
2881  * this element.
2882  *
2883  * returns the xmlAttributePtr if found or NULL
2884  */
2885
2886 xmlAttributePtr
2887 xmlGetDtdQAttrDesc(xmlDtdPtr dtd, const xmlChar *elem, const xmlChar *name,
2888                   const xmlChar *prefix) {
2889     xmlAttributeTablePtr table;
2890
2891     if (dtd == NULL) return(NULL);
2892     if (dtd->attributes == NULL) return(NULL);
2893     table = (xmlAttributeTablePtr) dtd->attributes;
2894
2895     return(xmlHashLookup3(table, name, prefix, elem));
2896 }
2897
2898 /**
2899  * xmlGetDtdNotationDesc:
2900  * @dtd:  a pointer to the DtD to search
2901  * @name:  the notation name
2902  *
2903  * Search the DTD for the description of this notation
2904  *
2905  * returns the xmlNotationPtr if found or NULL
2906  */
2907
2908 xmlNotationPtr
2909 xmlGetDtdNotationDesc(xmlDtdPtr dtd, const xmlChar *name) {
2910     xmlNotationTablePtr table;
2911
2912     if (dtd == NULL) return(NULL);
2913     if (dtd->notations == NULL) return(NULL);
2914     table = (xmlNotationTablePtr) dtd->notations;
2915
2916     return(xmlHashLookup(table, name));
2917 }
2918
2919 /**
2920  * xmlValidateNotationUse:
2921  * @ctxt:  the validation context
2922  * @doc:  the document
2923  * @notationName:  the notation name to check
2924  *
2925  * Validate that the given name match a notation declaration.
2926  * - [ VC: Notation Declared ]
2927  *
2928  * returns 1 if valid or 0 otherwise
2929  */
2930
2931 int
2932 xmlValidateNotationUse(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
2933                        const xmlChar *notationName) {
2934     xmlNotationPtr notaDecl;
2935     if ((doc == NULL) || (doc->intSubset == NULL)) return(-1);
2936
2937     notaDecl = xmlGetDtdNotationDesc(doc->intSubset, notationName);
2938     if ((notaDecl == NULL) && (doc->extSubset != NULL))
2939         notaDecl = xmlGetDtdNotationDesc(doc->extSubset, notationName);
2940
2941     if ((notaDecl == NULL) && (ctxt != NULL)) {
2942         VERROR(ctxt->userData, "NOTATION %s is not declared\n",
2943                notationName);
2944         return(0);
2945     }
2946     return(1);
2947 }
2948
2949 /**
2950  * xmlIsMixedElement:
2951  * @doc:  the document
2952  * @name:  the element name
2953  *
2954  * Search in the DtDs whether an element accept Mixed content (or ANY)
2955  * basically if it is supposed to accept text childs
2956  *
2957  * returns 0 if no, 1 if yes, and -1 if no element description is available
2958  */
2959
2960 int
2961 xmlIsMixedElement(xmlDocPtr doc, const xmlChar *name) {
2962     xmlElementPtr elemDecl;
2963
2964     if ((doc == NULL) || (doc->intSubset == NULL)) return(-1);
2965
2966     elemDecl = xmlGetDtdElementDesc(doc->intSubset, name);
2967     if ((elemDecl == NULL) && (doc->extSubset != NULL))
2968         elemDecl = xmlGetDtdElementDesc(doc->extSubset, name);
2969     if (elemDecl == NULL) return(-1);
2970     switch (elemDecl->etype) {
2971         case XML_ELEMENT_TYPE_UNDEFINED:
2972             return(-1);
2973         case XML_ELEMENT_TYPE_ELEMENT:
2974             return(0);
2975         case XML_ELEMENT_TYPE_EMPTY:
2976             /*
2977              * return 1 for EMPTY since we want VC error to pop up
2978              * on <empty>     </empty> for example
2979              */
2980         case XML_ELEMENT_TYPE_ANY:
2981         case XML_ELEMENT_TYPE_MIXED:
2982             return(1);
2983     }
2984     return(1);
2985 }
2986
2987 /**
2988  * xmlValidateNameValue:
2989  * @value:  an Name value
2990  *
2991  * Validate that the given value match Name production
2992  *
2993  * returns 1 if valid or 0 otherwise
2994  */
2995
2996 int
2997 xmlValidateNameValue(const xmlChar *value) {
2998     const xmlChar *cur;
2999     int val, len;
3000
3001     if (value == NULL) return(0);
3002     cur = value;
3003     val = xmlStringCurrentChar(NULL, cur, &len);
3004     cur += len;
3005     if (!IS_LETTER(val) && (val != '_') &&
3006         (val != ':')) {
3007         return(0);
3008     }
3009
3010     val = xmlStringCurrentChar(NULL, cur, &len);
3011     cur += len;
3012     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
3013            (val == '.') || (val == '-') ||
3014            (val == '_') || (val == ':') ||
3015            (IS_COMBINING(val)) ||
3016            (IS_EXTENDER(val))) {
3017         val = xmlStringCurrentChar(NULL, cur, &len);
3018         cur += len;
3019     }
3020
3021     if (val != 0) return(0);
3022
3023     return(1);
3024 }
3025
3026 /**
3027  * xmlValidateNamesValue:
3028  * @value:  an Names value
3029  *
3030  * Validate that the given value match Names production
3031  *
3032  * returns 1 if valid or 0 otherwise
3033  */
3034
3035 int
3036 xmlValidateNamesValue(const xmlChar *value) {
3037     const xmlChar *cur;
3038     int val, len;
3039
3040     if (value == NULL) return(0);
3041     cur = value;
3042     val = xmlStringCurrentChar(NULL, cur, &len);
3043     cur += len;
3044
3045     if (!IS_LETTER(val) && (val != '_') &&
3046         (val != ':')) {
3047         return(0);
3048     }
3049
3050     val = xmlStringCurrentChar(NULL, cur, &len);
3051     cur += len;
3052     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
3053            (val == '.') || (val == '-') ||
3054            (val == '_') || (val == ':') ||
3055            (IS_COMBINING(val)) ||
3056            (IS_EXTENDER(val))) {
3057         val = xmlStringCurrentChar(NULL, cur, &len);
3058         cur += len;
3059     }
3060
3061     while (IS_BLANK(val)) {
3062         while (IS_BLANK(val)) {
3063             val = xmlStringCurrentChar(NULL, cur, &len);
3064             cur += len;
3065         }
3066
3067         if (!IS_LETTER(val) && (val != '_') &&
3068             (val != ':')) {
3069             return(0);
3070         }
3071         val = xmlStringCurrentChar(NULL, cur, &len);
3072         cur += len;
3073
3074         while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
3075                (val == '.') || (val == '-') ||
3076                (val == '_') || (val == ':') ||
3077                (IS_COMBINING(val)) ||
3078                (IS_EXTENDER(val))) {
3079             val = xmlStringCurrentChar(NULL, cur, &len);
3080             cur += len;
3081         }
3082     }
3083
3084     if (val != 0) return(0);
3085
3086     return(1);
3087 }
3088
3089 /**
3090  * xmlValidateNmtokenValue:
3091  * @value:  an Nmtoken value
3092  *
3093  * Validate that the given value match Nmtoken production
3094  *
3095  * [ VC: Name Token ]
3096  *
3097  * returns 1 if valid or 0 otherwise
3098  */
3099
3100 int
3101 xmlValidateNmtokenValue(const xmlChar *value) {
3102     const xmlChar *cur;
3103     int val, len;
3104
3105     if (value == NULL) return(0);
3106     cur = value;
3107     val = xmlStringCurrentChar(NULL, cur, &len);
3108     cur += len;
3109
3110     if (!IS_LETTER(val) && !IS_DIGIT(val) &&
3111         (val != '.') && (val != '-') &&
3112         (val != '_') && (val != ':') &&
3113         (!IS_COMBINING(val)) &&
3114         (!IS_EXTENDER(val)))
3115         return(0);
3116
3117     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
3118            (val == '.') || (val == '-') ||
3119            (val == '_') || (val == ':') ||
3120            (IS_COMBINING(val)) ||
3121            (IS_EXTENDER(val))) {
3122         val = xmlStringCurrentChar(NULL, cur, &len);
3123         cur += len;
3124     }
3125
3126     if (val != 0) return(0);
3127
3128     return(1);
3129 }
3130
3131 /**
3132  * xmlValidateNmtokensValue:
3133  * @value:  an Nmtokens value
3134  *
3135  * Validate that the given value match Nmtokens production
3136  *
3137  * [ VC: Name Token ]
3138  *
3139  * returns 1 if valid or 0 otherwise
3140  */
3141
3142 int
3143 xmlValidateNmtokensValue(const xmlChar *value) {
3144     const xmlChar *cur;
3145     int val, len;
3146
3147     if (value == NULL) return(0);
3148     cur = value;
3149     val = xmlStringCurrentChar(NULL, cur, &len);
3150     cur += len;
3151
3152     while (IS_BLANK(val)) {
3153         val = xmlStringCurrentChar(NULL, cur, &len);
3154         cur += len;
3155     }
3156
3157     if (!IS_LETTER(val) && !IS_DIGIT(val) &&
3158         (val != '.') && (val != '-') &&
3159         (val != '_') && (val != ':') &&
3160         (!IS_COMBINING(val)) &&
3161         (!IS_EXTENDER(val)))
3162         return(0);
3163
3164     while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
3165            (val == '.') || (val == '-') ||
3166            (val == '_') || (val == ':') ||
3167            (IS_COMBINING(val)) ||
3168            (IS_EXTENDER(val))) {
3169         val = xmlStringCurrentChar(NULL, cur, &len);
3170         cur += len;
3171     }
3172
3173     while (IS_BLANK(val)) {
3174         while (IS_BLANK(val)) {
3175             val = xmlStringCurrentChar(NULL, cur, &len);
3176             cur += len;
3177         }
3178         if (val == 0) return(1);
3179
3180         if (!IS_LETTER(val) && !IS_DIGIT(val) &&
3181             (val != '.') && (val != '-') &&
3182             (val != '_') && (val != ':') &&
3183             (!IS_COMBINING(val)) &&
3184             (!IS_EXTENDER(val)))
3185             return(0);
3186
3187         while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
3188                (val == '.') || (val == '-') ||
3189                (val == '_') || (val == ':') ||
3190                (IS_COMBINING(val)) ||
3191                (IS_EXTENDER(val))) {
3192             val = xmlStringCurrentChar(NULL, cur, &len);
3193             cur += len;
3194         }
3195     }
3196
3197     if (val != 0) return(0);
3198
3199     return(1);
3200 }
3201
3202 /**
3203  * xmlValidateNotationDecl:
3204  * @ctxt:  the validation context
3205  * @doc:  a document instance
3206  * @nota:  a notation definition
3207  *
3208  * Try to validate a single notation definition
3209  * basically it does the following checks as described by the
3210  * XML-1.0 recommendation:
3211  *  - it seems that no validity constraint exists on notation declarations
3212  * But this function get called anyway ...
3213  *
3214  * returns 1 if valid or 0 otherwise
3215  */
3216
3217 int
3218 xmlValidateNotationDecl(xmlValidCtxtPtr ctxt ATTRIBUTE_UNUSED, xmlDocPtr doc ATTRIBUTE_UNUSED,
3219                          xmlNotationPtr nota ATTRIBUTE_UNUSED) {
3220     int ret = 1;
3221
3222     return(ret);
3223 }
3224
3225 /**
3226  * xmlValidateAttributeValue:
3227  * @type:  an attribute type
3228  * @value:  an attribute value
3229  *
3230  * Validate that the given attribute value match  the proper production
3231  *
3232  * [ VC: ID ]
3233  * Values of type ID must match the Name production....
3234  *
3235  * [ VC: IDREF ]
3236  * Values of type IDREF must match the Name production, and values
3237  * of type IDREFS must match Names ...
3238  *
3239  * [ VC: Entity Name ]
3240  * Values of type ENTITY must match the Name production, values
3241  * of type ENTITIES must match Names ...
3242  *
3243  * [ VC: Name Token ]
3244  * Values of type NMTOKEN must match the Nmtoken production; values
3245  * of type NMTOKENS must match Nmtokens.
3246  *
3247  * returns 1 if valid or 0 otherwise
3248  */
3249
3250 int
3251 xmlValidateAttributeValue(xmlAttributeType type, const xmlChar *value) {
3252     switch (type) {
3253         case XML_ATTRIBUTE_ENTITIES:
3254         case XML_ATTRIBUTE_IDREFS:
3255             return(xmlValidateNamesValue(value));
3256         case XML_ATTRIBUTE_ENTITY:
3257         case XML_ATTRIBUTE_IDREF:
3258         case XML_ATTRIBUTE_ID:
3259         case XML_ATTRIBUTE_NOTATION:
3260             return(xmlValidateNameValue(value));
3261         case XML_ATTRIBUTE_NMTOKENS:
3262         case XML_ATTRIBUTE_ENUMERATION:
3263             return(xmlValidateNmtokensValue(value));
3264         case XML_ATTRIBUTE_NMTOKEN:
3265             return(xmlValidateNmtokenValue(value));
3266         case XML_ATTRIBUTE_CDATA:
3267             break;
3268     }
3269     return(1);
3270 }
3271
3272 /**
3273  * xmlValidateAttributeValue2:
3274  * @ctxt:  the validation context
3275  * @doc:  the document
3276  * @name:  the attribute name (used for error reporting only)
3277  * @type:  the attribute type
3278  * @value:  the attribute value
3279  *
3280  * Validate that the given attribute value match a given type.
3281  * This typically cannot be done before having finished parsing
3282  * the subsets.
3283  *
3284  * [ VC: IDREF ]
3285  * Values of type IDREF must match one of the declared IDs
3286  * Values of type IDREFS must match a sequence of the declared IDs
3287  * each Name must match the value of an ID attribute on some element
3288  * in the XML document; i.e. IDREF values must match the value of
3289  * some ID attribute
3290  *
3291  * [ VC: Entity Name ]
3292  * Values of type ENTITY must match one declared entity
3293  * Values of type ENTITIES must match a sequence of declared entities
3294  *
3295  * [ VC: Notation Attributes ]
3296  * all notation names in the declaration must be declared.
3297  *
3298  * returns 1 if valid or 0 otherwise
3299  */
3300
3301 static int
3302 xmlValidateAttributeValue2(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
3303       const xmlChar *name, xmlAttributeType type, const xmlChar *value) {
3304     int ret = 1;
3305     switch (type) {
3306         case XML_ATTRIBUTE_IDREFS:
3307         case XML_ATTRIBUTE_IDREF:
3308         case XML_ATTRIBUTE_ID:
3309         case XML_ATTRIBUTE_NMTOKENS:
3310         case XML_ATTRIBUTE_ENUMERATION:
3311         case XML_ATTRIBUTE_NMTOKEN:
3312         case XML_ATTRIBUTE_CDATA:
3313             break;
3314         case XML_ATTRIBUTE_ENTITY: {
3315             xmlEntityPtr ent;
3316
3317             ent = xmlGetDocEntity(doc, value);
3318             if ((ent == NULL) && (doc->standalone == 1)) {
3319                 doc->standalone = 0;
3320                 ent = xmlGetDocEntity(doc, value);
3321                 if (ent != NULL) {
3322                     VERROR(ctxt->userData,
3323 "standalone problem: attribute %s reference entity \"%s\" in external subset\n",
3324                            name, value);
3325                     /* WAIT to get answer from the Core WG on this
3326                     ret = 0;
3327                      */
3328                 }
3329             }
3330             if (ent == NULL) {
3331                 VERROR(ctxt->userData,
3332    "ENTITY attribute %s reference an unknown entity \"%s\"\n",
3333                        name, value);
3334                 ret = 0;
3335             } else if (ent->etype != XML_EXTERNAL_GENERAL_UNPARSED_ENTITY) {
3336                 VERROR(ctxt->userData,
3337    "ENTITY attribute %s reference an entity \"%s\" of wrong type\n",
3338                        name, value);
3339                 ret = 0;
3340             }
3341             break;
3342         }
3343         case XML_ATTRIBUTE_ENTITIES: {
3344             xmlChar *dup, *nam = NULL, *cur, save;
3345             xmlEntityPtr ent;
3346
3347             dup = xmlStrdup(value);
3348             if (dup == NULL)
3349                 return(0);
3350             cur = dup;
3351             while (*cur != 0) {
3352                 nam = cur;
3353                 while ((*cur != 0) && (!IS_BLANK(*cur))) cur++;
3354                 save = *cur;
3355                 *cur = 0;
3356                 ent = xmlGetDocEntity(doc, nam);
3357                 if (ent == NULL) {
3358                     VERROR(ctxt->userData,
3359        "ENTITIES attribute %s reference an unknown entity \"%s\"\n",
3360                            name, nam);
3361                     ret = 0;
3362                 } else if (ent->etype != XML_EXTERNAL_GENERAL_UNPARSED_ENTITY) {
3363                     VERROR(ctxt->userData,
3364        "ENTITIES attribute %s reference an entity \"%s\" of wrong type\n",
3365                            name, nam);
3366                     ret = 0;
3367                 }
3368                 if (save == 0)
3369                     break;
3370                 *cur = save;
3371                 while (IS_BLANK(*cur)) cur++;
3372             }
3373             xmlFree(dup);
3374             break;
3375         }
3376         case XML_ATTRIBUTE_NOTATION: {
3377             xmlNotationPtr nota;
3378
3379             nota = xmlGetDtdNotationDesc(doc->intSubset, value);
3380             if ((nota == NULL) && (doc->extSubset != NULL))
3381                 nota = xmlGetDtdNotationDesc(doc->extSubset, value);
3382
3383             if (nota == NULL) {
3384                 VERROR(ctxt->userData,
3385        "NOTATION attribute %s reference an unknown notation \"%s\"\n",
3386                        name, value);
3387                 ret = 0;
3388             }
3389             break;
3390         }
3391     }
3392     return(ret);
3393 }
3394
3395 /**
3396  * xmlValidCtxtNormalizeAttributeValue:
3397  * @ctxt: the validation context
3398  * @doc:  the document
3399  * @elem:  the parent
3400  * @name:  the attribute name
3401  * @value:  the attribute value
3402  * @ctxt:  the validation context or NULL
3403  *
3404  * Does the validation related extra step of the normalization of attribute
3405  * values:
3406  *
3407  * If the declared value is not CDATA, then the XML processor must further
3408  * process the normalized attribute value by discarding any leading and
3409  * trailing space (#x20) characters, and by replacing sequences of space
3410  * (#x20) characters by single space (#x20) character.
3411  *
3412  * Also  check VC: Standalone Document Declaration in P32, and update
3413  *  ctxt->valid accordingly
3414  *
3415  * returns a new normalized string if normalization is needed, NULL otherwise
3416  *      the caller must free the returned value.
3417  */
3418
3419 xmlChar *
3420 xmlValidCtxtNormalizeAttributeValue(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
3421              xmlNodePtr elem, const xmlChar *name, const xmlChar *value) {
3422     xmlChar *ret, *dst;
3423     const xmlChar *src;
3424     xmlAttributePtr attrDecl = NULL;
3425     int extsubset = 0;
3426
3427     if (doc == NULL) return(NULL);
3428     if (elem == NULL) return(NULL);
3429     if (name == NULL) return(NULL);
3430     if (value == NULL) return(NULL);
3431
3432     if ((elem->ns != NULL) && (elem->ns->prefix != NULL)) {
3433         xmlChar fn[50];
3434         xmlChar *fullname;
3435
3436         fullname = xmlBuildQName(elem->name, elem->ns->prefix, fn, 50);
3437         if (fullname == NULL)
3438             return(0);
3439         attrDecl = xmlGetDtdAttrDesc(doc->intSubset, fullname, name);
3440         if ((attrDecl == NULL) && (doc->extSubset != NULL)) {
3441             attrDecl = xmlGetDtdAttrDesc(doc->extSubset, fullname, name);
3442             if (attrDecl != NULL)
3443                 extsubset = 1;
3444         }
3445         if ((fullname != fn) && (fullname != elem->name))
3446             xmlFree(fullname);
3447     }
3448     if ((attrDecl == NULL) && (doc->intSubset != NULL))
3449         attrDecl = xmlGetDtdAttrDesc(doc->intSubset, elem->name, name);
3450     if ((attrDecl == NULL) && (doc->extSubset != NULL)) {
3451         attrDecl = xmlGetDtdAttrDesc(doc->extSubset, elem->name, name);
3452         if (attrDecl != NULL)
3453             extsubset = 1;
3454     }
3455
3456     if (attrDecl == NULL)
3457         return(NULL);
3458     if (attrDecl->atype == XML_ATTRIBUTE_CDATA)
3459         return(NULL);
3460
3461     ret = xmlStrdup(value);
3462     if (ret == NULL)
3463         return(NULL);
3464     src = value;
3465     dst = ret;
3466     while (*src == 0x20) src++;
3467     while (*src != 0) {
3468         if (*src == 0x20) {
3469             while (*src == 0x20) src++;
3470             if (*src != 0)
3471                 *dst++ = 0x20;
3472         } else {
3473             *dst++ = *src++;
3474         }
3475     }
3476     *dst = 0;
3477     if ((doc->standalone) && (extsubset == 1) && (!xmlStrEqual(value, ret))) {
3478         VERROR(ctxt->userData,
3479 "standalone: %s on %s value had to be normalized based on external subset declaration\n",
3480                name, elem->name);
3481         ctxt->valid = 0;
3482     }
3483     return(ret);
3484 }
3485
3486 /**
3487  * xmlValidNormalizeAttributeValue:
3488  * @doc:  the document
3489  * @elem:  the parent
3490  * @name:  the attribute name
3491  * @value:  the attribute value
3492  *
3493  * Does the validation related extra step of the normalization of attribute
3494  * values:
3495  *
3496  * If the declared value is not CDATA, then the XML processor must further
3497  * process the normalized attribute value by discarding any leading and
3498  * trailing space (#x20) characters, and by replacing sequences of space
3499  * (#x20) characters by single space (#x20) character.
3500  *
3501  * returns a new normalized string if normalization is needed, NULL otherwise
3502  *      the caller must free the returned value.
3503  */
3504
3505 xmlChar *
3506 xmlValidNormalizeAttributeValue(xmlDocPtr doc, xmlNodePtr elem,
3507                                 const xmlChar *name, const xmlChar *value) {
3508     xmlChar *ret, *dst;
3509     const xmlChar *src;
3510     xmlAttributePtr attrDecl = NULL;
3511
3512     if (doc == NULL) return(NULL);
3513     if (elem == NULL) return(NULL);
3514     if (name == NULL) return(NULL);
3515     if (value == NULL) return(NULL);
3516
3517     if ((elem->ns != NULL) && (elem->ns->prefix != NULL)) {
3518         xmlChar fn[50];
3519         xmlChar *fullname;
3520
3521         fullname = xmlBuildQName(elem->name, elem->ns->prefix, fn, 50);
3522         if (fullname == NULL)
3523             return(0);
3524         attrDecl = xmlGetDtdAttrDesc(doc->intSubset, fullname, name);
3525         if ((attrDecl == NULL) && (doc->extSubset != NULL))
3526             attrDecl = xmlGetDtdAttrDesc(doc->extSubset, fullname, name);
3527         if ((fullname != fn) && (fullname != elem->name))
3528             xmlFree(fullname);
3529     }
3530     attrDecl = xmlGetDtdAttrDesc(doc->intSubset, elem->name, name);
3531     if ((attrDecl == NULL) && (doc->extSubset != NULL))
3532         attrDecl = xmlGetDtdAttrDesc(doc->extSubset, elem->name, name);
3533
3534     if (attrDecl == NULL)
3535         return(NULL);
3536     if (attrDecl->atype == XML_ATTRIBUTE_CDATA)
3537         return(NULL);
3538
3539     ret = xmlStrdup(value);
3540     if (ret == NULL)
3541         return(NULL);
3542     src = value;
3543     dst = ret;
3544     while (*src == 0x20) src++;
3545     while (*src != 0) {
3546         if (*src == 0x20) {
3547             while (*src == 0x20) src++;
3548             if (*src != 0)
3549                 *dst++ = 0x20;
3550         } else {
3551             *dst++ = *src++;
3552         }
3553     }
3554     *dst = 0;
3555     return(ret);
3556 }
3557
3558 static void
3559 xmlValidateAttributeIdCallback(xmlAttributePtr attr, int *count,
3560                                const xmlChar* name ATTRIBUTE_UNUSED) {
3561     if (attr->atype == XML_ATTRIBUTE_ID) (*count)++;
3562 }
3563
3564 /**
3565  * xmlValidateAttributeDecl:
3566  * @ctxt:  the validation context
3567  * @doc:  a document instance
3568  * @attr:  an attribute definition
3569  *
3570  * Try to validate a single attribute definition
3571  * basically it does the following checks as described by the
3572  * XML-1.0 recommendation:
3573  *  - [ VC: Attribute Default Legal ]
3574  *  - [ VC: Enumeration ]
3575  *  - [ VC: ID Attribute Default ]
3576  *
3577  * The ID/IDREF uniqueness and matching are done separately
3578  *
3579  * returns 1 if valid or 0 otherwise
3580  */
3581
3582 int
3583 xmlValidateAttributeDecl(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
3584                          xmlAttributePtr attr) {
3585     int ret = 1;
3586     int val;
3587     CHECK_DTD;
3588     if(attr == NULL) return(1);
3589
3590     /* Attribute Default Legal */
3591     /* Enumeration */
3592     if (attr->defaultValue != NULL) {
3593         val = xmlValidateAttributeValue(attr->atype, attr->defaultValue);
3594         if (val == 0) {
3595             VERROR(ctxt->userData,
3596                "Syntax of default value for attribute %s of %s is not valid\n",
3597                    attr->name, attr->elem);
3598         }
3599         ret &= val;
3600     }
3601
3602     /* ID Attribute Default */
3603     if ((attr->atype == XML_ATTRIBUTE_ID)&&
3604         (attr->def != XML_ATTRIBUTE_IMPLIED) &&
3605         (attr->def != XML_ATTRIBUTE_REQUIRED)) {
3606         VERROR(ctxt->userData,
3607           "ID attribute %s of %s is not valid must be #IMPLIED or #REQUIRED\n",
3608                attr->name, attr->elem);
3609         ret = 0;
3610     }
3611
3612     /* One ID per Element Type */
3613     if (attr->atype == XML_ATTRIBUTE_ID) {
3614         int nbId;
3615
3616         /* the trick is that we parse DtD as their own internal subset */
3617         xmlElementPtr elem = xmlGetDtdElementDesc(doc->intSubset,
3618                                                   attr->elem);
3619         if (elem != NULL) {
3620             nbId = xmlScanIDAttributeDecl(NULL, elem);
3621         } else {
3622             xmlAttributeTablePtr table;
3623
3624             /*
3625              * The attribute may be declared in the internal subset and the
3626              * element in the external subset.
3627              */
3628             nbId = 0;
3629             table = (xmlAttributeTablePtr) doc->intSubset->attributes;
3630             xmlHashScan3(table, NULL, NULL, attr->elem, (xmlHashScanner)
3631                          xmlValidateAttributeIdCallback, &nbId);
3632         }
3633         if (nbId > 1) {
3634             VERROR(ctxt->userData,
3635        "Element %s has %d ID attribute defined in the internal subset : %s\n",
3636                    attr->elem, nbId, attr->name);
3637         } else if (doc->extSubset != NULL) {
3638             int extId = 0;
3639             elem = xmlGetDtdElementDesc(doc->extSubset, attr->elem);
3640             if (elem != NULL) {
3641                 extId = xmlScanIDAttributeDecl(NULL, elem);
3642             }
3643             if (extId > 1) {
3644                 VERROR(ctxt->userData,
3645        "Element %s has %d ID attribute defined in the external subset : %s\n",
3646                        attr->elem, extId, attr->name);
3647             } else if (extId + nbId > 1) {
3648                 VERROR(ctxt->userData,
3649 "Element %s has ID attributes defined in the internal and external subset : %s\n",
3650                        attr->elem, attr->name);
3651             }
3652         }
3653     }
3654
3655     /* Validity Constraint: Enumeration */
3656     if ((attr->defaultValue != NULL) && (attr->tree != NULL)) {
3657         xmlEnumerationPtr tree = attr->tree;
3658         while (tree != NULL) {
3659             if (xmlStrEqual(tree->name, attr->defaultValue)) break;
3660             tree = tree->next;
3661         }
3662         if (tree == NULL) {
3663             VERROR(ctxt->userData,
3664 "Default value \"%s\" for attribute %s of %s is not among the enumerated set\n",
3665                    attr->defaultValue, attr->name, attr->elem);
3666             ret = 0;
3667         }
3668     }
3669
3670     return(ret);
3671 }
3672
3673 /**
3674  * xmlValidateElementDecl:
3675  * @ctxt:  the validation context
3676  * @doc:  a document instance
3677  * @elem:  an element definition
3678  *
3679  * Try to validate a single element definition
3680  * basically it does the following checks as described by the
3681  * XML-1.0 recommendation:
3682  *  - [ VC: One ID per Element Type ]
3683  *  - [ VC: No Duplicate Types ]
3684  *  - [ VC: Unique Element Type Declaration ]
3685  *
3686  * returns 1 if valid or 0 otherwise
3687  */
3688
3689 int
3690 xmlValidateElementDecl(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
3691                        xmlElementPtr elem) {
3692     int ret = 1;
3693     xmlElementPtr tst;
3694
3695     CHECK_DTD;
3696
3697     if (elem == NULL) return(1);
3698
3699 #if 0
3700 #ifdef LIBXML_REGEXP_ENABLED
3701     /* Build the regexp associated to the content model */
3702     ret = xmlValidBuildContentModel(ctxt, elem);
3703 #endif
3704 #endif
3705
3706     /* No Duplicate Types */
3707     if (elem->etype == XML_ELEMENT_TYPE_MIXED) {
3708         xmlElementContentPtr cur, next;
3709         const xmlChar *name;
3710
3711         cur = elem->content;
3712         while (cur != NULL) {
3713             if (cur->type != XML_ELEMENT_CONTENT_OR) break;
3714             if (cur->c1 == NULL) break;
3715             if (cur->c1->type == XML_ELEMENT_CONTENT_ELEMENT) {
3716                 name = cur->c1->name;
3717                 next = cur->c2;
3718                 while (next != NULL) {
3719                     if (next->type == XML_ELEMENT_CONTENT_ELEMENT) {
3720                         if ((xmlStrEqual(next->name, name)) &&
3721                             (xmlStrEqual(next->prefix, cur->prefix))) {
3722                             if (cur->prefix == NULL) {
3723                                 VERROR(ctxt->userData,
3724                    "Definition of %s has duplicate references of %s\n",
3725                                        elem->name, name);
3726                             } else {
3727                                 VERROR(ctxt->userData,
3728                    "Definition of %s has duplicate references of %s:%s\n",
3729                                        elem->name, cur->prefix, name);
3730                             }
3731                             ret = 0;
3732                         }
3733                         break;
3734                     }
3735                     if (next->c1 == NULL) break;
3736                     if (next->c1->type != XML_ELEMENT_CONTENT_ELEMENT) break;
3737                     if ((xmlStrEqual(next->c1->name, name)) &&
3738                         (xmlStrEqual(next->c1->prefix, cur->prefix))) {
3739                         if (cur->prefix == NULL) {
3740                             VERROR(ctxt->userData,
3741                "Definition of %s has duplicate references to %s\n",
3742                                    elem->name, name);
3743                         } else {
3744                             VERROR(ctxt->userData,
3745                "Definition of %s has duplicate references to %s:%s\n",
3746                                    elem->name, cur->prefix, name);
3747                         }
3748                         ret = 0;
3749                     }
3750                     next = next->c2;
3751                 }
3752             }
3753             cur = cur->c2;
3754         }
3755     }
3756
3757     /* VC: Unique Element Type Declaration */
3758     tst = xmlGetDtdElementDesc(doc->intSubset, elem->name);
3759     if ((tst != NULL ) && (tst != elem) &&
3760         ((tst->prefix == elem->prefix) ||
3761          (xmlStrEqual(tst->prefix, elem->prefix))) &&
3762         (tst->etype != XML_ELEMENT_TYPE_UNDEFINED)) {
3763         VERROR(ctxt->userData, "Redefinition of element %s\n",
3764                elem->name);
3765         ret = 0;
3766     }
3767     tst = xmlGetDtdElementDesc(doc->extSubset, elem->name);
3768     if ((tst != NULL ) && (tst != elem) &&
3769         ((tst->prefix == elem->prefix) ||
3770          (xmlStrEqual(tst->prefix, elem->prefix))) &&
3771         (tst->etype != XML_ELEMENT_TYPE_UNDEFINED)) {
3772         VERROR(ctxt->userData, "Redefinition of element %s\n",
3773                elem->name);
3774         ret = 0;
3775     }
3776     /* One ID per Element Type
3777      * already done when registering the attribute
3778     if (xmlScanIDAttributeDecl(ctxt, elem) > 1) {
3779         ret = 0;
3780     } */
3781     return(ret);
3782 }
3783
3784 /**
3785  * xmlValidateOneAttribute:
3786  * @ctxt:  the validation context
3787  * @doc:  a document instance
3788  * @elem:  an element instance
3789  * @attr:  an attribute instance
3790  * @value:  the attribute value (without entities processing)
3791  *
3792  * Try to validate a single attribute for an element
3793  * basically it does the following checks as described by the
3794  * XML-1.0 recommendation:
3795  *  - [ VC: Attribute Value Type ]
3796  *  - [ VC: Fixed Attribute Default ]
3797  *  - [ VC: Entity Name ]
3798  *  - [ VC: Name Token ]
3799  *  - [ VC: ID ]
3800  *  - [ VC: IDREF ]
3801  *  - [ VC: Entity Name ]
3802  *  - [ VC: Notation Attributes ]
3803  *
3804  * The ID/IDREF uniqueness and matching are done separately
3805  *
3806  * returns 1 if valid or 0 otherwise
3807  */
3808
3809 int
3810 xmlValidateOneAttribute(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
3811                         xmlNodePtr elem, xmlAttrPtr attr, const xmlChar *value) {
3812     /* xmlElementPtr elemDecl; */
3813     xmlAttributePtr attrDecl =  NULL;
3814     int val;
3815     int ret = 1;
3816
3817     CHECK_DTD;
3818     if ((elem == NULL) || (elem->name == NULL)) return(0);
3819     if ((attr == NULL) || (attr->name == NULL)) return(0);
3820
3821     if ((elem->ns != NULL) && (elem->ns->prefix != NULL)) {
3822         xmlChar fn[50];
3823         xmlChar *fullname;
3824
3825         fullname = xmlBuildQName(elem->name, elem->ns->prefix, fn, 50);
3826         if (fullname == NULL)
3827             return(0);
3828         if (attr->ns != NULL) {
3829             attrDecl = xmlGetDtdQAttrDesc(doc->intSubset, fullname,
3830                                           attr->name, attr->ns->prefix);
3831             if ((attrDecl == NULL) && (doc->extSubset != NULL))
3832                 attrDecl = xmlGetDtdQAttrDesc(doc->extSubset, fullname,
3833                                               attr->name, attr->ns->prefix);
3834         } else {
3835             attrDecl = xmlGetDtdAttrDesc(doc->intSubset, fullname, attr->name);
3836             if ((attrDecl == NULL) && (doc->extSubset != NULL))
3837                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset,
3838                                              fullname, attr->name);
3839         }
3840         if ((fullname != fn) && (fullname != elem->name))
3841             xmlFree(fullname);
3842     }
3843     if (attrDecl == NULL) {
3844         if (attr->ns != NULL) {
3845             attrDecl = xmlGetDtdQAttrDesc(doc->intSubset, elem->name,
3846                                           attr->name, attr->ns->prefix);
3847             if ((attrDecl == NULL) && (doc->extSubset != NULL))
3848                 attrDecl = xmlGetDtdQAttrDesc(doc->extSubset, elem->name,
3849                                               attr->name, attr->ns->prefix);
3850         } else {
3851             attrDecl = xmlGetDtdAttrDesc(doc->intSubset,
3852                                          elem->name, attr->name);
3853             if ((attrDecl == NULL) && (doc->extSubset != NULL))
3854                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset,
3855                                              elem->name, attr->name);
3856         }
3857     }
3858
3859
3860     /* Validity Constraint: Attribute Value Type */
3861     if (attrDecl == NULL) {
3862         VECTXT(ctxt, elem);
3863         VERROR(ctxt->userData,
3864                "No declaration for attribute %s of element %s\n",
3865                attr->name, elem->name);
3866         return(0);
3867     }
3868     attr->atype = attrDecl->atype;
3869
3870     val = xmlValidateAttributeValue(attrDecl->atype, value);
3871     if (val == 0) {
3872         VECTXT(ctxt, elem);
3873         VERROR(ctxt->userData,
3874            "Syntax of value for attribute %s of %s is not valid\n",
3875                attr->name, elem->name);
3876         ret = 0;
3877     }
3878
3879     /* Validity constraint: Fixed Attribute Default */
3880     if (attrDecl->def == XML_ATTRIBUTE_FIXED) {
3881         if (!xmlStrEqual(value, attrDecl->defaultValue)) {
3882             VECTXT(ctxt, elem);
3883             VERROR(ctxt->userData,
3884            "Value for attribute %s of %s is different from default \"%s\"\n",
3885                    attr->name, elem->name, attrDecl->defaultValue);
3886             ret = 0;
3887         }
3888     }
3889
3890     /* Validity Constraint: ID uniqueness */
3891     if (attrDecl->atype == XML_ATTRIBUTE_ID) {
3892         if (xmlAddID(ctxt, doc, value, attr) == NULL)
3893             ret = 0;
3894     }
3895
3896     if ((attrDecl->atype == XML_ATTRIBUTE_IDREF) ||
3897         (attrDecl->atype == XML_ATTRIBUTE_IDREFS)) {
3898         if (xmlAddRef(ctxt, doc, value, attr) == NULL)
3899             ret = 0;
3900     }
3901
3902     /* Validity Constraint: Notation Attributes */
3903     if (attrDecl->atype == XML_ATTRIBUTE_NOTATION) {
3904         xmlEnumerationPtr tree = attrDecl->tree;
3905         xmlNotationPtr nota;
3906
3907         /* First check that the given NOTATION was declared */
3908         nota = xmlGetDtdNotationDesc(doc->intSubset, value);
3909         if (nota == NULL)
3910             nota = xmlGetDtdNotationDesc(doc->extSubset, value);
3911
3912         if (nota == NULL) {
3913             VECTXT(ctxt, elem);
3914             VERROR(ctxt->userData,
3915        "Value \"%s\" for attribute %s of %s is not a declared Notation\n",
3916                    value, attr->name, elem->name);
3917             ret = 0;
3918         }
3919
3920         /* Second, verify that it's among the list */
3921         while (tree != NULL) {
3922             if (xmlStrEqual(tree->name, value)) break;
3923             tree = tree->next;
3924         }
3925         if (tree == NULL) {
3926             VECTXT(ctxt, elem);
3927             VERROR(ctxt->userData,
3928 "Value \"%s\" for attribute %s of %s is not among the enumerated notations\n",
3929                    value, attr->name, elem->name);
3930             ret = 0;
3931         }
3932     }
3933
3934     /* Validity Constraint: Enumeration */
3935     if (attrDecl->atype == XML_ATTRIBUTE_ENUMERATION) {
3936         xmlEnumerationPtr tree = attrDecl->tree;
3937         while (tree != NULL) {
3938             if (xmlStrEqual(tree->name, value)) break;
3939             tree = tree->next;
3940         }
3941         if (tree == NULL) {
3942             VECTXT(ctxt, elem);
3943             VERROR(ctxt->userData,
3944        "Value \"%s\" for attribute %s of %s is not among the enumerated set\n",
3945                    value, attr->name, elem->name);
3946             ret = 0;
3947         }
3948     }
3949
3950     /* Fixed Attribute Default */
3951     if ((attrDecl->def == XML_ATTRIBUTE_FIXED) &&
3952         (!xmlStrEqual(attrDecl->defaultValue, value))) {
3953         VECTXT(ctxt, elem);
3954         VERROR(ctxt->userData,
3955            "Value for attribute %s of %s must be \"%s\"\n",
3956                attr->name, elem->name, attrDecl->defaultValue);
3957         ret = 0;
3958     }
3959
3960     /* Extra check for the attribute value */
3961     ret &= xmlValidateAttributeValue2(ctxt, doc, attr->name,
3962                                       attrDecl->atype, value);
3963
3964     return(ret);
3965 }
3966
3967 /**
3968  * xmlValidateOneNamespace:
3969  * @ctxt:  the validation context
3970  * @doc:  a document instance
3971  * @elem:  an element instance
3972  * @prefix:  the namespace prefix
3973  * @ns:  an namespace declaration instance
3974  * @value:  the attribute value (without entities processing)
3975  *
3976  * Try to validate a single namespace declaration for an element
3977  * basically it does the following checks as described by the
3978  * XML-1.0 recommendation:
3979  *  - [ VC: Attribute Value Type ]
3980  *  - [ VC: Fixed Attribute Default ]
3981  *  - [ VC: Entity Name ]
3982  *  - [ VC: Name Token ]
3983  *  - [ VC: ID ]
3984  *  - [ VC: IDREF ]
3985  *  - [ VC: Entity Name ]
3986  *  - [ VC: Notation Attributes ]
3987  *
3988  * The ID/IDREF uniqueness and matching are done separately
3989  *
3990  * returns 1 if valid or 0 otherwise
3991  */
3992
3993 int
3994 xmlValidateOneNamespace(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
3995 xmlNodePtr elem, const xmlChar *prefix, xmlNsPtr ns, const xmlChar *value) {
3996     /* xmlElementPtr elemDecl; */
3997     xmlAttributePtr attrDecl =  NULL;
3998     int val;
3999     int ret = 1;
4000
4001     CHECK_DTD;
4002     if ((elem == NULL) || (elem->name == NULL)) return(0);
4003     if ((ns == NULL) || (ns->href == NULL)) return(0);
4004
4005     if (prefix != NULL) {
4006         xmlChar fn[50];
4007         xmlChar *fullname;
4008
4009         fullname = xmlBuildQName(elem->name, prefix, fn, 50);
4010         if (fullname == NULL) {
4011             VERROR(ctxt->userData, "Out of memory\n");
4012             return(0);
4013         }
4014         if (ns->prefix != NULL) {
4015             attrDecl = xmlGetDtdQAttrDesc(doc->intSubset, fullname,
4016                                           ns->prefix, BAD_CAST "xmlns");
4017             if ((attrDecl == NULL) && (doc->extSubset != NULL))
4018                 attrDecl = xmlGetDtdQAttrDesc(doc->extSubset, fullname,
4019                                           ns->prefix, BAD_CAST "xmlns");
4020         } else {
4021             attrDecl = xmlGetDtdAttrDesc(doc->intSubset, fullname,
4022                                          BAD_CAST "xmlns");
4023             if ((attrDecl == NULL) && (doc->extSubset != NULL))
4024                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset, fullname,
4025                                          BAD_CAST "xmlns");
4026         }
4027         if ((fullname != fn) && (fullname != elem->name))
4028             xmlFree(fullname);
4029     }
4030     if (attrDecl == NULL) {
4031         if (ns->prefix != NULL) {
4032             attrDecl = xmlGetDtdQAttrDesc(doc->intSubset, elem->name,
4033                                           ns->prefix, BAD_CAST "xmlns");
4034             if ((attrDecl == NULL) && (doc->extSubset != NULL))
4035                 attrDecl = xmlGetDtdQAttrDesc(doc->extSubset, elem->name,
4036                                               ns->prefix, BAD_CAST "xmlns");
4037         } else {
4038             attrDecl = xmlGetDtdAttrDesc(doc->intSubset,
4039                                          elem->name, BAD_CAST "xmlns");
4040             if ((attrDecl == NULL) && (doc->extSubset != NULL))
4041                 attrDecl = xmlGetDtdAttrDesc(doc->extSubset,
4042                                              elem->name, BAD_CAST "xmlns");
4043         }
4044     }
4045
4046
4047     /* Validity Constraint: Attribute Value Type */
4048     if (attrDecl == NULL) {
4049         VECTXT(ctxt, elem);
4050         if (ns->prefix != NULL) {
4051             VERROR(ctxt->userData,
4052                    "No declaration for attribute xmlns:%s of element %s\n",
4053                    ns->prefix, elem->name);
4054         } else {
4055             VERROR(ctxt->userData,
4056                    "No declaration for attribute xmlns of element %s\n",
4057                    elem->name);
4058         }
4059         return(0);
4060     }
4061
4062     val = xmlValidateAttributeValue(attrDecl->atype, value);
4063     if (val == 0) {
4064         VECTXT(ctxt, elem);
4065         if (ns->prefix != NULL) {
4066             VERROR(ctxt->userData,
4067                "Syntax of value for attribute xmlns:%s of %s is not valid\n",
4068                    ns->prefix, elem->name);
4069         } else {
4070             VERROR(ctxt->userData,
4071                "Syntax of value for attribute xmlns of %s is not valid\n",
4072                    elem->name);
4073         }
4074         ret = 0;
4075     }
4076
4077     /* Validity constraint: Fixed Attribute Default */
4078     if (attrDecl->def == XML_ATTRIBUTE_FIXED) {
4079         if (!xmlStrEqual(value, attrDecl->defaultValue)) {
4080             VECTXT(ctxt, elem);
4081             if (ns->prefix != NULL) {
4082                 VERROR(ctxt->userData,
4083        "Value for attribute xmlns:%s of %s is different from default \"%s\"\n",
4084                        ns->prefix, elem->name, attrDecl->defaultValue);
4085             } else {
4086                 VERROR(ctxt->userData,
4087        "Value for attribute xmlns of %s is different from default \"%s\"\n",
4088                        elem->name, attrDecl->defaultValue);
4089             }
4090             ret = 0;
4091         }
4092     }
4093
4094     /* Validity Constraint: ID uniqueness */
4095     if (attrDecl->atype == XML_ATTRIBUTE_ID) {
4096         if (xmlAddID(ctxt, doc, value, (xmlAttrPtr) ns) == NULL)
4097             ret = 0;
4098     }
4099
4100     if ((attrDecl->atype == XML_ATTRIBUTE_IDREF) ||
4101         (attrDecl->atype == XML_ATTRIBUTE_IDREFS)) {
4102         if (xmlAddRef(ctxt, doc, value, (xmlAttrPtr) ns) == NULL)
4103             ret = 0;
4104     }
4105
4106     /* Validity Constraint: Notation Attributes */
4107     if (attrDecl->atype == XML_ATTRIBUTE_NOTATION) {
4108         xmlEnumerationPtr tree = attrDecl->tree;
4109         xmlNotationPtr nota;
4110
4111         /* First check that the given NOTATION was declared */
4112         nota = xmlGetDtdNotationDesc(doc->intSubset, value);
4113         if (nota == NULL)
4114             nota = xmlGetDtdNotationDesc(doc->extSubset, value);
4115
4116         if (nota == NULL) {
4117             VECTXT(ctxt, elem);
4118             if (ns->prefix != NULL) {
4119                 VERROR(ctxt->userData,
4120        "Value \"%s\" for attribute xmlns:%s of %s is not a declared Notation\n",
4121                        value, ns->prefix, elem->name);
4122             } else {
4123                 VERROR(ctxt->userData,
4124        "Value \"%s\" for attribute xmlns of %s is not a declared Notation\n",
4125                        value, elem->name);
4126             }
4127             ret = 0;
4128         }
4129
4130         /* Second, verify that it's among the list */
4131         while (tree != NULL) {
4132             if (xmlStrEqual(tree->name, value)) break;
4133             tree = tree->next;
4134         }
4135         if (tree == NULL) {
4136             VECTXT(ctxt, elem);
4137             if (ns->prefix != NULL) {
4138                 VERROR(ctxt->userData,
4139 "Value \"%s\" for attribute xmlns:%s of %s is not among the enumerated notations\n",
4140                        value, ns->prefix, elem->name);
4141             } else {
4142                 VERROR(ctxt->userData,
4143 "Value \"%s\" for attribute xmlns of %s is not among the enumerated notations\n",
4144                        value, elem->name);
4145             }
4146             ret = 0;
4147         }
4148     }
4149
4150     /* Validity Constraint: Enumeration */
4151     if (attrDecl->atype == XML_ATTRIBUTE_ENUMERATION) {
4152         xmlEnumerationPtr tree = attrDecl->tree;
4153         while (tree != NULL) {
4154             if (xmlStrEqual(tree->name, value)) break;
4155             tree = tree->next;
4156         }
4157         if (tree == NULL) {
4158             VECTXT(ctxt, elem);
4159             if (ns->prefix != NULL) {
4160                 VERROR(ctxt->userData,
4161 "Value \"%s\" for attribute xmlns:%s of %s is not among the enumerated set\n",
4162                        value, ns->prefix, elem->name);
4163             } else {
4164                 VERROR(ctxt->userData,
4165 "Value \"%s\" for attribute xmlns of %s is not among the enumerated set\n",
4166                        value, elem->name);
4167             }
4168             ret = 0;
4169         }
4170     }
4171
4172     /* Fixed Attribute Default */
4173     if ((attrDecl->def == XML_ATTRIBUTE_FIXED) &&
4174         (!xmlStrEqual(attrDecl->defaultValue, value))) {
4175         VECTXT(ctxt, elem);
4176         if (ns->prefix != NULL) {
4177             VERROR(ctxt->userData,
4178                    "Value for attribute xmlns:%s of %s must be \"%s\"\n",
4179                    ns->prefix, elem->name, attrDecl->defaultValue);
4180         } else {
4181             VERROR(ctxt->userData,
4182                    "Value for attribute xmlns of %s must be \"%s\"\n",
4183                    elem->name, attrDecl->defaultValue);
4184         }
4185         ret = 0;
4186     }
4187
4188     /* Extra check for the attribute value */
4189     if (ns->prefix != NULL) {
4190         ret &= xmlValidateAttributeValue2(ctxt, doc, ns->prefix,
4191                                           attrDecl->atype, value);
4192     } else {
4193         ret &= xmlValidateAttributeValue2(ctxt, doc, BAD_CAST "xmlns",
4194                                           attrDecl->atype, value);
4195     }
4196
4197     return(ret);
4198 }
4199
4200 #ifndef  LIBXML_REGEXP_ENABLED
4201 /**
4202  * xmlValidateSkipIgnorable:
4203  * @ctxt:  the validation context
4204  * @child:  the child list
4205  *
4206  * Skip ignorable elements w.r.t. the validation process
4207  *
4208  * returns the first element to consider for validation of the content model
4209  */
4210
4211 static xmlNodePtr
4212 xmlValidateSkipIgnorable(xmlNodePtr child) {
4213     while (child != NULL) {
4214         switch (child->type) {
4215             /* These things are ignored (skipped) during validation.  */
4216             case XML_PI_NODE:
4217             case XML_COMMENT_NODE:
4218             case XML_XINCLUDE_START:
4219             case XML_XINCLUDE_END:
4220                 child = child->next;
4221                 break;
4222             case XML_TEXT_NODE:
4223                 if (xmlIsBlankNode(child))
4224                     child = child->next;
4225                 else
4226                     return(child);
4227                 break;
4228             /* keep current node */
4229             default:
4230                 return(child);
4231         }
4232     }
4233     return(child);
4234 }
4235
4236 /**
4237  * xmlValidateElementType:
4238  * @ctxt:  the validation context
4239  *
4240  * Try to validate the content model of an element internal function
4241  *
4242  * returns 1 if valid or 0 ,-1 in case of error, -2 if an entity
4243  *           reference is found and -3 if the validation succeeded but
4244  *           the content model is not determinist.
4245  */
4246
4247 static int
4248 xmlValidateElementType(xmlValidCtxtPtr ctxt) {
4249     int ret = -1;
4250     int determinist = 1;
4251
4252     NODE = xmlValidateSkipIgnorable(NODE);
4253     if ((NODE == NULL) && (CONT == NULL))
4254         return(1);
4255     if ((NODE == NULL) &&
4256         ((CONT->ocur == XML_ELEMENT_CONTENT_MULT) ||
4257          (CONT->ocur == XML_ELEMENT_CONTENT_OPT))) {
4258         return(1);
4259     }
4260     if (CONT == NULL) return(-1);
4261     if ((NODE != NULL) && (NODE->type == XML_ENTITY_REF_NODE))
4262         return(-2);
4263
4264     /*
4265      * We arrive here when more states need to be examined
4266      */
4267 cont:
4268
4269     /*
4270      * We just recovered from a rollback generated by a possible
4271      * epsilon transition, go directly to the analysis phase
4272      */
4273     if (STATE == ROLLBACK_PARENT) {
4274         DEBUG_VALID_MSG("restored parent branch");
4275         DEBUG_VALID_STATE(NODE, CONT)
4276         ret = 1;
4277         goto analyze;
4278     }
4279
4280     DEBUG_VALID_STATE(NODE, CONT)
4281     /*
4282      * we may have to save a backup state here. This is the equivalent
4283      * of handling epsilon transition in NFAs.
4284      */
4285     if ((CONT != NULL) &&
4286         ((CONT->parent == NULL) ||
4287          (CONT->parent->type != XML_ELEMENT_CONTENT_OR)) &&
4288         ((CONT->ocur == XML_ELEMENT_CONTENT_MULT) ||
4289          (CONT->ocur == XML_ELEMENT_CONTENT_OPT) ||
4290          ((CONT->ocur == XML_ELEMENT_CONTENT_PLUS) && (OCCURRENCE)))) {
4291         DEBUG_VALID_MSG("saving parent branch");
4292         if (vstateVPush(ctxt, CONT, NODE, DEPTH, OCCURS, ROLLBACK_PARENT) < 0)
4293             return(0);
4294     }
4295
4296
4297     /*
4298      * Check first if the content matches
4299      */
4300     switch (CONT->type) {
4301         case XML_ELEMENT_CONTENT_PCDATA:
4302             if (NODE == NULL) {
4303                 DEBUG_VALID_MSG("pcdata failed no node");
4304                 ret = 0;
4305                 break;
4306             }
4307             if (NODE->type == XML_TEXT_NODE) {
4308                 DEBUG_VALID_MSG("pcdata found, skip to next");
4309                 /*
4310                  * go to next element in the content model
4311                  * skipping ignorable elems
4312                  */
4313                 do {
4314                     NODE = NODE->next;
4315                     NODE = xmlValidateSkipIgnorable(NODE);
4316                     if ((NODE != NULL) &&
4317                         (NODE->type == XML_ENTITY_REF_NODE))
4318                         return(-2);
4319                 } while ((NODE != NULL) &&
4320                          ((NODE->type != XML_ELEMENT_NODE) &&
4321                           (NODE->type != XML_TEXT_NODE) &&
4322                           (NODE->type != XML_CDATA_SECTION_NODE)));
4323                 ret = 1;
4324                 break;
4325             } else {
4326                 DEBUG_VALID_MSG("pcdata failed");
4327                 ret = 0;
4328                 break;
4329             }
4330             break;
4331         case XML_ELEMENT_CONTENT_ELEMENT:
4332             if (NODE == NULL) {
4333                 DEBUG_VALID_MSG("element failed no node");
4334                 ret = 0;
4335                 break;
4336             }
4337             ret = ((NODE->type == XML_ELEMENT_NODE) &&
4338                    (xmlStrEqual(NODE->name, CONT->name)));
4339             if (ret == 1) {
4340                 if ((NODE->ns == NULL) || (NODE->ns->prefix == NULL)) {
4341                     ret = (CONT->prefix == NULL);
4342                 } else if (CONT->prefix == NULL) {
4343                     ret = 0;
4344                 } else {
4345                     ret = xmlStrEqual(NODE->ns->prefix, CONT->prefix);
4346                 }
4347             }
4348             if (ret == 1) {
4349                 DEBUG_VALID_MSG("element found, skip to next");
4350                 /*
4351                  * go to next element in the content model
4352                  * skipping ignorable elems
4353                  */
4354                 do {
4355                     NODE = NODE->next;
4356                     NODE = xmlValidateSkipIgnorable(NODE);
4357                     if ((NODE != NULL) &&
4358                         (NODE->type == XML_ENTITY_REF_NODE))
4359                         return(-2);
4360                 } while ((NODE != NULL) &&
4361                          ((NODE->type != XML_ELEMENT_NODE) &&
4362                           (NODE->type != XML_TEXT_NODE) &&
4363                           (NODE->type != XML_CDATA_SECTION_NODE)));
4364             } else {
4365                 DEBUG_VALID_MSG("element failed");
4366                 ret = 0;
4367                 break;
4368             }
4369             break;
4370         case XML_ELEMENT_CONTENT_OR:
4371             /*
4372              * Small optimization.
4373              */
4374             if (CONT->c1->type == XML_ELEMENT_CONTENT_ELEMENT) {
4375                 if ((NODE == NULL) ||
4376                     (!xmlStrEqual(NODE->name, CONT->c1->name))) {
4377                     DEPTH++;
4378                     CONT = CONT->c2;
4379                     goto cont;
4380                 }
4381                 if ((NODE->ns == NULL) || (NODE->ns->prefix == NULL)) {
4382                     ret = (CONT->c1->prefix == NULL);
4383                 } else if (CONT->c1->prefix == NULL) {
4384                     ret = 0;
4385                 } else {
4386                     ret = xmlStrEqual(NODE->ns->prefix, CONT->c1->prefix);
4387                 }
4388                 if (ret == 0) {
4389                     DEPTH++;
4390                     CONT = CONT->c2;
4391                     goto cont;
4392                 }
4393             }
4394
4395             /*
4396              * save the second branch 'or' branch
4397              */
4398             DEBUG_VALID_MSG("saving 'or' branch");
4399             if (vstateVPush(ctxt, CONT->c2, NODE, (unsigned char)(DEPTH + 1),
4400                             OCCURS, ROLLBACK_OR) < 0)
4401                 return(-1);
4402             DEPTH++;
4403             CONT = CONT->c1;
4404             goto cont;
4405         case XML_ELEMENT_CONTENT_SEQ:
4406             /*
4407              * Small optimization.
4408              */
4409             if ((CONT->c1->type == XML_ELEMENT_CONTENT_ELEMENT) &&
4410                 ((CONT->c1->ocur == XML_ELEMENT_CONTENT_OPT) ||
4411                  (CONT->c1->ocur == XML_ELEMENT_CONTENT_MULT))) {
4412                 if ((NODE == NULL) ||
4413                     (!xmlStrEqual(NODE->name, CONT->c1->name))) {
4414                     DEPTH++;
4415                     CONT = CONT->c2;
4416                     goto cont;
4417                 }
4418                 if ((NODE->ns == NULL) || (NODE->ns->prefix == NULL)) {
4419                     ret = (CONT->c1->prefix == NULL);
4420                 } else if (CONT->c1->prefix == NULL) {
4421                     ret = 0;
4422                 } else {
4423                     ret = xmlStrEqual(NODE->ns->prefix, CONT->c1->prefix);
4424                 }
4425                 if (ret == 0) {
4426                     DEPTH++;
4427                     CONT = CONT->c2;
4428                     goto cont;
4429                 }
4430             }
4431             DEPTH++;
4432             CONT = CONT->c1;
4433             goto cont;
4434     }
4435
4436     /*
4437      * At this point handle going up in the tree
4438      */
4439     if (ret == -1) {
4440         DEBUG_VALID_MSG("error found returning");
4441         return(ret);
4442     }
4443 analyze:
4444     while (CONT != NULL) {
4445         /*
4446          * First do the analysis depending on the occurrence model at
4447          * this level.
4448          */
4449         if (ret == 0) {
4450             switch (CONT->ocur) {
4451                 xmlNodePtr cur;
4452
4453                 case XML_ELEMENT_CONTENT_ONCE:
4454                     cur = ctxt->vstate->node;
4455                     DEBUG_VALID_MSG("Once branch failed, rollback");
4456                     if (vstateVPop(ctxt) < 0 ) {
4457                         DEBUG_VALID_MSG("exhaustion, failed");
4458                         return(0);
4459                     }
4460                     if (cur != ctxt->vstate->node)
4461                         determinist = -3;
4462                     goto cont;
4463                 case XML_ELEMENT_CONTENT_PLUS:
4464                     if (OCCURRENCE == 0) {
4465                         cur = ctxt->vstate->node;
4466                         DEBUG_VALID_MSG("Plus branch failed, rollback");
4467                         if (vstateVPop(ctxt) < 0 ) {
4468                             DEBUG_VALID_MSG("exhaustion, failed");
4469                             return(0);
4470                         }
4471                         if (cur != ctxt->vstate->node)
4472                             determinist = -3;
4473                         goto cont;
4474                     }
4475                     DEBUG_VALID_MSG("Plus branch found");
4476                     ret = 1;
4477                     break;
4478                 case XML_ELEMENT_CONTENT_MULT:
4479 #ifdef DEBUG_VALID_ALGO
4480                     if (OCCURRENCE == 0) {
4481                         DEBUG_VALID_MSG("Mult branch failed");
4482                     } else {
4483                         DEBUG_VALID_MSG("Mult branch found");
4484                     }
4485 #endif
4486                     ret = 1;
4487                     break;
4488                 case XML_ELEMENT_CONTENT_OPT:
4489                     DEBUG_VALID_MSG("Option branch failed");
4490                     ret = 1;
4491                     break;
4492             }
4493         } else {
4494             switch (CONT->ocur) {
4495                 case XML_ELEMENT_CONTENT_OPT:
4496                     DEBUG_VALID_MSG("Option branch succeeded");
4497                     ret = 1;
4498                     break;
4499                 case XML_ELEMENT_CONTENT_ONCE:
4500                     DEBUG_VALID_MSG("Once branch succeeded");
4501                     ret = 1;
4502                     break;
4503                 case XML_ELEMENT_CONTENT_PLUS:
4504                     if (STATE == ROLLBACK_PARENT) {
4505                         DEBUG_VALID_MSG("Plus branch rollback");
4506                         ret = 1;
4507                         break;
4508                     }
4509                     if (NODE == NULL) {
4510                         DEBUG_VALID_MSG("Plus branch exhausted");
4511                         ret = 1;
4512                         break;
4513                     }
4514                     DEBUG_VALID_MSG("Plus branch succeeded, continuing");
4515                     SET_OCCURRENCE;
4516                     goto cont;
4517                 case XML_ELEMENT_CONTENT_MULT:
4518                     if (STATE == ROLLBACK_PARENT) {
4519                         DEBUG_VALID_MSG("Mult branch rollback");
4520                         ret = 1;
4521                         break;
4522                     }
4523                     if (NODE == NULL) {
4524                         DEBUG_VALID_MSG("Mult branch exhausted");
4525                         ret = 1;
4526                         break;
4527                     }
4528                     DEBUG_VALID_MSG("Mult branch succeeded, continuing");
4529                     /* SET_OCCURRENCE; */
4530                     goto cont;
4531             }
4532         }
4533         STATE = 0;
4534
4535         /*
4536          * Then act accordingly at the parent level
4537          */
4538         RESET_OCCURRENCE;
4539         if (CONT->parent == NULL)
4540             break;
4541
4542         switch (CONT->parent->type) {
4543             case XML_ELEMENT_CONTENT_PCDATA:
4544                 DEBUG_VALID_MSG("Error: parent pcdata");
4545                 return(-1);
4546             case XML_ELEMENT_CONTENT_ELEMENT:
4547                 DEBUG_VALID_MSG("Error: parent element");
4548                 return(-1);
4549             case XML_ELEMENT_CONTENT_OR:
4550                 if (ret == 1) {
4551                     DEBUG_VALID_MSG("Or succeeded");
4552                     CONT = CONT->parent;
4553                     DEPTH--;
4554                 } else {
4555                     DEBUG_VALID_MSG("Or failed");
4556                     CONT = CONT->parent;
4557                     DEPTH--;
4558                 }
4559                 break;
4560             case XML_ELEMENT_CONTENT_SEQ:
4561                 if (ret == 0) {
4562                     DEBUG_VALID_MSG("Sequence failed");
4563                     CONT = CONT->parent;
4564                     DEPTH--;
4565                 } else if (CONT == CONT->parent->c1) {
4566                     DEBUG_VALID_MSG("Sequence testing 2nd branch");
4567                     CONT = CONT->parent->c2;
4568                     goto cont;
4569                 } else {
4570                     DEBUG_VALID_MSG("Sequence succeeded");
4571                     CONT = CONT->parent;
4572                     DEPTH--;
4573                 }
4574         }
4575     }
4576     if (NODE != NULL) {
4577         xmlNodePtr cur;
4578
4579         cur = ctxt->vstate->node;
4580         DEBUG_VALID_MSG("Failed, remaining input, rollback");
4581         if (vstateVPop(ctxt) < 0 ) {
4582             DEBUG_VALID_MSG("exhaustion, failed");
4583             return(0);
4584         }
4585         if (cur != ctxt->vstate->node)
4586             determinist = -3;
4587         goto cont;
4588     }
4589     if (ret == 0) {
4590         xmlNodePtr cur;
4591
4592         cur = ctxt->vstate->node;
4593         DEBUG_VALID_MSG("Failure, rollback");
4594         if (vstateVPop(ctxt) < 0 ) {
4595             DEBUG_VALID_MSG("exhaustion, failed");
4596             return(0);
4597         }
4598         if (cur != ctxt->vstate->node)
4599             determinist = -3;
4600         goto cont;
4601     }
4602     return(determinist);
4603 }
4604 #endif
4605
4606 /**
4607  * xmlSnprintfElements:
4608  * @buf:  an output buffer
4609  * @size:  the size of the buffer
4610  * @content:  An element
4611  * @glob: 1 if one must print the englobing parenthesis, 0 otherwise
4612  *
4613  * This will dump the list of elements to the buffer
4614  * Intended just for the debug routine
4615  */
4616 static void
4617 xmlSnprintfElements(char *buf, int size, xmlNodePtr node, int glob) {
4618     xmlNodePtr cur;
4619     int len;
4620
4621     if (node == NULL) return;
4622     if (glob) strcat(buf, "(");
4623     cur = node;
4624     while (cur != NULL) {
4625         len = strlen(buf);
4626         if (size - len < 50) {
4627             if ((size - len > 4) && (buf[len - 1] != '.'))
4628                 strcat(buf, " ...");
4629             return;
4630         }
4631         switch (cur->type) {
4632             case XML_ELEMENT_NODE:
4633                 if ((cur->ns != NULL) && (cur->ns->prefix != NULL)) {
4634                     if (size - len < xmlStrlen(cur->ns->prefix) + 10) {
4635                         if ((size - len > 4) && (buf[len - 1] != '.'))
4636                             strcat(buf, " ...");
4637                         return;
4638                     }
4639                     strcat(buf, (char *) cur->ns->prefix);
4640                     strcat(buf, ":");
4641                 }
4642                 if (size - len < xmlStrlen(cur->name) + 10) {
4643                     if ((size - len > 4) && (buf[len - 1] != '.'))
4644                         strcat(buf, " ...");
4645                     return;
4646                 }
4647                 strcat(buf, (char *) cur->name);
4648                 if (cur->next != NULL)
4649                     strcat(buf, " ");
4650                 break;
4651             case XML_TEXT_NODE:
4652                 if (xmlIsBlankNode(cur))
4653                     break;
4654             case XML_CDATA_SECTION_NODE:
4655             case XML_ENTITY_REF_NODE:
4656                 strcat(buf, "CDATA");
4657                 if (cur->next != NULL)
4658                     strcat(buf, " ");
4659                 break;
4660             case XML_ATTRIBUTE_NODE:
4661             case XML_DOCUMENT_NODE:
4662 #ifdef LIBXML_DOCB_ENABLED
4663             case XML_DOCB_DOCUMENT_NODE:
4664 #endif
4665             case XML_HTML_DOCUMENT_NODE:
4666             case XML_DOCUMENT_TYPE_NODE:
4667             case XML_DOCUMENT_FRAG_NODE:
4668             case XML_NOTATION_NODE:
4669             case XML_NAMESPACE_DECL:
4670                 strcat(buf, "???");
4671                 if (cur->next != NULL)
4672                     strcat(buf, " ");
4673                 break;
4674             case XML_ENTITY_NODE:
4675             case XML_PI_NODE:
4676             case XML_DTD_NODE:
4677             case XML_COMMENT_NODE:
4678             case XML_ELEMENT_DECL:
4679             case XML_ATTRIBUTE_DECL:
4680             case XML_ENTITY_DECL:
4681             case XML_XINCLUDE_START:
4682             case XML_XINCLUDE_END:
4683                 break;
4684         }
4685         cur = cur->next;
4686     }
4687     if (glob) strcat(buf, ")");
4688 }
4689
4690 /**
4691  * xmlValidateElementContent:
4692  * @ctxt:  the validation context
4693  * @child:  the child list
4694  * @elemDecl:  pointer to the element declaration
4695  * @warn:  emit the error message
4696  * @parent: the parent element (for error reporting)
4697  *
4698  * Try to validate the content model of an element
4699  *
4700  * returns 1 if valid or 0 if not and -1 in case of error
4701  */
4702
4703 static int
4704 xmlValidateElementContent(xmlValidCtxtPtr ctxt, xmlNodePtr child,
4705        xmlElementPtr elemDecl, int warn, xmlNodePtr parent) {
4706     int ret = 1;
4707 #ifndef  LIBXML_REGEXP_ENABLED
4708     xmlNodePtr repl = NULL, last = NULL, tmp;
4709 #endif
4710     xmlNodePtr cur;
4711     xmlElementContentPtr cont;
4712     const xmlChar *name;
4713
4714     if (elemDecl == NULL)
4715         return(-1);
4716     cont = elemDecl->content;
4717     name = elemDecl->name;
4718
4719 #ifdef LIBXML_REGEXP_ENABLED
4720     /* Build the regexp associated to the content model */
4721     if (elemDecl->contModel == NULL)
4722         ret = xmlValidBuildContentModel(ctxt, elemDecl);
4723     if (elemDecl->contModel == NULL) {
4724         return(-1);
4725     } else {
4726         xmlRegExecCtxtPtr exec;
4727
4728         if (!xmlRegexpIsDeterminist(elemDecl->contModel)) {
4729             return(-1);
4730         }
4731         ctxt->nodeMax = 0;
4732         ctxt->nodeNr = 0;
4733         ctxt->nodeTab = NULL;
4734         exec = xmlRegNewExecCtxt(elemDecl->contModel, NULL, NULL);
4735         if (exec != NULL) {
4736             cur = child;
4737             while (cur != NULL) {
4738                 switch (cur->type) {
4739                     case XML_ENTITY_REF_NODE:
4740                         /*
4741                          * Push the current node to be able to roll back
4742                          * and process within the entity
4743                          */
4744                         if ((cur->children != NULL) &&
4745                             (cur->children->children != NULL)) {
4746                             nodeVPush(ctxt, cur);
4747                             cur = cur->children->children;
4748                             continue;
4749                         }
4750                         break;
4751                     case XML_TEXT_NODE:
4752                         if (xmlIsBlankNode(cur))
4753                             break;
4754                         ret = 0;
4755                         goto fail;
4756                     case XML_CDATA_SECTION_NODE:
4757                         /* TODO */
4758                         ret = 0;
4759                         goto fail;
4760                     case XML_ELEMENT_NODE:
4761                         if ((cur->ns != NULL) && (cur->ns->prefix != NULL)) {
4762                             xmlChar fn[50];
4763                             xmlChar *fullname;
4764
4765                             fullname = xmlBuildQName(cur->name,
4766                                                      cur->ns->prefix, fn, 50);
4767                             if (fullname == NULL) {
4768                                 ret = -1;
4769                                 goto fail;
4770                             }
4771                             ret = xmlRegExecPushString(exec, fullname, NULL);
4772                             if ((fullname != fn) && (fullname != cur->name))
4773                                 xmlFree(fullname);
4774                         } else {
4775                             ret = xmlRegExecPushString(exec, cur->name, NULL);
4776                         }
4777                         break;
4778                     default:
4779                         break;
4780                 }
4781                 /*
4782                  * Switch to next element
4783                  */
4784                 cur = cur->next;
4785                 while (cur == NULL) {
4786                     cur = nodeVPop(ctxt);
4787                     if (cur == NULL)
4788                         break;
4789                     cur = cur->next;
4790                 }
4791             }
4792             ret = xmlRegExecPushString(exec, NULL, NULL);
4793 fail:
4794             xmlRegFreeExecCtxt(exec);
4795         }
4796     }
4797 #else  /* LIBXML_REGEXP_ENABLED */
4798     /*
4799      * Allocate the stack
4800      */
4801     ctxt->vstateMax = 8;
4802     ctxt->vstateTab = (xmlValidState *) xmlMalloc(
4803                  ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
4804     if (ctxt->vstateTab == NULL) {
4805         xmlGenericError(xmlGenericErrorContext,
4806                 "malloc failed !n");
4807         return(-1);
4808     }
4809     /*
4810      * The first entry in the stack is reserved to the current state
4811      */
4812     ctxt->nodeMax = 0;
4813     ctxt->nodeNr = 0;
4814     ctxt->nodeTab = NULL;
4815     ctxt->vstate = &ctxt->vstateTab[0];
4816     ctxt->vstateNr = 1;
4817     CONT = cont;
4818     NODE = child;
4819     DEPTH = 0;
4820     OCCURS = 0;
4821     STATE = 0;
4822     ret = xmlValidateElementType(ctxt);
4823     if ((ret == -3) && (warn)) {
4824         VWARNING(ctxt->userData,
4825            "Content model for Element %s is ambiguous\n", name);
4826     } else if (ret == -2) {
4827         /*
4828          * An entities reference appeared at this level.
4829          * Buid a minimal representation of this node content
4830          * sufficient to run the validation process on it
4831          */
4832         DEBUG_VALID_MSG("Found an entity reference, linearizing");
4833         cur = child;
4834         while (cur != NULL) {
4835             switch (cur->type) {
4836                 case XML_ENTITY_REF_NODE:
4837                     /*
4838                      * Push the current node to be able to roll back
4839                      * and process within the entity
4840                      */
4841                     if ((cur->children != NULL) &&
4842                         (cur->children->children != NULL)) {
4843                         nodeVPush(ctxt, cur);
4844                         cur = cur->children->children;
4845                         continue;
4846                     }
4847                     break;
4848                 case XML_TEXT_NODE:
4849                     if (xmlIsBlankNode(cur))
4850                         break;
4851                     /* no break on purpose */
4852                 case XML_CDATA_SECTION_NODE:
4853                     /* no break on purpose */
4854                 case XML_ELEMENT_NODE:
4855                     /*
4856                      * Allocate a new node and minimally fills in
4857                      * what's required
4858                      */
4859                     tmp = (xmlNodePtr) xmlMalloc(sizeof(xmlNode));
4860                     if (tmp == NULL) {
4861                         xmlGenericError(xmlGenericErrorContext,
4862                                 "xmlValidateElementContent : malloc failed\n");
4863                         xmlFreeNodeList(repl);
4864                         ret = -1;
4865                         goto done;
4866                     }
4867                     tmp->type = cur->type;
4868                     tmp->name = cur->name;
4869                     tmp->ns = cur->ns;
4870                     tmp->next = NULL;
4871                     tmp->content = NULL;
4872                     if (repl == NULL)
4873                         repl = last = tmp;
4874                     else {
4875                         last->next = tmp;
4876                         last = tmp;
4877                     }
4878                     if (cur->type == XML_CDATA_SECTION_NODE) {
4879                         /*
4880                          * E59 spaces in CDATA does not match the
4881                          * nonterminal S
4882                          */
4883                         tmp->content = xmlStrdup(BAD_CAST "CDATA");
4884                     }
4885                     break;
4886                 default:
4887                     break;
4888             }
4889             /*
4890              * Switch to next element
4891              */
4892             cur = cur->next;
4893             while (cur == NULL) {
4894                 cur = nodeVPop(ctxt);
4895                 if (cur == NULL)
4896                     break;
4897                 cur = cur->next;
4898             }
4899         }
4900
4901         /*
4902          * Relaunch the validation
4903          */
4904         ctxt->vstate = &ctxt->vstateTab[0];
4905         ctxt->vstateNr = 1;
4906         CONT = cont;
4907         NODE = repl;
4908         DEPTH = 0;
4909         OCCURS = 0;
4910         STATE = 0;
4911         ret = xmlValidateElementType(ctxt);
4912     }
4913 #endif /* LIBXML_REGEXP_ENABLED */
4914     if ((warn) && ((ret != 1) && (ret != -3))) {
4915         if ((ctxt != NULL) && (ctxt->warning != NULL)) {
4916             char expr[5000];
4917             char list[5000];
4918
4919             expr[0] = 0;
4920             xmlSnprintfElementContent(&expr[0], 5000, cont, 1);
4921             list[0] = 0;
4922 #ifndef LIBXML_REGEXP_ENABLED
4923             if (repl != NULL)
4924                 xmlSnprintfElements(&list[0], 5000, repl, 1);
4925             else
4926 #endif /* LIBXML_REGEXP_ENABLED */
4927                 xmlSnprintfElements(&list[0], 5000, child, 1);
4928
4929             if (name != NULL) {
4930                 if (parent != NULL) VECTXT(ctxt, parent);
4931                 VERROR(ctxt->userData,
4932            "Element %s content does not follow the DTD\nExpecting %s, got %s\n",
4933                        name, expr, list);
4934             } else {
4935                 if (parent != NULL) VECTXT(ctxt, parent);
4936                 VERROR(ctxt->userData,
4937            "Element content does not follow the DTD\nExpecting %s, got %s\n",
4938                        expr, list);
4939             }
4940         } else {
4941             if (name != NULL) {
4942                 if (parent != NULL) VECTXT(ctxt, parent);
4943                 VERROR(ctxt->userData,
4944                        "Element %s content does not follow the DTD\n",
4945                        name);
4946             } else {
4947                 if (parent != NULL) VECTXT(ctxt, parent);
4948                 VERROR(ctxt->userData,
4949                        "Element content does not follow the DTD\n");
4950             }
4951         }
4952         ret = 0;
4953     }
4954     if (ret == -3)
4955         ret = 1;
4956
4957 #ifndef  LIBXML_REGEXP_ENABLED
4958 done:
4959     /*
4960      * Deallocate the copy if done, and free up the validation stack
4961      */
4962     while (repl != NULL) {
4963         tmp = repl->next;
4964         xmlFree(repl);
4965         repl = tmp;
4966     }
4967     ctxt->vstateMax = 0;
4968     if (ctxt->vstateTab != NULL) {
4969         xmlFree(ctxt->vstateTab);
4970         ctxt->vstateTab = NULL;
4971     }
4972 #endif
4973     ctxt->nodeMax = 0;
4974     ctxt->nodeNr = 0;
4975     if (ctxt->nodeTab != NULL) {
4976         xmlFree(ctxt->nodeTab);
4977         ctxt->nodeTab = NULL;
4978     }
4979     return(ret);
4980
4981 }
4982
4983 /**
4984  * xmlValidateCdataElement:
4985  * @ctxt:  the validation context
4986  * @doc:  a document instance
4987  * @elem:  an element instance
4988  *
4989  * Check that an element follows #CDATA
4990  *
4991  * returns 1 if valid or 0 otherwise
4992  */
4993 static int
4994 xmlValidateOneCdataElement(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
4995                            xmlNodePtr elem) {
4996     int ret = 1;
4997     xmlNodePtr cur, child;
4998
4999     if ((ctxt == NULL) || (doc == NULL) || (elem == NULL))
5000         return(0);
5001
5002     child = elem->children;
5003
5004     cur = child;
5005     while (cur != NULL) {
5006         switch (cur->type) {
5007             case XML_ENTITY_REF_NODE:
5008                 /*
5009                  * Push the current node to be able to roll back
5010                  * and process within the entity
5011                  */
5012                 if ((cur->children != NULL) &&
5013                     (cur->children->children != NULL)) {
5014                     nodeVPush(ctxt, cur);
5015                     cur = cur->children->children;
5016                     continue;
5017                 }
5018                 break;
5019             case XML_COMMENT_NODE:
5020             case XML_PI_NODE:
5021             case XML_TEXT_NODE:
5022             case XML_CDATA_SECTION_NODE:
5023                 break;
5024             default:
5025                 ret = 0;
5026                 goto done;
5027         }
5028         /*
5029          * Switch to next element
5030          */
5031         cur = cur->next;
5032         while (cur == NULL) {
5033             cur = nodeVPop(ctxt);
5034             if (cur == NULL)
5035                 break;
5036             cur = cur->next;
5037         }
5038     }
5039 done:
5040     ctxt->nodeMax = 0;
5041     ctxt->nodeNr = 0;
5042     if (ctxt->nodeTab != NULL) {
5043         xmlFree(ctxt->nodeTab);
5044         ctxt->nodeTab = NULL;
5045     }
5046     return(ret);
5047 }
5048
5049 /**
5050  * xmlValidateCheckMixed:
5051  * @ctxt:  the validation context
5052  * @cont:  the mixed content model
5053  * @qname:  the qualified name as appearing in the serialization
5054  *
5055  * Check if the given node is part of the content model.
5056  *
5057  * Returns 1 if yes, 0 if no, -1 in case of error
5058  */
5059 static int
5060 xmlValidateCheckMixed(xmlValidCtxtPtr ctxt  ATTRIBUTE_UNUSED,
5061                       xmlElementContentPtr cont, const xmlChar *qname) {
5062     const xmlChar *name;
5063     int plen;
5064     name = xmlSplitQName3(qname, &plen);
5065
5066     if (name == NULL) {
5067         while (cont != NULL) {
5068             if (cont->type == XML_ELEMENT_CONTENT_ELEMENT) {
5069                 if ((cont->prefix == NULL) && (xmlStrEqual(cont->name, qname)))
5070                     return(1);
5071             } else if ((cont->type == XML_ELEMENT_CONTENT_OR) &&
5072                (cont->c1 != NULL) &&
5073                (cont->c1->type == XML_ELEMENT_CONTENT_ELEMENT)){
5074                 if ((cont->c1->prefix == NULL) &&
5075                     (xmlStrEqual(cont->c1->name, qname)))
5076                     return(1);
5077             } else if ((cont->type != XML_ELEMENT_CONTENT_OR) ||
5078                 (cont->c1 == NULL) ||
5079                 (cont->c1->type != XML_ELEMENT_CONTENT_PCDATA)){
5080                 /* Internal error !!! */
5081                 xmlGenericError(xmlGenericErrorContext,
5082                         "Internal: MIXED struct bad\n");
5083                 break;
5084             }
5085             cont = cont->c2;
5086         }
5087     } else {
5088         while (cont != NULL) {
5089             if (cont->type == XML_ELEMENT_CONTENT_ELEMENT) {
5090                 if ((cont->prefix != NULL) &&
5091                     (xmlStrncmp(cont->prefix, qname, plen) == 0) &&
5092                     (xmlStrEqual(cont->name, name)))
5093                     return(1);
5094             } else if ((cont->type == XML_ELEMENT_CONTENT_OR) &&
5095                (cont->c1 != NULL) &&
5096                (cont->c1->type == XML_ELEMENT_CONTENT_ELEMENT)){
5097                 if ((cont->c1->prefix != NULL) &&
5098                     (xmlStrncmp(cont->c1->prefix, qname, plen) == 0) &&
5099                     (xmlStrEqual(cont->c1->name, name)))
5100                     return(1);
5101             } else if ((cont->type != XML_ELEMENT_CONTENT_OR) ||
5102                 (cont->c1 == NULL) ||
5103                 (cont->c1->type != XML_ELEMENT_CONTENT_PCDATA)){
5104                 /* Internal error !!! */
5105                 xmlGenericError(xmlGenericErrorContext,
5106                         "Internal: MIXED struct bad\n");
5107                 break;
5108             }
5109             cont = cont->c2;
5110         }
5111     }
5112     return(0);
5113 }
5114
5115 /**
5116  * xmlValidGetElemDecl:
5117  * @ctxt:  the validation context
5118  * @doc:  a document instance
5119  * @elem:  an element instance
5120  * @extsubset:  pointer, (out) indicate if the declaration was found
5121  *              in the external subset.
5122  *
5123  * Finds a declaration associated to an element in the document.
5124  *
5125  * returns the pointer to the declaration or NULL if not found.
5126  */
5127 static xmlElementPtr
5128 xmlValidGetElemDecl(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
5129                     xmlNodePtr elem, int *extsubset) {
5130     xmlElementPtr elemDecl = NULL;
5131     const xmlChar *prefix = NULL;
5132
5133     if ((elem == NULL) || (elem->name == NULL)) return(NULL);
5134     if (extsubset != NULL)
5135         *extsubset = 0;
5136
5137     /*
5138      * Fetch the declaration for the qualified name
5139      */
5140     if ((elem->ns != NULL) && (elem->ns->prefix != NULL))
5141         prefix = elem->ns->prefix;
5142
5143     if (prefix != NULL) {
5144         elemDecl = xmlGetDtdQElementDesc(doc->intSubset,
5145                                          elem->name, prefix);
5146         if ((elemDecl == NULL) && (doc->extSubset != NULL)) {
5147             elemDecl = xmlGetDtdQElementDesc(doc->extSubset,
5148                                              elem->name, prefix);
5149             if ((elemDecl != NULL) && (extsubset != NULL))
5150                 *extsubset = 1;
5151         }
5152     }
5153
5154     /*
5155      * Fetch the declaration for the non qualified name
5156      * This is "non-strict" validation should be done on the
5157      * full QName but in that case being flexible makes sense.
5158      */
5159     if (elemDecl == NULL) {
5160         elemDecl = xmlGetDtdElementDesc(doc->intSubset, elem->name);
5161         if ((elemDecl == NULL) && (doc->extSubset != NULL)) {
5162             elemDecl = xmlGetDtdElementDesc(doc->extSubset, elem->name);
5163             if ((elemDecl != NULL) && (extsubset != NULL))
5164                 *extsubset = 1;
5165         }
5166     }
5167     if (elemDecl == NULL) {
5168         VECTXT(ctxt, elem);
5169         VERROR(ctxt->userData, "No declaration for element %s\n",
5170                elem->name);
5171     }
5172     return(elemDecl);
5173 }
5174
5175 #ifdef LIBXML_REGEXP_ENABLED
5176 /**
5177  * xmlValidatePushElement:
5178  * @ctxt:  the validation context
5179  * @doc:  a document instance
5180  * @elem:  an element instance
5181  * @qname:  the qualified name as appearing in the serialization
5182  *
5183  * Push a new element start on the validation stack.
5184  *
5185  * returns 1 if no validation problem was found or 0 otherwise
5186  */
5187 int
5188 xmlValidatePushElement(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
5189                        xmlNodePtr elem, const xmlChar *qname) {
5190     int ret = 1;
5191     xmlElementPtr eDecl;
5192     int extsubset = 0;
5193
5194 /* printf("PushElem %s\n", qname); */
5195     if ((ctxt->vstateNr > 0) && (ctxt->vstate != NULL)) {
5196         xmlValidStatePtr state = ctxt->vstate;
5197         xmlElementPtr elemDecl;
5198
5199         /*
5200          * Check the new element agaisnt the content model of the new elem.
5201          */
5202         if (state->elemDecl != NULL) {
5203             elemDecl = state->elemDecl;
5204
5205             switch(elemDecl->etype) {
5206                 case XML_ELEMENT_TYPE_UNDEFINED:
5207                     ret = 0;
5208                     break;
5209                 case XML_ELEMENT_TYPE_EMPTY:
5210                     VECTXT(ctxt, state->node);
5211                     VERROR(ctxt->userData,
5212                "Element %s was declared EMPTY this one has content\n",
5213                            state->node->name);
5214                     ret = 0;
5215                     break;
5216                 case XML_ELEMENT_TYPE_ANY:
5217                     /* I don't think anything is required then */
5218                     break;
5219                 case XML_ELEMENT_TYPE_MIXED:
5220                     /* simple case of declared as #PCDATA */
5221                     if ((elemDecl->content != NULL) &&
5222                         (elemDecl->content->type ==
5223                          XML_ELEMENT_CONTENT_PCDATA)) {
5224                         VECTXT(ctxt, state->node);
5225                         VERROR(ctxt->userData,
5226                "Element %s was declared #PCDATA but contains non text nodes\n",
5227                                 state->node->name);
5228                         ret = 0;
5229                     } else {
5230                         ret = xmlValidateCheckMixed(ctxt, elemDecl->content,
5231                                                     qname);
5232                         if (ret != 1) {
5233                             VECTXT(ctxt, state->node);
5234                             VERROR(ctxt->userData,
5235                "Element %s is not declared in %s list of possible children\n",
5236                                     qname, state->node->name);
5237                         }
5238                     }
5239                     break;
5240                 case XML_ELEMENT_TYPE_ELEMENT:
5241                     /*
5242                      * TODO:
5243                      * VC: Standalone Document Declaration
5244                      *     - element types with element content, if white space
5245                      *       occurs directly within any instance of those types.
5246                      */
5247                     if (state->exec != NULL) {
5248                         ret = xmlRegExecPushString(state->exec, qname, NULL);
5249                         if (ret < 0) {
5250                             VECTXT(ctxt, state->node);
5251                             VERROR(ctxt->userData,
5252                "Element %s content does not follow the DTD\nMisplaced %s\n",
5253                                    state->node->name, qname);
5254                             ret = 0;
5255                         } else {
5256                             ret = 1;
5257                         }
5258                     }
5259                     break;
5260             }
5261         }
5262     }
5263     eDecl = xmlValidGetElemDecl(ctxt, doc, elem, &extsubset);
5264     vstateVPush(ctxt, eDecl, elem);
5265     return(ret);
5266 }
5267
5268 /**
5269  * xmlValidatePushCData:
5270  * @ctxt:  the validation context
5271  * @data:  some character data read
5272  * @len:  the lenght of the data
5273  *
5274  * check the CData parsed for validation in the current stack
5275  *
5276  * returns 1 if no validation problem was found or 0 otherwise
5277  */
5278 int
5279 xmlValidatePushCData(xmlValidCtxtPtr ctxt, const xmlChar *data, int len) {
5280     int ret = 1;
5281
5282 /* printf("CDATA %s %d\n", data, len); */
5283     if (len <= 0)
5284         return(ret);
5285     if ((ctxt->vstateNr > 0) && (ctxt->vstate != NULL)) {
5286         xmlValidStatePtr state = ctxt->vstate;
5287         xmlElementPtr elemDecl;
5288
5289         /*
5290          * Check the new element agaisnt the content model of the new elem.
5291          */
5292         if (state->elemDecl != NULL) {
5293             elemDecl = state->elemDecl;
5294
5295             switch(elemDecl->etype) {
5296                 case XML_ELEMENT_TYPE_UNDEFINED:
5297                     ret = 0;
5298                     break;
5299                 case XML_ELEMENT_TYPE_EMPTY:
5300                     VECTXT(ctxt, state->node);
5301                     VERROR(ctxt->userData,
5302                "Element %s was declared EMPTY this one has content\n",
5303                            state->node->name);
5304                     ret = 0;
5305                     break;
5306                 case XML_ELEMENT_TYPE_ANY:
5307                     break;
5308                 case XML_ELEMENT_TYPE_MIXED:
5309                     break;
5310                 case XML_ELEMENT_TYPE_ELEMENT:
5311                     if (len > 0) {
5312                         int i;
5313
5314                         for (i = 0;i < len;i++) {
5315                             if (!IS_BLANK(data[i])) {
5316                                 VECTXT(ctxt, state->node);
5317                                 VERROR(ctxt->userData,
5318            "Element %s content does not follow the DTD\nText not allowed\n",
5319                                        state->node->name);
5320                                 ret = 0;
5321                                 goto done;
5322                             }
5323                         }
5324                         /*
5325                          * TODO:
5326                          * VC: Standalone Document Declaration
5327                          *  element types with element content, if white space
5328                          *  occurs directly within any instance of those types.
5329                          */
5330                     }
5331                     break;
5332             }
5333         }
5334     }
5335 done:
5336     return(ret);
5337 }
5338
5339 /**
5340  * xmlValidatePopElement:
5341  * @ctxt:  the validation context
5342  * @doc:  a document instance
5343  * @elem:  an element instance
5344  * @qname:  the qualified name as appearing in the serialization
5345  *
5346  * Pop the element end from the validation stack.
5347  *
5348  * returns 1 if no validation problem was found or 0 otherwise
5349  */
5350 int
5351 xmlValidatePopElement(xmlValidCtxtPtr ctxt, xmlDocPtr doc ATTRIBUTE_UNUSED,
5352                       xmlNodePtr elem ATTRIBUTE_UNUSED,
5353                       const xmlChar *qname ATTRIBUTE_UNUSED) {
5354     int ret = 1;
5355
5356 /* printf("PopElem %s\n", qname); */
5357     if ((ctxt->vstateNr > 0) && (ctxt->vstate != NULL)) {
5358         xmlValidStatePtr state = ctxt->vstate;
5359         xmlElementPtr elemDecl;
5360
5361         /*
5362          * Check the new element agaisnt the content model of the new elem.
5363          */
5364         if (state->elemDecl != NULL) {
5365             elemDecl = state->elemDecl;
5366
5367             if (elemDecl->etype == XML_ELEMENT_TYPE_ELEMENT) {
5368                 if (state->exec != NULL) {
5369                     ret = xmlRegExecPushString(state->exec, NULL, NULL);
5370                     if (ret == 0) {
5371                         VECTXT(ctxt, state->node);
5372                         VERROR(ctxt->userData,
5373            "Element %s content does not follow the DTD\nExpecting more child\n",
5374                                state->node->name);
5375                     } else {
5376                         /*
5377                          * previous validation errors should not generate
5378                          * a new one here
5379                          */
5380                         ret = 1;
5381                     }
5382                 }
5383             }
5384         }
5385         vstateVPop(ctxt);
5386     }
5387     return(ret);
5388 }
5389 #endif /* LIBXML_REGEXP_ENABLED */
5390
5391 /**
5392  * xmlValidateOneElement:
5393  * @ctxt:  the validation context
5394  * @doc:  a document instance
5395  * @elem:  an element instance
5396  *
5397  * Try to validate a single element and it's attributes,
5398  * basically it does the following checks as described by the
5399  * XML-1.0 recommendation:
5400  *  - [ VC: Element Valid ]
5401  *  - [ VC: Required Attribute ]
5402  * Then call xmlValidateOneAttribute() for each attribute present.
5403  *
5404  * The ID/IDREF checkings are done separately
5405  *
5406  * returns 1 if valid or 0 otherwise
5407  */
5408
5409 int
5410 xmlValidateOneElement(xmlValidCtxtPtr ctxt, xmlDocPtr doc,
5411                       xmlNodePtr elem) {
5412     xmlElementPtr elemDecl = NULL;
5413     xmlElementContentPtr cont;
5414     xmlAttributePtr attr;
5415     xmlNodePtr child;
5416     int ret = 1, tmp;
5417     const xmlChar *name;
5418     int extsubset = 0;
5419
5420     CHECK_DTD;
5421
5422     if (elem == NULL) return(0);
5423     switch (elem->type) {
5424         case XML_ATTRIBUTE_NODE:
5425             VECTXT(ctxt, elem);
5426             VERROR(ctxt->userData,
5427                    "Attribute element not expected here\n");
5428             return(0);
5429         case XML_TEXT_NODE:
5430             if (elem->children != NULL) {
5431                 VECTXT(ctxt, elem);
5432                 VERROR(ctxt->userData, "Text element has childs !\n");
5433                 return(0);
5434             }
5435             if (elem->properties != NULL) {
5436                 VECTXT(ctxt, elem);
5437                 VERROR(ctxt->userData, "Text element has attributes !\n");
5438                 return(0);
5439             }
5440             if (elem->ns != NULL) {
5441                 VECTXT(ctxt, elem);
5442                 VERROR(ctxt->userData, "Text element has namespace !\n");
5443                 return(0);
5444             }
5445             if (elem->nsDef != NULL) {
5446                 VECTXT(ctxt, elem);
5447                 VERROR(ctxt->userData,
5448                        "Text element carries namespace definitions !\n");
5449                 return(0);
5450             }
5451             if (elem->content == NULL) {
5452                 VECTXT(ctxt, elem);
5453                 VERROR(ctxt->userData,
5454                        "Text element has no content !\n");
5455                 return(0);
5456             }
5457             return(1);
5458         case XML_XINCLUDE_START:
5459         case XML_XINCLUDE_END:
5460             return(1);
5461         case XML_CDATA_SECTION_NODE:
5462         case XML_ENTITY_REF_NODE:
5463         case XML_PI_NODE:
5464         case XML_COMMENT_NODE:
5465             return(1);
5466         case XML_ENTITY_NODE:
5467             VECTXT(ctxt, elem);
5468             VERROR(ctxt->userData,
5469                    "Entity element not expected here\n");
5470             return(0);
5471         case XML_NOTATION_NODE:
5472             VECTXT(ctxt, elem);
5473             VERROR(ctxt->userData,
5474                    "Notation element not expected here\n");
5475             return(0);
5476         case XML_DOCUMENT_NODE:
5477         case XML_DOCUMENT_TYPE_NODE:
5478         case XML_DOCUMENT_FRAG_NODE:
5479             VECTXT(ctxt, elem);
5480             VERROR(ctxt->userData,
5481                    "Document element not expected here\n");
5482             return(0);
5483         case XML_HTML_DOCUMENT_NODE:
5484             VECTXT(ctxt, elem);
5485             VERROR(ctxt->userData,
5486                    "\n");
5487             return(0);
5488         case XML_ELEMENT_NODE:
5489             break;
5490         default:
5491             VECTXT(ctxt, elem);
5492             VERROR(ctxt->userData,
5493                    "unknown element type %d\n", elem->type);
5494             return(0);
5495     }
5496
5497     /*
5498      * Fetch the declaration
5499      */
5500     elemDecl = xmlValidGetElemDecl(ctxt, doc, elem, &extsubset);
5501     if (elemDecl == NULL)
5502         return(0);
5503
5504     /*
5505      * If vstateNr is not zero that means continuous validation is
5506      * activated, do not try to check the content model at that level.
5507      */
5508     if (ctxt->vstateNr == 0) {
5509     /* Check that the element content matches the definition */
5510     switch (elemDecl->etype) {
5511         case XML_ELEMENT_TYPE_UNDEFINED:
5512             VECTXT(ctxt, elem);
5513             VERROR(ctxt->userData, "No declaration for element %s\n",
5514                    elem->name);
5515             return(0);
5516         case XML_ELEMENT_TYPE_EMPTY:
5517             if (elem->children != NULL) {
5518                 VECTXT(ctxt, elem);
5519                 VERROR(ctxt->userData,
5520                "Element %s was declared EMPTY this one has content\n",
5521                        elem->name);
5522                 ret = 0;
5523             }
5524             break;
5525         case XML_ELEMENT_TYPE_ANY:
5526             /* I don't think anything is required then */
5527             break;
5528         case XML_ELEMENT_TYPE_MIXED:
5529
5530             /* simple case of declared as #PCDATA */
5531             if ((elemDecl->content != NULL) &&
5532                 (elemDecl->content->type == XML_ELEMENT_CONTENT_PCDATA)) {
5533                 ret = xmlValidateOneCdataElement(ctxt, doc, elem);
5534                 if (!ret) {
5535                     VECTXT(ctxt, elem);
5536                     VERROR(ctxt->userData,
5537                "Element %s was declared #PCDATA but contains non text nodes\n",
5538                            elem->name);
5539                 }
5540                 break;
5541             }
5542             child = elem->children;
5543             /* Hum, this start to get messy */
5544             while (child != NULL) {
5545                 if (child->type == XML_ELEMENT_NODE) {
5546                     name = child->name;
5547                     if ((child->ns != NULL) && (child->ns->prefix != NULL)) {
5548                         xmlChar fn[50];
5549                         xmlChar *fullname;
5550
5551                         fullname = xmlBuildQName(child->name, child->ns->prefix,
5552                                                  fn, 50);
5553                         if (fullname == NULL)
5554                             return(0);
5555                         cont = elemDecl->content;
5556                         while (cont != NULL) {
5557                             if (cont->type == XML_ELEMENT_CONTENT_ELEMENT) {
5558                                 if (xmlStrEqual(cont->name, fullname))
5559                                     break;
5560                             } else if ((cont->type == XML_ELEMENT_CONTENT_OR) &&
5561                                (cont->c1 != NULL) &&
5562                                (cont->c1->type == XML_ELEMENT_CONTENT_ELEMENT)){
5563                                 if (xmlStrEqual(cont->c1->name, fullname))
5564                                     break;
5565                             } else if ((cont->type != XML_ELEMENT_CONTENT_OR) ||
5566                                 (cont->c1 == NULL) ||
5567                                 (cont->c1->type != XML_ELEMENT_CONTENT_PCDATA)){
5568                                 /* Internal error !!! */
5569                                 xmlGenericError(xmlGenericErrorContext,
5570                                         "Internal: MIXED struct bad\n");
5571                                 break;
5572                             }
5573                             cont = cont->c2;
5574                         }
5575                         if ((fullname != fn) && (fullname != child->name))
5576                             xmlFree(fullname);
5577                         if (cont != NULL)
5578                             goto child_ok;
5579                     }
5580                     cont = elemDecl->content;
5581                     while (cont != NULL) {
5582                         if (cont->type == XML_ELEMENT_CONTENT_ELEMENT) {
5583                             if (xmlStrEqual(cont->name, name)) break;
5584                         } else if ((cont->type == XML_ELEMENT_CONTENT_OR) &&
5585                            (cont->c1 != NULL) &&
5586                            (cont->c1->type == XML_ELEMENT_CONTENT_ELEMENT)) {
5587                             if (xmlStrEqual(cont->c1->name, name)) break;
5588                         } else if ((cont->type != XML_ELEMENT_CONTENT_OR) ||
5589                             (cont->c1 == NULL) ||
5590                             (cont->c1->type != XML_ELEMENT_CONTENT_PCDATA)) {
5591                             /* Internal error !!! */
5592                             xmlGenericError(xmlGenericErrorContext,
5593                                     "Internal: MIXED struct bad\n");
5594                             break;
5595                         }
5596                         cont = cont->c2;
5597                     }
5598                     if (cont == NULL) {
5599                         VECTXT(ctxt, elem);
5600                         VERROR(ctxt->userData,
5601                "Element %s is not declared in %s list of possible children\n",
5602                                name, elem->name);
5603                         ret = 0;
5604                     }
5605                 }
5606 child_ok:
5607                 child = child->next;
5608             }
5609             break;
5610         case XML_ELEMENT_TYPE_ELEMENT:
5611             if ((doc->standalone == 1) && (extsubset == 1)) {
5612                 /*
5613                  * VC: Standalone Document Declaration
5614                  *     - element types with element content, if white space
5615                  *       occurs directly within any instance of those types.
5616                  */
5617                 child = elem->children;
5618                 while (child != NULL) {
5619                     if (child->type == XML_TEXT_NODE) {
5620                         const xmlChar *content = child->content;
5621
5622                         while (IS_BLANK(*content))
5623                             content++;
5624                         if (*content == 0) {
5625                             VECTXT(ctxt, elem);
5626                             VERROR(ctxt->userData,
5627 "standalone: %s declared in the external subset contains white spaces nodes\n",
5628                                    elem->name);
5629                             ret = 0;
5630                             break;
5631                         }
5632                     }
5633                     child =child->next;
5634                 }
5635             }
5636             child = elem->children;
5637             cont = elemDecl->content;
5638             tmp = xmlValidateElementContent(ctxt, child, elemDecl, 1, elem);
5639             if (tmp <= 0)
5640                 ret = tmp;
5641             break;
5642     }
5643     } /* not continuous */
5644
5645     /* [ VC: Required Attribute ] */
5646     attr = elemDecl->attributes;
5647     while (attr != NULL) {
5648         if (attr->def == XML_ATTRIBUTE_REQUIRED) {
5649             int qualified = -1;
5650
5651             if ((attr->prefix == NULL) &&
5652                 (xmlStrEqual(attr->name, BAD_CAST "xmlns"))) {
5653                 xmlNsPtr ns;
5654
5655                 ns = elem->nsDef;
5656                 while (ns != NULL) {
5657                     if (ns->prefix == NULL)
5658                         goto found;
5659                     ns = ns->next;
5660                 }
5661             } else if (xmlStrEqual(attr->prefix, BAD_CAST "xmlns")) {
5662                 xmlNsPtr ns;
5663
5664                 ns = elem->nsDef;
5665                 while (ns != NULL) {
5666                     if (xmlStrEqual(attr->name, ns->prefix))
5667                         goto found;
5668                     ns = ns->next;
5669                 }
5670             } else {
5671                 xmlAttrPtr attrib;
5672
5673                 attrib = elem->properties;
5674                 while (attrib != NULL) {
5675                     if (xmlStrEqual(attrib->name, attr->name)) {
5676                         if (attr->prefix != NULL) {
5677                             xmlNsPtr nameSpace = attrib->ns;
5678
5679                             if (nameSpace == NULL)
5680                                 nameSpace = elem->ns;
5681                             /*
5682                              * qualified names handling is problematic, having a
5683                              * different prefix should be possible but DTDs don't
5684                              * allow to define the URI instead of the prefix :-(
5685                              */
5686                             if (nameSpace == NULL) {
5687                                 if (qualified < 0)
5688                                     qualified = 0;
5689                             } else if (!xmlStrEqual(nameSpace->prefix,
5690                                                     attr->prefix)) {
5691                                 if (qualified < 1)
5692                                     qualified = 1;
5693                             } else
5694                                 goto found;
5695                         } else {
5696                             /*
5697                              * We should allow applications to define namespaces
5698                              * for their application even if the DTD doesn't
5699                              * carry one, otherwise, basically we would always
5700                              * break.
5701                              */
5702                             goto found;
5703                         }
5704                     }
5705                     attrib = attrib->next;
5706                 }
5707             }
5708             if (qualified == -1) {
5709                 if (attr->prefix == NULL) {
5710                     VECTXT(ctxt, elem);
5711                     VERROR(ctxt->userData,
5712                        "Element %s does not carry attribute %s\n",
5713                            elem->name, attr->name);
5714                     ret = 0;
5715                 } else {
5716                     VECTXT(ctxt, elem);
5717                     VERROR(ctxt->userData,
5718                        "Element %s does not carry attribute %s:%s\n",
5719                            elem->name, attr->prefix,attr->name);
5720                     ret = 0;
5721                 }
5722             } else if (qualified == 0) {
5723                 VWARNING(ctxt->userData,
5724                    "Element %s required attribute %s:%s has no prefix\n",
5725                        elem->name, attr->prefix,attr->name);
5726             } else if (qualified == 1) {
5727                 VWARNING(ctxt->userData,
5728                    "Element %s required attribute %s:%s has different prefix\n",
5729                        elem->name, attr->prefix,attr->name);
5730             }
5731         } else if (attr->def == XML_ATTRIBUTE_FIXED) {
5732             /*
5733              * Special tests checking #FIXED namespace declarations
5734              * have the right value since this is not done as an
5735              * attribute checking
5736              */
5737             if ((attr->prefix == NULL) &&
5738                 (xmlStrEqual(attr->name, BAD_CAST "xmlns"))) {
5739                 xmlNsPtr ns;
5740
5741                 ns = elem->nsDef;
5742                 while (ns != NULL) {
5743                     if (ns->prefix == NULL) {
5744                         if (!xmlStrEqual(attr->defaultValue, ns->href)) {
5745                             VECTXT(ctxt, elem);
5746                             VERROR(ctxt->userData,
5747    "Element %s namespace name for default namespace does not match the DTD\n",
5748                                    elem->name);
5749                             ret = 0;
5750                         }
5751                         goto found;
5752                     }
5753                     ns = ns->next;
5754                 }
5755             } else if (xmlStrEqual(attr->prefix, BAD_CAST "xmlns")) {
5756                 xmlNsPtr ns;
5757
5758                 ns = elem->nsDef;
5759                 while (ns != NULL) {
5760                     if (xmlStrEqual(attr->name, ns->prefix)) {
5761                         if (!xmlStrEqual(attr->defaultValue, ns->href)) {
5762                             VECTXT(ctxt, elem);
5763                             VERROR(ctxt->userData,
5764                    "Element %s namespace name for %s does not match the DTD\n",
5765                                    elem->name, ns->prefix);
5766                             ret = 0;
5767                         }
5768                         goto found;
5769                     }
5770                     ns = ns->next;
5771                 }
5772             }
5773         }
5774 found:
5775         attr = attr->nexth;
5776     }
5777     return(ret);
5778 }
5779
5780 /**
5781  * xmlValidateRoot:
5782  * @ctxt:  the validation context
5783  * @doc:  a document instance
5784  *
5785  * Try to validate a the root element
5786  * basically it does the following check as described by the
5787  * XML-1.0 recommendation:
5788  *  - [ VC: Root Element Type ]
5789  * it doesn't try to recurse or apply other check to the element
5790  *
5791  * returns 1 if valid or 0 otherwise
5792  */
5793
5794 int
5795 xmlValidateRoot(xmlValidCtxtPtr ctxt, xmlDocPtr doc) {
5796     xmlNodePtr root;
5797     int ret;
5798
5799     if (doc == NULL) return(0);
5800
5801     root = xmlDocGetRootElement(doc);
5802     if ((root == NULL) || (root->name == NULL)) {
5803         VERROR(ctxt->userData, "Not valid: no root element\n");
5804         return(0);
5805     }
5806
5807     /*
5808      * When doing post validation against a separate DTD, those may
5809      * no internal subset has been generated
5810      */
5811     if ((doc->intSubset != NULL) &&
5812         (doc->intSubset->name != NULL)) {
5813         /*
5814          * Check first the document root against the NQName
5815          */
5816         if (!xmlStrEqual(doc->intSubset->name, root->name)) {
5817             if ((root->ns != NULL) && (root->ns->prefix != NULL)) {
5818                 xmlChar fn[50];
5819                 xmlChar *fullname;
5820
5821                 fullname = xmlBuildQName(root->name, root->ns->prefix, fn, 50);
5822                 if (fullname == NULL) {
5823                     VERROR(ctxt->userData, "Out of memory\n");
5824                     return(0);
5825                 }
5826                 ret = xmlStrEqual(doc->intSubset->name, fullname);
5827                 if ((fullname != fn) && (fullname != root->name))
5828                     xmlFree(fullname);
5829                 if (ret == 1)
5830                     goto name_ok;
5831             }
5832             if ((xmlStrEqual(doc->intSubset->name, BAD_CAST "HTML")) &&
5833                 (xmlStrEqual(root->name, BAD_CAST "html")))
5834                 goto name_ok;
5835             VECTXT(ctxt, root);
5836             VERROR(ctxt->userData,
5837                    "Not valid: root and DTD name do not match '%s' and '%s'\n",
5838                    root->name, doc->intSubset->name);
5839             return(0);
5840
5841         }
5842     }
5843 name_ok:
5844     return(1);
5845 }
5846
5847
5848 /**
5849  * xmlValidateElement:
5850  * @ctxt:  the validation context
5851  * @doc:  a document instance
5852  * @elem:  an element instance
5853  *
5854  * Try to validate the subtree under an element
5855  *
5856  * returns 1 if valid or 0 otherwise
5857  */
5858
5859 int
5860 xmlValidateElement(xmlValidCtxtPtr ctxt, xmlDocPtr doc, xmlNodePtr elem) {
5861     xmlNodePtr child;
5862     xmlAttrPtr attr;
5863     xmlChar *value;
5864     int ret = 1;
5865
5866     if (elem == NULL) return(0);
5867
5868     /*
5869      * XInclude elements were added after parsing in the infoset,
5870      * they don't really mean anything validation wise.
5871      */
5872     if ((elem->type == XML_XINCLUDE_START) ||
5873         (elem->type == XML_XINCLUDE_END))
5874         return(1);
5875
5876     CHECK_DTD;
5877
5878     /*
5879      * Entities references have to be handled separately
5880      */
5881     if (elem->type == XML_ENTITY_REF_NODE) {
5882         return(1);
5883     }
5884
5885     ret &= xmlValidateOneElement(ctxt, doc, elem);
5886     attr = elem->properties;
5887     while(attr != NULL) {
5888         value = xmlNodeListGetString(doc, attr->children, 0);
5889         ret &= xmlValidateOneAttribute(ctxt, doc, elem, attr, value);
5890         if (value != NULL)
5891             xmlFree(value);
5892         attr= attr->next;
5893     }
5894     child = elem->children;
5895     while (child != NULL) {
5896         ret &= xmlValidateElement(ctxt, doc, child);
5897         child = child->next;
5898     }
5899
5900     return(ret);
5901 }
5902
5903 /**
5904  * xmlValidateRef:
5905  * @ref:   A reference to be validated
5906  * @ctxt:  Validation context
5907  * @name:  Name of ID we are searching for
5908  *
5909  */
5910 static void
5911 xmlValidateRef(xmlRefPtr ref, xmlValidCtxtPtr ctxt,
5912                            const xmlChar *name) {
5913     xmlAttrPtr id;
5914     xmlAttrPtr attr;
5915
5916     if (ref == NULL)
5917         return;
5918     if ((ref->attr == NULL) && (ref->name == NULL))
5919         return;
5920     attr = ref->attr;
5921     if (attr == NULL) {
5922         xmlChar *dup, *str = NULL, *cur, save;
5923
5924         dup = xmlStrdup(name);
5925         if (dup == NULL) {
5926             ctxt->valid = 0;
5927             return;
5928         }
5929         cur = dup;
5930         while (*cur != 0) {
5931             str = cur;
5932             while ((*cur != 0) && (!IS_BLANK(*cur))) cur++;
5933             save = *cur;
5934             *cur = 0;
5935             id = xmlGetID(ctxt->doc, str);
5936             if (id == NULL) {
5937                 VERROR(ctxt->userData,
5938            "attribute %s line %d references an unknown ID \"%s\"\n",
5939                        ref->name, ref->lineno, str);
5940                 ctxt->valid = 0;
5941             }
5942             if (save == 0)
5943                 break;
5944             *cur = save;
5945             while (IS_BLANK(*cur)) cur++;
5946         }
5947         xmlFree(dup);
5948     } else if (attr->atype == XML_ATTRIBUTE_IDREF) {
5949         id = xmlGetID(ctxt->doc, name);
5950         if (id == NULL) {
5951             VECTXT(ctxt, attr->parent);
5952             VERROR(ctxt->userData,
5953            "IDREF attribute %s references an unknown ID \"%s\"\n",
5954                    attr->name, name);
5955             ctxt->valid = 0;
5956         }
5957     } else if (attr->atype == XML_ATTRIBUTE_IDREFS) {
5958         xmlChar *dup, *str = NULL, *cur, save;
5959
5960         dup = xmlStrdup(name);
5961         if (dup == NULL) {
5962             ctxt->valid = 0;
5963             return;
5964         }
5965         cur = dup;
5966         while (*cur != 0) {
5967             str = cur;
5968             while ((*cur != 0) && (!IS_BLANK(*cur))) cur++;
5969             save = *cur;
5970             *cur = 0;
5971             id = xmlGetID(ctxt->doc, str);
5972             if (id == NULL) {
5973                 VECTXT(ctxt, attr->parent);
5974                 VERROR(ctxt->userData,
5975            "IDREFS attribute %s references an unknown ID \"%s\"\n",
5976                        attr->name, str);
5977                 ctxt->valid = 0;
5978             }
5979             if (save == 0)
5980                 break;
5981             *cur = save;
5982             while (IS_BLANK(*cur)) cur++;
5983         }
5984         xmlFree(dup);
5985     }
5986 }
5987
5988 /**
5989  * xmlWalkValidateList:
5990  * @data:  Contents of current link
5991  * @user:  Value supplied by the user
5992  *
5993  * Returns 0 to abort the walk or 1 to continue
5994  */
5995 static int
5996 xmlWalkValidateList(const void *data, const void *user)
5997 {
5998         xmlValidateMemoPtr memo = (xmlValidateMemoPtr)user;
5999         xmlValidateRef((xmlRefPtr)data, memo->ctxt, memo->name);
6000         return 1;
6001 }
6002
6003 /**
6004  * xmlValidateCheckRefCallback:
6005  * @ref_list:  List of references
6006  * @ctxt:  Validation context
6007  * @name:  Name of ID we are searching for
6008  *
6009  */
6010 static void
6011 xmlValidateCheckRefCallback(xmlListPtr ref_list, xmlValidCtxtPtr ctxt,
6012                            const xmlChar *name) {
6013     xmlValidateMemo memo;
6014
6015     if (ref_list == NULL)
6016         return;
6017     memo.ctxt = ctxt;
6018     memo.name = name;
6019
6020     xmlListWalk(ref_list, xmlWalkValidateList, &memo);
6021
6022 }
6023
6024 /**
6025  * xmlValidateDocumentFinal:
6026  * @ctxt:  the validation context
6027  * @doc:  a document instance
6028  *
6029  * Does the final step for the document validation once all the
6030  * incremental validation steps have been completed
6031  *
6032  * basically it does the following checks described by the XML Rec
6033  *
6034  * Check all the IDREF/IDREFS attributes definition for validity
6035  *
6036  * returns 1 if valid or 0 otherwise
6037  */
6038
6039 int
6040 xmlValidateDocumentFinal(xmlValidCtxtPtr ctxt, xmlDocPtr doc) {
6041     xmlRefTablePtr table;
6042
6043     if (doc == NULL) {
6044         xmlGenericError(xmlGenericErrorContext,
6045                 "xmlValidateDocumentFinal: doc == NULL\n");
6046         return(0);
6047     }
6048
6049     /*
6050      * Check all the NOTATION/NOTATIONS attributes
6051      */
6052     /*
6053      * Check all the ENTITY/ENTITIES attributes definition for validity
6054      */
6055     /*
6056      * Check all the IDREF/IDREFS attributes definition for validity
6057      */
6058     table = (xmlRefTablePtr) doc->refs;
6059     ctxt->doc = doc;
6060     ctxt->valid = 1;
6061     xmlHashScan(table, (xmlHashScanner) xmlValidateCheckRefCallback, ctxt);
6062     return(ctxt->valid);
6063 }
6064
6065 /**
6066  * xmlValidateDtd:
6067  * @ctxt:  the validation context
6068  * @doc:  a document instance
6069  * @dtd:  a dtd instance
6070  *
6071  * Try to validate the document against the dtd instance
6072  *
6073  * basically it does check all the definitions in the DtD.
6074  *
6075  * returns 1 if valid or 0 otherwise
6076  */
6077
6078 int
6079 xmlValidateDtd(xmlValidCtxtPtr ctxt, xmlDocPtr doc, xmlDtdPtr dtd) {
6080     int ret;
6081     xmlDtdPtr oldExt;
6082     xmlNodePtr root;
6083
6084     if (dtd == NULL) return(0);
6085     if (doc == NULL) return(0);
6086     oldExt = doc->extSubset;
6087     doc->extSubset = dtd;
6088     ret = xmlValidateRoot(ctxt, doc);
6089     if (ret == 0) {
6090         doc->extSubset = oldExt;
6091         return(ret);
6092     }
6093     if (doc->ids != NULL) {
6094           xmlFreeIDTable(doc->ids);
6095           doc->ids = NULL;
6096     }
6097     if (doc->refs != NULL) {
6098           xmlFreeRefTable(doc->refs);
6099           doc->refs = NULL;
6100     }
6101     root = xmlDocGetRootElement(doc);
6102     ret = xmlValidateElement(ctxt, doc, root);
6103     ret &= xmlValidateDocumentFinal(ctxt, doc);
6104     doc->extSubset = oldExt;
6105     return(ret);
6106 }
6107
6108 static void
6109 xmlValidateNotationCallback(xmlEntityPtr cur, xmlValidCtxtPtr ctxt,
6110                             const xmlChar *name ATTRIBUTE_UNUSED) {
6111     if (cur == NULL)
6112         return;
6113     if (cur->etype == XML_EXTERNAL_GENERAL_UNPARSED_ENTITY) {
6114         xmlChar *notation = cur->content;
6115
6116         if (notation != NULL) {
6117             int ret;
6118
6119             ret = xmlValidateNotationUse(ctxt, cur->doc, notation);
6120             if (ret != 1) {
6121                 ctxt->valid = 0;
6122             }
6123         }
6124     }
6125 }
6126
6127 static void
6128 xmlValidateAttributeCallback(xmlAttributePtr cur, xmlValidCtxtPtr ctxt,
6129                             const xmlChar *name ATTRIBUTE_UNUSED) {
6130     int ret;
6131     xmlDocPtr doc;
6132     xmlElementPtr elem;
6133
6134     if (cur == NULL)
6135         return;
6136     switch (cur->atype) {
6137         case XML_ATTRIBUTE_CDATA:
6138         case XML_ATTRIBUTE_ID:
6139         case XML_ATTRIBUTE_IDREF        :
6140         case XML_ATTRIBUTE_IDREFS:
6141         case XML_ATTRIBUTE_NMTOKEN:
6142         case XML_ATTRIBUTE_NMTOKENS:
6143         case XML_ATTRIBUTE_ENUMERATION:
6144             break;
6145         case XML_ATTRIBUTE_ENTITY:
6146         case XML_ATTRIBUTE_ENTITIES:
6147         case XML_ATTRIBUTE_NOTATION:
6148             if (cur->defaultValue != NULL) {
6149
6150                 ret = xmlValidateAttributeValue2(ctxt, ctxt->doc, cur->name,
6151                                                  cur->atype, cur->defaultValue);
6152                 if ((ret == 0) && (ctxt->valid == 1))
6153                     ctxt->valid = 0;
6154             }
6155             if (cur->tree != NULL) {
6156                 xmlEnumerationPtr tree = cur->tree;
6157                 while (tree != NULL) {
6158                     ret = xmlValidateAttributeValue2(ctxt, ctxt->doc,
6159                                     cur->name, cur->atype, tree->name);
6160                     if ((ret == 0) && (ctxt->valid == 1))
6161                         ctxt->valid = 0;
6162                     tree = tree->next;
6163                 }
6164             }
6165     }
6166     if (cur->atype == XML_ATTRIBUTE_NOTATION) {
6167         doc = cur->doc;
6168         if ((doc == NULL) || (cur->elem == NULL)) {
6169             VERROR(ctxt->userData,
6170                    "xmlValidateAttributeCallback(%s): internal error\n",
6171                    cur->name);
6172             return;
6173         }
6174         elem = xmlGetDtdElementDesc(doc->intSubset, cur->elem);
6175         if (elem == NULL)
6176             elem = xmlGetDtdElementDesc(doc->extSubset, cur->elem);
6177         if (elem == NULL) {
6178             VERROR(ctxt->userData,
6179                    "attribute %s: could not find decl for element %s\n",
6180                    cur->name, cur->elem);
6181             return;
6182         }
6183         if (elem->etype == XML_ELEMENT_TYPE_EMPTY) {
6184             VERROR(ctxt->userData,
6185                    "NOTATION attribute %s declared for EMPTY element %s\n",
6186                    cur->name, cur->elem);
6187             ctxt->valid = 0;
6188         }
6189     }
6190 }
6191
6192 /**
6193  * xmlValidateDtdFinal:
6194  * @ctxt:  the validation context
6195  * @doc:  a document instance
6196  *
6197  * Does the final step for the dtds validation once all the
6198  * subsets have been parsed
6199  *
6200  * basically it does the following checks described by the XML Rec
6201  * - check that ENTITY and ENTITIES type attributes default or
6202  *   possible values matches one of the defined entities.
6203  * - check that NOTATION type attributes default or
6204  *   possible values matches one of the defined notations.
6205  *
6206  * returns 1 if valid or 0 if invalid and -1 if not well-formed
6207  */
6208
6209 int
6210 xmlValidateDtdFinal(xmlValidCtxtPtr ctxt, xmlDocPtr doc) {
6211     xmlDtdPtr dtd;
6212     xmlAttributeTablePtr table;
6213     xmlEntitiesTablePtr entities;
6214
6215     if (doc == NULL) return(0);
6216     if ((doc->intSubset == NULL) && (doc->extSubset == NULL))
6217         return(0);
6218     ctxt->doc = doc;
6219     ctxt->valid = 1;
6220     dtd = doc->intSubset;
6221     if ((dtd != NULL) && (dtd->attributes != NULL)) {
6222         table = (xmlAttributeTablePtr) dtd->attributes;
6223         xmlHashScan(table, (xmlHashScanner) xmlValidateAttributeCallback, ctxt);
6224     }
6225     if ((dtd != NULL) && (dtd->entities != NULL)) {
6226         entities = (xmlEntitiesTablePtr) dtd->entities;
6227         xmlHashScan(entities, (xmlHashScanner) xmlValidateNotationCallback,
6228                     ctxt);
6229     }
6230     dtd = doc->extSubset;
6231     if ((dtd != NULL) && (dtd->attributes != NULL)) {
6232         table = (xmlAttributeTablePtr) dtd->attributes;
6233         xmlHashScan(table, (xmlHashScanner) xmlValidateAttributeCallback, ctxt);
6234     }
6235     if ((dtd != NULL) && (dtd->entities != NULL)) {
6236         entities = (xmlEntitiesTablePtr) dtd->entities;
6237         xmlHashScan(entities, (xmlHashScanner) xmlValidateNotationCallback,
6238                     ctxt);
6239     }
6240     return(ctxt->valid);
6241 }
6242
6243 /**
6244  * xmlValidateDocument:
6245  * @ctxt:  the validation context
6246  * @doc:  a document instance
6247  *
6248  * Try to validate the document instance
6249  *
6250  * basically it does the all the checks described by the XML Rec
6251  * i.e. validates the internal and external subset (if present)
6252  * and validate the document tree.
6253  *
6254  * returns 1 if valid or 0 otherwise
6255  */
6256
6257 int
6258 xmlValidateDocument(xmlValidCtxtPtr ctxt, xmlDocPtr doc) {
6259     int ret;
6260     xmlNodePtr root;
6261
6262     if ((doc->intSubset == NULL) && (doc->extSubset == NULL)) {
6263         VERROR(ctxt->userData, "no DTD found!\n" );
6264         return(0);
6265     }
6266     if ((doc->intSubset != NULL) && ((doc->intSubset->SystemID != NULL) ||
6267         (doc->intSubset->ExternalID != NULL)) && (doc->extSubset == NULL)) {
6268         doc->extSubset = xmlParseDTD(doc->intSubset->ExternalID,
6269                                      doc->intSubset->SystemID);
6270         if (doc->extSubset == NULL) {
6271             if (doc->intSubset->SystemID != NULL) {
6272                 VERROR(ctxt->userData,
6273                        "Could not load the external subset \"%s\"\n",
6274                        doc->intSubset->SystemID);
6275             } else {
6276                 VERROR(ctxt->userData,
6277                        "Could not load the external subset \"%s\"\n",
6278                        doc->intSubset->ExternalID);
6279             }
6280             return(0);
6281         }
6282     }
6283
6284     if (doc->ids != NULL) {
6285           xmlFreeIDTable(doc->ids);
6286           doc->ids = NULL;
6287     }
6288     if (doc->refs != NULL) {
6289           xmlFreeRefTable(doc->refs);
6290           doc->refs = NULL;
6291     }
6292     ret = xmlValidateDtdFinal(ctxt, doc);
6293     if (!xmlValidateRoot(ctxt, doc)) return(0);
6294
6295     root = xmlDocGetRootElement(doc);
6296     ret &= xmlValidateElement(ctxt, doc, root);
6297     ret &= xmlValidateDocumentFinal(ctxt, doc);
6298     return(ret);
6299 }
6300
6301
6302 /************************************************************************
6303  *                                                                      *
6304  *              Routines for dynamic validation editing                 *
6305  *                                                                      *
6306  ************************************************************************/
6307
6308 /**
6309  * xmlValidGetPotentialChildren:
6310  * @ctree:  an element content tree
6311  * @list:  an array to store the list of child names
6312  * @len:  a pointer to the number of element in the list
6313  * @max:  the size of the array
6314  *
6315  * Build/extend a list of  potential children allowed by the content tree
6316  *
6317  * returns the number of element in the list, or -1 in case of error.
6318  */
6319
6320 int
6321 xmlValidGetPotentialChildren(xmlElementContent *ctree, const xmlChar **list,
6322                              int *len, int max) {
6323     int i;
6324
6325     if ((ctree == NULL) || (list == NULL) || (len == NULL))
6326         return(-1);
6327     if (*len >= max) return(*len);
6328
6329     switch (ctree->type) {
6330         case XML_ELEMENT_CONTENT_PCDATA:
6331             for (i = 0; i < *len;i++)
6332                 if (xmlStrEqual(BAD_CAST "#PCDATA", list[i])) return(*len);
6333             list[(*len)++] = BAD_CAST "#PCDATA";
6334             break;
6335         case XML_ELEMENT_CONTENT_ELEMENT:
6336             for (i = 0; i < *len;i++)
6337                 if (xmlStrEqual(ctree->name, list[i])) return(*len);
6338             list[(*len)++] = ctree->name;
6339             break;
6340         case XML_ELEMENT_CONTENT_SEQ:
6341             xmlValidGetPotentialChildren(ctree->c1, list, len, max);
6342             xmlValidGetPotentialChildren(ctree->c2, list, len, max);
6343             break;
6344         case XML_ELEMENT_CONTENT_OR:
6345             xmlValidGetPotentialChildren(ctree->c1, list, len, max);
6346             xmlValidGetPotentialChildren(ctree->c2, list, len, max);
6347             break;
6348    }
6349
6350    return(*len);
6351 }
6352
6353 /**
6354  * xmlValidGetValidElements:
6355  * @prev:  an element to insert after
6356  * @next:  an element to insert next
6357  * @list:  an array to store the list of child names
6358  * @max:  the size of the array
6359  *
6360  * This function returns the list of authorized children to insert
6361  * within an existing tree while respecting the validity constraints
6362  * forced by the Dtd. The insertion point is defined using @prev and
6363  * @next in the following ways:
6364  *  to insert before 'node': xmlValidGetValidElements(node->prev, node, ...
6365  *  to insert next 'node': xmlValidGetValidElements(node, node->next, ...
6366  *  to replace 'node': xmlValidGetValidElements(node->prev, node->next, ...
6367  *  to prepend a child to 'node': xmlValidGetValidElements(NULL, node->childs,
6368  *  to append a child to 'node': xmlValidGetValidElements(node->last, NULL, ...
6369  *
6370  * pointers to the element names are inserted at the beginning of the array
6371  * and do not need to be freed.
6372  *
6373  * returns the number of element in the list, or -1 in case of error. If
6374  *    the function returns the value @max the caller is invited to grow the
6375  *    receiving array and retry.
6376  */
6377
6378 int
6379 xmlValidGetValidElements(xmlNode *prev, xmlNode *next, const xmlChar **list,
6380                          int max) {
6381     xmlValidCtxt vctxt;
6382     int nb_valid_elements = 0;
6383     const xmlChar *elements[256];
6384     int nb_elements = 0, i;
6385     const xmlChar *name;
6386
6387     xmlNode *ref_node;
6388     xmlNode *parent;
6389     xmlNode *test_node;
6390
6391     xmlNode *prev_next;
6392     xmlNode *next_prev;
6393     xmlNode *parent_childs;
6394     xmlNode *parent_last;
6395
6396     xmlElement *element_desc;
6397
6398     memset(&vctxt, 0, sizeof (xmlValidCtxt));
6399
6400     if (prev == NULL && next == NULL)
6401         return(-1);
6402
6403     if (list == NULL) return(-1);
6404     if (max <= 0) return(-1);
6405
6406     nb_valid_elements = 0;
6407     ref_node = prev ? prev : next;
6408     parent = ref_node->parent;
6409
6410     /*
6411      * Retrieves the parent element declaration
6412      */
6413     element_desc = xmlGetDtdElementDesc(parent->doc->intSubset,
6414                                          parent->name);
6415     if ((element_desc == NULL) && (parent->doc->extSubset != NULL))
6416         element_desc = xmlGetDtdElementDesc(parent->doc->extSubset,
6417                                              parent->name);
6418     if (element_desc == NULL) return(-1);
6419
6420     /*
6421      * Do a backup of the current tree structure
6422      */
6423     prev_next = prev ? prev->next : NULL;
6424     next_prev = next ? next->prev : NULL;
6425     parent_childs = parent->children;
6426     parent_last = parent->last;
6427
6428     /*
6429      * Creates a dummy node and insert it into the tree
6430      */
6431     test_node = xmlNewNode (NULL, BAD_CAST "<!dummy?>");
6432     test_node->doc = ref_node->doc;
6433     test_node->parent = parent;
6434     test_node->prev = prev;
6435     test_node->next = next;
6436     name = test_node->name;
6437
6438     if (prev) prev->next = test_node;
6439     else parent->children = test_node;
6440
6441     if (next) next->prev = test_node;
6442     else parent->last = test_node;
6443
6444     /*
6445      * Insert each potential child node and check if the parent is
6446      * still valid
6447      */
6448     nb_elements = xmlValidGetPotentialChildren(element_desc->content,
6449                        elements, &nb_elements, 256);
6450
6451     for (i = 0;i < nb_elements;i++) {
6452         test_node->name = elements[i];
6453         if (xmlValidateOneElement(&vctxt, parent->doc, parent)) {
6454             int j;
6455
6456             for (j = 0; j < nb_valid_elements;j++)
6457                 if (xmlStrEqual(elements[i], list[j])) break;
6458             list[nb_valid_elements++] = elements[i];
6459             if (nb_valid_elements >= max) break;
6460         }
6461     }
6462
6463     /*
6464      * Restore the tree structure
6465      */
6466     if (prev) prev->next = prev_next;
6467     if (next) next->prev = next_prev;
6468     parent->children = parent_childs;
6469     parent->last = parent_last;
6470
6471     /*
6472      * Free up the dummy node
6473      */
6474     test_node->name = name;
6475     xmlFreeNode(test_node);
6476
6477     return(nb_valid_elements);
6478 }