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