valid.c 185 KB
Newer Older
1 2 3 4 5 6
/*
 * valid.c : part of the code use to do the DTD handling and the validity
 *           checking
 *
 * See Copyright for the status of this software.
 *
7
 * daniel@veillard.com
8 9
 */

10
#define IN_LIBXML
Bjorn Reese's avatar
Bjorn Reese committed
11
#include "libxml.h"
12 13 14 15 16 17 18 19 20

#include <string.h>

#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif

#include <libxml/xmlmemory.h>
#include <libxml/hash.h>
21
#include <libxml/uri.h>
22 23 24 25 26
#include <libxml/valid.h>
#include <libxml/parser.h>
#include <libxml/parserInternals.h>
#include <libxml/xmlerror.h>
#include <libxml/list.h>
27
#include <libxml/globals.h>
28

29 30
static xmlElementPtr xmlGetDtdElementDesc2(xmlDtdPtr dtd, const xmlChar *name,
	                           int create);
31
/* #define DEBUG_VALID_ALGO */
32
/* #define DEBUG_REGEXP_ALGO */
33

34 35 36 37
#define TODO 								\
    xmlGenericError(xmlGenericErrorContext,				\
	    "Unimplemented block at %s:%d\n",				\
            __FILE__, __LINE__);
38

39 40 41 42 43 44 45
/************************************************************************
 *									*
 *			Error handling routines				*
 *									*
 ************************************************************************/

/**
46
 * xmlVErrMemory:
47 48 49 50 51 52
 * @ctxt:  an XML validation parser context
 * @extra:  extra informations
 *
 * Handle an out of memory error
 */
static void
53
xmlVErrMemory(xmlValidCtxtPtr ctxt, const char *extra)
54
{
55 56 57 58 59 60 61
    xmlGenericErrorFunc channel = NULL;
    xmlParserCtxtPtr pctxt = NULL;
    void *data = NULL;

    if (ctxt != NULL) {
        channel = ctxt->error;
        data = ctxt->userData;
62 63 64 65 66 67
	/* Use the special values to detect if it is part of a parsing
	   context */
	if ((ctxt->finishDtd == XML_CTXT_FINISH_DTD_0) ||
	    (ctxt->finishDtd == XML_CTXT_FINISH_DTD_1)) {
	    pctxt = ctxt->userData;
	}
68
    }
69
    if (extra)
70
        __xmlRaiseError(NULL, channel, data,
71
                        pctxt, NULL, XML_FROM_VALID, XML_ERR_NO_MEMORY,
72 73
                        XML_ERR_FATAL, NULL, 0, extra, NULL, NULL, 0, 0,
                        "Memory allocation failed : %s\n", extra);
74
    else
75
        __xmlRaiseError(NULL, channel, data,
76
                        pctxt, NULL, XML_FROM_VALID, XML_ERR_NO_MEMORY,
77 78
                        XML_ERR_FATAL, NULL, 0, NULL, NULL, NULL, 0, 0,
                        "Memory allocation failed\n");
79 80 81 82 83
}

/**
 * xmlErrValid:
 * @ctxt:  an XML validation parser context
84
 * @error:  the error number
85 86 87 88 89
 * @extra:  extra informations
 *
 * Handle a validation error
 */
static void
90
xmlErrValid(xmlValidCtxtPtr ctxt, xmlParserErrors error,
91
            const char *msg, const char *extra)
92
{
93 94 95 96 97 98 99
    xmlGenericErrorFunc channel = NULL;
    xmlParserCtxtPtr pctxt = NULL;
    void *data = NULL;

    if (ctxt != NULL) {
        channel = ctxt->error;
        data = ctxt->userData;
100 101 102 103 104 105
	/* Use the special values to detect if it is part of a parsing
	   context */
	if ((ctxt->finishDtd == XML_CTXT_FINISH_DTD_0) ||
	    (ctxt->finishDtd == XML_CTXT_FINISH_DTD_1)) {
	    pctxt = ctxt->userData;
	}
106
    }
107
    if (extra)
108
        __xmlRaiseError(NULL, channel, data,
109
                        pctxt, NULL, XML_FROM_VALID, error,
110 111
                        XML_ERR_ERROR, NULL, 0, extra, NULL, NULL, 0, 0,
                        msg, extra);
112
    else
113
        __xmlRaiseError(NULL, channel, data,
114
                        pctxt, NULL, XML_FROM_VALID, error,
115 116 117 118
                        XML_ERR_ERROR, NULL, 0, NULL, NULL, NULL, 0, 0,
                        msg);
}

119
#if defined(LIBXML_VALID_ENABLED) || defined(LIBXML_SCHEMAS_ENABLED)
120
/**
121
 * xmlErrValidNode:
122 123 124 125
 * @ctxt:  an XML validation parser context
 * @node:  the node raising the error
 * @error:  the error number
 * @str1:  extra informations
126
 * @str2:  extra informations
127 128 129 130 131
 * @str3:  extra informations
 *
 * Handle a validation error, provide contextual informations
 */
static void
132
xmlErrValidNode(xmlValidCtxtPtr ctxt,
133 134
                xmlNodePtr node, xmlParserErrors error,
                const char *msg, const xmlChar * str1,
135
                const xmlChar * str2, const xmlChar * str3)
