/**

 * This file is part of the CSS implementation for KDE.

 *

 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)

 *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)

 *           (C) 2006 Nicholas Shanks (webkit@nickshanks.com)

 * Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Library General Public

 * License as published by the Free Software Foundation; either

 * version 2 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Library General Public License for more details.

 *

 * You should have received a copy of the GNU Library General Public License

 * along with this library; see the file COPYING.LIB.  If not, write to

 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

 * Boston, MA 02110-1301, USA.

 */

#include "CSSStyleSelector.h"

#include "CSSBorderImageValue.h"

#include "CSSCursorImageValue.h"

#include "CSSImageValue.h"

#include "CSSImportRule.h"

#include "CSSMediaRule.h"

#include "CSSProperty.h"

#include "CSSPropertyNames.h"

#include "CSSRuleList.h"

#include "CSSSelector.h"

#include "CSSStyleRule.h"

#include "CSSStyleSheet.h"

#include "CSSValueKeywords.h"

#include "CSSValueList.h"

#include "CachedImage.h"

#include "Counter.h"

#include "DashboardRegion.h"

#include "FontFamilyValue.h"

#include "FontValue.h"

#include "Frame.h"

#include "FrameView.h"

#include "GlobalHistory.h"

#include "HTMLDocument.h"

#include "HTMLElement.h"

#include "HTMLInputElement.h"

#include "HTMLNames.h"

#include "MediaList.h"

#include "MediaQueryEvaluator.h"

#include "Pair.h"

#include "Rect.h"

#include "RenderTheme.h"

#include "Settings.h"

#include "ShadowValue.h"

#include "StyleSheetList.h"

#include "UserAgentStyleSheets.h"

#include "loader.h"

#if ENABLE(SVG)

#include "XLinkNames.h"

#include "SVGNames.h"

#endif

#if PLATFORM(SYMBIAN)

#include "Frame.h"

#include "WebCoreFrameBridge.h"

#endif

using namespace std;

namespace WebCore {

using namespace HTMLNames;

// #define STYLE_SHARING_STATS 1

#define HANDLE_INHERIT(prop, Prop) \

if (isInherit) { \

    style->set##Prop(parentStyle->prop()); \

    return; \

}

#define HANDLE_INHERIT_AND_INITIAL(prop, Prop) \

HANDLE_INHERIT(prop, Prop) \

if (isInitial) { \

    style->set##Prop(RenderStyle::initial##Prop()); \

    return; \

}

#define HANDLE_INHERIT_AND_INITIAL_WITH_VALUE(prop, Prop, Value) \

HANDLE_INHERIT(prop, Prop) \

if (isInitial) { \

    style->set##Prop(RenderStyle::initial##Value());\

    return;\

}

#define HANDLE_BACKGROUND_INHERIT_AND_INITIAL(prop, Prop) \

if (isInherit) { \

    BackgroundLayer* currChild = style->accessBackgroundLayers(); \

    BackgroundLayer* prevChild = 0; \

    const BackgroundLayer* currParent = parentStyle->backgroundLayers(); \

    while (currParent && currParent->is##Prop##Set()) { \

        if (!currChild) { \

            /* Need to make a new layer.*/ \

            currChild = new BackgroundLayer(); \

            prevChild->setNext(currChild); \

        } \

        currChild->set##Prop(currParent->prop()); \

        prevChild = currChild; \

        currChild = prevChild->next(); \

        currParent = currParent->next(); \

    } \

    \

    while (currChild) { \

        /* Reset any remaining layers to not have the property set. */ \

        currChild->clear##Prop(); \

        currChild = currChild->next(); \

    } \

    return; \

} \

if (isInitial) { \

    BackgroundLayer* currChild = style->accessBackgroundLayers(); \

    currChild->set##Prop(RenderStyle::initial##Prop()); \

    for (currChild = currChild->next(); currChild; currChild = currChild->next()) \

        currChild->clear##Prop(); \

    return; \

}

#define HANDLE_BACKGROUND_VALUE(prop, Prop, value) { \

HANDLE_BACKGROUND_INHERIT_AND_INITIAL(prop, Prop) \

if (!value->isPrimitiveValue() && !value->isValueList()) \

