/*

 * Copyright (c) 2006, 2017, Oracle and/or its affiliates. All rights reserved.

 */

/*

 * Licensed to the Apache Software Foundation (ASF) under one or more

 * contributor license agreements.  See the NOTICE file distributed with

 * this work for additional information regarding copyright ownership.

 * The ASF licenses this file to You under the Apache License, Version 2.0

 * (the "License"); you may not use this file except in compliance with

 * the License.  You may obtain a copy of the License at

 *

 *      http://www.apache.org/licenses/LICENSE-2.0

 *

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 */

package com.sun.org.apache.xerces.internal.impl.xs.models;

import com.sun.org.apache.xerces.internal.impl.dtd.models.CMNode;

import com.sun.org.apache.xerces.internal.impl.dtd.models.CMStateSet;

import com.sun.org.apache.xerces.internal.impl.xs.SchemaSymbols;

import com.sun.org.apache.xerces.internal.impl.xs.SubstitutionGroupHandler;

import com.sun.org.apache.xerces.internal.impl.xs.XMLSchemaException;

import com.sun.org.apache.xerces.internal.impl.xs.XSConstraints;

import java.util.ArrayList;

import java.util.HashMap;

/**

 * DFAContentModel is the implementation of XSCMValidator that does

 * all of the non-trivial element content validation. This class does

 * the conversion from the regular expression to the DFA that

 * it then uses in its validation algorithm.

 *

 * @xerces.internal

 *

 * @author Neil Graham, IBM

 */

