1/*
2 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3 *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
4 * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
5 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
6 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
7 * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
8 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
9 * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
10 * Copyright (C) Research In Motion Limited 2011. All rights reserved.
11 * Copyright (C) 2013 Google Inc. All rights reserved.
12 *
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Library General Public
15 * License as published by the Free Software Foundation; either
16 * version 2 of the License, or (at your option) any later version.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
21 * Library General Public License for more details.
22 *
23 * You should have received a copy of the GNU Library General Public License
24 * along with this library; see the file COPYING.LIB.  If not, write to
25 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
26 * Boston, MA 02110-1301, USA.
27 */
28
29#include "config.h"
30#include "core/css/resolver/SharedStyleFinder.h"
31
32#include "HTMLNames.h"
33#include "XMLNames.h"
34#include "core/css/resolver/StyleResolver.h"
35#include "core/css/resolver/StyleResolverState.h"
36#include "core/dom/ContainerNode.h"
37#include "core/dom/Document.h"
38#include "core/dom/Element.h"
39#include "core/dom/FullscreenElementStack.h"
40#include "core/dom/Node.h"
41#include "core/dom/NodeRenderStyle.h"
42#include "core/dom/NodeTraversal.h"
43#include "core/dom/QualifiedName.h"
44#include "core/dom/SpaceSplitString.h"
45#include "core/dom/shadow/ElementShadow.h"
46#include "core/html/HTMLElement.h"
47#include "core/html/HTMLInputElement.h"
48#include "core/html/HTMLOptGroupElement.h"
49#include "core/html/track/WebVTTElement.h"
50#include "core/rendering/style/RenderStyle.h"
51#include "core/svg/SVGElement.h"
52#include "wtf/HashSet.h"
53#include "wtf/text/AtomicString.h"
54
55namespace WebCore {
56
57using namespace HTMLNames;
58
59static const unsigned cStyleSearchThreshold = 10;
60static const unsigned cStyleSearchLevelThreshold = 10;
61
62static inline bool parentElementPreventsSharing(const Element* parentElement)
63{
64    if (!parentElement)
65        return false;
66    return parentElement->hasFlagsSetDuringStylingOfChildren();
67}
68
69Node* SharedStyleFinder::locateCousinList(Element* parent, unsigned& visitedNodeCount) const
70{
71    if (visitedNodeCount >= cStyleSearchThreshold * cStyleSearchLevelThreshold)
72        return 0;
73    if (!parent || !parent->isStyledElement())
74        return 0;
75    if (parent->hasScopedHTMLStyleChild())
76        return 0;
77    if (parent->inlineStyle())
78        return 0;
79    if (parent->isSVGElement() && toSVGElement(parent)->animatedSMILStyleProperties())
80        return 0;
81    if (parent->hasID() && m_features.idsInRules.contains(parent->idForStyleResolution().impl()))
82        return 0;
83    if (isShadowHost(parent) && parent->shadow()->containsActiveStyles())
84        return 0;
85
86    RenderStyle* parentStyle = parent->renderStyle();
87    unsigned subcount = 0;
88    Node* thisCousin = parent;
89    Node* currentNode = parent->previousSibling();
90
91    // Reserve the tries for this level. This effectively makes sure that the algorithm
92    // will never go deeper than cStyleSearchLevelThreshold levels into recursion.
93    visitedNodeCount += cStyleSearchThreshold;
94    while (thisCousin) {
95        while (currentNode) {
96            ++subcount;
97            if (!currentNode->hasScopedHTMLStyleChild() && currentNode->renderStyle() == parentStyle && currentNode->lastChild()
98                && currentNode->isElementNode() && !parentElementPreventsSharing(toElement(currentNode))
99                && !toElement(currentNode)->shadow()
100                ) {
101                // Adjust for unused reserved tries.
102                visitedNodeCount -= cStyleSearchThreshold - subcount;
103                return currentNode->lastChild();
104            }
105            if (subcount >= cStyleSearchThreshold)
106                return 0;
107            currentNode = currentNode->previousSibling();
108        }
109        currentNode = locateCousinList(thisCousin->parentElement(), visitedNodeCount);
110        thisCousin = currentNode;
111    }
112
113    return 0;
114}
115
116
117bool SharedStyleFinder::canShareStyleWithControl(const ElementResolveContext& context, Element* element) const
118{
119    if (!element->hasTagName(inputTag) || !context.element()->hasTagName(inputTag))
120        return false;
121
122    HTMLInputElement* thisInputElement = toHTMLInputElement(element);
123    HTMLInputElement* otherInputElement = toHTMLInputElement(context.element());
124    if (thisInputElement->elementData() != otherInputElement->elementData()) {
125        if (thisInputElement->fastGetAttribute(typeAttr) != otherInputElement->fastGetAttribute(typeAttr))
126            return false;
127        if (thisInputElement->fastGetAttribute(readonlyAttr) != otherInputElement->fastGetAttribute(readonlyAttr))
128            return false;
129    }
130
131    if (thisInputElement->isAutofilled() != otherInputElement->isAutofilled())
132        return false;
133    if (thisInputElement->shouldAppearChecked() != otherInputElement->shouldAppearChecked())
134        return false;
135    if (thisInputElement->shouldAppearIndeterminate() != otherInputElement->shouldAppearIndeterminate())
136        return false;
137    if (thisInputElement->isRequired() != otherInputElement->isRequired())
138        return false;
139
140    if (element->isDisabledFormControl() != context.element()->isDisabledFormControl())
141        return false;
142
143    if (element->isDefaultButtonForForm() != context.element()->isDefaultButtonForForm())
144        return false;
145
146    if (context.document()->containsValidityStyleRules()) {
147        bool willValidate = element->willValidate();
148
149        if (willValidate != context.element()->willValidate())
150            return false;
151
152        if (willValidate && (element->isValidFormControlElement() != context.element()->isValidFormControlElement()))
153            return false;
154
155        if (element->isInRange() != context.element()->isInRange())
156            return false;
157
158        if (element->isOutOfRange() != context.element()->isOutOfRange())
159            return false;
160    }
161
162    return true;
163}
164
165bool SharedStyleFinder::classNamesAffectedByRules(const SpaceSplitString& classNames) const
166{
167    for (unsigned i = 0; i < classNames.size(); ++i) {
168        if (m_features.classesInRules.contains(classNames[i].impl()))
169            return true;
170    }
171    return false;
172}
173
174static inline bool elementHasDirectionAuto(Element* element)
175{
176    // FIXME: This line is surprisingly hot, we may wish to inline hasDirectionAuto into StyleResolver.
177    return element->isHTMLElement() && toHTMLElement(element)->hasDirectionAuto();
178}
179
180bool SharedStyleFinder::sharingCandidateHasIdenticalStyleAffectingAttributes(const ElementResolveContext& context, Element* sharingCandidate) const
181{
182    if (context.element()->elementData() == sharingCandidate->elementData())
183        return true;
184    if (context.element()->fastGetAttribute(XMLNames::langAttr) != sharingCandidate->fastGetAttribute(XMLNames::langAttr))
185        return false;
186    if (context.element()->fastGetAttribute(langAttr) != sharingCandidate->fastGetAttribute(langAttr))
187        return false;
188
189    if (!m_elementAffectedByClassRules) {
190        if (sharingCandidate->hasClass() && classNamesAffectedByRules(sharingCandidate->classNames()))
191            return false;
192    } else if (sharingCandidate->hasClass()) {
193        // SVG elements require a (slow!) getAttribute comparision because "class" is an animatable attribute for SVG.
194        if (context.element()->isSVGElement()) {
195            if (context.element()->getAttribute(classAttr) != sharingCandidate->getAttribute(classAttr))
196                return false;
197        } else if (context.element()->classNames() != sharingCandidate->classNames()) {
198            return false;
199        }
200    } else {
201        return false;
202    }
203
204    if (context.element()->presentationAttributeStyle() != sharingCandidate->presentationAttributeStyle())
205        return false;
206
207    if (context.element()->hasTagName(progressTag)) {
208        if (context.element()->shouldAppearIndeterminate() != sharingCandidate->shouldAppearIndeterminate())
209            return false;
210    }
211
212    return true;
213}
214
215bool SharedStyleFinder::canShareStyleWithElement(const ElementResolveContext& context, Element* element) const
216{
217    RenderStyle* style = element->renderStyle();
218    if (!style)
219        return false;
220    if (style->unique())
221        return false;
222    if (style->hasUniquePseudoStyle())
223        return false;
224    if (element->tagQName() != context.element()->tagQName())
225        return false;
226    if (element->inlineStyle())
227        return false;
228    if (element->needsStyleRecalc())
229        return false;
230    if (element->isSVGElement() && toSVGElement(element)->animatedSMILStyleProperties())
231        return false;
232    if (element->isLink() != context.element()->isLink())
233        return false;
234    if (element->hovered() != context.element()->hovered())
235        return false;
236    if (element->active() != context.element()->active())
237        return false;
238    if (element->focused() != context.element()->focused())
239        return false;
240    if (element->shadowPseudoId() != context.element()->shadowPseudoId())
241        return false;
242    if (element == element->document()->cssTarget())
243        return false;
244    if (!sharingCandidateHasIdenticalStyleAffectingAttributes(context, element))
245        return false;
246    if (element->additionalPresentationAttributeStyle() != context.element()->additionalPresentationAttributeStyle())
247        return false;
248
249    if (element->hasID() && m_features.idsInRules.contains(element->idForStyleResolution().impl()))
250        return false;
251    if (element->hasScopedHTMLStyleChild())
252        return false;
253    if (isShadowHost(element) && element->shadow()->containsActiveStyles())
254        return 0;
255
256    // FIXME: We should share style for option and optgroup whenever possible.
257    // Before doing so, we need to resolve issues in HTMLSelectElement::recalcListItems
258    // and RenderMenuList::setText. See also https://bugs.webkit.org/show_bug.cgi?id=88405
259    if (element->hasTagName(optionTag) || isHTMLOptGroupElement(element))
260        return false;
261
262    bool isControl = element->isFormControlElement();
263
264    if (isControl != context.element()->isFormControlElement())
265        return false;
266
267    if (isControl && !canShareStyleWithControl(context, element))
268        return false;
269
270    if (style->transitions() || style->animations())
271        return false;
272
273    // Turn off style sharing for elements that can gain layers for reasons outside of the style system.
274    // See comments in RenderObject::setStyle().
275    if (element->hasTagName(iframeTag) || element->hasTagName(frameTag) || element->hasTagName(embedTag) || element->hasTagName(objectTag) || element->hasTagName(appletTag) || element->hasTagName(canvasTag))
276        return false;
277
278    if (elementHasDirectionAuto(element))
279        return false;
280
281    if (element->isLink() && context.elementLinkState() != style->insideLink())
282        return false;
283
284    if (element->isUnresolvedCustomElement() != context.element()->isUnresolvedCustomElement())
285        return false;
286
287    // Deny sharing styles between WebVTT and non-WebVTT nodes.
288    if (element->isWebVTTElement() != context.element()->isWebVTTElement())
289        return false;
290
291    if (element->isWebVTTElement() && context.element()->isWebVTTElement() && toWebVTTElement(element)->isPastNode() != toWebVTTElement(context.element())->isPastNode())
292        return false;
293
294    if (FullscreenElementStack* fullscreen = FullscreenElementStack::fromIfExists(context.document())) {
295        if (element == fullscreen->webkitCurrentFullScreenElement() || context.element() == fullscreen->webkitCurrentFullScreenElement())
296            return false;
297    }
298
299    return true;
300}
301
302inline Element* SharedStyleFinder::findSiblingForStyleSharing(const ElementResolveContext& context, Node* node, unsigned& count) const
303{
304    for (; node; node = node->previousSibling()) {
305        if (!node->isStyledElement())
306            continue;
307        if (canShareStyleWithElement(context, toElement(node)))
308            break;
309        if (count++ == cStyleSearchThreshold)
310            return 0;
311    }
312    return toElement(node);
313}
314
315#ifdef STYLE_STATS
316Element* SharedStyleFinder::searchDocumentForSharedStyle(const ElementResolveContext& context) const
317{
318    for (Element* element = context.element()->document()->documentElement(); element; element = ElementTraversal::next(element)) {
319        if (canShareStyleWithElement(context, element))
320            return element;
321    }
322    return 0;
323}
324#endif
325
326RenderStyle* SharedStyleFinder::locateSharedStyle(const ElementResolveContext& context, RenderStyle* newStyle)
327{
328    STYLE_STATS_ADD_SEARCH();
329    if (!context.element() || !context.element()->isStyledElement())
330        return 0;
331
332    // If the element has inline style it is probably unique.
333    if (context.element()->inlineStyle())
334        return 0;
335    if (context.element()->isSVGElement() && toSVGElement(context.element())->animatedSMILStyleProperties())
336        return 0;
337    // Ids stop style sharing if they show up in the stylesheets.
338    if (context.element()->hasID() && m_features.idsInRules.contains(context.element()->idForStyleResolution().impl()))
339        return 0;
340    // Active and hovered elements always make a chain towards the document node
341    // and no siblings or cousins will have the same state.
342    if (context.element()->hovered())
343        return 0;
344    if (context.element()->active())
345        return 0;
346    // There is always only one focused element.
347    if (context.element()->focused())
348        return 0;
349    if (parentElementPreventsSharing(context.element()->parentElement()))
350        return 0;
351    if (context.element()->hasScopedHTMLStyleChild())
352        return 0;
353    if (context.element() == context.document()->cssTarget())
354        return 0;
355    if (elementHasDirectionAuto(context.element()))
356        return 0;
357    if (context.element()->hasActiveAnimations())
358        return 0;
359    // When a dialog is first shown, its style is mutated to center it in the
360    // viewport. So the styles can't be shared since the viewport position and
361    // size may be different each time a dialog is opened.
362    if (context.element()->hasTagName(dialogTag))
363        return 0;
364    if (isShadowHost(context.element()) && context.element()->shadow()->containsActiveStyles())
365        return 0;
366
367    STYLE_STATS_ADD_ELEMENT_ELIGIBLE_FOR_SHARING();
368
369    // Cache whether context.element() is affected by any known class selectors.
370    // FIXME: This should be an explicit out parameter, instead of a member variable.
371    m_elementAffectedByClassRules = context.element() && context.element()->hasClass() && classNamesAffectedByRules(context.element()->classNames());
372
373    // Check previous siblings and their cousins.
374    unsigned count = 0;
375    unsigned visitedNodeCount = 0;
376    Element* shareElement = 0;
377    Node* cousinList = context.element()->previousSibling();
378    while (cousinList) {
379        shareElement = findSiblingForStyleSharing(context, cousinList, count);
380        if (shareElement)
381            break;
382        cousinList = locateCousinList(cousinList->parentElement(), visitedNodeCount);
383    }
384
385#ifdef STYLE_STATS
386    // FIXME: these stats don't to into account whether or not sibling/attribute
387    // rules prevent these nodes from actually sharing
388    if (shareElement) {
389        STYLE_STATS_ADD_SEARCH_FOUND_SIBLING_FOR_SHARING();
390    } else {
391        shareElement = searchDocumentForSharedStyle(context);
392        if (shareElement)
393            STYLE_STATS_ADD_SEARCH_MISSED_SHARING();
394        shareElement = 0;
395    }
396#endif
397
398    // If we have exhausted all our budget or our cousins.
399    if (!shareElement)
400        return 0;
401
402    // Can't share if sibling rules apply. This is checked at the end as it should rarely fail.
403    if (m_styleResolver->styleSharingCandidateMatchesRuleSet(context, newStyle, m_siblingRuleSet))
404        return 0;
405    // Can't share if attribute rules apply.
406    if (m_styleResolver->styleSharingCandidateMatchesRuleSet(context, newStyle, m_uncommonAttributeRuleSet))
407        return 0;
408    // Tracking child index requires unique style for each node. This may get set by the sibling rule match above.
409    if (parentElementPreventsSharing(context.element()->parentElement()))
410        return 0;
411    STYLE_STATS_ADD_STYLE_SHARED();
412    return shareElement->renderStyle();
413}
414
415}
416