OILS / vendor / souffle / utility / MiscUtil.h View on Github | oilshell.org

265 lines, 133 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2021, The Souffle Developers. All rights reserved
4 * Licensed under the Universal Permissive License v 1.0 as shown at:
5 * - https://opensource.org/licenses/UPL
6 * - <souffle root>/licenses/SOUFFLE-UPL.txt
7 */
8
9/************************************************************************
10 *
11 * @file MiscUtil.h
12 *
13 * @brief Datalog project utilities
14 *
15 ***********************************************************************/
16
17#pragma once
18
19#include "souffle/utility/General.h"
20#include "souffle/utility/Iteration.h"
21#include "souffle/utility/Types.h"
22#include "tinyformat.h"
23#include <cassert>
24#include <chrono>
25#include <iostream>
26#include <map>
27#include <memory>
28#include <optional>
29#include <type_traits>
30#include <unordered_map>
31#include <utility>
32
33#ifdef _WIN32
34#define NOMINMAX
35#define NOGDI
36#include <fcntl.h>
37#include <io.h>
38#include <stdlib.h>
39#include <windows.h>
40
41/**
42 * On windows, the following gcc builtins are missing.
43 *
44 * In the case of popcountll, __popcnt64 is the windows equivalent.
45 *
46 * For ctz and ctzll, BitScanForward and BitScanForward64 are the respective
47 * windows equivalents. However ctz is used in a constexpr context, and we can't
48 * use BitScanForward, so we implement it ourselves.
49 */
50#if _WIN64
51#define __builtin_popcountll __popcnt64
52#else
53#define __builtin_popcountll __popcnt
54#endif
55
56#if defined(_MSC_VER)
57// return the number of trailing zeroes in value, or 32 if value is zero.
58inline constexpr unsigned long __builtin_ctz(unsigned long value) {
59 unsigned long trailing_zeroes = 0;
60 if (value == 0) return 32;
61 while ((value = value >> 1) ^ 1) {
62 ++trailing_zeroes;
63 }
64 return trailing_zeroes;
65}
66
67// return the number of trailing zeroes in value, or 64 if value is zero.
68inline constexpr int __builtin_ctzll_constexpr(unsigned long long value) {
69 int trailing_zeroes = 0;
70
71 if (value == 0) return 64;
72 while ((value = value >> 1) ^ 1) {
73 ++trailing_zeroes;
74 }
75 return trailing_zeroes;
76}
77
78inline int __builtin_ctzll(unsigned long long value) {
79 unsigned long trailing_zeroes = 0;
80
81#if _WIN64
82 if (_BitScanForward64(&trailing_zeroes, value)) {
83#else
84 if (_BitScanForward(&trailing_zeroes, value)) {
85#endif
86 return static_cast<int>(trailing_zeroes);
87 } else {
88 return 64; // return 64 like GCC would when value == 0
89 }
90}
91#endif // _MSC_VER
92#endif // _WIN32
93
94// -------------------------------------------------------------------------------
95// Timing Utils
96// -------------------------------------------------------------------------------
97
98namespace souffle {
99
100/// select the most precise and steady clock to measure durations
101using steady_clock = std::conditional<std::chrono::high_resolution_clock::is_steady,
102 std::chrono::high_resolution_clock, std::chrono::steady_clock>::type;
103
104static_assert(steady_clock::is_steady, "clock is not monotonically-increasing");
105
106// a type def for a time point
107using time_point = steady_clock::time_point;
108using microseconds = std::chrono::microseconds;
109
110// a shortcut for taking the current time
111inline time_point now() {
112 return steady_clock::now();
113}
114
115// a shortcut for obtaining the time difference in milliseconds
116inline int64_t duration_in_ms(const time_point& start, const time_point& end) {
117 return static_cast<int64_t>(std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count());
118}
119
120// a shortcut for obtaining the time difference in microseconds
121inline int64_t duration_in_us(const time_point& start, const time_point& end) {
122 return static_cast<int64_t>(std::chrono::duration_cast<std::chrono::microseconds>(end - start).count());
123}
124
125// a shortcut for obtaining the time difference in nanoseconds
126inline int64_t duration_in_ns(const time_point& start, const time_point& end) {
127 return static_cast<int64_t>(std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count());
128}
129
130// -------------------------------------------------------------------------------
131// Cloning Utilities
132// -------------------------------------------------------------------------------
133
134namespace detail {
135// TODO: This function is still used by ram::Node::clone() because it hasn't been
136// converted to return Own<>. Once converted, remove this.
137template <typename D, typename B>
138Own<D> downCast(B* ptr) {
139 // ensure the clone operation casts to appropriate pointer
140 static_assert(std::is_base_of_v<std::remove_const_t<B>, std::remove_const_t<D>>,
141 "Needs to be able to downcast");
142 return Own<D>(ptr);
143}
144
145template <typename D, typename B>
146Own<D> downCast(Own<B> ptr) {
147 // ensure the clone operation casts to appropriate pointer
148 static_assert(std::is_base_of_v<std::remove_const_t<B>, std::remove_const_t<D>>,
149 "Needs to be able to downcast");
150 return Own<D>(static_cast<D*>(ptr.release()));
151}
152
153} // namespace detail
154
155template <typename A>
156std::enable_if_t<!std::is_pointer_v<A> && !is_range_v<A>, Own<A>> clone(const A& node) {
157 return detail::downCast<A>(node.cloneImpl());
158}
159
160template <typename A>
161Own<A> clone(const A* node) {
162 return node ? clone(*node) : nullptr;
163}
164
165template <typename A>
166Own<A> clone(const Own<A>& node) {
167 return clone(node.get());
168}
169
170template <typename K, typename V, typename C>
171auto clone(const std::map<K, V, C>& xs) {
172 std::map<K, decltype(clone(std::declval<const V&>())), C> ys;
173 for (auto&& [k, v] : xs)
174 ys.insert({k, clone(v)});
175 return ys;
176}
177
178template <typename K, typename V, typename H>
179auto clone(const std::unordered_map<K, V, H>& xs) {
180 std::unordered_map<K, decltype(clone(std::declval<const V&>())), H> ys;
181 for (auto&& [k, v] : xs)
182 ys.insert({k, clone(v)});
183 return ys;
184}
185
186/**
187 * Clone a range
188 */
189template <typename R>
190auto cloneRange(R const& range) {
191 return makeTransformRange(std::begin(range), std::end(range), [](auto const& x) { return clone(x); });
192}
193
194/**
195 * Clone a range, optionally allowing up-casting the result to D
196 */
197template <typename D = void, typename R, std::enable_if_t<is_range_v<R>, void*> = nullptr>
198auto clone(R const& range) {
199 auto rn = cloneRange(range);
200 using ValueType = remove_cvref_t<decltype(**std::begin(range))>;
201 using ResType = std::conditional_t<std::is_same_v<D, void>, ValueType, D>;
202 return VecOwn<ResType>(rn.begin(), rn.end());
203}
204
205template <typename A, typename B>
206auto clone(const std::pair<A, B>& p) {
207 return std::make_pair(clone(p.first), clone(p.second));
208}
209
210// -------------------------------------------------------------------------------
211// Comparison Utilities
212// -------------------------------------------------------------------------------
213/**
214 * Compares two values referenced by a pointer where the case where both
215 * pointers are null is also considered equivalent.
216 */
217template <typename T>
218bool equal_ptr(const T* a, const T* b) {
219 if (a == nullptr && b == nullptr) {
220 return true;
221 }
222 if (a != nullptr && b != nullptr) {
223 return *a == *b;
224 }
225 return false;
226}
227
228/**
229 * Compares two values referenced by a pointer where the case where both
230 * pointers are null is also considered equivalent.
231 */
232template <typename T>
233bool equal_ptr(const Own<T>& a, const Own<T>& b) {
234 return equal_ptr(a.get(), b.get());
235}
236
237// -------------------------------------------------------------------------------
238// Error Utilities
239// -------------------------------------------------------------------------------
240
241template <typename... Args>
242[[noreturn]] void fatal(const char* format, const Args&... args) {
243 tfm::format(std::cerr, format, args...);
244 std::cerr << "\n";
245 assert(false && "fatal error; see std err");
246 abort();
247}
248
249// HACK: Workaround to suppress spurious reachability warnings.
250#define UNREACHABLE_BAD_CASE_ANALYSIS fatal("unhandled switch branch");
251
252// -------------------------------------------------------------------------------
253// Other Utilities
254// -------------------------------------------------------------------------------
255
256template <typename F>
257auto lazy(F f) {
258 using A = decltype(f());
259 return [cache = std::optional<A>{}, f = std::move(f)]() mutable -> A& {
260 if (!cache) cache = f();
261 return *cache;
262 };
263}
264
265} // namespace souffle