Index: include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h +++ include/llvm/DebugInfo/DWARF/DWARFDebugRangeList.h @@ -22,9 +22,46 @@ class raw_ostream; +typedef std::pair DWARFRange; + +/// Returns true if [LHS.first, LHS.second) intersects with +/// [RHS.first, RHS.second). +inline bool DWARFRangesIntersect(const DWARFRange &LHS, const DWARFRange &RHS) { + if (LHS.first == LHS.second || RHS.first == RHS.second) + return false; // Empty ranges can't intersect. + return (LHS.first < RHS.second) && (LHS.second > RHS.first); +} + +/// Returns true if [LHS.first, LHS.second) contains [RHS.first, RHS.second). +inline bool DWARFRangeContains(const DWARFRange &LHS, const DWARFRange &RHS) { + if (LHS.first <= RHS.first && RHS.first < LHS.second) + return LHS.first < RHS.second && RHS.second <= LHS.second; + return false; +} + /// DWARFAddressRangesVector - represents a set of absolute address ranges. -typedef std::vector> DWARFAddressRangesVector; +typedef std::vector DWARFAddressRangesVector; +/// Returns true if any ranges in LHS intersect with any ranges of RHS. +inline bool AnyDWARFRangesIntersect(const DWARFAddressRangesVector &LHS, + const DWARFAddressRangesVector &RHS) { + for (const auto &R : LHS) + for (const auto &L : RHS) + if (DWARFRangesIntersect(R, L)) + return true; + return false; +} + +/// Returns true LHS contains all ranges in RHS. +inline bool DWARFRangesContains(const DWARFAddressRangesVector &LHS, + const DWARFAddressRangesVector &RHS) { + for (const auto &L : LHS) + for (const auto &R : RHS) + if (!DWARFRangeContains(L, R)) + return false; + return true; +} + class DWARFDebugRangeList { public: struct RangeListEntry { Index: include/llvm/DebugInfo/DWARF/DWARFVerifier.h =================================================================== --- include/llvm/DebugInfo/DWARF/DWARFVerifier.h +++ include/llvm/DebugInfo/DWARF/DWARFVerifier.h @@ -10,9 +10,13 @@ #ifndef LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H #define LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H +#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h" +#include "llvm/DebugInfo/DWARF/DWARFDie.h" + #include #include #include +#include namespace llvm { class raw_ostream; @@ -23,15 +27,63 @@ /// A class that verifies DWARF debug information given a DWARF Context. class DWARFVerifier { + struct DieRangeInfo { + DWARFDie Die; + DWARFAddressRangesVector Ranges; + + DieRangeInfo() : Die(), Ranges() {} + DieRangeInfo(DWARFDie D, const DWARFAddressRangesVector &R); + /// Return true if this object contains all ranges within RHS. + bool Contains(const DieRangeInfo &RHS) const; + bool DoesIntersect(const DieRangeInfo &RHS) const; + void Dump(raw_ostream &OS) const; + bool operator<(const DieRangeInfo &RHS) const; + /// Return true if there are errors in the ranges R. + bool SortAndCheckRangesHasErrors(raw_ostream &OS); + }; + + struct NonOverlappingRanges { + std::set NonOverlappingRanges; + + /// Returns true if the sibling ranges + const DieRangeInfo *GetOverlappingRangeInfo(const DieRangeInfo &RI) const; + }; + raw_ostream &OS; DWARFContext &DCtx; + DieRangeInfo UnitRI; + NonOverlappingRanges AllFunctionRanges; + /// A map that tracks all references (converted absolute references) so we /// can verify each reference points to a valid DIE and not an offset that /// lies between to valid DIEs. std::map> ReferenceToDIEOffsets; + uint32_t NumDebugInfoErrors; uint32_t NumDebugLineErrors; + /// Verifies the a DIE's tag and gathers information about all DIEs. + /// + /// This function currently checks for: + /// - Checks DW_TAG_compile_unit address range(s) + /// - Checks DW_TAG_subprogram address range(s) and if the compile unit + /// has ranges, verifies that its address range is fully contained in + /// the compile unit ranges. Also adds the functions address range info + /// to AllFunctionDieRangeInfos to look for functions with overlapping + /// ranges after all DIEs have been processed. + /// - Checks that DW_TAG_lexical_block and DW_TAG_inlined_subroutine DIEs + /// have address range(s) that are fully contained in their parent DIEs + /// address range(s). + /// + /// \param Die The DWARF DIE to check + /// \param ParantRI The parent DIE's range information + /// \param NOR The parent DIE's list of ranges that can't overlap. + void verifyDie(const DWARFDie &Die, const DieRangeInfo &ParentRI, + NonOverlappingRanges &NOR); + + /// Verify that no DIE ranges overlap. + void verifyNoRangesOverlap(const std::set &DieRangeInfos); + /// Verifies the attribute's DWARF attribute and its value. /// /// This function currently checks for: Index: lib/DebugInfo/DWARF/DWARFVerifier.cpp =================================================================== --- lib/DebugInfo/DWARF/DWARFVerifier.cpp +++ lib/DebugInfo/DWARF/DWARFVerifier.cpp @@ -23,6 +23,199 @@ using namespace dwarf; using namespace object; +bool DWARFVerifier::DieRangeInfo::SortAndCheckRangesHasErrors(raw_ostream &OS) { + bool HasErrors = false; + size_t I = 0; + while (I < Ranges.size()) { + if (Ranges[I].first >= Ranges[I].second) { + if (Ranges[I].first > Ranges[I].second) { + if (!HasErrors) { + HasErrors = true; + OS << "error: invalid range in DIE:\n"; + } + } + // Remove empty or invalid ranges. + Ranges.erase(Ranges.begin() + I); + continue; + } else { + ++I; // Only increment if we didn't remove the range. + } + } + std::sort(Ranges.begin(), Ranges.end()); + return HasErrors; +} + +void DWARFVerifier::DieRangeInfo::Dump(raw_ostream &OS) const { + OS << format("0x%08" PRIx32, Die.getOffset()) << ":"; + for (const auto &R : Ranges) + OS << " [" << format("0x%" PRIx32, R.first) << "-" + << format("0x%" PRIx32, R.second) << ")"; + OS << "\n"; +} + +void DWARFVerifier::verifyNoRangesOverlap( + const std::set &DieRangeInfos) { + auto End = DieRangeInfos.end(); + auto Prev = End; + for (auto Curr = DieRangeInfos.begin(); Curr != End; ++Curr) { + if (Prev != End) { + if (Prev->DoesIntersect(*Curr)) { + ++NumDebugInfoErrors; + OS << "error: DIEs have overlapping address ranges:\n"; + Prev->Die.dump(OS, 0); + Curr->Die.dump(OS, 0); + OS << "\n"; + } + } + Prev = Curr; + } +} + +bool DWARFVerifier::DieRangeInfo::Contains(const DieRangeInfo &RHS) const { + return DWARFRangesContains(Ranges, RHS.Ranges); +} + +bool DWARFVerifier::DieRangeInfo::DoesIntersect(const DieRangeInfo &RHS) const { + return AnyDWARFRangesIntersect(Ranges, RHS.Ranges); +} + +bool DWARFVerifier::DieRangeInfo::operator<(const DieRangeInfo &RHS) const { + if (Ranges.empty()) { + if (RHS.Ranges.empty()) + return Die.getOffset() < RHS.Die.getOffset(); + return true; + } + if (RHS.Ranges.empty()) + return false; + size_t LeftSize = Ranges.size(); + size_t RightSize = RHS.Ranges.size(); + for (size_t I = 0; I < LeftSize; ++I) { + if (I >= RightSize) + return false; + if (Ranges[I].first != RHS.Ranges[I].first) + return Ranges[I].first < RHS.Ranges[I].first; + if (Ranges[I].second != RHS.Ranges[I].second) + return Ranges[I].second < RHS.Ranges[I].second; + } + return false; +} + +const DWARFVerifier::DieRangeInfo * +DWARFVerifier::NonOverlappingRanges::GetOverlappingRangeInfo( + const DieRangeInfo &RI) const { + if (!NonOverlappingRanges.empty()) { + auto Iter = NonOverlappingRanges.lower_bound(RI); + if (Iter != NonOverlappingRanges.end()) { + if (AnyDWARFRangesIntersect(Iter->Ranges, RI.Ranges)) + return &*Iter; + } + if (Iter != NonOverlappingRanges.begin()) { + --Iter; + if (AnyDWARFRangesIntersect(Iter->Ranges, RI.Ranges)) + return &*Iter; + } + } + return nullptr; +} +void DWARFVerifier::verifyDie(const DWARFDie &Die, const DieRangeInfo &ParentRI, + NonOverlappingRanges &NOR) { + const auto Tag = Die.getTag(); + + DieRangeInfo RI; + RI.Die = Die; + switch (Tag) { + case DW_TAG_null: + return; + case DW_TAG_compile_unit: { + UnitRI.Die = Die; + UnitRI.Ranges = Die.getAddressRanges(); + if (UnitRI.SortAndCheckRangesHasErrors(OS)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + } break; + case DW_TAG_subprogram: { + RI.Ranges = Die.getAddressRanges(); + if (RI.SortAndCheckRangesHasErrors(OS)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + if (RI.Ranges.empty()) + break; + + // If the compile unit has address ranges, make sure it contains this DIE's + // ranges. + if (!UnitRI.Ranges.empty() && !UnitRI.Contains(RI)) { + ++NumDebugInfoErrors; + OS << "error: CU DIE has child with address ranges " + "that are not contained in its ranges:\n"; + UnitRI.Die.dump(OS, 0); + Die.dump(OS, 0); + OS << "\n"; + } + + // Check if this function's range overlaps with any previous function ranges + // from any compile unit and make an error if needed. + auto OverlappingRI = AllFunctionRanges.GetOverlappingRangeInfo(RI); + if (OverlappingRI) { + ++NumDebugInfoErrors; + OS << "error: DIEs have overlapping address ranges:\n"; + OverlappingRI->Die.dump(OS, 0); + Die.dump(OS, 0); + OS << "\n"; + } + // Add the function to the compile unit's verify info + AllFunctionRanges.NonOverlappingRanges.insert(RI); + + } break; + case DW_TAG_lexical_block: + case DW_TAG_inlined_subroutine: { + RI.Ranges = Die.getAddressRanges(); + if (RI.SortAndCheckRangesHasErrors(OS)) { + ++NumDebugInfoErrors; + Die.dump(OS, 0); + OS << "\n"; + } + if (RI.Ranges.empty()) + break; + // Check to make sure our parent contains all ranges for this Die. + if (!ParentRI.Contains(RI)) { + ++NumDebugInfoErrors; + OS << "error: DIE has a child " << TagString(Tag) + << " DIE whose address ranges that are not contained " + "in its ranges:\n"; + ParentRI.Die.dump(OS, 0); + Die.dump(OS, 0); + } + + // Check if this range overlaps with any previous sibling ranges and make an + // error if needed. + auto OverlappingRI = NOR.GetOverlappingRangeInfo(RI); + if (OverlappingRI) { + ++NumDebugInfoErrors; + OS << "error: DIEs have overlapping address ranges:\n"; + OverlappingRI->Die.dump(OS, 0); + Die.dump(OS, 0); + OS << "\n"; + } + NOR.NonOverlappingRanges.insert(RI); + + } break; + default: + break; + } + // Verify the attributes and forms. + for (auto AttrValue : Die.attributes()) { + verifyDebugInfoAttribute(Die, AttrValue); + verifyDebugInfoForm(Die, AttrValue); + } + + NonOverlappingRanges DieNRO; + for (DWARFDie Child : Die) + verifyDie(Child, RI, DieNRO); +} void DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die, DWARFAttribute &AttrValue) { const auto Attr = AttrValue.Attr; @@ -160,17 +353,9 @@ NumDebugInfoErrors = 0; OS << "Verifying .debug_info...\n"; for (const auto &CU : DCtx.compile_units()) { - unsigned NumDies = CU->getNumDIEs(); - for (unsigned I = 0; I < NumDies; ++I) { - auto Die = CU->getDIEAtIndex(I); - const auto Tag = Die.getTag(); - if (Tag == DW_TAG_null) - continue; - for (auto AttrValue : Die.attributes()) { - verifyDebugInfoAttribute(Die, AttrValue); - verifyDebugInfoForm(Die, AttrValue); - } - } + NonOverlappingRanges NRO; + verifyDie(CU->getUnitDIE(/* ExtractUnitDIEOnly = */ false), DieRangeInfo(), + NRO); } verifyDebugInfoReferences(); return NumDebugInfoErrors == 0; Index: unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp =================================================================== --- unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp +++ unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp @@ -2142,4 +2142,422 @@ "offset:"); } +TEST(DWARFDebugInfo, TestDwarfVerifyCURangesIncomplete) { + // Create a single compile unit with a single function. The compile + // unit has a DW_AT_ranges attribute that doesn't fully contain the + // address range of the function. The verification should fail due to + // the CU ranges not containing all of the address ranges of all of the + // functions. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + debug_abbrev: + - Code: 0x00000001 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 46 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000001500 + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: CU DIE has child with address ranges that " + "are not contained in its ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyLexicalBlockRanges) { + // Create a single compile unit with a single function that has a lexical + // block whose address range is not contained in the function address range. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + debug_abbrev: + - Code: 0x00000001 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Code: 0x00000003 + Tag: DW_TAG_lexical_block + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 52 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000003 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002001 + - AbbrCode: 0x00000000 + Values: + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: DIE has a child DW_TAG_lexical_block DIE " + "whose address ranges that are not contained in " + "its ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingFunctionRanges) { + // Create a single compile unit with a two functions that have overlapping + // address ranges. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + - foo + debug_abbrev: + - Code: 0x00000001 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 55 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000002 + Values: + - Value: 0x0000000000000012 + - Value: 0x0000000000001FFF + - Value: 0x0000000000002000 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: DIEs have overlapping address ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingLexicalBlockRanges) { + // Create a single compile unit with a two functions that have overlapping + // address ranges. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + debug_abbrev: + - Code: 0x00000001 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + - Code: 0x00000003 + Tag: DW_TAG_lexical_block + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 85 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000002000 + - AbbrCode: 0x00000003 + Values: + - Value: 0x0000000000001100 + - Value: 0x0000000000001300 + - AbbrCode: 0x00000003 + Values: + - Value: 0x00000000000012FF + - Value: 0x0000000000001300 + - AbbrCode: 0x00000000 + Values: + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: DIEs have overlapping address ranges:"); +} + +TEST(DWARFDebugInfo, TestDwarfVerifyInvalidDIERange) { + // Create a single compile unit with a single function that has an invalid + // address range where the high PC is smaller than the low PC. + StringRef yamldata = R"( + debug_str: + - '' + - /tmp/main.c + - main + debug_abbrev: + - Code: 0x00000001 + Tag: DW_TAG_compile_unit + Children: DW_CHILDREN_yes + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Code: 0x00000002 + Tag: DW_TAG_subprogram + Children: DW_CHILDREN_no + Attributes: + - Attribute: DW_AT_name + Form: DW_FORM_strp + - Attribute: DW_AT_low_pc + Form: DW_FORM_addr + - Attribute: DW_AT_high_pc + Form: DW_FORM_addr + debug_info: + - Length: + TotalLength: 34 + Version: 4 + AbbrOffset: 0 + AddrSize: 8 + Entries: + - AbbrCode: 0x00000001 + Values: + - Value: 0x0000000000000001 + - AbbrCode: 0x00000002 + Values: + - Value: 0x000000000000000D + - Value: 0x0000000000001000 + - Value: 0x0000000000000900 + - AbbrCode: 0x00000000 + Values: + )"; + auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata); + ASSERT_TRUE((bool)ErrOrSections); + DWARFContextInMemory DwarfContext(*ErrOrSections, 8); + VerifyError(DwarfContext, "error: invalid range in DIE:"); +} + +namespace { + +void AssertRangesIntersect(const DWARFRange &LHS, const DWARFRange &RHS) { + ASSERT_TRUE(DWARFRangesIntersect(LHS, RHS)); + ASSERT_TRUE(DWARFRangesIntersect(RHS, LHS)); +} +void AssertRangesDontIntersect(const DWARFRange &LHS, const DWARFRange &RHS) { + ASSERT_FALSE(DWARFRangesIntersect(LHS, RHS)); + ASSERT_FALSE(DWARFRangesIntersect(RHS, LHS)); +} + +void AssertRangesIntersect(const DWARFAddressRangesVector &LHS, + const DWARFAddressRangesVector &RHS) { + ASSERT_TRUE(AnyDWARFRangesIntersect(LHS, RHS)); + ASSERT_TRUE(AnyDWARFRangesIntersect(RHS, LHS)); +} + +void AssertRangesDontIntersect(const DWARFAddressRangesVector &LHS, + const DWARFAddressRangesVector &RHS) { + ASSERT_FALSE(AnyDWARFRangesIntersect(LHS, RHS)); + ASSERT_FALSE(AnyDWARFRangesIntersect(RHS, LHS)); +} + +} // namespace +TEST(DWARFDebugInfo, TestDwarfRangesIntersect) { + DWARFRange R(0x10, 0x20); + + //---------------------------------------------------------------------- + // Test ranges that start before R... + //---------------------------------------------------------------------- + // Other range ends before start of R + AssertRangesDontIntersect(R, {0x00, 0x10}); + // Other range end address is start of a R + AssertRangesIntersect(R, {0x00, 0x11}); + // Other range end address is in R + AssertRangesIntersect(R, {0x00, 0x15}); + // Other range end address is at and of R + AssertRangesIntersect(R, {0x00, 0x20}); + // Other range end address is past end of R + AssertRangesIntersect(R, {0x00, 0x40}); + + //---------------------------------------------------------------------- + // Test ranges that start at R's start address + //---------------------------------------------------------------------- + // Ensure empty ranges doesn't match + AssertRangesDontIntersect(R, {0x10, 0x10}); + // 1 byte of Range + AssertRangesIntersect(R, {0x10, 0x11}); + // same as Range + AssertRangesIntersect(R, {0x10, 0x20}); + // 1 byte past Range + AssertRangesIntersect(R, {0x10, 0x21}); + + //---------------------------------------------------------------------- + // Test ranges that start inside Range + //---------------------------------------------------------------------- + // empty in range + AssertRangesDontIntersect(R, {0x11, 0x11}); + // all in Range + AssertRangesIntersect(R, {0x11, 0x1f}); + // ends at end of Range + AssertRangesIntersect(R, {0x11, 0x20}); + // ends past Range + AssertRangesIntersect(R, {0x11, 0x21}); + + //---------------------------------------------------------------------- + // Test ranges that start at last bytes of Range + //---------------------------------------------------------------------- + // ends at end of Range + AssertRangesIntersect(R, {0x1f, 0x20}); + // ends past Range + AssertRangesIntersect(R, {0x1f, 0x21}); + + //---------------------------------------------------------------------- + // Test ranges that start after Range + //---------------------------------------------------------------------- + // empty just past in Range + AssertRangesDontIntersect(R, {0x20, 0x20}); + // valid past Range + AssertRangesDontIntersect(R, {0x20, 0x21}); +} + +TEST(DWARFDebugInfo, TestDwarfRangeVectorsIntersect) { + DWARFAddressRangesVector Ranges = {{0x10, 0x20}, {0x30, 0x40}}; + + // Test empty range + AssertRangesDontIntersect(Ranges, {}); + // Test range that appears before all ranges in Ranges + AssertRangesDontIntersect(Ranges, {{0x00, 0x10}}); + // Test range that appears between ranges in Ranges + AssertRangesDontIntersect(Ranges, {{0x20, 0x30}}); + // Test range that appears after ranges in Ranges + AssertRangesDontIntersect(Ranges, {{0x40, 0x50}}); + + // Test range that start before first range + AssertRangesIntersect(Ranges, {{0x00, 0x11}}); + // Test range that start at first range + AssertRangesIntersect(Ranges, {{0x10, 0x11}}); + // Test range that start in first range + AssertRangesIntersect(Ranges, {{0x11, 0x12}}); + // Test range that start at end of first range + AssertRangesIntersect(Ranges, {{0x1f, 0x20}}); + // Test range that starts at end of first range + AssertRangesDontIntersect(Ranges, {{0x20, 0x21}}); + // Test range that starts at end of first range + AssertRangesIntersect(Ranges, {{0x20, 0x31}}); + + // Test range that start before second range and ends before second + AssertRangesDontIntersect(Ranges, {{0x2f, 0x30}}); + // Test range that start before second range and ends in second + AssertRangesIntersect(Ranges, {{0x2f, 0x31}}); + // Test range that start at second range + AssertRangesIntersect(Ranges, {{0x30, 0x31}}); + // Test range that start in second range + AssertRangesIntersect(Ranges, {{0x31, 0x32}}); + // Test range that start at end of second range + AssertRangesIntersect(Ranges, {{0x3f, 0x40}}); + // Test range that starts at end of second range + AssertRangesDontIntersect(Ranges, {{0x40, 0x41}}); +} + } // end anonymous namespace