| // Copyright 2016 Google Inc. All Rights Reserved. |
| // |
| // 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 "bloaty.h" |
| |
| #include "gmock/gmock.h" |
| #include "gtest/gtest.h" |
| |
| #include <tuple> |
| |
| namespace bloaty { |
| |
| class RangeMapTest : public ::testing::Test { |
| protected: |
| void CheckConsistencyFor(const bloaty::RangeMap& map) { |
| uint64_t last_end = 0; |
| for (auto it = map.mappings_.begin(); it != map.mappings_.end(); ++it) { |
| ASSERT_GE(it->first, last_end); |
| last_end = map.RangeEnd(it); |
| } |
| } |
| |
| void CheckConsistency() { |
| CheckConsistencyFor(map_); |
| CheckConsistencyFor(map2_); |
| CheckConsistencyFor(map3_); |
| } |
| |
| struct Row { |
| std::vector<std::string> keys; |
| uint64_t start; |
| uint64_t end; |
| }; |
| |
| void AssertRollupEquals(const std::vector<const RangeMap*> maps, |
| const std::vector<Row>& rows) { |
| int i = 0; |
| RangeMap::ComputeRollup( |
| maps, [&i, &rows](const std::vector<std::string>& keys, uint64_t start, |
| uint64_t end) { |
| ASSERT_LT(i, rows.size()); |
| const auto& row = rows[i]; |
| ASSERT_EQ(row.keys, keys); |
| ASSERT_EQ(row.start, start); |
| ASSERT_EQ(row.end, end); |
| i++; |
| }); |
| ASSERT_EQ(rows.size(), i); |
| } |
| |
| struct Entry { |
| uint64_t addr; |
| uint64_t end; |
| uint64_t other_start; |
| std::string label; |
| }; |
| |
| void AssertMapEquals(const bloaty::RangeMap& map, |
| const std::vector<Entry>& entries) { |
| auto iter = map.mappings_.begin(); |
| size_t i = 0; |
| for (; i < entries.size() && iter != map.mappings_.end(); ++i, ++iter) { |
| const auto& entry = entries[i]; |
| ASSERT_EQ(entry.addr, iter->first) << i; |
| ASSERT_EQ(entry.end, map.RangeEnd(iter)) << i; |
| ASSERT_EQ(entry.other_start, iter->second.other_start) << i; |
| ASSERT_EQ(entry.label, iter->second.label) << i; |
| } |
| ASSERT_EQ(i, entries.size()); |
| ASSERT_EQ(iter, map.mappings_.end()); |
| |
| // Also test that ComputeRollup yields the same thing. |
| i = 0; |
| RangeMap::ComputeRollup({&map}, |
| [&i, &entries](const std::vector<std::string>& keys, |
| uint64_t start, uint64_t end) { |
| ASSERT_LT(i, entries.size()); |
| const auto& entry = entries[i]; |
| ASSERT_EQ(entry.addr, start); |
| ASSERT_EQ(entry.end, end); |
| ASSERT_EQ(entry.label, keys[0]); |
| i++; |
| }); |
| ASSERT_EQ(entries.size(), i); |
| } |
| |
| void AssertMainMapEquals(const std::vector<Entry>& entries) { |
| AssertMapEquals(map_, entries); |
| } |
| |
| bloaty::RangeMap map_; |
| bloaty::RangeMap map2_; |
| bloaty::RangeMap map3_; |
| |
| const uint64_t kNoTranslation = RangeMap::kNoTranslation; |
| const uint64_t kUnknownSize = RangeMap::kUnknownSize; |
| }; |
| |
| TEST_F(RangeMapTest, AddRange) { |
| CheckConsistency(); |
| AssertMainMapEquals({}); |
| |
| map_.AddRange(4, 3, "foo"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {4, 7, kNoTranslation, "foo"} |
| }); |
| |
| map_.AddRange(30, 5, "bar"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {4, 7, kNoTranslation, "foo"}, |
| {30, 35, kNoTranslation, "bar"} |
| }); |
| |
| map_.AddRange(50, 0, "baz"); // No-op due to 0 size. |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {4, 7, kNoTranslation, "foo"}, |
| {30, 35, kNoTranslation, "bar"} |
| }); |
| |
| map_.AddRange(20, 5, "baz"); |
| map_.AddRange(25, 5, "baz2"); |
| map_.AddRange(40, 5, "quux"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {4, 7, kNoTranslation, "foo"}, |
| {20, 25, kNoTranslation, "baz"}, |
| {25, 30, kNoTranslation, "baz2"}, |
| {30, 35, kNoTranslation, "bar"}, |
| {40, 45, kNoTranslation, "quux"} |
| }); |
| |
| map_.AddRange(21, 25, "overlapping"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {4, 7, kNoTranslation, "foo"}, |
| {20, 25, kNoTranslation, "baz"}, |
| {25, 30, kNoTranslation, "baz2"}, |
| {30, 35, kNoTranslation, "bar"}, |
| {35, 40, kNoTranslation, "overlapping"}, |
| {40, 45, kNoTranslation, "quux"}, |
| {45, 46, kNoTranslation, "overlapping"} |
| }); |
| |
| map_.AddRange(21, 25, "overlapping no-op"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {4, 7, kNoTranslation, "foo"}, |
| {20, 25, kNoTranslation, "baz"}, |
| {25, 30, kNoTranslation, "baz2"}, |
| {30, 35, kNoTranslation, "bar"}, |
| {35, 40, kNoTranslation, "overlapping"}, |
| {40, 45, kNoTranslation, "quux"}, |
| {45, 46, kNoTranslation, "overlapping"} |
| }); |
| |
| map_.AddRange(0, 100, "overlap everything"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {0, 4, kNoTranslation, "overlap everything"}, |
| {4, 7, kNoTranslation, "foo"}, |
| {7, 20, kNoTranslation, "overlap everything"}, |
| {20, 25, kNoTranslation, "baz"}, |
| {25, 30, kNoTranslation, "baz2"}, |
| {30, 35, kNoTranslation, "bar"}, |
| {35, 40, kNoTranslation, "overlapping"}, |
| {40, 45, kNoTranslation, "quux"}, |
| {45, 46, kNoTranslation, "overlapping"}, |
| {46, 100, kNoTranslation, "overlap everything"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, UnknownSize) { |
| map_.AddRange(5, kUnknownSize, "foo"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {5, UINT64_MAX, kNoTranslation, "foo"} |
| }); |
| |
| map_.AddRange(100, 15, "bar"); |
| map_.AddRange(200, kUnknownSize, "baz"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {5, 100, kNoTranslation, "foo"}, |
| {100, 115, kNoTranslation, "bar"}, |
| {200, UINT64_MAX, kNoTranslation, "baz"} |
| }); |
| |
| map2_.AddRange(5, 110, "base0"); |
| map2_.AddRange(200, 50, "base1"); |
| |
| AssertRollupEquals({&map2_, &map_}, { |
| {{"base0", "foo"}, 5, 100}, |
| {{"base0", "bar"}, 100, 115}, |
| {{"base1", "baz"}, 200, 250}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, UnknownSize2) { |
| // This case is slightly weird, but we do consider the "100" below to be a |
| // hard fact even if the size is unknown, so the "[95, 105]: bar" range |
| // doesn't override it. |
| map_.AddRange(100, kUnknownSize, "foo"); |
| map_.AddRange(95, 10, "bar"); |
| AssertMainMapEquals({ |
| {95, 100, kNoTranslation, "bar"}, |
| {100, 105, kNoTranslation, "foo"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, UnknownSize3) { |
| map_.AddRange(100, kUnknownSize, "foo"); |
| map_.AddRange(150, kUnknownSize, "bar"); |
| // This tells us the ultimate size of "foo", and we keep the "foo" label even |
| // though the new label is "baz". |
| map_.AddRange(100, 100, "baz"); |
| AssertMainMapEquals({ |
| {100, 150, kNoTranslation, "foo"}, |
| {150, 200, kNoTranslation, "bar"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, UnknownSize4) { |
| map_.AddRange(100, kUnknownSize, "foo"); |
| map_.AddRange(150, 100, "bar"); |
| // This tells us the ultimate size of "foo", and we keep the "foo" label even |
| // though the new label is "baz". |
| map_.AddRange(100, 100, "baz"); |
| AssertMainMapEquals({ |
| {100, 150, kNoTranslation, "foo"}, |
| {150, 250, kNoTranslation, "bar"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, Bug1) { |
| map_.AddRange(100, 20, "foo"); |
| map_.AddRange(120, 20, "bar"); |
| map_.AddRange(100, 15, "baz"); |
| AssertMainMapEquals({ |
| {100, 120, kNoTranslation, "foo"}, |
| {120, 140, kNoTranslation, "bar"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, Bug2) { |
| map_.AddRange(100, kUnknownSize, "foo"); |
| map_.AddRange(200, 50, "bar"); |
| map_.AddRange(150, 10, "baz"); |
| AssertMainMapEquals({ |
| {100, 150, kNoTranslation, "foo"}, |
| {150, 160, kNoTranslation, "baz"}, |
| {200, 250, kNoTranslation, "bar"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, Bug3) { |
| map_.AddRange(100, kUnknownSize, "foo"); |
| map_.AddRange(200, kUnknownSize, "bar"); |
| map_.AddRange(150, 10, "baz"); |
| AssertMainMapEquals({ |
| {100, 150, kNoTranslation, "foo"}, |
| {150, 160, kNoTranslation, "baz"}, |
| {200, UINT64_MAX, kNoTranslation, "bar"}, |
| }); |
| } |
| |
| TEST_F(RangeMapTest, GetLabel) { |
| map_.AddRange(100, kUnknownSize, "foo"); |
| map_.AddRange(200, 50, "bar"); |
| map_.AddRange(150, 10, "baz"); |
| AssertMainMapEquals({ |
| {100, 150, kNoTranslation, "foo"}, |
| {150, 160, kNoTranslation, "baz"}, |
| {200, 250, kNoTranslation, "bar"}, |
| }); |
| |
| std::string label; |
| |
| ASSERT_TRUE(map_.TryGetLabel(100, &label)); |
| ASSERT_EQ(label, "foo"); |
| ASSERT_TRUE(map_.TryGetLabel(155, &label)); |
| ASSERT_EQ(label, "baz"); |
| ASSERT_TRUE(map_.TryGetLabel(249, &label)); |
| ASSERT_EQ(label, "bar"); |
| ASSERT_FALSE(map_.TryGetLabel(250, &label)); |
| |
| ASSERT_TRUE(map_.TryGetLabelForRange(100, 10, &label)); |
| ASSERT_EQ(label, "foo"); |
| ASSERT_TRUE(map_.TryGetLabelForRange(155, 3, &label)); |
| ASSERT_EQ(label, "baz"); |
| ASSERT_TRUE(map_.TryGetLabelForRange(200, 50, &label)); |
| ASSERT_EQ(label, "bar"); |
| ASSERT_FALSE(map_.TryGetLabelForRange(200, 51, &label)); |
| } |
| |
| TEST_F(RangeMapTest, Translation) { |
| map_.AddDualRange(20, 5, 120, "foo"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {20, 25, 120, "foo"} |
| }); |
| |
| ASSERT_TRUE(map2_.AddRangeWithTranslation(20, 5, "translate me", map_, false, |
| &map3_)); |
| |
| CheckConsistency(); |
| AssertMapEquals(map2_, { |
| {20, 25, kNoTranslation, "translate me"} |
| }); |
| AssertMapEquals(map3_, { |
| {120, 125, kNoTranslation, "translate me"} |
| }); |
| |
| map_.AddDualRange(1000, 30, 1100, "bar"); |
| ASSERT_TRUE(map2_.AddRangeWithTranslation(1000, 5, "translate me2", map_, |
| false, &map3_)); |
| AssertMapEquals(map2_, { |
| {20, 25, kNoTranslation, "translate me"}, |
| {1000, 1005, kNoTranslation, "translate me2"} |
| }); |
| AssertMapEquals(map3_, { |
| {120, 125, kNoTranslation, "translate me"}, |
| {1100, 1105, kNoTranslation, "translate me2"} |
| }); |
| |
| // Starts before base map. |
| ASSERT_FALSE(map2_.AddRangeWithTranslation(15, 8, "translate me", map_, false, |
| &map3_)); |
| |
| // Extends past base map. |
| ASSERT_FALSE(map2_.AddRangeWithTranslation(22, 15, "translate me", map_, |
| false, &map3_)); |
| |
| // Starts and ends in base map, but skips range in the middle. |
| ASSERT_FALSE(map2_.AddRangeWithTranslation(20, 1000, "translate me", map_, |
| false, &map3_)); |
| } |
| |
| TEST_F(RangeMapTest, Translation2) { |
| map_.AddRange(5, 5, "foo"); |
| map_.AddDualRange(20, 5, 120, "bar"); |
| map_.AddRange(25, 5, "baz"); |
| map_.AddDualRange(30, 5, 130, "quux"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {5, 10, kNoTranslation, "foo"}, |
| {20, 25, 120, "bar"}, |
| {25, 30, kNoTranslation, "baz"}, |
| {30, 35, 130, "quux"} |
| }); |
| |
| ASSERT_TRUE(map2_.AddRangeWithTranslation(20, 15, "translate me", map_, false, |
| &map3_)); |
| CheckConsistency(); |
| AssertMapEquals(map2_, { |
| {20, 25, kNoTranslation, "translate me"}, |
| {25, 30, kNoTranslation, "translate me"}, |
| {30, 35, kNoTranslation, "translate me"} |
| }); |
| AssertMapEquals(map3_, { |
| {120, 125, kNoTranslation, "translate me"}, |
| {130, 135, kNoTranslation, "translate me"} |
| }); |
| } |
| |
| TEST_F(RangeMapTest, UnknownTranslation) { |
| map_.AddDualRange(20, 10, 120, "foo"); |
| CheckConsistency(); |
| AssertMainMapEquals({ |
| {20, 30, 120, "foo"} |
| }); |
| |
| map2_.AddRangeWithTranslation(25, kUnknownSize, "translate me", map_, false, |
| &map3_); |
| CheckConsistency(); |
| AssertMapEquals(map2_, { |
| {25, UINT64_MAX, kNoTranslation, "translate me"} |
| }); |
| AssertMapEquals(map3_, { |
| {125, UINT64_MAX, kNoTranslation, "translate me"} |
| }); |
| |
| map2_.AddRange(20, 10, "fallback"); |
| |
| AssertRollupEquals({&map_, &map2_}, { |
| {{"foo", "fallback"}, 20, 25}, |
| {{"foo", "translate me"}, 25, 30}, |
| }); |
| } |
| |
| } // namespace bloaty |