runtime/subtype_check_info_test.cc

/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * 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
 *
 *      http://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 "subtype_check_info.h"

#include "gtest/gtest.h"
#include "android-base/logging.h"

namespace art {

constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
constexpr size_t BitString::kCapacity;

};  // namespace art

using namespace art;  // NOLINT

// These helper functions are only used by the test,
// so they are not in the main BitString class.
std::string Stringify(BitString bit_string) {
  std::stringstream ss;
  ss << bit_string;
  return ss.str();
}

BitStringChar MakeBitStringChar(size_t idx, size_t val) {
  return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx));
}

BitStringChar MakeBitStringChar(size_t val) {
  return BitStringChar(val, MinimumBitsToStore(val));
}

BitString MakeBitString(std::initializer_list<size_t> values = {}) {
  CHECK_GE(BitString::kCapacity, values.size());

  BitString bs{};

  size_t i = 0;
  for (size_t val : values) {
    bs.SetAt(i, MakeBitStringChar(i, val));
    ++i;
  }

  return bs;
}

template <typename T>
size_t AsUint(const T& value) {
  size_t uint_value = 0;
  memcpy(&uint_value, &value, sizeof(value));
  return uint_value;
}

// Make max bistring, e.g. BitString[4095,15,2047] for {12,4,11}
template <size_t kCount = BitString::kCapacity>
BitString MakeBitStringMax() {
  BitString bs{};

  for (size_t i = 0; i < kCount; ++i) {
    bs.SetAt(i,
             MakeBitStringChar(i, MaxInt<BitStringChar::StorageType>(BitString::kBitSizeAtPosition[i])));
  }

  return bs;
}

BitString SetBitStringCharAt(BitString bit_string, size_t i, size_t val) {
  BitString bs = bit_string;
  bs.SetAt(i, MakeBitStringChar(i, val));
  return bs;
}

struct SubtypeCheckInfoTest : public ::testing::Test {
 protected:
  void SetUp() override {
    android::base::InitLogging(/*argv=*/nullptr);
  }

  void TearDown() override {
  }

  static SubtypeCheckInfo MakeSubtypeCheckInfo(BitString path_to_root = {},
                                               BitStringChar next = {},
                                               bool overflow = false,
                                               size_t depth = 1u) {
    // Depth=1 is good default because it will go through all state transitions,
    // and its children will also go through all state transitions.
    return SubtypeCheckInfo(path_to_root, next, overflow, depth);
  }

  static SubtypeCheckInfo MakeSubtypeCheckInfoInfused(BitString bs = {},
                                                      bool overflow = false,
                                                      size_t depth = 1u) {
    // Depth=1 is good default because it will go through all state transitions,
    // and its children will also go through all state transitions.
    SubtypeCheckBits iod;
    iod.bitstring_ = bs;
    iod.overflow_ = overflow;
    return SubtypeCheckInfo::Create(iod, depth);
  }

  static SubtypeCheckInfo MakeSubtypeCheckInfoUnchecked(BitString bs = {},
                                                        bool overflow = false,
                                                        size_t depth = 1u) {
    // Depth=1 is good default because it will go through all state transitions,
    // and its children will also go through all state transitions.
    return SubtypeCheckInfo::MakeUnchecked(bs, overflow, depth);
  }

  static bool HasNext(const SubtypeCheckInfo& io) {
    return io.HasNext();
  }

  static BitString GetPathToRoot(const SubtypeCheckInfo& io) {
    return io.GetPathToRoot();
  }

  // Create an SubtypeCheckInfo with the same depth, but with everything else reset.
  // Returns: SubtypeCheckInfo in the Uninitialized state.
  static SubtypeCheckInfo CopyCleared(const SubtypeCheckInfo& sc) {
    SubtypeCheckInfo cleared_copy{};
    cleared_copy.depth_ = sc.depth_;
    DCHECK_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy.GetState());
    return cleared_copy;
  }
};

const char* GetExpectedMessageForDeathTest(const char* msg) {
#ifdef ART_TARGET_ANDROID
  // On Android, dcheck failure messages go to logcat,
  // which gtest death tests does not check, and thus the tests would fail with
  // "unexpected message ''"
  UNUSED(msg);
  return "";  // Still ensures there was a bad return code, but match anything.
#else
  return msg;
#endif
}

