// Copyright 2018 The BoringSSL Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// 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.

#include <openssl/stack.h>

#include <limits.h>

#include <algorithm>
#include <memory>
#include <utility>
#include <vector>

#include <gtest/gtest.h>

#include <openssl/err.h>
#include <openssl/mem.h>
#include <openssl/rand.h>

#include "../mem_internal.h"


// Define a custom stack type for testing. Its first member is a key for
// sorting/comparison, and its second member is a tag so we can tell different
// elements apart, in order to test stable sorting.
using TEST_INT = std::pair<int, int>;
DEFINE_STACK_OF(TEST_INT)

BSSL_NAMESPACE_BEGIN

static void TEST_INT_free(TEST_INT *x) { Delete(x); }

BORINGSSL_MAKE_DELETER(TEST_INT, TEST_INT_free)

static UniquePtr<TEST_INT> TEST_INT_new(int x, int y) {
  UniquePtr<TEST_INT> ret(New<TEST_INT>());
  if (!ret) {
    return nullptr;
  }
  *ret = std::make_pair(x, y);
  return ret;
}

static UniquePtr<TEST_INT> TEST_INT_new(int x) { return TEST_INT_new(x, 0); }

namespace {

struct ShallowStackDeleter {
  void operator()(STACK_OF(TEST_INT) *sk) const { sk_TEST_INT_free(sk); }
};

using ShallowStack = std::unique_ptr<STACK_OF(TEST_INT), ShallowStackDeleter>;

// kNull is treated as a nullptr expectation for purposes of ExpectStackEquals.
// The tests in this file will never use it as a test value.
static const int kNull = INT_MIN;

static void ExpectStackEquals(const STACK_OF(TEST_INT) *sk,
                              const std::vector<std::pair<int, int>> &vec) {
  EXPECT_EQ(vec.size(), sk_TEST_INT_num(sk));
  for (size_t i = 0; i < vec.size(); i++) {
    SCOPED_TRACE(i);
    const TEST_INT *obj = sk_TEST_INT_value(sk, i);
    if (vec[i].first == kNull) {
      EXPECT_FALSE(obj);
    } else {
      EXPECT_TRUE(obj);
      if (obj) {
        EXPECT_EQ(vec[i].first, obj->first);
        EXPECT_EQ(vec[i].second, obj->second);
      }
    }
  }

  // Reading out-of-bounds fails.
  EXPECT_FALSE(sk_TEST_INT_value(sk, vec.size()));
  EXPECT_FALSE(sk_TEST_INT_value(sk, vec.size() + 1));
}

static void ExpectStackEquals(const STACK_OF(TEST_INT) *sk,
                              const std::vector<int> &vec) {
  std::vector<std::pair<int, int>> pairs;
  for (int i : vec) {
    pairs.emplace_back(i, 0);
  }
  ExpectStackEquals(sk, pairs);
}

TEST(StackTest, Basic) {
  UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new_null());
  ASSERT_TRUE(sk);

  // The stack starts out empty.
  std::vector<int> empty;
  ExpectStackEquals(sk.get(), empty);

  // Removing elements from an empty stack does nothing.
  EXPECT_FALSE(sk_TEST_INT_pop(sk.get()));
  EXPECT_FALSE(sk_TEST_INT_shift(sk.get()));
  EXPECT_FALSE(sk_TEST_INT_delete(sk.get(), 0));

  // Push some elements.
  for (int i = 0; i < 6; i++) {
    auto value = TEST_INT_new(i);
    ASSERT_TRUE(value);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
  }

  ExpectStackEquals(sk.get(), {0, 1, 2, 3, 4, 5});

