unittests/Basic/DiverseStackTest.cpp

//===--- DiverseStackTest.cpp ---------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include "swift/Basic/DiverseStack.h"
#include "gtest/gtest.h"
#include <random>

using namespace swift;

namespace {

enum class ValueKind {
  TwoByte = 0,
  ThreeByte = 1,
};

struct ParentType {
  uint8_t allocatedSize;
  ValueKind kind;

public:
  ParentType(uint8_t allocatedSize, ValueKind kind)
      : allocatedSize(allocatedSize), kind(kind) {}

  unsigned allocated_size() const { return allocatedSize; }
  ValueKind getKind() const { return kind; }
};

struct TwoByteType : ParentType {
  uint8_t Value;

  TwoByteType(uint8_t Value)
      : ParentType(sizeof(*this), ValueKind::TwoByte), Value(Value) {}
};

struct ThreeByteType : ParentType {
  uint16_t Value;

  ThreeByteType(uint16_t Value)
      : ParentType(sizeof(*this), ValueKind::ThreeByte), Value(Value) {}
};

struct RandomValueGenerator {
  std::mt19937 gen;
  std::uniform_int_distribution<int> randomEightBitValueGenerator{
      0, std::numeric_limits<uint8_t>::max()};
  std::uniform_int_distribution<uint16_t> randomSixteenBitValueGenerator;

  // Randomly generated bits. This is frozen to ensure that the test doesn't
  // change in between runs.
  static constexpr unsigned seed() { return 0xb2f2c1c8; }

  RandomValueGenerator()
      : gen(seed()), randomEightBitValueGenerator(),
        randomSixteenBitValueGenerator() {}
  ~RandomValueGenerator() = default;

  RandomValueGenerator(const RandomValueGenerator &) = delete;
  RandomValueGenerator(RandomValueGenerator &&) = delete;
  RandomValueGenerator &operator=(const RandomValueGenerator &) = delete;
  RandomValueGenerator &operator=(RandomValueGenerator &&) = delete;

  void push(DiverseStackImpl<ParentType> &Stack,
            std::vector<TwoByteType> &TwoByteVector,
            std::vector<ThreeByteType> &ThreeByteVector,
            std::vector<ValueKind> &ControlVector) {
    uint8_t value = randomEightBitValueGenerator(gen) % 2;
    if (value) {
      auto Next = TwoByteType(randomEightBitValueGenerator(gen));
      Stack.push<TwoByteType>(Next);
      ControlVector.emplace_back(ValueKind::TwoByte);
      TwoByteVector.push_back(Next);
      return;
    }

    auto Next = ThreeByteType(randomSixteenBitValueGenerator(gen));
    Stack.push<ThreeByteType>(Next);
    ControlVector.emplace_back(ValueKind::ThreeByte);
    ThreeByteVector.push_back(Next);
  }

  void push(DiverseStackImpl<ParentType> &Stack) {
    uint8_t value = randomEightBitValueGenerator(gen) % 2;
    if (value) {
      auto Next = TwoByteType(randomEightBitValueGenerator(gen));
      Stack.push<TwoByteType>(Next);
      return;
    }

    auto Next = ThreeByteType(randomSixteenBitValueGenerator(gen));
    Stack.push<ThreeByteType>(Next);
  }
};

} // end anonymous namespace

TEST(DiverseStack, MonomorphicPushPop) {
  DiverseStack<ParentType, 128> Stack;

  EXPECT_TRUE(Stack.empty());

  constexpr size_t TwoByteDataSize = 5;
  uint8_t InputData[TwoByteDataSize] = {5, 9, 1, 2, 10};
  for (unsigned i = 0; i < TwoByteDataSize; ++i) {
    Stack.push<TwoByteType>(TwoByteType(InputData[i]));
  }

  EXPECT_FALSE(Stack.empty());

  for (int i = TwoByteDataSize - 1; i >= 0; --i) {
    TwoByteType T = reinterpret_cast<TwoByteType &>(Stack.top());
    Stack.pop();
    EXPECT_EQ(T.Value, InputData[i]);
  }

  EXPECT_TRUE(Stack.empty());
}

// We test the property here that iterating forward through the stack iterates
// in stack order. This is a bit counter-intuitive for people used to vector
// stacks.
TEST(DiverseStack, Iterate) {
  DiverseStack<ParentType, 128> Stack;

  constexpr size_t TwoByteDataSize = 5;
  uint8_t InputData[TwoByteDataSize] = {5, 9, 1, 2, 10};
  for (unsigned i = 0; i < TwoByteDataSize; ++i) {
    Stack.push<TwoByteType>(TwoByteType(InputData[i]));
  }

  const uint8_t *Ptr = &InputData[TwoByteDataSize - 1];
  for (auto II = Stack.begin(), IE = Stack.end(); II != IE;) {
    TwoByteType T = reinterpret_cast<TwoByteType &>(*II);
    EXPECT_EQ(T.Value, *Ptr);
    --Ptr;
    ++II;
  }
}

