blob: 27b840a78ab0204c168757d68d6e0163f0bbaed6 [file] [log] [blame]
// Copyright 2017-2020 The Verible 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
//
// 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 "common/util/range.h"
#include <iterator>
#include <string>
#include "gtest/gtest.h"
#include "absl/strings/string_view.h"
#include "common/util/iterator_range.h"
namespace verible {
namespace {
// Test that IsSubRange matches same empty string.
TEST(IsSubRangeTest, SameEmptyString) {
const absl::string_view substring = "";
EXPECT_TRUE(IsSubRange(substring, substring));
}
// Test that IsSubRange matches same nonempty string.
TEST(IsSubRangeTest, SameNonEmptyString) {
const absl::string_view substring = "nonempty";
EXPECT_TRUE(IsSubRange(substring, substring));
}
// Test that IsSubRange works on string and string_view.
TEST(IsSubRangeTest, MixedStringViewStdString) {
const std::string superstring("nonempty");
const absl::string_view substring =
absl::string_view(superstring).substr(1, 3);
// Note: std::string and absl::string_view iterators are not directly
// comparable to each other.
EXPECT_TRUE(IsSubRange(substring, absl::string_view(superstring)));
}
// Test that IsSubRange works on string iterators.
TEST(IsSubRangeTest, StringAndIterator) {
const std::string superstring("asdasdjasd");
const auto substring =
make_range(superstring.begin() + 1, superstring.begin() + 3);
EXPECT_TRUE(IsSubRange(substring, superstring));
}
// Test that IsSubRange is false on completely different string_views.
TEST(IsSubRangeTest, DifferentStringViews) {
const absl::string_view a = "twiddle-dee";
const absl::string_view b = "twiddle-dum";
EXPECT_FALSE(IsSubRange(a, b));
EXPECT_FALSE(IsSubRange(b, a));
}
// Test that IsSubRange detects non-overlapping string locations.
TEST(IsSubRangeTest, IdenticalSeparateStrings) {
const std::string superstring = "a";
const std::string substring = "a";
EXPECT_FALSE(IsSubRange(substring, superstring));
EXPECT_FALSE(IsSubRange(superstring, substring));
}
// Test that IsSubRange matches sub-string_view.
TEST(IsSubRangeTest, SubStringView) {
const absl::string_view superstring = "not-empty";
EXPECT_TRUE(IsSubRange(superstring.substr(0, 0), superstring)); // empty
EXPECT_TRUE(IsSubRange(superstring.substr(3, 0), superstring)); // empty
EXPECT_TRUE(IsSubRange(superstring.substr(0), superstring));
EXPECT_TRUE(IsSubRange(superstring, superstring.substr(0)));
EXPECT_TRUE(IsSubRange(superstring.substr(1), superstring));
EXPECT_TRUE(IsSubRange(superstring.substr(1, 3), superstring));
}
// Test that IsSubRange is false on superstring views (converse).
TEST(IsSubRangeTest, SuperStringView) {
const absl::string_view superstring = "also-nonempty";
EXPECT_FALSE(IsSubRange(superstring, superstring.substr(1)));
EXPECT_FALSE(IsSubRange(superstring, superstring.substr(1, 3)));
}
// Test that IsSubRange works on substring ranges.
TEST(IsSubRangeTest, DerivedSubStringView) {
const absl::string_view str = "qwertyuiop";
EXPECT_FALSE(IsSubRange(str.substr(0, 0), str.substr(1, 0))); // empty
EXPECT_FALSE(IsSubRange(str.substr(1, 0), str.substr(0, 0))); // empty
EXPECT_TRUE(IsSubRange(str.substr(1, 0), str.substr(0, 1)));
EXPECT_TRUE(IsSubRange(str.substr(1, 1), str.substr(1)));
EXPECT_TRUE(IsSubRange(str.substr(1, 1), str.substr(1, 1)));
EXPECT_FALSE(IsSubRange(str.substr(1, 2), str.substr(3, 2))); // abutting
EXPECT_FALSE(IsSubRange(str.substr(3, 2), str.substr(1, 2))); // abutting
EXPECT_FALSE(IsSubRange(str.substr(1, 2), str.substr(5, 2))); // disjoint
EXPECT_FALSE(IsSubRange(str.substr(5, 2), str.substr(1, 2))); // disjoint
EXPECT_FALSE(IsSubRange(str.substr(1, 4), str.substr(3, 4))); // partial
EXPECT_FALSE(IsSubRange(str.substr(3, 4), str.substr(1, 4))); // partial
}
// Test that BoundsEqual matches same empty string.
TEST(BoundsEqualTest, SameEmptyString) {
const absl::string_view substring = "";
EXPECT_TRUE(BoundsEqual(substring, substring));
}
// Test that BoundsEqual matches same nonempty string.
TEST(BoundsEqualTest, SameNonEmptyString) {
const absl::string_view substring = "nonempty";
EXPECT_TRUE(BoundsEqual(substring, substring));
}
// Test that BoundsEqual is false on completely different string_views.
TEST(BoundsEqualTest, DifferentStringViews) {
const absl::string_view a = "twiddle-dee";
const absl::string_view b = "twiddle-dum";
EXPECT_FALSE(BoundsEqual(a, b));
EXPECT_FALSE(BoundsEqual(b, a));
}
// Test that BoundsEqual is false on non-overlapping string locations.
TEST(BoundsEqualTest, IdenticalSeparateStrings) {
const std::string superstring = "a";
const std::string substring = "a";
EXPECT_FALSE(BoundsEqual(substring, superstring));
EXPECT_FALSE(BoundsEqual(superstring, substring));
}
// Test that BoundsEqual matches sub-string_view.
TEST(BoundsEqualTest, SubStringView) {
const absl::string_view superstring = "not-empty";
EXPECT_FALSE(BoundsEqual(superstring.substr(0, 0), superstring)); // empty
EXPECT_FALSE(BoundsEqual(superstring.substr(3, 0), superstring)); // empty
EXPECT_TRUE(BoundsEqual(superstring.substr(0), superstring));
EXPECT_TRUE(BoundsEqual(superstring, superstring.substr(0)));
EXPECT_FALSE(BoundsEqual(superstring.substr(1), superstring));
EXPECT_FALSE(BoundsEqual(superstring.substr(1, 3), superstring));
}
// Test that BoundsEqual is false on superstring views (converse).
TEST(BoundsEqualTest, SuperStringView) {
const absl::string_view superstring = "also-nonempty";
EXPECT_FALSE(BoundsEqual(superstring, superstring.substr(1)));
EXPECT_FALSE(BoundsEqual(superstring, superstring.substr(1, 3)));
}
// Test that BoundsEqual works on substring ranges.
TEST(BoundsEqualTest, DerivedSubStringView) {
const absl::string_view str = "qwertyuiop";
EXPECT_FALSE(BoundsEqual(str.substr(0, 0), str.substr(1, 0))); // empty
EXPECT_FALSE(BoundsEqual(str.substr(1, 0), str.substr(0, 0))); // empty
EXPECT_FALSE(BoundsEqual(str.substr(1, 0), str.substr(0, 1)));
EXPECT_FALSE(BoundsEqual(str.substr(1, 1), str.substr(1)));
EXPECT_TRUE(BoundsEqual(str.substr(2, 0), str.substr(2, 0))); // empty
EXPECT_TRUE(BoundsEqual(str.substr(1, 1), str.substr(1, 1)));
EXPECT_FALSE(BoundsEqual(str.substr(1, 2), str.substr(3, 2))); // abutting
EXPECT_FALSE(BoundsEqual(str.substr(3, 2), str.substr(1, 2))); // abutting
EXPECT_FALSE(BoundsEqual(str.substr(1, 2), str.substr(5, 2))); // disjoint
EXPECT_FALSE(BoundsEqual(str.substr(5, 2), str.substr(1, 2))); // disjoint
EXPECT_FALSE(BoundsEqual(str.substr(1, 4), str.substr(3, 4))); // partial
EXPECT_FALSE(BoundsEqual(str.substr(3, 4), str.substr(1, 4))); // partial
}
typedef std::pair<int, int> IntPair;
TEST(SubRangeIndicesTest, Empty) {
const std::vector<int> v;
const auto supersequence = make_range(v.begin(), v.end());
const auto subsequence = supersequence;
EXPECT_EQ(SubRangeIndices(subsequence, supersequence), IntPair(0, 0));
}
TEST(SubRangeIndicesTest, RangeInvariant) {
const std::vector<int> supersequence(5);
for (size_t i = 0; i < supersequence.size(); ++i) {
for (size_t j = i; j < supersequence.size(); ++j) {
const auto subsequence =
make_range(supersequence.begin() + i, supersequence.begin() + j);
EXPECT_EQ(SubRangeIndices(subsequence, supersequence), IntPair(i, j))
<< i << ", " << j;
}
}
}
// Tests that swapping subsequence with supersequence fails.
TEST(SubRangeIndicesTest, InsideOut) {
const std::vector<int> supersequence(5);
for (size_t i = 0; i < supersequence.size(); ++i) {
for (size_t j = i; j < supersequence.size(); ++j) {
const auto subsequence =
make_range(supersequence.begin() + i, supersequence.begin() + j);
EXPECT_DEATH(SubRangeIndices(supersequence, subsequence), "")
<< i << ", " << j;
}
}
}
TEST(SubRangeIndicesTest, PartialOverlap) {
const std::vector<int> v(4);
for (size_t i = 0; i < v.size(); ++i) {
for (size_t j = 1; j < v.size(); ++j) {
const auto left = make_range(v.begin(), v.begin() + i);
const auto right = make_range(v.begin() + j, v.end());
EXPECT_DEATH(SubRangeIndices(left, right), "") << i << ", " << j;
}
}
}
// This tests that range indices are comparable and usable in EXPECT_EQ.
TEST(SubRangeIndicesTest, EqComparable) {
const std::vector<int> v;
const auto supersequence = make_range(v.begin(), v.end());
const auto subsequence = supersequence;
auto indices = [&v](const decltype(supersequence)& range) {
return SubRangeIndices(range, v); // v is the common base for both ranges
};
EXPECT_EQ(indices(subsequence), indices(supersequence));
}
} // namespace
} // namespace verible