  // Items may be inserted in the middle.
  auto value = TEST_INT_new(6);
  ASSERT_TRUE(value);
  // Hold on to the object for later.
  TEST_INT *raw = value.get();
  ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), value.get(), 4));
  value.release();  // sk_TEST_INT_insert takes ownership on success.

  ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5});

  // Without a comparison function, find searches by pointer.
  value = TEST_INT_new(6);
  ASSERT_TRUE(value);
  size_t index;
  EXPECT_FALSE(sk_TEST_INT_find(sk.get(), &index, value.get()));
  ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, raw));
  EXPECT_EQ(4u, index);

  // sk_TEST_INT_insert can also insert values at the end.
  value = TEST_INT_new(7);
  ASSERT_TRUE(value);
  ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), value.get(), 7));
  value.release();  // sk_TEST_INT_insert takes ownership on success.

  ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5, 7});

  // Out-of-bounds indices are clamped.
  value = TEST_INT_new(8);
  ASSERT_TRUE(value);
  ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), value.get(), 999));
  value.release();  // sk_TEST_INT_insert takes ownership on success.

  ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5, 7, 8});

  // Test removing elements from various places.
  UniquePtr<TEST_INT> removed(sk_TEST_INT_pop(sk.get()));
  EXPECT_EQ(8, removed->first);
  ExpectStackEquals(sk.get(), {0, 1, 2, 3, 6, 4, 5, 7});

  removed.reset(sk_TEST_INT_shift(sk.get()));
  EXPECT_EQ(0, removed->first);
  ExpectStackEquals(sk.get(), {1, 2, 3, 6, 4, 5, 7});

  removed.reset(sk_TEST_INT_delete(sk.get(), 2));
  EXPECT_EQ(3, removed->first);
  ExpectStackEquals(sk.get(), {1, 2, 6, 4, 5, 7});

  // Objects may also be deleted by pointer.
  removed.reset(sk_TEST_INT_delete_ptr(sk.get(), raw));
  EXPECT_EQ(raw, removed.get());
  ExpectStackEquals(sk.get(), {1, 2, 4, 5, 7});

  // Deleting is a no-op is the object is not found.
  value = TEST_INT_new(100);
  ASSERT_TRUE(value);
  EXPECT_FALSE(sk_TEST_INT_delete_ptr(sk.get(), value.get()));

  // Insert nullptr to test deep copy handling of it.
  ASSERT_TRUE(sk_TEST_INT_insert(sk.get(), nullptr, 0));
  ExpectStackEquals(sk.get(), {kNull, 1, 2, 4, 5, 7});

  // Test both deep and shallow copies.
  UniquePtr<STACK_OF(TEST_INT)> copy(sk_TEST_INT_deep_copy(
      sk.get(),
      [](const TEST_INT *x) -> TEST_INT * {
        return x == nullptr ? nullptr
                            : TEST_INT_new(x->first, x->second).release();
      },
      TEST_INT_free));
  ASSERT_TRUE(copy);
  ExpectStackEquals(copy.get(), {kNull, 1, 2, 4, 5, 7});

  ShallowStack shallow(sk_TEST_INT_dup(sk.get()));
  ASSERT_TRUE(shallow);
  ASSERT_EQ(sk_TEST_INT_num(sk.get()), sk_TEST_INT_num(shallow.get()));
  for (size_t i = 0; i < sk_TEST_INT_num(sk.get()); i++) {
    EXPECT_EQ(sk_TEST_INT_value(sk.get(), i),
              sk_TEST_INT_value(shallow.get(), i));
  }

  // Deep copies may fail. This should clean up temporaries.
  EXPECT_FALSE(sk_TEST_INT_deep_copy(
      sk.get(),
      [](const TEST_INT *x) -> TEST_INT * {
        return x == nullptr || x->first == 4
                   ? nullptr
                   : TEST_INT_new(x->first, x->second).release();
      },
      TEST_INT_free));

  // sk_TEST_INT_zero clears a stack, but does not free the elements.
  ShallowStack shallow2(sk_TEST_INT_dup(sk.get()));
  ASSERT_TRUE(shallow2);
  sk_TEST_INT_zero(shallow2.get());
  ExpectStackEquals(shallow2.get(), empty);
}

