//===- AffineStructuresTest.cpp - Tests for AffineStructures ----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "mlir/Analysis/AffineStructures.h"
#include "./AffineStructuresParser.h"
#include "mlir/IR/IntegerSet.h"
#include "mlir/IR/MLIRContext.h"

#include <gmock/gmock.h>
#include <gtest/gtest.h>

#include <numeric>

namespace mlir {

using testing::ElementsAre;

enum class TestFunction { Sample, Empty };

/// If fn is TestFunction::Sample (default):
/// If hasSample is true, check that findIntegerSample returns a valid sample
/// for the FlatAffineConstraints fac.
/// If hasSample is false, check that findIntegerSample returns None.
///
/// If fn is TestFunction::Empty, check that isIntegerEmpty returns the
/// opposite of hasSample.
static void checkSample(bool hasSample, const FlatAffineConstraints &fac,
                        TestFunction fn = TestFunction::Sample) {
  Optional<SmallVector<int64_t, 8>> maybeSample;
  switch (fn) {
  case TestFunction::Sample:
    maybeSample = fac.findIntegerSample();
    if (!hasSample) {
      EXPECT_FALSE(maybeSample.hasValue());
      if (maybeSample.hasValue()) {
        for (auto x : *maybeSample)
          llvm::errs() << x << ' ';
        llvm::errs() << '\n';
      }
    } else {
      ASSERT_TRUE(maybeSample.hasValue());
      EXPECT_TRUE(fac.containsPoint(*maybeSample));
    }
    break;
  case TestFunction::Empty:
    EXPECT_EQ(!hasSample, fac.isIntegerEmpty());
    break;
  }
}

/// Construct a FlatAffineConstraints from a set of inequality and
/// equality constraints.
static FlatAffineConstraints
makeFACFromConstraints(unsigned ids, ArrayRef<SmallVector<int64_t, 4>> ineqs,
                       ArrayRef<SmallVector<int64_t, 4>> eqs,
                       unsigned syms = 0) {
  FlatAffineConstraints fac(ineqs.size(), eqs.size(), ids + 1, ids - syms, syms,
                            /*numLocals=*/0);
  for (const auto &eq : eqs)
    fac.addEquality(eq);
  for (const auto &ineq : ineqs)
    fac.addInequality(ineq);
  return fac;
}

/// Check sampling for all the permutations of the dimensions for the given
/// constraint set. Since the GBR algorithm progresses dimension-wise, different
/// orderings may cause the algorithm to proceed differently. At least some of
///.these permutations should make it past the heuristics and test the
/// implementation of the GBR algorithm itself.
/// Use TestFunction fn to test.
static void checkPermutationsSample(bool hasSample, unsigned nDim,
                                    ArrayRef<SmallVector<int64_t, 4>> ineqs,
                                    ArrayRef<SmallVector<int64_t, 4>> eqs,
                                    TestFunction fn = TestFunction::Sample) {
  SmallVector<unsigned, 4> perm(nDim);
  std::iota(perm.begin(), perm.end(), 0);
  auto permute = [&perm](ArrayRef<int64_t> coeffs) {
    SmallVector<int64_t, 4> permuted;
    for (unsigned id : perm)
      permuted.push_back(coeffs[id]);
    permuted.push_back(coeffs.back());
    return permuted;
  };
  do {
    SmallVector<SmallVector<int64_t, 4>, 4> permutedIneqs, permutedEqs;
    for (const auto &ineq : ineqs)
      permutedIneqs.push_back(permute(ineq));
    for (const auto &eq : eqs)
      permutedEqs.push_back(permute(eq));

    checkSample(hasSample,
                makeFACFromConstraints(nDim, permutedIneqs, permutedEqs), fn);
  } while (std::next_permutation(perm.begin(), perm.end()));
}

/// Parses a FlatAffineConstraints from a StringRef. It is expected that the
/// string represents a valid IntegerSet, otherwise it will violate a gtest
/// assertion.
static FlatAffineConstraints parseFAC(StringRef str, MLIRContext *context) {
  FailureOr<FlatAffineConstraints> fac = parseIntegerSetToFAC(str, context);

  EXPECT_TRUE(succeeded(fac));

  return *fac;
}

TEST(FlatAffineConstraintsTest, FindSampleTest) {
  // Bounded sets with only inequalities.

  MLIRContext context;

  // 0 <= 7x <= 5
  checkSample(true, parseFAC("(x) : (7 * x >= 0, -7 * x + 5 >= 0)", &context));

  // 1 <= 5x and 5x <= 4 (no solution).
  checkSample(false, makeFACFromConstraints(1, {{5, -1}, {-5, 4}}, {}));

  // 1 <= 5x and 5x <= 9 (solution: x = 1).
  checkSample(true, makeFACFromConstraints(1, {{5, -1}, {-5, 9}}, {}));

  // Bounded sets with equalities.
  // x >= 8 and 40 >= y and x = y.
  checkSample(
      true, makeFACFromConstraints(2, {{1, 0, -8}, {0, -1, 40}}, {{1, -1, 0}}));

  // x <= 10 and y <= 10 and 10 <= z and x + 2y = 3z.
  // solution: x = y = z = 10.
  checkSample(true, makeFACFromConstraints(
                        3, {{-1, 0, 0, 10}, {0, -1, 0, 10}, {0, 0, 1, -10}},
                        {{1, 2, -3, 0}}));

  // x <= 10 and y <= 10 and 11 <= z and x + 2y = 3z.
  // This implies x + 2y >= 33 and x + 2y <= 30, which has no solution.
  checkSample(false, makeFACFromConstraints(
                         3, {{-1, 0, 0, 10}, {0, -1, 0, 10}, {0, 0, 1, -11}},
                         {{1, 2, -3, 0}}));

  // 0 <= r and r <= 3 and 4q + r = 7.
  // Solution: q = 1, r = 3.
  checkSample(true,
              makeFACFromConstraints(2, {{0, 1, 0}, {0, -1, 3}}, {{4, 1, -7}}));

  // 4q + r = 7 and r = 0.
  // Solution: q = 1, r = 3.
  checkSample(false, makeFACFromConstraints(2, {}, {{4, 1, -7}, {0, 1, 0}}));

  // The next two sets are large sets that should take a long time to sample
  // with a naive branch and bound algorithm but can be sampled efficiently with
  // the GBR algorithm.
  //
  // This is a triangle with vertices at (1/3, 0), (2/3, 0) and (10000, 10000).
  checkSample(
      true,
      makeFACFromConstraints(
          2, {{0, 1, 0}, {300000, -299999, -100000}, {-300000, 299998, 200000}},
          {}));

  // This is a tetrahedron with vertices at
  // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 10000), and (10000, 10000, 10000).
  // The first three points form a triangular base on the xz plane with the
  // apex at the fourth point, which is the only integer point.
  checkPermutationsSample(
      true, 3,
      {
          {0, 1, 0, 0},  // y >= 0
          {0, -1, 1, 0}, // z >= y
          {300000, -299998, -1,
           -100000},                    // -300000x + 299998y + 100000 + z <= 0.
          {-150000, 149999, 0, 100000}, // -150000x + 149999y + 100000 >= 0.
      },
      {});

  // Same thing with some spurious extra dimensions equated to constants.
  checkSample(true,
              makeFACFromConstraints(
                  5,
                  {
                      {0, 1, 0, 1, -1, 0},
                      {0, -1, 1, -1, 1, 0},
                      {300000, -299998, -1, -9, 21, -112000},
                      {-150000, 149999, 0, -15, 47, 68000},
                  },
                  {{0, 0, 0, 1, -1, 0},       // p = q.
                   {0, 0, 0, 1, 1, -2000}})); // p + q = 20000 => p = q = 10000.

  // This is a tetrahedron with vertices at
  // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 100), (100, 100 - 1/3, 100).
  checkPermutationsSample(false, 3,
                          {
                              {0, 1, 0, 0},
                              {0, -300, 299, 0},
                              {300 * 299, -89400, -299, -100 * 299},
                              {-897, 894, 0, 598},
                          },
                          {});

  // Two tests involving equalities that are integer empty but not rational
  // empty.

  // This is a line segment from (0, 1/3) to (100, 100 + 1/3).
  checkSample(false, makeFACFromConstraints(
                         2,
                         {
                             {1, 0, 0},   // x >= 0.
                             {-1, 0, 100} // -x + 100 >= 0, i.e., x <= 100.
                         },
                         {
                             {3, -3, 1} // 3x - 3y + 1 = 0, i.e., y = x + 1/3.
                         }));

  // A thin parallelogram. 0 <= x <= 100 and x + 1/3 <= y <= x + 2/3.
  checkSample(false, makeFACFromConstraints(2,
                                            {
                                                {1, 0, 0},    // x >= 0.
                                                {-1, 0, 100}, // x <= 100.
                                                {3, -3, 2},   // 3x - 3y >= -2.
                                                {-3, 3, -1},  // 3x - 3y <= -1.
                                            },
                                            {}));

  checkSample(true, makeFACFromConstraints(2,
                                           {
                                               {2, 0, 0},   // 2x >= 1.
                                               {-2, 0, 99}, // 2x <= 99.
                                               {0, 2, 0},   // 2y >= 0.
                                               {0, -2, 99}, // 2y <= 99.
                                           },
                                           {}));
  // 2D cone with apex at (10000, 10000) and
  // edges passing through (1/3, 0) and (2/3, 0).
  checkSample(
      true,
      makeFACFromConstraints(
          2, {{300000, -299999, -100000}, {-300000, 299998, 200000}}, {}));

  // Cartesian product of a tetrahedron and a 2D cone.
  // The tetrahedron has vertices at
  // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 10000), and (10000, 10000, 10000).
  // The first three points form a triangular base on the xz plane with the
  // apex at the fourth point, which is the only integer point.
  // The cone has apex at (10000, 10000) and
  // edges passing through (1/3, 0) and (2/3, 0).
  checkPermutationsSample(
      true /* not empty */, 5,
      {
          // Tetrahedron contraints:
          {0, 1, 0, 0, 0, 0},  // y >= 0
          {0, -1, 1, 0, 0, 0}, // z >= y
                               // -300000x + 299998y + 100000 + z <= 0.
          {300000, -299998, -1, 0, 0, -100000},
          // -150000x + 149999y + 100000 >= 0.
          {-150000, 149999, 0, 0, 0, 100000},

          // Triangle constraints:
          // 300000p - 299999q >= 100000
          {0, 0, 0, 300000, -299999, -100000},
          // -300000p + 299998q + 200000 >= 0
          {0, 0, 0, -300000, 299998, 200000},
      },
      {});

  // Cartesian product of same tetrahedron as above and {(p, q) : 1/3 <= p <=
  // 2/3}. Since the second set is empty, the whole set is too.
  checkPermutationsSample(
      false /* empty */, 5,
      {
          // Tetrahedron contraints:
          {0, 1, 0, 0, 0, 0},  // y >= 0
          {0, -1, 1, 0, 0, 0}, // z >= y
                               // -300000x + 299998y + 100000 + z <= 0.
          {300000, -299998, -1, 0, 0, -100000},
          // -150000x + 149999y + 100000 >= 0.
          {-150000, 149999, 0, 0, 0, 100000},

          // Second set constraints:
          // 3p >= 1
          {0, 0, 0, 3, 0, -1},
          // 3p <= 2
          {0, 0, 0, -3, 0, 2},
      },
      {});

  // Cartesian product of same tetrahedron as above and
  // {(p, q, r) : 1 <= p <= 2 and p = 3q + 3r}.
  // Since the second set is empty, the whole set is too.
  checkPermutationsSample(
      false /* empty */, 5,
      {
          // Tetrahedron contraints:
          {0, 1, 0, 0, 0, 0, 0},  // y >= 0
          {0, -1, 1, 0, 0, 0, 0}, // z >= y
                                  // -300000x + 299998y + 100000 + z <= 0.
          {300000, -299998, -1, 0, 0, 0, -100000},
          // -150000x + 149999y + 100000 >= 0.
          {-150000, 149999, 0, 0, 0, 0, 100000},

          // Second set constraints:
          // p >= 1
          {0, 0, 0, 1, 0, 0, -1},
          // p <= 2
          {0, 0, 0, -1, 0, 0, 2},
      },
      {
          {0, 0, 0, 1, -3, -3, 0}, // p = 3q + 3r
      });

  // Cartesian product of a tetrahedron and a 2D cone.
  // The tetrahedron is empty and has vertices at
  // (1/3, 0, 0), (2/3, 0, 0), (2/3, 0, 100), and (100, 100 - 1/3, 100).
  // The cone has apex at (10000, 10000) and
  // edges passing through (1/3, 0) and (2/3, 0).
  // Since the tetrahedron is empty, the Cartesian product is too.
  checkPermutationsSample(false /* empty */, 5,
                          {
                              // Tetrahedron contraints:
                              {0, 1, 0, 0, 0, 0},
                              {0, -300, 299, 0, 0, 0},
                              {300 * 299, -89400, -299, 0, 0, -100 * 299},
                              {-897, 894, 0, 0, 0, 598},

                              // Triangle constraints:
                              // 300000p - 299999q >= 100000
                              {0, 0, 0, 300000, -299999, -100000},
                              // -300000p + 299998q + 200000 >= 0
                              {0, 0, 0, -300000, 299998, 200000},
                          },
                          {});

  // Cartesian product of same tetrahedron as above and
  // {(p, q) : 1/3 <= p <= 2/3}.
  checkPermutationsSample(false /* empty */, 5,
                          {
                              // Tetrahedron contraints:
                              {0, 1, 0, 0, 0, 0},
                              {0, -300, 299, 0, 0, 0},
                              {300 * 299, -89400, -299, 0, 0, -100 * 299},
                              {-897, 894, 0, 0, 0, 598},

                              // Second set constraints:
                              // 3p >= 1
                              {0, 0, 0, 3, 0, -1},
                              // 3p <= 2
                              {0, 0, 0, -3, 0, 2},
                          },
                          {});

  checkSample(true, makeFACFromConstraints(3,
                                           {
                                               {2, 0, 0, -1}, // 2x >= 1
                                           },
                                           {{
                                               {1, -1, 0, -1}, // y = x - 1
                                               {0, 1, -1, 0},  // z = y
                                           }}));
}

TEST(FlatAffineConstraintsTest, IsIntegerEmptyTest) {
  // 1 <= 5x and 5x <= 4 (no solution).
  EXPECT_TRUE(
      makeFACFromConstraints(1, {{5, -1}, {-5, 4}}, {}).isIntegerEmpty());
  // 1 <= 5x and 5x <= 9 (solution: x = 1).
  EXPECT_FALSE(
      makeFACFromConstraints(1, {{5, -1}, {-5, 9}}, {}).isIntegerEmpty());

  // Unbounded sets.
  EXPECT_TRUE(makeFACFromConstraints(3,
                                     {
                                         {0, 2, 0, -1}, // 2y >= 1
                                         {0, -2, 0, 1}, // 2y <= 1
                                         {0, 0, 2, -1}, // 2z >= 1
                                     },
                                     {{2, 0, 0, -1}} // 2x = 1
                                     )
                  .isIntegerEmpty());

  EXPECT_FALSE(makeFACFromConstraints(3,
                                      {
                                          {2, 0, 0, -1},  // 2x >= 1
                                          {-3, 0, 0, 3},  // 3x <= 3
                                          {0, 0, 5, -6},  // 5z >= 6
                                          {0, 0, -7, 17}, // 7z <= 17
                                          {0, 3, 0, -2},  // 3y >= 2
                                      },
                                      {})
                   .isIntegerEmpty());

  EXPECT_FALSE(makeFACFromConstraints(3,
                                      {
                                          {2, 0, 0, -1}, // 2x >= 1
                                      },
                                      {{
                                          {1, -1, 0, -1}, // y = x - 1
                                          {0, 1, -1, 0},  // z = y
                                      }})
                   .isIntegerEmpty());

  // FlatAffineConstraints::isEmpty() does not detect the following sets to be
  // empty.

  // 3x + 7y = 1 and 0 <= x, y <= 10.
  // Since x and y are non-negative, 3x + 7y can never be 1.
  EXPECT_TRUE(
      makeFACFromConstraints(
          2, {{1, 0, 0}, {-1, 0, 10}, {0, 1, 0}, {0, -1, 10}}, {{3, 7, -1}})
          .isIntegerEmpty());

  // 2x = 3y and y = x - 1 and x + y = 6z + 2 and 0 <= x, y <= 100.
  // Substituting y = x - 1 in 3y = 2x, we obtain x = 3 and hence y = 2.
  // Since x + y = 5 cannot be equal to 6z + 2 for any z, the set is empty.
  EXPECT_TRUE(
      makeFACFromConstraints(3,
                             {
                                 {1, 0, 0, 0},
                                 {-1, 0, 0, 100},
                                 {0, 1, 0, 0},
                                 {0, -1, 0, 100},
                             },
                             {{2, -3, 0, 0}, {1, -1, 0, -1}, {1, 1, -6, -2}})
          .isIntegerEmpty());

  // 2x = 3y and y = x - 1 + 6z and x + y = 6q + 2 and 0 <= x, y <= 100.
  // 2x = 3y implies x is a multiple of 3 and y is even.
  // Now y = x - 1 + 6z implies y = 2 mod 3. In fact, since y is even, we have
  // y = 2 mod 6. Then since x = y + 1 + 6z, we have x = 3 mod 6, implying
  // x + y = 5 mod 6, which contradicts x + y = 6q + 2, so the set is empty.
  EXPECT_TRUE(makeFACFromConstraints(
                  4,
                  {
                      {1, 0, 0, 0, 0},
                      {-1, 0, 0, 0, 100},
                      {0, 1, 0, 0, 0},
                      {0, -1, 0, 0, 100},
                  },
                  {{2, -3, 0, 0, 0}, {1, -1, 6, 0, -1}, {1, 1, 0, -6, -2}})
                  .isIntegerEmpty());

  // Set with symbols.
  FlatAffineConstraints fac6 = makeFACFromConstraints(2,
                                                      {
                                                          {1, 1, 0},
                                                      },
                                                      {
                                                          {1, -1, 0},
                                                      },
                                                      1);
  EXPECT_FALSE(fac6.isIntegerEmpty());
}

TEST(FlatAffineConstraintsTest, removeRedundantConstraintsTest) {
  FlatAffineConstraints fac = makeFACFromConstraints(1,
                                                     {
                                                         {1, -2}, // x >= 2.
                                                         {-1, 2}  // x <= 2.
                                                     },
                                                     {{1, -2}}); // x == 2.
  fac.removeRedundantConstraints();

  // Both inequalities are redundant given the equality. Both have been removed.
  EXPECT_EQ(fac.getNumInequalities(), 0u);
  EXPECT_EQ(fac.getNumEqualities(), 1u);

  FlatAffineConstraints fac2 =
      makeFACFromConstraints(2,
                             {
                                 {1, 0, -3}, // x >= 3.
                                 {0, 1, -2}  // y >= 2 (redundant).
                             },
                             {{1, -1, 0}}); // x == y.
  fac2.removeRedundantConstraints();

  // The second inequality is redundant and should have been removed. The
  // remaining inequality should be the first one.
  EXPECT_EQ(fac2.getNumInequalities(), 1u);
  EXPECT_THAT(fac2.getInequality(0), ElementsAre(1, 0, -3));
  EXPECT_EQ(fac2.getNumEqualities(), 1u);

  FlatAffineConstraints fac3 =
      makeFACFromConstraints(3, {},
                             {{1, -1, 0, 0},   // x == y.
                              {1, 0, -1, 0},   // x == z.
                              {0, 1, -1, 0}}); // y == z.
  fac3.removeRedundantConstraints();

  // One of the three equalities can be removed.
  EXPECT_EQ(fac3.getNumInequalities(), 0u);
  EXPECT_EQ(fac3.getNumEqualities(), 2u);

  FlatAffineConstraints fac4 = makeFACFromConstraints(
      17,
      {{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
       {0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 500},
       {0, 0, 0, -16, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
       {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 998},
       {0, 0, 0, 16, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15},
       {0, 0, 0, 0, -16, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1},
       {0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 998},
       {0, 0, 0, 0, 16, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15},
       {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 500},
       {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 15},
       {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -16, 0, 0, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -16, 0, 1, 0, 0, 0},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 998},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, -1, 0, 0, 15},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 1},
       {0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 8, 8},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, -8, -1},
       {0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -8, -1},
       {0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -10},
       {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 10},
       {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -13},
       {0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 13},
       {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10},
       {0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10},
       {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -13},
       {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13}},
      {});

  // The above is a large set of constraints without any redundant constraints,
  // as verified by the Fourier-Motzkin based removeRedundantInequalities.
  unsigned nIneq = fac4.getNumInequalities();
  unsigned nEq = fac4.getNumEqualities();
  fac4.removeRedundantInequalities();
  ASSERT_EQ(fac4.getNumInequalities(), nIneq);
  ASSERT_EQ(fac4.getNumEqualities(), nEq);
  // Now we test that removeRedundantConstraints does not find any constraints
  // to be redundant either.
  fac4.removeRedundantConstraints();
  EXPECT_EQ(fac4.getNumInequalities(), nIneq);
  EXPECT_EQ(fac4.getNumEqualities(), nEq);

  FlatAffineConstraints fac5 =
      makeFACFromConstraints(2,
                             {
                                 {128, 0, 127}, // [0]: 128x >= -127.
                                 {-1, 0, 7},    // [1]: x <= 7.
                                 {-128, 1, 0},  // [2]: y >= 128x.
                                 {0, 1, 0}      // [3]: y >= 0.
                             },
                             {});
  // [0] implies that 128x >= 0, since x has to be an integer. (This should be
  // caught by GCDTightenInqualities().)
  // So [2] and [0] imply [3] since we have y >= 128x >= 0.
  fac5.removeRedundantConstraints();
  EXPECT_EQ(fac5.getNumInequalities(), 3u);
  SmallVector<int64_t, 8> redundantConstraint = {0, 1, 0};
  for (unsigned i = 0; i < 3; ++i) {
    // Ensure that the removed constraint was the redundant constraint [3].
    EXPECT_NE(fac5.getInequality(i), ArrayRef<int64_t>(redundantConstraint));
  }
}

