1 /*
   2  * Copyright (c) 2006, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * @LastModified: Oct 2017
   4  */
   5 /*
   6  * Licensed to the Apache Software Foundation (ASF) under one or more
   7  * contributor license agreements.  See the NOTICE file distributed with
   8  * this work for additional information regarding copyright ownership.
   9  * The ASF licenses this file to You under the Apache License, Version 2.0
  10  * (the "License"); you may not use this file except in compliance with
  11  * the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  */
  21 
  22 package com.sun.org.apache.xerces.internal.impl.xs.models;
  23 
  24 import com.sun.org.apache.xerces.internal.impl.dtd.models.CMNode;
  25 import com.sun.org.apache.xerces.internal.impl.dtd.models.CMStateSet;
  26 import com.sun.org.apache.xerces.internal.impl.xs.SchemaSymbols;
  27 import com.sun.org.apache.xerces.internal.impl.xs.SubstitutionGroupHandler;
  28 import com.sun.org.apache.xerces.internal.impl.xs.XMLSchemaException;
  29 import com.sun.org.apache.xerces.internal.impl.xs.XSConstraints;
  30 import com.sun.org.apache.xerces.internal.impl.xs.XSElementDecl;
  31 import com.sun.org.apache.xerces.internal.impl.xs.XSModelGroupImpl;
  32 import com.sun.org.apache.xerces.internal.impl.xs.XSParticleDecl;
  33 import com.sun.org.apache.xerces.internal.impl.xs.XSWildcardDecl;
  34 import com.sun.org.apache.xerces.internal.xni.QName;
  35 import java.util.ArrayList;
  36 import java.util.HashMap;
  37 import java.util.List;
  38 import java.util.Map;
  39 
  40 /**
  41  * DFAContentModel is the implementation of XSCMValidator that does
  42  * all of the non-trivial element content validation. This class does
  43  * the conversion from the regular expression to the DFA that
  44  * it then uses in its validation algorithm.
  45  *
  46  * @xerces.internal
  47  *
  48  * @author Neil Graham, IBM
  49  */
  50 public class XSDFACM
  51     implements XSCMValidator {
  52 
  53     //
  54     // Constants
  55     //
  56     private static final boolean DEBUG = false;
  57 
  58     // special strings
  59 
  60     // debugging
  61 
  62     /** Set to true to debug content model validation. */
  63     private static final boolean DEBUG_VALIDATE_CONTENT = false;
  64 
  65     //
  66     // Data
  67     //
  68 
  69     /**
  70      * This is the map of unique input symbol elements to indices into
  71      * each state's per-input symbol transition table entry. This is part
  72      * of the built DFA information that must be kept around to do the
  73      * actual validation.  Note tat since either XSElementDecl or XSParticleDecl object
  74      * can live here, we've got to use an Object.
  75      */
  76     private Object fElemMap[] = null;
  77 
  78     /**
  79      * This is a map of whether the element map contains information
  80      * related to ANY models.
  81      */
  82     private int fElemMapType[] = null;
  83 
  84     /**
  85      * id of the unique input symbol
  86      */
  87     private int fElemMapId[] = null;
  88 
  89     /** The element map size. */
  90     private int fElemMapSize = 0;
  91 
  92     /**
  93      * This is an array of booleans, one per state (there are
  94      * fTransTableSize states in the DFA) that indicates whether that
  95      * state is a final state.
  96      */
  97     private boolean fFinalStateFlags[] = null;
  98 
  99     /**
 100      * The list of follow positions for each NFA position (i.e. for each
 101      * non-epsilon leaf node.) This is only used during the building of
 102      * the DFA, and is let go afterwards.
 103      */
 104     private CMStateSet fFollowList[] = null;
 105 
 106     /**
 107      * This is the head node of our intermediate representation. It is
 108      * only non-null during the building of the DFA (just so that it
 109      * does not have to be passed all around.) Once the DFA is built,
 110      * this is no longer required so its nulled out.
 111      */
 112     private CMNode fHeadNode = null;
 113 
 114     /**
 115      * The count of leaf nodes. This is an important number that set some
 116      * limits on the sizes of data structures in the DFA process.
 117      */
 118     private int fLeafCount = 0;
 119 
 120     /**
 121      * An array of non-epsilon leaf nodes, which is used during the DFA
 122      * build operation, then dropped.
 123      */
 124     private XSCMLeaf fLeafList[] = null;
 125 
 126     /** Array mapping ANY types to the leaf list. */
 127     private int fLeafListType[] = null;
 128 
 129     /**
 130      * This is the transition table that is the main by product of all
 131      * of the effort here. It is an array of arrays of ints. The first
 132      * dimension is the number of states we end up with in the DFA. The
 133      * second dimensions is the number of unique elements in the content
 134      * model (fElemMapSize). Each entry in the second dimension indicates
 135      * the new state given that input for the first dimension's start
 136      * state.
 137      * <p>
 138      * The fElemMap array handles mapping from element indexes to
 139      * positions in the second dimension of the transition table.
 140      */
 141     private int fTransTable[][] = null;
 142 
 143     /**
 144      * Array containing occurence information for looping states
 145      * which use counters to check minOccurs/maxOccurs.
 146      */
 147     private Occurence [] fCountingStates = null;
 148     static final class Occurence {
 149         final int minOccurs;
 150         final int maxOccurs;
 151         final int elemIndex;
 152         public Occurence (XSCMRepeatingLeaf leaf, int elemIndex) {
 153             minOccurs = leaf.getMinOccurs();
 154             maxOccurs = leaf.getMaxOccurs();
 155             this.elemIndex = elemIndex;
 156         }
 157         public String toString() {
 158             return "minOccurs=" + minOccurs
 159                 + ";maxOccurs=" +
 160                 ((maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED)
 161                         ? Integer.toString(maxOccurs) : "unbounded");
 162         }
 163     }
 164 
 165     /**
 166      * The number of valid entries in the transition table, and in the other
 167      * related tables such as fFinalStateFlags.
 168      */
 169     private int fTransTableSize = 0;
 170 
 171     private boolean fIsCompactedForUPA;
 172 
 173     /**
 174      * Array of counters for all the for elements (or wildcards)
 175      * of the form a{n,m} where n > 1 and m <= unbounded. Used
 176      * to count the a's to later check against n and m. Counter
 177      * set to -1 if element (or wildcard) not optimized by
 178      * constant space algorithm.
 179      */
 180     private int fElemMapCounter[];
 181 
 182     /**
 183      * Array of lower bounds for all the for elements (or wildcards)
 184      * of the form a{n,m} where n > 1 and m <= unbounded. This array
 185      * stores the n's for those elements (or wildcards) for which
 186      * the constant space algorithm applies (or -1 otherwise).
 187      */
 188     private int fElemMapCounterLowerBound[];
 189 
 190     /**
 191      * Array of upper bounds for all the for elements (or wildcards)
 192      * of the form a{n,m} where n > 1 and m <= unbounded. This array
 193      * stores the n's for those elements (or wildcards) for which
 194      * the constant space algorithm applies, or -1 if algorithm does
 195      * not apply or m = unbounded.
 196      */
 197     private int fElemMapCounterUpperBound[];   // -1 if no upper bound
 198 
 199     // temp variables
 200 
 201     //
 202     // Constructors
 203     //
 204 
 205     /**
 206      * Constructs a DFA content model.
 207      *
 208      * @param syntaxTree    The syntax tree of the content model.
 209      * @param leafCount     The number of leaves.
 210      *
 211      * @exception RuntimeException Thrown if DFA can't be built.
 212      */
 213 
 214    public XSDFACM(CMNode syntaxTree, int leafCount) {
 215 
 216         // Store away our index and pools in members
 217         fLeafCount = leafCount;
 218         fIsCompactedForUPA = syntaxTree.isCompactedForUPA();
 219 
 220         //
 221         //  Create some string pool indexes that represent the names of some
 222         //  magical nodes in the syntax tree.
 223         //  (already done in static initialization...
 224         //
 225 
 226         //
 227         //  Ok, so lets grind through the building of the DFA. This method
 228         //  handles the high level logic of the algorithm, but it uses a
 229         //  number of helper classes to do its thing.
 230         //
 231         //  In order to avoid having hundreds of references to the error and
 232         //  string handlers around, this guy and all of his helper classes
 233         //  just throw a simple exception and we then pass it along.
 234         //
 235 
 236         if(DEBUG_VALIDATE_CONTENT) {
 237             XSDFACM.time -= System.currentTimeMillis();
 238         }
 239 
 240         buildDFA(syntaxTree);
 241 
 242         if(DEBUG_VALIDATE_CONTENT) {
 243             XSDFACM.time += System.currentTimeMillis();
 244             System.out.println("DFA build: " + XSDFACM.time + "ms");
 245         }
 246     }
 247 
 248     private static long time = 0;
 249 
 250     //
 251     // XSCMValidator methods
 252     //
 253 
 254     /**
 255      * check whether the given state is one of the final states
 256      *
 257      * @param state       the state to check
 258      *
 259      * @return whether it's a final state
 260      */
 261     public boolean isFinalState (int state) {
 262         return (state < 0)? false :
 263             fFinalStateFlags[state];
 264     }
 265 
 266     /**
 267      * one transition only
 268      *
 269      * @param curElem The current element's QName
 270      * @param state stack to store the previous state
 271      * @param subGroupHandler the substitution group handler
 272      *
 273      * @return  null if transition is invalid; otherwise the Object corresponding to the
 274      *      XSElementDecl or XSWildcardDecl identified.  Also, the
 275      *      state array will be modified to include the new state; this so that the validator can
 276      *      store it away.
 277      *
 278      * @exception RuntimeException thrown on error
 279      */
 280     public Object oneTransition(QName curElem, int[] state, SubstitutionGroupHandler subGroupHandler) {
 281         int curState = state[0];
 282 
 283         if(curState == XSCMValidator.FIRST_ERROR || curState == XSCMValidator.SUBSEQUENT_ERROR) {
 284             // there was an error last time; so just go find correct Object in fElemmMap.
 285             // ... after resetting state[0].
 286             if(curState == XSCMValidator.FIRST_ERROR)
 287                 state[0] = XSCMValidator.SUBSEQUENT_ERROR;
 288 
 289             return findMatchingDecl(curElem, subGroupHandler);
 290         }
 291 
 292         int nextState = 0;
 293         int elemIndex = 0;
 294         Object matchingDecl = null;
 295 
 296         for (; elemIndex < fElemMapSize; elemIndex++) {
 297             nextState = fTransTable[curState][elemIndex];
 298             if (nextState == -1)
 299                 continue;
 300             int type = fElemMapType[elemIndex] ;
 301             if (type == XSParticleDecl.PARTICLE_ELEMENT) {
 302                 matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);
 303                 if (matchingDecl != null) {
 304                     // Increment counter if constant space algorithm applies
 305                     if (fElemMapCounter[elemIndex] >= 0) {
 306                         fElemMapCounter[elemIndex]++;
 307                     }
 308                     break;
 309                 }
 310             }
 311             else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
 312                 if (((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {
 313                     matchingDecl = fElemMap[elemIndex];
 314                     // Increment counter if constant space algorithm applies
 315                     if (fElemMapCounter[elemIndex] >= 0) {
 316                         fElemMapCounter[elemIndex]++;
 317                     }
 318                     break;
 319                 }
 320             }
 321         }
 322 
 323         // if we still can't find a match, set the state to first_error
 324         // and return null
 325         if (elemIndex == fElemMapSize) {
 326             state[1] = state[0];
 327             state[0] = XSCMValidator.FIRST_ERROR;
 328             return findMatchingDecl(curElem, subGroupHandler);
 329         }
 330 
 331         if (fCountingStates != null) {
 332             Occurence o = fCountingStates[curState];
 333             if (o != null) {
 334                 if (curState == nextState) {
 335                     if (++state[2] > o.maxOccurs &&
 336                         o.maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED) {
 337                         // It's likely that we looped too many times on the current state
 338                         // however it's possible that we actually matched another particle
 339                         // which allows the same name.
 340                         //
 341                         // Consider:
 342                         //
 343                         // <xs:sequence>
 344                         //  <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>
 345                         //  <xs:element name="foo" type="xs:string" fixed="bar"/>
 346                         // </xs:sequence>
 347                         //
 348                         // and
 349                         //
 350                         // <xs:sequence>
 351                         //  <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>
 352                         //  <xs:any namespace="##any" processContents="skip"/>
 353                         // </xs:sequence>
 354                         //
 355                         // In the DFA there will be two transitions from the current state which
 356                         // allow "foo". Note that this is not a UPA violation. The ambiguity of which
 357                         // transition to take is resolved by the current value of the counter. Since
 358                         // we've already seen enough instances of the first "foo" perhaps there is
 359                         // another element declaration or wildcard deeper in the element map which
 360                         // matches.
 361                         return findMatchingDecl(curElem, state, subGroupHandler, elemIndex);
 362                     }
 363                 }
 364                 else if (state[2] < o.minOccurs) {
 365                     // not enough loops on the current state.
 366                     state[1] = state[0];
 367                     state[0] = XSCMValidator.FIRST_ERROR;
 368                     return findMatchingDecl(curElem, subGroupHandler);
 369                 }
 370                 else {
 371                     // Exiting a counting state. If we're entering a new
 372                     // counting state, reset the counter.
 373                     o = fCountingStates[nextState];
 374                     if (o != null) {
 375                         state[2] = (elemIndex == o.elemIndex) ? 1 : 0;
 376                     }
 377                 }
 378             }
 379             else {
 380                 o = fCountingStates[nextState];
 381                 if (o != null) {
 382                     // Entering a new counting state. Reset the counter.
 383                     // If we've already seen one instance of the looping
 384                     // particle set the counter to 1, otherwise set it
 385                     // to 0.
 386                     state[2] = (elemIndex == o.elemIndex) ? 1 : 0;
 387                 }
 388             }
 389         }
 390 
 391         state[0] = nextState;
 392         return matchingDecl;
 393     } // oneTransition(QName, int[], SubstitutionGroupHandler):  Object
 394 
 395     Object findMatchingDecl(QName curElem, SubstitutionGroupHandler subGroupHandler) {
 396         Object matchingDecl = null;
 397 
 398         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
 399             int type = fElemMapType[elemIndex] ;
 400             if (type == XSParticleDecl.PARTICLE_ELEMENT) {
 401                 matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);
 402                 if (matchingDecl != null) {
 403                     return matchingDecl;
 404                 }
 405             }
 406             else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
 407                 if(((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri))
 408                     return fElemMap[elemIndex];
 409             }
 410         }
 411 
 412         return null;
 413     } // findMatchingDecl(QName, SubstitutionGroupHandler): Object
 414 
 415     Object findMatchingDecl(QName curElem, int[] state, SubstitutionGroupHandler subGroupHandler, int elemIndex) {
 416 
 417         int curState = state[0];
 418         int nextState = 0;
 419         Object matchingDecl = null;
 420 
 421         while (++elemIndex < fElemMapSize) {
 422             nextState = fTransTable[curState][elemIndex];
 423             if (nextState == -1)
 424                 continue;
 425             int type = fElemMapType[elemIndex] ;
 426             if (type == XSParticleDecl.PARTICLE_ELEMENT) {
 427                 matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);
 428                 if (matchingDecl != null) {
 429                     break;
 430                 }
 431             }
 432             else if (type == XSParticleDecl.PARTICLE_WILDCARD) {
 433                 if (((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {
 434                     matchingDecl = fElemMap[elemIndex];
 435                     break;
 436                 }
 437             }
 438         }
 439 
 440         // if we still can't find a match, set the state to FIRST_ERROR and return null
 441         if (elemIndex == fElemMapSize) {
 442             state[1] = state[0];
 443             state[0] = XSCMValidator.FIRST_ERROR;
 444             return findMatchingDecl(curElem, subGroupHandler);
 445         }
 446 
 447         // if we found a match, set the next state and reset the
 448         // counter if the next state is a counting state.
 449         state[0] = nextState;
 450         final Occurence o = fCountingStates[nextState];
 451         if (o != null) {
 452             state[2] = (elemIndex == o.elemIndex) ? 1 : 0;
 453         }
 454         return matchingDecl;
 455     } // findMatchingDecl(QName, int[], SubstitutionGroupHandler, int): Object
 456 
 457     // This method returns the start states of the content model.
 458     public int[] startContentModel() {
 459         // Clear all constant space algorithm counters in use
 460         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
 461             if (fElemMapCounter[elemIndex] != -1) {
 462                 fElemMapCounter[elemIndex] = 0;
 463             }
 464         }
 465         // [0] : the current state
 466         // [1] : if [0] is an error state then the
 467         //       last valid state before the error
 468         // [2] : occurence counter for counting states
 469         return new int [3];
 470     } // startContentModel():int[]
 471 
 472     // this method returns whether the last state was a valid final state
 473     public boolean endContentModel(int[] state) {
 474         final int curState = state[0];
 475         if (fFinalStateFlags[curState]) {
 476             if (fCountingStates != null) {
 477                 Occurence o = fCountingStates[curState];
 478                 if (o != null && state[2] < o.minOccurs) {
 479                     // not enough loops on the current state to be considered final.
 480                     return false;
 481                 }
 482             }
 483             return true;
 484         }
 485         return false;
 486     } // endContentModel(int[]):  boolean
 487 
 488     // Killed off whatCanGoHere; we may need it for DOM canInsert(...) etc.,
 489     // but we can put it back later.
 490 
 491     //
 492     // Private methods
 493     //
 494 
 495     /**
 496      * Builds the internal DFA transition table from the given syntax tree.
 497      *
 498      * @param syntaxTree The syntax tree.
 499      *
 500      * @exception RuntimeException Thrown if DFA cannot be built.
 501      */
 502     private void buildDFA(CMNode syntaxTree) {
 503         //
 504         //  The first step we need to take is to rewrite the content model
 505         //  using our CMNode objects, and in the process get rid of any
 506         //  repetition short cuts, converting them into '*' style repetitions
 507         //  or getting rid of repetitions altogether.
 508         //
 509         //  The conversions done are:
 510         //
 511         //  x+ -> (x|x*)
 512         //  x? -> (x|epsilon)
 513         //
 514         //  This is a relatively complex scenario. What is happening is that
 515         //  we create a top level binary node of which the special EOC value
 516         //  is set as the right side node. The the left side is set to the
 517         //  rewritten syntax tree. The source is the original content model
 518         //  info from the decl pool. The rewrite is done by buildSyntaxTree()
 519         //  which recurses the decl pool's content of the element and builds
 520         //  a new tree in the process.
 521         //
 522         //  Note that, during this operation, we set each non-epsilon leaf
 523         //  node's DFA state position and count the number of such leafs, which
 524         //  is left in the fLeafCount member.
 525         //
 526         //  The nodeTmp object is passed in just as a temp node to use during
 527         //  the recursion. Otherwise, we'd have to create a new node on every
 528         //  level of recursion, which would be piggy in Java (as is everything
 529         //  for that matter.)
 530         //
 531 
 532         /* MODIFIED (Jan, 2001)
 533          *
 534          * Use following rules.
 535          *   nullable(x+) := nullable(x), first(x+) := first(x),  last(x+) := last(x)
 536          *   nullable(x?) := true, first(x?) := first(x),  last(x?) := last(x)
 537          *
 538          * The same computation of follow as x* is applied to x+
 539          *
 540          * The modification drastically reduces computation time of
 541          * "(a, (b, a+, (c, (b, a+)+, a+, (d,  (c, (b, a+)+, a+)+, (b, a+)+, a+)+)+)+)+"
 542          */
 543 
 544         //
 545         //  And handle specially the EOC node, which also must be numbered
 546         //  and counted as a non-epsilon leaf node. It could not be handled
 547         //  in the above tree build because it was created before all that
 548         //  started. We save the EOC position since its used during the DFA
 549         //  building loop.
 550         //
 551         int EOCPos = fLeafCount;
 552         XSCMLeaf nodeEOC = new XSCMLeaf(XSParticleDecl.PARTICLE_ELEMENT, null, -1, fLeafCount++);
 553         fHeadNode = new XSCMBinOp(
 554             XSModelGroupImpl.MODELGROUP_SEQUENCE,
 555             syntaxTree,
 556             nodeEOC
 557         );
 558 
 559         //
 560         //  Ok, so now we have to iterate the new tree and do a little more
 561         //  work now that we know the leaf count. One thing we need to do is
 562         //  to calculate the first and last position sets of each node. This
 563         //  is cached away in each of the nodes.
 564         //
 565         //  Along the way we also set the leaf count in each node as the
 566         //  maximum state count. They must know this in order to create their
 567         //  first/last pos sets.
 568         //
 569         //  We also need to build an array of references to the non-epsilon
 570         //  leaf nodes. Since we iterate it in the same way as before, this
 571         //  will put them in the array according to their position values.
 572         //
 573         fLeafList = new XSCMLeaf[fLeafCount];
 574         fLeafListType = new int[fLeafCount];
 575         postTreeBuildInit(fHeadNode);
 576 
 577         //
 578         //  And, moving onward... We now need to build the follow position
 579         //  sets for all the nodes. So we allocate an array of state sets,
 580         //  one for each leaf node (i.e. each DFA position.)
 581         //
 582         fFollowList = new CMStateSet[fLeafCount];
 583         for (int index = 0; index < fLeafCount; index++)
 584             fFollowList[index] = new CMStateSet(fLeafCount);
 585         calcFollowList(fHeadNode);
 586         //
 587         //  And finally the big push... Now we build the DFA using all the
 588         //  states and the tree we've built up. First we set up the various
 589         //  data structures we are going to use while we do this.
 590         //
 591         //  First of all we need an array of unique element names in our
 592         //  content model. For each transition table entry, we need a set of
 593         //  contiguous indices to represent the transitions for a particular
 594         //  input element. So we need to a zero based range of indexes that
 595         //  map to element types. This element map provides that mapping.
 596         //
 597         fElemMap = new Object[fLeafCount];
 598         fElemMapType = new int[fLeafCount];
 599         fElemMapId = new int[fLeafCount];
 600 
 601         fElemMapCounter = new int[fLeafCount];
 602         fElemMapCounterLowerBound = new int[fLeafCount];
 603         fElemMapCounterUpperBound = new int[fLeafCount];
 604 
 605         fElemMapSize = 0;
 606         Occurence [] elemOccurenceMap = null;
 607 
 608         for (int outIndex = 0; outIndex < fLeafCount; outIndex++) {
 609             // optimization from Henry Zongaro:
 610             //fElemMap[outIndex] = new Object ();
 611             fElemMap[outIndex] = null;
 612 
 613             int inIndex = 0;
 614             final int id = fLeafList[outIndex].getParticleId();
 615             for (; inIndex < fElemMapSize; inIndex++) {
 616                 if (id == fElemMapId[inIndex])
 617                     break;
 618             }
 619 
 620             // If it was not in the list, then add it, if not the EOC node
 621             if (inIndex == fElemMapSize) {
 622                 XSCMLeaf leaf = fLeafList[outIndex];
 623                 fElemMap[fElemMapSize] = leaf.getLeaf();
 624                 if (leaf instanceof XSCMRepeatingLeaf) {
 625                     if (elemOccurenceMap == null) {
 626                         elemOccurenceMap = new Occurence[fLeafCount];
 627                     }
 628                     elemOccurenceMap[fElemMapSize] = new Occurence((XSCMRepeatingLeaf) leaf, fElemMapSize);
 629                 }
 630 
 631                 fElemMapType[fElemMapSize] = fLeafListType[outIndex];
 632                 fElemMapId[fElemMapSize] = id;
 633 
 634                 // Init counters and bounds for a{n,m} algorithm
 635                 int[] bounds = (int[]) leaf.getUserData();
 636                 if (bounds != null) {
 637                     fElemMapCounter[fElemMapSize] = 0;
 638                     fElemMapCounterLowerBound[fElemMapSize] = bounds[0];
 639                     fElemMapCounterUpperBound[fElemMapSize] = bounds[1];
 640                 } else {
 641                     fElemMapCounter[fElemMapSize] = -1;
 642                     fElemMapCounterLowerBound[fElemMapSize] = -1;
 643                     fElemMapCounterUpperBound[fElemMapSize] = -1;
 644                 }
 645 
 646                 fElemMapSize++;
 647             }
 648         }
 649 
 650         // the last entry in the element map must be the EOC element.
 651         // remove it from the map.
 652         if (DEBUG) {
 653             if (fElemMapId[fElemMapSize-1] != -1)
 654                 System.err.println("interal error in DFA: last element is not EOC.");
 655         }
 656         fElemMapSize--;
 657 
 658         /***
 659          * Optimization(Jan, 2001); We sort fLeafList according to
 660          * elemIndex which is *uniquely* associated to each leaf.
 661          * We are *assuming* that each element appears in at least one leaf.
 662          **/
 663 
 664         int[] fLeafSorter = new int[fLeafCount + fElemMapSize];
 665         int fSortCount = 0;
 666 
 667         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
 668             final int id = fElemMapId[elemIndex];
 669             for (int leafIndex = 0; leafIndex < fLeafCount; leafIndex++) {
 670                 if (id == fLeafList[leafIndex].getParticleId())
 671                     fLeafSorter[fSortCount++] = leafIndex;
 672             }
 673             fLeafSorter[fSortCount++] = -1;
 674         }
 675 
 676         /* Optimization(Jan, 2001) */
 677 
 678         //
 679         //  Next lets create some arrays, some that hold transient
 680         //  information during the DFA build and some that are permament.
 681         //  These are kind of sticky since we cannot know how big they will
 682         //  get, but we don't want to use any Java collections because of
 683         //  performance.
 684         //
 685         //  Basically they will probably be about fLeafCount*2 on average,
 686         //  but can be as large as 2^(fLeafCount*2), worst case. So we start
 687         //  with fLeafCount*4 as a middle ground. This will be very unlikely
 688         //  to ever have to expand, though it if does, the overhead will be
 689         //  somewhat ugly.
 690         //
 691         int curArraySize = fLeafCount * 4;
 692         CMStateSet[] statesToDo = new CMStateSet[curArraySize];
 693         fFinalStateFlags = new boolean[curArraySize];
 694         fTransTable = new int[curArraySize][];
 695 
 696         //
 697         //  Ok we start with the initial set as the first pos set of the
 698         //  head node (which is the seq node that holds the content model
 699         //  and the EOC node.)
 700         //
 701         CMStateSet setT = fHeadNode.firstPos();
 702 
 703         //
 704         //  Init our two state flags. Basically the unmarked state counter
 705         //  is always chasing the current state counter. When it catches up,
 706         //  that means we made a pass through that did not add any new states
 707         //  to the lists, at which time we are done. We could have used a
 708         //  expanding array of flags which we used to mark off states as we
 709         //  complete them, but this is easier though less readable maybe.
 710         //
 711         int unmarkedState = 0;
 712         int curState = 0;
 713 
 714         //
 715         //  Init the first transition table entry, and put the initial state
 716         //  into the states to do list, then bump the current state.
 717         //
 718         fTransTable[curState] = makeDefStateList();
 719         statesToDo[curState] = setT;
 720         curState++;
 721 
 722         /* Optimization(Jan, 2001); This is faster for
 723          * a large content model such as, "(t001+|t002+|.... |t500+)".
 724          */
 725 
 726         Map<CMStateSet, Integer> stateTable = new HashMap<>();
 727 
 728         /* Optimization(Jan, 2001) */
 729 
 730         //
 731         //  Ok, almost done with the algorithm... We now enter the
 732         //  loop where we go until the states done counter catches up with
 733         //  the states to do counter.
 734         //
 735         while (unmarkedState < curState) {
 736             //
 737             //  Get the first unmarked state out of the list of states to do.
 738             //  And get the associated transition table entry.
 739             //
 740             setT = statesToDo[unmarkedState];
 741             int[] transEntry = fTransTable[unmarkedState];
 742 
 743             // Mark this one final if it contains the EOC state
 744             fFinalStateFlags[unmarkedState] = setT.getBit(EOCPos);
 745 
 746             // Bump up the unmarked state count, marking this state done
 747             unmarkedState++;
 748 
 749             // Loop through each possible input symbol in the element map
 750             CMStateSet newSet = null;
 751             /* Optimization(Jan, 2001) */
 752             int sorterIndex = 0;
 753             /* Optimization(Jan, 2001) */
 754             for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
 755                 //
 756                 //  Build up a set of states which is the union of all of
 757                 //  the follow sets of DFA positions that are in the current
 758                 //  state. If we gave away the new set last time through then
 759                 //  create a new one. Otherwise, zero out the existing one.
 760                 //
 761                 if (newSet == null)
 762                     newSet = new CMStateSet(fLeafCount);
 763                 else
 764                     newSet.zeroBits();
 765 
 766                 /* Optimization(Jan, 2001) */
 767                 int leafIndex = fLeafSorter[sorterIndex++];
 768 
 769                 while (leafIndex != -1) {
 770                     // If this leaf index (DFA position) is in the current set...
 771                     if (setT.getBit(leafIndex)) {
 772                         //
 773                         //  If this leaf is the current input symbol, then we
 774                         //  want to add its follow list to the set of states to
 775                         //  transition to from the current state.
 776                         //
 777                         newSet.union(fFollowList[leafIndex]);
 778                     }
 779 
 780                    leafIndex = fLeafSorter[sorterIndex++];
 781                 }
 782                 /* Optimization(Jan, 2001) */
 783 
 784                 //
 785                 //  If this new set is not empty, then see if its in the list
 786                 //  of states to do. If not, then add it.
 787                 //
 788                 if (!newSet.isEmpty()) {
 789                     //
 790                     //  Search the 'states to do' list to see if this new
 791                     //  state set is already in there.
 792                     //
 793 
 794                     /* Optimization(Jan, 2001) */
 795                     Integer stateObj = stateTable.get(newSet);
 796                     int stateIndex = (stateObj == null ? curState : stateObj);
 797                     /* Optimization(Jan, 2001) */
 798 
 799                     // If we did not find it, then add it
 800                     if (stateIndex == curState) {
 801                         //
 802                         //  Put this new state into the states to do and init
 803                         //  a new entry at the same index in the transition
 804                         //  table.
 805                         //
 806                         statesToDo[curState] = newSet;
 807                         fTransTable[curState] = makeDefStateList();
 808 
 809                         /* Optimization(Jan, 2001) */
 810                         stateTable.put(newSet, curState);
 811                         /* Optimization(Jan, 2001) */
 812 
 813                         // We now have a new state to do so bump the count
 814                         curState++;
 815 
 816                         //
 817                         //  Null out the new set to indicate we adopted it.
 818                         //  This will cause the creation of a new set on the
 819                         //  next time around the loop.
 820                         //
 821                         newSet = null;
 822                     }
 823 
 824                     //
 825                     //  Now set this state in the transition table's entry
 826                     //  for this element (using its index), with the DFA
 827                     //  state we will move to from the current state when we
 828                     //  see this input element.
 829                     //
 830                     transEntry[elemIndex] = stateIndex;
 831 
 832                     // Expand the arrays if we're full
 833                     if (curState == curArraySize) {
 834                         //
 835                         //  Yikes, we overflowed the initial array size, so
 836                         //  we've got to expand all of these arrays. So adjust
 837                         //  up the size by 50% and allocate new arrays.
 838                         //
 839                         final int newSize = (int)(curArraySize * 1.5);
 840                         CMStateSet[] newToDo = new CMStateSet[newSize];
 841                         boolean[] newFinalFlags = new boolean[newSize];
 842                         int[][] newTransTable = new int[newSize][];
 843 
 844                         // Copy over all of the existing content
 845                         System.arraycopy(statesToDo, 0, newToDo, 0, curArraySize);
 846                         System.arraycopy(fFinalStateFlags, 0, newFinalFlags, 0, curArraySize);
 847                         System.arraycopy(fTransTable, 0, newTransTable, 0, curArraySize);
 848 
 849                         // Store the new array size
 850                         curArraySize = newSize;
 851                         statesToDo = newToDo;
 852                         fFinalStateFlags = newFinalFlags;
 853                         fTransTable = newTransTable;
 854                     }
 855                 }
 856             }
 857         }
 858 
 859         //
 860         // Fill in the occurence information for each looping state
 861         // if we're using counters.
 862         //
 863         if (elemOccurenceMap != null) {
 864             fCountingStates = new Occurence[curState];
 865             for (int i = 0; i < curState; ++i) {
 866                 int [] transitions = fTransTable[i];
 867                 for (int j = 0; j < transitions.length; ++j) {
 868                     if (i == transitions[j]) {
 869                         fCountingStates[i] = elemOccurenceMap[j];
 870                         break;
 871                     }
 872                 }
 873             }
 874         }
 875 
 876         //
 877         //  And now we can say bye bye to the temp representation since we've
 878         //  built the DFA.
 879         //
 880         if (DEBUG_VALIDATE_CONTENT)
 881             dumpTree(fHeadNode, 0);
 882         fHeadNode = null;
 883         fLeafList = null;
 884         fFollowList = null;
 885         fLeafListType = null;
 886         fElemMapId = null;
 887     }
 888 
 889     /**
 890      * Calculates the follow list of the current node.
 891      *
 892      * @param nodeCur The curent node.
 893      *
 894      * @exception RuntimeException Thrown if follow list cannot be calculated.
 895      */
 896     private void calcFollowList(CMNode nodeCur) {
 897         // Recurse as required
 898         if (nodeCur.type() == XSModelGroupImpl.MODELGROUP_CHOICE) {
 899             // Recurse only
 900             calcFollowList(((XSCMBinOp)nodeCur).getLeft());
 901             calcFollowList(((XSCMBinOp)nodeCur).getRight());
 902         }
 903          else if (nodeCur.type() == XSModelGroupImpl.MODELGROUP_SEQUENCE) {
 904             // Recurse first
 905             calcFollowList(((XSCMBinOp)nodeCur).getLeft());
 906             calcFollowList(((XSCMBinOp)nodeCur).getRight());
 907 
 908             //
 909             //  Now handle our level. We use our left child's last pos
 910             //  set and our right child's first pos set, so go ahead and
 911             //  get them ahead of time.
 912             //
 913             final CMStateSet last  = ((XSCMBinOp)nodeCur).getLeft().lastPos();
 914             final CMStateSet first = ((XSCMBinOp)nodeCur).getRight().firstPos();
 915 
 916             //
 917             //  Now, for every position which is in our left child's last set
 918             //  add all of the states in our right child's first set to the
 919             //  follow set for that position.
 920             //
 921             for (int index = 0; index < fLeafCount; index++) {
 922                 if (last.getBit(index))
 923                     fFollowList[index].union(first);
 924             }
 925         }
 926          else if (nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_MORE
 927         || nodeCur.type() == XSParticleDecl.PARTICLE_ONE_OR_MORE) {
 928             // Recurse first
 929             calcFollowList(((XSCMUniOp)nodeCur).getChild());
 930 
 931             //
 932             //  Now handle our level. We use our own first and last position
 933             //  sets, so get them up front.
 934             //
 935             final CMStateSet first = nodeCur.firstPos();
 936             final CMStateSet last  = nodeCur.lastPos();
 937 
 938             //
 939             //  For every position which is in our last position set, add all
 940             //  of our first position states to the follow set for that
 941             //  position.
 942             //
 943             for (int index = 0; index < fLeafCount; index++) {
 944                 if (last.getBit(index))
 945                     fFollowList[index].union(first);
 946             }
 947         }
 948 
 949         else if (nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
 950             // Recurse only
 951             calcFollowList(((XSCMUniOp)nodeCur).getChild());
 952         }
 953 
 954     }
 955 
 956     /**
 957      * Dumps the tree of the current node to standard output.
 958      *
 959      * @param nodeCur The current node.
 960      * @param level   The maximum levels to output.
 961      *
 962      * @exception RuntimeException Thrown on error.
 963      */
 964     private void dumpTree(CMNode nodeCur, int level) {
 965         for (int index = 0; index < level; index++)
 966             System.out.print("   ");
 967 
 968         int type = nodeCur.type();
 969 
 970         switch(type ) {
 971 
 972         case XSModelGroupImpl.MODELGROUP_CHOICE:
 973         case XSModelGroupImpl.MODELGROUP_SEQUENCE: {
 974             if (type == XSModelGroupImpl.MODELGROUP_CHOICE)
 975                 System.out.print("Choice Node ");
 976             else
 977                 System.out.print("Seq Node ");
 978 
 979             if (nodeCur.isNullable())
 980                 System.out.print("Nullable ");
 981 
 982             System.out.print("firstPos=");
 983             System.out.print(nodeCur.firstPos().toString());
 984             System.out.print(" lastPos=");
 985             System.out.println(nodeCur.lastPos().toString());
 986 
 987             dumpTree(((XSCMBinOp)nodeCur).getLeft(), level+1);
 988             dumpTree(((XSCMBinOp)nodeCur).getRight(), level+1);
 989             break;
 990         }
 991         case XSParticleDecl.PARTICLE_ZERO_OR_MORE:
 992         case XSParticleDecl.PARTICLE_ONE_OR_MORE:
 993         case XSParticleDecl.PARTICLE_ZERO_OR_ONE: {
 994             System.out.print("Rep Node ");
 995 
 996             if (nodeCur.isNullable())
 997                 System.out.print("Nullable ");
 998 
 999             System.out.print("firstPos=");
1000             System.out.print(nodeCur.firstPos().toString());
1001             System.out.print(" lastPos=");
1002             System.out.println(nodeCur.lastPos().toString());
1003 
1004             dumpTree(((XSCMUniOp)nodeCur).getChild(), level+1);
1005             break;
1006         }
1007         case XSParticleDecl.PARTICLE_ELEMENT: {
1008             System.out.print
1009             (
1010                 "Leaf: (pos="
1011                 + ((XSCMLeaf)nodeCur).getPosition()
1012                 + "), "
1013                 + "(elemIndex="
1014                 + ((XSCMLeaf)nodeCur).getLeaf()
1015                 + ") "
1016             );
1017 
1018             if (nodeCur.isNullable())
1019                 System.out.print(" Nullable ");
1020 
1021             System.out.print("firstPos=");
1022             System.out.print(nodeCur.firstPos().toString());
1023             System.out.print(" lastPos=");
1024             System.out.println(nodeCur.lastPos().toString());
1025             break;
1026         }
1027         case XSParticleDecl.PARTICLE_WILDCARD:
1028               System.out.print("Any Node: ");
1029 
1030             System.out.print("firstPos=");
1031             System.out.print(nodeCur.firstPos().toString());
1032             System.out.print(" lastPos=");
1033             System.out.println(nodeCur.lastPos().toString());
1034             break;
1035         default: {
1036             throw new RuntimeException("ImplementationMessages.VAL_NIICM");
1037         }
1038         }
1039 
1040     }
1041 
1042 
1043     /**
1044      * -1 is used to represent bad transitions in the transition table
1045      * entry for each state. So each entry is initialized to an all -1
1046      * array. This method creates a new entry and initializes it.
1047      */
1048     private int[] makeDefStateList()
1049     {
1050         int[] retArray = new int[fElemMapSize];
1051         for (int index = 0; index < fElemMapSize; index++)
1052             retArray[index] = -1;
1053         return retArray;
1054     }
1055 
1056     /** Post tree build initialization. */
1057     private void postTreeBuildInit(CMNode nodeCur) throws RuntimeException {
1058         // Set the maximum states on this node
1059         nodeCur.setMaxStates(fLeafCount);
1060 
1061         XSCMLeaf leaf = null;
1062         int pos = 0;
1063         // Recurse as required
1064         if (nodeCur.type() == XSParticleDecl.PARTICLE_WILDCARD) {
1065             leaf = (XSCMLeaf)nodeCur;
1066             pos = leaf.getPosition();
1067             fLeafList[pos] = leaf;
1068             fLeafListType[pos] = XSParticleDecl.PARTICLE_WILDCARD;
1069         }
1070         else if ((nodeCur.type() == XSModelGroupImpl.MODELGROUP_CHOICE) ||
1071                  (nodeCur.type() == XSModelGroupImpl.MODELGROUP_SEQUENCE)) {
1072             postTreeBuildInit(((XSCMBinOp)nodeCur).getLeft());
1073             postTreeBuildInit(((XSCMBinOp)nodeCur).getRight());
1074         }
1075         else if (nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_MORE ||
1076                  nodeCur.type() == XSParticleDecl.PARTICLE_ONE_OR_MORE ||
1077                  nodeCur.type() == XSParticleDecl.PARTICLE_ZERO_OR_ONE) {
1078             postTreeBuildInit(((XSCMUniOp)nodeCur).getChild());
1079         }
1080         else if (nodeCur.type() == XSParticleDecl.PARTICLE_ELEMENT) {
1081             //  Put this node in the leaf list at the current index if its
1082             //  a non-epsilon leaf.
1083             leaf = (XSCMLeaf)nodeCur;
1084             pos = leaf.getPosition();
1085             fLeafList[pos] = leaf;
1086             fLeafListType[pos] = XSParticleDecl.PARTICLE_ELEMENT;
1087         }
1088         else {
1089             throw new RuntimeException("ImplementationMessages.VAL_NIICM");
1090         }
1091     }
1092 
1093     /**
1094      * check whether this content violates UPA constraint.
1095      *
1096      * @param subGroupHandler the substitution group handler
1097      * @return true if this content model contains other or list wildcard
1098      */
1099     public boolean checkUniqueParticleAttribution(SubstitutionGroupHandler subGroupHandler) throws XMLSchemaException {
1100         // Unique Particle Attribution
1101         // store the conflict results between any two elements in fElemMap
1102         // 0: not compared; -1: no conflict; 1: conflict
1103         // initialize the conflict table (all 0 initially)
1104         byte conflictTable[][] = new byte[fElemMapSize][fElemMapSize];
1105 
1106         // for each state, check whether it has overlap transitions
1107         for (int i = 0; i < fTransTable.length && fTransTable[i] != null; i++) {
1108             for (int j = 0; j < fElemMapSize; j++) {
1109                 for (int k = j+1; k < fElemMapSize; k++) {
1110                     if (fTransTable[i][j] != -1 &&
1111                         fTransTable[i][k] != -1) {
1112                         if (conflictTable[j][k] == 0) {
1113                             if (XSConstraints.overlapUPA
1114                                     (fElemMap[j], fElemMap[k],
1115                                             subGroupHandler)) {
1116                                 if (fCountingStates != null) {
1117                                     Occurence o = fCountingStates[i];
1118                                     // If "i" is a counting state and exactly one of the transitions
1119                                     // loops back to "i" then the two particles do not overlap if
1120                                     // minOccurs == maxOccurs.
1121                                     if (o != null &&
1122                                         fTransTable[i][j] == i ^ fTransTable[i][k] == i &&
1123                                         o.minOccurs == o.maxOccurs) {
1124                                         conflictTable[j][k] = (byte) -1;
1125                                         continue;
1126                                     }
1127                                 }
1128                                 conflictTable[j][k] = (byte) 1;
1129                             }
1130                             else {
1131                                 conflictTable[j][k] = (byte) -1;
1132                             }
1133                         }
1134                     }
1135                 }
1136             }
1137         }
1138 
1139         // report all errors
1140         for (int i = 0; i < fElemMapSize; i++) {
1141             for (int j = 0; j < fElemMapSize; j++) {
1142                 if (conflictTable[i][j] == 1) {
1143                     //errors.newError("cos-nonambig", new Object[]{fElemMap[i].toString(),
1144                     //                                             fElemMap[j].toString()});
1145                     // REVISIT: do we want to report all errors? or just one?
1146                     throw new XMLSchemaException("cos-nonambig", new Object[]{fElemMap[i].toString(),
1147                                                                               fElemMap[j].toString()});
1148                 }
1149             }
1150         }
1151 
1152         // if there is a other or list wildcard, we need to check this CM
1153         // again, if this grammar is cached.
1154         for (int i = 0; i < fElemMapSize; i++) {
1155             if (fElemMapType[i] == XSParticleDecl.PARTICLE_WILDCARD) {
1156                 XSWildcardDecl wildcard = (XSWildcardDecl)fElemMap[i];
1157                 if (wildcard.fType == XSWildcardDecl.NSCONSTRAINT_LIST ||
1158                     wildcard.fType == XSWildcardDecl.NSCONSTRAINT_NOT) {
1159                     return true;
1160                 }
1161             }
1162         }
1163 
1164         return false;
1165     }
1166 
1167     /**
1168      * Check which elements are valid to appear at this point. This method also
1169      * works if the state is in error, in which case it returns what should
1170      * have been seen.
1171      *
1172      * @param state  the current state
1173      * @return       a list whose entries are instances of
1174      *               either XSWildcardDecl or XSElementDecl.
1175      */
1176     public List<Object> whatCanGoHere(int[] state) {
1177         int curState = state[0];
1178         if (curState < 0)
1179             curState = state[1];
1180         Occurence o = (fCountingStates != null) ?
1181                 fCountingStates[curState] : null;
1182         int count = state[2];
1183 
1184         // Can be XSElementDecl or XSWildcardDecl, but eventually the content is
1185         // only used to evaluate toString
1186         List<Object> ret = new ArrayList<>();
1187         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
1188             int nextState = fTransTable[curState][elemIndex];
1189             if (nextState != -1) {
1190                 if (o != null) {
1191                     if (curState == nextState) {
1192                         // Do not include transitions which loop back to the
1193                         // current state if we've looped the maximum number
1194                         // of times or greater.
1195                         if (count >= o.maxOccurs &&
1196                             o.maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED) {
1197                             continue;
1198                         }
1199                     }
1200                     // Do not include transitions which advance past the
1201                     // current state if we have not looped enough times.
1202                     else if (count < o.minOccurs) {
1203                         continue;
1204                     }
1205                 }
1206                 ret.add(fElemMap[elemIndex]);
1207             }
1208         }
1209         return ret;
1210     }
1211 
1212     /**
1213      * Used by constant space algorithm for a{n,m} for n > 1 and
1214      * m <= unbounded. Called by a validator if validation of
1215      * countent model succeeds after subsuming a{n,m} to a*
1216      * (or a+) to check the n and m bounds.
1217      * Returns <code>null</code> if validation of bounds is
1218      * successful. Returns a list of strings with error info
1219      * if not. Even entries in list returned are error codes
1220      * (used to look up properties) and odd entries are parameters
1221      * to be passed when formatting error message. Each parameter
1222      * is associated with the error code that preceeds it in
1223      * the list.
1224      */
1225     public List<String> checkMinMaxBounds() {
1226         List<String> result = null;
1227         for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {
1228             int count = fElemMapCounter[elemIndex];
1229             if (count == -1) {
1230                 continue;
1231             }
1232             final int minOccurs = fElemMapCounterLowerBound[elemIndex];
1233             final int maxOccurs = fElemMapCounterUpperBound[elemIndex];
1234             if (count < minOccurs) {
1235                 if (result == null) result = new ArrayList<>();
1236                 result.add("cvc-complex-type.2.4.b");
1237                 result.add("{" + fElemMap[elemIndex] + "}");
1238             }
1239             if (maxOccurs != -1 && count > maxOccurs) {
1240                 if (result == null) result = new ArrayList<>();
1241                 result.add("cvc-complex-type.2.4.d.1");
1242                 result.add("{" + fElemMap[elemIndex] + "}");
1243             }
1244         }
1245         return result;
1246     }
1247 
1248     public int [] occurenceInfo(int[] state) {
1249         if (fCountingStates != null) {
1250             int curState = state[0];
1251             if (curState < 0) {
1252                 curState = state[1];
1253             }
1254             Occurence o = fCountingStates[curState];
1255             if (o != null) {
1256                 int [] occurenceInfo = new int[4];
1257                 occurenceInfo[0] = o.minOccurs;
1258                 occurenceInfo[1] = o.maxOccurs;
1259                 occurenceInfo[2] = state[2];
1260                 occurenceInfo[3] = o.elemIndex;
1261                 return occurenceInfo;
1262             }
1263         }
1264         return null;
1265     }
1266 
1267     public String getTermName(int termId) {
1268         Object term = fElemMap[termId];
1269         return (term != null) ? term.toString() : null;
1270     }
1271 
1272     public boolean isCompactedForUPA() {
1273         return fIsCompactedForUPA;
1274     }
1275 } // class DFAContentModel