/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 2001, 2002 The Apache Software Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Xerces" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written
 *    permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation and was
 * originally based on software copyright (c) 1999, International
 * Business Machines, Inc., http://www.apache.org.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */

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

import com.sun.org.apache.xerces.internal.impl.Constants;
import com.sun.org.apache.xerces.internal.impl.xpath.XPath;
import com.sun.org.apache.xerces.internal.xs.XSTypeDefinition;
import com.sun.org.apache.xerces.internal.util.IntStack;
import com.sun.org.apache.xerces.internal.xni.QName;
import com.sun.org.apache.xerces.internal.xni.XMLAttributes;
import com.sun.org.apache.xerces.internal.xs.AttributePSVI;


/**
 * XPath matcher.
 *
 * @author Andy Clark, IBM
 *
 * @version $Id: XPathMatcher.java,v 1.22 2004/02/10 21:26:03 kohsuke Exp $
 */
public class XPathMatcher {

    //
    // Constants
    //

    // debugging

    /** Compile to true to debug everything. */
    protected static final boolean DEBUG_ALL = false;

    /** Compile to true to debug method callbacks. */
    protected static final boolean DEBUG_METHODS = false || DEBUG_ALL;

    /** Compile to true to debug important method callbacks. */
    protected static final boolean DEBUG_METHODS2 = false || DEBUG_METHODS || DEBUG_ALL;

    /** Compile to true to debug the <em>really</em> important methods. */
    protected static final boolean DEBUG_METHODS3 = false || DEBUG_METHODS || DEBUG_ALL;

    /** Compile to true to debug match. */
    protected static final boolean DEBUG_MATCH = false || DEBUG_ALL;

    /** Compile to true to debug step index stack. */
    protected static final boolean DEBUG_STACK = false || DEBUG_ALL;

    /** Don't touch this value unless you add more debug constants. */
    protected static final boolean DEBUG_ANY = DEBUG_METHODS ||
                                               DEBUG_METHODS2 ||
                                               DEBUG_METHODS3 ||
                                               DEBUG_MATCH ||
                                               DEBUG_STACK;

    // constants describing whether a match was made,
    // and if so how.  
    // matched any way
    protected static final int MATCHED = 1;
    // matched on the attribute axis
    protected static final int MATCHED_ATTRIBUTE = 3;
    // matched on the descendant-or-self axixs
    protected static final int MATCHED_DESCENDANT = 5;
    // matched some previous (ancestor) node on the descendant-or-self-axis, but not this node
    protected static final int MATCHED_DESCENDANT_PREVIOUS = 13;

    //
    // Data
    //

    /** XPath location path. */
    private XPath.LocationPath[] fLocationPaths;

    /** True if XPath has been matched. */
    private int[] fMatched;

    /** The matching string. */
    protected Object fMatchedString;

    /** Integer stack of step indexes. */
    private IntStack[] fStepIndexes;

    /** Current step. */
    private int[] fCurrentStep;

    /**
     * No match depth. The value of this field will be zero while
     * matching is successful for the given xpath expression.
     */
    private int [] fNoMatchDepth;
    
    final QName fQName = new QName();

  	XSTypeDefinition fCurrMatchedType = null;	
    //
    // Constructors
    //

    /**
     * Constructs an XPath matcher that implements a document fragment
     * handler.
     *
     * @param xpath   The xpath.
     */
    public XPathMatcher(XPath xpath) {
        fLocationPaths = xpath.getLocationPaths();
        fStepIndexes = new IntStack[fLocationPaths.length];
        for(int i=0; i<fStepIndexes.length; i++) fStepIndexes[i] = new IntStack();
        fCurrentStep = new int[fLocationPaths.length];
        fNoMatchDepth = new int[fLocationPaths.length];
        fMatched = new int[fLocationPaths.length];        
    } // <init>(XPath)

    //
    // Public methods
    //