TEST(FlatAffineConstraintsTest, addConstantUpperBound) {
  FlatAffineConstraints fac = makeFACFromConstraints(2, {}, {});
  fac.addBound(FlatAffineConstraints::UB, 0, 1);
  EXPECT_EQ(fac.atIneq(0, 0), -1);
  EXPECT_EQ(fac.atIneq(0, 1), 0);
  EXPECT_EQ(fac.atIneq(0, 2), 1);

  fac.addBound(FlatAffineConstraints::UB, {1, 2, 3}, 1);
  EXPECT_EQ(fac.atIneq(1, 0), -1);
  EXPECT_EQ(fac.atIneq(1, 1), -2);
  EXPECT_EQ(fac.atIneq(1, 2), -2);
}

TEST(FlatAffineConstraintsTest, addConstantLowerBound) {
  FlatAffineConstraints fac = makeFACFromConstraints(2, {}, {});
  fac.addBound(FlatAffineConstraints::LB, 0, 1);
  EXPECT_EQ(fac.atIneq(0, 0), 1);
  EXPECT_EQ(fac.atIneq(0, 1), 0);
  EXPECT_EQ(fac.atIneq(0, 2), -1);

  fac.addBound(FlatAffineConstraints::LB, {1, 2, 3}, 1);
  EXPECT_EQ(fac.atIneq(1, 0), 1);
  EXPECT_EQ(fac.atIneq(1, 1), 2);
  EXPECT_EQ(fac.atIneq(1, 2), 2);
}

