187 lines
6.2 KiB
C++
187 lines
6.2 KiB
C++
/*
|
|
* Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
|
|
* Copyright (C) 2006, 2009, 2013 Apple Inc. All rights reserved.
|
|
* 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 "XPathPath.h"
|
|
|
|
#include "Document.h"
|
|
#include "XPathPredicate.h"
|
|
#include "XPathStep.h"
|
|
|
|
namespace WebCore {
|
|
namespace XPath {
|
|
|
|
Filter::Filter(std::unique_ptr<Expression> expression, Vector<std::unique_ptr<Expression>> predicates)
|
|
: m_expression(WTFMove(expression)), m_predicates(WTFMove(predicates))
|
|
{
|
|
setIsContextNodeSensitive(m_expression->isContextNodeSensitive());
|
|
setIsContextPositionSensitive(m_expression->isContextPositionSensitive());
|
|
setIsContextSizeSensitive(m_expression->isContextSizeSensitive());
|
|
}
|
|
|
|
Value Filter::evaluate() const
|
|
{
|
|
Value result = m_expression->evaluate();
|
|
|
|
NodeSet& nodes = result.modifiableNodeSet();
|
|
nodes.sort();
|
|
|
|
EvaluationContext& evaluationContext = Expression::evaluationContext();
|
|
for (auto& predicate : m_predicates) {
|
|
NodeSet newNodes;
|
|
evaluationContext.size = nodes.size();
|
|
evaluationContext.position = 0;
|
|
|
|
for (auto& node : nodes) {
|
|
evaluationContext.node = node;
|
|
++evaluationContext.position;
|
|
|
|
if (evaluatePredicate(*predicate))
|
|
newNodes.append(node.copyRef());
|
|
}
|
|
nodes = WTFMove(newNodes);
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
LocationPath::LocationPath()
|
|
: m_isAbsolute(false)
|
|
{
|
|
setIsContextNodeSensitive(true);
|
|
}
|
|
|
|
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_isAbsolute && !context->isDocumentNode())
|
|
context = &context->rootNode();
|
|
|
|
NodeSet nodes;
|
|
nodes.append(context);
|
|
evaluate(nodes);
|
|
|
|
evaluationContext = backupContext;
|
|
return Value(WTFMove(nodes));
|
|
}
|
|
|
|
void LocationPath::evaluate(NodeSet& nodes) const
|
|
{
|
|
bool resultIsSorted = nodes.isSorted();
|
|
|
|
for (auto& step : m_steps) {
|
|
NodeSet newNodes;
|
|
HashSet<RefPtr<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 (auto& node : nodes) {
|
|
NodeSet matches;
|
|
step->evaluate(*node, matches);
|
|
|
|
if (!matches.isSorted())
|
|
resultIsSorted = false;
|
|
|
|
for (auto& match : matches) {
|
|
if (!needToCheckForDuplicateNodes || newNodesSet.add(match.get()).isNewEntry)
|
|
newNodes.append(match.copyRef());
|
|
}
|
|
}
|
|
|
|
nodes = WTFMove(newNodes);
|
|
}
|
|
|
|
nodes.markSorted(resultIsSorted);
|
|
}
|
|
|
|
void LocationPath::appendStep(std::unique_ptr<Step> step)
|
|
{
|
|
unsigned stepCount = m_steps.size();
|
|
if (stepCount) {
|
|
bool dropSecondStep;
|
|
optimizeStepPair(*m_steps[stepCount - 1], *step, dropSecondStep);
|
|
if (dropSecondStep)
|
|
return;
|
|
}
|
|
step->optimize();
|
|
m_steps.append(WTFMove(step));
|
|
}
|
|
|
|
void LocationPath::prependStep(std::unique_ptr<Step> step)
|
|
{
|
|
if (m_steps.size()) {
|
|
bool dropSecondStep;
|
|
optimizeStepPair(*step, *m_steps[0], dropSecondStep);
|
|
if (dropSecondStep) {
|
|
m_steps[0] = WTFMove(step);
|
|
return;
|
|
}
|
|
}
|
|
step->optimize();
|
|
m_steps.insert(0, WTFMove(step));
|
|
}
|
|
|
|
Path::Path(std::unique_ptr<Expression> filter, std::unique_ptr<LocationPath> path)
|
|
: m_filter(WTFMove(filter))
|
|
, m_path(WTFMove(path))
|
|
{
|
|
setIsContextNodeSensitive(m_filter->isContextNodeSensitive());
|
|
setIsContextPositionSensitive(m_filter->isContextPositionSensitive());
|
|
setIsContextSizeSensitive(m_filter->isContextSizeSensitive());
|
|
}
|
|
|
|
Value Path::evaluate() const
|
|
{
|
|
Value result = m_filter->evaluate();
|
|
|
|
NodeSet& nodes = result.modifiableNodeSet();
|
|
m_path->evaluate(nodes);
|
|
|
|
return result;
|
|
}
|
|
|
|
}
|
|
}
|