1/*
2 * Copyright (C) 2010 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
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 *    notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 *    notice, this list of conditions and the following disclaimer in the
11 *    documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef HTMLFormattingElementList_h
27#define HTMLFormattingElementList_h
28
29#include "HTMLStackItem.h"
30#include <wtf/Forward.h>
31#include <wtf/RefPtr.h>
32#include <wtf/Vector.h>
33
34namespace WebCore {
35
36class Element;
37
38// This may end up merged into HTMLElementStack.
39class HTMLFormattingElementList {
40    WTF_MAKE_NONCOPYABLE(HTMLFormattingElementList);
41public:
42    HTMLFormattingElementList();
43    ~HTMLFormattingElementList();
44
45    // Ideally Entry would be private, but HTMLTreeBuilder has to coordinate
46    // between the HTMLFormattingElementList and HTMLElementStack and needs
47    // access to Entry::isMarker() and Entry::replaceElement() to do so.
48    class Entry {
49    public:
50        // Inline because they're hot and Vector<T> uses them.
51        explicit Entry(PassRefPtr<HTMLStackItem> item)
52            : m_item(item)
53        {
54        }
55        enum MarkerEntryType { MarkerEntry };
56        Entry(MarkerEntryType)
57            : m_item(0)
58        {
59        }
60        ~Entry() {}
61
62        bool isMarker() const { return !m_item; }
63
64        PassRefPtr<HTMLStackItem> stackItem() const { return m_item; }
65        Element* element() const
66        {
67            // The fact that !m_item == isMarker() is an implementation detail
68            // callers should check isMarker() before calling element().
69            ASSERT(m_item);
70            return m_item->element();
71        }
72        void replaceElement(PassRefPtr<HTMLStackItem> item) { m_item = item; }
73
74        // Needed for use with Vector.  These are super-hot and must be inline.
75        bool operator==(Element* element) const { return !m_item ? !element : m_item->element() == element; }
76        bool operator!=(Element* element) const { return !m_item ? !!element : m_item->element() != element; }
77
78    private:
79        RefPtr<HTMLStackItem> m_item;
80    };
81
82    class Bookmark {
83    public:
84        Bookmark(Entry* entry)
85            : m_hasBeenMoved(false)
86            , m_mark(entry)
87        {
88        }
89
90        void moveToAfter(Entry* before)
91        {
92            m_hasBeenMoved = true;
93            m_mark = before;
94        }
95
96        bool hasBeenMoved() const { return m_hasBeenMoved; }
97        Entry* mark() const { return m_mark; }
98
99    private:
100        bool m_hasBeenMoved;
101        Entry* m_mark;
102    };
103
104    bool isEmpty() const { return !size(); }
105    size_t size() const { return m_entries.size(); }
106
107    Element* closestElementInScopeWithName(const AtomicString&);
108
109    Entry* find(Element*);
110    bool contains(Element*);
111    void append(PassRefPtr<HTMLStackItem>);
112    void remove(Element*);
113
114    Bookmark bookmarkFor(Element*);
115    void swapTo(Element* oldElement, PassRefPtr<HTMLStackItem> newItem, const Bookmark&);
116
117    void appendMarker();
118    // clearToLastMarker also clears the marker (per the HTML5 spec).
119    void clearToLastMarker();
120
121    const Entry& at(size_t i) const { return m_entries[i]; }
122    Entry& at(size_t i) { return m_entries[i]; }
123
124#ifndef NDEBUG
125    void show();
126#endif
127
128private:
129    Entry* first() { return &at(0); }
130
131    // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#list-of-active-formatting-elements
132    // These functions enforce the "Noah's Ark" condition, which removes redundant mis-nested elements.
133    void tryToEnsureNoahsArkConditionQuickly(HTMLStackItem*, Vector<HTMLStackItem*>& remainingCandiates);
134    void ensureNoahsArkCondition(HTMLStackItem*);
135
136    Vector<Entry> m_entries;
137};
138
139}
140
141#endif // HTMLFormattingElementList_h
142