KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > xerces > impl > xs > models > XSDFACM


1 /*
2  * Copyright 1999-2004 The Apache Software Foundation.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 package org.apache.xerces.impl.xs.models;
18
19 import org.apache.xerces.xni.QName;
20 import org.apache.xerces.impl.dtd.models.CMNode;
21 import org.apache.xerces.impl.dtd.models.CMStateSet;
22 import org.apache.xerces.impl.xs.SubstitutionGroupHandler;
23 import org.apache.xerces.impl.xs.XSElementDecl;
24 import org.apache.xerces.impl.xs.XSParticleDecl;
25 import org.apache.xerces.impl.xs.XSModelGroupImpl;
26 import org.apache.xerces.impl.xs.XSWildcardDecl;
27 import org.apache.xerces.impl.xs.XMLSchemaException;
28 import org.apache.xerces.impl.xs.XSConstraints;
29
30 import java.util.Vector JavaDoc;
31
32 /**
33  * DFAContentModel is the implementation of XSCMValidator that does
34  * all of the non-trivial element content validation. This class does
35  * the conversion from the regular expression to the DFA that
36  * it then uses in its validation algorithm.
37  *
38  * @xerces.internal
39  *
40  * @author Neil Graham, IBM
41  * @version $Id: XSDFACM.java,v 1.13 2004/10/06 15:14:52 mrglavas Exp $
42  */
43 public class XSDFACM
44     implements XSCMValidator {
45
46     //
47 // Constants
48 //
49 private static final boolean DEBUG = false;
50
51     // special strings
52
53     // debugging
54
55     /** Set to true to debug content model validation. */
56     private static final boolean DEBUG_VALIDATE_CONTENT = false;
57
58     //
59 // Data
60 //
61
62     /**
63      * This is the map of unique input symbol elements to indices into
64      * each state's per-input symbol transition table entry. This is part
65      * of the built DFA information that must be kept around to do the
66      * actual validation. Note tat since either XSElementDecl or XSParticleDecl object
67      * can live here, we've got to use an Object.
68      */
69     private Object JavaDoc fElemMap[] = null;
70
71     /**
72      * This is a map of whether the element map contains information
73      * related to ANY models.
74      */
75     private int fElemMapType[] = null;
76
77     /**
78      * id of the unique input symbol
79      */
80     private int fElemMapId[] = null;
81     
82     /** The element map size. */
83     private int fElemMapSize = 0;
84
85     /**
86      * This is an array of booleans, one per state (there are
87      * fTransTableSize states in the DFA) that indicates whether that
88      * state is a final state.
89      */
90     private boolean fFinalStateFlags[] = null;
91
92     /**
93      * The list of follow positions for each NFA position (i.e. for each
94      * non-epsilon leaf node.) This is only used during the building of
95      * the DFA, and is let go afterwards.
96      */
97     private CMStateSet fFollowList[] = null;
98
99     /**
100      * This is the head node of our intermediate representation. It is
101      * only non-null during the building of the DFA (just so that it
102      * does not have to be passed all around.) Once the DFA is built,
103      * this is no longer required so its nulled out.
104      */
105     private CMNode fHeadNode = null;
106
107     /**
108      * The count of leaf nodes. This is an important number that set some
109      * limits on the sizes of data structures in the DFA process.
110      */
111     private int fLeafCount = 0;
112
113     /**
114      * An array of non-epsilon leaf nodes, which is used during the DFA
115      * build operation, then dropped.
116      */
117     private XSCMLeaf fLeafList[] = null;
118
119     /** Array mapping ANY types to the leaf list. */
120     private int fLeafListType[] = null;
121
122     /**
123      * This is the transition table that is the main by product of all
124      * of the effort here. It is an array of arrays of ints. The first
125      * dimension is the number of states we end up with in the DFA. The
126      * second dimensions is the number of unique elements in the content
127      * model (fElemMapSize). Each entry in the second dimension indicates
128      * the new state given that input for the first dimension's start
129      * state.
130      * <p>
131      * The fElemMap array handles mapping from element indexes to
132      * positions in the second dimension of the transition table.
133      */
134     private int fTransTable[][] = null;
135
136     /**
137      * The number of valid entries in the transition table, and in the other
138      * related tables such as fFinalStateFlags.
139      */
140     private int fTransTableSize = 0;
141
142     // temp variables
143
144     //
145 // Constructors
146 //
147
148     /**
149      * Constructs a DFA content model.
150      *
151      * @param syntaxTree The syntax tree of the content model.
152      * @param leafCount The number of leaves.
153      *
154      * @exception RuntimeException Thrown if DFA can't be built.
155      */
156
157    public XSDFACM(CMNode syntaxTree, int leafCount) {
158    
159         // Store away our index and pools in members
160 fLeafCount = leafCount;
161
162         //
163 // Create some string pool indexes that represent the names of some
164 // magical nodes in the syntax tree.
165 // (already done in static initialization...
166 //
167
168         //
169 // Ok, so lets grind through the building of the DFA. This method
170 // handles the high level logic of the algorithm, but it uses a
171 // number of helper classes to do its thing.
172 //
173 // In order to avoid having hundreds of references to the error and
174 // string handlers around, this guy and all of his helper classes
175 // just throw a simple exception and we then pass it along.
176 //
177
178         if(DEBUG_VALIDATE_CONTENT) {
179             XSDFACM.time -= System.currentTimeMillis();
180         }
181
182         buildDFA(syntaxTree);
183
184         if(DEBUG_VALIDATE_CONTENT) {
185             XSDFACM.time += System.currentTimeMillis();
186             System.out.println("DFA build: " + XSDFACM.time + "ms");
187         }
188     }
189
190     private static long time = 0;
191
192     //
193 // XSCMValidator methods
194 //
195
196     /**
197      * check whether the given state is one of the final states
198      *
199      * @param state the state to check
200      *
201      * @return whether it's a final state
202      */
203     public boolean isFinalState (int state) {
204         return (state < 0)? false :
205             fFinalStateFlags[state];
206     }
207
208     /**
209      * one transition only
210      *
211      * @param curElem The current element's QName
212      * @param state stack to store the previous state
213      * @param subGroupHandler the substitution group handler
214      *
215      * @return null if transition is invalid; otherwise the Object corresponding to the
216      * XSElementDecl or XSWildcardDecl identified. Also, the
217      * state array will be modified to include the new state; this so that the validator can
218      * store it away.
219      *
220      * @exception RuntimeException thrown on error
221      */
222     public Object JavaDoc oneTransition(QName curElem, int[] state, SubstitutionGroupHandler subGroupHandler) {
223         int curState = state[0];
224
225         if(curState == XSCMValidator.FIRST_ERROR || curState == XSCMValidator.SUBSEQUENT_ERROR) {
226             // there was an error last time; so just go find correct Object in fElemmMap.
227 // ... after resetting state[0].
228 if(curState == XSCMValidator.FIRST_ERROR)
229                 state[0] = XSCMValidator.SUBSEQUENT_ERROR;
230
231             return findMatchingDecl(curElem, subGroupHandler);
232         }
233
234         int nextState = 0;
235         int elemIndex = 0;
236         Object JavaDoc matchingDecl = null;
237
238         for (; elemIndex < fElemMapSize; elemIndex++) {
239             nextState = fTransTable[curState][elemIndex];
240             if (nextState == -1)
241                 continue;
242             int type = fElemMapType[elemIndex] ;
243             if (type == XSParticleDecl.PARTICLE_ELEMENT) {
244                 matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);
245                 if (matchingDecl != null) {
246                     break;
247                 }
248             }
249             else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
250                 if(((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {
251                     matchingDecl = fElemMap[elemIndex];
252                     break;
253                 }
254             }
255         }
256
257         // if we still can't find a match, set the state to first_error
258 // and return null
259 if (elemIndex == fElemMapSize) {
260             state[1] = state[0];
261             state[0] = XSCMValidator.FIRST_ERROR;
262             return findMatchingDecl(curElem, subGroupHandler);
263         }
264
265         state[0] = nextState;
266         return matchingDecl;
267     } // oneTransition(QName, int[], SubstitutionGroupHandler): Object
268
269     Object JavaDoc findMatchingDecl(QName curElem, SubstitutionGroupHandler subGroupHandler) {
270         Object JavaDoc matchingDecl = null;
271
272         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
273             int type = fElemMapType[elemIndex] ;
274             if (type == XSParticleDecl.PARTICLE_ELEMENT) {
275                 matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);
276                 if (matchingDecl != null) {
277                     return matchingDecl;
278                 }
279             }
280             else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
281                 if(((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri))
282                     return fElemMap[elemIndex];
283             }
284         }
285
286         return null;
287     }
288
289     // This method returns the start states of the content model.
290 public int[] startContentModel() {
291         int[] val = new int[2];
292         val[0] = 0;
293         return val;
294     } // startContentModel():int[]
295
296     // this method returns whether the last state was a valid final state
297 public boolean endContentModel(int[] state) {
298         return fFinalStateFlags[state[0]];
299     } // endContentModel(int[]): boolean
300
301     // Killed off whatCanGoHere; we may need it for DOM canInsert(...) etc.,
302 // but we can put it back later.
303
304     //
305 // Private methods
306 //
307
308     /**
309      * Builds the internal DFA transition table from the given syntax tree.
310      *
311      * @param syntaxTree The syntax tree.
312      *
313      * @exception RuntimeException Thrown if DFA cannot be built.
314      */
315     private void buildDFA(CMNode syntaxTree) {
316         //
317 // The first step we need to take is to rewrite the content model
318 // using our CMNode objects, and in the process get rid of any
319 // repetition short cuts, converting them into '*' style repetitions
320 // or getting rid of repetitions altogether.
321 //
322 // The conversions done are:
323 //
324 // x+ -> (x|x*)
325 // x? -> (x|epsilon)
326 //
327 // This is a relatively complex scenario. What is happening is that
328 // we create a top level binary node of which the special EOC value
329 // is set as the right side node. The the left side is set to the
330 // rewritten syntax tree. The source is the original content model
331 // info from the decl pool. The rewrite is done by buildSyntaxTree()
332 // which recurses the decl pool's content of the element and builds
333 // a new tree in the process.
334 //
335 // Note that, during this operation, we set each non-epsilon leaf
336 // node's DFA state position and count the number of such leafs, which
337 // is left in the fLeafCount member.
338 //
339 // The nodeTmp object is passed in just as a temp node to use during
340 // the recursion. Otherwise, we'd have to create a new node on every
341 // level of recursion, which would be piggy in Java (as is everything
342 // for that matter.)
343 //
344
345         /* MODIFIED (Jan, 2001)
346          *
347          * Use following rules.
348          * nullable(x+) := nullable(x), first(x+) := first(x), last(x+) := last(x)
349          * nullable(x?) := true, first(x?) := first(x), last(x?) := last(x)
350          *
351          * The same computation of follow as x* is applied to x+
352          *
353          * The modification drastically reduces computation time of
354          * "(a, (b, a+, (c, (b, a+)+, a+, (d, (c, (b, a+)+, a+)+, (b, a+)+, a+)+)+)+)+"
355          */
356
357         //
358 // And handle specially the EOC node, which also must be numbered
359 // and counted as a non-epsilon leaf node. It could not be handled
360 // in the above tree build because it was created before all that
361 // started. We save the EOC position since its used during the DFA
362 // building loop.
363 //
364 int EOCPos = fLeafCount;
365         XSCMLeaf nodeEOC = new XSCMLeaf(XSParticleDecl.PARTICLE_ELEMENT, null, -1, fLeafCount++);
366         fHeadNode = new XSCMBinOp(
367             XSModelGroupImpl.MODELGROUP_SEQUENCE,
368             syntaxTree,
369             nodeEOC
370         );
371
372         //
373 // Ok, so now we have to iterate the new tree and do a little more
374 // work now that we know the leaf count. One thing we need to do is
375 // to calculate the first and last position sets of each node. This
376 // is cached away in each of the nodes.
377 //
378 // Along the way we also set the leaf count in each node as the
379 // maximum state count. They must know this in order to create their
380 // first/last pos sets.
381 //
382 // We also need to build an array of references to the non-epsilon
383 // leaf nodes. Since we iterate it in the same way as before, this
384 // will put them in the array according to their position values.
385 //
386 fLeafList = new XSCMLeaf[fLeafCount];
387         fLeafListType = new int[fLeafCount];
388         postTreeBuildInit(fHeadNode);
389
390         //
391 // And, moving onward... We now need to build the follow position
392 // sets for all the nodes. So we allocate an array of state sets,
393 // one for each leaf node (i.e. each DFA position.)
394 //
395 fFollowList = new CMStateSet[fLeafCount];
396         for (int index = 0; index < fLeafCount; index++)
397             fFollowList[index] = new CMStateSet(fLeafCount);
398         calcFollowList(fHeadNode);
399         //
400 // And finally the big push... Now we build the DFA using all the
401 // states and the tree we've built up. First we set up the various
402 // data structures we are going to use while we do this.
403 //
404 // First of all we need an array of unique element names in our
405 // content model. For each transition table entry, we need a set of
406 // contiguous indices to represent the transitions for a particular
407 // input element. So we need to a zero based range of indexes that
408 // map to element types. This element map provides that mapping.
409 //
410 fElemMap = new Object JavaDoc[fLeafCount];
411         fElemMapType = new int[fLeafCount];
412         fElemMapId = new int[fLeafCount];
413         fElemMapSize = 0;
414         for (int outIndex = 0; outIndex < fLeafCount; outIndex++) {
415             // optimization from Henry Zongaro:
416 //fElemMap[outIndex] = new Object ();
417 fElemMap[outIndex] = null;
418
419             int inIndex = 0;
420             final int id = fLeafList[outIndex].getParticleId();
421             for (; inIndex < fElemMapSize; inIndex++) {
422                 if (id == fElemMapId[inIndex])
423                     break;
424             }
425
426             // If it was not in the list, then add it, if not the EOC node
427 if (inIndex == fElemMapSize) {
428                 fElemMap[fElemMapSize] = fLeafList[outIndex].getLeaf();
429                 fElemMapType[fElemMapSize] = fLeafListType[outIndex];
430                 fElemMapId[fElemMapSize] = id;
431                 fElemMapSize++;
432             }
433         }
434
435         // the last entry in the element map must be the EOC element.
436 // remove it from the map.
437 if (DEBUG) {
438             if (fElemMapId[fElemMapSize-1] != -1)
439                 System.err.println("interal error in DFA: last element is not EOC.");
440         }
441         fElemMapSize--;
442
443         /***
444          * Optimization(Jan, 2001); We sort fLeafList according to
445          * elemIndex which is *uniquely* associated to each leaf.
446          * We are *assuming* that each element appears in at least one leaf.
447          **/
448
449         int[] fLeafSorter = new int[fLeafCount + fElemMapSize];
450         int fSortCount = 0;
451
452         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
453             final int id = fElemMapId[elemIndex];
454             for (int leafIndex = 0; leafIndex < fLeafCount; leafIndex++) {
455                 if (id == fLeafList[leafIndex].getParticleId())
456                     fLeafSorter[fSortCount++] = leafIndex;
457             }
458             fLeafSorter[fSortCount++] = -1;
459         }
460
461         /* Optimization(Jan, 2001) */
462
463         //
464 // Next lets create some arrays, some that hold transient
465 // information during the DFA build and some that are permament.
466 // These are kind of sticky since we cannot know how big they will
467 // get, but we don't want to use any Java collections because of
468 // performance.
469 //
470 // Basically they will probably be about fLeafCount*2 on average,
471 // but can be as large as 2^(fLeafCount*2), worst case. So we start
472 // with fLeafCount*4 as a middle ground. This will be very unlikely
473 // to ever have to expand, though it if does, the overhead will be
474 // somewhat ugly.
475 //
476 int curArraySize = fLeafCount * 4;
477         CMStateSet[] statesToDo = new CMStateSet[curArraySize];
478         fFinalStateFlags = new boolean[curArraySize];
479         fTransTable = new int[curArraySize][];
480
481         //
482 // Ok we start with the initial set as the first pos set of the
483 // head node (which is the seq node that holds the content model
484 // and the EOC node.)
485 //
486 CMStateSet setT = fHeadNode.firstPos();
487
488         //
489 // Init our two state flags. Basically the unmarked state counter
490 // is always chasing the current state counter. When it catches up,
491 // that means we made a pass through that did not add any new states
492 // to the lists, at which time we are done. We could have used a
493 // expanding array of flags which we used to mark off states as we
494 // complete them, but this is easier though less readable maybe.
495 //
496 int unmarkedState = 0;
497         int curState = 0;
498
499         //
500 // Init the first transition table entry, and put the initial state
501 // into the states to do list, then bump the current state.
502 //
503 fTransTable[curState] = makeDefStateList();
504         statesToDo[curState] = setT;
505         curState++;
506
507         /* Optimization(Jan, 2001); This is faster for
508          * a large content model such as, "(t001+|t002+|.... |t500+)".
509          */
510
511         java.util.Hashtable JavaDoc stateTable = new java.util.Hashtable JavaDoc();
512
513         /* Optimization(Jan, 2001) */
514
515         //
516 // Ok, almost done with the algorithm... We now enter the
517 // loop where we go until the states done counter catches up with
518 // the states to do counter.
519 //
520 while (unmarkedState < curState) {
521             //
522 // Get the first unmarked state out of the list of states to do.
523 // And get the associated transition table entry.
524 //
525 setT = statesToDo[unmarkedState];
526             int[] transEntry = fTransTable[unmarkedState];
527
528             // Mark this one final if it contains the EOC state
529 fFinalStateFlags[unmarkedState] = setT.getBit(EOCPos);
530
531             // Bump up the unmarked state count, marking this state done
532 unmarkedState++;
533
534             // Loop through each possible input symbol in the element map
535 CMStateSet newSet = null;
536             /* Optimization(Jan, 2001) */
537             int sorterIndex = 0;
538             /* Optimization(Jan, 2001) */
539             for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
540                 //
541 // Build up a set of states which is the union of all of
542 // the follow sets of DFA positions that are in the current
543 // state. If we gave away the new set last time through then
544 // create a new one. Otherwise, zero out the existing one.
545 //
546 if (newSet == null)
547                     newSet = new CMStateSet(fLeafCount);
548                 else
549                     newSet.zeroBits();
550
551                 /* Optimization(Jan, 2001) */
552                 int leafIndex = fLeafSorter[sorterIndex++];
553
554                 while (leafIndex != -1) {
555                     // If this leaf index (DFA position) is in the current set...
556 if (setT.getBit(leafIndex)) {
557                         //
558 // If this leaf is the current input symbol, then we
559 // want to add its follow list to the set of states to
560 // transition to from the current state.
561 //
562 newSet.union(fFollowList[leafIndex]);
563                     }
564
565                    leafIndex = fLeafSorter[sorterIndex++];
566                 }
567                 /* Optimization(Jan, 2001) */
568
569                 //
570 // If this new set is not empty, then see if its in the list
571 // of states to do. If not, then add it.
572 //
573 if (!newSet.isEmpty()) {
574                     //
575 // Search the 'states to do' list to see if this new
576 // state set is already in there.
577 //
578
579                     /* Optimization(Jan, 2001) */
580                     Integer JavaDoc stateObj = (Integer JavaDoc)stateTable.get(newSet);
581                     int stateIndex = (stateObj == null ? curState : stateObj.intValue());
582                     /* Optimization(Jan, 2001) */
583
584                     // If we did not find it, then add it
585 if (stateIndex == curState) {
586                         //
587 // Put this new state into the states to do and init
588 // a new entry at the same index in the transition
589 // table.
590 //
591 statesToDo[curState] = newSet;
592                         fTransTable[curState] = makeDefStateList();
593
594                         /* Optimization(Jan, 2001) */
595                         stateTable.put(newSet, new Integer JavaDoc(curState));
596                         /* Optimization(Jan, 2001) */
597
598                         // We now have a new state to do so bump the count
599 curState++;
600
601                         //
602 // Null out the new set to indicate we adopted it.
603 // This will cause the creation of a new set on the
604 // next time around the loop.
605 //
606 newSet = null;
607                     }
608
609                     //
610 // Now set this state in the transition table's entry
611 // for this element (using its index), with the DFA
612 // state we will move to from the current state when we
613 // see this input element.
614 //
615 transEntry[elemIndex] = stateIndex;
616
617                     // Expand the arrays if we're full
618 if (curState == curArraySize) {
619                         //
620 // Yikes, we overflowed the initial array size, so
621 // we've got to expand all of these arrays. So adjust
622 // up the size by 50% and allocate new arrays.
623 //
624 final int newSize = (int)(curArraySize * 1.5);
625                         CMStateSet[] newToDo = new CMStateSet[newSize];
626                         boolean[] newFinalFlags = new boolean[newSize];
627                         int[][] newTransTable = new int[newSize][];
628
629                         // Copy over all of the existing content
630 for (int expIndex = 0; expIndex < curArraySize; expIndex++) {
631                             newToDo[expIndex] = statesToDo[expIndex];
632                             newFinalFlags[expIndex] = fFinalStateFlags[expIndex];
633                             newTransTable[expIndex] = fTransTable[expIndex];
634                         }
635
636                         // Store the new array size
637 curArraySize = newSize;
638                         statesToDo = newToDo;
639                         fFinalStateFlags = newFinalFlags;
640                         fTransTable = newTransTable;
641                     }
642                 }
643             }
644         }
645
646         //
647 // And now we can say bye bye to the temp representation since we've
648 // built the DFA.
649 //
650 if (DEBUG_VALIDATE_CONTENT)
651             dumpTree(fHeadNode, 0);
652         fHeadNode = null;
653         fLeafList = null;
654         fFollowList = null;
655         fLeafListType = null;
656         fElemMapId = null;
657     }
658
659     /**
660      * Calculates the follow list of the current node.
661      *
662      * @param nodeCur The curent node.
663      *
664      * @exception RuntimeException Thrown if follow list cannot be calculated.
665      */
666     private void calcFollowList(CMNode nodeCur) {
667         // Recurse as required
668 if (nodeCur.type() == XSModelGroupImpl.MODELGROUP_CHOICE) {
669             // Recurse only
670 calcFollowList(((XSCMBinOp)nodeCur).getLeft());
671             calcFollowList(((XSCMBinOp)nodeCur).getRight());
672         }
673          else if (nodeCur.type() == XSModelGroupImpl.MODELGROUP_SEQUENCE) {
674             // Recurse first
675 calcFollowList(((XSCMBinOp)nodeCur).getLeft());
676             calcFollowList(((XSCMBinOp)nodeCur).getRight());
677
678             //
679 // Now handle our level. We use our left child's last pos
680 // set and our right child's first pos set, so go ahead and
681 // get them ahead of time.
682 //
683 final CMStateSet last = ((XSCMBinOp)nodeCur).getLeft().lastPos();
684             final CMStateSet first = ((XSCMBinOp)nodeCur).getRight().firstPos();
685
686             //
687 // Now, for every position which is in our left child's last set
688 // add all of the states in our right child's first set to the
689 // follow set for that position.
690 //
691 for (int index = 0; index < fLeafCount; index++) {
692                 if (last.getBit(index))
693                     fFollowList[index].union(first);
694             }
695         }
696          else if (nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_MORE
697         || nodeCur.type() == XSParticleDecl.PARTICLE_ONE_OR_MORE) {
698             // Recurse first
699 calcFollowList(((XSCMUniOp)nodeCur).getChild());
700
701             //
702 // Now handle our level. We use our own first and last position
703 // sets, so get them up front.
704 //
705 final CMStateSet first = nodeCur.firstPos();
706             final CMStateSet last = nodeCur.lastPos();
707
708             //
709 // For every position which is in our last position set, add all
710 // of our first position states to the follow set for that
711 // position.
712 //
713 for (int index = 0; index < fLeafCount; index++) {
714                 if (last.getBit(index))
715                     fFollowList[index].union(first);
716             }
717         }
718
719         else if (nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
720             // Recurse only
721 calcFollowList(((XSCMUniOp)nodeCur).getChild());
722         }
723
724     }
725
726     /**
727      * Dumps the tree of the current node to standard output.
728      *
729      * @param nodeCur The current node.
730      * @param level The maximum levels to output.
731      *
732      * @exception RuntimeException Thrown on error.
733      */
734     private void dumpTree(CMNode nodeCur, int level) {
735         for (int index = 0; index < level; index++)
736             System.out.print(" ");
737
738         int type = nodeCur.type();
739
740         switch(type ) {
741
742         case XSModelGroupImpl.MODELGROUP_CHOICE:
743         case XSModelGroupImpl.MODELGROUP_SEQUENCE: {
744             if (type == XSModelGroupImpl.MODELGROUP_CHOICE)
745                 System.out.print("Choice Node ");
746             else
747                 System.out.print("Seq Node ");
748
749             if (nodeCur.isNullable())
750                 System.out.print("Nullable ");
751
752             System.out.print("firstPos=");
753             System.out.print(nodeCur.firstPos().toString());
754             System.out.print(" lastPos=");
755             System.out.println(nodeCur.lastPos().toString());
756
757             dumpTree(((XSCMBinOp)nodeCur).getLeft(), level+1);
758             dumpTree(((XSCMBinOp)nodeCur).getRight(), level+1);
759             break;
760         }
761         case XSParticleDecl.PARTICLE_ZERO_OR_MORE:
762         case XSParticleDecl.PARTICLE_ONE_OR_MORE:
763         case XSParticleDecl.PARTICLE_ZERO_OR_ONE: {
764             System.out.print("Rep Node ");
765
766             if (nodeCur.isNullable())
767                 System.out.print("Nullable ");
768
769             System.out.print("firstPos=");
770             System.out.print(nodeCur.firstPos().toString());
771             System.out.print(" lastPos=");
772             System.out.println(nodeCur.lastPos().toString());
773
774             dumpTree(((XSCMUniOp)nodeCur).getChild(), level+1);
775             break;
776         }
777         case XSParticleDecl.PARTICLE_ELEMENT: {
778             System.out.print
779             (
780                 "Leaf: (pos="
781                 + ((XSCMLeaf)nodeCur).getPosition()
782                 + "), "
783                 + "(elemIndex="
784                 + ((XSCMLeaf)nodeCur).getLeaf()
785                 + ") "
786             );
787
788             if (nodeCur.isNullable())
789                 System.out.print(" Nullable ");
790
791             System.out.print("firstPos=");
792             System.out.print(nodeCur.firstPos().toString());
793             System.out.print(" lastPos=");
794             System.out.println(nodeCur.lastPos().toString());
795             break;
796         }
797         case XSParticleDecl.PARTICLE_WILDCARD:
798               System.out.print("Any Node: ");
799
800             System.out.print("firstPos=");
801             System.out.print(nodeCur.firstPos().toString());
802             System.out.print(" lastPos=");
803             System.out.println(nodeCur.lastPos().toString());
804             break;
805         default: {
806             throw new RuntimeException JavaDoc("ImplementationMessages.VAL_NIICM");
807         }
808         }
809
810     }
811
812
813     /**
814      * -1 is used to represent bad transitions in the transition table
815      * entry for each state. So each entry is initialized to an all -1
816      * array. This method creates a new entry and initializes it.
817      */
818     private int[] makeDefStateList()
819     {
820         int[] retArray = new int[fElemMapSize];
821         for (int index = 0; index < fElemMapSize; index++)
822             retArray[index] = -1;
823         return retArray;
824     }
825
826     /** Post tree build initialization. */
827     private void postTreeBuildInit(CMNode nodeCur) throws RuntimeException JavaDoc {
828         // Set the maximum states on this node
829 nodeCur.setMaxStates(fLeafCount);
830
831         XSCMLeaf leaf = null;
832         int pos = 0;
833         // Recurse as required
834 if (nodeCur.type() == XSParticleDecl.PARTICLE_WILDCARD) {
835             leaf = (XSCMLeaf)nodeCur;
836             pos = leaf.getPosition();
837             fLeafList[pos] = leaf;
838             fLeafListType[pos] = XSParticleDecl.PARTICLE_WILDCARD;
839         }
840         else if ((nodeCur.type() == XSModelGroupImpl.MODELGROUP_CHOICE) ||
841                  (nodeCur.type() == XSModelGroupImpl.MODELGROUP_SEQUENCE)) {
842             postTreeBuildInit(((XSCMBinOp)nodeCur).getLeft());
843             postTreeBuildInit(((XSCMBinOp)nodeCur).getRight());
844         }
845         else if (nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_MORE ||
846                  nodeCur.type() == XSParticleDecl.PARTICLE_ONE_OR_MORE ||
847                  nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
848             postTreeBuildInit(((XSCMUniOp)nodeCur).getChild());
849         }
850         else if (nodeCur.type() == XSParticleDecl.PARTICLE_ELEMENT) {
851             // Put this node in the leaf list at the current index if its
852 // a non-epsilon leaf.
853 leaf = (XSCMLeaf)nodeCur;
854             pos = leaf.getPosition();
855             fLeafList[pos] = leaf;
856             fLeafListType[pos] = XSParticleDecl.PARTICLE_ELEMENT;
857         }
858         else {
859             throw new RuntimeException JavaDoc("ImplementationMessages.VAL_NIICM");
860         }
861     }
862
863     /**
864      * check whether this content violates UPA constraint.
865      *
866      * @param subGroupHandler the substitution group handler
867      * @return true if this content model contains other or list wildcard
868      */
869     public boolean checkUniqueParticleAttribution(SubstitutionGroupHandler subGroupHandler) throws XMLSchemaException {
870         // Unique Particle Attribution
871 // store the conflict results between any two elements in fElemMap
872 // 0: not compared; -1: no conflict; 1: conflict
873 // initialize the conflict table (all 0 initially)
874 byte conflictTable[][] = new byte[fElemMapSize][fElemMapSize];
875
876         // for each state, check whether it has overlap transitions
877 for (int i = 0; i < fTransTable.length && fTransTable[i] != null; i++) {
878             for (int j = 0; j < fElemMapSize; j++) {
879                 for (int k = j+1; k < fElemMapSize; k++) {
880                     if (fTransTable[i][j] != -1 &&
881                         fTransTable[i][k] != -1) {
882                         if (conflictTable[j][k] == 0) {
883                             conflictTable[j][k] = XSConstraints.overlapUPA
884                                                    (fElemMap[j],fElemMap[k],
885                                                    subGroupHandler) ?
886                                                    (byte)1 : (byte)-1;
887                         }
888                     }
889                 }
890             }
891         }
892
893         // report all errors
894 for (int i = 0; i < fElemMapSize; i++) {
895             for (int j = 0; j < fElemMapSize; j++) {
896                 if (conflictTable[i][j] == 1) {
897                     //errors.newError("cos-nonambig", new Object[]{fElemMap[i].toString(),
898 // fElemMap[j].toString()});
899 // REVISIT: do we want to report all errors? or just one?
900 throw new XMLSchemaException("cos-nonambig", new Object JavaDoc[]{fElemMap[i].toString(),
901                                                                               fElemMap[j].toString()});
902                 }
903             }
904         }
905
906         // if there is a other or list wildcard, we need to check this CM
907 // again, if this grammar is cached.
908 for (int i = 0; i < fElemMapSize; i++) {
909             if (fElemMapType[i] == XSParticleDecl.PARTICLE_WILDCARD) {
910                 XSWildcardDecl wildcard = (XSWildcardDecl)fElemMap[i];
911                 if (wildcard.fType == XSWildcardDecl.NSCONSTRAINT_LIST ||
912                     wildcard.fType == XSWildcardDecl.NSCONSTRAINT_NOT) {
913                     return true;
914                 }
915             }
916         }
917
918         return false;
919     }
920
921     /**
922      * Check which elements are valid to appear at this point. This method also
923      * works if the state is in error, in which case it returns what should
924      * have been seen.
925      *
926      * @param state the current state
927      * @return a Vector whose entries are instances of
928      * either XSWildcardDecl or XSElementDecl.
929      */
930     public Vector JavaDoc whatCanGoHere(int[] state) {
931         int curState = state[0];
932         if (curState < 0)
933             curState = state[1];
934
935         Vector JavaDoc ret = new Vector JavaDoc();
936         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
937             if (fTransTable[curState][elemIndex] != -1)
938                 ret.addElement(fElemMap[elemIndex]);
939         }
940         return ret;
941     }
942         
943 } // class DFAContentModel
944
Popular Tags