TEST(FlatAffineConstraintsTest, removeInequality) {
  FlatAffineConstraints fac =
      makeFACFromConstraints(1, {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}, {});

  fac.removeInequalityRange(0, 0);
  EXPECT_EQ(fac.getNumInequalities(), 5u);

  fac.removeInequalityRange(1, 3);
  EXPECT_EQ(fac.getNumInequalities(), 3u);
  EXPECT_THAT(fac.getInequality(0), ElementsAre(0, 0));
  EXPECT_THAT(fac.getInequality(1), ElementsAre(3, 3));
  EXPECT_THAT(fac.getInequality(2), ElementsAre(4, 4));

  fac.removeInequality(1);
  EXPECT_EQ(fac.getNumInequalities(), 2u);
  EXPECT_THAT(fac.getInequality(0), ElementsAre(0, 0));
  EXPECT_THAT(fac.getInequality(1), ElementsAre(4, 4));
}

TEST(FlatAffineConstraintsTest, removeEquality) {
  FlatAffineConstraints fac =
      makeFACFromConstraints(1, {}, {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}});

  fac.removeEqualityRange(0, 0);
  EXPECT_EQ(fac.getNumEqualities(), 5u);

  fac.removeEqualityRange(1, 3);
  EXPECT_EQ(fac.getNumEqualities(), 3u);
  EXPECT_THAT(fac.getEquality(0), ElementsAre(0, 0));
  EXPECT_THAT(fac.getEquality(1), ElementsAre(3, 3));
  EXPECT_THAT(fac.getEquality(2), ElementsAre(4, 4));

  fac.removeEquality(1);
  EXPECT_EQ(fac.getNumEqualities(), 2u);
  EXPECT_THAT(fac.getEquality(0), ElementsAre(0, 0));
  EXPECT_THAT(fac.getEquality(1), ElementsAre(4, 4));
}

