protobuf/compiler/scc.h

0001 // Protocol Buffers - Google's data interchange format
0002 // Copyright 2008 Google Inc.  All rights reserved.
0003 //
0004 // Use of this source code is governed by a BSD-style
0005 // license that can be found in the LICENSE file or at
0006 // https://developers.google.com/open-source/licenses/bsd
0007
0008 #ifndef GOOGLE_PROTOBUF_COMPILER_SCC_H__
0009 #define GOOGLE_PROTOBUF_COMPILER_SCC_H__
0010
0011 #include <memory>
0012
0013 #include "absl/container/flat_hash_map.h"
0014 #include "absl/container/flat_hash_set.h"
0015 #include "absl/log/absl_check.h"
0016 #include "absl/memory/memory.h"
0017 #include "google/protobuf/descriptor.h"
0018
0019 // Must be included last.
0020 #include "google/protobuf/port_def.inc"
0021
0022 namespace google {
0023 namespace protobuf {
0024 namespace compiler {
0025
0026 // Description of each strongly connected component. Note that the order
0027 // of both the descriptors in this SCC and the order of children is
0028 // deterministic.
0029 struct SCC {
0030   std::vector<const Descriptor*> descriptors;
0031   std::vector<const SCC*> children;
0032
0033   const Descriptor* GetRepresentative() const { return descriptors[0]; }
0034
0035   // All messages must necessarily be in the same file.
0036   const FileDescriptor* GetFile() const { return descriptors[0]->file(); }
0037 };
0038
0039 // This class is used for analyzing the SCC for each message, to ensure linear
0040 // instead of quadratic performance, if we do this per message we would get
0041 // O(V*(V+E)).
0042 template <class DepsGenerator>
0043 class PROTOC_EXPORT SCCAnalyzer {
0044  public:
0045   explicit SCCAnalyzer() : index_(0) {}
0046   SCCAnalyzer(const SCCAnalyzer&) = delete;
0047   SCCAnalyzer& operator=(const SCCAnalyzer&) = delete;
0048
0049   const SCC* GetSCC(const Descriptor* descriptor) {
0050     auto it = cache_.find(descriptor);
0051     if (it == cache_.end()) {
0052       return DFS(descriptor).scc;
0053     }
0054     return it->second->scc;
0055   }
0056
0057  private:
0058   struct NodeData {
0059     const SCC* scc;  // if null it means its still on the stack
0060     int index;
0061     int lowlink;
0062   };
0063
0064   absl::flat_hash_map<const Descriptor*, std::unique_ptr<NodeData>> cache_;
0065   std::vector<const Descriptor*> stack_;
0066   int index_;
0067   std::vector<std::unique_ptr<SCC>> garbage_bin_;
0068
0069   SCC* CreateSCC() {
0070     garbage_bin_.emplace_back(new SCC());
0071     return garbage_bin_.back().get();
0072   }
0073
0074   // Tarjan's Strongly Connected Components algo
0075   NodeData DFS(const Descriptor* descriptor) {
0076     // Mark visited by inserting in map.
0077     auto ins = cache_.try_emplace(descriptor, absl::make_unique<NodeData>());
0078     // Must not have visited already.
0079     ABSL_DCHECK(ins.second);
0080     NodeData& result = *ins.first->second;
0081     // Initialize data structures.
0082     result.index = result.lowlink = index_++;
0083     stack_.push_back(descriptor);
0084
0085     // Recurse the fields / nodes in graph
0086     for (const auto* dep : DepsGenerator()(descriptor)) {
0087       ABSL_CHECK(dep);
0088       auto it = cache_.find(dep);
0089       if (it == cache_.end()) {
0090         // unexplored node
0091         NodeData child_data = DFS(dep);
0092         result.lowlink = std::min(result.lowlink, child_data.lowlink);
0093       } else {
0094         NodeData& child_data = *it->second;
0095         if (child_data.scc == nullptr) {
0096           // Still in the stack_ so we found a back edge
0097           result.lowlink = std::min(result.lowlink, child_data.index);
0098         }
0099       }
0100     }
0101     if (result.index == result.lowlink) {
0102       // This is the root of a strongly connected component
0103       SCC* scc = CreateSCC();
0104       while (true) {
0105         const Descriptor* scc_desc = stack_.back();
0106         scc->descriptors.push_back(scc_desc);
0107         // Remove from stack
0108         stack_.pop_back();
0109         cache_[scc_desc]->scc = scc;
0110
0111         if (scc_desc == descriptor) break;
0112       }
0113
0114       // The order of descriptors is random and depends how this SCC was
0115       // discovered. In-order to ensure maximum stability we sort it by name.
0116       std::sort(scc->descriptors.begin(), scc->descriptors.end(),
0117                 [](const Descriptor* a, const Descriptor* b) {
0118                   return a->full_name() < b->full_name();
0119                 });
0120       AddChildren(scc);
0121     }
0122     return result;
0123   }
0124
0125   // Add the SCC's that are children of this SCC to its children.
0126   void AddChildren(SCC* scc) {
0127     absl::flat_hash_set<const SCC*> seen;
0128     for (auto descriptor : scc->descriptors) {
0129       for (auto child_msg : DepsGenerator()(descriptor)) {
0130         ABSL_CHECK(child_msg);
0131         const SCC* child = GetSCC(child_msg);
0132         if (child == scc) continue;
0133         if (seen.insert(child).second) {
0134           scc->children.push_back(child);
0135         }
0136       }
0137     }
0138   }
0139 };
0140
0141 }  // namespace compiler
0142 }  // namespace protobuf
0143 }  // namespace google
0144
0145 #include "google/protobuf/port_undef.inc"
0146
0147 #endif  // GOOGLE_PROTOBUF_COMPILER_SCC_H__