/*
 * Copyright 1999-2004 The Apache Software Foundation
 *
 * Licensed 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 org.apache.commons.jxpath.ri.axes;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.apache.commons.jxpath.JXPathException;
import org.apache.commons.jxpath.ri.Compiler;
import org.apache.commons.jxpath.ri.EvalContext;
import org.apache.commons.jxpath.ri.InfoSetUtil;
import org.apache.commons.jxpath.ri.QName;
import org.apache.commons.jxpath.ri.compiler.Expression;
import org.apache.commons.jxpath.ri.compiler.NameAttributeTest;
import org.apache.commons.jxpath.ri.compiler.NodeNameTest;
import org.apache.commons.jxpath.ri.compiler.NodeTest;
import org.apache.commons.jxpath.ri.compiler.Step;
import org.apache.commons.jxpath.ri.model.NodeIterator;
import org.apache.commons.jxpath.ri.model.NodePointer;
import org.apache.commons.jxpath.ri.model.beans.LangAttributePointer;
import org.apache.commons.jxpath.ri.model.beans.NullElementPointer;
import org.apache.commons.jxpath.ri.model.beans.NullPropertyPointer;
import org.apache.commons.jxpath.ri.model.beans.PropertyOwnerPointer;
import org.apache.commons.jxpath.ri.model.beans.PropertyPointer;

/**
 * An evaluation mechanism for simple XPaths, which
 * is much faster than the usual process. It is only used for
 * xpaths which have no context-dependent parts, consist entirely of
 * <code>child::name</code> and <code>self::node()</code> steps with
 * predicates that either integer or have the form <code>[@name = ...]</code>.
 *
 * @author Dmitri Plotnikov
 * @version $Revision: 1.10 $ $Date: 2002/04/24 04:05:40 $
 */
public class SimplePathInterpreter {

    // Because of the complexity caused by the variety of situations
    // that need to be addressed by this class, we attempt to break up
    // the class into individual methods addressing those situations
    // individually.  The names of the methods are supposed to
    // give brief descriptions of those situations.

    private static final QName QNAME_NAME = new QName(null, "name");
    private static final int PERFECT_MATCH = 1000;

    // Uncomment this variable and the PATH = ... lines in
    // the two following methods in order to be able to print the
    // currently evaluated path for debugging of this class
//    private static String PATH;       // Debugging

    /**
     * Interpret a simple path that starts with the given root and
     * follows the given steps. All steps must have the axis "child::"
     * and a name test.  They can also optionally have predicates
     * of type [@name=expression] or simply [expression] interpreted
     * as an index.
     */
    public static NodePointer interpretSimpleLocationPath(
            EvalContext context, NodePointer root, Step steps[])
    {
//        PATH = createNullPointer(context, root, steps, 0).toString();  // Dbg
        NodePointer pointer = doStep(context, root, steps, 0);
//        return valuePointer(pointer);
        return pointer;
    }

    /**
     * Interpret the steps of a simple expression path that
     * starts with the given root, which is the result of evaluation
     * of the root expression of the expression path, applies the
     * given predicates to it and then follows the given steps.
     * All steps must have the axis "child::" or "attribute::"
     * and a name test.  They can also optionally have predicates
     * of type [@name=...] or simply [...] interpreted as an index.
     */
    public static NodePointer interpretSimpleExpressionPath(
                EvalContext context, NodePointer root,
                Expression predicates[], Step[] steps)
    {
//        PATH = createNullPointerForPredicates(context, root,
//                    steps, -1, predicates, 0).toString();  // Debugging
        NodePointer pointer =
            doPredicate(context, root, steps, -1, predicates, 0);
//        return valuePointer(pointer);
        return pointer;
    }

