libutil: add checked arithmetic tools

This is in preparation for adding checked arithmetic to the evaluator.

Change-Id: I6e115ce8f5411feda1706624977a4dcd5efd4d13

5 files changed, 384 insertions, 0 deletions

diff --git a/src/libutil/checked-arithmetic.hh b/src/libutil/checked-arithmetic.hh
new file mode 100644
index 000000000..c0c63feff
--- /dev/null
+++ b/src/libutil/checked-arithmetic.hh
@@ -0,0 +1,170 @@
+#pragma once
+/**
+ * @file Checked arithmetic with classes that make it hard to accidentally make something an unchecked operation.
+ */
+
+#include <compare>
+#include <concepts> // IWYU pragma: keep
+#include <exception>
+#include <ostream>
+#include <limits>
+#include <optional>
+#include <type_traits>
+
+namespace nix::checked {
+
+class DivideByZero : std::exception
+{};
+
+/**
+ * Numeric value enforcing checked arithmetic. Performing mathematical operations on such values will return a Result type which needs to be checked.
+ */
+template<std::integral T>
+struct Checked
+{
+    using Inner = T;
+
+    // TODO: this must be a "trivial default constructor", which means it
+    // cannot set the value to NOT DO UB on uninit.
+    T value;
+
+    Checked() = default;
+    explicit Checked(T const value) : value{value} {}
+    Checked(Checked<T> const & other) = default;
+    Checked(Checked<T> && other) = default;
+    Checked<T> & operator=(Checked<T> const & other) = default;
+
+    std::strong_ordering operator<=>(Checked<T> const & other) const = default;
+    std::strong_ordering operator<=>(T const & other) const
+    {
+        return value <=> other;
+    }
+
+    explicit operator T() const
+    {
+        return value;
+    }
+
+    enum class OverflowKind {
+        NoOverflow,
+        Overflow,
+        DivByZero,
+    };
+
+    class Result
+    {
+        T value;
+        OverflowKind overflowed_;
+
+    public:
+        Result(T value, bool overflowed) : value{value}, overflowed_{overflowed ? OverflowKind::Overflow : OverflowKind::NoOverflow} {}
+        Result(T value, OverflowKind overflowed) : value{value}, overflowed_{overflowed} {}
+
+        bool operator==(Result other) const
+        {
+            return value == other.value && overflowed_ == other.overflowed_;
+        }
+
+        std::optional<T> valueChecked() const
+        {
+            if (overflowed_ != OverflowKind::NoOverflow) {
+                return std::nullopt;
+            } else {
+                return value;
+            }
+        }
+
+        /**
+         * Returns the result as if the arithmetic were performed as wrapping arithmetic.
+         *
+         * \throws DivideByZero if the operation was a divide by zero.
+         */
+        T valueWrapping() const
+        {
+            if (overflowed_ == OverflowKind::DivByZero) {
+                throw DivideByZero{};
+            }
+            return value;
+        }
+
+        bool overflowed() const
+        {
+            return overflowed_ == OverflowKind::Overflow;
+        }
+
+        bool divideByZero() const
+        {
+            return overflowed_ == OverflowKind::DivByZero;
+        }
+    };
+
+    Result operator+(Checked<T> const other) const
+    {
+        return (*this) + other.value;
+    }
+    Result operator+(T const other) const
+    {
+        T result;
+        bool overflowed = __builtin_add_overflow(value, other, &result);
+        return Result{result, overflowed};
+    }
+
+    Result operator-(Checked<T> const other) const
+    {
+        return (*this) - other.value;
+    }
+    Result operator-(T const other) const
+    {
+        T result;
+        bool overflowed = __builtin_sub_overflow(value, other, &result);
+        return Result{result, overflowed};
+    }
+
+    Result operator*(Checked<T> const other) const
+    {
+        return (*this) * other.value;
+    }
+    Result operator*(T const other) const
+    {
+        T result;
+        bool overflowed = __builtin_mul_overflow(value, other, &result);
+        return Result{result, overflowed};
+    }
+
+    Result operator/(Checked<T> const other) const
+    {
+        return (*this) / other.value;
+    }
+    /**
+     * Performs a checked division.
+     *
+     * If the right hand side is zero, the result is marked as a DivByZero and
+     * valueWrapping will throw.
+     */
+    Result operator/(T const other) const
+    {
+        constexpr T const minV = std::numeric_limits<T>::min();
+
+        // It's only possible to overflow with signed division since doing so
+        // requires crossing the two's complement limits by MIN / -1 (since
+        // two's complement has one more in range in the negative direction
+        // than in the positive one).
+        if (std::is_signed<T>() && (value == minV && other == -1)) {
+            return Result{minV, true};
+        } else if (other == 0) {
+            return Result{0, OverflowKind::DivByZero};
+        } else {
+            T result = value / other;
+            return Result{result, false};
+        }
+    }
+};
+
+template<std::integral T>
+std::ostream & operator<<(std::ostream & ios, Checked<T> v)
+{
+    ios << v.value;
+    return ios;
+}
+
+}
diff --git a/src/libutil/meson.build b/src/libutil/meson.build
index 211196c60..c860e7e00 100644
--- a/src/libutil/meson.build
+++ b/src/libutil/meson.build
@@ -52,6 +52,7 @@ libutil_headers = files(
   'box_ptr.hh',
   'canon-path.hh',
   'cgroup.hh',
+  'checked-arithmetic.hh',
   'chunked-vector.hh',
   'closure.hh',
   'comparator.hh',
diff --git a/tests/unit/libutil-support/tests/gtest-with-params.hh b/tests/unit/libutil-support/tests/gtest-with-params.hh
new file mode 100644
index 000000000..323a083fe
--- /dev/null
+++ b/tests/unit/libutil-support/tests/gtest-with-params.hh
@@ -0,0 +1,54 @@
+#pragma once
+// SPDX-FileCopyrightText: 2014 Emil Eriksson
+//
+// SPDX-License-Identifier: BSD-2-Clause
+//
+// The lion's share of this code is copy pasted directly out of RapidCheck
+// headers, so the copyright is set accordingly.
+/**
+ * @file Implements the ability to run a RapidCheck test under gtest with changed
+ * test parameters such as the number of tests to run. This is useful for
+ * running very large numbers of the extremely cheap property tests.
+ */
+
+#include <gtest/gtest.h>
+#include <rapidcheck/gtest.h>
+#include <rapidcheck/gen/Arbitrary.hpp>
+
+namespace rc::detail {
+
+using MakeTestParams = TestParams (*)();
+
+template<typename Testable>
+void checkGTestWith(Testable && testable, MakeTestParams makeTestParams)
+{
+    const auto testInfo = ::testing::UnitTest::GetInstance()->current_test_info();
+    detail::TestMetadata metadata;
+    metadata.id = std::string(testInfo->test_case_name()) + "/" + std::string(testInfo->name());
+    metadata.description = std::string(testInfo->name());
+
+    const auto result = checkTestable(std::forward<Testable>(testable), metadata, makeTestParams());
+
+    if (result.template is<detail::SuccessResult>()) {
+        const auto success = result.template get<detail::SuccessResult>();
+        if (!success.distribution.empty()) {
+            printResultMessage(result, std::cout);
+            std::cout << std::endl;
+        }
+    } else {
+        std::ostringstream ss;
+        printResultMessage(result, ss);
+        FAIL() << ss.str() << std::endl;
+    }
+}
+}
+
+#define RC_GTEST_PROP_WITH_PARAMS(TestCase, Name, MakeParams, ArgList)                      \
+    void rapidCheck_propImpl_##TestCase##_##Name ArgList;                                   \
+                                                                                            \
+    TEST(TestCase, Name)                                                                    \
+    {                                                                                       \
+        ::rc::detail::checkGTestWith(&rapidCheck_propImpl_##TestCase##_##Name, MakeParams); \
+    }                                                                                       \
+                                                                                            \
+    void rapidCheck_propImpl_##TestCase##_##Name ArgList
diff --git a/tests/unit/libutil/checked-arithmetic.cc b/tests/unit/libutil/checked-arithmetic.cc
new file mode 100644
index 000000000..2a9ba6906
--- /dev/null
+++ b/tests/unit/libutil/checked-arithmetic.cc
@@ -0,0 +1,158 @@
+#include <cstdint>
+#include <gtest/gtest.h>
+#include <limits>
+#include <rapidcheck/Assertions.h>
+#include <rapidcheck/gtest.h>
+#include <rapidcheck/gen/Arbitrary.hpp>
+
+#include <checked-arithmetic.hh>
+
+#include "tests/gtest-with-params.hh"
+
+namespace rc {
+using namespace nix;
+
+template<std::integral T>
+struct Arbitrary<nix::checked::Checked<T>>
+{
+    static Gen<nix::checked::Checked<T>> arbitrary()
+    {
+        return gen::arbitrary<T>();
+    }
+};
+
+}
+
+namespace nix::checked {
+
+// Pointer to member function! Mildly gross.
+template <std::integral T>
+using Oper = Checked<T>::Result (Checked<T>::*)(T const other) const;
+
+template<std::integral T>
+using ReferenceOper = T (*)(T a, T b);
+
+/**
+ * Checks that performing an operation that overflows into an inaccurate result
+ * has the desired behaviour.
+ *
+ * TBig is a type large enough to represent all results of TSmall operations.
+ */
+template <std::integral TSmall, std::integral TBig>
+void checkType(TSmall a_, TSmall b, Oper<TSmall> oper, ReferenceOper<TBig> reference)
+{
+    // Sufficient to fit all values
+    TBig referenceResult = reference(a_, b);
+    constexpr const TSmall minV = std::numeric_limits<TSmall>::min();
+    constexpr const TSmall maxV = std::numeric_limits<TSmall>::max();
+
+    Checked<TSmall> a{a_};
+    auto result = (a.*(oper))(b);
+
+    // Just truncate it to get the in-range result
+    RC_ASSERT(result.valueWrapping() == static_cast<TSmall>(referenceResult));
+
+    if (referenceResult > maxV || referenceResult < minV) {
+        RC_ASSERT(result.overflowed());
+        RC_ASSERT(!result.valueChecked().has_value());
+    } else {
+        RC_ASSERT(!result.overflowed());
+        RC_ASSERT(result.valueChecked().has_value());
+        RC_ASSERT(*result.valueChecked() == referenceResult);
+    }
+}
+
+/**
+ * Checks that performing an operation that overflows into an inaccurate result
+ * has the desired behaviour.
+ *
+ * TBig is a type large enough to represent all results of TSmall operations.
+ */
+template <std::integral TSmall, std::integral TBig>
+void checkDivision(TSmall a_, TSmall b)
+{
+    // Sufficient to fit all values
+    constexpr const TSmall minV = std::numeric_limits<TSmall>::min();
+
+    Checked<TSmall> a{a_};
+    auto result = a / b;
+
+    if (std::is_signed<TSmall>() && a_ == minV && b == -1) {
+        // This is the only possible overflow condition
+        RC_ASSERT(result.valueWrapping() == minV);
+        RC_ASSERT(result.overflowed());
+    } else if (b == 0) {
+        RC_ASSERT(result.divideByZero());
+        RC_ASSERT_THROWS_AS(result.valueWrapping(), nix::checked::DivideByZero);
+        RC_ASSERT(result.valueChecked() == std::nullopt);
+    } else {
+        TBig referenceResult = a_ / b;
+        auto result_ = result.valueChecked();
+        RC_ASSERT(result_.has_value());
+        RC_ASSERT(*result_ == referenceResult);
+        RC_ASSERT(result.valueWrapping() == referenceResult);
+    }
+}
+
+/** Creates parameters that perform a more adequate number of checks to validate
+ * extremely cheap tests such as arithmetic tests */
+static rc::detail::TestParams makeParams() {
+    auto const & conf = rc::detail::configuration();
+    auto newParams = conf.testParams;
+    newParams.maxSuccess = 10000;
+    return newParams;
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, add_unsigned, makeParams, (uint16_t a, uint16_t b))
+{
+    checkType<uint16_t, int32_t>(a, b, &Checked<uint16_t>::operator+, [](int32_t a, int32_t b) { return a + b; });
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, add_signed, makeParams, (int16_t a, int16_t b))
+{
+    checkType<int16_t, int32_t>(a, b, &Checked<int16_t>::operator+, [](int32_t a, int32_t b) { return a + b; });
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, sub_unsigned, makeParams, (uint16_t a, uint16_t b))
+{
+    checkType<uint16_t, int32_t>(a, b, &Checked<uint16_t>::operator-, [](int32_t a, int32_t b) { return a - b; });
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, sub_signed, makeParams, (int16_t a, int16_t b))
+{
+    checkType<int16_t, int32_t>(a, b, &Checked<int16_t>::operator-, [](int32_t a, int32_t b) { return a - b; });
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, mul_unsigned, makeParams, (uint16_t a, uint16_t b))
+{
+    checkType<uint16_t, int64_t>(a, b, &Checked<uint16_t>::operator*, [](int64_t a, int64_t b) { return a * b; });
+}
+
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, mul_signed, makeParams, (int16_t a, int16_t b))
+{
+    checkType<int16_t, int64_t>(a, b, &Checked<int16_t>::operator*, [](int64_t a, int64_t b) { return a * b; });
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, div_unsigned, makeParams, (uint16_t a, uint16_t b))
+{
+    checkDivision<uint16_t, int64_t>(a, b);
+}
+
+RC_GTEST_PROP_WITH_PARAMS(Checked, div_signed, makeParams, (int16_t a, int16_t b))
+{
+    checkDivision<int16_t, int64_t>(a, b);
+}
+
+// Make absolutely sure that we check the special cases if the proptest
+// generator does not come up with them. This one is especially important
+// because it has very specific pairs required for the edge cases unlike the
+// others.
+TEST(Checked, div_signed_special_cases)
+{
+    checkDivision<int16_t, int64_t>(std::numeric_limits<int16_t>::min(), -1);
+    checkDivision<int16_t, int64_t>(std::numeric_limits<int16_t>::min(), 0);
+    checkDivision<int16_t, int64_t>(0, 0);
+}
+
+}
diff --git a/tests/unit/meson.build b/tests/unit/meson.build
index a6719a060..c449b2276 100644
--- a/tests/unit/meson.build
+++ b/tests/unit/meson.build
@@ -35,6 +35,7 @@ liblixutil_test_support = declare_dependency(
 
 libutil_tests_sources = files(
   'libutil/canon-path.cc',
+  'libutil/checked-arithmetic.cc',
   'libutil/chunked-vector.cc',
   'libutil/closure.cc',
   'libutil/compression.cc',