Unreviewed, rolling out r234489.
[WebKit-https.git] / Source / WTF / wtf / SingleRootGraph.h
1 /*
2  * Copyright (C) 2017 Apple 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 APPLE 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 APPLE 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 WTF_SingleRootGraph_h
27 #define WTF_SingleRootGraph_h
28
29 #include <wtf/FastMalloc.h>
30 #include <wtf/GraphNodeWorklist.h>
31 #include <wtf/Noncopyable.h>
32 #include <wtf/StdLibExtras.h>
33
34 namespace WTF {
35
36 template <typename Graph>
37 class SingleRootGraphNode {
38 public:
39     // We use "#root" to refer to the synthetic root we have created.
40     static const char* rootName() { return "#root"; };
41
42     SingleRootGraphNode(typename Graph::Node node = typename Graph::Node())
43         : m_node(node)
44     {
45     }
46
47     static SingleRootGraphNode root()
48     {
49         SingleRootGraphNode result;
50         result.m_node = 0;
51         result.m_isRoot = true;
52         return result;
53     }
54
55     bool operator==(const SingleRootGraphNode& other) const
56     {
57         return m_node == other.m_node
58             && m_isRoot == other.m_isRoot;
59     }
60
61     bool operator!=(const SingleRootGraphNode& other) const
62     {
63         return !(*this == other);
64     }
65
66     explicit operator bool() const { return *this != SingleRootGraphNode(); }
67
68     bool isRoot() const
69     {
70         return m_isRoot;
71     }
72
73     typename Graph::Node node() const
74     {
75         ASSERT(!m_isRoot);
76         return m_node;
77     }
78
79 private:
80     typename Graph::Node m_node;
81     bool m_isRoot { false };
82 };
83
84 template <typename Graph>
85 class SingleRootGraphSet {
86     using Node = SingleRootGraphNode<Graph>;
87 public:
88     SingleRootGraphSet() = default;
89     
90     bool add(const Node& node)
91     {
92         if (node.isRoot())
93             return checkAndSet(m_hasRoot, true);
94         return m_set.add(node.node());
95     }
96
97     bool remove(const Node& node)
98     {
99         if (node.isRoot())
100             return checkAndSet(m_hasRoot, false);
101         return m_set.remove(node.node());
102     }
103
104     bool contains(const Node& node)
105     {
106         if (node.isRoot())
107             return m_hasRoot;
108         return m_set.contains(node.node());
109     }
110
111     void dump(PrintStream& out) const
112     {
113         if (m_hasRoot)
114             out.print(Node::rootName(), " ");
115         out.print(m_set);
116     }
117     
118 private:
119     typename Graph::Set m_set;
120     bool m_hasRoot { false };
121 };
122
123 template<typename T, typename Graph>
124 class SingleRootMap {
125     using Node = SingleRootGraphNode<Graph>;
126 public:
127     SingleRootMap(Graph& graph)
128         : m_map(graph.template newMap<T>())
129     {
130     }
131
132     SingleRootMap(SingleRootMap&& other)
133         : m_map(WTFMove(other.m_map))
134         , m_root(WTFMove(other.m_root))
135     {
136     }
137
138     void clear()
139     {
140         m_map.clear();
141         m_root = T();
142     }
143
144     size_t size() const { return m_map.size() + 1; }
145
146     T& operator[](size_t index)
147     {
148         if (!index)
149             return m_root;
150         return m_map[index - 1];
151     }
152
153     const T& operator[](size_t index) const
154     {
155         return (*const_cast<SingleRootMap*>(this))[index];
156     }
157
158     T& operator[](const Node& node)
159     {
160         if (node.isRoot())
161             return m_root;
162         return m_map[node.node()];
163     }
164
165     const T& operator[](const Node& node) const
166     {
167         return (*const_cast<SingleRootMap*>(this))[node];
168     }
169     
170 private:
171     typename Graph::template Map<T> m_map;
172     T m_root;
173 };
174
175 template<typename Graph>
176 class SingleRootGraph {
177     WTF_MAKE_NONCOPYABLE(SingleRootGraph);
178     WTF_MAKE_FAST_ALLOCATED;
179 public:
180
181     using Node = SingleRootGraphNode<Graph>;
182     using Set = SingleRootGraphSet<Graph>;
183     template <typename T> using Map = SingleRootMap<T, Graph>;
184     using List = Vector<Node, 4>;
185
186     SingleRootGraph(Graph& graph)
187         : m_graph(graph)
188     {
189         for (typename Graph::Node realRoot : m_graph.roots()) {
190             ASSERT(m_graph.predecessors(realRoot).isEmpty());
191             m_rootSuccessorList.append(realRoot);
192             m_rootSuccessorSet.add(realRoot);
193         }
194         ASSERT(m_rootSuccessorList.size());
195     }
196
197     Node root() const { return Node::root(); }
198
199     template<typename T>
200     Map<T> newMap() { return Map<T>(m_graph); }
201
202     List successors(const Node& node) const
203     {
204         assertIsConsistent();
205
206         if (node.isRoot())
207             return m_rootSuccessorList;
208         List result;
209         for (typename Graph::Node successor : m_graph.successors(node.node()))
210             result.append(successor);
211         return result;
212     }
213
214     List predecessors(const Node& node) const
215     {
216         assertIsConsistent();
217
218         if (node.isRoot())
219             return List { };
220
221         if (m_rootSuccessorSet.contains(node.node())) {
222             ASSERT(m_graph.predecessors(node.node()).isEmpty());
223             return List { root() };
224         }
225
226         List result;
227         for (typename Graph::Node predecessor : m_graph.predecessors(node.node()))
228             result.append(predecessor);
229         return result;
230     }
231
232     unsigned index(const Node& node) const
233     {
234         if (node.isRoot())
235             return 0;
236         return m_graph.index(node.node()) + 1;
237     }
238
239     Node node(unsigned index) const
240     {
241         if (!index)
242             return root();
243         return m_graph.node(index - 1);
244     }
245
246     unsigned numNodes() const
247     {
248         return m_graph.numNodes() + 1;
249     }
250
251     CString dump(Node node) const
252     {
253         StringPrintStream out;
254         if (!node)
255             out.print("<null>");
256         else if (node.isRoot())
257             out.print(Node::rootName());
258         else
259             out.print(m_graph.dump(node.node()));
260         return out.toCString();
261     }
262
263     void dump(PrintStream& out) const
264     {
265         for (unsigned i = 0; i < numNodes(); ++i) {
266             Node node = this->node(i);
267             if (!node)
268                 continue;
269             out.print(dump(node), ":\n");
270             out.print("    Preds: ");
271             CommaPrinter comma;
272             for (Node predecessor : predecessors(node))
273                 out.print(comma, dump(predecessor));
274             out.print("\n");
275             out.print("    Succs: ");
276             comma = CommaPrinter();
277             for (Node successor : successors(node))
278                 out.print(comma, dump(successor));
279             out.print("\n");
280         }
281     }
282
283 private:
284     ALWAYS_INLINE void assertIsConsistent() const
285     {
286 #if !ASSERT_DISABLED
287         // We expect the roots() function to be idempotent while we're alive so we can cache
288         // the result in the constructor. If a user of this changes the result of its roots()
289         // function, it's expected that the user will create a new instance of this class.
290         List rootSuccessorList;
291         for (typename Graph::Node realRoot : m_graph.roots()) {
292             ASSERT(m_graph.predecessors(realRoot).isEmpty());
293             rootSuccessorList.append(realRoot);
294         }
295         ASSERT(rootSuccessorList.size());
296         ASSERT(rootSuccessorList == m_rootSuccessorList);
297 #endif
298     }
299
300     Graph& m_graph;
301     List m_rootSuccessorList;
302     typename Graph::Set m_rootSuccessorSet;
303 };
304
305 } // namespace WTF
306
307 using WTF::SingleRootGraph;
308
309 #endif // WTF_SingleRootGraph_h