    /**
     * Recursive evaluation of a path. The general plan is:
     * Look at the current step,
     * find nodes that match it,
     * iterate over those nodes and
     * for each of them call doStep again for subsequent steps.
     */
    private static NodePointer doStep(
            EvalContext context, NodePointer parent,
            Step steps[], int currentStep)
    {
        if (parent == null) {
            return null;
        }

        if (currentStep == steps.length) {
            // We have reached the end of the list of steps
            return parent;
        }

        // Open all containers
        parent = valuePointer(parent);
        
        Step step = steps[currentStep];
        Expression predicates[] = step.getPredicates();

        // Divide and conquer: the process is broken out into
        // four major use cases.
        // 1. Current step has no predicates and
        //    the root is a property owner (e.g. bean or map)
        // 2. Current step has predicates and
        //    the root is a property owner (e.g. bean or map)
        // 3. Current step has no predicates and
        //    the root is an InfoSet standard node (e.g. DOM Node)
        // 4. Current step has predicates and
        //    the root is an InfoSet standard node (e.g. DOM Node)

        if (parent instanceof PropertyOwnerPointer) {
            if (predicates == null || predicates.length == 0) {
                return doStepNoPredicatesPropertyOwner(
                    context,
                    (PropertyOwnerPointer) parent,
                    steps,
                    currentStep);
            }
            else {
                return doStepPredicatesPropertyOwner(
                    context,
                    (PropertyOwnerPointer) parent,
                    steps,
                    currentStep);
            }
        }
        else {
            if (predicates == null || predicates.length == 0) {
                return doStepNoPredicatesStandard(
                    context,
                    parent,
                    steps,
                    currentStep);
            }
            else {
                return doStepPredicatesStandard(
                    context,
                    parent,
                    steps,
                    currentStep);
            }
        }
    }

    /**
     * We have a step that starts with a property owner (bean, map, etc) and has
     * no predicates.  The name test of the step may map to a scalar property
     * or to a collection.  If it is a collection, we should apply the tail of
     * the path to each element until we find a match. If we don't find
     * a perfect match, we should return the "best quality" pointer, which
     * has the longest chain of steps mapping to existing nodes and the shortes
     * tail of Null* pointers.
     */
    private static NodePointer doStepNoPredicatesPropertyOwner(
                EvalContext context, PropertyOwnerPointer parentPointer,
                Step[] steps, int currentStep)
    {
        Step step = steps[currentStep];
        NodePointer childPointer =
            createChildPointerForStep(parentPointer, step);

        if (!childPointer.isActual()) {
            // The property does not exist - create a null pointer.
            return createNullPointer(
                context,
                parentPointer,
                steps,
                currentStep);
        }
        else if (currentStep == steps.length - 1) {
            // If this is the last step - we are done, we found it
            return childPointer;
        }
        else if (childPointer.isCollection()) {
            // Iterate over all values and
            // execute remaining steps for each node,
            // looking for the best quality match
            int bestQuality = 0;
            childPointer = (NodePointer) childPointer.clone();
            NodePointer bestMatch = null;
            int count = childPointer.getLength();
            for (int i = 0; i < count; i++) {
                childPointer.setIndex(i);
                NodePointer pointer =
                    doStep(context, childPointer, steps, currentStep + 1);
                int quality = computeQuality(pointer);
                if (quality == PERFECT_MATCH) {
                    return pointer;
                }
                else if (quality > bestQuality) {
                    bestQuality = quality;
                    bestMatch = (NodePointer) pointer.clone();
                }
            }
            if (bestMatch != null) {
                return bestMatch;
            }
            // This step did not find anything - return a null pointer
            return createNullPointer(context, childPointer, steps, currentStep);
        }
        else {
            // Evaluate subsequent steps
            return doStep(context, childPointer, steps, currentStep + 1);
        }
    }

