From patchwork Fri Jun 11 15:33:16 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuliano Procida X-Patchwork-Id: 43834 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 DB33A38515E7 for ; Fri, 11 Jun 2021 15:34:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org DB33A38515E7 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1623425667; bh=AppFbIGceq/7qgWRXZpcEsZGbclnV4KoLQEA1L+OJMY=; h=Date:In-Reply-To:References:Subject:To:List-Id:List-Unsubscribe: List-Archive:List-Help:List-Subscribe:From:Reply-To:Cc:From; b=n19+3S9cR0q8X+GGPfoEhxrOW3uPiHwgxjo2nxzHDJKU+Lxw90gmiZDEBOY/wUJpn zdmQmVMr/5wMJHEMbsk0o3cOn7GMMFR5Kh7Egb+WgdmlLGwsT9oPNMnOBiMwEAF+Jc DoY5mSbh9CF64iqqN6PV2E/FBW0jgB/USQOaurig= X-Original-To: libabigail@sourceware.org Delivered-To: libabigail@sourceware.org Received: from mail-yb1-xb49.google.com (mail-yb1-xb49.google.com [IPv6:2607:f8b0:4864:20::b49]) by sourceware.org (Postfix) with ESMTPS id 8770C398B17A for ; Fri, 11 Jun 2021 15:34:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8770C398B17A Received: by mail-yb1-xb49.google.com with SMTP id g9-20020a25ae490000b029052f9e5b7d3fso4454476ybe.4 for ; Fri, 11 Jun 2021 08:34:19 -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=AppFbIGceq/7qgWRXZpcEsZGbclnV4KoLQEA1L+OJMY=; b=JUnkTRv6ed96sJMOWaN2VzWZHiN6v6eR0nBn05I293OLSkZL4iMICnqB8QOUG1n8L+ L6ukIXlRncjOhtdSEXipFBIIHKOcU2nzs5DZrE/7VIiDTGNQ4FWFGsc4Ty7cQxVFufxZ BMwnlCnPGzLcMqqy6ORhkWES8V8W+fzpw27yp3octXCuMTNUrAlfSUjsUbz5Gcsj8qgx 7i0vCtYU4nwzYa+GP36rr8FiUSyPETWQASjdquSrkd9a8cQ0q07jJ373xcISKuSX1tu/ DcP659WrDboJf/GAzuBDhro0zSFuXxQIBt1/2wYj/v78+YD5O3w64yzf2HS3m/EyATUl P7gQ== X-Gm-Message-State: AOAM531yzqYb32TpmjyXzpDhplgnyXXr8ZJj901b7oVh0m9pLpxSF+Bq M1fvQoWupLZvTnSkkIzh622vuE8OgTMjkLW7xJNp2weUj1SMf38wZAXSwSHQe0iCzIzJV1A10xs 76P1ZC1rQ+iq1erMWBy72GuJQ/idRl0Iwlqmd1jlcQ99COjtr/r1Vk27aFi0oFy9zVnLg/Vs= X-Google-Smtp-Source: ABdhPJwt6jDP43IZKA5wHBBFWvamZbfsIxqmG/fr3xa+Ng7Mos42s9Xe+tzQi5iJpXqvqSZvHzxJ8/oZ3Lac+w== X-Received: from tef.lon.corp.google.com ([2a00:79e0:d:210:c264:c1f9:cf3c:2c0b]) (user=gprocida job=sendgmr) by 2002:a25:5383:: with SMTP id h125mr6478473ybb.463.1623425659003; Fri, 11 Jun 2021 08:34:19 -0700 (PDT) Date: Fri, 11 Jun 2021 16:33:16 +0100 In-Reply-To: <20210611153319.778996-1-gprocida@google.com> Message-Id: <20210611153319.778996-4-gprocida@google.com> Mime-Version: 1.0 References: <20210611153319.778996-1-gprocida@google.com> X-Mailer: git-send-email 2.32.0.272.g935e593368-goog Subject: [PATCH 3/6] BTF: add SCC finder and test To: libabigail@sourceware.org X-Spam-Status: No, score=-22.8 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, teguiani@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..d60b1aed --- /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 the user must supply a well-behaved + * comparison function (allowing arbitrary data to accompany each node). + * + * 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 ensure that nodes are not revisited once they have been + * assigned to an SCC. The finder does not maintain any state for such nodes. + * + * GUARANTEES + * + * Each node will be 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 visited 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. + * + * Once the examination is done, call Close, passing in the handle and + * optionally a function to update data associated with the node. 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: + explicit SCC(std::function cmp) : cmp_(cmp) + {} + ~SCC() { + assert(open_.empty()); + assert(root_index_.empty()); + } + + std::optional Open(const Node &node) { + for (size_t ix = 0; ix < open_.size(); ++ix) { + const auto &other = open_[ix]; + // node == other? + if (!cmp_(node, other) && !cmp_(other, node)) { + // Pop indices to nodes which cannot be the root of their SCC. + while (root_index_.back() > ix) + root_index_.pop_back(); + return {}; + } + } + // Unvisited, mark node as open and record root index. + auto ix = open_.size(); + open_.push_back(node); + root_index_.push_back(ix); + return ix; + } + + std::vector Close( + size_t ix, std::function update = [](Node &){}) { + std::vector scc; + assert(ix < open_.size()); + update(open_[ix]); + if (ix == root_index_.back()) { + // Close SCC. + root_index_.pop_back(); + std::move(open_.begin() + ix, open_.end(), std::back_inserter(scc)); + open_.resize(ix); + } + return scc; + } + + private: + std::function cmp_; + std::vector open_; + 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..ccabb471 --- /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::less()}; + 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