    return; \

BackgroundLayer* currChild = style->accessBackgroundLayers(); \

BackgroundLayer* prevChild = 0; \

if (value->isPrimitiveValue()) { \

    map##Prop(currChild, value); \

    currChild = currChild->next(); \

} \

else { \

    /* Walk each value and put it into a layer, creating new layers as needed. */ \

    CSSValueList* valueList = static_cast<CSSValueList*>(value); \

    for (unsigned int i = 0; i < valueList->length(); i++) { \

        if (!currChild) { \

            /* Need to make a new layer to hold this value */ \

            currChild = new BackgroundLayer(); \

            prevChild->setNext(currChild); \

        } \

        map##Prop(currChild, valueList->item(i)); \

        prevChild = currChild; \

        currChild = currChild->next(); \

    } \

} \

while (currChild) { \

    /* Reset all remaining layers to not have the property set. */ \

    currChild->clear##Prop(); \

    currChild = currChild->next(); \

} }

#define HANDLE_INHERIT_COND(propID, prop, Prop) \

if (id == propID) { \

    style->set##Prop(parentStyle->prop()); \

    return; \

}

#define HANDLE_INITIAL_COND(propID, Prop) \

if (id == propID) { \

    style->set##Prop(RenderStyle::initial##Prop()); \

    return; \

}

#define HANDLE_INITIAL_COND_WITH_VALUE(propID, Prop, Value) \

if (id == propID) { \

    style->set##Prop(RenderStyle::initial##Value()); \

    return; \

}

class CSSRuleSet

{

public:

    CSSRuleSet();

    ~CSSRuleSet();

    typedef HashMap<AtomicStringImpl*, CSSRuleDataList*> AtomRuleMap;

    void addRulesFromSheet(CSSStyleSheet* sheet, MediaQueryEvaluator* medium);

    void addRule(CSSStyleRule* rule, CSSSelector* sel);

    void addToRuleSet(AtomicStringImpl* key, AtomRuleMap& map,

                      CSSStyleRule* rule, CSSSelector* sel);

    CSSRuleDataList* getIDRules(AtomicStringImpl* key) { return m_idRules.get(key); }

    CSSRuleDataList* getClassRules(AtomicStringImpl* key) { return m_classRules.get(key); }

    CSSRuleDataList* getTagRules(AtomicStringImpl* key) { return m_tagRules.get(key); }

    CSSRuleDataList* getUniversalRules() { return m_universalRules; }

public:

    AtomRuleMap m_idRules;

    AtomRuleMap m_classRules;

    AtomRuleMap m_tagRules;

    CSSRuleDataList* m_universalRules;

    unsigned m_ruleCount;

};

CSSRuleSet* CSSStyleSelector::defaultStyle = 0;

CSSRuleSet* CSSStyleSelector::defaultQuirksStyle = 0;

CSSRuleSet* CSSStyleSelector::defaultPrintStyle = 0;

CSSRuleSet* CSSStyleSelector::defaultViewSourceStyle = 0;

CSSStyleSheet* CSSStyleSelector::defaultSheet = 0;

RenderStyle* CSSStyleSelector::styleNotYetAvailable = 0;

CSSStyleSheet* CSSStyleSelector::quirksSheet = 0;

CSSStyleSheet* CSSStyleSelector::viewSourceSheet = 0;

#if ENABLE(SVG)

CSSStyleSheet *CSSStyleSelector::svgSheet = 0;

#endif

static CSSStyleSelector::Encodedurl *currentEncodedURL = 0;

static PseudoState pseudoState;

CSSStyleSelector::CSSStyleSelector(Document* doc, const String& userStyleSheet, StyleSheetList *styleSheets, bool _strictParsing)

{

    init();

    m_document = doc;

    strictParsing = _strictParsing;

    if (!defaultStyle)

        loadDefaultStyle();

    m_userStyle = 0;

    // construct document root element default style. this is needed

    // to evaluate media queries that contain relative constraints, like "screen and (max-width: 10em)"

    // This is here instead of constructor, because when constructor is run,

    // document doesn't have documentElement

    // NOTE: this assumes that element that gets passed to styleForElement -call

    // is always from the document that owns the style selector

    FrameView* view = m_document->view();

    if (view)

        m_medium = new MediaQueryEvaluator(view->mediaType());

    else

        m_medium = new MediaQueryEvaluator("all");

    Element* root = doc->documentElement();

    if (root)

        m_rootDefaultStyle = styleForElement(root, 0, false, true); // dont ref, because the RenderStyle is allocated from global heap

    if (m_rootDefaultStyle && view) {

        delete m_medium;

        m_medium = new MediaQueryEvaluator(view->mediaType(), view->frame()->page(), m_rootDefaultStyle);

    }

    // FIXME: This sucks! The user sheet is reparsed every time!

    if (!userStyleSheet.isEmpty()) {

        m_userSheet = new CSSStyleSheet(doc);

        m_userSheet->parseString(userStyleSheet, strictParsing);

        m_userStyle = new CSSRuleSet();

        m_userStyle->addRulesFromSheet(m_userSheet.get(), m_medium);

    }

    // add stylesheets from document

    m_authorStyle = new CSSRuleSet();

    DeprecatedPtrListIterator<StyleSheet> it(styleSheets->styleSheets);

    for (; it.current(); ++it)

        if (it.current()->isCSSStyleSheet() && !it.current()->disabled())

            m_authorStyle->addRulesFromSheet(static_cast<CSSStyleSheet*>(it.current()), m_medium);

}

