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