Source/core/xml/XPathPath.cpp

/*
 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
 * Copyright (C) 2006, 2009 Apple Inc.
 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
 *
 * 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS 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 AUTHOR 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.
 */

#include "config.h"
#include "core/xml/XPathPath.h"

#include "core/dom/Document.h"
#include "core/xml/XPathPredicate.h"
#include "core/xml/XPathStep.h"
#include "core/xml/XPathValue.h"

namespace WebCore {
namespace XPath {

Filter::Filter(Expression* expr, const Vector<Predicate*>& predicates)
    : m_expr(expr), m_predicates(predicates)
{
    setIsContextNodeSensitive(m_expr->isContextNodeSensitive());
    setIsContextPositionSensitive(m_expr->isContextPositionSensitive());
    setIsContextSizeSensitive(m_expr->isContextSizeSensitive());
}

Filter::~Filter()
{
    delete m_expr;
    deleteAllValues(m_predicates);
}

Value Filter::evaluate() const
{
    Value v = m_expr->evaluate();

    NodeSet& nodes = v.modifiableNodeSet();
    nodes.sort();

    EvaluationContext& evaluationContext = Expression::evaluationContext();
    for (unsigned i = 0; i < m_predicates.size(); i++) {
        NodeSet newNodes;
        evaluationContext.size = nodes.size();
        evaluationContext.position = 0;

        for (unsigned j = 0; j < nodes.size(); j++) {
            Node* node = nodes[j];

            evaluationContext.node = node;
            ++evaluationContext.position;

            if (m_predicates[i]->evaluate())
                newNodes.append(node);
        }
        nodes.swap(newNodes);
    }

    return v;
}

LocationPath::LocationPath()
    : m_absolute(false)
{
    setIsContextNodeSensitive(true);
}

LocationPath::~LocationPath()
{
    deleteAllValues(m_steps);
}

Value LocationPath::evaluate() const
{
    EvaluationContext& evaluationContext = Expression::evaluationContext();
    EvaluationContext backupContext = evaluationContext;
    // http://www.w3.org/TR/xpath/
    // Section 2, Location Paths:
    // "/ selects the document root (which is always the parent of the document element)"
    // "A / by itself selects the root node of the document containing the context node."
    // In the case of a tree that is detached from the document, we violate
    // the spec and treat / as the root node of the detached tree.
    // This is for compatibility with Firefox, and also seems like a more
    // logical treatment of where you would expect the "root" to be.
    Node* context = evaluationContext.node.get();
    if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)  {
        if (context->inDocument())
            context = context->ownerDocument();
        else
            context = context->highestAncestor();
    }

    NodeSet nodes;
    nodes.append(context);
    evaluate(nodes);

    evaluationContext = backupContext;
    return Value(nodes, Value::adopt);
}

void LocationPath::evaluate(NodeSet& nodes) const
{
    bool resultIsSorted = nodes.isSorted();

    for (unsigned i = 0; i < m_steps.size(); i++) {
        Step* step = m_steps[i];
        NodeSet newNodes;
        HashSet<Node*> newNodesSet;

        bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis
            && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis);

        if (needToCheckForDuplicateNodes)
            resultIsSorted = false;

        // This is a simplified check that can be improved to handle more cases.
        if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis))
            newNodes.markSubtreesDisjoint(true);

        for (unsigned j = 0; j < nodes.size(); j++) {
            NodeSet matches;
            step->evaluate(nodes[j], matches);

            if (!matches.isSorted())
                resultIsSorted = false;

            for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) {
                Node* node = matches[nodeIndex];
                if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry)
                    newNodes.append(node);
            }
        }

        nodes.swap(newNodes);
    }

    nodes.markSorted(resultIsSorted);
}

void LocationPath::appendStep(Step* step)
{
    unsigned stepCount = m_steps.size();
    if (stepCount) {
        bool dropSecondStep;
        optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep);
        if (dropSecondStep) {
            delete step;
            return;
        }
    }
    step->optimize();
    m_steps.append(step);
}

void LocationPath::insertFirstStep(Step* step)
{
    if (m_steps.size()) {
        bool dropSecondStep;
        optimizeStepPair(step, m_steps[0], dropSecondStep);
        if (dropSecondStep) {
            delete m_steps[0];
            m_steps[0] = step;
            return;
        }
    }
    step->optimize();
    m_steps.insert(0, step);
}

Path::Path(Filter* filter, LocationPath* path)
    : m_filter(filter)
    , m_path(path)
{
    setIsContextNodeSensitive(filter->isContextNodeSensitive());
    setIsContextPositionSensitive(filter->isContextPositionSensitive());
    setIsContextSizeSensitive(filter->isContextSizeSensitive());
}

Path::~Path()
{
    delete m_filter;
    delete m_path;
}

Value Path::evaluate() const
{
    Value v = m_filter->evaluate();

    NodeSet& nodes = v.modifiableNodeSet();
    m_path->evaluate(nodes);

    return v;
}

}
}