    /** 
     * Returns value of first member of fMatched that
     * is nonzero.  
     */
    public boolean isMatched() {
        // xpath has been matched if any one of the members of the union have matched.
        for (int i=0; i < fLocationPaths.length; i++) 
            if (((fMatched[i] & MATCHED) == MATCHED) 
                    && ((fMatched[i] & MATCHED_DESCENDANT_PREVIOUS) != MATCHED_DESCENDANT_PREVIOUS) 
                    && ((fNoMatchDepth[i] == 0)
                    || ((fMatched[i] & MATCHED_DESCENDANT) == MATCHED_DESCENDANT))) 
                return true;

        return false;
    } // isMatched():int

    //
    // Protected methods
    //

    // a place-holder method; to be overridden by subclasses
    // that care about matching element content.
    protected void handleContent(XSTypeDefinition type, boolean nillable, Object value) { 
    } 

    /**
     * This method is called when the XPath handler matches the
     * XPath expression. Subclasses can override this method to
     * provide default handling upon a match.
     */
    protected void matched(Object actualValue, boolean isNil) {
        if (DEBUG_METHODS3) {
            System.out.println(toString()+"#matched(\""+actualValue+"\")");
        }
    } // matched(String content, XSSimpleType val)

    //
    // ~XMLDocumentFragmentHandler methods
    //

    /**
     * The start of the document fragment.
     *
     * @param context The namespace scope in effect at the
     *                start of this document fragment.
     */
    public void startDocumentFragment(){
        if (DEBUG_METHODS) {
            System.out.println(toString()+"#startDocumentFragment("+
                               ")");
        }

        // reset state
        fMatchedString = null;
        for(int i = 0; i < fLocationPaths.length; i++) {
            fStepIndexes[i].clear();
            fCurrentStep[i] = 0;
            fNoMatchDepth[i] = 0;
            fMatched[i] = 0;
        }


    } // startDocumentFragment(SymbolTable)

    /**
     * The start of an element. If the document specifies the start element
     * by using an empty tag, then the startElement method will immediately
     * be followed by the endElement method, with no intervening methods.
     *
     * @param element    The name of the element.
     * @param attributes The element attributes.
     * @param type: The element's type
     *
     * @throws SAXException Thrown by handler to signal an error.
     */
    public void startElement(QName element, XMLAttributes attributes){
        if (DEBUG_METHODS2) {
            System.out.println(toString()+"#startElement("+
                               "element={"+element+"},"+
                               "attributes=..."+attributes+
                               ")");                     
        }

        for(int i = 0; i < fLocationPaths.length; i++) {
            // push context
            int startStep = fCurrentStep[i];
            fStepIndexes[i].push(startStep);

            // try next xpath, if not matching
            if ((fMatched[i] & MATCHED_DESCENDANT) == MATCHED || fNoMatchDepth[i] > 0) {
                fNoMatchDepth[i]++;
                continue;
            }
            if((fMatched[i] & MATCHED_DESCENDANT) == MATCHED_DESCENDANT) {
                fMatched[i] = MATCHED_DESCENDANT_PREVIOUS;
            }

            if (DEBUG_STACK) {
                System.out.println(toString()+": "+fStepIndexes[i]);
            }

            // consume self::node() steps
            XPath.Step[] steps = fLocationPaths[i].steps;
            while (fCurrentStep[i] < steps.length &&
                    steps[fCurrentStep[i]].axis.type == XPath.Axis.SELF) {
                if (DEBUG_MATCH) {
                    XPath.Step step = steps[fCurrentStep[i]];
                    System.out.println(toString()+" [SELF] MATCHED!");
                }
                fCurrentStep[i]++;
            }
            if (fCurrentStep[i] == steps.length) {
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" XPath MATCHED!");
                }
                fMatched[i] = MATCHED;
                continue;
            }