TEST_F(SubtypeCheckInfoTest, IllegalValues) {
  // This test relies on BitString being at least 3 large.
  // It will need to be updated otherwise.
  ASSERT_LE(3u, BitString::kCapacity);

  // Illegal values during construction would cause a Dcheck failure and crash.
  ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}),
                                    /*next=*/MakeBitStringChar(0),
                                    /*overflow=*/false,
                                    /*depth=*/0u),
               GetExpectedMessageForDeathTest("Path was too long for the depth"));
  ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({1u, 1u}),
                                           /*overflow=*/false,
                                           /*depth=*/0u),
               GetExpectedMessageForDeathTest("Bitstring too long for depth"));
  ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({1u}),
                                    /*next=*/MakeBitStringChar(0),
                                    /*overflow=*/false,
                                    /*depth=*/1u),
               GetExpectedMessageForDeathTest("Expected \\(Assigned\\|Initialized\\) "
                                              "state to have >0 Next value"));
  ASSERT_DEATH(MakeSubtypeCheckInfoInfused(MakeBitString({0u, 2u, 1u}),
                                           /*overflow=*/false,
                                           /*depth=*/2u),
               GetExpectedMessageForDeathTest("Path to root had non-0s following 0s"));
  ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 2u}),
                                    /*next=*/MakeBitStringChar(1u),
                                    /*overflow=*/false,
                                    /*depth=*/2u),
               GetExpectedMessageForDeathTest("Path to root had non-0s following 0s"));
  ASSERT_DEATH(MakeSubtypeCheckInfo(MakeBitString({0u, 1u, 1u}),
                                    /*next=*/MakeBitStringChar(0),
                                    /*overflow=*/false,
                                    /*depth=*/3u),
               GetExpectedMessageForDeathTest("Path to root had non-0s following 0s"));

  // These are really slow (~1sec per death test on host),
  // keep them down to a minimum.
}

TEST_F(SubtypeCheckInfoTest, States) {
  EXPECT_EQ(SubtypeCheckInfo::kUninitialized, MakeSubtypeCheckInfo().GetState());
  EXPECT_EQ(SubtypeCheckInfo::kInitialized,
            MakeSubtypeCheckInfo(/*path_to_root=*/{}, /*next=*/MakeBitStringChar(1)).GetState());
  EXPECT_EQ(SubtypeCheckInfo::kOverflowed,
            MakeSubtypeCheckInfo(/*path_to_root=*/{},
                                 /*next=*/MakeBitStringChar(1),
                                 /*overflow=*/true,
                                 /*depth=*/1u).GetState());
  EXPECT_EQ(SubtypeCheckInfo::kAssigned,
            MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitString({1u}),
                                 /*next=*/MakeBitStringChar(1),
                                 /*overflow=*/false,
                                 /*depth=*/1u).GetState());

  // Test edge conditions: depth == BitString::kCapacity (No Next value).
  EXPECT_EQ(SubtypeCheckInfo::kAssigned,
            MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(),
                                 /*next=*/MakeBitStringChar(0),
                                 /*overflow=*/false,
                                 /*depth=*/BitString::kCapacity).GetState());
  EXPECT_EQ(SubtypeCheckInfo::kInitialized,
            MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax<BitString::kCapacity - 1u>(),
                                 /*next=*/MakeBitStringChar(0),
                                 /*overflow=*/false,
                                 /*depth=*/BitString::kCapacity).GetState());
  // Test edge conditions: depth > BitString::kCapacity (Must overflow).
  EXPECT_EQ(SubtypeCheckInfo::kOverflowed,
            MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(),
                                 /*next=*/MakeBitStringChar(0),
                                 /*overflow=*/true,
                                 /*depth=*/BitString::kCapacity + 1u).GetState());
}

TEST_F(SubtypeCheckInfoTest, NextValue) {
  // Validate "Next" is correctly aliased as the Bitstring[Depth] character.
  EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}),
                                                                 /*overflow=*/false,
                                                                 /*depth=*/0u).GetNext());
  EXPECT_EQ(MakeBitStringChar(2u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}),
                                                                 /*overflow=*/false,
                                                                 /*depth=*/1u).GetNext());
  EXPECT_EQ(MakeBitStringChar(3u), MakeSubtypeCheckInfoUnchecked(MakeBitString({1u, 2u, 3u}),
                                                                 /*overflow=*/false,
                                                                 /*depth=*/2u).GetNext());
  EXPECT_EQ(MakeBitStringChar(1u), MakeSubtypeCheckInfoUnchecked(MakeBitString({0u, 2u, 1u}),
                                                                 /*overflow=*/false,
                                                                 /*depth=*/2u).GetNext());
  // Test edge conditions: depth == BitString::kCapacity (No Next value).
  EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(),
                                                     /*overflow=*/false,
                                                     /*depth=*/BitString::kCapacity)));
  // Anything with depth >= BitString::kCapacity has no next value.
  EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<BitString::kCapacity>(),
                                                     /*overflow=*/false,
                                                     /*depth=*/BitString::kCapacity + 1u)));
  EXPECT_FALSE(HasNext(MakeSubtypeCheckInfoUnchecked(MakeBitStringMax(),
                                                     /*overflow=*/false,
                                                     /*depth=*/std::numeric_limits<size_t>::max())));
}

