1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // 4 // Use of this source code is governed by a BSD-style 5 // license that can be found in the LICENSE file or at 6 // https://developers.google.com/open-source/licenses/bsd 7 8 #ifndef GOOGLE_PROTOBUF_COMPILER_SCC_H__ 9 #define GOOGLE_PROTOBUF_COMPILER_SCC_H__ 10 11 #include <memory> 12 13 #include "absl/container/flat_hash_map.h" 14 #include "absl/container/flat_hash_set.h" 15 #include "absl/log/absl_check.h" 16 #include "absl/memory/memory.h" 17 #include "google/protobuf/descriptor.h" 18 19 // Must be included last. 20 #include "google/protobuf/port_def.inc" 21 22 namespace google { 23 namespace protobuf { 24 namespace compiler { 25 26 // Description of each strongly connected component. Note that the order 27 // of both the descriptors in this SCC and the order of children is 28 // deterministic. 29 struct SCC { 30 std::vector<const Descriptor*> descriptors; 31 std::vector<const SCC*> children; 32 GetRepresentativeSCC33 const Descriptor* GetRepresentative() const { return descriptors[0]; } 34 35 // All messages must necessarily be in the same file. GetFileSCC36 const FileDescriptor* GetFile() const { return descriptors[0]->file(); } 37 }; 38 39 // This class is used for analyzing the SCC for each message, to ensure linear 40 // instead of quadratic performance, if we do this per message we would get 41 // O(V*(V+E)). 42 template <class DepsGenerator> 43 class PROTOC_EXPORT SCCAnalyzer { 44 public: SCCAnalyzer()45 explicit SCCAnalyzer() : index_(0) {} 46 SCCAnalyzer(const SCCAnalyzer&) = delete; 47 SCCAnalyzer& operator=(const SCCAnalyzer&) = delete; 48 GetSCC(const Descriptor * descriptor)49 const SCC* GetSCC(const Descriptor* descriptor) { 50 auto it = cache_.find(descriptor); 51 if (it == cache_.end()) { 52 return DFS(descriptor).scc; 53 } 54 return it->second->scc; 55 } 56 57 private: 58 struct NodeData { 59 const SCC* scc; // if null it means its still on the stack 60 int index; 61 int lowlink; 62 }; 63 64 absl::flat_hash_map<const Descriptor*, std::unique_ptr<NodeData>> cache_; 65 std::vector<const Descriptor*> stack_; 66 int index_; 67 std::vector<std::unique_ptr<SCC>> garbage_bin_; 68 CreateSCC()69 SCC* CreateSCC() { 70 garbage_bin_.emplace_back(new SCC()); 71 return garbage_bin_.back().get(); 72 } 73 74 // Tarjan's Strongly Connected Components algo DFS(const Descriptor * descriptor)75 NodeData DFS(const Descriptor* descriptor) { 76 // Mark visited by inserting in map. 77 auto ins = cache_.try_emplace(descriptor, absl::make_unique<NodeData>()); 78 // Must not have visited already. 79 ABSL_DCHECK(ins.second); 80 NodeData& result = *ins.first->second; 81 // Initialize data structures. 82 result.index = result.lowlink = index_++; 83 stack_.push_back(descriptor); 84 85 // Recurse the fields / nodes in graph 86 for (const auto* dep : DepsGenerator()(descriptor)) { 87 ABSL_CHECK(dep); 88 auto it = cache_.find(dep); 89 if (it == cache_.end()) { 90 // unexplored node 91 NodeData child_data = DFS(dep); 92 result.lowlink = std::min(result.lowlink, child_data.lowlink); 93 } else { 94 NodeData& child_data = *it->second; 95 if (child_data.scc == nullptr) { 96 // Still in the stack_ so we found a back edge 97 result.lowlink = std::min(result.lowlink, child_data.index); 98 } 99 } 100 } 101 if (result.index == result.lowlink) { 102 // This is the root of a strongly connected component 103 SCC* scc = CreateSCC(); 104 while (true) { 105 const Descriptor* scc_desc = stack_.back(); 106 scc->descriptors.push_back(scc_desc); 107 // Remove from stack 108 stack_.pop_back(); 109 cache_[scc_desc]->scc = scc; 110 111 if (scc_desc == descriptor) break; 112 } 113 114 // The order of descriptors is random and depends how this SCC was 115 // discovered. In-order to ensure maximum stability we sort it by name. 116 std::sort(scc->descriptors.begin(), scc->descriptors.end(), 117 [](const Descriptor* a, const Descriptor* b) { 118 return a->full_name() < b->full_name(); 119 }); 120 AddChildren(scc); 121 } 122 return result; 123 } 124 125 // Add the SCC's that are children of this SCC to its children. AddChildren(SCC * scc)126 void AddChildren(SCC* scc) { 127 absl::flat_hash_set<const SCC*> seen; 128 for (auto descriptor : scc->descriptors) { 129 for (auto child_msg : DepsGenerator()(descriptor)) { 130 ABSL_CHECK(child_msg); 131 const SCC* child = GetSCC(child_msg); 132 if (child == scc) continue; 133 if (seen.insert(child).second) { 134 scc->children.push_back(child); 135 } 136 } 137 } 138 } 139 }; 140 141 } // namespace compiler 142 } // namespace protobuf 143 } // namespace google 144 145 #include "google/protobuf/port_undef.inc" 146 147 #endif // GOOGLE_PROTOBUF_COMPILER_SCC_H__ 148