CSSStyleSelector::CSSStyleSelector(CSSStyleSheet *sheet)

{

    init();

    if (!defaultStyle)

        loadDefaultStyle();

    FrameView *view = sheet->doc()->view();

    if (view)

        m_medium = new MediaQueryEvaluator(view->mediaType());

    else

        m_medium = new MediaQueryEvaluator("all");

    Element* root = sheet->doc()->documentElement();

    if (root)

        m_rootDefaultStyle = styleForElement(root, 0, false, true);

    if (m_rootDefaultStyle && view) {

        delete m_medium;

        m_medium = new MediaQueryEvaluator(view->mediaType(), view->frame()->page(), m_rootDefaultStyle);

    }

    m_authorStyle = new CSSRuleSet();

    m_authorStyle->addRulesFromSheet(sheet, m_medium);

}

void CSSStyleSelector::init()

{

    element = 0;

    m_matchedDecls.clear();

    m_ruleList = 0;

    m_collectRulesOnly = false;

    m_rootDefaultStyle = 0;

    m_medium = 0;

}

void CSSStyleSelector::setEncodedURL(const KURL& url)

{

    KURL u = url;

    u.setQuery(DeprecatedString::null);

    u.setRef(DeprecatedString::null);

    encodedurl.file = u.url();

    int pos = encodedurl.file.findRev('/');

    encodedurl.path = encodedurl.file;

    if (pos > 0) {

        encodedurl.path.truncate(pos);

        encodedurl.path += '/';

    }

    u.setPath(DeprecatedString::null);

    encodedurl.host = u.url();

}

CSSStyleSelector::~CSSStyleSelector()

{

    delete m_medium;

    ::delete m_rootDefaultStyle;

    delete m_authorStyle;

    delete m_userStyle;

}

static CSSStyleSheet* parseUASheet(const char* characters, unsigned size)

{

    CSSStyleSheet* const parent = 0;

    CSSStyleSheet* sheet = new CSSStyleSheet(parent);

    sheet->ref(); // leak the sheet on purpose since it will be stored in a global variable

    sheet->parseString(String(characters, size));

    return sheet;

}

template<typename T> CSSStyleSheet* parseUASheet(const T& array)

{

    return parseUASheet((const char*)array, sizeof(array));

}

void CSSStyleSelector::loadDefaultStyle()

{

    if (defaultStyle)

        return;

    defaultStyle = new CSSRuleSet;

    defaultPrintStyle = new CSSRuleSet;

    defaultQuirksStyle = new CSSRuleSet;

    defaultViewSourceStyle = new CSSRuleSet;

    MediaQueryEvaluator screenEval("screen");

    MediaQueryEvaluator printEval("print");

    // Strict-mode rules.

    defaultSheet = parseUASheet(html4UserAgentStyleSheet);

    defaultStyle->addRulesFromSheet(defaultSheet, &screenEval);

    defaultPrintStyle->addRulesFromSheet(defaultSheet, &printEval);

#if ENABLE(SVG)

    // SVG rules.

    svgSheet = parseUASheet(svgUserAgentStyleSheet);

    defaultStyle->addRulesFromSheet(svgSheet, &screenEval);

    defaultPrintStyle->addRulesFromSheet(svgSheet, &printEval);

#endif

    // Quirks-mode rules.

    quirksSheet = parseUASheet(quirksUserAgentStyleSheet);

    defaultQuirksStyle->addRulesFromSheet(quirksSheet, &screenEval);

    // View source rules.

    viewSourceSheet = parseUASheet(sourceUserAgentStyleSheet);

    defaultViewSourceStyle->addRulesFromSheet(viewSourceSheet, &screenEval);

}

void CSSStyleSelector::matchRules(CSSRuleSet* rules, int& firstRuleIndex, int& lastRuleIndex)