TEST(FlatAffineConstraintsTest, clearConstraints) {
  FlatAffineConstraints fac = makeFACFromConstraints(1, {}, {});

  fac.addInequality({1, 0});
  EXPECT_EQ(fac.atIneq(0, 0), 1);
  EXPECT_EQ(fac.atIneq(0, 1), 0);

  fac.clearConstraints();

  fac.addInequality({1, 0});
  EXPECT_EQ(fac.atIneq(0, 0), 1);
  EXPECT_EQ(fac.atIneq(0, 1), 0);
}

/// Check if the expected division representation of local variables matches the
/// computed representation. The expected division representation is given as
/// a vector of expressions set in `divisions` and the corressponding
/// denominator in `denoms`. If expected denominator for a variable is
/// non-positive, the local variable is expected to not have a computed
/// representation.
static void checkDivisionRepresentation(
    FlatAffineConstraints &fac,
    const std::vector<SmallVector<int64_t, 8>> &divisions,
    const SmallVector<int64_t, 8> &denoms) {

  assert(divisions.size() == fac.getNumLocalIds() &&
         "Size of expected divisions does not match number of local variables");
  assert(
      denoms.size() == fac.getNumLocalIds() &&
      "Size of expected denominators does not match number of local variables");

  std::vector<llvm::Optional<std::pair<unsigned, unsigned>>> res(
      fac.getNumLocalIds(), llvm::None);
  fac.getLocalReprs(res);

  // Check if all expected divisions are computed.
  for (unsigned i = 0, e = fac.getNumLocalIds(); i < e; ++i)
    if (denoms[i] > 0)
      EXPECT_TRUE(res[i].hasValue());
    else
      EXPECT_FALSE(res[i].hasValue());

  unsigned divOffset = fac.getNumDimAndSymbolIds();
  for (unsigned i = 0, e = fac.getNumLocalIds(); i < e; ++i) {
    if (!res[i])
      continue;

    // Check if the bounds are of the form:
    //      0 <= expr - divisor * id <= divisor - 1
    // Rearranging, we have:
    //       divisor * id - expr + (divisor - 1) >= 0  <-- Lower bound for 'id'
    //      -divisor * id + expr                 >= 0  <-- Upper bound for 'id'
    // where `id = expr floordiv divisor`.
    unsigned ubPos = res[i]->first, lbPos = res[i]->second;
    const SmallVector<int64_t, 8> &expr = divisions[i];

    // Check if lower bound is of the correct form.
    int64_t computedDivisorLb = fac.atIneq(lbPos, i + divOffset);
    EXPECT_EQ(computedDivisorLb, denoms[i]);
    for (unsigned c = 0, f = fac.getNumLocalIds(); c < f; ++c) {
      if (c == i + divOffset)
        continue;
      EXPECT_EQ(fac.atIneq(lbPos, c), -expr[c]);
    }
    // Check if constant term of lower bound matches expected constant term.
    EXPECT_EQ(fac.atIneq(lbPos, fac.getNumCols() - 1),
              -expr.back() + (denoms[i] - 1));

    // Check if upper bound is of the correct form.
    int64_t computedDivisorUb = fac.atIneq(ubPos, i + divOffset);
    EXPECT_EQ(computedDivisorUb, -denoms[i]);
    for (unsigned c = 0, f = fac.getNumLocalIds(); c < f; ++c) {
      if (c == i + divOffset)
        continue;
      EXPECT_EQ(fac.atIneq(ubPos, c), expr[c]);
    }
    // Check if constant term of upper bound matches expected constant term.
    EXPECT_EQ(fac.atIneq(ubPos, fac.getNumCols() - 1), expr.back());
  }
}