136
{
137
    xmlStructuredErrorFunc schannel = NULL;
138 139 140 141 142 143 144
    xmlGenericErrorFunc channel = NULL;
    xmlParserCtxtPtr pctxt = NULL;
    void *data = NULL;

    if (ctxt != NULL) {
        channel = ctxt->error;
        data = ctxt->userData;
145 146 147 148 149 150
	/* Use the special values to detect if it is part of a parsing
	   context */
	if ((ctxt->finishDtd == XML_CTXT_FINISH_DTD_0) ||
	    (ctxt->finishDtd == XML_CTXT_FINISH_DTD_1)) {
	    pctxt = ctxt->userData;
	}
151
    }
152
    __xmlRaiseError(schannel, channel, data, pctxt, node, XML_FROM_VALID, error,
153 154
                    XML_ERR_ERROR, NULL, 0,
                    (const char *) str1,
155 156
                    (const char *) str1,
                    (const char *) str3, 0, 0, msg, str1, str2, str3);
157
}
158 159 160
#endif /* LIBXML_VALID_ENABLED or LIBXML_SCHEMAS_ENABLED */

#ifdef LIBXML_VALID_ENABLED
161
/**
162
 * xmlErrValidNodeNr:
163 164 165 166
 * @ctxt:  an XML validation parser context
 * @node:  the node raising the error
 * @error:  the error number
 * @str1:  extra informations
167
 * @int2:  extra informations
168 169 170 171 172
 * @str3:  extra informations
 *
 * Handle a validation error, provide contextual informations
 */
static void
173
xmlErrValidNodeNr(xmlValidCtxtPtr ctxt,
174 175
                xmlNodePtr node, xmlParserErrors error,
                const char *msg, const xmlChar * str1,
176
                int int2, const xmlChar * str3)
177
{
178
    xmlStructuredErrorFunc schannel = NULL;
179 180 181 182 183 184 185
    xmlGenericErrorFunc channel = NULL;
    xmlParserCtxtPtr pctxt = NULL;
    void *data = NULL;

    if (ctxt != NULL) {
        channel = ctxt->error;
        data = ctxt->userData;
186 187 188 189 190 191
	/* Use the special values to detect if it is part of a parsing
	   context */
	if ((ctxt->finishDtd == XML_CTXT_FINISH_DTD_0) ||
	    (ctxt->finishDtd == XML_CTXT_FINISH_DTD_1)) {
	    pctxt = ctxt->userData;
	}
192
    }
193
    __xmlRaiseError(schannel, channel, data, pctxt, node, XML_FROM_VALID, error,
194 195
                    XML_ERR_ERROR, NULL, 0,
                    (const char *) str1,
196 197
                    (const char *) str3,
                    NULL, int2, 0, msg, str1, int2, str3);
198
}
199

200 201 202 203 204
/**
 * xmlErrValidWarning:
 * @ctxt:  an XML validation parser context
 * @node:  the node raising the error
 * @error:  the error number
205 206 207
 * @str1:  extra information
 * @str2:  extra information
 * @str3:  extra information
208
 *
209
 * Handle a validation error, provide contextual information
210 211
 */
static void
212
xmlErrValidWarning(xmlValidCtxtPtr ctxt,
213 214 215 216
                xmlNodePtr node, xmlParserErrors error,
                const char *msg, const xmlChar * str1,
                const xmlChar * str2, const xmlChar * str3)
{
217
    xmlStructuredErrorFunc schannel = NULL;
218 219 220 221 222
    xmlGenericErrorFunc channel = NULL;
    xmlParserCtxtPtr pctxt = NULL;
    void *data = NULL;

    if (ctxt != NULL) {
223
        channel = ctxt->warning;
224
        data = ctxt->userData;
225 226 227 228 229 230
	/* Use the special values to detect if it is part of a parsing
	   context */
	if ((ctxt->finishDtd == XML_CTXT_FINISH_DTD_0) ||
	    (ctxt->finishDtd == XML_CTXT_FINISH_DTD_1)) {
	    pctxt = ctxt->userData;
	}
231
    }
232
    __xmlRaiseError(schannel, channel, data, pctxt, node, XML_FROM_VALID, error,
233 234 235 236
                    XML_ERR_WARNING, NULL, 0,
                    (const char *) str1,
                    (const char *) str1,
                    (const char *) str3, 0, 0, msg, str1, str2, str3);
237 238
}

239

240

241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
#ifdef LIBXML_REGEXP_ENABLED
/*
 * If regexp are enabled we can do continuous validation without the
 * need of a tree to validate the content model. this is done in each
 * callbacks.
 * Each xmlValidState represent the validation state associated to the
 * set of nodes currently open from the document root to the current element.
 */


typedef struct _xmlValidState {
    xmlElementPtr	 elemDecl;	/* pointer to the content model */
    xmlNodePtr           node;		/* pointer to the current node */
    xmlRegExecCtxtPtr    exec;		/* regexp runtime */
} _xmlValidState;


