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


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags