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 "core/html/parser/HTMLStackItem.h"
30#include "wtf/Forward.h"
31#include "wtf/RefPtr.h"
32#include "wtf/Vector.h"
33
34namespace blink {
35
36class Element;
37
38// This may end up merged into HTMLElementStack.
39class HTMLFormattingElementList {
40    WTF_MAKE_NONCOPYABLE(HTMLFormattingElementList);
41    DISALLOW_ALLOCATION();
42public:
43    HTMLFormattingElementList();
44    ~HTMLFormattingElementList();
45
46    // Ideally Entry would be private, but HTMLTreeBuilder has to coordinate
47    // between the HTMLFormattingElementList and HTMLElementStack and needs
48    // access to Entry::isMarker() and Entry::replaceElement() to do so.
49    class Entry {
50        ALLOW_ONLY_INLINE_ALLOCATION();
51    public:
52        // Inline because they're hot and Vector<T> uses them.
53        explicit Entry(PassRefPtrWillBeRawPtr<HTMLStackItem> item)
54            : m_item(item)
55        {
56        }
57        enum MarkerEntryType { MarkerEntry };
58        explicit Entry(MarkerEntryType)
59            : m_item(nullptr)
60        {
61        }
62        ~Entry() {}
63
64        bool isMarker() const { return !m_item; }
65
66        PassRefPtrWillBeRawPtr<HTMLStackItem> stackItem() const { return m_item; }
67        Element* element() const
68        {
69            // The fact that !m_item == isMarker() is an implementation detail
70            // callers should check isMarker() before calling element().
71            ASSERT(m_item);
72            return m_item->element();
73        }
74        void replaceElement(PassRefPtrWillBeRawPtr<HTMLStackItem> item) { m_item = item; }
75
76        // Needed for use with Vector.  These are super-hot and must be inline.
77        bool operator==(Element* element) const { return !m_item ? !element : m_item->element() == element; }
78        bool operator!=(Element* element) const { return !m_item ? !!element : m_item->element() != element; }
79
80        void trace(Visitor* visitor) { visitor->trace(m_item); }
81
82    private:
83        RefPtrWillBeMember<HTMLStackItem> m_item;
84    };
85
86    class Bookmark {
87    public:
88        explicit Bookmark(Entry* entry)
89            : m_hasBeenMoved(false)
90            , m_mark(entry)
91        {
92        }
93
94        void moveToAfter(Entry* before)
95        {
96            m_hasBeenMoved = true;
97            m_mark = before;
98        }
99
100        bool hasBeenMoved() const { return m_hasBeenMoved; }
101        Entry* mark() const { return m_mark; }
102
103    private:
104        bool m_hasBeenMoved;
105        Entry* m_mark;
106    };
107
108    bool isEmpty() const { return !size(); }
109    size_t size() const { return m_entries.size(); }
110
111    Element* closestElementInScopeWithName(const AtomicString&);
112
113    Entry* find(Element*);
114    bool contains(Element*);
115    void append(PassRefPtrWillBeRawPtr<HTMLStackItem>);
116    void remove(Element*);
117
118    Bookmark bookmarkFor(Element*);
119    void swapTo(Element* oldElement, PassRefPtrWillBeRawPtr<HTMLStackItem> newItem, const Bookmark&);
120
121    void appendMarker();
122    // clearToLastMarker also clears the marker (per the HTML5 spec).
123    void clearToLastMarker();
124
125    const Entry& at(size_t i) const { return m_entries[i]; }
126    Entry& at(size_t i) { return m_entries[i]; }
127
128    void trace(Visitor* visitor) { visitor->trace(m_entries); }
129
130#ifndef NDEBUG
131    void show();
132#endif
133
134private:
135    Entry* first() { return &at(0); }
136
137    // http://www.whatwg.org/specs/web-apps/current-work/multipage/parsing.html#list-of-active-formatting-elements
138    // These functions enforce the "Noah's Ark" condition, which removes redundant mis-nested elements.
139    void tryToEnsureNoahsArkConditionQuickly(HTMLStackItem*, WillBeHeapVector<RawPtrWillBeMember<HTMLStackItem> >& remainingCandiates);
140    void ensureNoahsArkCondition(HTMLStackItem*);
141
142    WillBeHeapVector<Entry> m_entries;
143};
144
145} // namespace blink
146
147WTF_ALLOW_MOVE_AND_INIT_WITH_MEM_FUNCTIONS(blink::HTMLFormattingElementList::Entry);
148
149#endif // HTMLFormattingElementList_h
150