source: icXML/icXML-devel/src/icxercesc/validators/common/DFAContentModel.cpp @ 2720

Last change on this file since 2720 was 2720, checked in by cameron, 6 years ago

Initial check-in of icXML 0.8 source files

File size: 53.4 KB
Line 
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements.  See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License.  You may obtain a copy of the License at
8 *
9 *      http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18/*
19 * $Id: DFAContentModel.cpp 901107 2010-01-20 08:45:02Z borisk $
20 */
21
22
23// ---------------------------------------------------------------------------
24//  Includes
25// ---------------------------------------------------------------------------
26#include <xercesc/util/RuntimeException.hpp>
27#include <xercesc/framework/XMLBuffer.hpp>
28#include <xercesc/framework/XMLElementDecl.hpp>
29#include <xercesc/framework/XMLValidator.hpp>
30#include <xercesc/validators/common/CMAny.hpp>
31#include <xercesc/validators/common/CMBinaryOp.hpp>
32#include <xercesc/validators/common/CMLeaf.hpp>
33#include <xercesc/validators/common/CMRepeatingLeaf.hpp>
34#include <xercesc/validators/common/CMUnaryOp.hpp>
35#include <xercesc/validators/common/DFAContentModel.hpp>
36#include <xercesc/validators/common/ContentSpecNode.hpp>
37#include <xercesc/validators/common/Grammar.hpp>
38#include <xercesc/validators/schema/SchemaSymbols.hpp>
39#include <xercesc/validators/schema/SubstitutionGroupComparator.hpp>
40#include <xercesc/validators/schema/XercesElementWildcard.hpp>
41#include <xercesc/util/RefHashTableOf.hpp>
42#include <xercesc/util/XMLInteger.hpp>
43#include <xercesc/util/XMLString.hpp>
44#include <math.h>
45
46XERCES_CPP_NAMESPACE_BEGIN
47
48struct CMStateSetHasher
49{
50  XMLSize_t getHashVal(const void *const key, XMLSize_t mod)
51  {
52        const CMStateSet* const pkey = (const CMStateSet*) key;
53        return ((pkey->hashCode()) % mod);
54  }
55
56  bool equals(const void *const key1, const void *const key2)
57  {
58        const CMStateSet* const pkey1 = (const CMStateSet*) key1;
59        const CMStateSet* const pkey2 = (const CMStateSet*) key2;
60        return (*pkey1==*pkey2);
61  }
62};
63
64// ---------------------------------------------------------------------------
65//  DFAContentModel: Constructors and Destructor
66// ---------------------------------------------------------------------------
67DFAContentModel::DFAContentModel( const bool             dtd
68                                                                , ContentSpecNode* const elemContentSpec
69                                                                , MemoryManager* const   manager) :
70
71        fElemMap(0)
72        , fElemMapType(0)
73        , fElemMapSize(0)
74        , fEmptyOk(false)
75        , fEOCPos(0)
76        , fFinalStateFlags(0)
77        , fFollowList(0)
78        , fHeadNode(0)
79        , fLeafCount(0)
80        , fLeafList(0)
81        , fLeafListType(0)
82        , fTransTable(0)
83        , fTransTableSize(0)
84        , fCountingStates(0)
85        , fDTD(dtd)
86        , fIsMixed(false)
87        , fLeafNameTypeVector(0)
88        , fMemoryManager(manager)
89{
90        // And build the DFA data structures
91        buildDFA(elemContentSpec);
92}
93
94DFAContentModel::DFAContentModel( const bool             dtd
95                                                                , ContentSpecNode* const elemContentSpec
96                                                                , const bool             isMixed
97                                                                , MemoryManager* const   manager):
98
99        fElemMap(0)
100        , fElemMapType(0)
101        , fElemMapSize(0)
102        , fEmptyOk(false)
103        , fEOCPos(0)
104        , fFinalStateFlags(0)
105        , fFollowList(0)
106        , fHeadNode(0)
107        , fLeafCount(0)
108        , fLeafList(0)
109        , fLeafListType(0)
110        , fTransTable(0)
111        , fTransTableSize(0)
112        , fCountingStates(0)
113        , fDTD(dtd)
114        , fIsMixed(isMixed)
115        , fLeafNameTypeVector(0)
116        , fMemoryManager(manager)
117{
118        // And build the DFA data structures
119        buildDFA(elemContentSpec);
120}
121
122DFAContentModel::~DFAContentModel()
123{
124        //
125        //  Clean up all the stuff that is not just temporary representation
126        //  data that was cleaned up after building the DFA.
127        //
128        fMemoryManager->deallocate(fFinalStateFlags); //delete [] fFinalStateFlags;
129
130        unsigned int index;
131        for (index = 0; index < fTransTableSize; index++)
132                fMemoryManager->deallocate(fTransTable[index]); //delete [] fTransTable[index];
133        fMemoryManager->deallocate(fTransTable); //delete [] fTransTable;
134
135        if(fCountingStates)
136        {
137                for (unsigned int j = 0; j < fTransTableSize; ++j)
138                        delete fCountingStates[j];
139                fMemoryManager->deallocate(fCountingStates);
140        }
141
142        for (index = 0; index < fLeafCount; index++)
143                delete fElemMap[index];
144        fMemoryManager->deallocate(fElemMap); //delete [] fElemMap;
145
146        fMemoryManager->deallocate(fElemMapType); //delete [] fElemMapType;
147        fMemoryManager->deallocate(fLeafListType); //delete [] fLeafListType;
148
149        delete fLeafNameTypeVector;
150}
151
152
153// ---------------------------------------------------------------------------
154//  DFAContentModel: Implementation of the ContentModel virtual interface
155// ---------------------------------------------------------------------------
156bool
157DFAContentModel::validateContent
158(
159        #ifdef STORE_CHILDREN_INFORMATION_IN_PARSER
160        XMLElementDecl ** const         children
161        #else
162        QName** const                           children
163        #endif
164        , XMLSize_t                                     childCount
165        , XMLSize_t*                            indexOfFailingChild
166        , MemoryManager*    const       manager
167) const
168{
169        DEBUG_MESSAGE("DFAContentModel::validateContent(<children>," << childCount << ')');
170
171        //
172        //  If there are no children, then either we fail on the 0th element
173        //  or we return success. It depends upon whether this content model
174        //  accepts empty content, which we determined earlier.
175        //
176        if (!childCount)
177        {
178                // success
179                if (fEmptyOk)
180                        return true;
181                *indexOfFailingChild=0;
182                return false;
183        }
184
185        //
186        //  Lets loop through the children in the array and move our way
187        //  through the states. Note that we use the fElemMap array to map
188        //  an element index to a state index.
189        //
190        unsigned int curState = 0;
191        unsigned int nextState = 0;
192        unsigned int loopCount = 0;
193        unsigned int childIndex = 0;
194        for (; childIndex < childCount; childIndex++)
195        {
196                // Get the current element index out
197                #ifdef STORE_CHILDREN_INFORMATION_IN_PARSER
198                QName * const curElem = children[childIndex]->getElementName();
199                #else
200                // Get the current child out of the source index
201                QName * const curElem = children[childIndex];
202                #endif
203
204                const XMLCh* curElemRawName = 0;
205                if (fDTD)
206                {
207                        curElemRawName = curElem->getRawName();
208                }
209
210                // If this is text in a Schema mixed content model, skip it.
211                if (fIsMixed && (curElem->getURI() == XMLElementDecl::fgPCDataElemId))
212                {
213                        continue;
214                }
215
216                // Look up this child in our element map
217                unsigned int elemIndex = 0;
218                for (; elemIndex < fElemMapSize; elemIndex++)
219                {
220                        const QName* inElem  = fElemMap[elemIndex];
221
222                        if (fDTD)
223                        {
224                                if (XMLString::equals(inElem->getRawName(), curElemRawName))
225                                {
226                                        nextState = fTransTable[curState][elemIndex];
227                                        if (nextState != XMLContentModel::gInvalidTrans)
228                                                break;
229                                }
230                        }
231                        else
232                        {
233                                ContentSpecNode::NodeTypes type = fElemMapType[elemIndex];
234
235                                if (type == ContentSpecNode::Leaf)
236                                {
237                                        if ((inElem->getURI() == curElem->getURI()) && (XMLString::equals(inElem->getLocalPart(), curElem->getLocalPart())))
238                                        {
239                                                nextState = fTransTable[curState][elemIndex];
240                                                if (nextState != XMLContentModel::gInvalidTrans)
241                                                        break;
242                                        }
243                                }
244                                else if ((type & 0x0f)== ContentSpecNode::Any)
245                                {
246                                        nextState = fTransTable[curState][elemIndex];
247                                        if (nextState != XMLContentModel::gInvalidTrans)
248                                                break;
249                                }
250                                else if ((type & 0x0f) == ContentSpecNode::Any_NS)
251                                {
252                                        if (inElem->getURI() == curElem->getURI())
253                                        {
254                                                nextState = fTransTable[curState][elemIndex];
255                                                if (nextState != XMLContentModel::gInvalidTrans)
256                                                {
257                                                        break;
258                                                }
259                                        }
260                                }
261                                else if ((type & 0x0f) == ContentSpecNode::Any_Other)
262                                {
263                                        // Here we assume that empty string has id 1.
264                                        //
265                                        unsigned int uriId = curElem->getURI();
266                                        if (uriId != XMLNamespaceResolver::fEmptyUriId && uriId != inElem->getURI())
267                                        {
268                                                nextState = fTransTable[curState][elemIndex];
269                                                if (nextState != XMLContentModel::gInvalidTrans)
270                                                        break;
271                                        }
272                                }
273                        }
274                }//for elemIndex
275
276                // If "nextState" is -1, we found a match, but the transition is invalid
277                if (nextState == XMLContentModel::gInvalidTrans)
278                {
279                        *indexOfFailingChild=childIndex;
280                        return false;
281                }
282
283                // If we didn't find it, then obviously not valid
284                if (elemIndex == fElemMapSize)
285                {
286                        *indexOfFailingChild=childIndex;
287                        return false;
288                }
289
290                unsigned int nextLoop = 0;
291                if (!handleRepetitions(curElem, curState, loopCount, nextState, nextLoop, elemIndex, 0))
292                {
293                        *indexOfFailingChild=childIndex;
294                        return false;
295                }
296
297                curState = nextState;
298                loopCount = nextLoop;
299                nextState = 0;
300
301        }//for childIndex
302
303        //
304        //  We transitioned all the way through the input list. However, that
305        //  does not mean that we ended in a final state. So check whether
306        //  our ending state is a final state.
307        //
308        if (!fFinalStateFlags[curState])
309        {
310                *indexOfFailingChild=childIndex;
311                return false;
312        }
313
314        // verify if we exited before the minOccurs was satisfied
315        if (fCountingStates != 0)
316        {
317                const Occurence * occurence = fCountingStates[curState];
318                if (occurence && loopCount < (unsigned int)occurence->minOccurs)
319                {
320                        // not enough loops on the current state to be considered final.
321                        *indexOfFailingChild=childIndex;
322                        return false;
323                }
324        }
325
326        //success
327        return true;
328}
329
330bool DFAContentModel::validateContentSpecial
331(
332        #ifdef STORE_CHILDREN_INFORMATION_IN_PARSER
333        XMLElementDecl ** const                 children
334        #else
335        QName** const                                   children
336        #endif
337        , XMLSize_t                                             childCount
338        , GrammarResolver*  const               pGrammarResolver
339        , XMLNamespaceResolver* const   pUriResolver
340        , XMLSize_t*                                    indexOfFailingChild
341        , MemoryManager*    const               manager
342) const
343{
344
345        if (childCount == 0)
346        {
347                if(fEmptyOk)
348                        return true;
349                *indexOfFailingChild=0;
350                return false;
351        }
352
353        SubstitutionGroupComparator comparator(pGrammarResolver, pUriResolver);
354
355        //
356        //  Lets loop through the children in the array and move our way
357        //  through the states. Note that we use the fElemMap array to map
358        //  an element index to a state index.
359        //
360        unsigned int curState = 0;
361        unsigned int loopCount = 0;
362        unsigned int nextState = 0;
363        unsigned int childIndex = 0;
364        for (; childIndex < childCount; childIndex++)
365        {
366                // Get the current element index out
367                #ifdef STORE_CHILDREN_INFORMATION_IN_PARSER
368                QName * const curElem = children[childIndex]->getElementName();
369                curElem->setURI(children[childIndex]->getURI());
370                #else
371                // Get the current child out of the source index
372                QName * const curElem = children[childIndex];
373                #endif
374
375                // If this is text in a Schema mixed content model, skip it.
376                if ( fIsMixed &&
377                        ( curElem->getURI() == XMLElementDecl::fgPCDataElemId))
378                        continue;
379
380                // Look up this child in our element map
381                unsigned int elemIndex = 0;
382                for (; elemIndex < fElemMapSize; elemIndex++)
383                {
384                        QName* inElem  = fElemMap[elemIndex];
385                        ContentSpecNode::NodeTypes type = fElemMapType[elemIndex];
386                        if (type == ContentSpecNode::Leaf)
387                        {
388                                if (comparator.isEquivalentTo(curElem, inElem) )
389                                {
390                                        nextState = fTransTable[curState][elemIndex];
391                                        if (nextState != XMLContentModel::gInvalidTrans)
392                                                break;
393                                }
394
395                        }
396                        else if ((type & 0x0f)== ContentSpecNode::Any)
397                        {
398                                nextState = fTransTable[curState][elemIndex];
399                                if (nextState != XMLContentModel::gInvalidTrans)
400                                        break;
401                        }
402                        else if ((type & 0x0f) == ContentSpecNode::Any_NS)
403                        {
404                                if (inElem->getURI() == curElem->getURI())
405                                {
406                                        nextState = fTransTable[curState][elemIndex];
407                                        if (nextState != XMLContentModel::gInvalidTrans)
408                                                break;
409                                }
410                        }
411                        else if ((type & 0x0f) == ContentSpecNode::Any_Other)
412                        {
413                                // Here we assume that empty string has id 1.
414                                //
415                                unsigned int uriId = curElem->getURI();
416                                if (uriId != 1 && uriId != inElem->getURI())
417                                {
418                                        nextState = fTransTable[curState][elemIndex];
419                                        if (nextState != XMLContentModel::gInvalidTrans)
420                                                break;
421                                }
422                        }
423                }//for elemIndex
424
425                // If "nextState" is -1, we found a match, but the transition is invalid
426                if (nextState == XMLContentModel::gInvalidTrans)
427                {
428                        *indexOfFailingChild=childIndex;
429                        return false;
430                }
431
432                // If we didn't find it, then obviously not valid
433                if (elemIndex == fElemMapSize)
434                {
435                        *indexOfFailingChild=childIndex;
436                        return false;
437                }
438
439                unsigned int nextLoop = 0;
440                if(!handleRepetitions(curElem, curState, loopCount, nextState, nextLoop, elemIndex, &comparator))
441                {
442                        *indexOfFailingChild=childIndex;
443                        return false;
444                }
445
446                curState = nextState;
447                loopCount = nextLoop;
448                nextState = 0;
449
450        }//for childIndex
451
452        //
453        //  We transitioned all the way through the input list. However, that
454        //  does not mean that we ended in a final state. So check whether
455        //  our ending state is a final state.
456        //
457        if (!fFinalStateFlags[curState])
458        {
459                *indexOfFailingChild=childIndex;
460                return false;
461        }
462
463        // verify if we exited before the minOccurs was satisfied
464        if (fCountingStates != 0) {
465                Occurence* o = fCountingStates[curState];
466                if (o != 0) {
467                        if (loopCount < (unsigned int)o->minOccurs) {
468                                // not enough loops on the current state.
469                                *indexOfFailingChild=childIndex;
470                                return false;
471                        }
472                }
473        }
474
475        //success
476        return true;
477}
478
479bool DFAContentModel::handleRepetitions(const QName* const curElem,
480                                                                                unsigned int curState,
481                                                                                unsigned int currentLoop,
482                                                                                unsigned int& nextState,
483                                                                                unsigned int& nextLoop,
484                                                                                XMLSize_t elemIndex,
485                                                                                SubstitutionGroupComparator * comparator) const
486{
487        nextLoop = 0;
488        if (fCountingStates != 0) {
489                nextLoop = currentLoop;
490                Occurence* o = fCountingStates[curState];
491                if (o != 0) {
492                        if (curState == nextState) {
493                                if (++nextLoop > (unsigned int)o->maxOccurs && o->maxOccurs != -1) {
494                                        // It's likely that we looped too many times on the current state
495                                        // however it's possible that we actually matched another particle
496                                        // which allows the same name.
497                                        //
498                                        // Consider:
499                                        //
500                                        // <xs:sequence>
501                                        //  <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>
502                                        //  <xs:element name="foo" type="xs:string" fixed="bar"/>
503                                        // </xs:sequence>
504                                        //
505                                        // and
506                                        //
507                                        // <xs:sequence>
508                                        //  <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>
509                                        //  <xs:any namespace="##any" processContents="skip"/>
510                                        // </xs:sequence>
511                                        //
512                                        // In the DFA there will be two transitions from the current state which
513                                        // allow "foo". Note that this is not a UPA violation. The ambiguity of which
514                                        // transition to take is resolved by the current value of the counter. Since
515                                        // we've already seen enough instances of the first "foo" perhaps there is
516                                        // another element declaration or wildcard deeper in the element map which
517                                        // matches.
518                                        unsigned int tempNextState = 0;
519
520                                        while (++elemIndex < fElemMapSize) {
521                                                QName* inElem  = fElemMap[elemIndex];
522                                                ContentSpecNode::NodeTypes type = fElemMapType[elemIndex];
523                                                if (type == ContentSpecNode::Leaf)
524                                                {
525                                                        if(comparator!=0) {
526                                                                if (comparator->isEquivalentTo(curElem, inElem) )
527                                                                {
528                                                                        tempNextState = fTransTable[curState][elemIndex];
529                                                                        if (tempNextState != XMLContentModel::gInvalidTrans)
530                                                                                break;
531                                                                }
532                                                        }
533                                                        else if (fDTD) {
534                                                                if (XMLString::equals(inElem->getRawName(), curElem->getRawName())) {
535                                                                        tempNextState = fTransTable[curState][elemIndex];
536                                                                        if (tempNextState != XMLContentModel::gInvalidTrans)
537                                                                                break;
538                                                                }
539                                                        }
540                                                        else {
541                                                                if ((inElem->getURI() == curElem->getURI()) &&
542                                                                (XMLString::equals(inElem->getLocalPart(), curElem->getLocalPart()))) {
543                                                                        tempNextState = fTransTable[curState][elemIndex];
544                                                                        if (tempNextState != XMLContentModel::gInvalidTrans)
545                                                                                break;
546                                                                }
547                                                        }
548                                                }
549                                                else if ((type & 0x0f)== ContentSpecNode::Any)
550                                                {
551                                                        tempNextState = fTransTable[curState][elemIndex];
552                                                        if (tempNextState != XMLContentModel::gInvalidTrans)
553                                                                break;
554                                                }
555                                                else if ((type & 0x0f) == ContentSpecNode::Any_NS)
556                                                {
557                                                        if (inElem->getURI() == curElem->getURI())
558                                                        {
559                                                                tempNextState = fTransTable[curState][elemIndex];
560                                                                if (tempNextState != XMLContentModel::gInvalidTrans)
561                                                                        break;
562                                                        }
563                                                }
564                                                else if ((type & 0x0f) == ContentSpecNode::Any_Other)
565                                                {
566                                                        // Here we assume that empty string has id 1.
567                                                        //
568                                                        unsigned int uriId = curElem->getURI();
569                                                        if (uriId != 1 && uriId != inElem->getURI())
570                                                        {
571                                                                tempNextState = fTransTable[curState][elemIndex];
572                                                                if (tempNextState != XMLContentModel::gInvalidTrans)
573                                                                        break;
574                                                        }
575                                                }
576                                        }
577
578                                        // if we still can't find a match, report the error
579                                        if (elemIndex == fElemMapSize)
580                                                return false;
581
582                                        // if we found a match, set the next state and reset the
583                                        // counter if the next state is a counting state.
584                                        nextState = tempNextState;
585                                        Occurence* o = fCountingStates[nextState];
586                                        if (o != 0) {
587                                          nextLoop = (elemIndex == XMLSize_t (o->elemIndex)) ? 1 : 0;
588                                        }
589                                }
590                        }
591                        else if (nextLoop < (unsigned int)o->minOccurs) {
592                                // not enough loops on the current state.
593                                return false;
594                        }
595                        else {
596                                // Exiting a counting state. If we're entering a new
597                                // counting state, reset the counter.
598                                o = fCountingStates[nextState];
599                                if (o != 0) {
600                                  nextLoop = (elemIndex == XMLSize_t (o->elemIndex)) ? 1 : 0;
601                                }
602                        }
603                }
604                else {
605                        o = fCountingStates[nextState];
606                        if (o != 0) {
607                                // Entering a new counting state. Reset the counter.
608                                // If we've already seen one instance of the looping
609                                // particle set the counter to 1, otherwise set it
610                                // to 0.
611                          nextLoop = (elemIndex == XMLSize_t (o->elemIndex)) ? 1 : 0;
612                        }
613                }
614        }
615        return true;
616}
617
618// ---------------------------------------------------------------------------
619//  DFAContentModel: Private helper methods
620// ---------------------------------------------------------------------------
621void DFAContentModel::buildDFA(ContentSpecNode* const curNode)
622{
623        unsigned int index;
624
625        DEBUG_MESSAGE("DFAContentModel::buildDFA(" << curNode << ')');
626
627        //
628        //  The first step we need to take is to rewrite the content model using
629        //  our CMNode objects, and in the process get rid of any repetition short
630        //  cuts, converting them into '*' style repetitions or getting rid of
631        //  repetitions altogether.
632        //
633        //  The conversions done are:
634        //
635        //  x+ -> (x|x*)
636        //  x? -> (x|epsilon)
637        //
638        //  This is a relatively complex scenario. What is happening is that we
639        //  create a top level binary node of which the special EOC value is set
640        //  as the right side node. The the left side is set to the rewritten
641        //  syntax tree. The source is the original content model info from the
642        //  decl pool. The rewrite is done by buildSyntaxTree() which recurses the
643        //  decl pool's content of the element and builds a new tree in the
644        //  process.
645        //
646        //  Note that, during this operation, we set each non-epsilon leaf node's
647        //  DFA state position and count the number of such leafs, which is left
648        //  in the fLeafCount member.
649        //
650        fLeafCount=countLeafNodes(curNode);
651        fEOCPos = fLeafCount++;
652
653        //  We need to build an array of references to the non-epsilon
654        //  leaf nodes. We will put them in the array according to their position values
655        //
656        fLeafList = (CMLeaf**) fMemoryManager->allocate(fLeafCount*sizeof(CMLeaf*)); //new CMLeaf*[fLeafCount];
657        fLeafListType = (ContentSpecNode::NodeTypes*) fMemoryManager->allocate
658        (
659                fLeafCount * sizeof(ContentSpecNode::NodeTypes)
660        ); //new ContentSpecNode::NodeTypes[fLeafCount];
661        //
662        //  And, moving onward... We now need to build the follow position sets
663        //  for all the nodes. So we allocate an array of pointers to state sets,
664        //  one for each leaf node (i.e. each significant DFA position.)
665        //
666        fFollowList = (CMStateSet**) fMemoryManager->allocate
667        (
668                fLeafCount * sizeof(CMStateSet*)
669        ); //new CMStateSet*[fLeafCount];
670        for (index = 0; index < fLeafCount; index++)
671        {
672                fFollowList[index] = new (fMemoryManager) CMStateSet(fLeafCount, fMemoryManager);
673        }
674
675        //  The buildSyntaxTree function will recursively iterate over the ContentSpecNode
676        //  and build the CMNode hierarchy; it will also put every leaf node in the fLeafList
677        //  array, then calculate the first and last position sets of each node. This is
678        //  cached away in each of the nodes.
679        //
680        //  Along the way we also set the leaf count in each node as the maximum
681        //  state count. They must know this in order to create their first/last
682        //  position sets.
683        //
684        unsigned int counter=0;
685        CMNode* nodeOrgContent = buildSyntaxTree(curNode, counter);
686        //
687        //  Check to see whether this content model can handle an empty content,
688        //  which is something we need to optimize by looking now before we
689        //  throw away the info that would tell us that.
690        //
691        //  If the left node of the head (the top level of the original content)
692        //  is nullable, then its true.
693        //
694        fEmptyOk = nodeOrgContent->isNullable();
695
696        //
697        //  And handle specially the EOC node, which also must be numbered and
698        //  counted as a non-epsilon leaf node. It could not be handled in the
699        //  above tree build because it was created before all that started. We
700        //  save the EOC position since its used during the DFA building loop.
701        //
702        CMLeaf* nodeEOC = new (fMemoryManager) CMLeaf
703        (
704                new (fMemoryManager) QName
705                (
706                        XMLUni::fgZeroLenString
707                        , XMLUni::fgZeroLenString
708                        , XMLContentModel::gEOCFakeId
709                        , fMemoryManager
710                )
711                , fEOCPos
712                , true
713                , fLeafCount
714                , fMemoryManager
715        );
716        fHeadNode = new (fMemoryManager) CMBinaryOp
717        (
718                ContentSpecNode::Sequence
719                , nodeOrgContent
720                , nodeEOC
721                , fLeafCount
722                , fMemoryManager
723        );
724
725        //  Put also the final EOC node in the leaf array
726        fLeafList[counter] = new (fMemoryManager) CMLeaf
727        (
728                nodeEOC->getElement()
729                , nodeEOC->getPosition()
730                , fLeafCount
731                , fMemoryManager
732        );
733        fLeafListType[counter] = ContentSpecNode::Leaf;
734
735        //
736        //  Now handle our top level. We use our left child's last pos set and our
737        //  right child's first pos set, so get them now for convenience.
738        //
739        const CMStateSet& last  = nodeOrgContent->getLastPos();
740        const CMStateSet& first = nodeEOC->getFirstPos();
741
742        //
743        //  Now, for every position which is in our left child's last set
744        //  add all of the states in our right child's first set to the
745        //  follow set for that position.
746        //
747        CMStateSetEnumerator enumLast(&last);
748        while(enumLast.hasMoreElements())
749        {
750                XMLSize_t index=enumLast.nextElement();
751                *fFollowList[index] |= first;
752        }
753
754        //
755        //  And finally the big push... Now we build the DFA using all the states
756        //  and the tree we've built up. First we set up the various data
757        //  structures we are going to use while we do this.
758        //
759        //  First of all we need an array of unique element ids in our content
760        //  model. For each transition table entry, we need a set of contiguous
761        //  indices to represent the transitions for a particular input element.
762        //  So we need to a zero based range of indexes that map to element types.
763        //  This element map provides that mapping.
764        //
765        fElemMap = (QName**) fMemoryManager->allocate
766        (
767                fLeafCount * sizeof(QName*)
768        );
769
770        fElemMapType = (ContentSpecNode::NodeTypes*) fMemoryManager->allocate
771        (
772                fLeafCount * sizeof(ContentSpecNode::NodeTypes)
773        ); //new ContentSpecNode::NodeTypes[fLeafCount];
774        fElemMapSize = 0;
775
776        Occurence** elemOccurenceMap=0;
777        for (unsigned int outIndex = 0; outIndex < fLeafCount; outIndex++)
778        {
779                fElemMap[outIndex] = new (fMemoryManager) QName(fMemoryManager);
780
781                if ( (fLeafListType[outIndex] & 0x0f) != ContentSpecNode::Leaf )
782                        if (!fLeafNameTypeVector)
783                                fLeafNameTypeVector = new (fMemoryManager) ContentLeafNameTypeVector(fMemoryManager);
784
785                // Get the current leaf's element index
786                CMLeaf* leaf=fLeafList[outIndex];
787                const QName* element = leaf->getElement();
788                const XMLCh* elementRawName = 0;
789                if (fDTD && element)
790                        elementRawName = element->getRawName();
791
792                // See if the current leaf node's element index is in the list
793                unsigned int inIndex = 0;
794
795                for (; inIndex < fElemMapSize; inIndex++)
796                {
797                        const QName* inElem = fElemMap[inIndex];
798                        if (fDTD)
799                        {
800                                if (XMLString::equals(inElem->getRawName(), elementRawName))
801                                {
802                                        break;
803                                }
804                        }
805                        else
806                        {
807                                if ((fElemMapType[inIndex] == fLeafListType[outIndex]) &&
808                                        (inElem->getURI() == element->getURI()) &&
809                                        (XMLString::equals(inElem->getLocalPart(), element->getLocalPart())))
810                                {
811                                        break;
812                                }
813                        }
814                }
815
816                // If it was not in the list, then add it and bump the map size
817                if (inIndex == fElemMapSize)
818                {
819                        fElemMap[fElemMapSize]->setValues(*element);
820                        if(leaf->isRepeatableLeaf())
821                        {
822                                if (elemOccurenceMap == 0)
823                                {
824                                        elemOccurenceMap = (Occurence**)fMemoryManager->allocate(fLeafCount*sizeof(Occurence*));
825                                        memset(elemOccurenceMap, 0, fLeafCount*sizeof(Occurence*));
826                                }
827                                elemOccurenceMap[fElemMapSize] = new (fMemoryManager) Occurence(((CMRepeatingLeaf*)leaf)->getMinOccurs(), ((CMRepeatingLeaf*)leaf)->getMaxOccurs(), fElemMapSize);
828                        }
829                        fElemMapType[fElemMapSize] = fLeafListType[outIndex];
830                        ++fElemMapSize;
831                }
832        }
833
834        // set up the fLeafNameTypeVector object if there is one.
835        if (fLeafNameTypeVector)
836        {
837                fLeafNameTypeVector->setValues(fElemMap, fElemMapType, fElemMapSize);
838        }
839
840        /***
841         * Optimization(Jan, 2001); We sort fLeafList according to
842         * elemIndex which is *uniquely* associated to each leaf.
843         * We are *assuming* that each element appears in at least one leaf.
844         **/
845        // don't forget to delete it
846#ifdef OPTIMIZED_BUT_STILL_LINEAR_SEARCH
847        int *fLeafSorter = (int*) fMemoryManager->allocate
848        (
849                (fLeafCount + fElemMapSize) * sizeof(int)
850        ); //new int[fLeafCount + fElemMapSize];
851        unsigned int fSortCount = 0;
852
853        for (unsigned int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++)
854        {
855                const QName* element = fElemMap[elemIndex];
856                const XMLCh* elementRawName = 0;
857                if (fDTD && element)
858                        elementRawName = element->getRawName();
859
860                for (unsigned int leafIndex = 0; leafIndex < fLeafCount; leafIndex++)
861                {
862                        const QName* leaf = fLeafList[leafIndex]->getElement();
863                        if (fDTD) {
864                                if (XMLString::equals(leaf->getRawName(), elementRawName)) {
865                                        fLeafSorter[fSortCount++] = leafIndex;
866                                }
867                        }
868                        else {
869                                if ((fElemMapType[elemIndex] == fLeafListType[leafIndex]) &&
870                                        (leaf->getURI() == element->getURI()) &&
871                                        (XMLString::equals(leaf->getLocalPart(), element->getLocalPart()))) {
872                                          fLeafSorter[fSortCount++] = leafIndex;
873                                }
874                        }
875                }
876                fLeafSorter[fSortCount++] = -1;
877        }
878#endif
879
880        // instead of using a single array with -1 to separate elements, use a bidimensional map
881        unsigned int** fLeafSorter = (unsigned int**)fMemoryManager->allocate(fElemMapSize * sizeof(unsigned int*));
882        unsigned int* tmpSorter = (unsigned int*)fMemoryManager->allocate(fLeafCount * sizeof(unsigned int));
883        for (unsigned int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++)
884        {
885                const QName* element = fElemMap[elemIndex];
886                const XMLCh* elementRawName = 0;
887                if (fDTD && element)
888                        elementRawName = element->getRawName();
889
890                unsigned int fSortCount=0;
891                for (unsigned int leafIndex = 0; leafIndex < fLeafCount; leafIndex++)
892                {
893                        const QName* leaf = fLeafList[leafIndex]->getElement();
894                        if (fDTD) {
895                                if (XMLString::equals(leaf->getRawName(), elementRawName)) {
896                                        tmpSorter[fSortCount++] = leafIndex;
897                                }
898                        }
899                        else {
900                                if ((fElemMapType[elemIndex] == fLeafListType[leafIndex]) &&
901                                        (leaf->getURI() == element->getURI()) &&
902                                        (XMLString::equals(leaf->getLocalPart(), element->getLocalPart()))) {
903                                          tmpSorter[fSortCount++] = leafIndex;
904                                }
905                        }
906                }
907
908                fLeafSorter[elemIndex]=(unsigned int*)fMemoryManager->allocate((fSortCount+1) * sizeof(unsigned int));
909                fLeafSorter[elemIndex][0]=fSortCount;
910                for (unsigned int index=0;index<fSortCount;index++)
911                        fLeafSorter[elemIndex][index+1]=tmpSorter[index];
912        }
913        fMemoryManager->deallocate(tmpSorter);
914
915        //
916        //  Next lets create some arrays, some that that hold transient info
917        //  during the DFA build and some that are permament. These are kind of
918        //  sticky since we cannot know how big they will get, but we don't want
919        //  to use any collection type classes because of performance.
920        //
921        //  Basically they will probably be about fLeafCount*2 on average, but can
922        //  be as large as 2^(fLeafCount*2), worst case. So we start with
923        //  fLeafCount*4 as a middle ground. This will be very unlikely to ever
924        //  have to expand though, it if does, the overhead will be somewhat ugly.
925        //
926        unsigned int curArraySize = fLeafCount * 4;
927        CMStateSet** statesToDo = (CMStateSet**)
928                fMemoryManager->allocate
929                (
930                        curArraySize * sizeof(CMStateSet*)
931                ); //new const CMStateSet*[curArraySize];
932        fFinalStateFlags = (bool*) fMemoryManager->allocate
933        (
934                curArraySize * sizeof(bool)
935        ); //new bool[curArraySize];
936        fTransTable = (unsigned int**) fMemoryManager->allocate
937        (
938                curArraySize * sizeof(unsigned int*)
939        ); //new unsigned int*[curArraySize];
940
941        //
942        //  Ok we start with the initial set as the first pos set of the head node
943        //  (which is the seq node that holds the content model and the EOC node.)
944        //
945        CMStateSet* setT = new (fMemoryManager) CMStateSet(fHeadNode->getFirstPos());
946
947        //
948        // Note on memory leak: Bugzilla#2707:
949        // ===================================
950        // The CMBinary, pointed to by fHeadNode, shall be released by
951        // deleted by itself.
952        //
953        // fLeafList[] maintains its **OWN** copy of CMLeaf to avoid double deletion
954        // of CMLeaf.
955        //
956
957        delete fHeadNode;
958
959        //
960        //  Init our two state flags. Basically the unmarked state counter is
961        //  always chasing the current state counter. When it catches up, that
962        //  means we made a pass through that did not add any new states to the
963        //  lists, at which time we are done. We could have used a expanding array
964        //  of flags which we used to mark off states as we complete them, but
965        //  this is easier though less readable maybe.
966        //
967        unsigned int unmarkedState = 0;
968        unsigned int curState = 0;
969
970        //
971        //  Init the first transition table entry, and put the initial state
972        //  into the states to do list, then bump the current state.
973        //
974        fTransTable[curState] = makeDefStateList();
975        statesToDo[curState] = setT;
976        curState++;
977
978        //
979        // the stateTable is an auxiliary means to fast
980        // identification of new state created (instead
981        // of sequential loop statesToDo to find out),
982        // while the role that statesToDo plays remain unchanged.
983        //
984        RefHashTableOf<XMLInteger, CMStateSetHasher> *stateTable =
985                new (fMemoryManager) RefHashTableOf<XMLInteger, CMStateSetHasher>
986                (
987                        curArraySize
988                        , true
989                        , fMemoryManager
990                );
991        //stateTable->put((CMStateSet*)setT, new (fMemoryManager) XMLInteger(0));
992
993        //
994        //  Ok, almost done with the algorithm from hell... We now enter the
995        //  loop where we go until the states done counter catches up with
996        //  the states to do counter.
997        //
998        CMStateSet* newSet = 0;
999        while (unmarkedState < curState)
1000        {
1001                //
1002                //  Get the next unmarked state out of the list of states to do.
1003                //  And get the associated transition table entry.
1004                //
1005                setT = statesToDo[unmarkedState];
1006                unsigned int* transEntry = fTransTable[unmarkedState];
1007
1008                // Mark this one final if it contains the EOC state
1009                fFinalStateFlags[unmarkedState] = setT->getBit(fEOCPos);
1010
1011                // Bump up the unmarked state count, marking this state done
1012                unmarkedState++;
1013
1014#ifdef OPTIMIZED_BUT_STILL_LINEAR_SEARCH
1015                // Optimization(Jan, 2001)
1016                unsigned int sorterIndex = 0;
1017                // Optimization(Jan, 2001)
1018#endif
1019
1020                // Loop through each possible input symbol in the element map
1021                for (unsigned int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++)
1022                {
1023                        //
1024                        //  Build up a set of states which is the union of all of the
1025                        //  follow sets of DFA positions that are in the current state. If
1026                        //  we gave away the new set last time through then create a new
1027                        //  one. Otherwise, zero out the existing one.
1028                        //
1029                        if (!newSet)
1030                                newSet = new (fMemoryManager) CMStateSet
1031                                (
1032                                        fLeafCount
1033                                        , fMemoryManager
1034                                );
1035                        else
1036                                newSet->zeroBits();
1037
1038#ifdef OBSOLETED
1039// unoptimized code
1040                        for (unsigned int leafIndex = 0; leafIndex < fLeafCount; leafIndex++)
1041                        {
1042                                // If this leaf index (DFA position) is in the current set...
1043                                if (setT->getBit(leafIndex))
1044                                {
1045                                        //
1046                                        //  If this leaf is the current input symbol, then we want
1047                                        //  to add its follow list to the set of states to transition
1048                                        //  to from the current state.
1049                                        //
1050                                        const QName* leaf = fLeafList[leafIndex]->getElement();
1051                                        const QName* element = fElemMap[elemIndex];
1052                                        if (fDTD) {
1053                                                if (XMLString::equals(leaf->getRawName(), element->getRawName())) {
1054                                                        *newSet |= *fFollowList[leafIndex];
1055                                                }
1056                                        }
1057                                        else {
1058                                                if ((leaf->getURI() == element->getURI()) &&
1059                                                        (XMLString::equals(leaf->getLocalPart(), element->getLocalPart()))) {
1060                                                        *newSet |= *fFollowList[leafIndex];
1061                                                }
1062                                        }
1063                                }
1064                        } // for leafIndex
1065#endif
1066
1067#ifdef OPTIMIZED_BUT_STILL_LINEAR_SEARCH
1068                        // Optimization(Jan, 2001)
1069                        int leafIndex = fLeafSorter[sorterIndex++];
1070
1071                        while (leafIndex != -1)
1072                        {
1073                                // If this leaf index (DFA position) is in the current set...
1074                                if (setT->getBit(leafIndex))
1075                                {
1076                                        //
1077                                        //  If this leaf is the current input symbol, then we
1078                                        //  want to add its follow list to the set of states to
1079                                        //  transition to from the current state.
1080                                        //
1081                                        *newSet |= *fFollowList[leafIndex];
1082                                }
1083                                leafIndex = fLeafSorter[sorterIndex++];
1084                        } // while (leafIndex != -1)
1085#endif
1086
1087                        unsigned int* fLeafIndexes=fLeafSorter[elemIndex];
1088                        unsigned int fNumItems=fLeafIndexes[0];
1089                        if(fNumItems!=0)
1090                        {
1091                                // The algorithm requires finding the leaf that is present both in the bitfield of the current state, and in the
1092                                // list of places where the currently tested item can appear. When this occurs, the follow list of this parent item
1093                                // is added to the bitfield representing the next state.
1094                                // Both the bitfield and the list of places are sorted, so we can analyze them in two ways; either iterating over the
1095                                // parent items, testing the bitfield for the existence of the parent (N times a constant Tb), or by iterating over the
1096                                // bitfield (restricted to the range of the sorted list of places), using a binary search to locate the leaf in the
1097                                // sorted list of places (M times log(N) testing operations Ts)
1098                                // Assuming that the time to test a bit is roughly the same of the time needed to compute the average of two integers,
1099                                // plus a couple of comparisons and additions, we compare N agains M*log(N) to decide which algorithm should be faster given
1100                                // the two sets
1101                                if(fNumItems <= setT->getBitCountInRange(fLeafIndexes[1], fLeafIndexes[fNumItems])*log((float)fNumItems))
1102                                {
1103                                        for(unsigned int i=1; i<=fNumItems; ++i)
1104                                                if(setT->getBit(fLeafIndexes[i]))
1105                                                {
1106                                                        //
1107                                                        //  If this leaf is the current input symbol, then we
1108                                                        //  want to add its follow list to the set of states to
1109                                                        //  transition to from the current state.
1110                                                        //
1111                                                        *newSet |= *fFollowList[ fLeafIndexes[i] ];
1112                                                }
1113                                }
1114                                else
1115                                {
1116                                        // Further optimization: given that the bitfield enumerator returns the numbers in order,
1117                                        // every time we raise the lower marker we know it will true also for the next bits, so
1118                                        // the next binary search will not start from 1 but from this index
1119                                        unsigned int lowIndex = 1;
1120                                        // Start the enumerator from the first index in the sorted list of places,
1121                                        // as nothing before that point will match
1122                                        CMStateSetEnumerator enumBits(setT, fLeafIndexes[1]);
1123                                        while(enumBits.hasMoreElements())
1124                                        {
1125                                                unsigned int bitIndex=enumBits.nextElement();
1126                                                // if this leaf is greater than the last index in the sorted list of places,
1127                                                // nothing can be found from now on, so get out of here
1128                                                if(bitIndex > fLeafIndexes[fNumItems])
1129                                                        break;
1130
1131                                                // Check if this leaf index (DFA position) is in the current set
1132                                                // (using binary search: the indexes are sorted)
1133                                                unsigned int first=lowIndex,last=fNumItems,i;
1134                                                while(first<=last)
1135                                                {
1136                                                        i=(first+last)/2;
1137                                                        if(fLeafIndexes[i]>bitIndex)
1138                                                                last=i-1;
1139                                                        else if(fLeafIndexes[i]<bitIndex)
1140                                                                lowIndex=first=i+1;
1141                                                        else
1142                                                        {
1143                                                                //
1144                                                                //  If this leaf is the current input symbol, then we
1145                                                                //  want to add its follow list to the set of states to
1146                                                                //  transition to from the current state.
1147                                                                //
1148                                                                *newSet |= *fFollowList[bitIndex];
1149                                                                break;
1150                                                        }
1151                                                }
1152                                        }
1153                                }
1154                        }
1155
1156                        //
1157                        //  If this new set is not empty, then see if its in the list
1158                        //  of states to do. If not, then add it.
1159                        //
1160                        if (!newSet->isEmpty())
1161                        {
1162                                //
1163                                //  Search the 'states to do' list to see if this new
1164                                //  state set is already in there.
1165                                //
1166                                /***
1167                                unsigned int stateIndex = 0;
1168                                for (; stateIndex < curState; stateIndex++)
1169                                {
1170                                        if (*statesToDo[stateIndex] == *newSet)
1171                                                break;
1172                                }
1173                                ***/
1174
1175                                XMLInteger *stateObj = stateTable->get(newSet);
1176                                unsigned int stateIndex = (stateObj == 0 ? curState : stateObj->intValue());
1177
1178                                // If we did not find it, then add it
1179                                if (stateIndex == curState)
1180                                {
1181                                        //
1182                                        //  Put this new state into the states to do and init
1183                                        //  a new entry at the same index in the transition
1184                                        //  table.
1185                                        //
1186                                        statesToDo[curState] = newSet;
1187                                        fTransTable[curState] = makeDefStateList();
1188                                        stateTable->put
1189                                        (
1190                                                newSet
1191                                                , new (fMemoryManager) XMLInteger(curState)
1192                                        );
1193
1194                                        // We now have a new state to do so bump the count
1195                                        curState++;
1196
1197                                        //
1198                                        //  Null out the new set to indicate we adopted it. This
1199                                        //  will cause the creation of a new set on the next time
1200                                        //  around the loop.
1201                                        //
1202                                        newSet = 0;
1203                                }
1204
1205                                //
1206                                //  Now set this state in the transition table's entry for this
1207                                //  element (using its index), with the DFA state we will move
1208                                //  to from the current state when we see this input element.
1209                                //
1210                                transEntry[elemIndex] = stateIndex;
1211
1212                                // Expand the arrays if we're full
1213                                if (curState == curArraySize)
1214                                {
1215                                        //
1216                                        //  Yikes, we overflowed the initial array size, so we've
1217                                        //  got to expand all of these arrays. So adjust up the
1218                                        //  size by 50% and allocate new arrays.
1219                                        //
1220                                        const unsigned int newSize = (unsigned int)(curArraySize * 1.5);
1221                                        CMStateSet** newToDo = (CMStateSet**)
1222                                                fMemoryManager->allocate
1223                                                (
1224                                                        newSize * sizeof(CMStateSet*)
1225                                                ); //new const CMStateSet*[newSize];
1226                                        bool* newFinalFlags = (bool*) fMemoryManager->allocate
1227                                        (
1228                                                newSize * sizeof(bool)
1229                                        ); //new bool[newSize];
1230                                        unsigned int** newTransTable = (unsigned int**)
1231                                                fMemoryManager->allocate
1232                                                (
1233                                                        newSize * sizeof(unsigned int*)
1234                                                ); //new unsigned int*[newSize];
1235
1236                                        // Copy over all of the existing content
1237                                        for (unsigned int expIndex = 0; expIndex < curArraySize; expIndex++)
1238                                        {
1239                                                newToDo[expIndex] = statesToDo[expIndex];
1240                                                newFinalFlags[expIndex] = fFinalStateFlags[expIndex];
1241                                                newTransTable[expIndex] = fTransTable[expIndex];
1242                                        }
1243
1244                                        // Clean up the old stuff
1245                                        fMemoryManager->deallocate(statesToDo); //delete [] statesToDo;
1246                                        fMemoryManager->deallocate(fFinalStateFlags); //delete [] fFinalStateFlags;
1247                                        fMemoryManager->deallocate(fTransTable); //delete [] fTransTable;
1248
1249                                        // Store the new array size and pointers
1250                                        curArraySize = newSize;
1251                                        statesToDo = newToDo;
1252                                        fFinalStateFlags = newFinalFlags;
1253                                        fTransTable = newTransTable;
1254                                } //if (curState == curArraySize)
1255                        } //if (!newSet->isEmpty())
1256                } // for elemIndex
1257        } //while
1258
1259        // Store the current state count in the trans table size
1260        fTransTableSize = curState;
1261
1262        //
1263        // Fill in the occurence information for each looping state
1264        // if we're using counters.
1265        //
1266        if (elemOccurenceMap != 0) {
1267                fCountingStates = (Occurence**)fMemoryManager->allocate(fTransTableSize*sizeof(Occurence));
1268                memset(fCountingStates, 0, fTransTableSize*sizeof(Occurence*));
1269                for (unsigned int i = 0; i < fTransTableSize; ++i) {
1270                        unsigned int * transitions = fTransTable[i];
1271                        for (unsigned int j = 0; j < fElemMapSize; ++j) {
1272                                if (i == transitions[j]) {
1273                                        Occurence* old=elemOccurenceMap[j];
1274                                        if(old!=0)
1275                                                fCountingStates[i] = new (fMemoryManager) Occurence(old->minOccurs, old->maxOccurs, old->elemIndex);
1276                                        break;
1277                                }
1278                        }
1279                }
1280                for (unsigned int j = 0; j < fLeafCount; ++j) {
1281                        if(elemOccurenceMap[j]!=0)
1282                                delete elemOccurenceMap[j];
1283                }
1284                fMemoryManager->deallocate(elemOccurenceMap);
1285        }
1286
1287        // If the last temp set was not stored, then clean it up
1288        if (newSet)
1289                delete newSet;
1290
1291        //
1292        //  Now we can clean up all of the temporary data that was needed during
1293        //  DFA build.
1294        //
1295
1296        for (index = 0; index < fLeafCount; index++)
1297                delete fFollowList[index];
1298        fMemoryManager->deallocate(fFollowList); //delete [] fFollowList;
1299
1300        //
1301        // removeAll() will delete all data, XMLInteger,
1302        // while the keys are to be deleted by the
1303        // deletion of statesToDo.
1304        //
1305        delete stateTable;
1306
1307        for (index = 0; index < curState; index++)
1308                delete statesToDo[index];
1309        fMemoryManager->deallocate(statesToDo); //delete [] statesToDo;
1310
1311        for (index = 0; index < fLeafCount; index++)
1312                delete fLeafList[index];
1313        fMemoryManager->deallocate(fLeafList); //delete [] fLeafList;
1314
1315#ifdef OPTIMIZED_BUT_STILL_LINEAR_SEARCH
1316        fMemoryManager->deallocate(fLeafSorter); //delete [] fLeafSorter;
1317#endif
1318        for (index=0; index < fElemMapSize; index++)
1319                fMemoryManager->deallocate(fLeafSorter[index]);
1320        fMemoryManager->deallocate(fLeafSorter);
1321}
1322
1323unsigned int DFAContentModel::countLeafNodes(ContentSpecNode* const curNode)
1324{
1325        unsigned int count = 0;
1326
1327        // Get the spec type of the passed node
1328        const ContentSpecNode::NodeTypes curType = curNode->getType();
1329
1330        if ((curType & 0x0f) == ContentSpecNode::Any
1331                || (curType & 0x0f) == ContentSpecNode::Any_Other
1332                || (curType & 0x0f) == ContentSpecNode::Any_NS
1333                || curType == ContentSpecNode::Leaf
1334                || curType == ContentSpecNode::Loop)
1335        {
1336                count++;
1337        }
1338        else
1339        {
1340                //
1341                //  Its not a leaf, so we have to recurse its left and maybe right
1342                //  nodes. Save both values before we recurse and trash the node.
1343                //
1344                ContentSpecNode* leftNode = curNode->getFirst();
1345                ContentSpecNode* rightNode = curNode->getSecond();
1346
1347                // Detect if we have a deep tree that can be analyzed using a loop instead of recursion
1348                unsigned int nLoopCount=0;
1349                ContentSpecNode* cursor=curNode;
1350                while(cursor->getType()==ContentSpecNode::Sequence && cursor->getFirst() && cursor->getFirst()->getSecond()==rightNode)
1351                {
1352                        nLoopCount++;
1353                        cursor=cursor->getFirst();
1354                }
1355                if(nLoopCount!=0)
1356                {
1357                        count += countLeafNodes(cursor);
1358                        for(unsigned int i=0;i<nLoopCount;i++)
1359                                count += countLeafNodes(rightNode);
1360                        return count;
1361                }
1362                if(leftNode)
1363                        count+=countLeafNodes(leftNode);
1364                if(rightNode)
1365                        count+=countLeafNodes(rightNode);
1366        }
1367        return count;
1368}
1369
1370CMNode* DFAContentModel::buildSyntaxTree(ContentSpecNode* const curNode
1371                                                                                 , unsigned int&        curIndex)
1372{
1373        // Initialize a return node pointer
1374        CMNode* retNode = 0;
1375
1376        // Get the spec type of the passed node
1377        const ContentSpecNode::NodeTypes curType = curNode->getType();
1378
1379        if ((curType & 0x0f) == ContentSpecNode::Any
1380                || (curType & 0x0f) == ContentSpecNode::Any_Other
1381                || (curType & 0x0f) == ContentSpecNode::Any_NS)
1382        {
1383                retNode = new (fMemoryManager) CMAny
1384                (
1385                        curType
1386                        , curNode->getElement()->getURI()
1387                        , curIndex
1388                        , fLeafCount
1389                        , fMemoryManager
1390                );
1391                fLeafList[curIndex] = new (fMemoryManager) CMLeaf
1392                (
1393                        new (fMemoryManager) QName
1394                        (
1395                                XMLUni::fgZeroLenString
1396                                , XMLUni::fgZeroLenString
1397                                , curNode->getElement()->getURI()
1398                                , fMemoryManager
1399                        )
1400                        , curIndex
1401                        , true
1402                        , fLeafCount
1403                        , fMemoryManager
1404                );
1405                fLeafListType[curIndex] = curType;
1406                ++curIndex;
1407        }
1408        else if (curType == ContentSpecNode::Leaf)
1409        {
1410                //
1411                //  Create a new leaf node, and pass it the current leaf count, which
1412                //  is its DFA state position. Bump the leaf count after storing it.
1413                //  This makes the positions zero based since we store first and then
1414                //  increment.
1415                //
1416                retNode = new (fMemoryManager) CMLeaf
1417                (
1418                        curNode->getElement()
1419                        , curIndex
1420                        , fLeafCount
1421                        , fMemoryManager
1422                );
1423                fLeafList[curIndex] = new (fMemoryManager) CMLeaf
1424                (
1425                        curNode->getElement()
1426                        , curIndex
1427                        , fLeafCount
1428                        , fMemoryManager
1429                );
1430                fLeafListType[curIndex] = ContentSpecNode::Leaf;
1431                ++curIndex;
1432        }
1433        else if (curType == ContentSpecNode::Loop)
1434        {
1435                //
1436                //  Create a new leaf node, and pass it the current leaf count, which
1437                //  is its DFA state position. Bump the leaf count after storing it.
1438                //  This makes the positions zero based since we store first and then
1439                //  increment.
1440                //
1441                retNode = new (fMemoryManager) CMRepeatingLeaf
1442                (
1443                        curNode->getFirst()->getElement()
1444                        , curNode->getMinOccurs()
1445                        , curNode->getMaxOccurs()
1446                        , curIndex
1447                        , fLeafCount
1448                        , fMemoryManager
1449                );
1450                fLeafList[curIndex] = new (fMemoryManager) CMRepeatingLeaf
1451                (
1452                        curNode->getFirst()->getElement()
1453                        , curNode->getMinOccurs()
1454                        , curNode->getMaxOccurs()
1455                        , curIndex
1456                        , fLeafCount
1457                        , fMemoryManager
1458                );
1459                fLeafListType[curIndex] = curNode->getFirst()->getType();
1460                ++curIndex;
1461        }
1462         else
1463        {
1464                //
1465                //  Its not a leaf, so we have to recurse its left and maybe right
1466                //  nodes. Save both values before we recurse and trash the node.
1467                //
1468                ContentSpecNode* leftNode = curNode->getFirst();
1469                ContentSpecNode* rightNode = curNode->getSecond();
1470
1471                // Detect if we have a deep tree that can be analyzed using a loop instead of recursion
1472                unsigned int nLoopCount=0;
1473                ContentSpecNode* cursor=curNode;
1474                while(cursor->getType()==ContentSpecNode::Sequence && cursor->getFirst() && cursor->getFirst()->getSecond()==rightNode)
1475                {
1476                        nLoopCount++;
1477                        cursor=cursor->getFirst();
1478                }
1479                if(nLoopCount!=0)
1480                {
1481                        retNode = buildSyntaxTree(cursor, curIndex);
1482                        for(unsigned int i=0;i<nLoopCount;i++)
1483                        {
1484                                CMNode* newRight = buildSyntaxTree(rightNode, curIndex);
1485                                //
1486                                //  Now handle our level. We use our left child's last pos set and our
1487                                //  right child's first pos set, so get them now for convenience.
1488                                //
1489                                const CMStateSet& last  = retNode->getLastPos();
1490                                const CMStateSet& first = newRight->getFirstPos();
1491
1492                                //
1493                                //  Now, for every position which is in our left child's last set
1494                                //  add all of the states in our right child's first set to the
1495                                //  follow set for that position.
1496                                //
1497                                CMStateSetEnumerator enumLast(&last);
1498                                while(enumLast.hasMoreElements())
1499                                {
1500                                        XMLSize_t index=enumLast.nextElement();
1501                                        *fFollowList[index] |= first;
1502                                }
1503                                retNode = new (fMemoryManager) CMBinaryOp
1504                                (
1505                                        ContentSpecNode::Sequence
1506                                        , retNode
1507                                        , newRight
1508                                        , fLeafCount
1509                                        , fMemoryManager
1510                                );
1511                        }
1512                        return retNode;
1513                }
1514
1515                if (((curType & 0x0f) == ContentSpecNode::Choice)
1516                ||   ((curType & 0x0f) == ContentSpecNode::Sequence))
1517                {
1518                        //
1519                        //  Recurse on both children, and return a binary op node with the
1520                        //  two created sub nodes as its children. The node type is the
1521                        //  same type as the source.
1522                        //
1523                        CMNode* newLeft = buildSyntaxTree(leftNode, curIndex);
1524                        CMNode* newRight = buildSyntaxTree(rightNode, curIndex);
1525                        if(((curType & 0x0f) == ContentSpecNode::Sequence))
1526                        {
1527                                //
1528                                //  Now handle our level. We use our left child's last pos set and our
1529                                //  right child's first pos set, so get them now for convenience.
1530                                //
1531                                const CMStateSet& last  = newLeft->getLastPos();
1532                                const CMStateSet& first = newRight->getFirstPos();
1533
1534                                //
1535                                //  Now, for every position which is in our left child's last set
1536                                //  add all of the states in our right child's first set to the
1537                                //  follow set for that position.
1538                                //
1539                                CMStateSetEnumerator enumLast(&last);
1540                                while(enumLast.hasMoreElements())
1541                                {
1542                                        XMLSize_t index=enumLast.nextElement();
1543                                        *fFollowList[index] |= first;
1544                                }
1545                        }
1546                        retNode = new (fMemoryManager) CMBinaryOp
1547                        (
1548                                curType
1549                                , newLeft
1550                                , newRight
1551                                , fLeafCount
1552                                , fMemoryManager
1553                        );
1554                }
1555                 else if (curType == ContentSpecNode::ZeroOrMore
1556                           || curType == ContentSpecNode::ZeroOrOne
1557                           || curType == ContentSpecNode::OneOrMore)
1558                {
1559                        CMNode* newChild = buildSyntaxTree(leftNode, curIndex);
1560                        if (curType == ContentSpecNode::ZeroOrMore
1561                           || curType == ContentSpecNode::OneOrMore)
1562                        {
1563                                //
1564                                //  Now handle our level. We use our own first and last position
1565                                //  sets, so get them up front.
1566                                //
1567                                const CMStateSet& first = newChild->getFirstPos();
1568                                const CMStateSet& last  = newChild->getLastPos();
1569
1570                                //
1571                                //  For every position which is in our last position set, add all
1572                                //  of our first position states to the follow set for that
1573                                //  position.
1574                                //
1575                                CMStateSetEnumerator enumLast(&last);
1576                                while(enumLast.hasMoreElements())
1577                                {
1578                                        XMLSize_t index=enumLast.nextElement();
1579                                        *fFollowList[index] |= first;
1580                                }
1581                        }
1582                        // This one is fine as is, just change to our form
1583                        retNode = new (fMemoryManager) CMUnaryOp
1584                        (
1585                                curType
1586                                , newChild
1587                                , fLeafCount
1588                                , fMemoryManager
1589                        );
1590                }
1591                 else
1592                {
1593                        ThrowXMLwithMemMgr(RuntimeException, XMLExcepts::CM_UnknownCMSpecType, fMemoryManager);
1594                }
1595        }
1596        // fault in the first and last pos, then delete it children
1597        retNode->getFirstPos();
1598        retNode->getLastPos();
1599        retNode->orphanChild();
1600        return retNode;
1601}
1602
1603//
1604//  gInvalidTrans is used to represent bad transitions in the transition table
1605//  entry for each state. So each entry is initialized to that value. This
1606//  method creates a new entry and initializes it.
1607//
1608unsigned int* DFAContentModel::makeDefStateList() const
1609{
1610        unsigned int* retArray = (unsigned int*) fMemoryManager->allocate
1611        (
1612                fElemMapSize * sizeof(unsigned int)
1613        ); //new unsigned int[fElemMapSize];
1614        for (unsigned int index = 0; index < fElemMapSize; index++)
1615                retArray[index] = XMLContentModel::gInvalidTrans;
1616        return retArray;
1617}
1618
1619ContentLeafNameTypeVector* DFAContentModel::getContentLeafNameTypeVector() const
1620{
1621   //later change it to return the data member
1622        return fLeafNameTypeVector;
1623}
1624
1625void DFAContentModel::checkUniqueParticleAttribution
1626(
1627        SchemaGrammar*    const                 pGrammar
1628        , GrammarResolver*  const               pGrammarResolver
1629        , XMLNamespaceResolver* const   pUriResolver
1630        , XMLValidator*     const               pValidator
1631        , unsigned int*     const               pContentSpecOrgURI
1632        , const XMLCh*                                  pComplexTypeName /*= 0*/
1633)
1634{
1635        SubstitutionGroupComparator comparator(pGrammarResolver, pUriResolver);
1636
1637        unsigned int i, j, k;
1638
1639        // Rename the URI back
1640        for (i = 0; i < fElemMapSize; i++) {
1641
1642                unsigned int orgURIIndex = fElemMap[i]->getURI();
1643
1644                if ((orgURIIndex != XMLContentModel::gEOCFakeId) &&
1645                        (orgURIIndex != XMLContentModel::gEpsilonFakeId) &&
1646                        (orgURIIndex != XMLElementDecl::fgInvalidElemId) &&
1647                        (orgURIIndex != XMLElementDecl::fgPCDataElemId)) {
1648                        fElemMap[i]->setURI(pContentSpecOrgURI[orgURIIndex]);
1649                }
1650        }
1651
1652        // Unique Particle Attribution
1653        // Store the conflict results between any two elements in fElemMap
1654        // 0 - not yet tested, 1 - conflict, (-1) - no conflict
1655        signed char** conflictTable = (signed char**) fMemoryManager->allocate
1656        (
1657                fElemMapSize * sizeof(signed char*)
1658        );
1659
1660        // initialize the conflict table
1661        for (j = 0; j < fElemMapSize; j++) {
1662                conflictTable[j] = (signed char*) fMemoryManager->allocate
1663                (
1664                        fElemMapSize * sizeof(signed char)
1665                );
1666                memset(conflictTable[j], 0, fElemMapSize*sizeof(signed char));
1667        }
1668
1669        // for each state, check whether it has overlap transitions
1670        for (i = 0; i < fTransTableSize; i++) {
1671                for (j = 0; j < fElemMapSize; j++) {
1672                        for (k = j+1; k < fElemMapSize; k++) {
1673                                if (fTransTable[i][j] != XMLContentModel::gInvalidTrans &&
1674                                        fTransTable[i][k] != XMLContentModel::gInvalidTrans &&
1675                                        conflictTable[j][k] == 0) {
1676
1677                                        // If this is text in a Schema mixed content model, skip it.
1678                                        if ( fIsMixed &&
1679                                                 (( fElemMap[j]->getURI() == XMLElementDecl::fgPCDataElemId) ||
1680                                                  ( fElemMap[k]->getURI() == XMLElementDecl::fgPCDataElemId)))
1681                                                continue;
1682
1683                                        if (XercesElementWildcard::conflict(pGrammar,
1684                                                                                                                fElemMapType[j],
1685                                                                                                                fElemMap[j],
1686                                                                                                                fElemMapType[k],
1687                                                                                                                fElemMap[k],
1688                                                                                                                &comparator)) {
1689                                                if (fCountingStates != 0) {
1690                                                        Occurence* o = fCountingStates[i];
1691                                                        // If "i" is a counting state and exactly one of the transitions
1692                                                        // loops back to "i" then the two particles do not overlap if
1693                                                        // minOccurs == maxOccurs.
1694                                                        if (o != 0 &&
1695                                                                ((fTransTable[i][j] == i) ^ (fTransTable[i][k] == i)) &&
1696                                                                o->minOccurs == o->maxOccurs) {
1697                                                                conflictTable[j][k] = -1;
1698                                                                continue;
1699                                                        }
1700                                                }
1701                                           conflictTable[j][k] = 1;
1702
1703                                           XMLBuffer buf1(1023, fMemoryManager);
1704                                           if (((fElemMapType[j] & 0x0f) == ContentSpecNode::Any) ||
1705                                                   ((fElemMapType[j] & 0x0f) == ContentSpecNode::Any_NS))
1706                                                   buf1.set(SchemaSymbols::fgATTVAL_TWOPOUNDANY);
1707                                           else if ((fElemMapType[j] & 0x0f) == ContentSpecNode::Any_Other)
1708                                                   buf1.set(SchemaSymbols::fgATTVAL_TWOPOUNDOTHER);
1709                                           else
1710                                                   buf1.set(fElemMap[j]->getRawName());
1711
1712                                           XMLBuffer buf2(1023, fMemoryManager);
1713                                           if (((fElemMapType[k] & 0x0f) == ContentSpecNode::Any) ||
1714                                                   ((fElemMapType[k] & 0x0f) == ContentSpecNode::Any_NS))
1715                                                   buf2.set(SchemaSymbols::fgATTVAL_TWOPOUNDANY);
1716                                           else if ((fElemMapType[k] & 0x0f) == ContentSpecNode::Any_Other)
1717                                                   buf2.set(SchemaSymbols::fgATTVAL_TWOPOUNDOTHER);
1718                                           else
1719                                                   buf2.set(fElemMap[k]->getRawName());
1720
1721                                           pValidator->emitError(XMLValid::UniqueParticleAttributionFail,
1722                                                                                         pComplexTypeName,
1723                                                                                         buf1.getRawBuffer(),
1724                                                                                         buf2.getRawBuffer());
1725                                        }
1726                                        else
1727                                                conflictTable[j][k] = -1;
1728                                }
1729                        }
1730                }
1731        }
1732
1733        for (i = 0; i < fElemMapSize; i++)
1734                fMemoryManager->deallocate(conflictTable[i]);
1735        fMemoryManager->deallocate(conflictTable);
1736}
1737
1738
1739bool DFAContentModel::validateContent
1740(
1741        QName** const
1742  , XMLSize_t
1743  , unsigned int
1744  , XMLSize_t*
1745  , MemoryManager*  const
1746)
1747const
1748{
1749        DEPRECATED_FEATURE_IN_ICXML;
1750}
1751
1752bool DFAContentModel::validateContentSpecial
1753(
1754        QName** const
1755  , XMLSize_t
1756  , unsigned int
1757  , GrammarResolver*  const
1758  , XMLStringPool*    const
1759  , XMLSize_t*
1760  , MemoryManager*    const
1761)
1762const
1763{
1764        DEPRECATED_FEATURE_IN_ICXML;
1765}
1766
1767void DFAContentModel::checkUniqueParticleAttribution
1768(
1769        SchemaGrammar*    const
1770  , GrammarResolver*  const
1771  , XMLStringPool*    const
1772  , XMLValidator*     const
1773  , unsigned int*     const
1774  , const XMLCh*
1775)
1776{
1777        DEPRECATED_FEATURE_IN_ICXML;
1778}
1779
1780XERCES_CPP_NAMESPACE_END
Note: See TracBrowser for help on using the repository browser.