    /**
     * A path that starts with a standard InfoSet node (e.g. DOM Node) and
     * has no predicates.  Get a child iterator and apply the tail of
     * the path to each element until we find a match. If we don't find
     * a perfect match, we should return the "best quality" pointer, which
     * has the longest chain of steps mapping to existing nodes and the shortes
     * tail of Null* pointers.
     */
    private static NodePointer doStepNoPredicatesStandard(
                EvalContext context, NodePointer parentPointer,
                Step[] steps, int currentStep)
    {
        Step step = steps[currentStep];

        if (step.getAxis() == Compiler.AXIS_SELF) {
            return doStep(context, parentPointer, steps, currentStep + 1);
        }

        int bestQuality = 0;
        NodePointer bestMatch = null;
        NodeIterator it = getNodeIterator(context, parentPointer, step);
        if (it != null) {
            for (int i = 1; it.setPosition(i); i++) {
                NodePointer childPointer = it.getNodePointer();
                if (steps.length == currentStep + 1) {
                    // If this is the last step - we are done, we found it
                    return childPointer;
                }
                NodePointer pointer = doStep(
                        context, childPointer, steps, currentStep + 1);
                int quality = computeQuality(pointer);
                if (quality == PERFECT_MATCH) {
                    return pointer;
                }
                else if (quality > bestQuality) {
                    bestQuality = quality;
                    bestMatch = (NodePointer) pointer.clone();
                }
            }
        }

        if (bestMatch != null) {
            return bestMatch;
        }

        return createNullPointer(
                context, parentPointer, steps, currentStep);
    }

    /**
     * A path that starts with a property owner. The method evaluates
     * the first predicate in a special way and then forwards to
     * a general predicate processing method.
     */
    private static NodePointer doStepPredicatesPropertyOwner(
            EvalContext context, PropertyOwnerPointer parentPointer,
            Step[] steps, int currentStep)
    {
        Step step = steps[currentStep];
        Expression predicates[] = step.getPredicates();

        NodePointer childPointer =
            createChildPointerForStep(parentPointer, step);
        if (!childPointer.isActual()) {
            // Property does not exist - return a null pointer
            return createNullPointer(
                context,
                parentPointer,
                steps,
                currentStep);
        }

        // Evaluate predicates
        return doPredicate(
            context,
            childPointer,
            steps,
            currentStep,
            predicates,
            0);
    }

    private static NodePointer createChildPointerForStep(
                PropertyOwnerPointer parentPointer, Step step)
    {
        int axis = step.getAxis();
        if (axis == Compiler.AXIS_CHILD || axis == Compiler.AXIS_ATTRIBUTE) {
            NodePointer childPointer;
            QName name = ((NodeNameTest) step.getNodeTest()).getNodeName();
            if (axis == Compiler.AXIS_ATTRIBUTE && isLangAttribute(name)) {
                childPointer = new LangAttributePointer(parentPointer);
            }
            else {
                childPointer = parentPointer.getPropertyPointer();
                ((PropertyPointer) childPointer).setPropertyName(
                    name.toString());
                childPointer.setAttribute(axis == Compiler.AXIS_ATTRIBUTE);
            }
            return childPointer;
        }
        else {
            return parentPointer;
        }
    }

    /**
     * A path that starts with a standard InfoSet node, e.g. a DOM Node.
     * The method evaluates the first predicate in a special way and
     * then forwards to a general predicate processing method.
     */
    private static NodePointer doStepPredicatesStandard(
            EvalContext context, NodePointer parent,
            Step[] steps, int currentStep)
    {
        Step step = steps[currentStep];
        Expression predicates[] = step.getPredicates();

        int axis = step.getAxis();
        if (axis == Compiler.AXIS_SELF) {
            return doPredicate(
                context,
                parent,
                steps,
                currentStep,
                predicates,
                0);
        }

        Expression predicate = predicates[0];

        // Optimize for a single predicate to avoid building a list
        // and to allow the direct access to the index'th element
        // in the case of a simple subscript predecate
        // It is a very common use case, so it deserves individual
        // attention
        if (predicates.length == 1) {
            NodeIterator it = getNodeIterator(context, parent, step);
            NodePointer pointer = null;
            if (it != null) {
                if (predicate instanceof NameAttributeTest) { // [@name = key]
                    String key = keyFromPredicate(context, predicate);
                    for (int i = 1; it.setPosition(i); i++) {
                        NodePointer ptr = it.getNodePointer();
                        if (isNameAttributeEqual(ptr, key)) {
                            pointer = ptr;
                            break;
                        }
                    }
                }
                else {
                    int index = indexFromPredicate(context, predicate);
                    if (it.setPosition(index + 1)) {
                        pointer = it.getNodePointer();
                    }
                }
            }
            if (pointer != null) {
                return doStep(context, pointer, steps, currentStep + 1);
            }
        }
        else {
            NodeIterator it = getNodeIterator(context, parent, step);
            if (it != null) {
                List list = new ArrayList();
                for (int i = 1; it.setPosition(i); i++) {
                    list.add(it.getNodePointer());
                }
                NodePointer pointer =
                    doPredicatesStandard(
                        context,
                        list,
                        steps,
                        currentStep,
                        predicates,
                        0);
                if (pointer != null) {
                    return pointer;
                }
            }
        }
        return createNullPointer(context, parent, steps, currentStep);
    }