            // now if the current step is a descendant step, we let the next
            // step do its thing; if it fails, we reset ourselves
            // to look at this step for next time we're called.
            // so first consume all descendants:
            int descendantStep = fCurrentStep[i];
            while(fCurrentStep[i] < steps.length && steps[fCurrentStep[i]].axis.type == XPath.Axis.DESCENDANT) {
                if (DEBUG_MATCH) {
                    XPath.Step step = steps[fCurrentStep[i]];
                    System.out.println(toString()+" [DESCENDANT] MATCHED!");
                }
                fCurrentStep[i]++;
            }
            boolean sawDescendant = fCurrentStep[i] > descendantStep;
            if (fCurrentStep[i] == steps.length) {
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" XPath DIDN'T MATCH!");
                }
                fNoMatchDepth[i]++;
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" [CHILD] after NO MATCH");
                }
                continue;
            }

            // match child::... step, if haven't consumed any self::node()
            if ((fCurrentStep[i] == startStep || fCurrentStep[i] > descendantStep) &&
                steps[fCurrentStep[i]].axis.type == XPath.Axis.CHILD) {
                XPath.Step step = steps[fCurrentStep[i]];
                XPath.NodeTest nodeTest = step.nodeTest;
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" [CHILD] before");
                }
                if (nodeTest.type == XPath.NodeTest.QNAME) {
                    if (!nodeTest.name.equals(element)) {
                        if(fCurrentStep[i] > descendantStep) {
                            fCurrentStep[i] = descendantStep;
                            continue;
                        }
                        fNoMatchDepth[i]++;
                        if (DEBUG_MATCH) {
                            System.out.println(toString()+" [CHILD] after NO MATCH");
                        }
                        continue;
                    }
                }
                fCurrentStep[i]++;
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" [CHILD] after MATCHED!");
                }
            }
            if (fCurrentStep[i] == steps.length) {
                if(sawDescendant) {
                    fCurrentStep[i] = descendantStep;
                    fMatched[i] = MATCHED_DESCENDANT;
                } else {
                    fMatched[i] = MATCHED;
                }
                continue;
            }

            // match attribute::... step
            if (fCurrentStep[i] < steps.length &&
                steps[fCurrentStep[i]].axis.type == XPath.Axis.ATTRIBUTE) {
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" [ATTRIBUTE] before");
                }
                int attrCount = attributes.getLength();
                if (attrCount > 0) {
                    XPath.NodeTest nodeTest = steps[fCurrentStep[i]].nodeTest;

                    for (int aIndex = 0; aIndex < attrCount; aIndex++) {
                        attributes.getName(aIndex, fQName);
                        if (nodeTest.type != XPath.NodeTest.QNAME ||
                            nodeTest.name.equals(fQName)) {
                            fCurrentStep[i]++;
                            if (fCurrentStep[i] == steps.length) {
                                fMatched[i] = MATCHED_ATTRIBUTE;
                                int j=0;
                                for(; j<i && ((fMatched[j] & MATCHED) != MATCHED); j++);
                                if(j==i) {
                                    AttributePSVI attrPSVI = (AttributePSVI)attributes.getAugmentations(aIndex).getItem(Constants.ATTRIBUTE_PSVI);
                                    fMatchedString = attrPSVI.getActualNormalizedValue();
									fCurrMatchedType = attrPSVI.getTypeDefinition();
                                    matched(fMatchedString, false);
                                }
                            }
                            break;
                        }
                    }
                }
                if ((fMatched[i] & MATCHED) != MATCHED) {
                    if(fCurrentStep[i] > descendantStep) {
                        fCurrentStep[i] = descendantStep;
                        continue;
                    }
                    fNoMatchDepth[i]++;
                    if (DEBUG_MATCH) {
                        System.out.println(toString()+" [ATTRIBUTE] after");
                    }
                    continue;
                }
                if (DEBUG_MATCH) {
                    System.out.println(toString()+" [ATTRIBUTE] after MATCHED!");
                }
            }
        }

    } 
    // startElement(QName,XMLAttrList,int)

    /**
       * @param element
       *        name of the element.
       * @param type
       *        content type of this element. IOW, the XML schema type
       *        of the <tt>value</tt>. Note that this may not be the type declared
       *        in the element declaration, but it is "the actual type". For example,
       *        if the XML is <foo xsi:type="xs:string">aaa</foo>, this
       *        parameter will be "xs:string".
       * @param nillable - nillable
       *        true if the element declaration is nillable.
       * @param value - actual value
       *        the typed value of the content of this element. 
       */
    public void endElement(QName element, XSTypeDefinition type, boolean nillable, Object value ) {
        if (DEBUG_METHODS2) {
            System.out.println(toString()+"#endElement("+
                               "element={"+element+"},"+
                               ")");
        }
        for(int i = 0; i<fLocationPaths.length; i++) {
            // go back a step
            fCurrentStep[i] = fStepIndexes[i].pop();

            // don't do anything, if not matching
            if (fNoMatchDepth[i] > 0) {
                fNoMatchDepth[i]--;
            }

            // signal match, if appropriate
            else {
                int j=0;
                for(; j<i && ((fMatched[j] & MATCHED) != MATCHED); j++);
                if ((j<i) || (fMatched[j] == 0) ||
                        ((fMatched[j] & MATCHED_ATTRIBUTE) == MATCHED_ATTRIBUTE)) {
                    continue;
                }
                // only certain kinds of matchers actually
                // match element content.  This permits
                // them a way to override this to do nothing
                // and hopefully save a few operations.
                handleContent(type, nillable, value);
                fMatched[i] = 0;
            }

            if (DEBUG_STACK) {
                System.out.println(toString()+": "+fStepIndexes[i]);
            }
        }

    } // endElement(QName)

    //
    // Object methods
    //

    /** Returns a string representation of this object. */
    public String toString() {
        /***
        return fLocationPath.toString();
        /***/
        StringBuffer str = new StringBuffer();
        String s = super.toString();
        int index2 = s.lastIndexOf('.');
        if (index2 != -1) {
            s = s.substring(index2 + 1);
        }
        str.append(s);
        for(int i =0;i<fLocationPaths.length; i++) {
            str.append('[');
            XPath.Step[] steps = fLocationPaths[i].steps;
            for (int j = 0; j < steps.length; j++) {
                if (j == fCurrentStep[i]) {
                    str.append('^');
                }
                str.append(steps[j].toString());
                if (j < steps.length - 1) {
                    str.append('/');
                }
            }
            if (fCurrentStep[i] == steps.length) {
                str.append('^');
            }
            str.append(']');
            str.append(',');
        }
        return str.toString();
    } // toString():String

    //
    // Private methods
    //

    /** Normalizes text. */
    private String normalize(String s) {
        StringBuffer str = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '\n': {
                    str.append("\\n");
                    break;
                }
                default: {
                    str.append(c);
                }
            }
        }
        return str.toString();
    } // normalize(String):String

	public XSTypeDefinition getCurrentMatchedType(){
		return fCurrMatchedType;
	}

    //
    // MAIN
    //

    // NOTE: The main of this class is here for debugging purposes.
    //       However, javac (JDK 1.1.8) has an internal compiler
    //       error when compiling. Jikes has no problem, though.
    //
    //       If you want to use this main, use Jikes to compile but
    //       *never* check in this code to CVS without commenting it
    //       out. -Ac

    /** Main program. */
    /***
    public static void main(String[] argv) throws XNIException {

        if (DEBUG_ANY) {
            for (int i = 0; i < argv.length; i++) {
                final String expr = argv[i];
                final XPath xpath = new XPath(expr, symbols, null);
                final XPathMatcher matcher = new XPathMatcher(xpath, true);
                com.sun.org.apache.xerces.internal.parsers.SAXParser parser =
                    new com.sun.org.apache.xerces.internal.parsers.SAXParser(symbols) {
                    public void startDocument() throws XNIException {
                        matcher.startDocumentFragment(symbols, null);
                    }
                    public void startElement(QName element, XMLAttrList attributes, int handle) throws XNIException {
                        matcher.startElement(element, attributes, handle);
                    }
                    public void characters(char[] ch, int offset, int length) throws XNIException {
                        matcher.characters(ch, offset, length);
                    }
                    public void endElement(QName element) throws XNIException {
                        matcher.endElement(element);
                    }
                    public void endDocument() throws XNIException {
                        matcher.endDocumentFragment();
                    }
                };
                System.out.println("#### argv["+i+"]: \""+expr+"\" -> \""+xpath.toString()+'"');
                final String uri = argv[++i];
                System.out.println("#### argv["+i+"]: "+uri);
                parser.parse(uri);
            }
        }

    } // main(String[])
    /***/

} // class XPathMatcher