TEST(FlatAffineConstraintsTest, computeLocalReprSimple) {
  FlatAffineConstraints fac = makeFACFromConstraints(1, {}, {});

  fac.addLocalFloorDiv({1, 4}, 10);
  fac.addLocalFloorDiv({1, 0, 100}, 10);

  std::vector<SmallVector<int64_t, 8>> divisions = {{1, 0, 0, 4},
                                                    {1, 0, 0, 100}};
  SmallVector<int64_t, 8> denoms = {10, 10};

  // Check if floordivs can be computed when no other inequalities exist
  // and floor divs do not depend on each other.
  checkDivisionRepresentation(fac, divisions, denoms);
}

TEST(FlatAffineConstraintsTest, computeLocalReprConstantFloorDiv) {
  FlatAffineConstraints fac = makeFACFromConstraints(4, {}, {});

  fac.addInequality({1, 0, 3, 1, 2});
  fac.addInequality({1, 2, -8, 1, 10});
  fac.addEquality({1, 2, -4, 1, 10});

  fac.addLocalFloorDiv({0, 0, 0, 0, 10}, 30);
  fac.addLocalFloorDiv({0, 0, 0, 0, 0, 99}, 101);

  std::vector<SmallVector<int64_t, 8>> divisions = {{0, 0, 0, 0, 0, 0, 10},
                                                    {0, 0, 0, 0, 0, 0, 99}};
  SmallVector<int64_t, 8> denoms = {30, 101};

  // Check if floordivs with constant numerator can be computed.
  checkDivisionRepresentation(fac, divisions, denoms);
}

