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

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

Additional files for icXML 0.9

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