TEST(StackTest, BigStack) {
  UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new_null());
  ASSERT_TRUE(sk);

  std::vector<int> expected;
  static const int kCount = 100000;
  for (int i = 0; i < kCount; i++) {
    auto value = TEST_INT_new(i);
    ASSERT_TRUE(value);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
    expected.push_back(i);
  }
  ExpectStackEquals(sk.get(), expected);
}

static uint64_t g_compare_count = 0;

// Compares the first member of the pair only.
static int compare(const TEST_INT *const *a, const TEST_INT *const *b) {
  g_compare_count++;
  if ((*a)->first < (*b)->first) {
    return -1;
  }
  if ((*a)->first > (*b)->first) {
    return 1;
  }
  return 0;
}

static int compare_reverse(const TEST_INT *const *a, const TEST_INT *const *b) {
  return -compare(a, b);
}

TEST(StackTest, Sorted) {
  // This test creates a stack containing three copies of each number in `vec`,
  // differing in their second member.
  std::vector<int> vec = {0, 1, 2, 3, 4, 5, 6};
  // This vector holds the expected order after sorting.
  std::vector<std::pair<int, int>> vec_sorted;
  for (int first : vec) {
    for (int second : {0, 1, 2}) {
      vec_sorted.emplace_back(first, second);
    }
  }
  // This vector holds the expected order after removing elements and reversing.
  std::vector<std::pair<int, int>> vec_rev_sorted;
  for (int first : {6, 5, 4, 3, 2, 1}) {
    for (int second : {0, 1, 2}) {
      vec_rev_sorted.emplace_back(first, second);
    }
  }

  do {
    UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
    ASSERT_TRUE(sk);
    for (int second : {0, 1, 2}) {
      for (int first : vec) {
        auto value = TEST_INT_new(first, second);
        ASSERT_TRUE(value);
        ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
      }
    }

    // The stack is not (known to be) sorted.
    EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));

    // With a comparison function, find matches by value of the first member.
    auto ten = TEST_INT_new(10);
    ASSERT_TRUE(ten);
    size_t index;
    EXPECT_FALSE(sk_TEST_INT_find(sk.get(), &index, ten.get()));

    auto three = TEST_INT_new(3);
    ASSERT_TRUE(three);
    ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
    EXPECT_EQ(3, sk_TEST_INT_value(sk.get(), index)->first);

    sk_TEST_INT_sort(sk.get());
    EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

    // The elements were sorted stably.
    ExpectStackEquals(sk.get(), vec_sorted);

    // Sorting an already-sorted list is a no-op.
    uint64_t old_compare_count = g_compare_count;
    sk_TEST_INT_sort(sk.get());
    EXPECT_EQ(old_compare_count, g_compare_count);
    EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
    ExpectStackEquals(sk.get(), vec_sorted);

    // When sorted, find uses binary search.
    ASSERT_TRUE(ten);
    EXPECT_FALSE(sk_TEST_INT_find(sk.get(), &index, ten.get()));

    ASSERT_TRUE(three);
    ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
    EXPECT_EQ(index / 3, 3u);

    // Copies preserve comparison and sorted information.
    UniquePtr<STACK_OF(TEST_INT)> copy(sk_TEST_INT_deep_copy(
        sk.get(),
        [](const TEST_INT *x) -> TEST_INT * {
          return TEST_INT_new(x->first, x->second).release();
        },
        TEST_INT_free));
    ASSERT_TRUE(copy);
    EXPECT_TRUE(sk_TEST_INT_is_sorted(copy.get()));
    ASSERT_TRUE(sk_TEST_INT_find(copy.get(), &index, three.get()));
    EXPECT_EQ(index / 3, 3u);

    ShallowStack copy2(sk_TEST_INT_dup(sk.get()));
    ASSERT_TRUE(copy2);
    EXPECT_TRUE(sk_TEST_INT_is_sorted(copy2.get()));
    ASSERT_TRUE(sk_TEST_INT_find(copy2.get(), &index, three.get()));
    EXPECT_EQ(index / 3, 3u);

    // Removing elements does not affect sortedness.
    // Remove all the elements with first member 0.
    TEST_INT_free(sk_TEST_INT_delete(sk.get(), 2));
    TEST_INT_free(sk_TEST_INT_delete(sk.get(), 1));
    TEST_INT_free(sk_TEST_INT_delete(sk.get(), 0));
    EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
    EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

    // Changing the comparison function invalidates sortedness.
    sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
    EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
    ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
    EXPECT_EQ(6u, index);

    sk_TEST_INT_sort(sk.get());
    EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
    ExpectStackEquals(sk.get(), vec_rev_sorted);
    ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, three.get()));
    EXPECT_EQ(index / 3, 3u);

    // Inserting a new element invalidates sortedness.
    auto tmp = TEST_INT_new(10);
    ASSERT_TRUE(tmp);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(tmp)));
    EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
    ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, ten.get()));
    EXPECT_EQ(18u, index);
  } while (std::next_permutation(vec.begin(), vec.end()));
}

