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.
|
58 | inline 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.
|
68 | inline 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 |
|
78 | inline 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 |
|
98 | namespace souffle {
|
99 |
|
100 | /// select the most precise and steady clock to measure durations
|
101 | using steady_clock = std::conditional<std::chrono::high_resolution_clock::is_steady,
|
102 | std::chrono::high_resolution_clock, std::chrono::steady_clock>::type;
|
103 |
|
104 | static_assert(steady_clock::is_steady, "clock is not monotonically-increasing");
|
105 |
|
106 | // a type def for a time point
|
107 | using time_point = steady_clock::time_point;
|
108 | using microseconds = std::chrono::microseconds;
|
109 |
|
110 | // a shortcut for taking the current time
|
111 | inline time_point now() {
|
112 | return steady_clock::now();
|
113 | }
|
114 |
|
115 | // a shortcut for obtaining the time difference in milliseconds
|
116 | inline 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
|
121 | inline 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
|
126 | inline 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 |
|
134 | namespace 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.
|
137 | template <typename D, typename B>
|
138 | Own<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 |
|
145 | template <typename D, typename B>
|
146 | Own<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 |
|
155 | template <typename A>
|
156 | std::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 |
|
160 | template <typename A>
|
161 | Own<A> clone(const A* node) {
|
162 | return node ? clone(*node) : nullptr;
|
163 | }
|
164 |
|
165 | template <typename A>
|
166 | Own<A> clone(const Own<A>& node) {
|
167 | return clone(node.get());
|
168 | }
|
169 |
|
170 | template <typename K, typename V, typename C>
|
171 | auto 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 |
|
178 | template <typename K, typename V, typename H>
|
179 | auto 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 | */
|
189 | template <typename R>
|
190 | auto 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 | */
|
197 | template <typename D = void, typename R, std::enable_if_t<is_range_v<R>, void*> = nullptr>
|
198 | auto 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 |
|
205 | template <typename A, typename B>
|
206 | auto 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 | */
|
217 | template <typename T>
|
218 | bool 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 | */
|
232 | template <typename T>
|
233 | bool 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 |
|
241 | template <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 |
|
256 | template <typename F>
|
257 | auto 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
|