From patchwork Tue Jun 22 10:33:15 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43952 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id A4861394D828 for ; Tue, 22 Jun 2021 10:33:39 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org A4861394D828 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1624358019; bh=OyMpIQX54A93zGujrKZe5JsnTuUOPvbrnGPvVhA5ohs=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=camjHygpDZRUKG0BVZgk7KRfhtuzDKecCIOfkj1CI0AD1WD6ami3BYA7GPoJofAYw lyjKNwY8QiuuIwVe228u0YDFxbiRuSv1ARnzDOe1eKMi5P2pR6aRqSh6Qnpl0x17ZS uLYax98KC09ia1qvOC60q+nAu4RtX767GCPpkEM8= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-wr1-x449.google.com (mail-wr1-x449.google.com [IPv6:2a00:1450:4864:20::449]) by sourceware.org (Postfix) with ESMTPS id 368AE388C00B for ; Tue, 22 Jun 2021 10:33:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 368AE388C00B Received: by mail-wr1-x449.google.com with SMTP id h104-20020adf90710000b029010de8455a3aso9542924wrh.12 for ; Tue, 22 Jun 2021 03:33:32 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:in-reply-to:message-id:mime-version :references:subject:from:to:cc; bh=OyMpIQX54A93zGujrKZe5JsnTuUOPvbrnGPvVhA5ohs=; b=C1Txw7mOMzR9CANhTFX0qYrZliOfyeN+aoZur1nXRjCBuDHzf7ARXv1XmqWcIsuv92 FghkNWqf6KRmnakyS2lUKyMzbUWAHS+cwTHmvXhDfQxGPY+Wa0KLC0QI63+lBSJUIsal oE3A+SvOv0WtuKX73at0kehzAzUkNBS3KpDmsdYaKeWr0J41P78vTNcp3Ayt1o7WDKnX X6+AaVVPVxkwwi0bPZ6R0A1vVHBBhmV4lOVsbc+d8q60kCt+0efhs+yaVy5K9U+F2Z7Z vnaa4zPeSDVAyCfIjp5EGyldwOJYex5rltUIU0RhBVP/ZICd/sN+iEpci1n8QVzu+ATD 7HIA== X-Gm-Message-State: AOAM531zLsjSrM+IC690sxctLNgB5AwN6X2j8oB7N5xi0GIun7gKXX6U Xz/+WDhgoF5/NvZNtSWMBFT4XjPxfoL4BaeAmGo7sawMa+On2WMEwqEXBDc3YaOpe9s3nj0y83+ h1PB7RA1Gqj3nUr4MhVOotZi0JvJsuRK9n5xcyIf2lvmZVeqVm4ex+wak5XSCbLQVNSjsUOs= X-Google-Smtp-Source: ABdhPJwhOMxSEb2AQU1aWXCPke+XYP/DdBgQ4c1jt3DvnzPmAs4w/Det1Ft7Nvgd0HJXzi3nG+UnEaAfoCdHBw== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:b7d7:a6fe:d167:7a5d]) (user=gprocida job=sendgmr) by 2002:a05:6000:128b:: with SMTP id f11mr3876573wrx.171.1624358011277; Tue, 22 Jun 2021 03:33:31 -0700 (PDT) Date: Tue, 22 Jun 2021 11:33:15 +0100 In-Reply-To: <20210622103318.478914-1-gprocida@google.com> Message-Id: <20210622103318.478914-4-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> <20210622103318.478914-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.288.g62a8d224e6-goog Subject: [PATCH v2 3/6] BTF: add SCC finder and test To: libabigail@sourceware.org X-Spam-Status: No, score=-23.0 required=5.0 tests=BAYES_00, DKIMWL_WL_MED, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, USER_IN_DEF_DKIM_WL autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libabigail@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Mailing list of the Libabigail project List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-Patchwork-Original-From: Giuliano Procida via Libabigail From: Giuliano Procida Reply-To: Giuliano Procida Cc: maennich@google.com, kernel-team@android.com Errors-To: libabigail-bounces+patchwork=sourceware.org@sourceware.org Sender: "Libabigail" The files are almost a straight copy of the originals. Changes: - Files renamed and #includes updated. - Header guards and include order are now in libabigail style. * include/abg-scc.h (SCC): New class to find SCCs. * tests/test-scc.cc: SCC test with randomly-generated graphs. * tests/Makefile.am: Add SCC test, conditional on C++17. Signed-off-by: Giuliano Procida --- include/abg-scc.h | 111 ++++++++++++++++++++++++++++ tests/Makefile.am | 7 ++ tests/test-scc.cc | 183 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 301 insertions(+) create mode 100644 include/abg-scc.h create mode 100644 tests/test-scc.cc diff --git a/include/abg-scc.h b/include/abg-scc.h new file mode 100644 index 00000000..8c542e67 --- /dev/null +++ b/include/abg-scc.h @@ -0,0 +1,111 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020 Google, Inc. +// +// Author: Giuliano Procida + +#ifndef __ABG_SCC_H__ +#define __ABG_SCC_H__ + +#include +#include +#include +#include +#include + +namespace abigail { + +/* + * This is a streamlined Strongly-Connected Component finder for use with + * procedurally generated or explored graphs, where the nodes and edges are not + * known a priori. + * + * REQUIREMENTS + * + * The Node type must be copyable and have a suitable hash function. + * + * The user code must take the form of a Depth First Search which can be + * repeatedly invoked on unvisited nodes until the whole graph has been + * traversed. + * + * The user code must always follow edges to child nodes, even if it knows the + * node has already been visited. The SCC finder needs to know about all edges. + * + * The user code must ensure that nodes are not re-examined once they have been + * assigned to an SCC. The finder does not maintain any state for such nodes. + * + * GUARANTEES + * + * The SCC finder will ensure each node is examined exactly once. + * + * The SCCs will be presented in a topological order, leaves first. + * + * Note that within each SCC, nodes will be presented in DFS traversal order, + * roots first. However, this is just an implemention detail, not a guarantee. + * + * USAGE + * + * Before examining a node, check it's not been assigned to an SCC already and + * then call Open. If the node is already "open" (i.e., is already waiting to be + * assigned to an SCC), this will return an empty optional value and the node + * should not be examined. If Open succeeds, a numerical node handle will be + * returned and the node will be recorded as waiting to be assigned to an SCC. + * + * Now examine the node, making recursive calls to follow edges to other nodes. + * Infomation about the node can be stored provisionally, but must NOT be used + * to make decisions about whether to revisit it - that is Open's job. + * + * Once the examination is done, call Close, passing in the handle. If the node + * has been identified as the "root" of an SCC, the whole SCC will be returned + * as a vector of nodes. If any processing needs to be done (such as recording + * the nodes as visited), this should be done now. Otherwise, an empty vector + * will be returned. + */ +template> class SCC { + public: + ~SCC() { + assert(open_.empty()); + assert(is_open_.empty()); + assert(root_index_.empty()); + } + + std::optional Open(const Node &node) { + // Insertion will fail if the node is already open. + auto [it, inserted] = is_open_.insert({node, is_open_.size()}); + auto ix = it->second; + if (!inserted) { + // Pop indices to nodes which cannot be the root of their SCC. + while (root_index_.back() > ix) + root_index_.pop_back(); + return {}; + } + // Unvisited, record open node and record root index. + open_.push_back(node); + root_index_.push_back(ix); + return ix; + } + + std::vector Close(size_t ix) { + std::vector scc; + assert(ix < open_.size()); + if (ix == root_index_.back()) { + // Close SCC. + for (size_t o = ix; o < open_.size(); ++o) + is_open_.erase(open_[o]); + std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); + open_.resize(ix); + root_index_.pop_back(); + } + return scc; + } + + private: + std::vector open_; // index to node + std::unordered_map is_open_; // node to index + std::vector root_index_; +}; + +} // namespace abigail + +#endif // __ABG_SCC_H__ diff --git a/tests/Makefile.am b/tests/Makefile.am index 7a3a1f98..95df9542 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -53,6 +53,10 @@ else TESTS += runtestdefaultsupprs.py endif +if ENABLE_CXX17 +TESTS += runtestscc +endif + EXTRA_DIST = \ runtestcanonicalizetypes.sh.in \ runtestfedabipkgdiff.py.in \ @@ -166,6 +170,9 @@ testdiff2_LDADD=$(top_builddir)/src/libabigail.la printdifftree_SOURCES = print-diff-tree.cc printdifftree_LDADD = $(top_builddir)/src/libabigail.la +runtestscc_SOURCES = test-scc.cc +runtestscc_LDADD = libcatch.la + runtestslowselfcompare_sh_SOURCES = runtestslowselfcompare.sh$(EXEEXT): diff --git a/tests/test-scc.cc b/tests/test-scc.cc new file mode 100644 index 00000000..a75b1ae0 --- /dev/null +++ b/tests/test-scc.cc @@ -0,0 +1,183 @@ +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// -*- mode: C++ -*- +// +// Copyright (C) 2020 Google, Inc. +// +// Author: Giuliano Procida + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "lib/catch.hpp" + +#include "abg-scc.h" + +namespace Test { + +using abigail::SCC; + +// Nodes are [0, N), the sets are the out-edges. +typedef std::vector> Graph; + +std::ostream &operator<<(std::ostream &os, const Graph &g) { + for (size_t i = 0; i < g.size(); ++i) { + os << i << ':'; + for (auto o : g[i]) + os << ' ' << o; + os << '\n'; + } + return os; +} + +template Graph invent(size_t n, G& gen) { + Graph graph(n); + std::uniform_int_distribution toss(0, 1); + for (auto &node : graph) { + for (size_t o = 0; o < n; ++o) { + if (toss(gen)) + node.insert(o); + } + } + return graph; +} + +// Generate a graph g' where a -> b iff a and b are strongly connected in g. +Graph symmetric_subset_of_reflexive_transitive_closure(Graph g) { + const size_t n = g.size(); + // transitive closure using Floyd-Warshall + for (size_t o = 0; o < n; ++o) + g[o].insert(o); + for (size_t k = 0; k < n; ++k) { + for (size_t i = 0; i < n; ++i) { + for (size_t j = 0; j < n; ++j) { + if (!g[i].count(j) && g[i].count(k) && g[k].count(j)) + g[i].insert(j); + } + } + } + // now a -> b iff a has path to b in g + for (size_t i = 0; i < n; ++i) { + for (size_t j = i + 1; j < n; ++j) { + // discard a -> b if not b -> a and vice versa + auto ij = g[i].count(j); + auto ji = g[j].count(i); + if (ij < ji) g[j].erase(i); + if (ji < ij) g[i].erase(j); + } + } + // now have a -> b iff a has path to b and b has path to a in g + return g; +} + +// Generate a graph where a -> b iff a and b are in the same SCC. +Graph scc_strong_connectivity(const std::vector> &sccs) { + size_t n = 0; + std::map *> edges; + for (const auto &scc : sccs) { + for (auto o : scc) { + if (o >= n) + n = o + 1; + edges[o] = &scc; + } + } + Graph g(n); + for (size_t o = 0; o < n; ++o) + g[o] = *edges[o]; + return g; +} + +void dfs(std::set &visited, SCC &scc, + const Graph &g, size_t node, + std::vector> &sccs) { + if (visited.count(node)) + return; + auto handle = scc.Open(node); + if (!handle) + return; + for (auto o : g[node]) + dfs(visited, scc, g, o, sccs); + auto nodes = scc.Close(handle.value()); + if (!nodes.empty()) { + std::set scc_set; + for (auto o : nodes) { + CHECK(visited.insert(o).second); + CHECK(scc_set.insert(o).second); + } + sccs.push_back(scc_set); + } +} + +void process(const Graph &g) { + const size_t n = g.size(); + + // find SCCs + std::set visited; + SCC scc; + std::vector> sccs; + for (size_t o = 0; o < n; ++o) + dfs(visited, scc, g, o, sccs); + + // check partition and topological order properties + std::set seen; + for (const auto &nodes : sccs) { + CHECK(!nodes.empty()); + for (auto node : nodes) { + // value in range [0, n) + CHECK(node < n); + // value seen at most once + CHECK(seen.insert(node).second); + } + for (auto node : nodes) { + for (auto o : g[node]) { + // edges point to nodes in this or earlier SCCs + CHECK(seen.count(o)); + } + } + } + // exactly n values seen + CHECK(seen.size() == n); + + // check strong connectivity + auto g_scc_closure = scc_strong_connectivity(sccs); + auto g_closure = symmetric_subset_of_reflexive_transitive_closure(g); + // catch isn't printing nicely + if (g_scc_closure != g_closure) { + std::cerr << "original:\n" << g + << "SCC finder:\n" << g_scc_closure + << "SCCs independently:\n" << g_closure; + } + CHECK(g_scc_closure == g_closure); +} + +TEST_CASE("randomly-generated graphs") { + std::mt19937 gen; + auto seed = gen(); + // NOTES: + // Graphs of size 6 are plenty big enough to shake out bugs. + // There are O(2^k^2) possible directed graphs of size k. + // Testing costs are O(k^3) so we restrict accordingly. + uint64_t budget = 10000; + for (size_t k = 0; k < 7; ++k) { + uint64_t count = std::min(static_cast(1) << (k*k), + budget / (k ? k * k * k : 1)); + INFO("testing with " << count << " graphs of size " << k); + for (uint64_t n = 0; n < count; ++n, ++seed) { + gen.seed(seed); + Graph g = invent(k, gen); + std::ostringstream os; + os << "a graph of " << k << " nodes generated using seed " << seed; + GIVEN(os.str()) { + process(g); + } + } + } +} + +} // namespace Test