开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多国语言处理 > 词法分析 > 查看源码
DFAContentModel.cpp
资源名称：xerces-c-src_2_3_0.zip　[点击查看]
上传用户：zhuqijet
上传日期：2013-06-25
资源大小：10074k
文件大小：53k
源码类别：

词法分析

开发平台：

Visual C++

DFAContentModel.cpp：源码内容
  1. /*
  2.  * The Apache Software License, Version 1.1
  3.  *
  4.  * Copyright (c) 1999-2001 The Apache Software Foundation.  All rights
  5.  * reserved.
  6.  *
  7.  * Redistribution and use in source and binary forms, with or without
  8.  * modification, are permitted provided that the following conditions
  9.  * are met:
  10.  *
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  *
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in
  16.  *    the documentation and/or other materials provided with the
  17.  *    distribution.
  18.  *
  19.  * 3. The end-user documentation included with the redistribution,
  20.  *    if any, must include the following acknowledgment:
  21.  *       "This product includes software developed by the
  22.  *        Apache Software Foundation (http://www.apache.org/)."
  23.  *    Alternately, this acknowledgment may appear in the software itself,
  24.  *    if and wherever such third-party acknowledgments normally appear.
  25.  *
  26.  * 4. The names "Xerces" and "Apache Software Foundation" must
  27.  *    not be used to endorse or promote products derived from this
  28.  *    software without prior written permission. For written
  29.  *    permission, please contact apache@apache.org.
  30.  *
  31.  * 5. Products derived from this software may not be called "Apache",
  32.  *    nor may "Apache" appear in their name, without prior written
  33.  *    permission of the Apache Software Foundation.
  34.  *
  35.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
  36.  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  37.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  38.  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
  39.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  40.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  41.  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  42.  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  43.  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  44.  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  45.  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  46.  * SUCH DAMAGE.
  47.  * ====================================================================
  48.  *
  49.  * This software consists of voluntary contributions made by many
  50.  * individuals on behalf of the Apache Software Foundation, and was
  51.  * originally based on software copyright (c) 1999, International
  52.  * Business Machines, Inc., http://www.ibm.com .  For more information
  53.  * on the Apache Software Foundation, please see
  54.  * <http://www.apache.org/>.
  55.  */
  57. /*
  58.  * $Log: DFAContentModel.cpp,v $
  59.  * Revision 1.7  2003/05/18 14:02:06  knoaman
  60.  * Memory manager implementation: pass per instance manager.
  61.  *
  62.  * Revision 1.6  2003/05/16 21:43:20  knoaman
  63.  * Memory manager implementation: Modify constructors to pass in the memory manager.
  64.  *
  65.  * Revision 1.5  2003/05/15 18:48:27  knoaman
  66.  * Partial implementation of the configurable memory manager.
  67.  *
  68.  * Revision 1.4  2002/11/04 14:54:58  tng
  69.  * C++ Namespace Support.
  70.  *
  71.  * Revision 1.3  2002/09/24 19:48:39  tng
  72.  * Performance: use XMLString::equals instead of XMLString::compareString
  73.  *
  74.  * Revision 1.2  2002/02/25 21:18:53  tng
  75.  * Schema Fix: Ensure no invalid uri index for UPA checking.
  76.  *
  77.  * Revision 1.1.1.1  2002/02/01 22:22:38  peiyongz
  78.  * sane_include
  79.  *
  80.  * Revision 1.29  2001/12/10 21:42:55  peiyongz
  81.  * Memory Leak: fLeafNameTypeVector
  82.  *
  83.  * Revision 1.28  2001/12/06 17:52:17  tng
  84.  * Performance Enhancement.  The QName that was passed to the CMLeaf
  85.  * constructor was always being copied, even though the CMLeaf objects
  86.  * only existed during construction of a DFA.  In most cases the original
  87.  * QName that was passed into the CMLeaf constructor continued to exist long
  88.  * after the CMLeaf was destroyed; in some cases the QName was constructed
  89.  * specifically to be passed to the CMLeaf constructor.  Added a second CMLeaf constructor that indicated the QName passed in was to be adopted; otherwise the CMLeaf constructor just sets a reference to the QName passed in.
  90.  * By Henry Zongaro.
  91.  *
  92.  * Revision 1.27  2001/11/21 14:30:13  knoaman
  93.  * Fix for UPA checking.
  94.  *
  95.  * Revision 1.26  2001/11/07 21:10:46  tng
  96.  * Performance: move getRawName() to outer loop so that it is called only once per outer loop.
  97.  *
  98.  * Revision 1.25  2001/10/04 15:08:55  knoaman
  99.  * Add support for circular import.
  100.  *
  101.  * Revision 1.24  2001/09/14 14:50:22  tng
  102.  * Schema: Fix some wildcard bugs, and some retrieving qualified/unqualified element decl problems.
  103.  *
  104.  * Revision 1.23  2001/08/24 12:48:48  tng
  105.  * Schema: AllContentModel
  106.  *
  107.  * Revision 1.22  2001/08/22 16:58:55  tng
  108.  * typo: should issue the name of second element.
  109.  *
  110.  * Revision 1.21  2001/08/21 16:50:23  tng
  111.  * Schema: Unique Particle Attribution Constraint Checking.
  112.  *
  113.  * Revision 1.20  2001/08/21 16:06:11  tng
  114.  * Schema: Unique Particle Attribution Constraint Checking.
  115.  *
  116.  * Revision 1.19  2001/08/17 16:12:51  peiyongz
  117.  * Fix to memory leak in buildDFA(),  patch from Nick Chiang (nchiang@ss8.com)
  118.  *
  119.  * Revision 1.18  2001/08/16 21:52:40  peiyongz
  120.  * stateTable created to optimize the identification of new state created.
  121.  *
  122.  * Revision 1.17  2001/07/31 17:45:25  peiyongz
  123.  * Fix: memory leak in postTreeBuildInit()
  124.  *
  125.  * Revision 1.16  2001/07/24 20:00:33  peiyongz
  126.  * Memory Leak fix: Bugzilla #2707 reported by Francois Rioux
  127.  *
  128.  * + |                              DESCRIPTION                                   |
  129.  * + There are some memory leaks in the buildDFA method :
  130.  * +    the first QName allocated object
  131.  * +    the nodeOrgContent
  132.  * +    fHeadNode
  133.  *
  134.  * Revision 1.15  2001/07/09 15:22:36  knoaman
  135.  * complete <any> declaration.
  136.  *
  137.  * Revision 1.14  2001/06/13 20:50:56  peiyongz
  138.  * fIsMixed: to handle mixed Content Model
  139.  *
  140.  * Revision 1.13  2001/06/12 19:07:14  peiyongz
  141.  * Memory leak: fixed by Erik Rydgren
  142.  *
  143.  * Revision 1.12  2001/06/12 17:30:49  knoaman
  144.  * Fix Typo
  145.  *
  146.  * Revision 1.11  2001/06/07 21:08:20  tng
  147.  * Fix unsigned/signed warning from Linux.  By Pei Yong Zhang.
  148.  *
  149.  * Revision 1.10  2001/05/28 20:52:44  tng
  150.  * Schema: move static data gInvalidTrans, gEOCFakeId, gEpsilonFakeId to XMLContentModel for others to access
  151.  *
  152.  * Revision 1.9  2001/05/11 13:27:18  tng
  153.  * Copyright update.
  154.  *
  155.  * Revision 1.8  2001/05/03 21:02:29  tng
  156.  * Schema: Add SubstitutionGroupComparator and update exception messages.  By Pei Yong Zhang.
  157.  *
  158.  * Revision 1.7  2001/04/19 18:17:30  tng
  159.  * Schema: SchemaValidator update, and use QName in Content Model
  160.  *
  161.  * Revision 1.6  2001/03/21 21:56:27  tng
  162.  * Schema: Add Schema Grammar, Schema Validator, and split the DTDValidator into DTDValidator, DTDScanner, and DTDGrammar.
  163.  *
  164.  * Revision 1.5  2001/03/21 19:29:51  tng
  165.  * Schema: Content Model Updates, by Pei Yong Zhang.
  166.  *
  167.  * Revision 1.4  2001/02/27 18:32:31  tng
  168.  * Schema: Use XMLElementDecl instead of DTDElementDecl in Content Model.
  169.  *
  170.  * Revision 1.3  2001/02/27 14:48:51  tng
  171.  * Schema: Add CMAny and ContentLeafNameTypeVector, by Pei Yong Zhang
  172.  *
  173.  * Revision 1.2  2001/02/16 14:58:57  tng
  174.  * Schema: Update Makefile, configure files, project files, and include path in
  175.  * certain cpp files because of the move of the common Content Model files.  By Pei Yong Zhang.
  176.  *
  177.  * Revision 1.1  2001/02/16 14:17:29  tng
  178.  * Schema: Move the common Content Model files that are shared by DTD
  179.  * and schema from 'DTD' folder to 'common' folder.  By Pei Yong Zhang.
  180.  *
  181.  * Revision 1.5  2000/03/28 19:43:25  roddey
  182.  * Fixes for signed/unsigned warnings. New work for two way transcoding
  183.  * stuff.
  184.  *
  185.  * Revision 1.4  2000/03/08 23:52:34  roddey
  186.  * Got rid of the use of -1 to represent an invalid transition state,
  187.  * and just created a const value that is unsigned. This should make
  188.  * some compilers happier.
  189.  *
  190.  * Revision 1.3  2000/03/02 19:55:38  roddey
  191.  * This checkin includes many changes done while waiting for the
  192.  * 1.1.0 code to be finished. I can't list them all here, but a list is
  193.  * available elsewhere.
  194.  *
  195.  * Revision 1.2  2000/02/09 21:42:37  abagchi
  196.  * Copyright swatswat
  197.  *
  198.  * Revision 1.1.1.1  1999/11/09 01:03:17  twl
  199.  * Initial checkin
  200.  *
  201.  * Revision 1.2  1999/11/08 20:45:38  rahul
  202.  * Swat for adding in Product name and CVS comment log variable.
  203.  *
  204.  */
  207. // ---------------------------------------------------------------------------
  208. //  Includes
  209. // ---------------------------------------------------------------------------
  210. #include <xercesc/util/RuntimeException.hpp>
  211. #include <xercesc/framework/XMLBuffer.hpp>
  212. #include <xercesc/framework/XMLElementDecl.hpp>
  213. #include <xercesc/framework/XMLValidator.hpp>
  214. #include <xercesc/validators/common/CMAny.hpp>
  215. #include <xercesc/validators/common/CMBinaryOp.hpp>
  216. #include <xercesc/validators/common/CMLeaf.hpp>
  217. #include <xercesc/validators/common/CMUnaryOp.hpp>
  218. #include <xercesc/validators/common/DFAContentModel.hpp>
  219. #include <xercesc/validators/common/ContentSpecNode.hpp>
  220. #include <xercesc/validators/common/Grammar.hpp>
  221. #include <xercesc/validators/schema/SchemaSymbols.hpp>
  222. #include <xercesc/validators/schema/SubstitutionGroupComparator.hpp>
  223. #include <xercesc/validators/schema/XercesElementWildcard.hpp>
  224. #include <xercesc/util/RefHashTableOf.hpp>
  225. #include <xercesc/util/HashCMStateSet.hpp>
  226. #include <xercesc/util/XMLInteger.hpp>
  228. XERCES_CPP_NAMESPACE_BEGIN
  231. // ---------------------------------------------------------------------------
  232. //  DFAContentModel: Constructors and Destructor
  233. // ---------------------------------------------------------------------------
  234. DFAContentModel::DFAContentModel( const bool             dtd
  235.                                 , ContentSpecNode* const elemContentSpec
  236.                                 , MemoryManager* const   manager) :
  238.     fElemMap(0)
  239.     , fElemMapType(0)
  240.     , fElemMapSize(0)
  241.     , fEmptyOk(false)
  242.     , fEOCPos(0)
  243.     , fFinalStateFlags(0)
  244.     , fFollowList(0)
  245.     , fHeadNode(0)
  246.     , fLeafCount(0)
  247.     , fLeafList(0)
  248.     , fTransTable(0)
  249.     , fTransTableSize(0)
  250.     , fDTD(dtd)
  251.     , fIsMixed(false)
  252.     , fLeafNameTypeVector(0)
  253.     , fMemoryManager(manager)
  254. {
  255.     // And build the DFA data structures
  256.     buildDFA(elemContentSpec);
  257. }
  259. DFAContentModel::DFAContentModel( const bool             dtd
  260.                                 , ContentSpecNode* const elemContentSpec
  261.                                 , const bool             isMixed
  262.                                 , MemoryManager* const   manager):
  264.     fElemMap(0)
  265.     , fElemMapType(0)
  266.     , fElemMapSize(0)
  267.     , fEmptyOk(false)
  268.     , fEOCPos(0)
  269.     , fFinalStateFlags(0)
  270.     , fFollowList(0)
  271.     , fHeadNode(0)
  272.     , fLeafCount(0)
  273.     , fLeafList(0)
  274.     , fTransTable(0)
  275.     , fTransTableSize(0)
  276.     , fDTD(dtd)
  277.     , fIsMixed(isMixed)
  278.     , fLeafNameTypeVector(0)
  279.     , fMemoryManager(manager)
  280. {
  281.     // And build the DFA data structures
  282.     buildDFA(elemContentSpec);
  283. }
  285. DFAContentModel::~DFAContentModel()
  286. {
  287.     //
  288.     //  Clean up all the stuff that is not just temporary representation
  289.     //  data that was cleaned up after building the DFA.
  290.     //
  291.     fMemoryManager->deallocate(fFinalStateFlags); //delete [] fFinalStateFlags;
  293.     unsigned index;
  294.     for (index = 0; index < fTransTableSize; index++)
  295.         fMemoryManager->deallocate(fTransTable[index]); //delete [] fTransTable[index];
  296.     fMemoryManager->deallocate(fTransTable); //delete [] fTransTable;
  298.     for (index = 0; index < fLeafCount; index++)
  299.         delete fElemMap[index];
  300.     fMemoryManager->deallocate(fElemMap); //delete [] fElemMap;
  302.     fMemoryManager->deallocate(fElemMapType); //delete [] fElemMapType;
  303.     fMemoryManager->deallocate(fLeafListType); //delete [] fLeafListType;
  305. delete fLeafNameTypeVector;
  306. }
  309. // ---------------------------------------------------------------------------
  310. //  DFAContentModel: Implementation of the ContentModel virtual interface
  311. // ---------------------------------------------------------------------------
  312. int
  313. DFAContentModel::validateContent( QName** const        children
  314.                                 , const unsigned int   childCount
  315.                                 , const unsigned int   emptyNamespaceId) const
  316. {
  317.     //
  318.     //  If there are no children, then either we fail on the 0th element
  319.     //  or we return success. It depends upon whether this content model
  320.     //  accepts empty content, which we determined earlier.
  321.     //
  322.     if (!childCount)
  323.     {
  324.         // success -1
  325.         return fEmptyOk ? -1 : 0;
  326.     }
  328.     //
  329.     //  Lets loop through the children in the array and move our way
  330.     //  through the states. Note that we use the fElemMap array to map
  331.     //  an element index to a state index.
  332.     //
  333.     unsigned int curState = 0;
  334.     unsigned int nextState = 0;
  335.     unsigned int childIndex = 0;
  336.     for (; childIndex < childCount; childIndex++)
  337.     {
  338.         // Get the current element index out
  339.         const QName* curElem = children[childIndex];
  340.         const XMLCh* curElemRawName = 0;
  341.         if (fDTD)
  342.             curElemRawName = curElem->getRawName();
  344.         // If this is text in a Schema mixed content model, skip it.
  345.         if ( fIsMixed &&
  346.             ( curElem->getURI() == XMLElementDecl::fgPCDataElemId))
  347.             continue;
  349.         // Look up this child in our element map
  350.         unsigned int elemIndex = 0;
  351.         for (; elemIndex < fElemMapSize; elemIndex++)
  352.         {
  353.             const QName* inElem  = fElemMap[elemIndex];
  354.             if (fDTD) {
  355.                 if (XMLString::equals(inElem->getRawName(), curElemRawName)) {
  356.                     nextState = fTransTable[curState][elemIndex];
  357.                     if (nextState != XMLContentModel::gInvalidTrans)
  358.                         break;
  359.                 }
  360.             }
  361.             else {
  362.                 ContentSpecNode::NodeTypes type = fElemMapType[elemIndex];
  363.                 if (type == ContentSpecNode::Leaf)
  364.                 {
  365.                     if ((inElem->getURI() == curElem->getURI()) &&
  366.                     (XMLString::equals(inElem->getLocalPart(), curElem->getLocalPart()))) {
  367.                         nextState = fTransTable[curState][elemIndex];
  368.                         if (nextState != XMLContentModel::gInvalidTrans)
  369.                             break;
  370.                     }
  371.                 }
  372.                 else if ((type & 0x0f)== ContentSpecNode::Any)
  373.                 {
  374.                     nextState = fTransTable[curState][elemIndex];
  375.                     if (nextState != XMLContentModel::gInvalidTrans)
  376.                             break;
  377.                 }
  378.                 else if ((type & 0x0f) == ContentSpecNode::Any_NS)
  379.                 {
  380.                     if (inElem->getURI() == curElem->getURI())
  381.                     {
  382.                         nextState = fTransTable[curState][elemIndex];
  383.                         if (nextState != XMLContentModel::gInvalidTrans)
  384.                             break;
  385.                     }
  386.                 }
  387.                 else if ((type & 0x0f) == ContentSpecNode::Any_Other)
  388.                 {
  389.                     if (inElem->getURI() != curElem->getURI()) {
  390.                         nextState = fTransTable[curState][elemIndex];
  391.                         if (nextState != XMLContentModel::gInvalidTrans)
  392.                             break;
  393.                     }
  394.                 }
  395.             }
  396.         }//for elemIndex
  398.         // If "nextState" is -1, we found a match, but the transition is invalid
  399.         if (nextState == XMLContentModel::gInvalidTrans)
  400.             return childIndex;
  402.         // If we didn't find it, then obviously not valid
  403.         if (elemIndex == fElemMapSize)
  404.             return childIndex;
  406.         curState = nextState;
  407.         nextState = 0;
  409.     }//for childIndex
  411.     //
  412.     //  We transitioned all the way through the input list. However, that
  413.     //  does not mean that we ended in a final state. So check whether
  414.     //  our ending state is a final state.
  415.     //
  416.     if (!fFinalStateFlags[curState])
  417.         return childIndex;
  419.     //success
  420.     return -1;
  421. }
  423. int DFAContentModel::validateContentSpecial(QName** const          children
  424.                                             , const unsigned int      childCount
  425.                                             , const unsigned int      emptyNamespaceId
  426.                                             , GrammarResolver*  const pGrammarResolver
  427.                                             , XMLStringPool*    const pStringPool) const
  428. {
  430.     SubstitutionGroupComparator comparator(pGrammarResolver, pStringPool);
  432.     if (childCount == 0)
  433.         return fEmptyOk ? -1 : 0;
  435.     //
  436.     //  Lets loop through the children in the array and move our way
  437.     //  through the states. Note that we use the fElemMap array to map
  438.     //  an element index to a state index.
  439.     //
  440.     unsigned int curState = 0;
  441.     unsigned int nextState = 0;
  442.     unsigned int childIndex = 0;
  443.     for (; childIndex < childCount; childIndex++)
  444.     {
  445.         // Get the current element index out
  446.         QName* curElem = children[childIndex];
  448.         // If this is text in a Schema mixed content model, skip it.
  449.         if ( fIsMixed &&
  450.             ( curElem->getURI() == XMLElementDecl::fgPCDataElemId))
  451.             continue;
  453.         // Look up this child in our element map
  454.         unsigned int elemIndex = 0;
  455.         for (; elemIndex < fElemMapSize; elemIndex++)
  456.         {
  457.             QName* inElem  = fElemMap[elemIndex];
  458.             ContentSpecNode::NodeTypes type = fElemMapType[elemIndex];
  459.             if (type == ContentSpecNode::Leaf)
  460.             {
  461.                 if (comparator.isEquivalentTo(curElem, inElem) )
  462.                 {
  463.                     nextState = fTransTable[curState][elemIndex];
  464.                     if (nextState != XMLContentModel::gInvalidTrans)
  465.                         break;
  466.                 }
  468.             }
  469.             else if ((type & 0x0f)== ContentSpecNode::Any)
  470.             {
  471.                 nextState = fTransTable[curState][elemIndex];
  472.                 if (nextState != XMLContentModel::gInvalidTrans)
  473.                         break;
  474.             }
  475.             else if ((type & 0x0f) == ContentSpecNode::Any_NS)
  476.             {
  477.                 if (inElem->getURI() == curElem->getURI())
  478.                 {
  479.                     nextState = fTransTable[curState][elemIndex];
  480.                     if (nextState != XMLContentModel::gInvalidTrans)
  481.                         break;
  482.                 }
  483.             }
  484.             else if ((type & 0x0f) == ContentSpecNode::Any_Other)
  485.             {
  486.                 if (inElem->getURI() != curElem->getURI())
  487.                 {
  488.                     nextState = fTransTable[curState][elemIndex];
  489.                     if (nextState != XMLContentModel::gInvalidTrans)
  490.                         break;
  491.                 }
  492.             }
  493.         }//for elemIndex
  495.         // If "nextState" is -1, we found a match, but the transition is invalid
  496.         if (nextState == XMLContentModel::gInvalidTrans)
  497.             return childIndex;
  499.         // If we didn't find it, then obviously not valid
  500.         if (elemIndex == fElemMapSize)
  501.             return childIndex;
  503.         curState = nextState;
  504.         nextState = 0;
  506.     }//for childIndex
  508.     //
  509.     //  We transitioned all the way through the input list. However, that
  510.     //  does not mean that we ended in a final state. So check whether
  511.     //  our ending state is a final state.
  512.     //
  513.     if (!fFinalStateFlags[curState])
  514.         return childIndex;
  516.     //success
  517.     return -1;
  518. }
  521. // ---------------------------------------------------------------------------
  522. //  DFAContentModel: Private helper methods
  523. // ---------------------------------------------------------------------------
  524. void DFAContentModel::buildDFA(ContentSpecNode* const curNode)
  525. {
  526.     unsigned int index;
  529.     //
  530.     //  The first step we need to take is to rewrite the content model using
  531.     //  our CMNode objects, and in the process get rid of any repetition short
  532.     //  cuts, converting them into '*' style repetitions or getting rid of
  533.     //  repetitions altogether.
  534.     //
  535.     //  The conversions done are:
  536.     //
  537.     //  x+ -> (x|x*)
  538.     //  x? -> (x|epsilon)
  539.     //
  540.     //  This is a relatively complex scenario. What is happening is that we
  541.     //  create a top level binary node of which the special EOC value is set
  542.     //  as the right side node. The the left side is set to the rewritten
  543.     //  syntax tree. The source is the original content model info from the
  544.     //  decl pool. The rewrite is done by buildSyntaxTree() which recurses the
  545.     //  decl pool's content of the element and builds a new tree in the
  546.     //  process.
  547.     //
  548.     //  Note that, during this operation, we set each non-epsilon leaf node's
  549.     //  DFA state position and count the number of such leafs, which is left
  550.     //  in the fLeafCount member.
  551.     //
  552.     CMLeaf* nodeEOC = new (fMemoryManager) CMLeaf
  553.     (
  554.         new (fMemoryManager) QName
  555.         (
  556.             XMLUni::fgZeroLenString
  557.             , XMLUni::fgZeroLenString
  558.             , XMLContentModel::gEOCFakeId
  559.             , fMemoryManager
  560.         )
  561.         , ~0
  562.         , true
  563.         , fMemoryManager
  564.     );
  565.     CMNode* nodeOrgContent = buildSyntaxTree(curNode);
  566.     fHeadNode = new (fMemoryManager) CMBinaryOp
  567.     (
  568.         ContentSpecNode::Sequence
  569.         , nodeOrgContent
  570.         , nodeEOC
  571.         , fMemoryManager
  572.     );
  574.     //
  575.     //  And handle specially the EOC node, which also must be numbered and
  576.     //  counted as a non-epsilon leaf node. It could not be handled in the
  577.     //  above tree build because it was created before all that started. We
  578.     //  save the EOC position since its used during the DFA building loop.
  579.     //
  580.     fEOCPos = fLeafCount;
  581.     nodeEOC->setPosition(fLeafCount++);
  583.     //
  584.     //  Ok, so now we have to iterate the new tree and do a little more work
  585.     //  now that we know the leaf count. One thing we need to do is to
  586.     //  calculate the first and last position sets of each node. This is
  587.     //  cached away in each of the nodes.
  588.     //
  589.     //  Along the way we also set the leaf count in each node as the maximum
  590.     //  state count. They must know this in order to create their first/last
  591.     //  position sets.
  592.     //
  593.     //  We also need to build an array of references to the non-epsilon
  594.     //  leaf nodes. Since we iterate here the same way as we did during the
  595.     //  initial tree build (which built their position numbers, we will put
  596.     //  them in the array according to their position values.
  597.     //
  598.     fLeafList = (CMLeaf**) fMemoryManager->allocate(fLeafCount*sizeof(CMLeaf*)); //new CMLeaf*[fLeafCount];
  599.     fLeafListType = (ContentSpecNode::NodeTypes*) fMemoryManager->allocate
  600.     (
  601.         fLeafCount * sizeof(ContentSpecNode::NodeTypes)
  602.     ); //new ContentSpecNode::NodeTypes[fLeafCount];
  603.     postTreeBuildInit(fHeadNode, 0);
  605.     //
  606.     //  And, moving onward... We now need to build the follow position sets
  607.     //  for all the nodes. So we allocate an array of pointers to state sets,
  608.     //  one for each leaf node (i.e. each significant DFA position.)
  609.     //
  610.     fFollowList = (CMStateSet**) fMemoryManager->allocate
  611.     (
  612.         fLeafCount * sizeof(CMStateSet*)
  613.     ); //new CMStateSet*[fLeafCount];
  614.     for (index = 0; index < fLeafCount; index++)
  615.         fFollowList[index] = new (fMemoryManager) CMStateSet(fLeafCount, fMemoryManager);
  616.     calcFollowList(fHeadNode);
  618.     //
  619.     //  Check to see whether this content model can handle an empty content,
  620.     //  which is something we need to optimize by looking now before we
  621.     //  throw away the info that would tell us that.
  622.     //
  623.     //  If the left node of the head (the top level of the original content)
  624.     //  is nullable, then its true.
  625.     //
  626.     fEmptyOk = nodeOrgContent->isNullable();
  628.     //
  629.     //  And finally the big push... Now we build the DFA using all the states
  630.     //  and the tree we've built up. First we set up the various data
  631.     //  structures we are going to use while we do this.
  632.     //
  633.     //  First of all we need an array of unique element ids in our content
  634.     //  model. For each transition table entry, we need a set of contiguous
  635.     //  indices to represent the transitions for a particular input element.
  636.     //  So we need to a zero based range of indexes that map to element types.
  637.     //  This element map provides that mapping.
  638.     //
  639.     fElemMap = (QName**) fMemoryManager->allocate
  640.     (
  641.         fLeafCount * sizeof(QName*)
  642.     ); //new QName*[fLeafCount];
  643.     fElemMapType = (ContentSpecNode::NodeTypes*) fMemoryManager->allocate
  644.     (
  645.         fLeafCount * sizeof(ContentSpecNode::NodeTypes)
  646.     ); //new ContentSpecNode::NodeTypes[fLeafCount];
  647.     fElemMapSize = 0;
  650.     for (unsigned int outIndex = 0; outIndex < fLeafCount; outIndex++)
  651.     {
  652.         fElemMap[outIndex] = new (fMemoryManager) QName(fMemoryManager);
  654.         if ( (fLeafListType[outIndex] & 0x0f) != ContentSpecNode::Leaf )
  655.             if (!fLeafNameTypeVector)
  656.                 fLeafNameTypeVector = new (fMemoryManager) ContentLeafNameTypeVector(fMemoryManager);
  658.         // Get the current leaf's element index
  659.         const QName* element = fLeafList[outIndex]->getElement();
  660.         const XMLCh* elementRawName = 0;
  661.         if (fDTD && element)
  662.             elementRawName = element->getRawName();
  664.         // See if the current leaf node's element index is in the list
  665.         unsigned int inIndex = 0;
  667.         for (; inIndex < fElemMapSize; inIndex++)
  668.         {
  669.             const QName* inElem = fElemMap[inIndex];
  670.             if (fDTD) {
  671.                 if (XMLString::equals(inElem->getRawName(), elementRawName)) {
  672.                     break;
  673.                 }
  674.             }
  675.             else {
  676.                 if ((fElemMapType[inIndex] == fLeafListType[outIndex]) &&
  677.                     (inElem->getURI() == element->getURI()) &&
  678.                     (XMLString::equals(inElem->getLocalPart(), element->getLocalPart()))) {
  679.                     break;
  680.                 }
  681.             }
  682.         }
  684.         // If it was not in the list, then add it and bump the map size
  685.         if (inIndex == fElemMapSize)
  686.         {
  687.             fElemMap[fElemMapSize]->setValues(*element);
  688.             fElemMapType[fElemMapSize] = fLeafListType[outIndex];
  689.             ++fElemMapSize;
  690.         }
  691.     }
  693.     // set up the fLeafNameTypeVector object if there is one.
  694.     if (fLeafNameTypeVector) {
  695.         fLeafNameTypeVector->setValues(fElemMap, fElemMapType, fElemMapSize);
  696.     }
  698.     /***
  699.      * Optimization(Jan, 2001); We sort fLeafList according to
  700.      * elemIndex which is *uniquely* associated to each leaf.
  701.      * We are *assuming* that each element appears in at least one leaf.
  702.      **/
  703.     // don't forget to delete it
  705.     int *fLeafSorter = (int*) fMemoryManager->allocate
  706.     (
  707.         (fLeafCount + fElemMapSize) * sizeof(int)
  708.     ); //new int[fLeafCount + fElemMapSize];
  709.     unsigned int fSortCount = 0;
  711.     for (unsigned int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++)
  712.     {
  713.         const QName* element = fElemMap[elemIndex];
  714.         const XMLCh* elementRawName = 0;
  715.         if (fDTD && element)
  716.             elementRawName = element->getRawName();
  718.         for (unsigned int leafIndex = 0; leafIndex < fLeafCount; leafIndex++)
  719.         {
  720.             const QName* leaf = fLeafList[leafIndex]->getElement();
  721.             const int leafType = fLeafListType[leafIndex];
  722.             if (fDTD) {
  723.                 if (XMLString::equals(leaf->getRawName(), elementRawName)) {
  724.                     fLeafSorter[fSortCount++] = leafIndex;
  725.                 }
  726.             }
  727.             else {
  728.                 if ((fElemMapType[elemIndex] == fLeafListType[leafIndex]) &&
  729.                     (leaf->getURI() == element->getURI()) &&
  730.                     (XMLString::equals(leaf->getLocalPart(), element->getLocalPart()))) {
  731.                       fLeafSorter[fSortCount++] = leafIndex;
  732.                 }
  733.             }
  734.         }
  735.         fLeafSorter[fSortCount++] = -1;
  736.     }
  738.     //
  739.     //  Next lets create some arrays, some that that hold transient info
  740.     //  during the DFA build and some that are permament. These are kind of
  741.     //  sticky since we cannot know how big they will get, but we don't want
  742.     //  to use any collection type classes because of performance.
  743.     //
  744.     //  Basically they will probably be about fLeafCount*2 on average, but can
  745.     //  be as large as 2^(fLeafCount*2), worst case. So we start with
  746.     //  fLeafCount*4 as a middle ground. This will be very unlikely to ever
  747.     //  have to expand though, it if does, the overhead will be somewhat ugly.
  748.     //
  749.     unsigned int curArraySize = fLeafCount * 4;
  750.     const CMStateSet** statesToDo = (const CMStateSet**) 
  751.         fMemoryManager->allocate
  752.         (
  753.             curArraySize * sizeof(const CMStateSet*)
  754.         ); //new const CMStateSet*[curArraySize];
  755.     fFinalStateFlags = (bool*) fMemoryManager->allocate
  756.     (
  757.         curArraySize * sizeof(bool)
  758.     ); //new bool[curArraySize];
  759.     fTransTable = (unsigned int**) fMemoryManager->allocate
  760.     (
  761.         curArraySize * sizeof(unsigned int*)
  762.     ); //new unsigned int*[curArraySize];
  764.     //
  765.     //  Ok we start with the initial set as the first pos set of the head node
  766.     //  (which is the seq node that holds the content model and the EOC node.)
  767.     //
  768.     const CMStateSet* setT = new (fMemoryManager) CMStateSet(fHeadNode->getFirstPos());
  770.     //
  771.     //  Init our two state flags. Basically the unmarked state counter is
  772.     //  always chasing the current state counter. When it catches up, that
  773.     //  means we made a pass through that did not add any new states to the
  774.     //  lists, at which time we are done. We could have used a expanding array
  775.     //  of flags which we used to mark off states as we complete them, but
  776.     //  this is easier though less readable maybe.
  777.     //
  778.     unsigned int unmarkedState = 0;
  779.     unsigned int curState = 0;
  781.     //
  782.     //  Init the first transition table entry, and put the initial state
  783.     //  into the states to do list, then bump the current state.
  784.     //
  785.     fTransTable[curState] = makeDefStateList();
  786.     statesToDo[curState] = setT;
  787.     curState++;
  789.     //
  790.     // the stateTable is an auxiliary means to fast
  791.     // identification of new state created (instead
  792.     // of squential loop statesToDo to find out),
  793.     // while the role that statesToDo plays remain unchanged.
  794.     //
  795.     // TODO: in the future, we may change the 29 to something
  796.     //       derived from curArraySize.
  797.     RefHashTableOf<XMLInteger> *stateTable =
  798.         new (fMemoryManager) RefHashTableOf<XMLInteger>
  799.         (
  800.             curArraySize
  801.             , true
  802.             , new (fMemoryManager) HashCMStateSet()
  803.             , fMemoryManager
  804.         );
  805.     //stateTable->put((CMStateSet*)setT, new (fMemoryManager) XMLInteger(0));
  807.     //
  808.     //  Ok, almost done with the algorithm from hell... We now enter the
  809.     //  loop where we go until the states done counter catches up with
  810.     //  the states to do counter.
  811.     //
  812.     CMStateSet* newSet = 0;
  813.     while (unmarkedState < curState)
  814.     {
  815.         //
  816.         //  Get the next unmarked state out of the list of states to do.
  817.         //  And get the associated transition table entry.
  818.         //
  819.         setT = statesToDo[unmarkedState];
  820.         unsigned int* transEntry = fTransTable[unmarkedState];
  822.         // Mark this one final if it contains the EOC state
  823.         fFinalStateFlags[unmarkedState] = setT->getBit(fEOCPos);
  825.         // Bump up the unmarked state count, marking this state done
  826.         unmarkedState++;
  828.         // Optimization(Jan, 2001)
  829.         unsigned int sorterIndex = 0;
  830.         // Optimization(Jan, 2001)
  832.         // Loop through each possible input symbol in the element map
  833.         for (unsigned int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++)
  834.         {
  835.             //
  836.             //  Build up a set of states which is the union of all of the
  837.             //  follow sets of DFA positions that are in the current state. If
  838.             //  we gave away the new set last time through then create a new
  839.             //  one. Otherwise, zero out the existing one.
  840.             //
  841.             if (!newSet)
  842.                 newSet = new (fMemoryManager) CMStateSet
  843.                 (
  844.                     fLeafCount
  845.                     , fMemoryManager
  846.                 );
  847.             else
  848.                 newSet->zeroBits();
  850. #ifdef OBSOLETED
  851. // unoptimized code
  852.             for (unsigned int leafIndex = 0; leafIndex < fLeafCount; leafIndex++)
  853.             {
  854.                 // If this leaf index (DFA position) is in the current set...
  855.                 if (setT->getBit(leafIndex))
  856.                 {
  857.                     //
  858.                     //  If this leaf is the current input symbol, then we want
  859.                     //  to add its follow list to the set of states to transition
  860.                     //  to from the current state.
  861.                     //
  862.                     const QName* leaf = fLeafList[leafIndex]->getElement();
  863.                     const QName* element = fElemMap[elemIndex];
  864.                     if (fDTD) {
  865.                         if (XMLString::equals(leaf->getRawName(), element->getRawName())) {
  866.                             *newSet |= *fFollowList[leafIndex];
  867.                         }
  868.                     }
  869.                     else {
  870.                         if ((leaf->getURI() == element->getURI()) &&
  871.                             (XMLString::equals(leaf->getLocalPart(), element->getLocalPart()))) {
  872.                             *newSet |= *fFollowList[leafIndex];
  873.                         }
  874.                     }
  875.                 }
  876.             } // for leafIndex
  877. #endif
  879.             // Optimization(Jan, 2001)
  880.             int leafIndex = fLeafSorter[sorterIndex++];
  882.             while (leafIndex != -1)
  883.             {
  884.                 // If this leaf index (DFA position) is in the current set...
  885.                 if (setT->getBit(leafIndex))
  886.                 {
  887.                     //
  888.                     //  If this leaf is the current input symbol, then we
  889.                     //  want to add its follow list to the set of states to
  890.                     //  transition to from the current state.
  891.                     //
  892.                     *newSet |= *fFollowList[leafIndex];
  893.                 }
  894.                 leafIndex = fLeafSorter[sorterIndex++];
  895.             } // while (leafIndex != -1)
  897.             //
  898.             //  If this new set is not empty, then see if its in the list
  899.             //  of states to do. If not, then add it.
  900.             //
  901.             if (!newSet->isEmpty())
  902.             {
  903.                 //
  904.                 //  Search the 'states to do' list to see if this new
  905.                 //  state set is already in there.
  906.                 //
  907.                 /***
  908.                 unsigned int stateIndex = 0;
  909.                 for (; stateIndex < curState; stateIndex++)
  910.                 {
  911.                     if (*statesToDo[stateIndex] == *newSet)
  912.                         break;
  913.                 }
  914.                 ***/
  916.                 XMLInteger *stateObj = (XMLInteger*) (stateTable->get(newSet));
  917.                 unsigned int stateIndex = (stateObj == 0 ? curState : stateObj->intValue());
  919.                 // If we did not find it, then add it
  920.                 if (stateIndex == curState)
  921.                 {
  922.                     //
  923.                     //  Put this new state into the states to do and init
  924.                     //  a new entry at the same index in the transition
  925.                     //  table.
  926.                     //
  927.                     statesToDo[curState] = newSet;
  928.                     fTransTable[curState] = makeDefStateList();
  929.                     stateTable->put
  930.                     (
  931.                         newSet
  932.                         , new (fMemoryManager) XMLInteger(curState)
  933.                     );
  935.                     // We now have a new state to do so bump the count
  936.                     curState++;
  938.                     //
  939.                     //  Null out the new set to indicate we adopted it. This
  940.                     //  will cause the creation of a new set on the next time
  941.                     //  around the loop.
  942.                     //
  943.                     newSet = 0;
  944.                 }
  946.                 //
  947.                 //  Now set this state in the transition table's entry for this
  948.                 //  element (using its index), with the DFA state we will move
  949.                 //  to from the current state when we see this input element.
  950.                 //
  951.                 transEntry[elemIndex] = stateIndex;
  953.                 // Expand the arrays if we're full
  954.                 if (curState == curArraySize)
  955.                 {
  956.                     //
  957.                     //  Yikes, we overflowed the initial array size, so we've
  958.                     //  got to expand all of these arrays. So adjust up the
  959.                     //  size by 50% and allocate new arrays.
  960.                     //
  961.                     const unsigned int newSize = (unsigned int)(curArraySize * 1.5);
  962.                     const CMStateSet** newToDo = (const CMStateSet**) 
  963.                         fMemoryManager->allocate
  964.                         (
  965.                             newSize * sizeof(const CMStateSet*)
  966.                         ); //new const CMStateSet*[newSize];
  967.                     bool* newFinalFlags = (bool*) fMemoryManager->allocate
  968.                     (
  969.                         newSize * sizeof(bool)
  970.                     ); //new bool[newSize];
  971.                     unsigned int** newTransTable = (unsigned int**)
  972.                         fMemoryManager->allocate
  973.                         (
  974.                             newSize * sizeof(unsigned int*)
  975.                         ); //new unsigned int*[newSize];
  977.                     // Copy over all of the existing content
  978.                     for (unsigned int expIndex = 0; expIndex < curArraySize; expIndex++)
  979.                     {
  980.                         newToDo[expIndex] = statesToDo[expIndex];
  981.                         newFinalFlags[expIndex] = fFinalStateFlags[expIndex];
  982.                         newTransTable[expIndex] = fTransTable[expIndex];
  983.                     }
  985.                     // Clean up the old stuff
  986.                     fMemoryManager->deallocate(statesToDo); //delete [] statesToDo;
  987.                     fMemoryManager->deallocate(fFinalStateFlags); //delete [] fFinalStateFlags;
  988.                     fMemoryManager->deallocate(fTransTable); //delete [] fTransTable;
  990.                     // Store the new array size and pointers
  991.                     curArraySize = newSize;
  992.                     statesToDo = newToDo;
  993.                     fFinalStateFlags = newFinalFlags;
  994.                     fTransTable = newTransTable;
  995.                 } //if (curState == curArraySize)
  996.             } //if (!newSet->isEmpty())
  997.         } // for elemIndex
  998.     } //while
  1000.     // Store the current state count in the trans table size
  1001.     fTransTableSize = curState;
  1003.     // If the last temp set was not stored, then clean it up
  1004.     if (newSet)
  1005.         delete newSet;
  1007.     //
  1008.     //  Now we can clean up all of the temporary data that was needed during
  1009.     //  DFA build.
  1010.     //
  1012.     //
  1013.     // Note on memory leak: Bugzilla#2707:
  1014.     // ===================================
  1015.     // The CMBinary, pointed to by fHeadNode, shall be released by
  1016.     // deleted by itself.
  1017.     //
  1018.     // Change has been made to postTreeBuildInit() such that fLeafList[]
  1019.     // would maintain its **OWN** copy of CMLeaf to avoid double deletion
  1020.     // of CMLeaf.
  1021.     //
  1023.     delete fHeadNode;
  1025.     for (index = 0; index < fLeafCount; index++)
  1026.         delete fFollowList[index];
  1027.     fMemoryManager->deallocate(fFollowList); //delete [] fFollowList;
  1029.     //
  1030.     // removeAll() will delete all data, XMLInteger,
  1031.     // while the keys are to be deleted by the
  1032.     // deletion of statesToDo.
  1033.     //
  1034.     delete stateTable;
  1036.     for (index = 0; index < curState; index++)
  1037.         delete (CMStateSet*)statesToDo[index];
  1038.     fMemoryManager->deallocate(statesToDo); //delete [] statesToDo;
  1040.     for (index = 0; index < fLeafCount; index++)
  1041.         delete fLeafList[index];
  1042.     fMemoryManager->deallocate(fLeafList); //delete [] fLeafList;
  1044.     fMemoryManager->deallocate(fLeafSorter); //delete [] fLeafSorter;
  1046. }
  1049. CMNode* DFAContentModel::buildSyntaxTree(ContentSpecNode* const curNode)
  1050. {
  1051.     // Initialize a return node pointer
  1052.     CMNode* retNode = 0;
  1054.     // Get the spec type of the passed node
  1055.     const ContentSpecNode::NodeTypes curType = curNode->getType();
  1057.     if ((curType & 0x0f) == ContentSpecNode::Any
  1058.         || (curType & 0x0f) == ContentSpecNode::Any_Other
  1059.         || (curType & 0x0f) == ContentSpecNode::Any_NS)
  1060.     {
  1061.         retNode = new (fMemoryManager) CMAny
  1062.         (
  1063.             curType
  1064.             , curNode->getElement()->getURI()
  1065.             , fLeafCount++
  1066.             , fMemoryManager
  1067.         );
  1068.     }
  1069.     else if (curType == ContentSpecNode::Leaf)
  1070.     {
  1071.         //
  1072.         //  Create a new leaf node, and pass it the current leaf count, which
  1073.         //  is its DFA state position. Bump the leaf count after storing it.
  1074.         //  This makes the positions zero based since we store first and then
  1075.         //  increment.
  1076.         //
  1077.         retNode = new (fMemoryManager) CMLeaf
  1078.         (
  1079.             curNode->getElement()
  1080.             , fLeafCount++
  1081.             , fMemoryManager
  1082.         );
  1083.     }
  1084.      else
  1085.     {
  1086.         //
  1087.         //  Its not a leaf, so we have to recurse its left and maybe right
  1088.         //  nodes. Save both values before we recurse and trash the node.
  1089.         //
  1090.         ContentSpecNode* leftNode = curNode->getFirst();
  1091.         ContentSpecNode* rightNode = curNode->getSecond();
  1093.         if ((curType == ContentSpecNode::Choice)
  1094.         ||   (curType == ContentSpecNode::Sequence))
  1095.         {
  1096.             //
  1097.             //  Recurse on both children, and return a binary op node with the
  1098.             //  two created sub nodes as its children. The node type is the
  1099.             //  same type as the source.
  1100.             //
  1101.             CMNode* newLeft = buildSyntaxTree(leftNode);
  1102.             CMNode* newRight = buildSyntaxTree(rightNode);
  1103.             retNode = new (fMemoryManager) CMBinaryOp
  1104.             (
  1105.                 curType
  1106.                 , newLeft
  1107.                 , newRight
  1108.                 , fMemoryManager
  1109.             );
  1110.         }
  1111.          else if (curType == ContentSpecNode::ZeroOrMore
  1112.                || curType == ContentSpecNode::ZeroOrOne
  1113.                || curType == ContentSpecNode::OneOrMore)
  1114.         {
  1115.             // This one is fine as is, just change to our form
  1116.             retNode = new (fMemoryManager) CMUnaryOp
  1117.             (
  1118.                 curType
  1119.                 , buildSyntaxTree(leftNode)
  1120.                 , fMemoryManager
  1121.             );
  1122.         }
  1123.          else
  1124.         {
  1125.             ThrowXML(RuntimeException, XMLExcepts::CM_UnknownCMSpecType);
  1126.         }
  1127.     }
  1128.     return retNode;
  1129. }
  1132. void DFAContentModel::calcFollowList(CMNode* const curNode)
  1133. {
  1134.     // Get the spec type of the passed node
  1135.     const ContentSpecNode::NodeTypes curType = curNode->getType();
  1137.     if (curType == ContentSpecNode::Choice)
  1138.     {
  1139.         // Just recurse
  1140.         calcFollowList(((CMBinaryOp*)curNode)->getLeft());
  1141.         calcFollowList(((CMBinaryOp*)curNode)->getRight());
  1142.     }
  1143.      else if (curType == ContentSpecNode::Sequence)
  1144.     {
  1145.         // Recurse before we process this node
  1146.         calcFollowList(((CMBinaryOp*)curNode)->getLeft());
  1147.         calcFollowList(((CMBinaryOp*)curNode)->getRight());
  1149.         //
  1150.         //  Now handle our level. We use our left child's last pos set and our
  1151.         //  right child's first pos set, so get them now for convenience.
  1152.         //
  1153.         const CMStateSet& last  = ((CMBinaryOp*)curNode)->getLeft()->getLastPos();
  1154.         const CMStateSet& first = ((CMBinaryOp*)curNode)->getRight()->getFirstPos();
  1156.         //
  1157.         //  Now, for every position which is in our left child's last set
  1158.         //  add all of the states in our right child's first set to the
  1159.         //  follow set for that position.
  1160.         //
  1161.         for (unsigned int index = 0; index < fLeafCount; index++)
  1162.         {
  1163.             if (last.getBit(index))
  1164.                 *fFollowList[index] |= first;
  1165.         }
  1166.     }
  1167.      else if (curType == ContentSpecNode::ZeroOrMore ||
  1168.       curType == ContentSpecNode::OneOrMore   )
  1169.     {
  1170.         // Recurse first
  1171.         calcFollowList(((CMUnaryOp*)curNode)->getChild());
  1173.         //
  1174.         //  Now handle our level. We use our own first and last position
  1175.         //  sets, so get them up front.
  1176.         //
  1177.         const CMStateSet& first = curNode->getFirstPos();
  1178.         const CMStateSet& last  = curNode->getLastPos();
  1180.         //
  1181.         //  For every position which is in our last position set, add all
  1182.         //  of our first position states to the follow set for that
  1183.         //  position.
  1184.         //
  1185.         for (unsigned int index = 0; index < fLeafCount; index++)
  1186.         {
  1187.             if (last.getBit(index))
  1188.                 *fFollowList[index] |= first;
  1189.         }
  1190.     }
  1191.      else if (curType == ContentSpecNode::ZeroOrOne)
  1192.     {
  1193.         // Recurse only
  1194.         calcFollowList(((CMUnaryOp*)curNode)->getChild());
  1195.     }
  1196. }
  1199. //
  1200. //  gInvalidTrans is used to represent bad transitions in the transition table
  1201. //  entry for each state. So each entry is initialized to that value. This
  1202. //  method creates a new entry and initializes it.
  1203. //
  1204. unsigned int* DFAContentModel::makeDefStateList() const
  1205. {
  1206.     unsigned int* retArray = (unsigned int*) fMemoryManager->allocate
  1207.     (
  1208.         fElemMapSize * sizeof(unsigned int)
  1209.     ); //new unsigned int[fElemMapSize];
  1210.     for (unsigned int index = 0; index < fElemMapSize; index++)
  1211.         retArray[index] = XMLContentModel::gInvalidTrans;
  1212.     return retArray;
  1213. }
  1216. int DFAContentModel::postTreeBuildInit(         CMNode* const   nodeCur
  1217.                                         , const unsigned int    curIndex)
  1218. {
  1219.     // Set the maximum states on this node
  1220.     nodeCur->setMaxStates(fLeafCount);
  1222.     // Get the spec type of the passed node
  1223.     const ContentSpecNode::NodeTypes curType = nodeCur->getType();
  1225.     // Get a copy of the index we can modify
  1226.     unsigned int newIndex = curIndex;
  1228.     // Recurse as required
  1229.     if ( ((curType & 0x0f) == ContentSpecNode::Any)       ||
  1230.          ((curType & 0x0f) == ContentSpecNode::Any_NS) ||
  1231.          ((curType & 0x0f) == ContentSpecNode::Any_Other)  )
  1232.     {
  1233.         fLeafList[newIndex] = new (fMemoryManager) CMLeaf
  1234.         (
  1235.             new (fMemoryManager) QName
  1236.             (
  1237.                 XMLUni::fgZeroLenString
  1238.                 , XMLUni::fgZeroLenString
  1239.                 , ((CMAny*) nodeCur)->getURI()
  1240.                 , fMemoryManager
  1241.             )
  1242.             , ((CMAny*)nodeCur)->getPosition()
  1243.             , true
  1244.             , fMemoryManager
  1245.         );
  1246.         fLeafListType[newIndex] = curType;
  1247.         ++newIndex;
  1248.     }
  1249.     else if ((curType == ContentSpecNode::Choice)
  1250.          ||  (curType == ContentSpecNode::Sequence))
  1251.     {
  1252.         newIndex = postTreeBuildInit(((CMBinaryOp*)nodeCur)->getLeft(), newIndex);
  1253.         newIndex = postTreeBuildInit(((CMBinaryOp*)nodeCur)->getRight(), newIndex);
  1254.     }
  1255.     else if (curType == ContentSpecNode::ZeroOrMore ||
  1256.              curType == ContentSpecNode::ZeroOrOne  ||
  1257.              curType == ContentSpecNode::OneOrMore)
  1258.     {
  1259.         newIndex = postTreeBuildInit(((CMUnaryOp*)nodeCur)->getChild(), newIndex);
  1260.     }
  1261.     else if (curType == ContentSpecNode::Leaf)
  1262.     {
  1263.         //
  1264.         //  Put this node in the leaf list at the current index if its
  1265.         //  a non-epsilon leaf.
  1266.         //
  1267.         if (((CMLeaf*)nodeCur)->getElement()->getURI() != XMLContentModel::gEpsilonFakeId)
  1268.         {
  1269.             //
  1270.             // fLeafList make its own copy of the CMLeaf, so that
  1271.             // delete[] fLeafList and delete the owner of the nodeCur
  1272.             // will NOT delete the nodeCur --twice--,
  1273.             // thuse to make delete the owner of the nodeCur possible.
  1274.             //
  1275.             fLeafList[newIndex] = new (fMemoryManager) CMLeaf
  1276.             (
  1277.                 ((CMLeaf*)nodeCur)->getElement()
  1278.                 , ((CMLeaf*)nodeCur)->getPosition()
  1279.                 , fMemoryManager
  1280.             );
  1281.             fLeafListType[newIndex] = ContentSpecNode::Leaf;
  1282.             ++newIndex;
  1283.         }
  1284.     }
  1285.     else
  1286.     {
  1287.         ThrowXML(RuntimeException, XMLExcepts::CM_UnknownCMSpecType);
  1288.     }
  1289.     return newIndex;
  1290. }
  1294. ContentLeafNameTypeVector* DFAContentModel::getContentLeafNameTypeVector() const
  1295. {
  1296.    //later change it to return the data member
  1297. return fLeafNameTypeVector;
  1298. };
  1300. void DFAContentModel::checkUniqueParticleAttribution (SchemaGrammar*    const pGrammar,
  1301.                                                       GrammarResolver*  const pGrammarResolver,
  1302.                                                       XMLStringPool*    const pStringPool,
  1303.                                                       XMLValidator*     const pValidator,
  1304.                                                       unsigned int*     const pContentSpecOrgURI)
  1305. {
  1307.     SubstitutionGroupComparator comparator(pGrammarResolver, pStringPool);
  1309.     unsigned int i, j, k;
  1311.     // Rename the URI back
  1312.     for (i = 0; i < fElemMapSize; i++) {
  1314.         unsigned int orgURIIndex = fElemMap[i]->getURI();
  1316.         if ((orgURIIndex != XMLContentModel::gEOCFakeId) &&
  1317.             (orgURIIndex != XMLContentModel::gEpsilonFakeId) &&
  1318.             (orgURIIndex != XMLElementDecl::fgInvalidElemId) &&
  1319.             (orgURIIndex != XMLElementDecl::fgPCDataElemId)) {
  1320.             fElemMap[i]->setURI(pContentSpecOrgURI[orgURIIndex]);
  1321.         }
  1322.     }
  1324.     // Unique Particle Attribution
  1325.     // store the conflict results between any two elements in fElemMap
  1326.     // XMLContentModel::gInvalidTrans: not compared; 0: no conflict; 1: conflict
  1327.     unsigned int** fConflictTable = (unsigned int**) fMemoryManager->allocate
  1328.     (
  1329.         fElemMapSize * sizeof(unsigned int*)
  1330.     ); //new unsigned int*[fElemMapSize];
  1332.     // initialize the conflict table
  1333.     for (j = 0; j < fElemMapSize; j++) {
  1334.         fConflictTable[j] = (unsigned int*) fMemoryManager->allocate
  1335.         (
  1336.             fElemMapSize * sizeof(unsigned int)
  1337.         ); //new unsigned int[fElemMapSize];
  1338.         for (k = j+1; k < fElemMapSize; k++)
  1339.             fConflictTable[j][k] = XMLContentModel::gInvalidTrans;
  1340.     }
  1342.     // for each state, check whether it has overlap transitions
  1343.     for (i = 0; i < fTransTableSize; i++) {
  1344.         for (j = 0; j < fElemMapSize; j++) {
  1345.             for (k = j+1; k < fElemMapSize; k++) {
  1346.                 if (fTransTable[i][j] != XMLContentModel::gInvalidTrans &&
  1347.                     fTransTable[i][k] != XMLContentModel::gInvalidTrans &&
  1348.                     fConflictTable[j][k] == XMLContentModel::gInvalidTrans) {
  1350.                     // If this is text in a Schema mixed content model, skip it.
  1351.                     if ( fIsMixed &&
  1352.                          (( fElemMap[j]->getURI() == XMLElementDecl::fgPCDataElemId) ||
  1353.                           ( fElemMap[k]->getURI() == XMLElementDecl::fgPCDataElemId)))
  1354.                         continue;
  1356.                     if (XercesElementWildcard::conflict(pGrammar,
  1357.                                                         fElemMapType[j],
  1358.                                                         fElemMap[j],
  1359.                                                         fElemMapType[k],
  1360.                                                         fElemMap[k],
  1361.                                                         &comparator)) {
  1362.                        fConflictTable[j][k] = 1;
  1364.                        XMLBuffer buf1(1023, fMemoryManager);
  1365.                        if (((fElemMapType[j] & 0x0f) == ContentSpecNode::Any) ||
  1366.                            ((fElemMapType[j] & 0x0f) == ContentSpecNode::Any_NS))
  1367.                            buf1.set(SchemaSymbols::fgATTVAL_TWOPOUNDANY);
  1368.                        else if ((fElemMapType[j] & 0x0f) == ContentSpecNode::Any_Other)
  1369.                            buf1.set(SchemaSymbols::fgATTVAL_TWOPOUNDOTHER);
  1370.                        else
  1371.                            buf1.set(fElemMap[j]->getRawName());
  1373.                        XMLBuffer buf2(1023, fMemoryManager);
  1374.                        if (((fElemMapType[k] & 0x0f) == ContentSpecNode::Any) ||
  1375.                            ((fElemMapType[k] & 0x0f) == ContentSpecNode::Any_NS))
  1376.                            buf2.set(SchemaSymbols::fgATTVAL_TWOPOUNDANY);
  1377.                        else if ((fElemMapType[k] & 0x0f) == ContentSpecNode::Any_Other)
  1378.                            buf2.set(SchemaSymbols::fgATTVAL_TWOPOUNDOTHER);
  1379.                        else
  1380.                            buf2.set(fElemMap[k]->getRawName());
  1382.                        pValidator->emitError(XMLValid::UniqueParticleAttributionFail,
  1383.                                              buf1.getRawBuffer(),
  1384.                                              buf2.getRawBuffer());
  1385.                     }
  1386.                     else
  1387.                        fConflictTable[j][k] = 0;
  1388.                 }
  1389.             }
  1390.         }
  1391.     }
  1393.     for (i = 0; i < fElemMapSize; i++)
  1394.         fMemoryManager->deallocate(fConflictTable[i]); //delete [] fConflictTable[i];
  1395.     fMemoryManager->deallocate(fConflictTable); //delete [] fConflictTable;
  1396. }
  1398. XERCES_CPP_NAMESPACE_END