template <size_t kPos = BitString::kCapacity>
size_t LenForPos() { return BitString::GetBitLengthTotalAtPosition(kPos); }

TEST_F(SubtypeCheckInfoTest, EncodedPathToRoot) {
  using StorageType = BitString::StorageType;

  SubtypeCheckInfo sci =
      MakeSubtypeCheckInfo(/*path_to_root=*/MakeBitStringMax(),
                           /*next=*/BitStringChar{},
                           /*overflow=*/false,
                           /*depth=*/BitString::kCapacity);
  // 0b000...111 where LSB == 1, and trailing 1s = the maximum bitstring representation.
  EXPECT_EQ(MaxInt<StorageType>(LenForPos()), sci.GetEncodedPathToRoot());

  // The rest of this test is written assuming kCapacity == 3 for convenience.
  // Please update the test if this changes.
  ASSERT_EQ(3u, BitString::kCapacity);
  ASSERT_EQ(12u, BitString::kBitSizeAtPosition[0]);
  ASSERT_EQ(4u, BitString::kBitSizeAtPosition[1]);
  ASSERT_EQ(11u, BitString::kBitSizeAtPosition[2]);

  SubtypeCheckInfo sci2 =
      MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(),
                                   /*overflow=*/false,
                                   /*depth=*/BitString::kCapacity);

#define MAKE_ENCODED_PATH(pos0, pos1, pos2) \
    (((pos0) << 0) | \
     ((pos1) << BitString::kBitSizeAtPosition[0]) | \
     ((pos2) << (BitString::kBitSizeAtPosition[0] + BitString::kBitSizeAtPosition[1])))

  EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0),
            sci2.GetEncodedPathToRoot());
  EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b11111111111),
            sci2.GetEncodedPathToRootMask());

  SubtypeCheckInfo sci3 =
      MakeSubtypeCheckInfoUnchecked(MakeBitStringMax<2u>(),
                                   /*overflow=*/false,
                                   /*depth=*/BitString::kCapacity - 1u);

  EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0),
            sci3.GetEncodedPathToRoot());
  EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b1111, 0b0),
            sci3.GetEncodedPathToRootMask());

  SubtypeCheckInfo sci4 =
      MakeSubtypeCheckInfoUnchecked(MakeBitString({0b1010101u}),
                                   /*overflow=*/false,
                                   /*depth=*/BitString::kCapacity - 2u);

  EXPECT_EQ(MAKE_ENCODED_PATH(0b1010101u, 0b0000, 0b0), sci4.GetEncodedPathToRoot());
  EXPECT_EQ(MAKE_ENCODED_PATH(MaxInt<BitString::StorageType>(12), 0b0000, 0b0),
            sci4.GetEncodedPathToRootMask());
}

TEST_F(SubtypeCheckInfoTest, NewForRoot) {
  SubtypeCheckInfo sci = SubtypeCheckInfo::CreateRoot();
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, sci.GetState());  // Root is always assigned.
  EXPECT_EQ(0u, GetPathToRoot(sci).Length());  // Root's path length is 0.
  EXPECT_TRUE(HasNext(sci));  // Root always has a "Next".
  EXPECT_EQ(MakeBitStringChar(1u), sci.GetNext());  // Next>=1 to disambiguate from Uninitialized.
}

TEST_F(SubtypeCheckInfoTest, CopyCleared) {
  SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot();
  EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());

  SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState());
  EXPECT_EQ(MakeBitStringChar(2u), root.GetNext());  // Next incremented for Assign.
  EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC));

  SubtypeCheckInfo cleared_copy = CopyCleared(childC);
  EXPECT_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy.GetState());
  EXPECT_EQ(MakeBitString({}), GetPathToRoot(cleared_copy));

  // CopyCleared is just a thin wrapper around value-init and providing the depth.
  SubtypeCheckInfo cleared_copy_value =
      SubtypeCheckInfo::Create(SubtypeCheckBits{}, /*depth=*/1u);
  EXPECT_EQ(SubtypeCheckInfo::kUninitialized, cleared_copy_value.GetState());
  EXPECT_EQ(MakeBitString({}), GetPathToRoot(cleared_copy_value));
}

