1// Protocol Buffers - Google's data interchange format
2// Copyright 2008 Google Inc. All rights reserved.
3// https://developers.google.com/protocol-buffers/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are
7// met:
8//
9// * Redistributions of source code must retain the above copyright
10// notice, this list of conditions and the following disclaimer.
11// * Redistributions in binary form must reproduce the above
12// copyright notice, this list of conditions and the following disclaimer
13// in the documentation and/or other materials provided with the
14// distribution.
15// * Neither the name of Google Inc. nor the names of its
16// contributors may be used to endorse or promote products derived from
17// this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31#ifndef GOOGLE_PROTOBUF_COMPILER_SCC_H__
32#define GOOGLE_PROTOBUF_COMPILER_SCC_H__
33
34#include <map>
35
36#include <google/protobuf/stubs/logging.h>
37#include <google/protobuf/stubs/common.h>
38#include <google/protobuf/descriptor.h>
39
40// Must be included last.
41#include <google/protobuf/port_def.inc>
42
43namespace google {
44namespace protobuf {
45namespace compiler {
46
47// Description of each strongly connected component. Note that the order
48// of both the descriptors in this SCC and the order of children is
49// deterministic.
50struct SCC {
51 std::vector<const Descriptor*> descriptors;
52 std::vector<const SCC*> children;
53
54 const Descriptor* GetRepresentative() const { return descriptors[0]; }
55
56 // All messages must necessarily be in the same file.
57 const FileDescriptor* GetFile() const { return descriptors[0]->file(); }
58};
59
60// This class is used for analyzing the SCC for each message, to ensure linear
61// instead of quadratic performance, if we do this per message we would get
62// O(V*(V+E)).
63template <class DepsGenerator>
64class PROTOC_EXPORT SCCAnalyzer {
65 public:
66 explicit SCCAnalyzer() : index_(0) {}
67
68 const SCC* GetSCC(const Descriptor* descriptor) {
69 if (cache_.count(descriptor)) return cache_[descriptor].scc;
70 return DFS(descriptor).scc;
71 }
72
73 private:
74 struct NodeData {
75 const SCC* scc; // if null it means its still on the stack
76 int index;
77 int lowlink;
78 };
79
80 std::map<const Descriptor*, NodeData> cache_;
81 std::vector<const Descriptor*> stack_;
82 int index_;
83 std::vector<std::unique_ptr<SCC>> garbage_bin_;
84
85 SCC* CreateSCC() {
86 garbage_bin_.emplace_back(args: new SCC());
87 return garbage_bin_.back().get();
88 }
89
90 // Tarjan's Strongly Connected Components algo
91 NodeData DFS(const Descriptor* descriptor) {
92 // Must not have visited already.
93 GOOGLE_DCHECK_EQ(cache_.count(descriptor), 0);
94
95 // Mark visited by inserting in map.
96 NodeData& result = cache_[descriptor];
97 // Initialize data structures.
98 result.index = result.lowlink = index_++;
99 stack_.push_back(x: descriptor);
100
101 // Recurse the fields / nodes in graph
102 for (auto dep : DepsGenerator()(descriptor)) {
103 GOOGLE_CHECK(dep);
104 if (cache_.count(dep) == 0) {
105 // unexplored node
106 NodeData child_data = DFS(descriptor: dep);
107 result.lowlink = std::min(result.lowlink, child_data.lowlink);
108 } else {
109 NodeData child_data = cache_[dep];
110 if (child_data.scc == nullptr) {
111 // Still in the stack_ so we found a back edge
112 result.lowlink = std::min(result.lowlink, child_data.index);
113 }
114 }
115 }
116 if (result.index == result.lowlink) {
117 // This is the root of a strongly connected component
118 SCC* scc = CreateSCC();
119 while (true) {
120 const Descriptor* scc_desc = stack_.back();
121 scc->descriptors.push_back(x: scc_desc);
122 // Remove from stack
123 stack_.pop_back();
124 cache_[scc_desc].scc = scc;
125
126 if (scc_desc == descriptor) break;
127 }
128
129 // The order of descriptors is random and depends how this SCC was
130 // discovered. In-order to ensure maximum stability we sort it by name.
131 std::sort(scc->descriptors.begin(), scc->descriptors.end(),
132 [](const Descriptor* a, const Descriptor* b) {
133 return a->full_name() < b->full_name();
134 });
135 AddChildren(scc);
136 }
137 return result;
138 }
139
140 // Add the SCC's that are children of this SCC to its children.
141 void AddChildren(SCC* scc) {
142 std::set<const SCC*> seen;
143 for (auto descriptor : scc->descriptors) {
144 for (auto child_msg : DepsGenerator()(descriptor)) {
145 GOOGLE_CHECK(child_msg);
146 const SCC* child = GetSCC(descriptor: child_msg);
147 if (child == scc) continue;
148 if (seen.insert(x: child).second) {
149 scc->children.push_back(x: child);
150 }
151 }
152 }
153 }
154
155 // This is necessary for compiler bug in msvc2015.
156 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(SCCAnalyzer);
157};
158
159} // namespace compiler
160} // namespace protobuf
161} // namespace google
162
163#include <google/protobuf/port_undef.inc>
164
165#endif // GOOGLE_PROTOBUF_COMPILER_SCC_H__
166