| /* |
| * The Apache Software License, Version 1.1 |
| * |
| * Copyright (c) 1999 The Apache Software Foundation. All rights |
| * reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in |
| * the documentation and/or other materials provided with the |
| * distribution. |
| * |
| * 3. The end-user documentation included with the redistribution, |
| * if any, must include the following acknowledgment: |
| * "This product includes software developed by the |
| * Apache Software Foundation (http://www.apache.org/)." |
| * Alternately, this acknowledgment may appear in the software itself, |
| * if and wherever such third-party acknowledgments normally appear. |
| * |
| * 4. The names "Xerces" and "Apache Software Foundation" must |
| * not be used to endorse or promote products derived from this |
| * software without prior written permission. For written |
| * permission, please contact apache\@apache.org. |
| * |
| * 5. Products derived from this software may not be called "Apache", |
| * nor may "Apache" appear in their name, without prior written |
| * permission of the Apache Software Foundation. |
| * |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED |
| * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR |
| * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF |
| * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
| * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT |
| * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| * ==================================================================== |
| * |
| * This software consists of voluntary contributions made by many |
| * individuals on behalf of the Apache Software Foundation, and was |
| * originally based on software copyright (c) 1999, International |
| * Business Machines, Inc., http://www.ibm.com . For more information |
| * on the Apache Software Foundation, please see |
| * <http://www.apache.org/>. |
| */ |
| |
| /** |
| * $Log$ |
| * Revision 1.1 1999/11/09 01:03:17 twl |
| * Initial revision |
| * |
| * Revision 1.2 1999/11/08 20:45:38 rahul |
| * Swat for adding in Product name and CVS comment log variable. |
| * |
| */ |
| |
| |
| // --------------------------------------------------------------------------- |
| // Includes |
| // --------------------------------------------------------------------------- |
| #include <util/RuntimeException.hpp> |
| #include <framework/XMLValidator.hpp> |
| #include <validators/DTD/CMBinaryOp.hpp> |
| #include <validators/DTD/CMLeaf.hpp> |
| #include <validators/DTD/CMUnaryOp.hpp> |
| #include <validators/DTD/DFAContentModel.hpp> |
| #include <validators/DTD/ContentSpecNode.hpp> |
| #include <validators/DTD/DTDElementDecl.hpp> |
| |
| |
| // --------------------------------------------------------------------------- |
| // Local static data |
| // |
| // gEOCFakeId |
| // gEpsilonFakeId |
| // We have to put in a couple of special CMLeaf nodes to represent |
| // special values, using fake element ids that we know won't conflict |
| // with real element ids. |
| // --------------------------------------------------------------------------- |
| static const unsigned int gEOCFakeId = 0xFFFFFFF1; |
| static const unsigned int gEpsilonFakeId = 0xFFFFFFF2; |
| |
| |
| // --------------------------------------------------------------------------- |
| // DFAContentModel: Constructors and Destructor |
| // --------------------------------------------------------------------------- |
| DFAContentModel::DFAContentModel(const DTDElementDecl& elemDecl) : |
| |
| fElemDecl(elemDecl) |
| , fElemMap(0) |
| , fElemMapSize(0) |
| , fEmptyOk(false) |
| , fEOCPos(0) |
| , fFinalStateFlags(0) |
| , fFollowList(0) |
| , fHeadNode(0) |
| , fLeafCount(0) |
| , fLeafList(0) |
| , fSpecNode(0) |
| , fTransTable(0) |
| , fTransTableSize(0) |
| { |
| // |
| // Store away our content spec node. This is used all over the place |
| // here so its easier to store a member pointer than to pass it around. |
| // |
| fSpecNode = elemDecl.getContentSpec(); |
| |
| // And build the DFA data structures |
| buildDFA(); |
| } |
| |
| DFAContentModel::~DFAContentModel() |
| { |
| // |
| // Clean up all the stuff that is not just temporary representation |
| // data that was cleaned up after building the DFA. |
| // |
| delete [] fFinalStateFlags; |
| |
| unsigned index; |
| for (index = 0; index < fTransTableSize; index++) |
| delete [] fTransTable[index]; |
| delete [] fTransTable; |
| |
| delete [] fElemMap; |
| } |
| |
| |
| // --------------------------------------------------------------------------- |
| // DFAContentModel: Implementation of the ContentModel virtual interface |
| // --------------------------------------------------------------------------- |
| int |
| DFAContentModel::validateContent( const unsigned int* childIds |
| , const unsigned int childCount) const |
| { |
| // |
| // If there are no children, then either we fail on the 0th element |
| // or we return success. It depends upon whether this content model |
| // accepts empty content, which we determined earlier. |
| // |
| if (!childCount) |
| { |
| if (fEmptyOk) |
| return -1; |
| return 0; |
| } |
| |
| // |
| // Lets loop through the children in the array and move our way |
| // through the states. Note that we use the fElemMap array to map |
| // an element index to a state index. |
| // |
| unsigned int curState = 0; |
| unsigned int childIndex = 0; |
| for (; childIndex < childCount; childIndex++) |
| { |
| // Get the current element index out |
| const unsigned int curElem = childIds[childIndex]; |
| |
| // Look up this child in our element map |
| unsigned int elemIndex = 0; |
| for (; elemIndex < fElemMapSize; elemIndex++) |
| { |
| if (fElemMap[elemIndex] == curElem) |
| break; |
| } |
| |
| // If we didn't find it, then obviously not valid |
| if (elemIndex == fElemMapSize) |
| return childIndex; |
| |
| // |
| // Look up the next state for this input symbol when in the |
| // current state. |
| // |
| curState = fTransTable[curState][elemIndex]; |
| |
| // If its not a legal transition then we failed. |
| if (curState == -1) |
| return childIndex; |
| } |
| |
| // |
| // We transitioned all the way through the input list. However, that |
| // does not mean that we ended in a final state. So check whether |
| // our ending state is a final state. |
| // |
| if (!fFinalStateFlags[curState]) |
| return childIndex; |
| |
| return XMLValidator::Success; |
| } |
| |
| |
| // --------------------------------------------------------------------------- |
| // DFAContentModel: Private helper methods |
| // --------------------------------------------------------------------------- |
| void DFAContentModel::buildDFA() |
| { |
| unsigned int index; |
| |
| |
| // |
| // The first step we need to take is to rewrite the content model using |
| // our CMNode objects, and in the process get rid of any repetition short |
| // cuts, converting them into '*' style repetitions or getting rid of |
| // repetitions altogether. |
| // |
| // The conversions done are: |
| // |
| // x+ -> (x|x*) |
| // x? -> (x|epsilon) |
| // |
| // This is a relatively complex scenario. What is happening is that we |
| // create a top level binary node of which the special EOC value is set |
| // as the right side node. The the left side is set to the rewritten |
| // syntax tree. The source is the original content model info from the |
| // decl pool. The rewrite is done by buildSyntaxTree() which recurses the |
| // decl pool's content of the element and builds a new tree in the |
| // process. |
| // |
| // Note that, during this operation, we set each non-epsilon leaf node's |
| // DFA state position and count the number of such leafs, which is left |
| // in the fLeafCount member. |
| // |
| CMLeaf* nodeEOC = new CMLeaf(gEOCFakeId); |
| CMNode* nodeOrgContent = buildSyntaxTree(fElemDecl.getContentSpec()); |
| fHeadNode = new CMBinaryOp |
| ( |
| ContentSpecNode::Sequence |
| , nodeOrgContent |
| , nodeEOC |
| ); |
| |
| // |
| // And handle specially the EOC node, which also must be numbered and |
| // counted as a non-epsilon leaf node. It could not be handled in the |
| // above tree build because it was created before all that started. We |
| // save the EOC position since its used during the DFA building loop. |
| // |
| fEOCPos = fLeafCount; |
| nodeEOC->setPosition(fLeafCount++); |
| |
| // |
| // Ok, so now we have to iterate the new tree and do a little more work |
| // now that we know the leaf count. One thing we need to do is to |
| // calculate the first and last position sets of each node. This is |
| // cached away in each of the nodes. |
| // |
| // Along the way we also set the leaf count in each node as the maximum |
| // state count. They must know this in order to create their first/last |
| // position sets. |
| // |
| // We also need to build an array of references to the non-epsilon |
| // leaf nodes. Since we iterate here the same way as we did during the |
| // initial tree build (which built their position numbers, we will put |
| // them in the array according to their position values. |
| // |
| fLeafList = new CMLeaf*[fLeafCount]; |
| postTreeBuildInit(fHeadNode, 0); |
| |
| // |
| // And, moving onward... We now need to build the follow position sets |
| // for all the nodes. So we allocate an array of pointers to state sets, |
| // one for each leaf node (i.e. each significant DFA position.) |
| // |
| fFollowList = new CMStateSet*[fLeafCount]; |
| for (index = 0; index < fLeafCount; index++) |
| fFollowList[index] = new CMStateSet(fLeafCount); |
| calcFollowList(fHeadNode); |
| |
| // |
| // Check the DFA for ambiguity. If it is ambiguous, then set the |
| // ambiguous flag member and keep going. |
| // |
| fIsAmbiguous = isAmbiguous(); |
| |
| // |
| // Check to see whether this content model can handle an empty content, |
| // which is something we need to optimize by looking now before we |
| // throw away the info that would tell us that. |
| // |
| // If the left node of the head (the top level of the original content) |
| // is nullable, then its true. |
| // |
| fEmptyOk = nodeOrgContent->isNullable(); |
| |
| // |
| // And finally the big push... Now we build the DFA using all the states |
| // and the tree we've built up. First we set up the various data |
| // structures we are going to use while we do this. |
| // |
| // First of all we need an array of unique element ids in our content |
| // model. For each transition table entry, we need a set of contiguous |
| // indices to represent the transitions for a particular input element. |
| // So we need to a zero based range of indexes that map to element types. |
| // This element map provides that mapping. |
| // |
| fElemMap = new unsigned int[fLeafCount]; |
| fElemMapSize = 0; |
| for (unsigned int outIndex = 0; outIndex < fLeafCount; outIndex++) |
| { |
| // Get the current leaf's element index |
| const unsigned int elemId = fLeafList[outIndex]->getId(); |
| |
| // See if the current leaf node's element index is in the list |
| unsigned int inIndex = 0; |
| for (; inIndex < fElemMapSize; inIndex++) |
| { |
| if (fElemMap[inIndex] == elemId) |
| break; |
| } |
| |
| // If it was not in the list, then add it and bump the map size |
| if (inIndex == fElemMapSize) |
| fElemMap[fElemMapSize++] = elemId; |
| } |
| |
| // |
| // Next lets create some arrays, some that that hold transient info |
| // during the DFA build and some that are permament. These are kind of |
| // sticky since we cannot know how big they will get, but we don't want |
| // to use any collection type classes because of performance. |
| // |
| // Basically they will probably be about fLeafCount*2 on average, but can |
| // be as large as 2^(fLeafCount*2), worst case. So we start with |
| // fLeafCount*4 as a middle ground. This will be very unlikely to ever |
| // have to expand though, it if does, the overhead will be somewhat ugly. |
| // |
| unsigned int curArraySize = fLeafCount * 4; |
| const CMStateSet** statesToDo = new const CMStateSet*[curArraySize]; |
| fFinalStateFlags = new bool[curArraySize]; |
| fTransTable = new unsigned int*[curArraySize]; |
| |
| // |
| // Ok we start with the initial set as the first pos set of the head node |
| // (which is the seq node that holds the content model and the EOC node.) |
| // |
| const CMStateSet* setT = new CMStateSet(fHeadNode->getFirstPos()); |
| |
| // |
| // Init our two state flags. Basically the unmarked state counter is |
| // always chasing the current state counter. When it catches up, that |
| // means we made a pass through that did not add any new states to the |
| // lists, at which time we are done. We could have used a expanding array |
| // of flags which we used to mark off states as we complete them, but |
| // this is easier though less readable maybe. |
| // |
| unsigned int unmarkedState = 0; |
| unsigned int curState = 0; |
| |
| // |
| // Init the first transition table entry, and put the initial state |
| // into the states to do list, then bump the current state. |
| // |
| fTransTable[curState] = makeDefStateList(); |
| statesToDo[curState] = setT; |
| curState++; |
| |
| // |
| // Ok, almost done with the algorithm from hell... We now enter the |
| // loop where we go until the states done counter catches up with |
| // the states to do counter. |
| // |
| CMStateSet* newSet = 0; |
| while (unmarkedState < curState) |
| { |
| // |
| // Get the next unmarked state out of the list of states to do. |
| // And get the associated transition table entry. |
| // |
| setT = statesToDo[unmarkedState]; |
| unsigned int* transEntry = fTransTable[unmarkedState]; |
| |
| // Mark this one final if it contains the EOC state |
| fFinalStateFlags[unmarkedState] = setT->getBit(fEOCPos); |
| |
| // Bump up the unmarked state count, marking this state done |
| unmarkedState++; |
| |
| // Loop through each possible input symbol in the element map |
| for (unsigned int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) |
| { |
| // |
| // Build up a set of states which is the union of all of the |
| // follow sets of DFA positions that are in the current state. If |
| // we gave away the new set last time through then create a new |
| // one. Otherwise, zero out the existing one. |
| // |
| if (!newSet) |
| newSet = new CMStateSet(fLeafCount); |
| else |
| newSet->zeroBits(); |
| |
| for (unsigned int leafIndex = 0; leafIndex < fLeafCount; leafIndex++) |
| { |
| // If this leaf index (DFA position) is in the current set... |
| if (setT->getBit(leafIndex)) |
| { |
| // |
| // If this leaf is the current input symbol, then we want |
| // to add its follow list to the set of states to transition |
| // to from the current state. |
| // |
| if (fLeafList[leafIndex]->getId() == fElemMap[elemIndex]) |
| *newSet |= *fFollowList[leafIndex]; |
| } |
| } |
| |
| // |
| // If this new set is not empty, then see if its in the list |
| // of states to do. If not, then add it. |
| // |
| if (!newSet->isEmpty()) |
| { |
| // |
| // Search the 'states to do' list to see if this new |
| // state set is already in there. |
| // |
| unsigned int stateIndex = 0; |
| for (; stateIndex < curState; stateIndex++) |
| { |
| if (*statesToDo[stateIndex] == *newSet) |
| break; |
| } |
| |
| // If we did not find it, then add it |
| if (stateIndex == curState) |
| { |
| // |
| // Put this new state into the states to do and init |
| // a new entry at the same index in the transition |
| // table. |
| // |
| statesToDo[curState] = newSet; |
| fTransTable[curState] = makeDefStateList(); |
| |
| // We now have a new state to do so bump the count |
| curState++; |
| |
| // |
| // Null out the new set to indicate we adopted it. This |
| // will cause the creation of a new set on the next time |
| // around the loop. |
| // |
| newSet = 0; |
| } |
| |
| // |
| // Now set this state in the transition table's entry for this |
| // element (using its index), with the DFA state we will move |
| // to from the current state when we see this input element. |
| // |
| transEntry[elemIndex] = stateIndex; |
| |
| // Expand the arrays if we're full |
| if (curState == curArraySize) |
| { |
| // |
| // Yikes, we overflowed the initial array size, so we've |
| // got to expand all of these arrays. So adjust up the |
| // size by 50% and allocate new arrays. |
| // |
| const unsigned int newSize = (unsigned int)(curArraySize * 1.5); |
| const CMStateSet** newToDo = new const CMStateSet*[newSize]; |
| bool* newFinalFlags = new bool[newSize]; |
| unsigned int** newTransTable = new unsigned int*[newSize]; |
| |
| // Copy over all of the existing content |
| for (unsigned int expIndex = 0; expIndex < curArraySize; expIndex++) |
| { |
| newToDo[expIndex] = statesToDo[expIndex]; |
| newFinalFlags[expIndex] = fFinalStateFlags[expIndex]; |
| newTransTable[expIndex] = fTransTable[expIndex]; |
| } |
| |
| // Clean up the old stuff |
| delete [] statesToDo; |
| delete [] fFinalStateFlags; |
| delete [] fTransTable; |
| |
| // Store the new array size and pointers |
| curArraySize = newSize; |
| statesToDo = newToDo; |
| fFinalStateFlags = newFinalFlags; |
| fTransTable = newTransTable; |
| } |
| } |
| } |
| } |
| |
| // Store the current state count in the trans table size |
| fTransTableSize = curState; |
| |
| // If the last temp set was not stored, then clean it up |
| if (newSet) |
| delete newSet; |
| |
| // |
| // Now we can clean up all of the temporary data that was needed during |
| // DFA build. |
| // |
| delete fHeadNode; |
| fHeadNode = 0; |
| |
| for (index = 0; index < fLeafCount; index++) |
| delete fFollowList[index]; |
| |
| for (index = 0; index < curState; index++) |
| delete (CMStateSet*)statesToDo[index]; |
| |
| delete [] fLeafList; |
| delete [] fFollowList; |
| delete [] statesToDo; |
| } |
| |
| |
| CMNode* DFAContentModel::buildSyntaxTree(const ContentSpecNode* const curNode) |
| { |
| // Initialize a return node pointer |
| CMNode* retNode = 0; |
| |
| // Get the spec type of the passed node |
| const ContentSpecNode::NodeTypes curType = curNode->getType(); |
| |
| if (curType == ContentSpecNode::Leaf) |
| { |
| // |
| // Create a new leaf node, and pass it the current leaf count, which |
| // is its DFA state position. Bump the leaf count after storing it. |
| // This makes the positions zero based since we store first and then |
| // increment. |
| // |
| retNode = new CMLeaf(curNode->getElemId(), fLeafCount++); |
| } |
| else |
| { |
| // |
| // Its not a leaf, so we have to recurse its left and maybe right |
| // nodes. Save both values before we recurse and trash the node. |
| // |
| const ContentSpecNode* leftNode = curNode->getFirst(); |
| const ContentSpecNode* rightNode = curNode->getSecond(); |
| |
| if ((curType == ContentSpecNode::Choice) |
| || (curType == ContentSpecNode::Sequence)) |
| { |
| // |
| // Recurse on both children, and return a binary op node with the |
| // two created sub nodes as its children. The node type is the |
| // same type as the source. |
| // |
| CMNode* newLeft = buildSyntaxTree(leftNode); |
| CMNode* newRight = buildSyntaxTree(rightNode); |
| retNode = new CMBinaryOp(curType, newLeft, newRight); |
| } |
| else if (curType == ContentSpecNode::ZeroOrMore) |
| { |
| // This one is fine as is, just change to our form |
| retNode = new CMUnaryOp(curType, buildSyntaxTree(leftNode)); |
| } |
| else if (curType == ContentSpecNode::ZeroOrOne) |
| { |
| // Convert to (x|epsilon) |
| CMNode* newLeft = buildSyntaxTree(leftNode); |
| retNode = new CMBinaryOp |
| ( |
| ContentSpecNode::Choice |
| , newLeft |
| , new CMLeaf(gEpsilonFakeId) |
| ); |
| } |
| else if (curType == ContentSpecNode::OneOrMore) |
| { |
| // Convert to (x,x*) |
| CMNode* newLeft = buildSyntaxTree(leftNode); |
| CMNode* newLeft2 = buildSyntaxTree(leftNode); |
| retNode = new CMBinaryOp |
| ( |
| ContentSpecNode::Sequence |
| , newLeft |
| , new CMUnaryOp(ContentSpecNode::ZeroOrMore, newLeft2) |
| ); |
| } |
| else |
| { |
| ThrowXML(RuntimeException, XML4CExcepts::CM_UnknownCMSpecType); |
| } |
| } |
| return retNode; |
| } |
| |
| |
| void DFAContentModel::calcFollowList(CMNode* const curNode) |
| { |
| // Get the spec type of the passed node |
| const ContentSpecNode::NodeTypes curType = curNode->getType(); |
| |
| if (curType == ContentSpecNode::Choice) |
| { |
| // Just recurse |
| calcFollowList(((CMBinaryOp*)curNode)->getLeft()); |
| calcFollowList(((CMBinaryOp*)curNode)->getRight()); |
| } |
| else if (curType == ContentSpecNode::Sequence) |
| { |
| // Recurse before we process this node |
| calcFollowList(((CMBinaryOp*)curNode)->getLeft()); |
| calcFollowList(((CMBinaryOp*)curNode)->getRight()); |
| |
| // |
| // Now handle our level. We use our left child's last pos set and our |
| // right child's first pos set, so get them now for convenience. |
| // |
| const CMStateSet& last = ((CMBinaryOp*)curNode)->getLeft()->getLastPos(); |
| const CMStateSet& first = ((CMBinaryOp*)curNode)->getRight()->getFirstPos(); |
| |
| // |
| // Now, for every position which is in our left child's last set |
| // add all of the states in our right child's first set to the |
| // follow set for that position. |
| // |
| for (unsigned int index = 0; index < fLeafCount; index++) |
| { |
| if (last.getBit(index)) |
| *fFollowList[index] |= first; |
| } |
| } |
| else if (curType == ContentSpecNode::ZeroOrMore) |
| { |
| // Recurse first |
| calcFollowList(((CMUnaryOp*)curNode)->getChild()); |
| |
| // |
| // Now handle our level. We use our own first and last position |
| // sets, so get them up front. |
| // |
| const CMStateSet& first = curNode->getFirstPos(); |
| const CMStateSet& last = curNode->getLastPos(); |
| |
| // |
| // For every position which is in our last position set, add all |
| // of our first position states to the follow set for that |
| // position. |
| // |
| for (unsigned int index = 0; index < fLeafCount; index++) |
| { |
| if (last.getBit(index)) |
| *fFollowList[index] |= first; |
| } |
| } |
| else if ((curType == ContentSpecNode::OneOrMore) |
| || (curType == ContentSpecNode::ZeroOrOne)) |
| { |
| ThrowXML1(RuntimeException, XML4CExcepts::CM_NotValidForSpecType, "CalcFollowList"); |
| } |
| } |
| |
| |
| bool DFAContentModel::isAmbiguous() const |
| { |
| unsigned int index; |
| |
| // |
| // Run through the current leaves and remember the min and max element |
| // ids. These will be used to create a bit set that will map to element |
| // ids (adjusted by the min value.) |
| // |
| // Do fLeafCount - 1 because we don't want to pick up the 'EOC' node, |
| // which has a very large dummy value in it. |
| // |
| unsigned int minId = 0xFFFFFFFF; |
| unsigned int maxId = 0; |
| for (index = 0; index < fLeafCount - 1; index++) |
| { |
| const unsigned int curId = fLeafList[index]->getId(); |
| if (curId < minId) |
| minId = curId; |
| |
| if (curId > maxId) |
| maxId = curId; |
| } |
| |
| // |
| // Ok, now we can create a range value that represents the spread |
| // between the min/max element value. The range can never be larger |
| // than the number of elements in the content model, so it would |
| // never be outrageously large unless the content model was just |
| // totally pathological. |
| // |
| // With this number we can create a state set that has a bit per |
| // possible entry in the leaf array. |
| // |
| const unsigned int idRange = (maxId - minId) + 1; |
| CMStateSet idSet(idRange); |
| |
| // Check each follow list |
| for (index = 0; index < fLeafCount - 1; index++) |
| { |
| // Get the current follow list set |
| const CMStateSet* curSet = fFollowList[index]; |
| |
| // |
| // For each possible leaf, we now go through and get the element |
| // id, adjust it to zero base it, then check it in the idSet. If |
| // that bit is already on, its ambiguous. Else set that bit and |
| // keep going. |
| // |
| for (unsigned int inner = 0; inner < fLeafCount - 1; inner++) |
| { |
| // If this bit is not on in the follow set, skip to next |
| if (!curSet->getBit(inner)) |
| continue; |
| |
| // Get the adjusted id value for the element in the follow list |
| const unsigned int adjustedId = fLeafList[inner]->getId() - minId; |
| |
| if (idSet.getBit(adjustedId)) |
| return true; |
| idSet.setBit(adjustedId); |
| } |
| |
| // Zero out the bitset for the next round |
| idSet.zeroBits(); |
| } |
| return false; |
| } |
| |
| |
| // |
| // -1 is used to represent bad transitions in the transition table entry for |
| // each state. So each entry is initialized to an all -1 array. This method |
| // creates a new entry and initializes it. |
| // |
| unsigned int* DFAContentModel::makeDefStateList() const |
| { |
| unsigned int* retArray = new unsigned int[fElemMapSize]; |
| for (unsigned int index = 0; index < fElemMapSize; index++) |
| retArray[index] = -1; |
| return retArray; |
| } |
| |
| |
| int DFAContentModel::postTreeBuildInit( CMNode* const nodeCur |
| , const unsigned int curIndex) |
| { |
| // Set the maximum states on this node |
| nodeCur->setMaxStates(fLeafCount); |
| |
| // Get the spec type of the passed node |
| const ContentSpecNode::NodeTypes curType = nodeCur->getType(); |
| |
| // Get a copy of the index we can modify |
| unsigned int newIndex = curIndex; |
| |
| // Recurse as required |
| if ((curType == ContentSpecNode::Choice) |
| || (curType == ContentSpecNode::Sequence)) |
| { |
| newIndex = postTreeBuildInit(((CMBinaryOp*)nodeCur)->getLeft(), newIndex); |
| newIndex = postTreeBuildInit(((CMBinaryOp*)nodeCur)->getRight(), newIndex); |
| } |
| else if (curType == ContentSpecNode::ZeroOrMore) |
| { |
| newIndex = postTreeBuildInit(((CMUnaryOp*)nodeCur)->getChild(), newIndex); |
| } |
| else if (curType == ContentSpecNode::Leaf) |
| { |
| // |
| // Put this node in the leaf list at the current index if its |
| // a non-epsilon leaf. |
| // |
| if (((CMLeaf*)nodeCur)->getId() != gEpsilonFakeId) |
| fLeafList[newIndex++] = (CMLeaf*)nodeCur; |
| } |
| else |
| { |
| ThrowXML(RuntimeException, XML4CExcepts::CM_UnknownCMSpecType); |
| } |
| return newIndex; |
| } |
