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