1/* 2 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org> 3 * Copyright (C) 2006, 2009 Apple Inc. 4 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org> 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 */ 27 28#include "config.h" 29#include "core/xml/XPathPath.h" 30 31#include "core/dom/Document.h" 32#include "core/dom/NodeTraversal.h" 33#include "core/xml/XPathPredicate.h" 34#include "core/xml/XPathStep.h" 35#include "core/xml/XPathValue.h" 36 37namespace blink { 38namespace XPath { 39 40Filter::Filter(PassOwnPtrWillBeRawPtr<Expression> expr, WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& predicates) 41 : m_expr(expr) 42{ 43 m_predicates.swap(predicates); 44 setIsContextNodeSensitive(m_expr->isContextNodeSensitive()); 45 setIsContextPositionSensitive(m_expr->isContextPositionSensitive()); 46 setIsContextSizeSensitive(m_expr->isContextSizeSensitive()); 47} 48 49Filter::~Filter() 50{ 51} 52 53void Filter::trace(Visitor* visitor) 54{ 55 visitor->trace(m_expr); 56 visitor->trace(m_predicates); 57 Expression::trace(visitor); 58} 59 60Value Filter::evaluate(EvaluationContext& evaluationContext) const 61{ 62 Value v = m_expr->evaluate(evaluationContext); 63 64 NodeSet& nodes = v.modifiableNodeSet(evaluationContext); 65 nodes.sort(); 66 67 for (unsigned i = 0; i < m_predicates.size(); i++) { 68 OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create()); 69 evaluationContext.size = nodes.size(); 70 evaluationContext.position = 0; 71 72 for (unsigned j = 0; j < nodes.size(); j++) { 73 Node* node = nodes[j]; 74 75 evaluationContext.node = node; 76 ++evaluationContext.position; 77 78 if (m_predicates[i]->evaluate(evaluationContext)) 79 newNodes->append(node); 80 } 81 nodes.swap(*newNodes); 82 } 83 84 return v; 85} 86 87LocationPath::LocationPath() 88 : m_absolute(false) 89{ 90 setIsContextNodeSensitive(true); 91} 92 93LocationPath::~LocationPath() 94{ 95#if !ENABLE(OILPAN) 96 deleteAllValues(m_steps); 97#endif 98} 99 100void LocationPath::trace(Visitor* visitor) 101{ 102#if ENABLE(OILPAN) 103 visitor->trace(m_steps); 104#endif 105 Expression::trace(visitor); 106} 107 108Value LocationPath::evaluate(EvaluationContext& evaluationContext) const 109{ 110 EvaluationContext clonedContext = evaluationContext; 111 // http://www.w3.org/TR/xpath/ 112 // Section 2, Location Paths: 113 // "/ selects the document root (which is always the parent of the document element)" 114 // "A / by itself selects the root node of the document containing the context node." 115 // In the case of a tree that is detached from the document, we violate 116 // the spec and treat / as the root node of the detached tree. 117 // This is for compatibility with Firefox, and also seems like a more 118 // logical treatment of where you would expect the "root" to be. 119 Node* context = evaluationContext.node.get(); 120 if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE) { 121 if (context->inDocument()) 122 context = context->ownerDocument(); 123 else 124 context = &NodeTraversal::highestAncestorOrSelf(*context); 125 } 126 127 OwnPtrWillBeRawPtr<NodeSet> nodes(NodeSet::create()); 128 nodes->append(context); 129 evaluate(clonedContext, *nodes); 130 131 return Value(nodes.release(), Value::adopt); 132} 133 134void LocationPath::evaluate(EvaluationContext& context, NodeSet& nodes) const 135{ 136 bool resultIsSorted = nodes.isSorted(); 137 138 for (unsigned i = 0; i < m_steps.size(); i++) { 139 Step* step = m_steps[i]; 140 OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create()); 141 WillBeHeapHashSet<RawPtrWillBeMember<Node> > newNodesSet; 142 143 bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis 144 && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis); 145 146 if (needToCheckForDuplicateNodes) 147 resultIsSorted = false; 148 149 // This is a simplified check that can be improved to handle more cases. 150 if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis)) 151 newNodes->markSubtreesDisjoint(true); 152 153 for (unsigned j = 0; j < nodes.size(); j++) { 154 OwnPtrWillBeRawPtr<NodeSet> matches(NodeSet::create()); 155 step->evaluate(context, nodes[j], *matches); 156 157 if (!matches->isSorted()) 158 resultIsSorted = false; 159 160 for (size_t nodeIndex = 0; nodeIndex < matches->size(); ++nodeIndex) { 161 Node* node = (*matches)[nodeIndex]; 162 if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry) 163 newNodes->append(node); 164 } 165 } 166 167 nodes.swap(*newNodes); 168 } 169 170 nodes.markSorted(resultIsSorted); 171} 172 173void LocationPath::appendStep(Step* step) 174{ 175 unsigned stepCount = m_steps.size(); 176 if (stepCount) { 177 bool dropSecondStep; 178 optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep); 179 if (dropSecondStep) { 180#if !ENABLE(OILPAN) 181 delete step; 182#endif 183 return; 184 } 185 } 186 step->optimize(); 187 m_steps.append(step); 188} 189 190void LocationPath::insertFirstStep(Step* step) 191{ 192 if (m_steps.size()) { 193 bool dropSecondStep; 194 optimizeStepPair(step, m_steps[0], dropSecondStep); 195 if (dropSecondStep) { 196#if !ENABLE(OILPAN) 197 delete m_steps[0]; 198#endif 199 m_steps[0] = step; 200 return; 201 } 202 } 203 step->optimize(); 204 m_steps.insert(0, step); 205} 206 207Path::Path(Expression* filter, LocationPath* path) 208 : m_filter(adoptPtrWillBeNoop(filter)) 209 , m_path(adoptPtrWillBeNoop(path)) 210{ 211 setIsContextNodeSensitive(filter->isContextNodeSensitive()); 212 setIsContextPositionSensitive(filter->isContextPositionSensitive()); 213 setIsContextSizeSensitive(filter->isContextSizeSensitive()); 214} 215 216Path::~Path() 217{ 218} 219 220void Path::trace(Visitor* visitor) 221{ 222 visitor->trace(m_filter); 223 visitor->trace(m_path); 224 Expression::trace(visitor); 225} 226 227Value Path::evaluate(EvaluationContext& context) const 228{ 229 Value v = m_filter->evaluate(context); 230 231 NodeSet& nodes = v.modifiableNodeSet(context); 232 m_path->evaluate(context, nodes); 233 234 return v; 235} 236 237} 238} 239