external/stg/order_test.cc

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// -*- mode: C++ -*-
//
// Copyright 2021-2024 Google LLC
//
// Licensed under the Apache License v2.0 with LLVM Exceptions (the
// "License"); you may not use this file except in compliance with the
// License.  You may obtain a copy of the License at
//
//     https://llvm.org/LICENSE.txt
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Author: Giuliano Procida

#include "order.h"

#include <cstddef>
#include <optional>
#include <random>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#include <catch2/catch.hpp>

namespace Test {

// Safe for small k!
size_t Factorial(size_t k) {
  size_t count = 1;
  for (size_t i = 1; i <= k; ++i) {
    count *= i;
  }
  return count;
}

TEST_CASE("hand-curated permutation") {
  std::vector<std::string> data = {"emily", "george", "rose", "ted"};
  std::vector<size_t> permutation = {2, 1, 3, 0};
  const std::vector<std::string> expected = {"rose", "george", "ted", "emily"};
  const std::vector<size_t> identity = {0, 1, 2, 3};
  stg::Permute(data, permutation);
  CHECK(data == expected);
  CHECK(permutation == identity);
}

template <typename G>
std::vector<size_t> MakePermutation(size_t k, G& gen) {
  std::vector<size_t> result(k);
  for (size_t i = 0; i < k; ++i) {
    result[i] = i;
  }
  for (size_t i = 0; i < k; ++i) {
    // pick one of [i, k)
    std::uniform_int_distribution<size_t> toss(i, k - 1);
    const auto pick = toss(gen);
    using std::swap;
    swap(result[i], result[pick]);
  }
  return result;
}

TEST_CASE("randomly-generated permutations") {
  std::ranlux48 gen;
  auto seed = gen();
  // NOTES:
  //   Permutations of size 6 are plenty big enough to shake out bugs.
  ///  There are k! permutations of size k. Testing costs are O(k).
  for (size_t k = 0; k < 7; ++k) {
    const auto count = Factorial(k);
    INFO("testing with " << count << " permutations of size " << k);
    std::vector<size_t> identity(k);
    for (size_t i = 0; i < k; ++i) {
      identity[i] = i;
    }
    for (size_t n = 0; n < count; ++n, ++seed) {
      gen.seed(seed);
      auto permutation = MakePermutation(k, gen);
      std::ostringstream os;
      os << "permutation of " << k << " numbers generated using seed " << seed;
      GIVEN(os.str()) {
        // NOTE: We could test with something other than [0, k) as the data, but
        // let's just say "parametric polymorphism" and move on.
        auto permutation_copy = permutation;
        auto identity_copy = identity;
        stg::Permute(identity_copy, permutation_copy);
        for (size_t i = 0; i < k; ++i) {
          // permutation_copy should be the identity
          CHECK(permutation_copy[i] == i);
          // identity_copy should now be the same as permutation
          CHECK(identity_copy[i] == permutation[i]);
        }
      }
    }
  }
}

TEST_CASE("randomly-generating ordering sequences, fully-matching") {
  std::ranlux48 gen;
  auto seed = gen();
  // NOTES:
  //   Permutations of size 6 are plenty big enough to shake out bugs.
  ///  There are k! permutations of size k. Testing costs are O(k^2).
  for (size_t k = 0; k < 7; ++k) {
    const auto count = Factorial(k);
    INFO("testing with " << count << " random orderings of size " << k);
    for (size_t n = 0; n < count; ++n, ++seed) {
      gen.seed(seed);
      const auto order1 = MakePermutation(k, gen);
      const auto order2 = MakePermutation(k, gen);
      std::ostringstream os;
      os << "orderings of " << k << " numbers generated using seed " << seed;
      GIVEN(os.str()) {
        const auto combined = stg::CombineOrders(order1, order2, k);
        // combined should be identical to order2
        CHECK(combined == order2);
      }
    }
  }
}

TEST_CASE("randomly-generating ordering sequences, disjoint") {
  std::ranlux48 gen;
  auto seed = gen();
  // NOTES:
  //   Orderings of size 4 are plenty big enough to shake out bugs.
  ///  There are k! permutations of size k. Testing costs are O(k^2).
  for (size_t k = 0; k < 5; ++k) {
    const auto count = Factorial(k);
    INFO("testing with " << count << " random orderings of size " << k);
    for (size_t n = 0; n < count; ++n, ++seed) {
      gen.seed(seed);
      const auto order1 = MakePermutation(k, gen);
      auto order2 = MakePermutation(k, gen);
      for (size_t i = 0; i < k; ++i) {
        order2[i] += k;
      }
      std::ostringstream os;
      os << "orderings of " << k << " numbers generated using seed " << seed;
      GIVEN(os.str()) {
        const auto combined = stg::CombineOrders(order1, order2, 2 * k);
        for (size_t i = 0; i < k; ++i) {
          // order1 should appear as the first part
          CHECK(combined[i] == order1[i]);
          // order2 should appear as the second part
          CHECK(combined[i + k] == order2[i]);
        }
      }
    }
  }
}

TEST_CASE("randomly-generating ordering sequences, single overlap") {
  std::ranlux48 gen;
  auto seed = gen();
  // NOTES:
  //   Orderings of size 4 are plenty big enough to shake out bugs.
  ///  There are k! permutations of size k. Testing costs are O(k^2).
  for (size_t k = 1; k < 5; ++k) {
    const auto count = Factorial(k);
    INFO("testing with " << count << " random orderings of size " << k);
    for (size_t n = 0; n < count; ++n, ++seed) {
      gen.seed(seed);
      const auto order1 = MakePermutation(k, gen);
      auto order2 = MakePermutation(k, gen);
      for (size_t i = 0; i < k; ++i) {
        order2[i] += k - 1;
      }
      const auto pivot = k - 1;
      std::ostringstream os;
      os << "orderings of " << k << " numbers generated using seed " << seed;
      GIVEN(os.str()) {
        const auto combined = stg::CombineOrders(order1, order2, 2 * k - 1);
        CHECK(combined.size() == 2 * k - 1);
        // order1 pre, order2 pre, pivot, order1 post, order2 post
        size_t ix = 0;
        size_t ix1 = 0;
        size_t ix2 = 0;
        while (order1[ix1] != pivot) {
          CHECK(combined[ix++] == order1[ix1++]);
        }
        while (order2[ix2] != pivot) {
          CHECK(combined[ix++] == order2[ix2++]);
        }
        ++ix1;
        ++ix2;
        CHECK(combined[ix++] == pivot);
        while (ix1 < k) {
          CHECK(combined[ix++] == order1[ix1++]);
        }
        while (ix2 < k) {
          CHECK(combined[ix++] == order2[ix2++]);
        }
      }
    }
  }
}

TEST_CASE("hand-curated ordering sequences") {
  using Sequence = std::vector<std::string>;
  // NOTES:
  //   The output sequence MUST include the second sequence as a subsequence.
  //   The first sequence's ordering is respected as far as possible.
  const std::vector<std::tuple<Sequence, Sequence, Sequence>> cases = {
    {{"rose", "george", "emily"}, {"george", "ted", "emily"},
      {"rose", "george", "ted", "emily"}},
    {{}, {}, {}},
    {{"a"}, {}, {"a"}},
    {{}, {"a"}, {"a"}},
    {{"a", "z"}, {}, {"a", "z"}},
    {{}, {"a", "z"}, {"a", "z"}},
    {{"a", "b", "c"}, {"c", "d"}, {"a", "b", "c", "d"}},
    {{"a", "b", "d"}, {"b", "c", "d"}, {"a", "b", "c", "d"}},
    {{"a", "c", "d"}, {"a", "b", "c"}, {"a", "b", "c", "d"}},
    {{"b", "c", "d"}, {"a", "b"}, {"a", "b", "c", "d"}},
    {{"z", "a", "q"}, {"a", "z"}, {"a", "z", "q"}},
  };
  for (const auto& [order1, order2, expected] : cases) {
    const auto combined = stg::CombineOrders(order1, order2, expected.size());
    CHECK(combined == expected);
  }
}

TEST_CASE("hand-curated reorderings with input order randomisation") {
  using Constraint = std::pair<std::optional<size_t>, std::optional<size_t>>;
  using Constraints = std::vector<Constraint>;
  // NOTES:
  //   item removed at position x: {x}, {}
  //   item added at position y: {}, {y}
  //   item modified at positions x and y: {x}, {y}
  //   input item order should be irrelevant to output order
  const std::vector<std::pair<Constraints, Constraints>> cases = {
    {
      {
        {{2}, {2}},  // emily
        {{1}, {0}},  // george
        {{0}, {}},   // rose
        {{}, {1}},   // ted
      },
      {
        {{0}, {}},   // rose
        {{1}, {0}},  // george
        {{}, {1}},   // ted
        {{2}, {2}},  // emily
      },
    },
    {{}, {}},
    {{{{0}, {0}}}, {{{0}, {0}}}},
    {{{{0}, {}}}, {{{0}, {}}}},
    {{{{}, {0}}}, {{{}, {0}}}},
    {{{{}, {2}}, {{}, {1}}, {{}, {0}}},
     {{{}, {0}}, {{}, {1}}, {{}, {2}}}},
    {{{{2}, {}}, {{1}, {}}, {{0}, {}}},
     {{{0}, {}}, {{1}, {}}, {{2}, {}}}},
    // int b; int c; -> int b; int a; int c
    {{{{}, {1}}, {{0}, {0}}, {{1}, {2}}},
     {{{0}, {0}}, {{}, {1}}, {{1}, {2}}}},
  };
  std::ranlux48 gen;
  auto seed = gen();
  for (const auto& [given, expected] : cases) {
    const auto k = given.size();
    const auto count = Factorial(k);
    INFO("testing with " << count << " random input orderings");
    for (size_t n = 0; n < count; ++n, ++seed) {
      gen.seed(seed);
      std::ostringstream os;
      os << "permutation of " << k << " items generated using seed " << seed;
      GIVEN(os.str()) {
        auto permutation = MakePermutation(k, gen);
        auto copy = given;
        stg::Permute(copy, permutation);
        stg::Reorder(copy);
        CHECK(copy == expected);
      }
    }
  }
}

}  // namespace Test