// sk_*_find should return the first matching element in all cases.
TEST(StackTest, FindFirst) {
  UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
  ASSERT_TRUE(sk);
  auto value = TEST_INT_new(1);
  ASSERT_TRUE(value);
  ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
  for (int i = 0; i < 10; i++) {
    value = TEST_INT_new(2);
    ASSERT_TRUE(value);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
  }

  const TEST_INT *two = sk_TEST_INT_value(sk.get(), 1);
  // Pointer-based equality.
  size_t index;
  ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
  EXPECT_EQ(1u, index);

  // Comparator-based equality, unsorted.
  sk_TEST_INT_set_cmp_func(sk.get(), compare);
  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
  ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
  EXPECT_EQ(1u, index);

  // Comparator-based equality, sorted.
  sk_TEST_INT_sort(sk.get());
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
  ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
  EXPECT_EQ(1u, index);

  // Comparator-based equality, sorted and at the front.
  sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
  sk_TEST_INT_sort(sk.get());
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
  ASSERT_TRUE(sk_TEST_INT_find(sk.get(), &index, two));
  EXPECT_EQ(0u, index);
}

// Exhaustively test the binary search.
TEST(StackTest, BinarySearch) {
  static const size_t kCount = 100;
  for (size_t i = 0; i < kCount; i++) {
    SCOPED_TRACE(i);
    for (size_t j = i; j <= kCount; j++) {
      SCOPED_TRACE(j);
      // Make a stack where [0, i) are below, [i, j) match, and [j, kCount) are
      // above.
      UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
      ASSERT_TRUE(sk);
      for (size_t k = 0; k < i; k++) {
        auto value = TEST_INT_new(-1);
        ASSERT_TRUE(value);
        ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
      }
      for (size_t k = i; k < j; k++) {
        auto value = TEST_INT_new(0);
        ASSERT_TRUE(value);
        ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
      }
      for (size_t k = j; k < kCount; k++) {
        auto value = TEST_INT_new(1);
        ASSERT_TRUE(value);
        ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
      }
      sk_TEST_INT_sort(sk.get());

      auto key = TEST_INT_new(0);
      ASSERT_TRUE(key);

      size_t idx;
      int found = sk_TEST_INT_find(sk.get(), &idx, key.get());
      if (i == j) {
        EXPECT_FALSE(found);
      } else {
        ASSERT_TRUE(found);
        EXPECT_EQ(i, idx);
      }
    }
  }
}