static int
vstateVPush(xmlValidCtxtPtr ctxt, xmlElementPtr elemDecl, xmlNodePtr node) {
260
    if ((ctxt->vstateMax == 0) || (ctxt->vstateTab == NULL)) {
261 262 263 264
	ctxt->vstateMax = 10;
	ctxt->vstateTab = (xmlValidState *) xmlMalloc(ctxt->vstateMax *
		              sizeof(ctxt->vstateTab[0]));
        if (ctxt->vstateTab == NULL) {
265
	    xmlVErrMemory(ctxt, "malloc failed");
266 267 268 269 270
	    return(-1);
	}
    }

    if (ctxt->vstateNr >= ctxt->vstateMax) {
271 272 273 274 275
        xmlValidState *tmp;

	tmp = (xmlValidState *) xmlRealloc(ctxt->vstateTab,
	             2 * ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
        if (tmp == NULL) {
276
	    xmlVErrMemory(ctxt, "realloc failed");
277 278
	    return(-1);
	}
279 280
	ctxt->vstateMax *= 2;
	ctxt->vstateTab = tmp;
281 282 283 284 285 286 287 288 289 290 291 292
    }
    ctxt->vstate = &ctxt->vstateTab[ctxt->vstateNr];
    ctxt->vstateTab[ctxt->vstateNr].elemDecl = elemDecl;
    ctxt->vstateTab[ctxt->vstateNr].node = node;
    if ((elemDecl != NULL) && (elemDecl->etype == XML_ELEMENT_TYPE_ELEMENT)) {
	if (elemDecl->contModel == NULL)
	    xmlValidBuildContentModel(ctxt, elemDecl);
	if (elemDecl->contModel != NULL) {
	    ctxt->vstateTab[ctxt->vstateNr].exec = 
		xmlRegNewExecCtxt(elemDecl->contModel, NULL, NULL);
	} else {
	    ctxt->vstateTab[ctxt->vstateNr].exec = NULL;
293 294 295 296
	    xmlErrValidNode(ctxt, (xmlNodePtr) elemDecl,
	                    XML_ERR_INTERNAL_ERROR,
			    "Failed to build content model regexp for %s\n",
			    node->name, NULL, NULL);
297 298 299 300 301 302 303 304 305
	}
    }
    return(ctxt->vstateNr++);
}

static int
vstateVPop(xmlValidCtxtPtr ctxt) {
    xmlElementPtr elemDecl;

306
    if (ctxt->vstateNr < 1) return(-1);
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
    ctxt->vstateNr--;
    elemDecl = ctxt->vstateTab[ctxt->vstateNr].elemDecl;
    ctxt->vstateTab[ctxt->vstateNr].elemDecl = NULL;
    ctxt->vstateTab[ctxt->vstateNr].node = NULL;
    if ((elemDecl != NULL) && (elemDecl->etype == XML_ELEMENT_TYPE_ELEMENT)) {
	xmlRegFreeExecCtxt(ctxt->vstateTab[ctxt->vstateNr].exec);
    }
    ctxt->vstateTab[ctxt->vstateNr].exec = NULL;
    if (ctxt->vstateNr >= 1)
	ctxt->vstate = &ctxt->vstateTab[ctxt->vstateNr - 1];
    else
	ctxt->vstate = NULL;
    return(ctxt->vstateNr);
}

#else /* not LIBXML_REGEXP_ENABLED */
323
/*
Daniel Veillard's avatar
Daniel Veillard committed
324 325
 * If regexp are not enabled, it uses a home made algorithm less
 * complex and easier to
326
 * debug/maintain than a generic NFA -> DFA state based algo. The
327 328 329 330 331 332 333 334 335
 * only restriction is on the deepness of the tree limited by the
 * size of the occurs bitfield
 *
 * this is the content of a saved state for rollbacks
 */

#define ROLLBACK_OR	0
#define ROLLBACK_PARENT	1

336
typedef struct _xmlValidState {
337 338
    xmlElementContentPtr cont;	/* pointer to the content model subtree */
    xmlNodePtr           node;	/* pointer to the current node in the list */
339
    long                 occurs;/* bitfield for multiple occurrences */
340 341 342 343
    unsigned char        depth; /* current depth in the overall tree */
    unsigned char        state; /* ROLLBACK_XXX */
} _xmlValidState;

344
#define MAX_RECURSE 25000
345 346 347 348 349 350 351
#define MAX_DEPTH ((sizeof(_xmlValidState.occurs)) * 8)
#define CONT ctxt->vstate->cont
#define NODE ctxt->vstate->node
#define DEPTH ctxt->vstate->depth
#define OCCURS ctxt->vstate->occurs
#define STATE ctxt->vstate->state

352 353
#define OCCURRENCE (ctxt->vstate->occurs & (1 << DEPTH))
#define PARENT_OCCURRENCE (ctxt->vstate->occurs & ((1 << DEPTH) - 1))
354

355 356
#define SET_OCCURRENCE ctxt->vstate->occurs |= (1 << DEPTH)
#define RESET_OCCURRENCE ctxt->vstate->occurs &= ((1 << DEPTH) - 1)
357 358 359 360 361

static int
vstateVPush(xmlValidCtxtPtr ctxt, xmlElementContentPtr cont,
	    xmlNodePtr node, unsigned char depth, long occurs,
	    unsigned char state) {
362 363
    int i = ctxt->vstateNr - 1;

364 365 366
    if (ctxt->vstateNr > MAX_RECURSE) {
	return(-1);
    }
367 368 369 370 371
    if (ctxt->vstateTab == NULL) {
	ctxt->vstateMax = 8;
	ctxt->vstateTab = (xmlValidState *) xmlMalloc(
		     ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
	if (ctxt->vstateTab == NULL) {
372
	    xmlVErrMemory(ctxt, "malloc failed");
373 374 375
	    return(-1);
	}
    }
376
    if (ctxt->vstateNr >= ctxt->vstateMax) {
377 378 379 380 381
        xmlValidState *tmp;

        tmp = (xmlValidState *) xmlRealloc(ctxt->vstateTab,
	             2 * ctxt->vstateMax * sizeof(ctxt->vstateTab[0]));
        if (tmp == NULL) {
382
	    xmlVErrMemory(ctxt, "malloc failed");
383
	    return(-1);
384
	}
385 386
	ctxt->vstateMax *= 2;
	ctxt->vstateTab = tmp;
387
	ctxt->vstate = &ctxt->vstateTab[0];
388
    }
389 390 391 392 393 394 395 396 397
    /*
     * Don't push on the stack a state already here
     */
    if ((i >= 0) && (ctxt->vstateTab[i].cont == cont) &&
	(ctxt->vstateTab[i].node == node) &&
	(ctxt->vstateTab[i].depth == depth) &&
	(ctxt->vstateTab[i].occurs == occurs) &&
	(ctxt->vstateTab[i].state == state))
	return(ctxt->vstateNr);
398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
    ctxt->vstateTab[ctxt->vstateNr].cont = cont;
    ctxt->vstateTab[ctxt->vstateNr].node = node;
    ctxt->vstateTab[ctxt->vstateNr].depth = depth;
    ctxt->vstateTab[ctxt->vstateNr].occurs = occurs;
    ctxt->vstateTab[ctxt->vstateNr].state = state;
    return(ctxt->vstateNr++);
}

static int
vstateVPop(xmlValidCtxtPtr ctxt) {
    if (ctxt->vstateNr <= 1) return(-1);
    ctxt->vstateNr--;
    ctxt->vstate = &ctxt->vstateTab[0];
    ctxt->vstate->cont =  ctxt->vstateTab[ctxt->vstateNr].cont;
    ctxt->vstate->node = ctxt->vstateTab[ctxt->vstateNr].node;
    ctxt->vstate->depth = ctxt->vstateTab[ctxt->vstateNr].depth;
    ctxt->vstate->occurs = ctxt->vstateTab[ctxt->vstateNr].occurs;
    ctxt->vstate->state = ctxt->vstateTab[ctxt->vstateNr].state;
    return(ctxt->vstateNr);
}

419 420
#endif /* LIBXML_REGEXP_ENABLED */

Daniel Veillard's avatar
Daniel Veillard committed
421 422 423 424 425 426 427 428 429
static int
nodeVPush(xmlValidCtxtPtr ctxt, xmlNodePtr value)
{
    if (ctxt->nodeMax <= 0) {
        ctxt->nodeMax = 4;
        ctxt->nodeTab =
            (xmlNodePtr *) xmlMalloc(ctxt->nodeMax *
                                     sizeof(ctxt->nodeTab[0]));
        if (ctxt->nodeTab == NULL) {
430
	    xmlVErrMemory(ctxt, "malloc failed");
Daniel Veillard's avatar
Daniel Veillard committed
431 432 433 434 435
            ctxt->nodeMax = 0;
            return (0);
        }
    }
    if (ctxt->nodeNr >= ctxt->nodeMax) {
436 437 438 439
        xmlNodePtr *tmp;
        tmp = (xmlNodePtr *) xmlRealloc(ctxt->nodeTab,
			      ctxt->nodeMax * 2 * sizeof(ctxt->nodeTab[0]));
        if (tmp == NULL) {
440
	    xmlVErrMemory(ctxt, "realloc failed");
Daniel Veillard's avatar
Daniel Veillard committed
441 442
            return (0);
        }
443 444
        ctxt->nodeMax *= 2;
	ctxt->nodeTab = tmp;
Daniel Veillard's avatar
Daniel Veillard committed
445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465
    }
    ctxt->nodeTab[ctxt->nodeNr] = value;
    ctxt->node = value;
    return (ctxt->nodeNr++);
}
static xmlNodePtr
nodeVPop(xmlValidCtxtPtr ctxt)
{
    xmlNodePtr ret;

    if (ctxt->nodeNr <= 0)
        return (0);
    ctxt->nodeNr--;
    if (ctxt->nodeNr > 0)
        ctxt->node = ctxt->nodeTab[ctxt->nodeNr - 1];
    else
        ctxt->node = NULL;
    ret = ctxt->nodeTab[ctxt->nodeNr];
    ctxt->nodeTab[ctxt->nodeNr] = 0;
    return (ret);
}
466 467

#ifdef DEBUG_VALID_ALGO
468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513
static void
xmlValidPrintNode(xmlNodePtr cur) {
    if (cur == NULL) {
	xmlGenericError(xmlGenericErrorContext, "null");
	return;
    }
    switch (cur->type) {
	case XML_ELEMENT_NODE:
	    xmlGenericError(xmlGenericErrorContext, "%s ", cur->name);
	    break;
	case XML_TEXT_NODE:
	    xmlGenericError(xmlGenericErrorContext, "text ");
	    break;
	case XML_CDATA_SECTION_NODE:
	    xmlGenericError(xmlGenericErrorContext, "cdata ");
	    break;
	case XML_ENTITY_REF_NODE:
	    xmlGenericError(xmlGenericErrorContext, "&%s; ", cur->name);
	    break;
	case XML_PI_NODE:
	    xmlGenericError(xmlGenericErrorContext, "pi(%s) ", cur->name);
	    break;
	case XML_COMMENT_NODE:
	    xmlGenericError(xmlGenericErrorContext, "comment ");
	    break;
	case XML_ATTRIBUTE_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?attr? ");
	    break;
	case XML_ENTITY_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?ent? ");
	    break;
	case XML_DOCUMENT_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?doc? ");
	    break;
	case XML_DOCUMENT_TYPE_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?doctype? ");
	    break;
	case XML_DOCUMENT_FRAG_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?frag? ");
	    break;
	case XML_NOTATION_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?nota? ");
	    break;
	case XML_HTML_DOCUMENT_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?html? ");
	    break;
514 515 516 517 518
#ifdef LIBXML_DOCB_ENABLED
	case XML_DOCB_DOCUMENT_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?docb? ");
	    break;
#endif
519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544
	case XML_DTD_NODE:
	    xmlGenericError(xmlGenericErrorContext, "?dtd? ");
	    break;
	case XML_ELEMENT_DECL:
	    xmlGenericError(xmlGenericErrorContext, "?edecl? ");
	    break;
	case XML_ATTRIBUTE_DECL:
	    xmlGenericError(xmlGenericErrorContext, "?adecl? ");
	    break;
	case XML_ENTITY_DECL:
	    xmlGenericError(xmlGenericErrorContext, "?entdecl? ");
	    break;
	case XML_NAMESPACE_DECL:
	    xmlGenericError(xmlGenericErrorContext, "?nsdecl? ");
	    break;
	case XML_XINCLUDE_START:
	    xmlGenericError(xmlGenericErrorContext, "incstart ");
	    break;
	case XML_XINCLUDE_END:
	    xmlGenericError(xmlGenericErrorContext, "incend ");
	    break;
    }
}

static void
xmlValidPrintNodeList(xmlNodePtr cur) {
545 546 547
    if (cur == NULL)
	xmlGenericError(xmlGenericErrorContext, "null ");
    while (cur != NULL) {
548
	xmlValidPrintNode(cur);
549 550 551 552
	cur = cur->next;
    }
}

553 554
static void
xmlValidDebug(xmlNodePtr cur, xmlElementContentPtr cont) {
555
    char expr[5000];
556 557 558 559 560

    expr[0] = 0;
    xmlGenericError(xmlGenericErrorContext, "valid: ");
    xmlValidPrintNodeList(cur);
    xmlGenericError(xmlGenericErrorContext, "against ");
561
    xmlSnprintfElementContent(expr, 5000, cont, 1);
562 563 564
    xmlGenericError(xmlGenericErrorContext, "%s\n", expr);
}

565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604
static void
xmlValidDebugState(xmlValidStatePtr state) {
    xmlGenericError(xmlGenericErrorContext, "(");
    if (state->cont == NULL)
	xmlGenericError(xmlGenericErrorContext, "null,");
    else
	switch (state->cont->type) {
            case XML_ELEMENT_CONTENT_PCDATA:
		xmlGenericError(xmlGenericErrorContext, "pcdata,");
		break;
            case XML_ELEMENT_CONTENT_ELEMENT:
		xmlGenericError(xmlGenericErrorContext, "%s,",
			        state->cont->name);
		break;
            case XML_ELEMENT_CONTENT_SEQ:
		xmlGenericError(xmlGenericErrorContext, "seq,");
		break;
            case XML_ELEMENT_CONTENT_OR:
		xmlGenericError(xmlGenericErrorContext, "or,");
		break;
	}
    xmlValidPrintNode(state->node);
    xmlGenericError(xmlGenericErrorContext, ",%d,%X,%d)",
	    state->depth, state->occurs, state->state);
}

static void
xmlValidStateDebug(xmlValidCtxtPtr ctxt) {
    int i, j;

    xmlGenericError(xmlGenericErrorContext, "state: ");
    xmlValidDebugState(ctxt->vstate);
    xmlGenericError(xmlGenericErrorContext, " stack: %d ",
	    ctxt->vstateNr - 1);
    for (i = 0, j = ctxt->vstateNr - 1;(i < 3) && (j > 0);i++,j--)
	xmlValidDebugState(&ctxt->vstateTab[j]);
    xmlGenericError(xmlGenericErrorContext, "\n");
}

/*****
605
#define DEBUG_VALID_STATE(n,c) xmlValidDebug(n,c);
606 607 608
 *****/

#define DEBUG_VALID_STATE(n,c) xmlValidStateDebug(ctxt);
Daniel Veillard's avatar
Daniel Veillard committed
609 610 611
#define DEBUG_VALID_MSG(m)					\
    xmlGenericError(xmlGenericErrorContext, "%s\n", m);
        
612 613
#else
#define DEBUG_VALID_STATE(n,c)
Daniel Veillard's avatar
Daniel Veillard committed
614
#define DEBUG_VALID_MSG(m)
615 616
#endif

617
/* TODO: use hash table for accesses to elem and attribute definitions */
618

619

620 621 622 623 624 625 626
#define CHECK_DTD						\
   if (doc == NULL) return(0);					\
   else if ((doc->intSubset == NULL) &&				\
	    (doc->extSubset == NULL)) return(0)

xmlAttributePtr xmlScanAttributeDecl(xmlDtdPtr dtd, const xmlChar *elem);

627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642
#ifdef LIBXML_REGEXP_ENABLED

/************************************************************************
 *									*
 *		Content model validation based on the regexps		*
 *									*
 ************************************************************************/

/**
 * xmlValidBuildAContentModel:
 * @content:  the content model
 * @ctxt:  the schema parser context
 * @name:  the element name whose content is being built
 *
 * Generate the automata sequence needed for that type
 *
643
 * Returns 1 if successful or 0 in case of error.
644 645 646 647 648 649
 */
static int
xmlValidBuildAContentModel(xmlElementContentPtr content,
		           xmlValidCtxtPtr ctxt,
		           const xmlChar *name) {
    if (content == NULL) {
650 651 652
	xmlErrValidNode(ctxt, NULL, XML_ERR_INTERNAL_ERROR,
			"Found NULL content in content model of %s\n",
			name, NULL, NULL);
653
	return(0);
654 655 656
    }
    switch (content->type) {
	case XML_ELEMENT_CONTENT_PCDATA:
657 658 659
	    xmlErrValidNode(ctxt, NULL, XML_ERR_INTERNAL_ERROR,
			    "Found PCDATA in content model of %s\n",
		            name, NULL, NULL);
660
	    return(0);
661 662 663
	    break;
	case XML_ELEMENT_CONTENT_ELEMENT: {
	    xmlAutomataStatePtr oldstate = ctxt->state;
664 665 666 667 668
	    xmlChar fn[50];
	    xmlChar *fullname;
	    
	    fullname = xmlBuildQName(content->name, content->prefix, fn, 50);
	    if (fullname == NULL) {
669
	        xmlVErrMemory(ctxt, "Building content model");
670
		return(0);
671 672
	    }

673 674 675
	    switch (content->ocur) {
		case XML_ELEMENT_CONTENT_ONCE:
		    ctxt->state = xmlAutomataNewTransition(ctxt->am,
676
			    ctxt->state, NULL, fullname, NULL);
677 678 679
		    break;
		case XML_ELEMENT_CONTENT_OPT:
		    ctxt->state = xmlAutomataNewTransition(ctxt->am,
680
			    ctxt->state, NULL, fullname, NULL);
681 682 683 684
		    xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
		    break;
		case XML_ELEMENT_CONTENT_PLUS:
		    ctxt->state = xmlAutomataNewTransition(ctxt->am,
685
			    ctxt->state, NULL, fullname, NULL);
686
		    xmlAutomataNewTransition(ctxt->am, ctxt->state,
687
			                     ctxt->state, fullname, NULL);
688 689
		    break;
		case XML_ELEMENT_CONTENT_MULT:
690 691 692 693
		    ctxt->state = xmlAutomataNewEpsilon(ctxt->am,
		    			    ctxt->state, NULL);
		    xmlAutomataNewTransition(ctxt->am,
		    	    ctxt->state, ctxt->state, fullname, NULL);
694 695
		    break;
	    }
696 697
	    if ((fullname != fn) && (fullname != content->name))
		xmlFree(fullname);
698 699 700
	    break;
	}
	case XML_ELEMENT_CONTENT_SEQ: {
701
	    xmlAutomataStatePtr oldstate, oldend;
702 703 704 705 706 707 708
	    xmlElementContentOccur ocur;

	    /*
	     * Simply iterate over the content
	     */
	    oldstate = ctxt->state;
	    ocur = content->ocur;
709 710 711 712
	    if (ocur != XML_ELEMENT_CONTENT_ONCE) {
		ctxt->state = xmlAutomataNewEpsilon(ctxt->am, oldstate, NULL);
		oldstate = ctxt->state;
	    }
713
	    do {
714 715
		xmlValidBuildAContentModel(content->c1, ctxt, name);
		content = content->c2;
716 717 718
	    } while ((content->type == XML_ELEMENT_CONTENT_SEQ) &&
		     (content->ocur == XML_ELEMENT_CONTENT_ONCE));
	    xmlValidBuildAContentModel(content, ctxt, name);
719 720
	    oldend = ctxt->state;
	    ctxt->state = xmlAutomataNewEpsilon(ctxt->am, oldend, NULL);
721 722 723 724 725 726 727 728
	    switch (ocur) {
		case XML_ELEMENT_CONTENT_ONCE:
		    break;
		case XML_ELEMENT_CONTENT_OPT:
		    xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
		    break;
		case XML_ELEMENT_CONTENT_MULT:
		    xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
729
		    xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
730 731
		    break;
		case XML_ELEMENT_CONTENT_PLUS:
732
		    xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
733 734 735 736 737
		    break;
	    }
	    break;
	}
	case XML_ELEMENT_CONTENT_OR: {
738
	    xmlAutomataStatePtr oldstate, oldend;
739 740 741
	    xmlElementContentOccur ocur;

	    ocur = content->ocur;
742 743 744 745 746 747 748
	    if ((ocur == XML_ELEMENT_CONTENT_PLUS) || 
		(ocur == XML_ELEMENT_CONTENT_MULT)) {
		ctxt->state = xmlAutomataNewEpsilon(ctxt->am,
			ctxt->state, NULL);
	    }
	    oldstate = ctxt->state;
	    oldend = xmlAutomataNewState(ctxt->am);
749 750 751 752 753

	    /*
	     * iterate over the subtypes and remerge the end with an
	     * epsilon transition
	     */
754
	    do {
755
		ctxt->state = oldstate;
756
		xmlValidBuildAContentModel(content->c1, ctxt, name);
757
		xmlAutomataNewEpsilon(ctxt->am, ctxt->state, oldend);
758
		content = content->c2;
759 760
	    } while ((content->type == XML_ELEMENT_CONTENT_OR) &&
		     (content->ocur == XML_ELEMENT_CONTENT_ONCE));
761
	    ctxt->state = oldstate;
762
	    xmlValidBuildAContentModel(content, ctxt, name);
763 764
	    xmlAutomataNewEpsilon(ctxt->am, ctxt->state, oldend);
	    ctxt->state = xmlAutomataNewEpsilon(ctxt->am, oldend, NULL);
765 766 767 768
	    switch (ocur) {
		case XML_ELEMENT_CONTENT_ONCE:
		    break;
		case XML_ELEMENT_CONTENT_OPT:
769
		    xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
770 771
		    break;
		case XML_ELEMENT_CONTENT_MULT:
772 773
		    xmlAutomataNewEpsilon(ctxt->am, oldstate, ctxt->state);
		    xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
774 775
		    break;
		case XML_ELEMENT_CONTENT_PLUS:
776
		    xmlAutomataNewEpsilon(ctxt->am, oldend, oldstate);
777 778 779 780 781
		    break;
	    }
	    break;
	}
	default:
782 783 784
	    xmlErrValid(ctxt, XML_ERR_INTERNAL_ERROR,
	                "ContentModel broken for element %s\n",
			(const char *) name);
785
	    return(0);
786
    }
787
    return(1);
788 789 790 791 792 793 794 795 796
}
/**
 * xmlValidBuildContentModel:
 * @ctxt:  a validation context
 * @elem:  an element declaration node
 *
 * (Re)Build the automata associated to the content model of this
 * element
 *
797
 * Returns 1 in case of success, 0 in case of error
798 799 800 801 802
 */
int
xmlValidBuildContentModel(xmlValidCtxtPtr ctxt, xmlElementPtr elem) {

    if ((ctxt == NULL) || (elem == NULL))
803
	return(0);
804 805
    if (elem->type != XML_ELEMENT_DECL)
	return(0);
806 807
    if (elem->etype != XML_ELEMENT_TYPE_ELEMENT)
	return(1);
808
    /* TODO: should we rebuild in this case ? */
809 810 811 812 813
    if (elem->contModel != NULL) {
	if (!xmlRegexpIsDeterminist(elem->contModel)) {
	    ctxt->valid = 0;
	    return(0);
	}
814
	return(1);
815
    }
816 817 818

    ctxt->am = xmlNewAutomata();
    if (ctxt->am == NULL) {
819 820 821 822
	xmlErrValidNode(ctxt, (xmlNodePtr) elem,
	                XML_ERR_INTERNAL_ERROR,
	                "Cannot create automata for element %s\n",
		        elem->name, NULL, NULL);
823
	return(0);
824
    }
William M. Brack's avatar
William M. Brack committed
825
    ctxt->state = xmlAutomataGetInitState(ctxt->am);
826 827
    xmlValidBuildAContentModel(elem->content, ctxt, elem->name);
    xmlAutomataSetFinalState(ctxt->am, ctxt->state);
828
    elem->contModel = xmlAutomataCompile(ctxt->am);
829
    if (xmlRegexpIsDeterminist(elem->contModel) != 1) {
830 831 832
	char expr[5000];
	expr[0] = 0;
	xmlSnprintfElementContent(expr, 5000, elem->content, 1);
833 834 835 836
	xmlErrValidNode(ctxt, (xmlNodePtr) elem,
	                XML_DTD_CONTENT_NOT_DETERMINIST,
	       "Content model of %s is not determinist: %s\n",
	       elem->name, BAD_CAST expr, NULL);
837 838 839
#ifdef DEBUG_REGEXP_ALGO
        xmlRegexpPrint(stderr, elem->contModel);
#endif
840
        ctxt->valid = 0;
841 842 843 844
	ctxt->state = NULL;
	xmlFreeAutomata(ctxt->am);
	ctxt->am = NULL;
	return(0);
845 846 847 848
    }
    ctxt->state = NULL;
    xmlFreeAutomata(ctxt->am);
    ctxt->am = NULL;
849
    return(1);
850 851 852 853
}

#endif /* LIBXML_REGEXP_ENABLED */

854 855 856 857 858 859
/****************************************************************
 *								*
 *	Util functions for data allocation/deallocation		*
 *								*
 ****************************************************************/

860 861 862 863 864 865 866
/**
 * xmlNewValidCtxt:
 *
 * Allocate a validation context structure.
 *
 * Returns NULL if not, otherwise the new validation context structure
 */
867
xmlValidCtxtPtr xmlNewValidCtxt(void) {
868 869
    xmlValidCtxtPtr ret;

870
    if ((ret = xmlMalloc(sizeof (xmlValidCtxt))) == NULL) {
871
	xmlVErrMemory(NULL, "malloc failed");
872
	return (NULL);
873
    }
874 875 876 877 878 879 880 881 882 883 884 885 886 887

    (void) memset(ret, 0, sizeof (xmlValidCtxt));

    return (ret);
}

/**
 * xmlFreeValidCtxt:
 * @cur:  the validation context to free
 *
 * Free a validation context structure.
 */
void
xmlFreeValidCtxt(xmlValidCtxtPtr cur) {
888 889 890 891
    if (cur->vstateTab != NULL)
        xmlFree(cur->vstateTab);
    if (cur->nodeTab != NULL)
        xmlFree(cur->nodeTab);
892 893 894
    xmlFree(cur);
}

895 896
#endif /* LIBXML_VALID_ENABLED */

897
/**
898 899
 * xmlNewDocElementContent:
 * @doc:  the document
900 901 902
 * @name:  the subelement name or NULL
 * @type:  the type of element content decl
 *
903
 * Allocate an element content structure for the document.
904
 *
905
 * Returns NULL if not, otherwise the new element content structure
906 907
 */
xmlElementContentPtr
908 909
xmlNewDocElementContent(xmlDocPtr doc, const xmlChar *name,
                        xmlElementContentType type) {
910
    xmlElementContentPtr ret;
911 912 913 914
    xmlDictPtr dict = NULL;

    if (doc != NULL)
        dict = doc->dict;
915 916 917 918

    switch(type) {
	case XML_ELEMENT_CONTENT_ELEMENT:
	    if (name == NULL) {
919 920 921
	        xmlErrValid(NULL, XML_ERR_INTERNAL_ERROR,
			"xmlNewElementContent : name == NULL !\n",
			NULL);
922 923 924 925 926 927
	    }
	    break;
        case XML_ELEMENT_CONTENT_PCDATA:
	case XML_ELEMENT_CONTENT_SEQ:
	case XML_ELEMENT_CONTENT_OR:
	    if (name != NULL) {
928 929 930
	        xmlErrValid(NULL, XML_ERR_INTERNAL_ERROR,
			"xmlNewElementContent : name != NULL !\n",
			NULL);
931 932 933
	    }
	    break;
	default:
934 935 936
	    xmlErrValid(NULL, XML_ERR_INTERNAL_ERROR, 
		    "Internal: ELEMENT content corrupted invalid type\n",
		    NULL);
937 938 939 940
	    return(NULL);
    }
    ret = (xmlElementContentPtr) xmlMalloc(sizeof(xmlElementContent));
    if (ret == NULL) {
941
	xmlVErrMemory(NULL, "malloc failed");
942 943
	return(NULL);
    }
944
    memset(ret, 0, sizeof(xmlElementContent));
945 946
    ret->type = type;
    ret->ocur = XML_ELEMENT_CONTENT_ONCE;
947
    if (name != NULL) {
948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965
        int l;
	const xmlChar *tmp;

	tmp = xmlSplitQName3(name, &l);
	if (tmp == NULL) {
	    if (dict == NULL)
		ret->name = xmlStrdup(name);
	    else
	        ret->name = xmlDictLookup(dict, name, -1);
	} else {
	    if (dict == NULL) {
		ret->prefix = xmlStrndup(name, l);
		ret->name = xmlStrdup(tmp);
	    } else {
	        ret->prefix = xmlDictLookup(dict, name, l);
		ret->name = xmlDictLookup(dict, tmp, -1);
	    }
	}
966
    }
967 968 969 970
    return(ret);
}

/**
971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987
 * xmlNewElementContent:
 * @name:  the subelement name or NULL
 * @type:  the type of element content decl
 *
 * Allocate an element content structure.
 * Deprecated in favor of xmlNewDocElementContent
 *
 * Returns NULL if not, otherwise the new element content structure
 */
xmlElementContentPtr
xmlNewElementContent(const xmlChar *name, xmlElementContentType type) {
    return(xmlNewDocElementContent(NULL, name, type));
}

/**
 * xmlCopyDocElementContent:
 * @doc:  the document owning the element declaration
988
 * @cur:  An element content pointer.
989 990 991 992 993 994
 *
 * Build a copy of an element content description.
 * 
 * Returns the new xmlElementContentPtr or NULL in case of error.
 */
xmlElementContentPtr
995 996 997
xmlCopyDocElementContent(xmlDocPtr doc, xmlElementContentPtr cur) {
    xmlElementContentPtr ret = NULL, prev = NULL, tmp;
    xmlDictPtr dict = NULL;
998 999

    if (cur == NULL) return(NULL);
1000 1001 1002 1003 1004

    if (doc != NULL)
        dict = doc->dict;

    ret = (xmlElementContentPtr) xmlMalloc(sizeof(xmlElementContent));
1005
    if (ret == NULL) {
1006
	xmlVErrMemory(NULL, "malloc failed");
1007 1008
	return(NULL);
    }
1009 1010
    memset(ret, 0, sizeof(xmlElementContent));
    ret->type = cur->type;
1011
    ret->ocur = cur->ocur;
1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026
    if (cur->name != NULL) {
	if (dict)
	    ret->name = xmlDictLookup(dict, cur->name, -1);
	else
	    ret->name = xmlStrdup(cur->name);
    }
    
    if (cur->prefix != NULL) {
	if (dict)
	    ret->prefix = xmlDictLookup(dict, cur->prefix, -1);
	else
	    ret->prefix = xmlStrdup(cur->prefix);
    }
    if (cur->c1 != NULL)
        ret->c1 = xmlCopyDocElementContent(doc, cur->c1);
1027 1028
    if (ret->c1 != NULL)
	ret->c1->parent = ret;
1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062
    if (cur->c2 != NULL) {
        prev = ret;
	cur = cur->c2;
	while (cur != NULL) {
	    tmp = (xmlElementContentPtr) xmlMalloc(sizeof(xmlElementContent));
	    if (tmp == NULL) {
		xmlVErrMemory(NULL, "malloc failed");
		return(ret);
	    }
	    memset(tmp, 0, sizeof(xmlElementContent));
	    tmp->type = cur->type;
	    tmp->ocur = cur->ocur;
	    prev->c2 = tmp;
	    if (cur->name != NULL) {
		if (dict)
		    tmp->name = xmlDictLookup(dict, cur->name, -1);
		else
		    tmp->name = xmlStrdup(cur->name);
	    }
	    
	    if (cur->prefix != NULL) {
		if (dict)
		    tmp->prefix = xmlDictLookup(dict, cur->prefix, -1);
		else
		    tmp->prefix = xmlStrdup(cur->prefix);
	    }
	    if (cur->c1 != NULL)
	        tmp->c1 = xmlCopyDocElementContent(doc,cur->c1);
	    if (tmp->c1 != NULL)
		tmp->c1->parent = ret;
	    prev = tmp;
	    cur = cur->c2;
	}
    }
1063 1064