1 //===- llvm/unittest/Support/AddresRangeTest.cpp --------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/ADT/AddressRanges.h" 10 #include "llvm/Testing/Support/Error.h" 11 12 #include "gmock/gmock.h" 13 #include "gtest/gtest.h" 14 #include <string> 15 16 using namespace llvm; 17 18 TEST(AddressRangeTest, TestRanges) { 19 // test llvm::AddressRange. 20 const uint64_t StartAddr = 0x1000; 21 const uint64_t EndAddr = 0x2000; 22 // Verify constructor and API to ensure it takes start and end address. 23 const AddressRange Range(StartAddr, EndAddr); 24 EXPECT_EQ(Range.size(), EndAddr - StartAddr); 25 26 // Verify llvm::AddressRange::contains(). 27 EXPECT_FALSE(Range.contains(0)); 28 EXPECT_FALSE(Range.contains(StartAddr - 1)); 29 EXPECT_TRUE(Range.contains(StartAddr)); 30 EXPECT_TRUE(Range.contains(EndAddr - 1)); 31 EXPECT_FALSE(Range.contains(EndAddr)); 32 EXPECT_FALSE(Range.contains(UINT64_MAX)); 33 34 const AddressRange RangeSame(StartAddr, EndAddr); 35 const AddressRange RangeDifferentStart(StartAddr + 1, EndAddr); 36 const AddressRange RangeDifferentEnd(StartAddr, EndAddr + 1); 37 const AddressRange RangeDifferentStartEnd(StartAddr + 1, EndAddr + 1); 38 // Test == and != with values that are the same 39 EXPECT_EQ(Range, RangeSame); 40 EXPECT_FALSE(Range != RangeSame); 41 // Test == and != with values that are the different 42 EXPECT_NE(Range, RangeDifferentStart); 43 EXPECT_NE(Range, RangeDifferentEnd); 44 EXPECT_NE(Range, RangeDifferentStartEnd); 45 EXPECT_FALSE(Range == RangeDifferentStart); 46 EXPECT_FALSE(Range == RangeDifferentEnd); 47 EXPECT_FALSE(Range == RangeDifferentStartEnd); 48 49 // Test "bool operator<(const AddressRange &, const AddressRange &)". 50 EXPECT_FALSE(Range < RangeSame); 51 EXPECT_FALSE(RangeSame < Range); 52 EXPECT_LT(Range, RangeDifferentStart); 53 EXPECT_LT(Range, RangeDifferentEnd); 54 EXPECT_LT(Range, RangeDifferentStartEnd); 55 // Test "bool operator<(const AddressRange &, uint64_t)" 56 EXPECT_LT(Range.start(), StartAddr + 1); 57 // Test "bool operator<(uint64_t, const AddressRange &)" 58 EXPECT_LT(StartAddr - 1, Range.start()); 59 60 // Verify llvm::AddressRange::isContiguousWith() and 61 // llvm::AddressRange::intersects(). 62 const AddressRange EndsBeforeRangeStart(0, StartAddr - 1); 63 const AddressRange EndsAtRangeStart(0, StartAddr); 64 const AddressRange OverlapsRangeStart(StartAddr - 1, StartAddr + 1); 65 const AddressRange InsideRange(StartAddr + 1, EndAddr - 1); 66 const AddressRange OverlapsRangeEnd(EndAddr - 1, EndAddr + 1); 67 const AddressRange StartsAtRangeEnd(EndAddr, EndAddr + 0x100); 68 const AddressRange StartsAfterRangeEnd(EndAddr + 1, EndAddr + 0x100); 69 70 EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart)); 71 EXPECT_FALSE(Range.intersects(EndsAtRangeStart)); 72 EXPECT_TRUE(Range.intersects(OverlapsRangeStart)); 73 EXPECT_TRUE(Range.intersects(InsideRange)); 74 EXPECT_TRUE(Range.intersects(OverlapsRangeEnd)); 75 EXPECT_FALSE(Range.intersects(StartsAtRangeEnd)); 76 EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd)); 77 78 // Test the functions that maintain address ranges: 79 // "bool AddressRange::contains(uint64_t Addr) const;" 80 // "void AddressRanges::insert(const AddressRange &R);" 81 AddressRanges Ranges; 82 Ranges.insert(AddressRange(0x1000, 0x2000)); 83 Ranges.insert(AddressRange(0x2000, 0x3000)); 84 Ranges.insert(AddressRange(0x4000, 0x5000)); 85 86 EXPECT_FALSE(Ranges.contains(0)); 87 EXPECT_FALSE(Ranges.contains(0x1000 - 1)); 88 EXPECT_TRUE(Ranges.contains(0x1000)); 89 EXPECT_TRUE(Ranges.contains(0x2000)); 90 EXPECT_TRUE(Ranges.contains(0x4000)); 91 EXPECT_TRUE(Ranges.contains(0x2000 - 1)); 92 EXPECT_TRUE(Ranges.contains(0x3000 - 1)); 93 EXPECT_FALSE(Ranges.contains(0x3000 + 1)); 94 EXPECT_TRUE(Ranges.contains(0x5000 - 1)); 95 EXPECT_FALSE(Ranges.contains(0x5000 + 1)); 96 EXPECT_FALSE(Ranges.contains(UINT64_MAX)); 97 98 EXPECT_FALSE(Ranges.contains(AddressRange())); 99 EXPECT_FALSE(Ranges.contains(AddressRange(0x1000 - 1, 0x1000))); 100 EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x1000))); 101 EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x1000 + 1))); 102 EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000))); 103 EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x2001))); 104 EXPECT_TRUE(Ranges.contains(AddressRange(0x2000, 0x3000))); 105 EXPECT_FALSE(Ranges.contains(AddressRange(0x2000, 0x3001))); 106 EXPECT_FALSE(Ranges.contains(AddressRange(0x3000, 0x3001))); 107 EXPECT_FALSE(Ranges.contains(AddressRange(0x1500, 0x4500))); 108 EXPECT_FALSE(Ranges.contains(AddressRange(0x5000, 0x5001))); 109 110 // Verify that intersecting ranges get combined 111 Ranges.clear(); 112 Ranges.insert(AddressRange(0x1100, 0x1F00)); 113 // Verify a wholy contained range that is added doesn't do anything. 114 Ranges.insert(AddressRange(0x1500, 0x1F00)); 115 EXPECT_EQ(Ranges.size(), 1u); 116 EXPECT_EQ(Ranges[0], AddressRange(0x1100, 0x1F00)); 117 118 // Verify a range that starts before and intersects gets combined. 119 Ranges.insert(AddressRange(0x1000, Ranges[0].start() + 1)); 120 EXPECT_EQ(Ranges.size(), 1u); 121 EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x1F00)); 122 123 // Verify a range that starts inside and extends ranges gets combined. 124 Ranges.insert(AddressRange(Ranges[0].end() - 1, 0x2000)); 125 EXPECT_EQ(Ranges.size(), 1u); 126 EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000)); 127 128 // Verify that adjacent ranges don't get combined 129 Ranges.insert(AddressRange(0x2000, 0x3000)); 130 EXPECT_EQ(Ranges.size(), 2u); 131 EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000)); 132 EXPECT_EQ(Ranges[1], AddressRange(0x2000, 0x3000)); 133 // Verify if we add an address range that intersects two ranges 134 // that they get combined 135 Ranges.insert(AddressRange(Ranges[0].end() - 1, Ranges[1].start() + 1)); 136 EXPECT_EQ(Ranges.size(), 1u); 137 EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x3000)); 138 139 Ranges.insert(AddressRange(0x3000, 0x4000)); 140 Ranges.insert(AddressRange(0x4000, 0x5000)); 141 Ranges.insert(AddressRange(0x2000, 0x4500)); 142 EXPECT_EQ(Ranges.size(), 1u); 143 EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000)); 144 } 145