TEST(StackTest, DeleteIf) {
  UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
  ASSERT_TRUE(sk);
  for (int v : {1, 9, 2, 8, 3, 7, 4, 6, 5}) {
    auto obj = TEST_INT_new(v);
    ASSERT_TRUE(obj);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(obj)));
  }

  auto keep_only_multiples = [](TEST_INT *x, void *data) {
    auto d = static_cast<const int *>(data);
    if (x->first % *d == 0) {
      return 0;
    }
    TEST_INT_free(x);
    return 1;
  };

  int d = 2;
  sk_TEST_INT_delete_if(sk.get(), keep_only_multiples, &d);
  ExpectStackEquals(sk.get(), {2, 8, 4, 6});

  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
  sk_TEST_INT_sort(sk.get());
  ExpectStackEquals(sk.get(), {2, 4, 6, 8});
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // Keep only multiples of four.
  d = 4;
  sk_TEST_INT_delete_if(sk.get(), keep_only_multiples, &d);
  ExpectStackEquals(sk.get(), {4, 8});

  // Removing elements preserves the sorted bit.
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // Delete everything.
  d = 16;
  sk_TEST_INT_delete_if(sk.get(), keep_only_multiples, &d);
  std::vector<int> empty;
  ExpectStackEquals(sk.get(), empty);
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
}

TEST(StackTest, SortAndDedup) {
  UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
  ASSERT_TRUE(sk);
  sk_TEST_INT_sort_and_dedup(sk.get(), TEST_INT_free);
  ExpectStackEquals(sk.get(), std::vector<int>{});

  for (int v : {1, 2, 3, 4, 5, 2, 2, 2, 2, 3}) {
    auto obj = TEST_INT_new(v);
    ASSERT_TRUE(obj);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(obj)));
  }

  sk_TEST_INT_sort_and_dedup(sk.get(), TEST_INT_free);
  ExpectStackEquals(sk.get(), {1, 2, 3, 4, 5});

  sk_TEST_INT_sort_and_dedup(sk.get(), TEST_INT_free);
  ExpectStackEquals(sk.get(), {1, 2, 3, 4, 5});

  // Repeat with non-owning pointers.
  sk.reset(sk_TEST_INT_new(compare));
  ASSERT_TRUE(sk);
  for (int v : {1, 2, 3, 4, 5, 2, 2, 2, 2, 3}) {
    auto obj = TEST_INT_new(v);
    ASSERT_TRUE(obj);
    ASSERT_TRUE(PushToStack(sk.get(), std::move(obj)));
  }

  // |not_owned| does not own its contents, so we cannot use bssl::UniquePtr.
  STACK_OF(TEST_INT) *not_owned = sk_TEST_INT_dup(sk.get());
  ASSERT_TRUE(not_owned);
  sk_TEST_INT_sort_and_dedup(not_owned, nullptr);
  ExpectStackEquals(not_owned, {1, 2, 3, 4, 5});
  sk_TEST_INT_sort_and_dedup(not_owned, nullptr);
  ExpectStackEquals(not_owned, {1, 2, 3, 4, 5});
  sk_TEST_INT_free(not_owned);
}

TEST(StackTest, IsSorted) {
  UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new_null());
  ASSERT_TRUE(sk);
  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));

  // Empty lists are always known to be sorted.
  sk_TEST_INT_set_cmp_func(sk.get(), compare);
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // As are one-element lists.
  auto value = TEST_INT_new(2);
  ASSERT_TRUE(value);
  ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // Two-element lists require an explicit sort.
  value = TEST_INT_new(1);
  ASSERT_TRUE(value);
  ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));

  // The list is now sorted.
  sk_TEST_INT_sort(sk.get());
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // After changing the comparison function, it no longer is sorted.
  sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));

  sk_TEST_INT_sort(sk.get());
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // After changing one element, it is no longer sorted.
  value = TEST_INT_new(10);
  ASSERT_TRUE(value);
  TEST_INT_free(sk_TEST_INT_value(sk.get(), 0));
  sk_TEST_INT_set(sk.get(), 0, value.release());
  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));

  sk_TEST_INT_sort(sk.get());
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // But, starting from one element, switching the comparison function preserves
  // the sorted bit.
  TEST_INT_free(sk_TEST_INT_pop(sk.get()));
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  sk_TEST_INT_set_cmp_func(sk.get(), compare);
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  value = TEST_INT_new(100);
  ASSERT_TRUE(value);
  TEST_INT_free(sk_TEST_INT_value(sk.get(), 0));
  sk_TEST_INT_set(sk.get(), 0, value.release());
  EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));

  // Without a comparison function, the list cannot be sorted.
  sk_TEST_INT_set_cmp_func(sk.get(), nullptr);
  EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
}

