/*

 */

/*

 * 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.dtd;

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

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

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

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

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

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

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

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

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

import com.sun.org.apache.xerces.internal.impl.dv.DatatypeValidator;

import com.sun.org.apache.xerces.internal.impl.validation.EntityState;

import com.sun.org.apache.xerces.internal.util.SymbolTable;

import com.sun.org.apache.xerces.internal.xni.Augmentations;

import com.sun.org.apache.xerces.internal.xni.QName;

import com.sun.org.apache.xerces.internal.xni.XMLDTDContentModelHandler;

import com.sun.org.apache.xerces.internal.xni.XMLDTDHandler;

import com.sun.org.apache.xerces.internal.xni.XMLLocator;

import com.sun.org.apache.xerces.internal.xni.XMLResourceIdentifier;

import com.sun.org.apache.xerces.internal.xni.XMLString;

import com.sun.org.apache.xerces.internal.xni.XNIException;

import com.sun.org.apache.xerces.internal.xni.grammars.Grammar;

import com.sun.org.apache.xerces.internal.xni.grammars.XMLGrammarDescription;

import com.sun.org.apache.xerces.internal.xni.parser.XMLDTDContentModelSource;

import com.sun.org.apache.xerces.internal.xni.parser.XMLDTDSource;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Map;

import java.util.Random;

/**

 * A DTD grammar. This class implements the XNI handler interfaces

 * for DTD information so that it can build the appropriate validation

 * structures automatically from the callbacks.

 *

 * @xerces.internal

 *

 * @author Eric Ye, IBM

 * @author Jeffrey Rodriguez, IBM

 * @author Andy Clark, IBM

 * @author Neil Graham, IBM

 *

 */