{

    m_matchedRules.clear();

    if (!rules || !element)

        return;

    // We need to collect the rules for id, class, tag, and everything else into a buffer and

    // then sort the buffer.

    if (element->hasID())

        matchRulesForList(rules->getIDRules(element->getIDAttribute().impl()), firstRuleIndex, lastRuleIndex);

    if (element->hasClass()) {

        for (const AtomicStringList* singleClass = element->getClassList(); singleClass; singleClass = singleClass->next())

            matchRulesForList(rules->getClassRules(singleClass->string().impl()), firstRuleIndex, lastRuleIndex);

    }

    matchRulesForList(rules->getTagRules(element->localName().impl()), firstRuleIndex, lastRuleIndex);

    matchRulesForList(rules->getUniversalRules(), firstRuleIndex, lastRuleIndex);

    // If we didn't match any rules, we're done.

    if (m_matchedRules.isEmpty())

        return;

    // Sort the set of matched rules.

    sortMatchedRules(0, m_matchedRules.size());

    // Now transfer the set of matched rules over to our list of decls.

    if (!m_collectRulesOnly) {

        for (unsigned i = 0; i < m_matchedRules.size(); i++)

            addMatchedDeclaration(m_matchedRules[i]->rule()->declaration());

    } else {

        for (unsigned i = 0; i < m_matchedRules.size(); i++) {

            if (!m_ruleList)

                m_ruleList = new CSSRuleList();

            m_ruleList->append(m_matchedRules[i]->rule());

        }

    }

}

void CSSStyleSelector::matchRulesForList(CSSRuleDataList* rules, int& firstRuleIndex, int& lastRuleIndex)

{

    if (!rules)

        return;

    for (CSSRuleData* d = rules->first(); d; d = d->next()) {

        CSSStyleRule* rule = d->rule();

        const AtomicString& localName = element->localName();

        const AtomicString& selectorLocalName = d->selector()->m_tag.localName();

        if ((localName == selectorLocalName || selectorLocalName == starAtom) && checkSelector(d->selector(), element)) {

            // If the rule has no properties to apply, then ignore it.

            CSSMutableStyleDeclaration* decl = rule->declaration();

            if (!decl || !decl->length())

                continue;

            // If we're matching normal rules, set a pseudo bit if 

            // we really just matched a pseudo-element.

            if (dynamicPseudo != RenderStyle::NOPSEUDO && pseudoStyle == RenderStyle::NOPSEUDO) {

                if (m_collectRulesOnly)

                    return;

                style->setHasPseudoStyle(dynamicPseudo);

            } else {

                // Update our first/last rule indices in the matched rules array.

                lastRuleIndex = m_matchedDecls.size() + m_matchedRules.size();

                if (firstRuleIndex == -1)

                    firstRuleIndex = lastRuleIndex;

                // Add this rule to our list of matched rules.

                addMatchedRule(d);

            }

        }

    }

}

bool operator >(CSSRuleData& r1, CSSRuleData& r2)

{

    int spec1 = r1.selector()->specificity();

    int spec2 = r2.selector()->specificity();

    return (spec1 == spec2) ? r1.position() > r2.position() : spec1 > spec2; 

}

bool operator <=(CSSRuleData& r1, CSSRuleData& r2)

{

    return !(r1 > r2);

}

void CSSStyleSelector::sortMatchedRules(unsigned start, unsigned end)

{

    if (start >= end || (end - start == 1))

        return; // Sanity check.

    if (end - start <= 6) {

        // Apply a bubble sort for smaller lists.

        for (unsigned i = end - 1; i > start; i--) {

            bool sorted = true;

            for (unsigned j = start; j < i; j++) {

                CSSRuleData* elt = m_matchedRules[j];

                CSSRuleData* elt2 = m_matchedRules[j + 1];

                if (*elt > *elt2) {

                    sorted = false;

                    m_matchedRules[j] = elt2;

                    m_matchedRules[j + 1] = elt;

                }

            }

            if (sorted)

                return;

        }

        return;

    }

    // Peform a merge sort for larger lists.

    unsigned mid = (start + end) / 2;

    sortMatchedRules(start, mid);

    sortMatchedRules(mid, end);

    CSSRuleData* elt = m_matchedRules[mid - 1];

    CSSRuleData* elt2 = m_matchedRules[mid];

    // Handle the fast common case (of equal specificity).  The list may already

    // be completely sorted.

    if (*elt <= *elt2)

        return;

    // We have to merge sort.  Ensure our merge buffer is big enough to hold

    // all the items.

    Vector<CSSRuleData*> rulesMergeBuffer;

    rulesMergeBuffer.reserveCapacity(end - start); 

    unsigned i1 = start;

    unsigned i2 = mid;

    elt = m_matchedRules[i1];

    elt2 = m_matchedRules[i2];