TEST_F(SubtypeCheckInfoTest, NewForChild2) {
  SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot();
  EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());

  SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState());
  EXPECT_EQ(MakeBitStringChar(2u), root.GetNext());  // Next incremented for Assign.
  EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC));
}

TEST_F(SubtypeCheckInfoTest, NewForChild) {
  SubtypeCheckInfo root = SubtypeCheckInfo::CreateRoot();
  EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());

  SubtypeCheckInfo childA = root.CreateChild(/*assign_next=*/false);
  EXPECT_EQ(SubtypeCheckInfo::kInitialized, childA.GetState());
  EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());  // Next unchanged for Initialize.
  EXPECT_EQ(MakeBitString({}), GetPathToRoot(childA));

  SubtypeCheckInfo childB = root.CreateChild(/*assign_next=*/false);
  EXPECT_EQ(SubtypeCheckInfo::kInitialized, childB.GetState());
  EXPECT_EQ(MakeBitStringChar(1u), root.GetNext());  // Next unchanged for Initialize.
  EXPECT_EQ(MakeBitString({}), GetPathToRoot(childB));

  SubtypeCheckInfo childC = root.CreateChild(/*assign_next=*/true);
  EXPECT_EQ(SubtypeCheckInfo::kAssigned, childC.GetState());
  EXPECT_EQ(MakeBitStringChar(2u), root.GetNext());  // Next incremented for Assign.
  EXPECT_EQ(MakeBitString({1u}), GetPathToRoot(childC));

  {
    size_t cur_depth = 1u;
    SubtypeCheckInfo latest_child = childC;
    while (cur_depth != BitString::kCapacity) {
      latest_child = latest_child.CreateChild(/*assign_next=*/true);
      ASSERT_EQ(SubtypeCheckInfo::kAssigned, latest_child.GetState());
      ASSERT_EQ(cur_depth + 1u, GetPathToRoot(latest_child).Length());
      cur_depth++;
    }

    // Future assignments will result in a too-deep overflow.
    SubtypeCheckInfo child_of_deep = latest_child.CreateChild(/*assign_next=*/true);
    EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of_deep.GetState());
    EXPECT_EQ(GetPathToRoot(latest_child), GetPathToRoot(child_of_deep));

    // Assignment of too-deep overflow also causes overflow.
    SubtypeCheckInfo child_of_deep_2 = child_of_deep.CreateChild(/*assign_next=*/true);
    EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of_deep_2.GetState());
    EXPECT_EQ(GetPathToRoot(child_of_deep), GetPathToRoot(child_of_deep_2));
  }

  {
    size_t cur_next = 2u;
    while (true) {
      if (cur_next == MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[0u])) {
        break;
      }

      SubtypeCheckInfo child = root.CreateChild(/*assign_next=*/true);
      ASSERT_EQ(SubtypeCheckInfo::kAssigned, child.GetState());
      ASSERT_EQ(MakeBitStringChar(cur_next+1u), root.GetNext());
      ASSERT_EQ(MakeBitString({cur_next}), GetPathToRoot(child));

      cur_next++;
    }
    // Now the root will be in a state that further assigns will be too-wide overflow.

    // Initialization still succeeds.
    SubtypeCheckInfo child = root.CreateChild(/*assign_next=*/false);
    EXPECT_EQ(SubtypeCheckInfo::kInitialized, child.GetState());
    EXPECT_EQ(MakeBitStringChar(cur_next), root.GetNext());
    EXPECT_EQ(MakeBitString({}), GetPathToRoot(child));

    // Assignment goes to too-wide Overflow.
    SubtypeCheckInfo child_of = root.CreateChild(/*assign_next=*/true);
    EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of.GetState());
    EXPECT_EQ(MakeBitStringChar(cur_next), root.GetNext());
    EXPECT_EQ(MakeBitString({}), GetPathToRoot(child_of));

    // Assignment of overflowed child still succeeds.
    // The path to root is the same.
    SubtypeCheckInfo child_of2 = child_of.CreateChild(/*assign_next=*/true);
    EXPECT_EQ(SubtypeCheckInfo::kOverflowed, child_of2.GetState());
    EXPECT_EQ(GetPathToRoot(child_of), GetPathToRoot(child_of2));
  }
}