test(3p/nix): Add property tests for attribute set r/1395

Add a set of property tests for the attribute set (Bindings) class
checking that the Merge operation satisfies the monoid laws. This
will hopefully become useful to make sure we're not breaking the
language semantics as we work towards optimizing or replacing the
implementation, but also serves as a test bed for adding
rapidcheck-based property tests to the codebase.

Change-Id: I1b4b7b6503d08d80c1c5a8f9408fd4b787d00e8e
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1283
Reviewed-by: isomer <isomer@tvl.fyi>
Tested-by: BuildkiteCI

4 files changed, 175 insertions, 1 deletions

diff --git a/third_party/nix/CMakeLists.txt b/third_party/nix/CMakeLists.txt
index f796ccdee4d6..71651a9b1168 100644
--- a/third_party/nix/CMakeLists.txt
+++ b/third_party/nix/CMakeLists.txt
@@ -43,6 +43,7 @@ option(PACKAGE_TESTS "Build the tests" ON)
 if (PACKAGE_TESTS)
   enable_testing()
   find_package(GTest)
+  find_package(rapidcheck)
   include(GoogleTest)
 endif()
 
diff --git a/third_party/nix/default.nix b/third_party/nix/default.nix
index c4a30501697f..54e77ec50d11 100644
--- a/third_party/nix/default.nix
+++ b/third_party/nix/default.nix
@@ -55,7 +55,6 @@ in pkgs.llvmPackages.libcxxStdenv.mkDerivation {
     flex
     glog
     grpc
-    gtest
     libseccomp
     libsodium
     openssl
@@ -67,6 +66,11 @@ in pkgs.llvmPackages.libcxxStdenv.mkDerivation {
   doCheck = false;
   doInstallCheck = true;
 
+  installCheckInputs = with pkgs; [
+    gtest
+    rapidcheck
+  ];
+
   propagatedBuildInputs = with pkgs; [
     boost
     largeBoehm
diff --git a/third_party/nix/src/tests/CMakeLists.txt b/third_party/nix/src/tests/CMakeLists.txt
index 81ccf95b7840..b21b194630c1 100644
--- a/third_party/nix/src/tests/CMakeLists.txt
+++ b/third_party/nix/src/tests/CMakeLists.txt
@@ -1,6 +1,16 @@
 # -*- mode: cmake; -*-
 include_directories(${PROJECT_BINARY_DIR}) # for 'generated/'
 
+add_executable(attr-set attr-set.cc)
+target_link_libraries(attr-set
+  nixexpr
+  rapidcheck
+  rapidcheck_gtest
+  GTest::gtest_main
+)
+
+gtest_discover_tests(attr-set)
+
 add_executable(value-to-json value-to-json.cc)
 target_link_libraries(value-to-json
   nixexpr
diff --git a/third_party/nix/src/tests/attr-set.cc b/third_party/nix/src/tests/attr-set.cc
new file mode 100644
index 000000000000..e8ad86664b9d
--- /dev/null
+++ b/third_party/nix/src/tests/attr-set.cc
@@ -0,0 +1,159 @@
+#include "libexpr/attr-set.hh"
+
+#include <cstdio>
+#include <optional>
+#include <string>
+#include <vector>
+
+#include <bits/stdint-intn.h>
+#include <gc/gc_cpp.h>
+#include <gtest/gtest.h>
+#include <rapidcheck.h>
+#include <rapidcheck/Assertions.h>
+#include <rapidcheck/gen/Arbitrary.h>
+#include <rapidcheck/gen/Build.h>
+#include <rapidcheck/gen/Create.h>
+#include <rapidcheck/gen/Transform.h>
+#include <rapidcheck/gtest.h>
+
+#include "libexpr/eval.hh"
+#include "libexpr/nixexpr.hh"
+#include "libexpr/symbol-table.hh"
+#include "libexpr/value.hh"
+#include "tests/dummy-store.hh"
+
+static nix::SymbolTable* symbol_table;
+
+namespace rc {
+using nix::Pos;
+using nix::Value;
+
+// TODO(grfn): These arbitrary implementations should be pulled out to a util
+// file sooner rather than later
+
+template <>
+struct Arbitrary<nix::Symbol> {
+  static Gen<nix::Symbol> arbitrary() {
+    return gen::map(gen::arbitrary<std::string>(),
+                    [](std::string s) { return symbol_table->Create(s); });
+  }
+};
+
+template <>
+struct Arbitrary<Value> {
+  static Gen<nix::Value> arbitrary() {
+    return gen::build(gen::construct<Value>(),
+                      // TODO(grfn) generalize to more types
+                      gen::set(&Value::type, gen::just(nix::ValueType::tInt)),
+                      gen::set(&Value::integer, gen::arbitrary<int64_t>()));
+  }
+};
+
+template <>
+struct Arbitrary<Value*> {
+  static Gen<nix::Value*> arbitrary() {
+    return gen::apply(
+        [](nix::ValueType typ, int i) {
+          auto ret = new (GC) Value();
+          ret->type = typ;
+          ret->integer = i;
+          return ret;
+        },
+        gen::just(nix::ValueType::tInt), gen::arbitrary<int64_t>());
+  }
+};
+
+template <>
+struct Arbitrary<nix::Pos> {
+  static Gen<nix::Pos> arbitrary() {
+    return gen::construct<nix::Pos>(gen::arbitrary<nix::Symbol>(),
+                                    gen::arbitrary<unsigned int>(),
+                                    gen::arbitrary<unsigned int>());
+  }
+};
+
+template <>
+struct Arbitrary<nix::Pos*> {
+  static Gen<nix::Pos*> arbitrary() {
+    return gen::apply(
+        [](unsigned int line, unsigned int column) {
+          return new (GC) Pos({}, line, column);
+        },
+        gen::arbitrary<unsigned int>(), gen::arbitrary<unsigned int>());
+  }
+};
+
+template <>
+struct Arbitrary<nix::Attr> {
+  static Gen<nix::Attr> arbitrary() {
+    return gen::construct<nix::Attr>(gen::arbitrary<nix::Symbol>(),
+                                     gen::arbitrary<Value*>(),
+                                     gen::arbitrary<nix::Pos*>());
+  }
+};
+
+template <>
+struct Arbitrary<nix::Bindings> {
+  static Gen<nix::Bindings> arbitrary() {
+    return gen::map(gen::arbitrary<std::vector<nix::Attr>>(), [](auto attrs) {
+      nix::Bindings res;
+      for (const auto& attr : attrs) {
+        res.push_back(attr);
+      }
+      return res;
+    });
+  }
+};
+
+}  // namespace rc
+
+namespace nix {
+
+using nix::tests::DummyStore;
+
+class AttrSetTest : public ::testing::Test {
+ protected:
+  EvalState* eval_state_;
+  void SetUp() override {
+    nix::initGC();
+    auto store = std::make_shared<DummyStore>();
+    eval_state_ = new EvalState({"."}, ref<Store>(store));
+    symbol_table = &eval_state_->symbols;
+  }
+
+  void assert_bindings_equal(nix::Bindings& lhs, nix::Bindings& rhs) {
+    Value lhs_val;
+    Value rhs_val;
+    lhs_val.type = rhs_val.type = ValueType::tAttrs;
+    lhs_val.attrs = &lhs;
+    rhs_val.attrs = &lhs;
+
+    RC_ASSERT(eval_state_->eqValues(lhs_val, rhs_val));
+  }
+};
+
+class AttrSetMonoidTest : public AttrSetTest {};
+
+RC_GTEST_FIXTURE_PROP(AttrSetMonoidTest, mergeLeftIdentity,
+                      (nix::Bindings && bindings)) {
+  auto empty_bindings = nix::Bindings::NewGC();
+  auto result = *Bindings::Merge(*empty_bindings, bindings);
+  assert_bindings_equal(result, bindings);
+}
+
+RC_GTEST_FIXTURE_PROP(AttrSetMonoidTest, mergeRightIdentity,
+                      (nix::Bindings && bindings)) {
+  auto empty_bindings = nix::Bindings::NewGC();
+  auto result = *Bindings::Merge(bindings, *empty_bindings);
+  assert_bindings_equal(result, bindings);
+}
+
+RC_GTEST_FIXTURE_PROP(AttrSetMonoidTest, mergeAssociative,
+                      (nix::Bindings && bindings_1, nix::Bindings&& bindings_2,
+                       nix::Bindings&& bindings_3)) {
+  assert_bindings_equal(
+      *Bindings::Merge(bindings_1, *Bindings::Merge(bindings_2, bindings_3)),
+      *Bindings::Merge(*Bindings::Merge(bindings_1, bindings_2), bindings_3));
+}
+
+}  // namespace nix