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 #include <google/protobuf/port_def.inc>
41 
42 namespace google {
43 namespace protobuf {
44 namespace compiler {
45 
46 // Description of each strongly connected component. Note that the order
47 // of both the descriptors in this SCC and the order of children is
48 // deterministic.
49 struct SCC {
50   std::vector<const Descriptor*> descriptors;
51   std::vector<const SCC*> children;
52 
GetRepresentativeSCC53   const Descriptor* GetRepresentative() const { return descriptors[0]; }
54 
55   // All messages must necessarily be in the same file.
GetFileSCC56   const FileDescriptor* GetFile() const { return descriptors[0]->file(); }
57 };
58 
59 // This class is used for analyzing the SCC for each message, to ensure linear
60 // instead of quadratic performance, if we do this per message we would get
61 // O(V*(V+E)).
62 template <class DepsGenerator>
63 class PROTOC_EXPORT SCCAnalyzer {
64  public:
SCCAnalyzer()65   explicit SCCAnalyzer() : index_(0) {}
66 
GetSCC(const Descriptor * descriptor)67   const SCC* GetSCC(const Descriptor* descriptor) {
68     if (cache_.count(descriptor)) return cache_[descriptor].scc;
69     return DFS(descriptor).scc;
70   }
71 
72  private:
73   struct NodeData {
74     const SCC* scc;  // if null it means its still on the stack
75     int index;
76     int lowlink;
77   };
78 
79   std::map<const Descriptor*, NodeData> cache_;
80   std::vector<const Descriptor*> stack_;
81   int index_;
82   std::vector<std::unique_ptr<SCC>> garbage_bin_;
83 
CreateSCC()84   SCC* CreateSCC() {
85     garbage_bin_.emplace_back(new SCC());
86     return garbage_bin_.back().get();
87   }
88 
89   // Tarjan's Strongly Connected Components algo
DFS(const Descriptor * descriptor)90   NodeData DFS(const Descriptor* descriptor) {
91     // Must not have visited already.
92     GOOGLE_DCHECK_EQ(cache_.count(descriptor), 0);
93 
94     // Mark visited by inserting in map.
95     NodeData& result = cache_[descriptor];
96     // Initialize data structures.
97     result.index = result.lowlink = index_++;
98     stack_.push_back(descriptor);
99 
100     // Recurse the fields / nodes in graph
101     for (auto dep : DepsGenerator()(descriptor)) {
102       GOOGLE_CHECK(dep);
103       if (cache_.count(dep) == 0) {
104         // unexplored node
105         NodeData child_data = DFS(dep);
106         result.lowlink = std::min(result.lowlink, child_data.lowlink);
107       } else {
108         NodeData child_data = cache_[dep];
109         if (child_data.scc == nullptr) {
110           // Still in the stack_ so we found a back edge
111           result.lowlink = std::min(result.lowlink, child_data.index);
112         }
113       }
114     }
115     if (result.index == result.lowlink) {
116       // This is the root of a strongly connected component
117       SCC* scc = CreateSCC();
118       while (true) {
119         const Descriptor* scc_desc = stack_.back();
120         scc->descriptors.push_back(scc_desc);
121         // Remove from stack
122         stack_.pop_back();
123         cache_[scc_desc].scc = scc;
124 
125         if (scc_desc == descriptor) break;
126       }
127 
128       // The order of descriptors is random and depends how this SCC was
129       // discovered. In-order to ensure maximum stability we sort it by name.
130       std::sort(scc->descriptors.begin(), scc->descriptors.end(),
131                 [](const Descriptor* a, const Descriptor* b) {
132                   return a->full_name() < b->full_name();
133                 });
134       AddChildren(scc);
135     }
136     return result;
137   }
138 
139   // Add the SCC's that are children of this SCC to its children.
AddChildren(SCC * scc)140   void AddChildren(SCC* scc) {
141     std::set<const SCC*> seen;
142     for (auto descriptor : scc->descriptors) {
143       for (auto child_msg : DepsGenerator()(descriptor)) {
144         GOOGLE_CHECK(child_msg);
145         const SCC* child = GetSCC(child_msg);
146         if (child == scc) continue;
147         if (seen.insert(child).second) {
148           scc->children.push_back(child);
149         }
150       }
151     }
152   }
153 
154   // This is necessary for compiler bug in msvc2015.
155   GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(SCCAnalyzer);
156 };
157 
158 }  // namespace compiler
159 }  // namespace protobuf
160 }  // namespace google
161 
162 #include <google/protobuf/port_undef.inc>
163 
164 #endif  // GOOGLE_PROTOBUF_COMPILER_SCC_H__
165