KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > enhydra > apache > xerces > validators > common > DFAContentModel


1 /*
2  * The Apache Software License, Version 1.1
3  *
4  *
5  * Copyright (c) 1999,2000 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 org.enhydra.apache.xerces.validators.common;
59
60 import org.enhydra.apache.xerces.framework.XMLContentSpec;
61 import org.enhydra.apache.xerces.utils.ImplementationMessages;
62 import org.enhydra.apache.xerces.utils.QName;
63 import org.enhydra.apache.xerces.validators.schema.SchemaGrammar;
64 import org.enhydra.apache.xerces.validators.schema.SubstitutionGroupComparator;
65
66 /**
67  * DFAContentModel is the derivative of ContentModel that does
68  * all of the non-trivial element content validation. This class does
69  * the conversion from the regular expression to the DFA that
70  * it then uses in its validation algorithm.
71  *
72  * @version $Id: DFAContentModel.java,v 1.2 2005/01/26 08:28:44 jkjome Exp $
73  */
74 public class DFAContentModel
75     implements XMLContentModel {
76
77     //
78 // Constants
79 //
80 // special strings
81
82     /** Epsilon string. */
83     //private static final String fEpsilonString = "<<CMNODE_EPSILON>>";
84 private static final int EPSILON = -2;
85
86     /** End-of-content string. */
87     //private static final String fEOCString = "<<CMNODE_EOC>>";
88 private static final int EOC = -3;
89
90     // debugging
91
92     /** Set to true to debug content model validation. */
93     private static final boolean DEBUG_VALIDATE_CONTENT = false;
94
95     //
96 // Data
97 //
98
99     /* this is the SubstitutionGroupComparator object */
100     private SubstitutionGroupComparator comparator = null;
101
102     /**
103      * This is the map of unique input symbol elements to indices into
104      * each state's per-input symbol transition table entry. This is part
105      * of the built DFA information that must be kept around to do the
106      * actual validation.
107      */
108     private QName 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     /** The element map size. */
117     private int fElemMapSize = 0;
118
119     /** Boolean to allow DTDs to validate even with namespace support. */
120     private boolean fDTD;
121
122     /* Used to indicated mixed model */
123     private boolean fMixed;
124
125     /**
126      * The string index for the 'end of content' string that we add to
127      * the string pool. This is used as the special name of an element
128      * that represents the end of the syntax tree.
129      */
130     private int fEOCIndex = 0;
131
132     /**
133      * The NFA position of the special EOC (end of content) node. This
134      * is saved away since it's used during the DFA build.
135      */
136     private int fEOCPos = 0;
137
138     /**
139      * The string index for the 'epsilon' string that we add to the
140      * string pool. This represents epsilon node transitions in the
141      * syntax tree.
142      */
143     private int fEpsilonIndex = 0;
144
145     /**
146      * This is an array of booleans, one per state (there are
147      * fTransTableSize states in the DFA) that indicates whether that
148      * state is a final state.
149      */
150     private boolean fFinalStateFlags[] = null;
151
152     /**
153      * The list of follow positions for each NFA position (i.e. for each
154      * non-epsilon leaf node.) This is only used during the building of
155      * the DFA, and is let go afterwards.
156      */
157     private CMStateSet fFollowList[] = null;
158
159     /**
160      * This is the head node of our intermediate representation. It is
161      * only non-null during the building of the DFA (just so that it
162      * does not have to be passed all around.) Once the DFA is built,
163      * this is no longer required so its nulled out.
164      */
165     private CMNode fHeadNode = null;
166
167     /**
168      * The count of leaf nodes. This is an important number that set some
169      * limits on the sizes of data structures in the DFA process.
170      */
171     private int fLeafCount = 0;
172
173     /**
174      * An array of non-epsilon leaf nodes, which is used during the DFA
175      * build operation, then dropped.
176      */
177     private CMLeaf fLeafList[] = null;
178
179     /** Array mapping ANY types to the leaf list. */
180     private int fLeafListType[] = null;
181
182     private ContentLeafNameTypeVector fLeafNameTypeVector = null;
183
184     /**
185      * The string pool of our parser session. This is set during construction
186      * and kept around.
187      */
188     //private StringPool fStringPool = null;
189
190     /**
191      * This is the transition table that is the main by product of all
192      * of the effort here. It is an array of arrays of ints. The first
193      * dimension is the number of states we end up with in the DFA. The
194      * second dimensions is the number of unique elements in the content
195      * model (fElemMapSize). Each entry in the second dimension indicates
196      * the new state given that input for the first dimension's start
197      * state.
198      * <p>
199      * The fElemMap array handles mapping from element indexes to
200      * positions in the second dimension of the transition table.
201      */
202     private int fTransTable[][] = null;
203
204     /**
205      * The number of valid entries in the transition table, and in the other
206      * related tables such as fFinalStateFlags.
207      */
208     private int fTransTableSize = 0;
209
210     /**
211      * Flag that indicates that even though we have a "complicated"
212      * content model, it is valid to have no content. In other words,
213      * all parts of the content model are optional. For example:
214      * <pre>
215      * &lt;!ELEMENT AllOptional (Optional*,NotRequired?)&gt;
216      * </pre>
217      */
218     private boolean fEmptyContentIsValid = false;
219
220     // temp variables
221
222     /** Temporary qualified name. */
223     private QName fQName = new QName();
224
225     //
226 // Constructors
227 //
228
229     /**
230      * Constructs a DFA content model.
231      *
232      * @param stringPool The string pool.
233      * @param syntaxTree The syntax tree of the content model.
234      * @param leafCount The number of leaves.
235      *
236      * @exception CMException Thrown if DMA can't be built.
237      */
238
239    // public DFAContentModel(StringPool stringPool,
240 public DFAContentModel( CMNode syntaxTree,
241                            int leafCount) throws CMException {
242        this(syntaxTree, leafCount, false, false);
243    }
244
245     /**
246      * Constructs a DFA content model.
247      *
248      * @param stringPool The string pool.
249      * @param syntaxTree The syntax tree of the content model.
250      * @param leafCount The number of leaves.
251      *
252      * @exception CMException Thrown if DMA can't be built.
253      */
254
255    // public DFAContentModel(StringPool stringPool,
256 public DFAContentModel( CMNode syntaxTree,
257                            int leafCount, boolean dtd, boolean mixed) throws CMException {
258
259         // Store away our index and pools in members
260 //fStringPool = stringPool;
261 fLeafCount = leafCount;
262
263         //
264 // Create some string pool indexes that represent the names of some
265 // magical nodes in the syntax tree.
266 //
267 /*** Defect 945 ***
268         if (fEpsilonString == null)
269         {
270             fEpsilonString = new String("<<CMNODE_EPSILON>>");
271             fEpsilonString.intern();
272             fEOCString = new String("<<CMNODE_EOC>>");
273             fEOCString.intern();
274         }
275         /***/
276
277        // fEpsilonIndex = fStringPool.addSymbol(fEpsilonString);
278 // fEOCIndex = fStringPool.addSymbol(fEOCString);
279
280         fEpsilonIndex = EPSILON;
281         fEOCIndex = EOC;
282
283         fDTD = dtd;
284         fMixed = mixed;
285
286         //
287 // Ok, so lets grind through the building of the DFA. This method
288 // handles the high level logic of the algorithm, but it uses a
289 // number of helper classes to do its thing.
290 //
291 // In order to avoid having hundreds of references to the error and
292 // string handlers around, this guy and all of his helper classes
293 // just throw a simple exception and we then pass it along.
294 //
295
296     DFAContentModel.time -= System.currentTimeMillis();
297
298         buildDFA(syntaxTree);
299
300     DFAContentModel.time += System.currentTimeMillis();
301
302     if (DEBUG_VALIDATE_CONTENT)
303         System.out.println("DFA build: " + DFAContentModel.time + "ms");
304     }
305
306     private static long time = 0;
307
308     //
309 // XMLContentModel methods
310 //
311
312     /**
313      * Check that the specified content is valid according to this
314      * content model. This method can also be called to do 'what if'
315      * testing of content models just to see if they would be valid.
316      * <p>
317      * A value of -1 in the children array indicates a PCDATA node. All other
318      * indexes will be positive and represent child elements. The count can be
319      * zero, since some elements have the EMPTY content model and that must be
320      * confirmed.
321      *
322      * @param children The children of this element. Each integer is an index within
323      * the <code>StringPool</code> of the child element name. An index
324      * of -1 is used to indicate an occurrence of non-whitespace character
325      * data.
326      * @param offset Offset into the array where the children starts.
327      * @param length The number of entries in the <code>children</code> array.
328      *
329      * @return The value -1 if fully valid, else the 0 based index of the child
330      * that first failed. If the value returned is equal to the number
331      * of children, then the specified children are valid but additional
332      * content is required to reach a valid ending state.
333      *
334      * @exception CMException Thrown on error.
335      */
336     public int validateContent(QName children[], int offset, int length) throws CMException {
337
338         if (DEBUG_VALIDATE_CONTENT)
339             System.out.println("DFAContentModel#validateContent");
340
341         //
342 // A DFA content model must *always* have at least 1 child
343 // so a failure is given if no children present.
344 //
345 // Defect 782: This is an incorrect statement because a DFA
346 // content model is also used for constructions such as:
347 //
348 // (Optional*,NotRequired?)
349 //
350 // where a perfectly valid content would be NO CHILDREN.
351 // Therefore, if there are no children, we must check to
352 // see if the CMNODE_EOC marker is a valid start state! -Ac
353 //
354 if (length == 0) {
355             if (DEBUG_VALIDATE_CONTENT) {
356                 System.out.println("!!! no children");
357                 System.out.println("elemMap="+fElemMap);
358                 for (int i = 0; i < fElemMap.length; i++) {
359                     int uriIndex = fElemMap[i].uri;
360                     int localpartIndex = fElemMap[i].localpart;
361                     /*
362                     System.out.println("fElemMap["+i+"]="+uriIndex+","+
363                                        localpartIndex+" ("+
364                                        fStringPool.toString(uriIndex)+", "+
365                                        fStringPool.toString(localpartIndex)+
366                                        ')');
367                                        */
368                 }
369                 System.out.println("EOCIndex="+fEOCIndex);
370             }
371
372             return fEmptyContentIsValid ? -1 : 0;
373
374         } // if child count == 0
375
376         //
377 // Lets loop through the children in the array and move our way
378 // through the states. Note that we use the fElemMap array to map
379 // an element index to a state index.
380 //
381 int curState = 0;
382         int nextState = 0;
383         for (int childIndex = 0; childIndex < length; childIndex++)
384         {
385             // Get the current element index out
386 final QName curElem = children[offset + childIndex];
387             //System.out.println("children["+(offset+childIndex)+"]: "+curElem);
388
389
390             // If this is text in a Schema mixed content model, skip it.
391 if (fMixed && (curElem.localpart == -1)) {
392                 continue;
393             }
394
395             // Look up this child in our element map
396 int elemIndex = 0;
397             for (; elemIndex < fElemMapSize; elemIndex++)
398             {
399                 if (fDTD) {
400                     if (fElemMap[elemIndex].rawname == curElem.rawname) {
401                         nextState = fTransTable[curState][elemIndex];
402                         if (nextState != -1)
403                           break;
404                     }
405                 }
406                 else {
407                     int type = fElemMapType[elemIndex] & 0x0f ;
408                     if (type == XMLContentSpec.CONTENTSPECNODE_LEAF) {
409                         if (fElemMap[elemIndex].uri==curElem.uri
410                             && fElemMap[elemIndex].localpart == curElem.localpart)
411                             {
412                             nextState = fTransTable[curState][elemIndex];
413                             if (nextState != -1)
414                                 break;
415                         }
416                     }
417                     else if (type == XMLContentSpec.CONTENTSPECNODE_ANY) {
418                             nextState = fTransTable[curState][elemIndex];
419                             if (nextState != -1)
420                               break;
421                         }
422                     else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_NS) {
423                         if (curElem.uri == fElemMap[elemIndex].uri) {
424                             nextState = fTransTable[curState][elemIndex];
425                             if (nextState != -1)
426                               break;
427                         }
428                     }
429                     else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER) {
430                         if (fElemMap[elemIndex].uri != curElem.uri) {
431                             nextState = fTransTable[curState][elemIndex];
432                             if (nextState != -1)
433                               break;
434                         }
435                     }
436                 }
437             }
438
439             // If "nextState" is -1, we found a match, but the transition is invalid
440 if (nextState == -1) {
441                 if (DEBUG_VALIDATE_CONTENT)
442                     System.out.println("!!! not a legal transition");
443                 return childIndex;
444             }
445
446             // If we didn't find it, then obviously not valid
447 if (elemIndex == fElemMapSize) {
448                 if (DEBUG_VALIDATE_CONTENT) {
449                     System.out.println("!!! didn't find it");
450
451                     System.out.println("curElem : " +curElem );
452                     for (int i=0; i<fElemMapSize; i++) {
453                         System.out.println("fElemMap["+i+"] = " +fElemMap[i] );
454                         System.out.println("fElemMapType["+i+"] = " +fElemMapType[i] );
455                     }
456                 }
457
458                 return childIndex;
459             }
460
461             curState = nextState;
462             nextState = 0;
463
464         }
465
466         //
467 // We transitioned all the way through the input list. However, that
468 // does not mean that we ended in a final state. So check whether
469 // our ending state is a final state.
470 //
471 if (DEBUG_VALIDATE_CONTENT)
472             System.out.println("curState="+curState+", childCount="+length);
473         if (!fFinalStateFlags[curState])
474             return length;
475
476         // success!
477 return -1;
478     }
479
480
481     private boolean isEqual(QName name1, QName name2) {
482             return name1.localpart == name2.localpart &&
483                 name1.uri == name2.uri;
484     }
485
486     public int validateContentSpecial(QName children[], int offset, int length) throws Exception JavaDoc{
487         if (DEBUG_VALIDATE_CONTENT)
488             System.out.println("DFAContentModel#validateContentSpecial");
489
490         if (comparator==null) {
491             return validateContent(children,offset, length);
492         }
493
494
495         if (length == 0) {
496             if (DEBUG_VALIDATE_CONTENT) {
497                 System.out.println("!!! no children");
498                 System.out.println("elemMap="+fElemMap);
499                 for (int i = 0; i < fElemMap.length; i++) {
500                     int uriIndex = fElemMap[i].uri;
501                     int localpartIndex = fElemMap[i].localpart;
502                 }
503                 System.out.println("EOCIndex="+fEOCIndex);
504             }
505
506             return fEmptyContentIsValid ? -1 : 0;
507
508         } // if child count == 0
509
510         //
511 // Lets loop through the children in the array and move our way
512 // through the states. Note that we use the fElemMap array to map
513 // an element index to a state index.
514 //
515 int curState = 0;
516         int nextState = 0;
517         for (int childIndex = 0; childIndex < length; childIndex++)
518         {
519             // Get the current element index out
520 final QName curElem = children[offset + childIndex];
521
522             // Look up this child in our element map
523 int elemIndex = 0;
524             for (; elemIndex < fElemMapSize; elemIndex++)
525             {
526                 int type = fElemMapType[elemIndex] & 0x0f ;
527                 if (type == XMLContentSpec.CONTENTSPECNODE_LEAF) {
528                     if (comparator.isEquivalentTo(curElem,fElemMap[elemIndex]) ) {
529                         nextState = fTransTable[curState][elemIndex];
530                         if (nextState != -1)
531                             break;
532                     }
533                 }
534                 else if (type == XMLContentSpec.CONTENTSPECNODE_ANY) {
535                         nextState = fTransTable[curState][elemIndex];
536                         if (nextState != -1)
537                           break;
538                 }
539                 else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_NS) {
540                     if (curElem.uri == fElemMap[elemIndex].uri) {
541                         nextState = fTransTable[curState][elemIndex];
542                         if (nextState != -1)
543                           break;
544                     }
545                 }
546                 else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER) {
547                     if (fElemMap[elemIndex].uri != curElem.uri) {
548                         nextState = fTransTable[curState][elemIndex];
549                         if (nextState != -1)
550                           break;
551                     }
552                 }
553
554             }
555
556             // If "nextState" is -1, we found a match, but the transition is invalid
557 if (nextState == -1) {
558                 if (DEBUG_VALIDATE_CONTENT)
559                     System.out.println("!!! not a legal transition");
560                 return childIndex;
561             }
562
563             // If we didn't find it, then obviously not valid
564 if (elemIndex == fElemMapSize) {
565                 if (DEBUG_VALIDATE_CONTENT) {
566                     System.out.println("!!! didn't find it");
567
568                     System.out.println("curElem : " +curElem );
569                     for (int i=0; i<fElemMapSize; i++) {
570                         System.out.println("fElemMap["+i+"] = " +fElemMap[i] );
571                         System.out.println("fElemMapType["+i+"] = " +fElemMapType[i] );
572                     }
573                 }
574
575                 return childIndex;
576             }
577
578             curState = nextState;
579             nextState = 0;
580
581         }
582
583         //
584 // We transitioned all the way through the input list. However, that
585 // does not mean that we ended in a final state. So check whether
586 // our ending state is a final state.
587 //
588 if (DEBUG_VALIDATE_CONTENT)
589             System.out.println("curState="+curState+", childCount="+length);
590         if (!fFinalStateFlags[curState])
591             return length;
592
593         // success!
594 return -1;
595     }
596
597     /**
598      * check whether the given state is one of the final states
599      *
600      * @param state the state to check
601      *
602      * @return whether it's a final state
603      */
604     public boolean isFinalState (int state) {
605         if (state < 0)
606             return false;
607         return fFinalStateFlags[state];
608     }
609
610     /**
611      * one transition only
612      *
613      * @param curElem The current element's QName
614      * @param stateStack stack to store the previous state
615      * @param curPos the current position of the stack
616      *
617      * @return The value -1 if not valid, otherwise the index of the matching leaf
618      *
619      * @exception CMException Thrown on error.
620      */
621     public int oneTransition(QName curElem, int[] stateStack, int curPos) throws Exception JavaDoc{
622         int curState = stateStack[curPos];
623
624         // if it's an illegal state, just return -1
625 if (curState < 0) {
626             return -1;
627         }
628
629         int nextState = 0;
630         int elemIndex = 0;
631
632         for (; elemIndex < fElemMapSize; elemIndex++) {
633             int type = fElemMapType[elemIndex] & 0x0f ;
634             if (type == XMLContentSpec.CONTENTSPECNODE_LEAF) {
635                 if (isEqual(curElem, fElemMap[elemIndex])) {
636                     nextState = fTransTable[curState][elemIndex];
637                     if (nextState != -1)
638                         break;
639                 }
640             }
641             else if (type == XMLContentSpec.CONTENTSPECNODE_ANY) {
642                     nextState = fTransTable[curState][elemIndex];
643                     if (nextState != -1)
644                       break;
645             }
646             else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_NS) {
647                 if (curElem.uri == fElemMap[elemIndex].uri) {
648                     nextState = fTransTable[curState][elemIndex];
649                     if (nextState != -1)
650                       break;
651                 }
652             }
653             else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER) {
654                 if (fElemMap[elemIndex].uri != curElem.uri) {
655                     nextState = fTransTable[curState][elemIndex];
656                     if (nextState != -1)
657                       break;
658                 }
659             }
660         }
661
662         // if we can't find a match, try substitutionGroup
663 if (elemIndex == fElemMapSize && comparator != null) {
664             for (elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
665                 if (fElemMapType[elemIndex] == XMLContentSpec.CONTENTSPECNODE_LEAF) {
666                     if (comparator.isEquivalentTo(curElem,fElemMap[elemIndex])) {
667                         nextState = fTransTable[curState][elemIndex];
668                         if (nextState != -1)
669                             break;
670                     }
671                 }
672             }
673         }
674
675         // if we still can't find a match, set the state to -1 (error)
676 // and return -1
677 if (elemIndex == fElemMapSize) {
678             stateStack[curPos] = -1;
679             return -1;
680         }
681
682         stateStack[curPos] = nextState;
683         return elemIndex;
684     }
685
686     public void setSubstitutionGroupComparator(SubstitutionGroupComparator comparator) {
687         this.comparator = comparator;
688     }
689
690     /**
691      * Returns information about which elements can be placed at a particular point
692      * in the passed element's content model.
693      * <p>
694      * Note that the incoming content model to test must be valid at least up to
695      * the insertion point. If not, then -1 will be returned and the info object
696      * will not have been filled in.
697      * <p>
698      * If, on return, the info.isValidEOC flag is set, then the 'insert after'
699      * element is a valid end of content. In other words, nothing needs to be
700      * inserted after it to make the parent element's content model valid.
701      *
702      * @param fullyValid Only return elements that can be inserted and still
703      * maintain the validity of subsequent elements past the
704      * insertion point (if any). If the insertion point is at
705      * the end, and this is true, then only elements that can
706      * be legal final states will be returned.
707      * @param info An object that contains the required input data for the method,
708      * and which will contain the output information if successful.
709      *
710      * @return The value -1 if fully valid, else the 0 based index of the child
711      * that first failed before the insertion point. If the value
712      * returned is equal to the number of children, then the specified
713      * children are valid but additional content is required to reach a
714      * valid ending state.
715      *
716      * @see InsertableElementsInfo
717      */
718     public int whatCanGoHere(boolean fullyValid,
719                              InsertableElementsInfo info) throws CMException {
720
721         //
722 // First, lets make sure that the passed in current content is valid
723 // up to the insert point.
724 //
725 int curState = 0;
726         for (int childIndex = 0; childIndex < info.insertAt; childIndex++)
727         {
728             // Get the current element index out
729 final QName curElem = info.curChildren[childIndex];
730
731             // Look up this child in our element map
732 int elemIndex = 0;
733             for (; elemIndex < fElemMapSize; elemIndex++)
734             {
735                 if (fElemMap[elemIndex].uri == curElem.uri &&
736                     fElemMap[elemIndex].localpart == curElem.localpart)
737                     break;
738             }
739
740             // If we didn't find it, then not valid so return failure index
741 if (elemIndex == fElemMapSize)
742                 return childIndex;
743
744             //
745 // Look up the next state for this input symbol when in the
746 // current state.
747 //
748 curState = fTransTable[curState][elemIndex];
749
750             // If its not a legal transition, then invalid
751 if (curState == -1)
752                 return childIndex;
753         }
754
755         //
756 // If we got here, then curState is set to the state that would be
757 // the transition before the insertion point. We let this sit until
758 // below, where it will be needed.
759 //
760 final int insertState = curState;
761
762         //
763 // Set any stuff we can know right off the bat for all cases.
764 // We can set the valid EOC flag at this point
765 // since its just based on the state we ended in at the insert point.
766 // The 'canHoldPCData" will be true if it's a mixed content model.
767 //
768 info.canHoldPCData = fMixed;
769         info.isValidEOC = fFinalStateFlags[insertState];
770
771         //
772 // Set the results count member and then see if we need to reallocate
773 // the outgoing arrays.
774 //
775 info.resultsCount = fElemMapSize;
776
777         if ((info.results == null) || (info.results.length < info.resultsCount))
778             info.results = new boolean[info.resultsCount];
779
780         if ((info.possibleChildren == null)
781         || (info.possibleChildren.length < info.resultsCount))
782         {
783             info.possibleChildren = new QName[info.resultsCount];
784             for (int i = 0; i < info.possibleChildren.length; i++) {
785                 info.possibleChildren[i] = new QName();
786             }
787         }
788
789         //
790 // Fill in the possible children array, from our array. For each one
791 // of them, see if there is a valid transition from our insert at
792 // state on that input. Mark the results index for that child according
793 // to whether there is a transition or not.
794 //
795 for (int index = 0; index < fElemMapSize; index++)
796         {
797             info.possibleChildren[index].setValues(fElemMap[index]);
798             info.results[index] = (fTransTable[insertState][index] != -1);
799         }
800
801         //
802 // If the fully valid parameter is set, then we have to go through
803 // the grunt work of plugging in each possible insertable element
804 // and running the DFA from that point to see if it would create a
805 // fully valid content model.
806 //
807 // <TBD> When/if the validator is changed to be stateful, then change
808 // this stuff to start the exploratory validation at the insert state,
809 // not from the start each time.
810 //
811 if (fullyValid)
812         {
813             for (int index = 0; index < info.resultsCount; index++)
814             {
815                 // Don't need to consider this one since its not insertable
816 if (!info.results[index])
817                     continue;
818
819                 // Stick this element into the insert at spot
820 info.curChildren[info.insertAt] = info.possibleChildren[index];
821
822                 // And validate it. If it fails, then this one loses
823 if (validateContent(info.curChildren, 0, info.childCount) != -1)
824                     info.results[index] = false;
825             }
826         }
827
828         return -1;
829     }
830
831     public ContentLeafNameTypeVector getContentLeafNameTypeVector() {
832         return fLeafNameTypeVector;
833     }
834
835     // Unique Particle Attribution
836 // store the conflict results between any two elements in fElemMap
837 // -1: not compared; 0: no conflict; 1: conflict
838 private byte fConflictTable[][];
839
840     // check UPA after build the DFA
841 public void checkUniqueParticleAttribution(SchemaGrammar gram) throws Exception JavaDoc {
842         // rename back
843 for (int i = 0; i < fElemMapSize; i++)
844             fElemMap[i].uri = gram.getContentSpecOrgUri(fElemMap[i].uri);
845
846         // initialize the conflict table
847 fConflictTable = new byte[fElemMapSize][fElemMapSize];
848         for (int j = 0; j < fElemMapSize; j++) {
849             for (int k = j+1; k < fElemMapSize; k++)
850                 fConflictTable[j][k] = -1;
851         }
852
853         // for each state, check whether it has overlap transitions
854 for (int i = 0; i < fTransTable.length && fTransTable[i] != null; i++) {
855             for (int j = 0; j < fElemMapSize; j++) {
856                 for (int k = j+1; k < fElemMapSize; k++) {
857                     if (fTransTable[i][j] != -1 &&
858                         fTransTable[i][k] != -1) {
859                         if (fConflictTable[j][k] == -1) {
860                             fConflictTable[j][k] = ElementWildcard.conflict
861                                                    (fElemMapType[j],
862                                                     fElemMap[j].localpart,
863                                                     fElemMap[j].uri,
864                                                     fElemMapType[k],
865                                                     fElemMap[k].localpart,
866                                                     fElemMap[k].uri,
867                                                     comparator) ? (byte)1 : (byte)0;
868                         }
869                     }
870                 }
871             }
872         }
873
874         fConflictTable = null;
875     }
876     // Unique Particle Attribution
877
878     //
879 // Private methods
880 //
881
882     /**
883      * Builds the internal DFA transition table from the given syntax tree.
884      *
885      * @param syntaxTree The syntax tree.
886      *
887      * @exception CMException Thrown if DFA cannot be built.
888      */
889     private void buildDFA(CMNode syntaxTree) throws CMException
890     {
891         //
892 // The first step we need to take is to rewrite the content model
893 // using our CMNode objects, and in the process get rid of any
894 // repetition short cuts, converting them into '*' style repetitions
895 // or getting rid of repetitions altogether.
896 //
897 // The conversions done are:
898 //
899 // x+ -> (x|x*)
900 // x? -> (x|epsilon)
901 //
902 // This is a relatively complex scenario. What is happening is that
903 // we create a top level binary node of which the special EOC value
904 // is set as the right side node. The the left side is set to the
905 // rewritten syntax tree. The source is the original content model
906 // info from the decl pool. The rewrite is done by buildSyntaxTree()
907 // which recurses the decl pool's content of the element and builds
908 // a new tree in the process.
909 //
910 // Note that, during this operation, we set each non-epsilon leaf
911 // node's DFA state position and count the number of such leafs, which
912 // is left in the fLeafCount member.
913 //
914 // The nodeTmp object is passed in just as a temp node to use during
915 // the recursion. Otherwise, we'd have to create a new node on every
916 // level of recursion, which would be piggy in Java (as is everything
917 // for that matter.)
918 //
919
920     /* MODIFIED (Jan, 2001)
921      *
922      * Use following rules.
923      * nullable(x+) := nullable(x), first(x+) := first(x), last(x+) := last(x)
924      * nullable(x?) := true, first(x?) := first(x), last(x?) := last(x)
925      *
926      * The same computation of follow as x* is applied to x+
927      *
928      * The modification drastically reduces computation time of
929      * "(a, (b, a+, (c, (b, a+)+, a+, (d, (c, (b, a+)+, a+)+, (b, a+)+, a+)+)+)+)+"
930      */
931
932         fQName.setValues(-1, fEOCIndex, fEOCIndex);
933         CMLeaf nodeEOC = new CMLeaf(fQName);
934         fHeadNode = new CMBinOp
935         (
936             XMLContentSpec.CONTENTSPECNODE_SEQ
937             , syntaxTree
938             , nodeEOC
939         );
940
941         //
942 // And handle specially the EOC node, which also must be numbered
943 // and counted as a non-epsilon leaf node. It could not be handled
944 // in the above tree build because it was created before all that
945 // started. We save the EOC position since its used during the DFA
946 // building loop.
947 //
948 fEOCPos = fLeafCount;
949         nodeEOC.setPosition(fLeafCount++);
950
951         //
952 // Ok, so now we have to iterate the new tree and do a little more
953 // work now that we know the leaf count. One thing we need to do is
954 // to calculate the first and last position sets of each node. This
955 // is cached away in each of the nodes.
956 //
957 // Along the way we also set the leaf count in each node as the
958 // maximum state count. They must know this in order to create their
959 // first/last pos sets.
960 //
961 // We also need to build an array of references to the non-epsilon
962 // leaf nodes. Since we iterate it in the same way as before, this
963 // will put them in the array according to their position values.
964 //
965 fLeafList = new CMLeaf[fLeafCount];
966         fLeafListType = new int[fLeafCount];
967         postTreeBuildInit(fHeadNode, 0);
968
969         //
970 // And, moving onward... We now need to build the follow position
971 // sets for all the nodes. So we allocate an array of state sets,
972 // one for each leaf node (i.e. each DFA position.)
973 //
974 fFollowList = new CMStateSet[fLeafCount];
975         for (int index = 0; index < fLeafCount; index++)
976             fFollowList[index] = new CMStateSet(fLeafCount);
977         calcFollowList(fHeadNode);
978         //
979 // And finally the big push... Now we build the DFA using all the
980 // states and the tree we've built up. First we set up the various
981 // data structures we are going to use while we do this.
982 //
983 // First of all we need an array of unique element names in our
984 // content model. For each transition table entry, we need a set of
985 // contiguous indices to represent the transitions for a particular
986 // input element. So we need to a zero based range of indexes that
987 // map to element types. This element map provides that mapping.
988 //
989 fElemMap = new QName[fLeafCount];
990         fElemMapType = new int[fLeafCount];
991         fElemMapSize = 0;
992         for (int outIndex = 0; outIndex < fLeafCount; outIndex++)
993         {
994             fElemMap[outIndex] = new QName();
995
996             if ( (fLeafListType[outIndex] & 0x0f) != 0 ) {
997                 if (fLeafNameTypeVector == null) {
998                     fLeafNameTypeVector = new ContentLeafNameTypeVector();
999                 }
1000            }
1001
1002            // Get the current leaf's element index
1003 final QName element = fLeafList[outIndex].getElement();
1004
1005            // See if the current leaf node's element index is in the list
1006 int inIndex = 0;
1007            for (; inIndex < fElemMapSize; inIndex++)
1008            {
1009                if (fDTD) {
1010                    if (fElemMap[inIndex].rawname == element.rawname) {
1011                        break;
1012                    }
1013                }
1014                else {
1015                    if (fElemMapType[inIndex] == fLeafListType[outIndex] &&
1016                        fElemMap[inIndex].uri == element.uri &&
1017                            fElemMap[inIndex].localpart == element.localpart)
1018                        break;
1019                }
1020            }
1021
1022            // If it was not in the list, then add it, if not the EOC node
1023 if (inIndex == fElemMapSize) {
1024                //if (fDTD) {
1025 // fElemMap[fElemMapSize].setValues(-1, element.rawname, element.rawname, -1);
1026 //}
1027 //else {
1028 fElemMap[fElemMapSize].setValues(element);
1029                //}
1030 fElemMapType[fElemMapSize] = fLeafListType[outIndex];
1031                fElemMapSize++;
1032            }
1033        }
1034        // set up the fLeafNameTypeVector object if there is one.
1035 if (fLeafNameTypeVector != null) {
1036            fLeafNameTypeVector.setValues(fElemMap, fElemMapType, fElemMapSize);
1037        }
1038
1039    /***
1040    * Optimization(Jan, 2001); We sort fLeafList according to
1041    * elemIndex which is *uniquely* associated to each leaf.
1042    * We are *assuming* that each element appears in at least one leaf.
1043    **/
1044
1045    int[] fLeafSorter = new int[fLeafCount + fElemMapSize];
1046    int fSortCount = 0;
1047
1048    for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
1049        for (int leafIndex = 0; leafIndex < fLeafCount; leafIndex++) {
1050        final QName leaf = fLeafList[leafIndex].getElement();
1051        final int leafType = fLeafListType[leafIndex];
1052        final QName element = fElemMap[elemIndex];
1053        if (fDTD) {
1054            if (leaf.rawname == element.rawname) {
1055                fLeafSorter[fSortCount++] = leafIndex;
1056            }
1057        }
1058        else if (fElemMapType[elemIndex] == fLeafListType[leafIndex] &&
1059                 leaf.uri == element.uri &&
1060                    leaf.localpart == element.localpart) {
1061                fLeafSorter[fSortCount++] = leafIndex;
1062        }
1063        }
1064        fLeafSorter[fSortCount++] = -1;
1065    }
1066
1067    /* Optimization(Jan, 2001) */
1068
1069        //
1070 // Next lets create some arrays, some that that hold transient
1071 // information during the DFA build and some that are permament.
1072 // These are kind of sticky since we cannot know how big they will
1073 // get, but we don't want to use any Java collections because of
1074 // performance.
1075 //
1076 // Basically they will probably be about fLeafCount*2 on average,
1077 // but can be as large as 2^(fLeafCount*2), worst case. So we start
1078 // with fLeafCount*4 as a middle ground. This will be very unlikely
1079 // to ever have to expand, though it if does, the overhead will be
1080 // somewhat ugly.
1081 //
1082 int curArraySize = fLeafCount * 4;
1083        CMStateSet[] statesToDo = new CMStateSet[curArraySize];
1084        fFinalStateFlags = new boolean[curArraySize];
1085        fTransTable = new int[curArraySize][];
1086
1087        //
1088 // Ok we start with the initial set as the first pos set of the
1089 // head node (which is the seq node that holds the content model
1090 // and the EOC node.)
1091 //
1092 CMStateSet setT = fHeadNode.firstPos();
1093
1094        //
1095 // Init our two state flags. Basically the unmarked state counter
1096 // is always chasing the current state counter. When it catches up,
1097 // that means we made a pass through that did not add any new states
1098 // to the lists, at which time we are done. We could have used a
1099 // expanding array of flags which we used to mark off states as we
1100 // complete them, but this is easier though less readable maybe.
1101 //
1102 int unmarkedState = 0;
1103        int curState = 0;
1104
1105        //
1106 // Init the first transition table entry, and put the initial state
1107 // into the states to do list, then bump the current state.
1108 //
1109 fTransTable[curState] = makeDefStateList();
1110        statesToDo[curState] = setT;
1111        curState++;
1112
1113        /* Optimization(Jan, 2001); This is faster for
1114         * a large content model such as, "(t001+|t002+|.... |t500+)".
1115         */
1116
1117    java.util.Hashtable JavaDoc stateTable = new java.util.Hashtable JavaDoc();
1118
1119        /* Optimization(Jan, 2001) */
1120
1121        //
1122 // Ok, almost done with the algorithm... We now enter the
1123 // loop where we go until the states done counter catches up with
1124 // the states to do counter.
1125 //
1126 while (unmarkedState < curState)
1127        {
1128            //
1129 // Get the first unmarked state out of the list of states to do.
1130 // And get the associated transition table entry.
1131 //
1132 setT = statesToDo[unmarkedState];
1133            int[] transEntry = fTransTable[unmarkedState];
1134
1135            // Mark this one final if it contains the EOC state
1136 fFinalStateFlags[unmarkedState] = setT.getBit(fEOCPos);
1137
1138            // Bump up the unmarked state count, marking this state done
1139 unmarkedState++;
1140
1141            // Loop through each possible input symbol in the element map
1142 CMStateSet newSet = null;
1143        /* Optimization(Jan, 2001) */
1144            int sorterIndex = 0;
1145        /* Optimization(Jan, 2001) */
1146            for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++)
1147            {
1148                //
1149 // Build up a set of states which is the union of all of
1150 // the follow sets of DFA positions that are in the current
1151 // state. If we gave away the new set last time through then
1152 // create a new one. Otherwise, zero out the existing one.
1153 //
1154 if (newSet == null)
1155                    newSet = new CMStateSet(fLeafCount);
1156                else
1157                    newSet.zeroBits();
1158
1159        /* Optimization(Jan, 2001) */
1160                int leafIndex = fLeafSorter[sorterIndex++];
1161
1162                while (leafIndex != -1) {
1163            // If this leaf index (DFA position) is in the current set...
1164 if (setT.getBit(leafIndex))
1165                    {
1166                        //
1167 // If this leaf is the current input symbol, then we
1168 // want to add its follow list to the set of states to
1169 // transition to from the current state.
1170 //
1171 newSet.union(fFollowList[leafIndex]);
1172                    }
1173
1174                   leafIndex = fLeafSorter[sorterIndex++];
1175    }
1176        /* Optimization(Jan, 2001) */
1177
1178                //
1179 // If this new set is not empty, then see if its in the list
1180 // of states to do. If not, then add it.
1181 //
1182 if (!newSet.isEmpty())
1183                {
1184                    //
1185 // Search the 'states to do' list to see if this new
1186 // state set is already in there.
1187 //
1188
1189        /* Optimization(Jan, 2001) */
1190        Integer JavaDoc stateObj = (Integer JavaDoc)stateTable.get(newSet);
1191        int stateIndex = (stateObj == null ? curState : stateObj.intValue());
1192        /* Optimization(Jan, 2001) */
1193
1194                    // If we did not find it, then add it
1195 if (stateIndex == curState)
1196                    {
1197                        //
1198 // Put this new state into the states to do and init
1199 // a new entry at the same index in the transition
1200 // table.
1201 //
1202 statesToDo[curState] = newSet;
1203                        fTransTable[curState] = makeDefStateList();
1204
1205        /* Optimization(Jan, 2001) */
1206                        stateTable.put(newSet, new Integer JavaDoc(curState));
1207        /* Optimization(Jan, 2001) */
1208
1209                        // We now have a new state to do so bump the count
1210 curState++;
1211
1212                        //
1213 // Null out the new set to indicate we adopted it.
1214 // This will cause the creation of a new set on the
1215 // next time around the loop.
1216 //
1217 newSet = null;
1218                    }
1219
1220                    //
1221 // Now set this state in the transition table's entry
1222 // for this element (using its index), with the DFA
1223 // state we will move to from the current state when we
1224 // see this input element.
1225 //
1226 transEntry[elemIndex] = stateIndex;
1227
1228                    // Expand the arrays if we're full
1229 if (curState == curArraySize)
1230                    {
1231                        //
1232 // Yikes, we overflowed the initial array size, so
1233 // we've got to expand all of these arrays. So adjust
1234 // up the size by 50% and allocate new arrays.
1235 //
1236 final int newSize = (int)(curArraySize * 1.5);
1237                        CMStateSet[] newToDo = new CMStateSet[newSize];
1238                        boolean[] newFinalFlags = new boolean[newSize];
1239                        int[][] newTransTable = new int[newSize][];
1240
1241                        // Copy over all of the existing content
1242 for (int expIndex = 0; expIndex < curArraySize; expIndex++)
1243                        {
1244                            newToDo[expIndex] = statesToDo[expIndex];
1245                            newFinalFlags[expIndex] = fFinalStateFlags[expIndex];
1246                            newTransTable[expIndex] = fTransTable[expIndex];
1247                        }
1248
1249                        // Store the new array size
1250 curArraySize = newSize;
1251                        statesToDo = newToDo;
1252                        fFinalStateFlags = newFinalFlags;
1253                        fTransTable = newTransTable;
1254                    }
1255                }
1256            }
1257        }
1258
1259        // Check to see if we can set the fEmptyContentIsValid flag.
1260 fEmptyContentIsValid = ((CMBinOp)fHeadNode).getLeft().isNullable();
1261
1262        //
1263 // And now we can say bye bye to the temp representation since we've
1264 // built the DFA.
1265 //
1266 if (DEBUG_VALIDATE_CONTENT)
1267            dumpTree(fHeadNode, 0);
1268        fHeadNode = null;
1269        fLeafList = null;
1270        fFollowList = null;
1271
1272    }
1273
1274    /**
1275     * Calculates the follow list of the current node.
1276     *
1277     * @param nodeCur The curent node.
1278     *
1279     * @exception CMException Thrown if follow list cannot be calculated.
1280     */
1281    private void calcFollowList(CMNode nodeCur) throws CMException
1282    {
1283        // Recurse as required
1284 if (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_CHOICE)
1285        {
1286            // Recurse only
1287 calcFollowList(((CMBinOp)nodeCur).getLeft());
1288            calcFollowList(((CMBinOp)nodeCur).getRight());
1289        }
1290         else if (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_SEQ)
1291        {
1292            // Recurse first
1293 calcFollowList(((CMBinOp)nodeCur).getLeft());
1294            calcFollowList(((CMBinOp)nodeCur).getRight());
1295
1296            //
1297 // Now handle our level. We use our left child's last pos
1298 // set and our right child's first pos set, so go ahead and
1299 // get them ahead of time.
1300 //
1301 final CMStateSet last = ((CMBinOp)nodeCur).getLeft().lastPos();
1302            final CMStateSet first = ((CMBinOp)nodeCur).getRight().firstPos();
1303
1304            //
1305 // Now, for every position which is in our left child's last set
1306 // add all of the states in our right child's first set to the
1307 // follow set for that position.
1308 //
1309 for (int index = 0; index < fLeafCount; index++)
1310            {
1311                if (last.getBit(index))
1312                    fFollowList[index].union(first);
1313            }
1314        }
1315         else if (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_ZERO_OR_MORE
1316        || nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_ONE_OR_MORE)
1317        {
1318            // Recurse first
1319 calcFollowList(((CMUniOp)nodeCur).getChild());
1320
1321            //
1322 // Now handle our level. We use our own first and last position
1323 // sets, so get them up front.
1324 //
1325 final CMStateSet first = nodeCur.firstPos();
1326            final CMStateSet last = nodeCur.lastPos();
1327
1328            //
1329 // For every position which is in our last position set, add all
1330 // of our first position states to the follow set for that
1331 // position.
1332 //
1333 for (int index = 0; index < fLeafCount; index++)
1334            {
1335                if (last.getBit(index))
1336                    fFollowList[index].union(first);
1337            }
1338        }
1339
1340        else if (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_ZERO_OR_ONE) {
1341            // Recurse only
1342 calcFollowList(((CMUniOp)nodeCur).getChild());
1343        }
1344
1345    }
1346
1347    /**
1348     * Dumps the tree of the current node to standard output.
1349     *
1350     * @param nodeCur The current node.
1351     * @param level The maximum levels to output.
1352     *
1353     * @exception CMException Thrown on error.
1354     */
1355    private void dumpTree(CMNode nodeCur, int level) throws CMException
1356    {
1357        for (int index = 0; index < level; index++)
1358            System.out.print(" ");
1359
1360        int type = nodeCur.type();
1361
1362        switch(type & 0x0f) {
1363
1364        case XMLContentSpec.CONTENTSPECNODE_CHOICE:
1365        case XMLContentSpec.CONTENTSPECNODE_SEQ:
1366        {
1367            if (type == XMLContentSpec.CONTENTSPECNODE_CHOICE)
1368                System.out.print("Choice Node ");
1369            else
1370                System.out.print("Seq Node ");
1371
1372            if (nodeCur.isNullable())
1373                System.out.print("Nullable ");
1374
1375            System.out.print("firstPos=");
1376            System.out.print(nodeCur.firstPos().toString());
1377            System.out.print(" lastPos=");
1378            System.out.println(nodeCur.lastPos().toString());
1379
1380            dumpTree(((CMBinOp)nodeCur).getLeft(), level+1);
1381            dumpTree(((CMBinOp)nodeCur).getRight(), level+1);
1382            break;
1383        }
1384        case XMLContentSpec.CONTENTSPECNODE_ZERO_OR_MORE:
1385        case XMLContentSpec.CONTENTSPECNODE_ONE_OR_MORE:
1386        case XMLContentSpec.CONTENTSPECNODE_ZERO_OR_ONE:
1387        {
1388            System.out.print("Rep Node ");
1389
1390            if (nodeCur.isNullable())
1391                System.out.print("Nullable ");
1392
1393            System.out.print("firstPos=");
1394            System.out.print(nodeCur.firstPos().toString());
1395            System.out.print(" lastPos=");
1396            System.out.println(nodeCur.lastPos().toString());
1397
1398            dumpTree(((CMUniOp)nodeCur).getChild(), level+1);
1399            break;
1400        }
1401        case XMLContentSpec.CONTENTSPECNODE_LEAF:
1402        {
1403            System.out.print
1404            (
1405                "Leaf: (pos="
1406                + ((CMLeaf)nodeCur).getPosition()
1407                + "), "
1408                + ((CMLeaf)nodeCur).getElement()
1409                + "(elemIndex="
1410                + ((CMLeaf)nodeCur).getElement()
1411                + ") "
1412            );
1413
1414            if (nodeCur.isNullable())
1415                System.out.print(" Nullable ");
1416
1417            System.out.print("firstPos=");
1418            System.out.print(nodeCur.firstPos().toString());
1419            System.out.print(" lastPos=");
1420            System.out.println(nodeCur.lastPos().toString());
1421            break;
1422        }
1423        case XMLContentSpec.CONTENTSPECNODE_ANY:
1424        case XMLContentSpec.CONTENTSPECNODE_ANY_OTHER:
1425        case XMLContentSpec.CONTENTSPECNODE_ANY_NS:
1426        {
1427            if (type == XMLContentSpec.CONTENTSPECNODE_ANY)
1428              System.out.print("Any Node: ");
1429            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_LAX)
1430              System.out.print("Any lax Node: ");
1431            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_SKIP)
1432              System.out.print("Any skip Node: ");
1433            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER)
1434              System.out.print("Any other Node: ");
1435            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER_LAX)
1436              System.out.print("Any other lax Node: ");
1437            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER_SKIP)
1438              System.out.print("Any other skip Node: ");
1439            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_NS)
1440              System.out.print("Any namespace Node: ");
1441            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_NS_LAX)
1442              System.out.print("Any namespace lax Node: ");
1443            else if (type == XMLContentSpec.CONTENTSPECNODE_ANY_NS_SKIP)
1444              System.out.print("Any namespace skip Node: ");
1445
1446            System.out.print("firstPos=");
1447            System.out.print(nodeCur.firstPos().toString());
1448            System.out.print(" lastPos=");
1449            System.out.println(nodeCur.lastPos().toString());
1450            break;
1451        }
1452        default:
1453        {
1454            throw new CMException(ImplementationMessages.VAL_NIICM);
1455        }
1456        }
1457
1458    }
1459
1460
1461    /**
1462     * -1 is used to represent bad transitions in the transition table
1463     * entry for each state. So each entry is initialized to an all -1
1464     * array. This method creates a new entry and initializes it.
1465     */
1466    private int[] makeDefStateList()
1467    {
1468        int[] retArray = new int[fElemMapSize];
1469        for (int index = 0; index < fElemMapSize; index++)
1470            retArray[index] = -1;
1471        return retArray;
1472    }
1473
1474    /** Post tree build initialization. */
1475    private int postTreeBuildInit(CMNode nodeCur, int curIndex) throws CMException
1476    {
1477        // Set the maximum states on this node
1478 nodeCur.setMaxStates(fLeafCount);
1479
1480        // Recurse as required
1481 if ((nodeCur.type() & 0x0f) == XMLContentSpec.CONTENTSPECNODE_ANY ||
1482            (nodeCur.type() & 0x0f) == XMLContentSpec.CONTENTSPECNODE_ANY_NS ||
1483            (nodeCur.type() & 0x0f) == XMLContentSpec.CONTENTSPECNODE_ANY_OTHER) {
1484            // REVISIT: Don't waste these structures.
1485 QName qname = new QName(-1, -1, -1, ((CMAny)nodeCur).getURI());
1486            fLeafList[curIndex] = new CMLeaf(qname, ((CMAny)nodeCur).getPosition());
1487            fLeafListType[curIndex] = nodeCur.type();
1488            curIndex++;
1489        }
1490        else if ((nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_CHOICE)
1491        || (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_SEQ))
1492        {
1493            curIndex = postTreeBuildInit(((CMBinOp)nodeCur).getLeft(), curIndex);
1494            curIndex = postTreeBuildInit(((CMBinOp)nodeCur).getRight(), curIndex);
1495        }
1496         else if (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_ZERO_OR_MORE
1497         || nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_ONE_OR_MORE
1498         || nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_ZERO_OR_ONE)
1499        {
1500            curIndex = postTreeBuildInit(((CMUniOp)nodeCur).getChild(), curIndex);
1501        }
1502         else if (nodeCur.type() == XMLContentSpec.CONTENTSPECNODE_LEAF)
1503        {
1504            //
1505 // Put this node in the leaf list at the current index if its
1506 // a non-epsilon leaf.
1507 //
1508 final QName node = ((CMLeaf)nodeCur).getElement();
1509            if (node.localpart != fEpsilonIndex) {
1510                fLeafList[curIndex] = (CMLeaf)nodeCur;
1511                fLeafListType[curIndex] = XMLContentSpec.CONTENTSPECNODE_LEAF;
1512                curIndex++;
1513            }
1514        }
1515         else
1516        {
1517            throw new CMException(ImplementationMessages.VAL_NIICM);
1518        }
1519        return curIndex;
1520    }
1521
1522
1523} // class DFAContentModel
1524
Popular Tags