1/* 2 * Copyright (C) 2011 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Neither the name of Google Inc. nor the names of its 11 * contributors may be used to endorse or promote products derived from 12 * this software without specific prior written permission. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 */ 26 27#include "config.h" 28#include "core/dom/shadow/ContentDistributor.h" 29 30#include "core/dom/NodeTraversal.h" 31#include "core/dom/shadow/ElementShadow.h" 32#include "core/dom/shadow/ShadowRoot.h" 33#include "core/html/shadow/HTMLContentElement.h" 34#include "core/html/shadow/HTMLShadowElement.h" 35 36 37namespace WebCore { 38 39void ContentDistribution::swap(ContentDistribution& other) 40{ 41 m_nodes.swap(other.m_nodes); 42 m_indices.swap(other.m_indices); 43} 44 45void ContentDistribution::append(PassRefPtr<Node> node) 46{ 47 size_t size = m_nodes.size(); 48 m_indices.set(node.get(), size); 49 m_nodes.append(node); 50} 51 52size_t ContentDistribution::find(const Node* node) const 53{ 54 HashMap<const Node*, size_t>::const_iterator it = m_indices.find(node); 55 if (it == m_indices.end()) 56 return notFound; 57 58 return it.get()->value; 59} 60 61Node* ContentDistribution::nextTo(const Node* node) const 62{ 63 size_t index = find(node); 64 if (index == notFound || index + 1 == size()) 65 return 0; 66 return at(index + 1).get(); 67} 68 69Node* ContentDistribution::previousTo(const Node* node) const 70{ 71 size_t index = find(node); 72 if (index == notFound || !index) 73 return 0; 74 return at(index - 1).get(); 75} 76 77 78ScopeContentDistribution::ScopeContentDistribution() 79 : m_insertionPointAssignedTo(0) 80 , m_numberOfShadowElementChildren(0) 81 , m_numberOfContentElementChildren(0) 82 , m_numberOfElementShadowChildren(0) 83 , m_insertionPointListIsValid(false) 84{ 85} 86 87void ScopeContentDistribution::setInsertionPointAssignedTo(PassRefPtr<InsertionPoint> insertionPoint) 88{ 89 m_insertionPointAssignedTo = insertionPoint; 90} 91 92void ScopeContentDistribution::invalidateInsertionPointList() 93{ 94 m_insertionPointListIsValid = false; 95 m_insertionPointList.clear(); 96} 97 98const Vector<RefPtr<InsertionPoint> >& ScopeContentDistribution::ensureInsertionPointList(ShadowRoot* shadowRoot) 99{ 100 if (m_insertionPointListIsValid) 101 return m_insertionPointList; 102 103 m_insertionPointListIsValid = true; 104 ASSERT(m_insertionPointList.isEmpty()); 105 106 if (!shadowRoot->containsInsertionPoints()) 107 return m_insertionPointList; 108 109 for (Element* element = ElementTraversal::firstWithin(shadowRoot); element; element = ElementTraversal::next(element, shadowRoot)) { 110 if (element->isInsertionPoint()) 111 m_insertionPointList.append(toInsertionPoint(element)); 112 } 113 114 return m_insertionPointList; 115} 116 117void ScopeContentDistribution::registerInsertionPoint(InsertionPoint* point) 118{ 119 if (isHTMLShadowElement(point)) 120 ++m_numberOfShadowElementChildren; 121 else if (isHTMLContentElement(point)) 122 ++m_numberOfContentElementChildren; 123 else 124 ASSERT_NOT_REACHED(); 125 126 invalidateInsertionPointList(); 127} 128 129void ScopeContentDistribution::unregisterInsertionPoint(InsertionPoint* point) 130{ 131 if (isHTMLShadowElement(point)) 132 --m_numberOfShadowElementChildren; 133 else if (isHTMLContentElement(point)) 134 --m_numberOfContentElementChildren; 135 else 136 ASSERT_NOT_REACHED(); 137 138 ASSERT(m_numberOfContentElementChildren >= 0); 139 ASSERT(m_numberOfShadowElementChildren >= 0); 140 141 invalidateInsertionPointList(); 142} 143 144ContentDistributor::ContentDistributor() 145 : m_needsSelectFeatureSet(false) 146{ 147} 148 149ContentDistributor::~ContentDistributor() 150{ 151} 152 153InsertionPoint* ContentDistributor::findInsertionPointFor(const Node* key) const 154{ 155 return m_nodeToInsertionPoint.get(key); 156} 157 158void ContentDistributor::populate(Node* node, Vector<Node*>& pool) 159{ 160 node->lazyReattachIfAttached(); 161 162 if (!isActiveInsertionPoint(node)) { 163 pool.append(node); 164 return; 165 } 166 167 InsertionPoint* insertionPoint = toInsertionPoint(node); 168 if (insertionPoint->hasDistribution()) { 169 for (size_t i = 0; i < insertionPoint->size(); ++i) 170 populate(insertionPoint->at(i), pool); 171 } else { 172 for (Node* fallbackNode = insertionPoint->firstChild(); fallbackNode; fallbackNode = fallbackNode->nextSibling()) 173 pool.append(fallbackNode); 174 } 175} 176 177void ContentDistributor::distribute(Element* host) 178{ 179 Vector<Node*> pool; 180 for (Node* node = host->firstChild(); node; node = node->nextSibling()) 181 populate(node, pool); 182 183 host->setNeedsStyleRecalc(); 184 185 Vector<bool> distributed(pool.size()); 186 distributed.fill(false); 187 188 Vector<HTMLShadowElement*, 8> activeShadowInsertionPoints; 189 for (ShadowRoot* root = host->youngestShadowRoot(); root; root = root->olderShadowRoot()) { 190 HTMLShadowElement* firstActiveShadowInsertionPoint = 0; 191 192 if (ScopeContentDistribution* scope = root->scopeDistribution()) { 193 const Vector<RefPtr<InsertionPoint> >& insertionPoints = scope->ensureInsertionPointList(root); 194 for (size_t i = 0; i < insertionPoints.size(); ++i) { 195 InsertionPoint* point = insertionPoints[i].get(); 196 if (!point->isActive()) 197 continue; 198 199 if (isHTMLShadowElement(point)) { 200 if (!firstActiveShadowInsertionPoint) 201 firstActiveShadowInsertionPoint = toHTMLShadowElement(point); 202 } else { 203 distributeSelectionsTo(point, pool, distributed); 204 if (ElementShadow* shadow = shadowOfParentForDistribution(point)) 205 shadow->setNeedsDistributionRecalc(); 206 } 207 } 208 } 209 210 if (firstActiveShadowInsertionPoint) 211 activeShadowInsertionPoints.append(firstActiveShadowInsertionPoint); 212 } 213 214 for (size_t i = activeShadowInsertionPoints.size(); i > 0; --i) { 215 HTMLShadowElement* shadowElement = activeShadowInsertionPoints[i - 1]; 216 ShadowRoot* root = shadowElement->containingShadowRoot(); 217 ASSERT(root); 218 if (!shadowElement->shouldSelect()) { 219 if (root->olderShadowRoot()) 220 root->olderShadowRoot()->ensureScopeDistribution()->setInsertionPointAssignedTo(shadowElement); 221 } else if (root->olderShadowRoot()) { 222 distributeNodeChildrenTo(shadowElement, root->olderShadowRoot()); 223 root->olderShadowRoot()->ensureScopeDistribution()->setInsertionPointAssignedTo(shadowElement); 224 } else { 225 distributeSelectionsTo(shadowElement, pool, distributed); 226 } 227 if (ElementShadow* shadow = shadowOfParentForDistribution(shadowElement)) 228 shadow->setNeedsDistributionRecalc(); 229 } 230} 231 232void ContentDistributor::distributeSelectionsTo(InsertionPoint* insertionPoint, const Vector<Node*>& pool, Vector<bool>& distributed) 233{ 234 ContentDistribution distribution; 235 236 for (size_t i = 0; i < pool.size(); ++i) { 237 if (distributed[i]) 238 continue; 239 240 if (isHTMLContentElement(insertionPoint) && !toHTMLContentElement(insertionPoint)->canSelectNode(pool, i)) 241 continue; 242 243 Node* child = pool[i]; 244 distribution.append(child); 245 m_nodeToInsertionPoint.add(child, insertionPoint); 246 distributed[i] = true; 247 } 248 249 insertionPoint->lazyReattachIfAttached(); 250 insertionPoint->setDistribution(distribution); 251} 252 253void ContentDistributor::distributeNodeChildrenTo(InsertionPoint* insertionPoint, ContainerNode* containerNode) 254{ 255 ContentDistribution distribution; 256 for (Node* node = containerNode->firstChild(); node; node = node->nextSibling()) { 257 node->lazyReattachIfAttached(); 258 if (isActiveInsertionPoint(node)) { 259 InsertionPoint* innerInsertionPoint = toInsertionPoint(node); 260 if (innerInsertionPoint->hasDistribution()) { 261 for (size_t i = 0; i < innerInsertionPoint->size(); ++i) { 262 distribution.append(innerInsertionPoint->at(i)); 263 m_nodeToInsertionPoint.add(innerInsertionPoint->at(i), insertionPoint); 264 } 265 } else { 266 for (Node* child = innerInsertionPoint->firstChild(); child; child = child->nextSibling()) { 267 distribution.append(child); 268 m_nodeToInsertionPoint.add(child, insertionPoint); 269 } 270 } 271 } else { 272 distribution.append(node); 273 m_nodeToInsertionPoint.add(node, insertionPoint); 274 } 275 } 276 277 insertionPoint->lazyReattachIfAttached(); 278 insertionPoint->setDistribution(distribution); 279} 280 281const SelectRuleFeatureSet& ContentDistributor::ensureSelectFeatureSet(ElementShadow* shadow) 282{ 283 if (!m_needsSelectFeatureSet) 284 return m_selectFeatures; 285 286 m_selectFeatures.clear(); 287 for (ShadowRoot* root = shadow->oldestShadowRoot(); root; root = root->youngerShadowRoot()) 288 collectSelectFeatureSetFrom(root); 289 m_needsSelectFeatureSet = false; 290 return m_selectFeatures; 291} 292 293void ContentDistributor::collectSelectFeatureSetFrom(ShadowRoot* root) 294{ 295 if (!root->containsShadowRoots() && !root->containsContentElements()) 296 return; 297 298 for (Element* element = ElementTraversal::firstWithin(root); element; element = ElementTraversal::next(element, root)) { 299 if (ElementShadow* shadow = element->shadow()) 300 m_selectFeatures.add(shadow->ensureSelectFeatureSet()); 301 if (!isHTMLContentElement(element)) 302 continue; 303 const CSSSelectorList& list = toHTMLContentElement(element)->selectorList(); 304 for (const CSSSelector* selector = list.first(); selector; selector = CSSSelectorList::next(selector)) { 305 for (const CSSSelector* component = selector; component; component = component->tagHistory()) 306 m_selectFeatures.collectFeaturesFromSelector(component); 307 } 308 } 309} 310 311void ContentDistributor::didAffectSelector(Element* host, AffectedSelectorMask mask) 312{ 313 if (ensureSelectFeatureSet(host->shadow()).hasSelectorFor(mask)) 314 host->shadow()->setNeedsDistributionRecalc(); 315} 316 317void ContentDistributor::willAffectSelector(Element* host) 318{ 319 for (ElementShadow* shadow = host->shadow(); shadow; shadow = shadow->containingShadow()) { 320 if (shadow->distributor().needsSelectFeatureSet()) 321 break; 322 shadow->distributor().setNeedsSelectFeatureSet(); 323 } 324 host->shadow()->setNeedsDistributionRecalc(); 325} 326 327void ContentDistributor::clearDistribution(Element* host) 328{ 329 m_nodeToInsertionPoint.clear(); 330 331 for (ShadowRoot* root = host->youngestShadowRoot(); root; root = root->olderShadowRoot()) { 332 if (ScopeContentDistribution* scope = root->scopeDistribution()) 333 scope->setInsertionPointAssignedTo(0); 334 } 335} 336 337} 338