    /**
     * Evaluates predicates and proceeds with the subsequent steps
     * of the path.
     */
    private static NodePointer doPredicate(
                EvalContext context, NodePointer parent,
                Step[] steps, int currentStep,
                Expression predicates[], int currentPredicate)
    {
        if (currentPredicate == predicates.length) {
            return doStep(context, parent, steps, currentStep + 1);
        }

        Expression predicate = predicates[currentPredicate];
        if (predicate instanceof NameAttributeTest) { // [@name = key1]
            return doPredicateName(
                context,
                parent,
                steps,
                currentStep,
                predicates,
                currentPredicate);
        }
        else { // [index]
            return doPredicateIndex(
                context,
                parent,
                steps,
                currentStep,
                predicates,
                currentPredicate);
        }
    }

    private static NodePointer doPredicateName(
            EvalContext context, NodePointer parent,
            Step[] steps, int currentStep,
            Expression[] predicates, int currentPredicate)
    {
        Expression predicate = predicates[currentPredicate];
        String key = keyFromPredicate(context, predicate);
        NodePointer child = valuePointer(parent);
        if (child instanceof PropertyOwnerPointer) {
            PropertyPointer pointer =
                ((PropertyOwnerPointer) child).getPropertyPointer();
            pointer.setPropertyName(key);
            if (pointer.isActual()) {
                return doPredicate(
                    context,
                    pointer,
                    steps,
                    currentStep,
                    predicates,
                    currentPredicate + 1);
            }
        }
        else if (child.isCollection()) {
            // For each node in the collection, perform the following:
            // if the node is a property owner, apply this predicate to it;
            // if the node is a collection, apply this predicate to each elem.;
            // if the node is not a prop owner or a collection,
            //  see if it has the attribute "name" with the right value,
            //  if so - proceed to the next predicate
            NodePointer bestMatch = null;
            int bestQuality = 0;
            child = (NodePointer) child.clone();
            int count = child.getLength();
            for (int i = 0; i < count; i++) {
                child.setIndex(i);
                NodePointer valuePointer = valuePointer(child);
                NodePointer pointer;
                if ((valuePointer instanceof PropertyOwnerPointer)
                    || valuePointer.isCollection()) {
                    pointer =
                        doPredicateName(
                            context,
                            valuePointer,
                            steps,
                            currentStep,
                            predicates,
                            currentPredicate);
                }
                else if (isNameAttributeEqual(valuePointer, key)) {
                    pointer =
                        doPredicate(
                            context,
                            valuePointer,
                            steps,
                            currentStep,
                            predicates,
                            currentPredicate + 1);
                }
                else {
                    pointer = null;
                }
                if (pointer != null) {
                    int quality = computeQuality(pointer);
                    if (quality == PERFECT_MATCH) {
                        return pointer;
                    }
                    if (quality > bestQuality) {
                        bestMatch = (NodePointer) pointer.clone();
                        bestQuality = quality;
                    }
                }
            }
            if (bestMatch != null) {
                return bestMatch;
            }
        }
        else {
            // If the node is a standard InfoSet node (e.g. DOM Node),
            // employ doPredicates_standard, which will iterate through
            // the node's children and apply all predicates
            NodePointer found =
                doPredicatesStandard(
                    context,
                    Collections.singletonList(child),
                    steps,
                    currentStep,
                    predicates,
                    currentPredicate);
            if (found != null) {
                return found;
            }
        }
        // If nothing worked - return a null pointer
        return createNullPointerForPredicates(
            context,
            child,
            steps,
            currentStep,
            predicates,
            currentPredicate);
    }