public class XSDFACM

    implements XSCMValidator {

    //

    // Constants

    //

    private static final boolean DEBUG = false;

    // special strings

    // debugging

    /** Set to true to debug content model validation. */

    private static final boolean DEBUG_VALIDATE_CONTENT = false;

    //

    // Data

    //

    /**

     * This is the map of unique input symbol elements to indices into

     * each state's per-input symbol transition table entry. This is part

     * of the built DFA information that must be kept around to do the

     * actual validation.  Note tat since either XSElementDecl or XSParticleDecl object

     * can live here, we've got to use an Object.

     */

    private Object fElemMap[] = null;

    /**

     * This is a map of whether the element map contains information

     * related to ANY models.

     */

    private int fElemMapType[] = null;

    /**

     * id of the unique input symbol

     */

    private int fElemMapId[] = null;

    /** The element map size. */

    private int fElemMapSize = 0;

    /**

     * This is an array of booleans, one per state (there are

     * fTransTableSize states in the DFA) that indicates whether that

     * state is a final state.

     */

    private boolean fFinalStateFlags[] = null;

    /**

     * The list of follow positions for each NFA position (i.e. for each

     * non-epsilon leaf node.) This is only used during the building of

     * the DFA, and is let go afterwards.

     */

    private CMStateSet fFollowList[] = null;

    /**

     * This is the head node of our intermediate representation. It is

     * only non-null during the building of the DFA (just so that it

     * does not have to be passed all around.) Once the DFA is built,

     * this is no longer required so its nulled out.

     */

    private CMNode fHeadNode = null;

    /**

     * The count of leaf nodes. This is an important number that set some

     * limits on the sizes of data structures in the DFA process.

     */

    private int fLeafCount = 0;

    /**

     * An array of non-epsilon leaf nodes, which is used during the DFA

     * build operation, then dropped.

     */

    private XSCMLeaf fLeafList[] = null;

    /** Array mapping ANY types to the leaf list. */

    private int fLeafListType[] = null;

    /**

     * This is the transition table that is the main by product of all

     * of the effort here. It is an array of arrays of ints. The first

     * dimension is the number of states we end up with in the DFA. The

     * second dimensions is the number of unique elements in the content

     * model (fElemMapSize). Each entry in the second dimension indicates

     * the new state given that input for the first dimension's start

     * state.

     * <p>

     * The fElemMap array handles mapping from element indexes to

     * positions in the second dimension of the transition table.

     */

    private int fTransTable[][] = null;

    /**

     * Array containing occurence information for looping states

     * which use counters to check minOccurs/maxOccurs.

     */

    private Occurence [] fCountingStates = null;

    static final class Occurence {

        final int minOccurs;

        final int maxOccurs;

        final int elemIndex;

        public Occurence (XSCMRepeatingLeaf leaf, int elemIndex) {

            minOccurs = leaf.getMinOccurs();

            maxOccurs = leaf.getMaxOccurs();

            this.elemIndex = elemIndex;

        }

        public String toString() {

            return "minOccurs=" + minOccurs

                + ";maxOccurs=" +

                ((maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED)

                        ? Integer.toString(maxOccurs) : "unbounded");

        }

    }

    /**

     * The number of valid entries in the transition table, and in the other

     * related tables such as fFinalStateFlags.

     */

    private int fTransTableSize = 0;

    private boolean fIsCompactedForUPA;

    /**

     * Array of counters for all the for elements (or wildcards)

     * of the form a{n,m} where n > 1 and m <= unbounded. Used

     * to count the a's to later check against n and m. Counter

     * set to -1 if element (or wildcard) not optimized by

     * constant space algorithm.

     */

    private int fElemMapCounter[];

    /**

     * Array of lower bounds for all the for elements (or wildcards)

     * of the form a{n,m} where n > 1 and m <= unbounded. This array

     * stores the n's for those elements (or wildcards) for which

     * the constant space algorithm applies (or -1 otherwise).

     */

    private int fElemMapCounterLowerBound[];

    /**

     * Array of upper bounds for all the for elements (or wildcards)

     * of the form a{n,m} where n > 1 and m <= unbounded. This array

     * stores the n's for those elements (or wildcards) for which

     * the constant space algorithm applies, or -1 if algorithm does

     * not apply or m = unbounded.

     */

    private int fElemMapCounterUpperBound[];   // -1 if no upper bound

    // temp variables

    //

    // Constructors

    //

    /**

     * Constructs a DFA content model.

     *

     * @param syntaxTree    The syntax tree of the content model.

     * @param leafCount     The number of leaves.

     *

     * @exception RuntimeException Thrown if DFA can't be built.

     */

   public XSDFACM(CMNode syntaxTree, int leafCount) {

        // Store away our index and pools in members

        fLeafCount = leafCount;

        fIsCompactedForUPA = syntaxTree.isCompactedForUPA();

        //

        //  Create some string pool indexes that represent the names of some

        //  magical nodes in the syntax tree.

        //  (already done in static initialization...

        //

        //

        //  Ok, so lets grind through the building of the DFA. This method

        //  handles the high level logic of the algorithm, but it uses a

        //  number of helper classes to do its thing.

        //

        //  In order to avoid having hundreds of references to the error and

        //  string handlers around, this guy and all of his helper classes

        //  just throw a simple exception and we then pass it along.

        //

        if(DEBUG_VALIDATE_CONTENT) {

            XSDFACM.time -= System.currentTimeMillis();

        }

        buildDFA(syntaxTree);

        if(DEBUG_VALIDATE_CONTENT) {

            XSDFACM.time += System.currentTimeMillis();

            System.out.println("DFA build: " + XSDFACM.time + "ms");

        }

    }

    private static long time = 0;

    //

    // XSCMValidator methods

    //

    /**

     * check whether the given state is one of the final states

     *

     * @param state       the state to check

     *

     * @return whether it's a final state

     */

    public boolean isFinalState (int state) {

        return (state < 0)? false :

            fFinalStateFlags[state];

    }

    /**

     * one transition only

     *

     * @param curElem The current element's QName

     * @param state stack to store the previous state

     * @param subGroupHandler the substitution group handler

     *

     * @return  null if transition is invalid; otherwise the Object corresponding to the

     *      XSElementDecl or XSWildcardDecl identified.  Also, the

     *      state array will be modified to include the new state; this so that the validator can

     *      store it away.

     *

     * @exception RuntimeException thrown on error

     */

    public Object oneTransition(QName curElem, int[] state, SubstitutionGroupHandler subGroupHandler) {

        int curState = state[0];

        if(curState == XSCMValidator.FIRST_ERROR || curState == XSCMValidator.SUBSEQUENT_ERROR) {

            // there was an error last time; so just go find correct Object in fElemmMap.

            // ... after resetting state[0].

            if(curState == XSCMValidator.FIRST_ERROR)

                state[0] = XSCMValidator.SUBSEQUENT_ERROR;

            return findMatchingDecl(curElem, subGroupHandler);

        }

        int nextState = 0;

        int elemIndex = 0;

        Object matchingDecl = null;

        for (; elemIndex < fElemMapSize; elemIndex++) {

            nextState = fTransTable[curState][elemIndex];

            if (nextState == -1)

                continue;

            int type = fElemMapType[elemIndex] ;

            if (type == XSParticleDecl.PARTICLE_ELEMENT) {

                matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);

                if (matchingDecl != null) {

                    // Increment counter if constant space algorithm applies

                    if (fElemMapCounter[elemIndex] >= 0) {

                        fElemMapCounter[elemIndex]++;

                    }

                    break;

                }

            }

            else if (type == XSParticleDecl.PARTICLE_WILDCARD) {

                if (((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {

                    matchingDecl = fElemMap[elemIndex];

                    // Increment counter if constant space algorithm applies

                    if (fElemMapCounter[elemIndex] >= 0) {

                        fElemMapCounter[elemIndex]++;

                    }

                    break;

                }

            }

        }

        // if we still can't find a match, set the state to first_error

        // and return null

        if (elemIndex == fElemMapSize) {

            state[1] = state[0];

            state[0] = XSCMValidator.FIRST_ERROR;

            return findMatchingDecl(curElem, subGroupHandler);

        }

        if (fCountingStates != null) {

            Occurence o = fCountingStates[curState];

            if (o != null) {

                if (curState == nextState) {

                    if (++state[2] > o.maxOccurs &&

                        o.maxOccurs != SchemaSymbols.OCCURRENCE_UNBOUNDED) {

                        // It's likely that we looped too many times on the current state

                        // however it's possible that we actually matched another particle

                        // which allows the same name.

                        //

                        // Consider:

                        //

                        // <xs:sequence>

                        //  <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>

                        //  <xs:element name="foo" type="xs:string" fixed="bar"/>

                        // </xs:sequence>

                        //

                        // and

                        //

                        // <xs:sequence>

                        //  <xs:element name="foo" type="xs:string" minOccurs="3" maxOccurs="3"/>

                        //  <xs:any namespace="##any" processContents="skip"/>

                        // </xs:sequence>

                        //

                        // In the DFA there will be two transitions from the current state which

                        // allow "foo". Note that this is not a UPA violation. The ambiguity of which

                        // transition to take is resolved by the current value of the counter. Since

                        // we've already seen enough instances of the first "foo" perhaps there is

                        // another element declaration or wildcard deeper in the element map which

                        // matches.

                        return findMatchingDecl(curElem, state, subGroupHandler, elemIndex);

                    }

                }

                else if (state[2] < o.minOccurs) {

                    // not enough loops on the current state.

                    state[1] = state[0];

                    state[0] = XSCMValidator.FIRST_ERROR;

                    return findMatchingDecl(curElem, subGroupHandler);

                }

                else {

                    // Exiting a counting state. If we're entering a new

                    // counting state, reset the counter.

                    o = fCountingStates[nextState];

                    if (o != null) {

                        state[2] = (elemIndex == o.elemIndex) ? 1 : 0;

                    }

                }

            }

            else {

                o = fCountingStates[nextState];

                if (o != null) {

                    // Entering a new counting state. Reset the counter.

                    // If we've already seen one instance of the looping

                    // particle set the counter to 1, otherwise set it

                    // to 0.

                    state[2] = (elemIndex == o.elemIndex) ? 1 : 0;

                }

            }

        }

        state[0] = nextState;

        return matchingDecl;

    } // oneTransition(QName, int[], SubstitutionGroupHandler):  Object

    Object findMatchingDecl(QName curElem, SubstitutionGroupHandler subGroupHandler) {

        Object matchingDecl = null;

        for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {

            int type = fElemMapType[elemIndex] ;

            if (type == XSParticleDecl.PARTICLE_ELEMENT) {

                matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);

                if (matchingDecl != null) {

                    return matchingDecl;

                }

            }

            else if (type == XSParticleDecl.PARTICLE_WILDCARD) {

                if(((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri))

                    return fElemMap[elemIndex];

            }

        }

        return null;

    } // findMatchingDecl(QName, SubstitutionGroupHandler): Object

    Object findMatchingDecl(QName curElem, int[] state, SubstitutionGroupHandler subGroupHandler, int elemIndex) {

        int curState = state[0];

        int nextState = 0;

        Object matchingDecl = null;

        while (++elemIndex < fElemMapSize) {

            nextState = fTransTable[curState][elemIndex];

            if (nextState == -1)

                continue;

            int type = fElemMapType[elemIndex] ;

            if (type == XSParticleDecl.PARTICLE_ELEMENT) {

                matchingDecl = subGroupHandler.getMatchingElemDecl(curElem, (XSElementDecl)fElemMap[elemIndex]);

                if (matchingDecl != null) {

                    break;

                }

            }

            else if (type == XSParticleDecl.PARTICLE_WILDCARD) {

                if (((XSWildcardDecl)fElemMap[elemIndex]).allowNamespace(curElem.uri)) {

                    matchingDecl = fElemMap[elemIndex];

                    break;

                }

            }

        }

        // if we still can't find a match, set the state to FIRST_ERROR and return null

        if (elemIndex == fElemMapSize) {

            state[1] = state[0];

            state[0] = XSCMValidator.FIRST_ERROR;

            return findMatchingDecl(curElem, subGroupHandler);

        }

        // if we found a match, set the next state and reset the

        // counter if the next state is a counting state.

        state[0] = nextState;

        final Occurence o = fCountingStates[nextState];

        if (o != null) {

            state[2] = (elemIndex == o.elemIndex) ? 1 : 0;

        }

        return matchingDecl;

    } // findMatchingDecl(QName, int[], SubstitutionGroupHandler, int): Object

    // This method returns the start states of the content model.

    public int[] startContentModel() {

        // Clear all constant space algorithm counters in use

        for (int elemIndex = 0; elemIndex < fElemMapSize; elemIndex++) {

            if (fElemMapCounter[elemIndex] != -1) {

                fElemMapCounter[elemIndex] = 0;

            }

        }

        // [0] : the current state

        // [1] : if [0] is an error state then the

        //       last valid state before the error

        // [2] : occurence counter for counting states

        return new int [3];

    } // startContentModel():int[]

    // this method returns whether the last state was a valid final state

    public boolean endContentModel(int[] state) {

        final int curState = state[0];

        if (fFinalStateFlags[curState]) {

            if (fCountingStates != null) {

                Occurence o = fCountingStates[curState];

                if (o != null && state[2] < o.minOccurs) {

                    // not enough loops on the current state to be considered final.

                    return false;

                }

            }

            return true;

        }

        return false;

    } // endContentModel(int[]):  boolean

    // Killed off whatCanGoHere; we may need it for DOM canInsert(...) etc.,

    // but we can put it back later.

    //

    // Private methods

    //

    /**

     * Builds the internal DFA transition table from the given syntax tree.

     *

     * @param syntaxTree The syntax tree.

     *

     * @exception RuntimeException Thrown if DFA cannot be built.

     */

    private void buildDFA(CMNode syntaxTree) {

        //

        //  The first step we need to take is to rewrite the content model

        //  using our CMNode objects, and in the process get rid of any

        //  repetition short cuts, converting them into '*' style repetitions

        //  or getting rid of repetitions altogether.

        //

        //  The conversions done are:

        //

        //  x+ -> (x|x*)

        //  x? -> (x|epsilon)

        //

        //  This is a relatively complex scenario. What is happening is that

        //  we create a top level binary node of which the special EOC value

        //  is set as the right side node. The the left side is set to the

        //  rewritten syntax tree. The source is the original content model

        //  info from the decl pool. The rewrite is done by buildSyntaxTree()

        //  which recurses the decl pool's content of the element and builds

        //  a new tree in the process.

        //

        //  Note that, during this operation, we set each non-epsilon leaf

        //  node's DFA state position and count the number of such leafs, which

        //  is left in the fLeafCount member.

        //

        //  The nodeTmp object is passed in just as a temp node to use during