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 "XPathPath.h" 30 31#include "Document.h" 32#include "XPathPredicate.h" 33#include "XPathStep.h" 34#include "XPathValue.h" 35 36namespace WebCore { 37namespace XPath { 38 39Filter::Filter(Expression* expr, const Vector<Predicate*>& predicates) 40 : m_expr(expr), m_predicates(predicates) 41{ 42 setIsContextNodeSensitive(m_expr->isContextNodeSensitive()); 43 setIsContextPositionSensitive(m_expr->isContextPositionSensitive()); 44 setIsContextSizeSensitive(m_expr->isContextSizeSensitive()); 45} 46 47Filter::~Filter() 48{ 49 delete m_expr; 50 deleteAllValues(m_predicates); 51} 52 53Value Filter::evaluate() const 54{ 55 Value v = m_expr->evaluate(); 56 57 NodeSet& nodes = v.modifiableNodeSet(); 58 nodes.sort(); 59 60 EvaluationContext& evaluationContext = Expression::evaluationContext(); 61 for (unsigned i = 0; i < m_predicates.size(); i++) { 62 NodeSet newNodes; 63 evaluationContext.size = nodes.size(); 64 evaluationContext.position = 0; 65 66 for (unsigned j = 0; j < nodes.size(); j++) { 67 Node* node = nodes[j]; 68 69 evaluationContext.node = node; 70 ++evaluationContext.position; 71 72 if (m_predicates[i]->evaluate()) 73 newNodes.append(node); 74 } 75 nodes.swap(newNodes); 76 } 77 78 return v; 79} 80 81LocationPath::LocationPath() 82 : m_absolute(false) 83{ 84 setIsContextNodeSensitive(true); 85} 86 87LocationPath::~LocationPath() 88{ 89 deleteAllValues(m_steps); 90} 91 92Value LocationPath::evaluate() const 93{ 94 EvaluationContext& evaluationContext = Expression::evaluationContext(); 95 EvaluationContext backupContext = evaluationContext; 96 // http://www.w3.org/TR/xpath/ 97 // Section 2, Location Paths: 98 // "/ selects the document root (which is always the parent of the document element)" 99 // "A / by itself selects the root node of the document containing the context node." 100 // In the case of a tree that is detached from the document, we violate 101 // the spec and treat / as the root node of the detached tree. 102 // This is for compatibility with Firefox, and also seems like a more 103 // logical treatment of where you would expect the "root" to be. 104 Node* context = evaluationContext.node.get(); 105 if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE) { 106 if (context->inDocument()) 107 context = context->ownerDocument(); 108 else 109 context = context->highestAncestor(); 110 } 111 112 NodeSet nodes; 113 nodes.append(context); 114 evaluate(nodes); 115 116 evaluationContext = backupContext; 117 return Value(nodes, Value::adopt); 118} 119 120void LocationPath::evaluate(NodeSet& nodes) const 121{ 122 bool resultIsSorted = nodes.isSorted(); 123 124 for (unsigned i = 0; i < m_steps.size(); i++) { 125 Step* step = m_steps[i]; 126 NodeSet newNodes; 127 HashSet<Node*> newNodesSet; 128 129 bool needToCheckForDuplicateNodes = !nodes.subtreesAreDisjoint() || (step->axis() != Step::ChildAxis && step->axis() != Step::SelfAxis 130 && step->axis() != Step::DescendantAxis && step->axis() != Step::DescendantOrSelfAxis && step->axis() != Step::AttributeAxis); 131 132 if (needToCheckForDuplicateNodes) 133 resultIsSorted = false; 134 135 // This is a simplified check that can be improved to handle more cases. 136 if (nodes.subtreesAreDisjoint() && (step->axis() == Step::ChildAxis || step->axis() == Step::SelfAxis)) 137 newNodes.markSubtreesDisjoint(true); 138 139 for (unsigned j = 0; j < nodes.size(); j++) { 140 NodeSet matches; 141 step->evaluate(nodes[j], matches); 142 143 if (!matches.isSorted()) 144 resultIsSorted = false; 145 146 for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) { 147 Node* node = matches[nodeIndex]; 148 if (!needToCheckForDuplicateNodes || newNodesSet.add(node).isNewEntry) 149 newNodes.append(node); 150 } 151 } 152 153 nodes.swap(newNodes); 154 } 155 156 nodes.markSorted(resultIsSorted); 157} 158 159void LocationPath::appendStep(Step* step) 160{ 161 unsigned stepCount = m_steps.size(); 162 if (stepCount) { 163 bool dropSecondStep; 164 optimizeStepPair(m_steps[stepCount - 1], step, dropSecondStep); 165 if (dropSecondStep) { 166 delete step; 167 return; 168 } 169 } 170 step->optimize(); 171 m_steps.append(step); 172} 173 174void LocationPath::insertFirstStep(Step* step) 175{ 176 if (m_steps.size()) { 177 bool dropSecondStep; 178 optimizeStepPair(step, m_steps[0], dropSecondStep); 179 if (dropSecondStep) { 180 delete m_steps[0]; 181 m_steps[0] = step; 182 return; 183 } 184 } 185 step->optimize(); 186 m_steps.insert(0, step); 187} 188 189Path::Path(Filter* filter, LocationPath* path) 190 : m_filter(filter) 191 , m_path(path) 192{ 193 setIsContextNodeSensitive(filter->isContextNodeSensitive()); 194 setIsContextPositionSensitive(filter->isContextPositionSensitive()); 195 setIsContextSizeSensitive(filter->isContextSizeSensitive()); 196} 197 198Path::~Path() 199{ 200 delete m_filter; 201 delete m_path; 202} 203 204Value Path::evaluate() const 205{ 206 Value v = m_filter->evaluate(); 207 208 NodeSet& nodes = v.modifiableNodeSet(); 209 m_path->evaluate(nodes); 210 211 return v; 212} 213 214} 215} 216