    /**
     * Called exclusively for standard InfoSet nodes, e.g. DOM nodes
     * to evaluate predicate sequences like [@name=...][@name=...][index].
     */
    private static NodePointer doPredicatesStandard(
                EvalContext context, List parents,
                Step[] steps, int currentStep,
                Expression predicates[], int currentPredicate)
    {
        if (parents.size() == 0) {
            return null;
        }

        // If all predicates have been processed, take the first
        // element from the list of results and proceed to the
        // remaining steps with that element.
        if (currentPredicate == predicates.length) {
            NodePointer pointer = (NodePointer) parents.get(0);
            return doStep(context, pointer, steps, currentStep + 1);
        }

        Expression predicate = predicates[currentPredicate];
        if (predicate instanceof NameAttributeTest) {
            String key = keyFromPredicate(context, predicate);
            List newList = new ArrayList();
            for (int i = 0; i < parents.size(); i++) {
                NodePointer pointer = (NodePointer) parents.get(i);
                if (isNameAttributeEqual(pointer, key)) {
                    newList.add(pointer);
                }
            }
            if (newList.size() == 0) {
                return null;
            }
            return doPredicatesStandard(
                context,
                newList,
                steps,
                currentStep,
                predicates,
                currentPredicate + 1);
        }
        else {
            // For a subscript, simply take the corresponding
            // element from the list of results and
            // proceed to the remaining predicates with that element
            int index = indexFromPredicate(context, predicate);
            if (index < 0 || index >= parents.size()) {
                return null;
            }
            NodePointer ptr = (NodePointer) parents.get(index);
            return doPredicate(
                context,
                ptr,
                steps,
                currentStep,
                predicates,
                currentPredicate + 1);
        }
    }

    /**
     * Evaluate a subscript predicate: see if the node is a collection and
     * if the index is inside the collection
     */
    private static NodePointer doPredicateIndex(
            EvalContext context, NodePointer parent,
            Step[] steps, int currentStep,
            Expression[] predicates, int currentPredicate)
    {
        Expression predicate = predicates[currentPredicate];
        int index = indexFromPredicate(context, predicate);
        NodePointer pointer = parent;
        if (isCollectionElement(pointer, index)) {
            pointer = (NodePointer) pointer.clone();
            pointer.setIndex(index);
            return doPredicate(
                context,
                pointer,
                steps,
                currentStep,
                predicates,
                currentPredicate + 1);
        }
        return createNullPointerForPredicates(
            context,
            parent,
            steps,
            currentStep,
            predicates,
            currentPredicate);
    }

    /**
     * Extract an integer from a subscript predicate. The returned index
     * starts with 0, even though the subscript starts with 1.
     */
    private static int indexFromPredicate(
        EvalContext context,
        Expression predicate) 
    {
        Object value = predicate.computeValue(context);
        if (value instanceof EvalContext) {
            value = ((EvalContext) value).getSingleNodePointer();
        }
        if (value instanceof NodePointer) {
            value = ((NodePointer) value).getValue();
        }
        if (value == null) {
            throw new JXPathException("Predicate value is null");
        }

        if (value instanceof Number) {
            return (int) (InfoSetUtil.doubleValue(value) + 0.5) - 1;
        }
        else if (InfoSetUtil.booleanValue(value)) {
            return 0;
        }

        return -1;
    }

    /**
     * Extracts the string value of the expression from a predicate like
     * [@name=expression].
     */
    private static String keyFromPredicate(EvalContext context,
                Expression predicate) 
    {
        Expression expr =
            ((NameAttributeTest) predicate).getNameTestExpression();
        return InfoSetUtil.stringValue(expr.computeValue(context));
    }

    /**
     * For a pointer that matches an actual node, returns 0.
     * For a pointer that does not match an actual node, but whose
     * parent pointer does returns -1, etc.
     */
    private static int computeQuality(NodePointer pointer) {
        int quality = PERFECT_MATCH;
        while (pointer != null && !pointer.isActual()) {
            quality--;
            pointer = pointer.getImmediateParentPointer();
        }
        return quality;
    }