TEST(StackTest, Sort) {
  constexpr size_t kMaxLength = 100;
  constexpr int kIterations = 500;
  for (size_t len = 0; len < kMaxLength; len++) {
    SCOPED_TRACE(len);
    for (int iter = 0; iter < kIterations; iter++) {
      // Make a random input list.
      std::vector<int> vec(len);
      RAND_bytes(reinterpret_cast<uint8_t *>(vec.data()),
                 sizeof(int) * vec.size());
      SCOPED_TRACE(testing::PrintToString(vec));

      // Convert it to a |STACK_OF(TEST_INT)|.
      UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new(compare));
      ASSERT_TRUE(sk);
      for (int v : vec) {
        auto value = TEST_INT_new(v);
        ASSERT_TRUE(value);
        ASSERT_TRUE(PushToStack(sk.get(), std::move(value)));
      }

      // Sort it with our sort implementation.
      sk_TEST_INT_sort(sk.get());
      std::vector<int> result;
      for (const TEST_INT *v : sk.get()) {
        result.push_back(v->first);
      }

      // The result must match the STL's version.
      std::stable_sort(vec.begin(), vec.end());
      EXPECT_EQ(vec, result);
    }
  }
}

// STACK_OF(T) APIs should generally cleanly treat nullptr as the empty list.
TEST(StackTest, NullIsEmpty) {
  // Clear the error queue, to be sampled later.
  ERR_clear_error();

  EXPECT_EQ(0u, sk_TEST_INT_num(nullptr));

  EXPECT_EQ(nullptr, sk_TEST_INT_value(nullptr, 0));
  EXPECT_EQ(nullptr, sk_TEST_INT_value(nullptr, 1));

  UniquePtr<TEST_INT> value = TEST_INT_new(6);
  ASSERT_TRUE(value);
  size_t index;
  EXPECT_FALSE(sk_TEST_INT_find(nullptr, &index, value.get()));

  // Deleting from an empty list is a no-op.
  EXPECT_EQ(nullptr, sk_TEST_INT_pop(nullptr));
  EXPECT_EQ(nullptr, sk_TEST_INT_shift(nullptr));
  EXPECT_EQ(nullptr, sk_TEST_INT_delete(nullptr, 0));
  EXPECT_EQ(nullptr, sk_TEST_INT_delete(nullptr, 1));
  EXPECT_EQ(nullptr, sk_TEST_INT_delete_ptr(nullptr, value.get()));
  sk_TEST_INT_delete_if(
      nullptr,
      [](TEST_INT *, void *) -> int {
        ADD_FAILURE() << "callback should not have been called";
        return 0;
      },
      nullptr);

  // An empty list is always sorted.
  EXPECT_TRUE(sk_TEST_INT_is_sorted(nullptr));
  sk_TEST_INT_sort(nullptr);

  // Copying an empty list gives an empty list.
  EXPECT_EQ(nullptr, sk_TEST_INT_dup(nullptr));
  EXPECT_EQ(nullptr,
            sk_TEST_INT_deep_copy(
                nullptr,
                [](const TEST_INT *) -> TEST_INT * {
                  ADD_FAILURE() << "copy callback should not have been called";
                  return nullptr;
                },
                [](TEST_INT *) {
                  ADD_FAILURE() << "free callback should not have been called";
                }));

  // None of these operations should have added to the error queue.
  EXPECT_EQ(0u, ERR_get_error());
}

}  // namespace
BSSL_NAMESPACE_END