TEST(FlatAffineConstraintsTest, computeLocalReprRecursive) {
  FlatAffineConstraints fac = makeFACFromConstraints(4, {}, {});
  fac.addInequality({1, 0, 3, 1, 2});
  fac.addInequality({1, 2, -8, 1, 10});
  fac.addEquality({1, 2, -4, 1, 10});

  fac.addLocalFloorDiv({0, -2, 7, 2, 10}, 3);
  fac.addLocalFloorDiv({3, 0, 9, 2, 2, 10}, 5);
  fac.addLocalFloorDiv({0, 1, -123, 2, 0, -4, 10}, 3);

  fac.addInequality({1, 2, -2, 1, -5, 0, 6, 100});
  fac.addInequality({1, 2, -8, 1, 3, 7, 0, -9});

  std::vector<SmallVector<int64_t, 8>> divisions = {{0, -2, 7, 2, 0, 0, 0, 10},
                                                    {3, 0, 9, 2, 2, 0, 0, 10},
                                                    {0, 1, -123, 2, 0, -4, 10}};
  SmallVector<int64_t, 8> denoms = {3, 5, 3};

  // Check if floordivs which may depend on other floordivs can be computed.
  checkDivisionRepresentation(fac, divisions, denoms);
}

TEST(FlatAffineConstraintsTest, removeIdRange) {
  FlatAffineConstraints fac(3, 2, 1);

  fac.addInequality({10, 11, 12, 20, 21, 30, 40});
  fac.removeId(FlatAffineConstraints::IdKind::Symbol, 1);
  EXPECT_THAT(fac.getInequality(0),
              testing::ElementsAre(10, 11, 12, 20, 30, 40));

  fac.removeIdRange(FlatAffineConstraints::IdKind::Dimension, 0, 2);
  EXPECT_THAT(fac.getInequality(0), testing::ElementsAre(12, 20, 30, 40));

  fac.removeIdRange(FlatAffineConstraints::IdKind::Local, 1, 1);
  EXPECT_THAT(fac.getInequality(0), testing::ElementsAre(12, 20, 30, 40));

  fac.removeIdRange(FlatAffineConstraints::IdKind::Local, 0, 1);
  EXPECT_THAT(fac.getInequality(0), testing::ElementsAre(12, 20, 40));
}

TEST(FlatAffineConstraintsTest, simplifyLocalsTest) {
  // (x) : (exists y: 2x + y = 1 and y = 2).
  FlatAffineConstraints fac(1, 0, 1);
  fac.addEquality({2, 1, -1});
  fac.addEquality({0, 1, -2});

  EXPECT_TRUE(fac.isEmpty());

  // (x) : (exists y, z, w: 3x + y = 1 and 2y = z and 3y = w and z = w).
  FlatAffineConstraints fac2(1, 0, 3);
  fac2.addEquality({3, 1, 0, 0, -1});
  fac2.addEquality({0, 2, -1, 0, 0});
  fac2.addEquality({0, 3, 0, -1, 0});
  fac2.addEquality({0, 0, 1, -1, 0});

  EXPECT_TRUE(fac2.isEmpty());

  // (x) : (exists y: x >= y + 1 and 2x + y = 0 and y >= -1).
  FlatAffineConstraints fac3(1, 0, 1);
  fac3.addInequality({1, -1, -1});
  fac3.addInequality({0, 1, 1});
  fac3.addEquality({2, 1, 0});

  EXPECT_TRUE(fac3.isEmpty());
}

} // namespace mlir