    /**
     * Returns true if the pointer has an attribute called "name" and
     * its value is equal to the supplied string.
     */
    private static boolean isNameAttributeEqual(
        NodePointer pointer,
        String name) 
    {
        NodeIterator it = pointer.attributeIterator(QNAME_NAME);
        return it != null
            && it.setPosition(1)
            && name.equals(it.getNodePointer().getValue());
    }

    /**
     * Returns true if the pointer is a collection and the index is
     * withing the bounds of the collection.
     */
    private static boolean isCollectionElement(
        NodePointer pointer,
        int index) 
    {
        return pointer.isActual()
            && (index == 0
                || (pointer.isCollection()
                    && index >= 0
                    && index < pointer.getLength()));
    }

    /**
     * For an intermediate pointer (e.g. PropertyPointer, ContainerPointer)
     * returns a pointer for the contained value.
     */
    private static NodePointer valuePointer(NodePointer pointer) {
        return pointer == null ? null : pointer.getValuePointer();
    }

    /**
     * Creates a "null pointer" that
     * a) represents the requested path and
     * b) can be used for creation of missing nodes in the path.
     */
    public static NodePointer createNullPointer(
            EvalContext context, NodePointer parent, Step[] steps,
            int currentStep)
    {
        if (currentStep == steps.length) {
            return parent;
        }

        parent = valuePointer(parent);

        Step step = steps[currentStep];

        int axis = step.getAxis();
        if (axis == Compiler.AXIS_CHILD || axis == Compiler.AXIS_ATTRIBUTE) {
            NullPropertyPointer pointer = new NullPropertyPointer(parent);
            QName name = ((NodeNameTest) step.getNodeTest()).getNodeName();
            pointer.setPropertyName(name.toString());
            pointer.setAttribute(axis == Compiler.AXIS_ATTRIBUTE);
            parent = pointer;
        }
        // else { it is self::node() }

        Expression predicates[] = step.getPredicates();
        return createNullPointerForPredicates(
            context,
            parent,
            steps,
            currentStep,
            predicates,
            0);
    }

    /**
     * Creates a "null pointer" that starts with predicates.
     */
    private static NodePointer createNullPointerForPredicates(
            EvalContext context, NodePointer parent,
            Step[] steps, int currentStep,
            Expression predicates[], int currentPredicate)
    {
        for (int i = currentPredicate; i < predicates.length; i++) {
            Expression predicate = predicates[i];
            if (predicate instanceof NameAttributeTest) {
                String key = keyFromPredicate(context, predicate);
                parent = valuePointer(parent);
                NullPropertyPointer pointer = new NullPropertyPointer(parent);
                pointer.setNameAttributeValue(key);
                parent = pointer;
            }
            else {
                int index = indexFromPredicate(context, predicate);
                if (parent instanceof NullPropertyPointer) {
                    parent.setIndex(index);
                }
                else {
                    parent = new NullElementPointer(parent, index);
                }
            }
        }
        // Proceed with the remaining steps
        return createNullPointer(
                    context, parent, steps, currentStep + 1);
    }

    private static NodeIterator getNodeIterator(
        EvalContext context,
        NodePointer pointer,
        Step step) 
    {
        if (step.getAxis() == Compiler.AXIS_CHILD) {
            NodeTest nodeTest = step.getNodeTest();
            QName qname = ((NodeNameTest) nodeTest).getNodeName();
            String prefix = qname.getPrefix();
            if (prefix != null) {
                String namespaceURI = context.getJXPathContext()
                        .getNamespaceURI(prefix);
                nodeTest = new NodeNameTest(qname, namespaceURI);

            }
            return pointer.childIterator(nodeTest, false, null);
        }
        else { // Compiler.AXIS_ATTRIBUTE
            if (!(step.getNodeTest() instanceof NodeNameTest)) {
                throw new UnsupportedOperationException(
                    "Not supported node test for attributes: "
                        + step.getNodeTest());
            }
            return pointer.attributeIterator(
                ((NodeNameTest) step.getNodeTest()).getNodeName());
        }
    }

    private static boolean isLangAttribute(QName name) {
        return name.getPrefix() != null
            && name.getPrefix().equals("xml")
            && name.getName().equals("lang");
    }
}