public class DTDGrammar

    implements XMLDTDHandler, XMLDTDContentModelHandler, EntityState, Grammar {

    //

    // Constants

    //

    /** Top level scope (-1). */

    public static final int TOP_LEVEL_SCOPE = -1;

    // private

    /** Chunk shift (8). */

    private static final int CHUNK_SHIFT = 8; // 2^8 = 256

    /** Chunk size (1 << CHUNK_SHIFT). */

    private static final int CHUNK_SIZE = (1 << CHUNK_SHIFT);

    /** Chunk mask (CHUNK_SIZE - 1). */

    private static final int CHUNK_MASK = CHUNK_SIZE - 1;

    /** Initial chunk count (1 << (10 - CHUNK_SHIFT)). */

    private static final int INITIAL_CHUNK_COUNT = (1 << (10 - CHUNK_SHIFT)); // 2^10 = 1k

    /** List flag (0x80). */

    private static final short LIST_FLAG = 0x80;

    /** List mask (~LIST_FLAG). */

    private static final short LIST_MASK = ~LIST_FLAG;

    // debugging

    /** Debug DTDGrammar. */

    private static final boolean DEBUG = false;

    //

    // Data

    //

    protected XMLDTDSource fDTDSource = null;

    protected XMLDTDContentModelSource fDTDContentModelSource = null;

    /** Current element index. */

    protected int fCurrentElementIndex;

    /** Current attribute index. */

    protected int fCurrentAttributeIndex;

    /** fReadingExternalDTD */

    protected boolean fReadingExternalDTD = false;

    /** Symbol table. */

    private SymbolTable fSymbolTable;

    // The XMLDTDDescription with which this Grammar is associated

    protected XMLDTDDescription fGrammarDescription = null;

    // element declarations

    /** Number of element declarations. */

    private int fElementDeclCount = 0;

    /** Element declaration name. */

    private QName fElementDeclName[][] = new QName[INITIAL_CHUNK_COUNT][];

    /**

     * Element declaration type.

     * @see XMLElementDecl

     */

    private short fElementDeclType[][] = new short[INITIAL_CHUNK_COUNT][];

    /**

     * Element declaration content spec index. This index value is used

     * to refer to the content spec information tables.

     */

    private int fElementDeclContentSpecIndex[][] = new int[INITIAL_CHUNK_COUNT][];

    /**

     * Element declaration content model validator. This validator is

     * constructed from the content spec nodes.

     */

    private ContentModelValidator fElementDeclContentModelValidator[][] = new ContentModelValidator[INITIAL_CHUNK_COUNT][];

    /** First attribute declaration of an element declaration. */

    private int fElementDeclFirstAttributeDeclIndex[][] = new int[INITIAL_CHUNK_COUNT][];

    /** Last attribute declaration of an element declaration. */

    private int fElementDeclLastAttributeDeclIndex[][] = new int[INITIAL_CHUNK_COUNT][];

    // attribute declarations

    /** Number of attribute declarations. */

    private int fAttributeDeclCount = 0 ;

    /** Attribute declaration name. */

    private QName fAttributeDeclName[][] = new QName[INITIAL_CHUNK_COUNT][];

    // is this grammar immutable?  (fully constructed and not changeable)

    private boolean fIsImmutable = false;

    /**

     * Attribute declaration type.

     * @see XMLAttributeDecl

     */

    private short fAttributeDeclType[][] = new short[INITIAL_CHUNK_COUNT][];

    /** Attribute declaration enumeration values. */

    private String[] fAttributeDeclEnumeration[][] = new String[INITIAL_CHUNK_COUNT][][];

    private short fAttributeDeclDefaultType[][] = new short[INITIAL_CHUNK_COUNT][];

    private DatatypeValidator fAttributeDeclDatatypeValidator[][] = new DatatypeValidator[INITIAL_CHUNK_COUNT][];

    private String fAttributeDeclDefaultValue[][] = new String[INITIAL_CHUNK_COUNT][];

    private String fAttributeDeclNonNormalizedDefaultValue[][] = new String[INITIAL_CHUNK_COUNT][];

    private int fAttributeDeclNextAttributeDeclIndex[][] = new int[INITIAL_CHUNK_COUNT][];

    // content specs

    // here saves the content spec binary trees for element decls,

    // each element with a content model will hold a pointer which is

    // the index of the head node of the content spec tree.

    private int fContentSpecCount = 0;

    private short fContentSpecType[][] = new short[INITIAL_CHUNK_COUNT][];

    private Object fContentSpecValue[][] = new Object[INITIAL_CHUNK_COUNT][];

    private Object fContentSpecOtherValue[][] = new Object[INITIAL_CHUNK_COUNT][];

    // entities

    private int fEntityCount = 0;

    private String fEntityName[][] = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fEntityValue = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fEntityPublicId = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fEntitySystemId = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fEntityBaseSystemId = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fEntityNotation = new String[INITIAL_CHUNK_COUNT][];

    private byte[][] fEntityIsPE = new byte[INITIAL_CHUNK_COUNT][];

    private byte[][] fEntityInExternal = new byte[INITIAL_CHUNK_COUNT][];

    // notations

    private int fNotationCount = 0;

    private String fNotationName[][] = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fNotationPublicId = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fNotationSystemId = new String[INITIAL_CHUNK_COUNT][];

    private String[][] fNotationBaseSystemId = new String[INITIAL_CHUNK_COUNT][];

    // other information

    /** Element index mapping table. */

    private final Map<String, Integer> fElementIndexMap = new HashMap<>();

    /** Entity index mapping table. */

    private final Map<String, Integer> fEntityIndexMap = new HashMap<>();

    /** Notation index mapping table. */

    private final Map<String, Integer> fNotationIndexMap = new HashMap<>();

    // temp variables

    /** Mixed. */

    private boolean fMixed;

    /** Temporary qualified name. */

    private final QName fQName = new QName();

    /** Temporary qualified name. */

    private final QName fQName2 = new QName();

    /** Temporary Attribute decl. */

    protected final XMLAttributeDecl fAttributeDecl = new XMLAttributeDecl();

    // for buildSyntaxTree method

    private int fLeafCount = 0;

    private int fEpsilonIndex = -1;

    /** Element declaration. */

    private XMLElementDecl fElementDecl = new XMLElementDecl();

    /** Entity declaration. */

    private XMLEntityDecl fEntityDecl = new XMLEntityDecl();

    /** Simple type. */

    private XMLSimpleType fSimpleType = new XMLSimpleType();

    /** Content spec node. */

    private XMLContentSpec fContentSpec = new XMLContentSpec();

    /** table of XMLElementDecl   */

    Map<String, XMLElementDecl> fElementDeclTab = new HashMap<>();

    /** Children content model operation stack. */

    private short[] fOpStack = null;

    /** Children content model index stack. */

    private int[] fNodeIndexStack = null;

    /** Children content model previous node index stack. */

    private int[] fPrevNodeIndexStack = null;

    /** Stack depth   */

    private int fDepth = 0;

    /** Entity stack. */

    private boolean[] fPEntityStack = new boolean[4];

    private int fPEDepth = 0;

    // additional fields(columns) for the element Decl pool in the Grammar

    /** flag if the elementDecl is External. */

    private int fElementDeclIsExternal[][] = new int[INITIAL_CHUNK_COUNT][];

    // additional fields(columns) for the attribute Decl pool in the Grammar

    /** flag if the AttributeDecl is External. */

    private int fAttributeDeclIsExternal[][] = new int[INITIAL_CHUNK_COUNT][];

    // for mixedElement method

    int valueIndex            = -1;

    int prevNodeIndex         = -1;

    int nodeIndex             = -1;

    //

    // Constructors

    //

    /** Default constructor. */

    public DTDGrammar(SymbolTable symbolTable, XMLDTDDescription desc) {

        fSymbolTable = symbolTable;

        fGrammarDescription = desc;

    } // <init>(SymbolTable)

    // Grammar methods

    // return the XMLDTDDescription object with which this is associated

    public XMLGrammarDescription getGrammarDescription() {

        return fGrammarDescription;

    } // getGrammarDescription():  XMLGrammarDescription

    //

    // Public methods

    //

    /**

     * Returns true if the specified element declaration is external.

     *

     * @param elementDeclIndex The element declaration index.

     */

    public boolean getElementDeclIsExternal(int elementDeclIndex) {

        if (elementDeclIndex < 0) {

            return false;

        }

        int chunk = elementDeclIndex >> CHUNK_SHIFT;

        int index = elementDeclIndex & CHUNK_MASK;

        return (fElementDeclIsExternal[chunk][index] != 0);

    } // getElementDeclIsExternal(int):boolean

    /**

     * Returns true if the specified attribute declaration is external.

     *

     * @param attributeDeclIndex Attribute declaration index.

     */

    public boolean getAttributeDeclIsExternal(int attributeDeclIndex) {

        if (attributeDeclIndex < 0) {

            return false;

        }

        int chunk = attributeDeclIndex >> CHUNK_SHIFT;

        int index = attributeDeclIndex & CHUNK_MASK;

        return (fAttributeDeclIsExternal[chunk][index] != 0);

    }

    public int getAttributeDeclIndex(int elementDeclIndex, String attributeDeclName) {

        if (elementDeclIndex == -1) {

            return -1;

        }

        int attDefIndex = getFirstAttributeDeclIndex(elementDeclIndex);

        while (attDefIndex != -1) {

            getAttributeDecl(attDefIndex, fAttributeDecl);

            if (fAttributeDecl.name.rawname == attributeDeclName

                || attributeDeclName.equals(fAttributeDecl.name.rawname) ) {

                return attDefIndex;

            }

            attDefIndex = getNextAttributeDeclIndex(attDefIndex);

        }

        return -1;

    } // getAttributeDeclIndex (int,QName)

    //

    // XMLDTDHandler methods

    //

    /**

     * The start of the DTD.

     *

     * @param locator  The document locator, or null if the document

     *                 location cannot be reported during the parsing of

     *                 the document DTD. However, it is <em>strongly</em>

     *                 recommended that a locator be supplied that can

     *                 at least report the base system identifier of the

     *                 DTD.

     *

     * @param augs Additional information that may include infoset

     *                      augmentations.

     * @throws XNIException Thrown by handler to signal an error.

     */

    public void startDTD(XMLLocator locator, Augmentations augs) throws XNIException {

        //Initialize stack

        fOpStack = null;

        fNodeIndexStack = null;

        fPrevNodeIndexStack = null;

    } // startDTD(XMLLocator)

    /**

     * This method notifies of the start of an entity. The DTD has the

     * pseudo-name of "[dtd]" and parameter entity names start with '%'.

     * <p>

     * <strong>Note:</strong> Since the DTD is an entity, the handler

     * will be notified of the start of the DTD entity by calling the

     * startParameterEntity method with the entity name "[dtd]" <em>before</em> calling

     * the startDTD method.

     *

     * @param name     The name of the parameter entity.

     * @param identifier The resource identifier.

     * @param encoding The auto-detected IANA encoding name of the entity

     *                 stream. This value will be null in those situations

     *                 where the entity encoding is not auto-detected (e.g.

     *                 internal parameter entities).

     * @param augs Additional information that may include infoset

     *                      augmentations.

     *

     * @throws XNIException Thrown by handler to signal an error.

     */

    public void startParameterEntity(String name,

                                     XMLResourceIdentifier identifier,

                                     String encoding,

                                     Augmentations augs) throws XNIException {

        // keep track of this entity before fEntityDepth is increased

        if (fPEDepth == fPEntityStack.length) {

            boolean[] entityarray = new boolean[fPEntityStack.length * 2];

            System.arraycopy(fPEntityStack, 0, entityarray, 0, fPEntityStack.length);

            fPEntityStack = entityarray;

        }

        fPEntityStack[fPEDepth] = fReadingExternalDTD;

        fPEDepth++;

    } // startParameterEntity(String,XMLResourceIdentifier,String,Augmentations)

    /**

     * The start of the DTD external subset.

     *

     * @param augs Additional information that may include infoset

     *                      augmentations.

     *

     * @throws XNIException Thrown by handler to signal an error.

     */

    public void startExternalSubset(XMLResourceIdentifier identifier,

                                    Augmentations augs) throws XNIException {

        fReadingExternalDTD = true;

    } // startExternalSubset(Augmentations)

    /**

     * This method notifies the end of an entity. The DTD has the pseudo-name

     * of "[dtd]" and parameter entity names start with '%'.

     * <p>

     * <strong>Note:</strong> Since the DTD is an entity, the handler

     * will be notified of the end of the DTD entity by calling the

     * endEntity method with the entity name "[dtd]" <em>after</em> calling

     * the endDTD method.

     *

     * @param name The name of the entity.

     * @param augs Additional information that may include infoset

     *                      augmentations.

     * @throws XNIException Thrown by handler to signal an error.

     */

    public void endParameterEntity(String name, Augmentations augs) throws XNIException {

        fPEDepth--;

        fReadingExternalDTD = fPEntityStack[fPEDepth];

    } // endParameterEntity(String,Augmentations)

    /**

     * The end of the DTD external subset.

     *

     * @param augs Additional information that may include infoset

     *                      augmentations.

     *

     * @throws XNIException Thrown by handler to signal an error.

     */

    public void endExternalSubset(Augmentations augs) throws XNIException {

        fReadingExternalDTD = false;

    } // endExternalSubset(Augmentations)

    /**

     * An element declaration.

     *

     * @param name         The name of the element.

     * @param contentModel The element content model.

     * @param augs Additional information that may include infoset

     *                      augmentations.

     * @throws XNIException Thrown by handler to signal an error.

     */

    public void elementDecl(String name, String contentModel, Augmentations augs)

        throws XNIException {

        XMLElementDecl tmpElementDecl = fElementDeclTab.get(name) ;

        // check if it is already defined

        if ( tmpElementDecl != null ) {

            if (tmpElementDecl.type == -1) {

                fCurrentElementIndex = getElementDeclIndex(name);

            }

            else {

                // duplicate element, ignored.

                return;

            }

        }

        else {

            fCurrentElementIndex = createElementDecl();//create element decl

        }

        XMLElementDecl elementDecl       = new XMLElementDecl();

        fQName.setValues(null, name, name, null);

        elementDecl.name.setValues(fQName);

        elementDecl.contentModelValidator = null;

        elementDecl.scope= -1;

        if (contentModel.equals("EMPTY")) {

            elementDecl.type = XMLElementDecl.TYPE_EMPTY;

        }

        else if (contentModel.equals("ANY")) {

            elementDecl.type = XMLElementDecl.TYPE_ANY;

        }

        else if (contentModel.startsWith("(") ) {

            if (contentModel.indexOf("#PCDATA") > 0 ) {

                elementDecl.type = XMLElementDecl.TYPE_MIXED;

            }

            else {

                elementDecl.type = XMLElementDecl.TYPE_CHILDREN;

            }

        }

        //add(or set) this elementDecl to the local cache

        this.fElementDeclTab.put(name, elementDecl );

        fElementDecl = elementDecl;

        addContentSpecToElement(elementDecl);