TEST(DiverseStack, PolymorphicPushPop) {
  RandomValueGenerator RandomGen;
  DiverseStack<ParentType, 128> Stack;
  std::vector<TwoByteType> TwoByteVector;
  std::vector<ThreeByteType> ThreeByteVector;
  std::vector<ValueKind> ControlVector;

  EXPECT_TRUE(Stack.empty());

  unsigned NumValues = 1024;
  for (unsigned i = 0; i < NumValues; ++i) {
    RandomGen.push(Stack, TwoByteVector, ThreeByteVector, ControlVector);
  }

  EXPECT_EQ(ControlVector.size(), NumValues);
  EXPECT_GE(ControlVector.size(), TwoByteVector.size());
  EXPECT_GE(ControlVector.size(), ThreeByteVector.size());

  while (!ControlVector.empty()) {
    EXPECT_FALSE(Stack.empty());
    ValueKind VectorSwitch = ControlVector.back();
    ControlVector.pop_back();

    if (VectorSwitch == ValueKind::TwoByte) {
      TwoByteType Expected = TwoByteVector.back();
      TwoByteVector.pop_back();
      TwoByteType Actual = static_cast<TwoByteType &>(Stack.top());
      Stack.pop<TwoByteType>();
      EXPECT_EQ(Expected.Value, Actual.Value);
      continue;
    }

    assert(VectorSwitch == ValueKind::ThreeByte);
    ThreeByteType Expected = ThreeByteVector.back();
    ThreeByteVector.pop_back();
    ThreeByteType Actual = static_cast<ThreeByteType &>(Stack.top());
    EXPECT_EQ(Expected.Value, Actual.Value);
    Stack.pop<ThreeByteType>();
  }

  EXPECT_TRUE(ControlVector.empty());
  EXPECT_TRUE(TwoByteVector.empty());
  EXPECT_TRUE(ThreeByteVector.empty());
  EXPECT_TRUE(Stack.empty());
}

TEST(DiverseStack, StableIndexLookup) {
  RandomValueGenerator RandomGen;
  DiverseStack<ParentType, sizeof(unsigned) * 4 * 8> Stack;

  unsigned FirstStop = 3;
  unsigned NumValues = 1024;
  for (unsigned i = 0; i < FirstStop; ++i) {
    RandomGen.push(Stack);
  }

  decltype(Stack)::stable_iterator Iter = Stack.stable_begin();
  ParentType &Parent = *Stack.find(Iter);
  ValueKind SavedKind = Parent.getKind();
  unsigned SavedValue;
  if (SavedKind == ValueKind::TwoByte) {
    SavedValue = static_cast<TwoByteType &>(Parent).Value;
  } else {
    SavedValue = static_cast<ThreeByteType &>(Parent).Value;
  }

  for (unsigned i = FirstStop; i < NumValues; ++i) {
    RandomGen.push(Stack);
  }

  Stack.pop();
  Stack.pop();
  Stack.pop();

  Parent = *Stack.find(Iter);
  EXPECT_EQ(SavedKind, Parent.getKind());
  if (SavedKind == ValueKind::TwoByte) {
    EXPECT_EQ(SavedValue, static_cast<TwoByteType &>(Parent).Value);
  } else {
    EXPECT_EQ(SavedValue, static_cast<ThreeByteType &>(Parent).Value);
  }
}

TEST(DiverseStack, PopMany) {
  RandomValueGenerator RandomGen;
  DiverseStack<ParentType, sizeof(unsigned) * 4 * 8> Stack;

  unsigned FirstStop = 3;
  unsigned NumValues = 1024;
  for (unsigned i = 0; i < FirstStop; ++i) {
    RandomGen.push(Stack);
  }

  decltype(Stack)::stable_iterator Iter = Stack.stable_begin();
  ParentType &Parent = *Stack.find(Iter);
  ValueKind SavedKind = Parent.getKind();
  unsigned SavedValue;
  if (SavedKind == ValueKind::TwoByte) {
    SavedValue = static_cast<TwoByteType &>(Parent).Value;
  } else {
    SavedValue = static_cast<ThreeByteType &>(Parent).Value;
  }

  for (unsigned i = FirstStop; i < NumValues; ++i) {
    RandomGen.push(Stack);
  }

  // Pop until Iter is the top of the stack.
  Stack.pop(Iter);

  Parent = *Stack.find(Iter);
  EXPECT_EQ(SavedKind, Parent.getKind());
  if (SavedKind == ValueKind::TwoByte) {
    EXPECT_EQ(SavedValue, static_cast<TwoByteType &>(Parent).Value);
  } else {
    EXPECT_EQ(SavedValue, static_cast<ThreeByteType &>(Parent).Value);
  }

  EXPECT_EQ(Iter, Stack.stable_begin());
}