Fix DWARFContext::getCompileUnitForOffset().

[friss]

Summary

The header comment for this funtction states that it is usable to find the
CompileUnit containing a given offset, but right now it only works for exact
start offsets of the Units.

To generalize it to any offset, change the comparator function to compare
against the Unit->getNextUnitOffset() and change the search function from
lower_bound to upper_bound. This way, the returned unit is the first one
where Unit->getNextUnitOffset() is strictly greater than the searched offset
which is exactly what we want.

Further patches will use this generalized function to lookup cross-unit
references, and test coverage for this fix will then come naturally through
the tests for that new functionality.

[samsonov]

lib/DebugInfo/DWARFContext.cpp

415 ↗

(On Diff #13452)

You still need to check that Offset you're looking for is inside the CU.

[friss]

Rebased the fix on trunk where the search code is now located in the DWARFUnitSection class.

[samsonov]

lib/DebugInfo/DWARFUnit.h

61

You still need to check that Offset you're looking for is inside the CU.

[friss]

lib/DebugInfo/DWARFContext.cpp

415 ↗

(On Diff #13452)

I don't think so as units in a section are necessarily contiguous. The range of acceptable offsets goes from 0 inclusive to lastUnit->getNextUnitOffset() exclusive. And upper_bound will rightly return CUs.end() if we pass an offset >= the last admissible one.

lib/DebugInfo/DWARFUnit.h

61

I might be wrong, but as I answered last time you told me that, I think this is not true. The admissible offsets go from 0 to lastUnit->getNextUnitOffset() exclusive. There is no hole in the section.

[samsonov]

LGTM

lib/DebugInfo/DWARFUnit.h

61

Sorry, I've received both answers at the same time (probably, your first comment was saved as draft but not submitted).

You are right - there are no holes. Please add a comment about it and feel free to submit this.

[friss]

lib/DebugInfo/DWARFUnit.h

61

Thanks! And sorry, I should have checked that the old review reply got sent out.
David are you also OK with this? I gathered that maybe you wanted to look more into the implications of this.

[dblaikie]

lib/DebugInfo/DWARFUnit.h

61

Thanks for looping back around/checking.

I'm still unclear on a few things here:

Do we need all 3 comparison operations? (if we only need one, I won't have to think so hard about the others - if we only need one, which I think we do (specifically the "(unique_ptr<Unit>, unsigned offset)")) - if we don't, please just delete the two unneeded ones in a preliminary cleanup patch to simplify this one.

getNextUnitOffset < Offset seems... OK, thinking about it I see that it makes sense. I'm not sure if a comment would be helpful to explain why (I can't think of a simple comment that really helps).

Looks fine to me with the optional preliminary cleanup mentioned above.

(we should be able to use code coverage to see that the other two comparison functions are never executed... someone maintains a code coverage website for LLVM but I forget the URL)

[dblaikie]

lib/DebugInfo/DWARFUnit.h

61

(further comment - if those other two comparisons are required, I think they may be incorrect, specifically I think the RHS should be getOffset in (1) and (3), not "getNextUnitOffset") - I can explain more if it turns out these are going to remain in the code, if they're being deleted then there's no need to discuss them)

[friss]

lib/DebugInfo/DWARFUnit.h

61

I don't think we need the 3, but it depends on the point of view, and I can't seem to find a definitive reference on the subject.

The documentation I found states that the functor needs to be convertible to a conversion between the value and the collection contents (the direction of the comparison varies between lower_/upper_bound). I tested with libcxx by only providing a simple function, and it works.
I also read that the parameter should adhere to the Compare concept. This means among other things that comp(a,a) must return false. With a simple function comparing an offset and a Unit, comp(a,a) is simply illegal.

I'm quite sure that no implementation would use anything else that a simple comparison function, but this doesn't mean it is right.

[dblaikie]

lib/DebugInfo/DWARFUnit.h

61

Since we're already relying on heterogenous comparisons here, I think it's safe to remove the other two.

As for language lawyering - it looks like the changes proposed here: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#270 were applied to C++11, where the final wording says:

"The elements e of [first,last) shall be partitioned with respect to the expression ... comp(e, value)."

[friss]

Remove unneeded methods in the comparison functor.

[dblaikie]

lib/DebugInfo/DWARFUnit.h

50

I'm rather surprised if this is the one function that's required. According to the spec, it looks like the specified value is passed as the RHS, not the LHS...

[friss]

lib/DebugInfo/DWARFUnit.h

50

Note I'm using upper_bound bellow. The link you provided says:
Change 25.3.3.2 [lib.upper.bound] paragraph 1 from:
-1- Requires: Type T is LessThanComparable (lib.lessthancomparable).
to:
-1- Requires: The elements e of [first, last) are partitioned with respect to the expression !(value < e) or !comp(value, e)

So value is on the LHS and the element at the RHS.

[dblaikie]

lib/DebugInfo/DWARFUnit.h

50

Oh, right - thanks for the explanation.

In that case, could we write this comparison as "LHS < RHS->getOffset()". That would be the real less-than comparison of the offset.

But then I suppose you'd have to switch around to lower_bound? Would there be a problem with that?

Sorry I'm being rather confused by all this...

It's just given the definition of upper_bound, it's sort of weird to give a less than comparison that's subtly different (doesn't actually compare !< for the same unit) and then access the element returned - when the element should be one /past/ the equal elements you're looking for... except for the subtle comparison which ends up doing what you want.

So I suppose what I'm trying to suggest is:

operator()(unique_ptr LHS, unsigned RHS)
  return LHS->getNextUnitOffset() <= RHS; // this is actually a "less than" comparison, because "next unit offset" is past the end of this unit, this could alternatively be written as "getNextUnitOffset() - 1 < RHS"
}
...
auto I = lower_bound... 
...

[friss]

lib/DebugInfo/DWARFUnit.h

50

For me 2 solutions work:

• upper_bound with Offset < RHS->getNextUnitOffset()
• lower_bound with LHS->getNextUnitOffset() <= Offset

upper_bound returns the first element comparing greater than Offset, thus the first Unit where the getNextUnitOffset is strictly greater than Offset. I find this definition quite logical.

lower_bound returns the first element 'not less than', i.e. the first element where the comparator returns false. Which is strictly equivalent, but IMHO not less than applied to the non-strict comparison requires a bit more thinking.

But I guess which one seems more logical depends on the mental model you have for both functions. I managed to convince myself that both are equivalent (I hope all this back and forth didn't confuse my logic :-) ), thus I really don't mind the version that gets committed.

[samsonov]

lib/DebugInfo/DWARFUnit.h

50

FWIW I'm perfectly fine with the current implementation.

[friss]

Closed by commit rL218040 (authored by @friss).

lib/DebugInfo/DWARFUnit.h

 };
 
 /// Concrete instance of DWARFUnitSection, specialized for one Unit type.
 template<typename UnitType>
 class DWARFUnitSection final : public SmallVector<std::unique_ptr<UnitType>, 1>,
                                public DWARFUnitSectionBase {
 
   struct UnitOffsetComparator {
-    bool operator()(const std::unique_ptr<UnitType> &LHS,
-                    const std::unique_ptr<UnitType> &RHS) const {
-      return LHS->getOffset() < RHS->getOffset();
-    }
-    bool operator()(const std::unique_ptr<UnitType> &LHS,
-                    uint32_t RHS) const {
-      return LHS->getOffset() < RHS;
-    }
     bool operator()(uint32_t LHS,
                     const std::unique_ptr<UnitType> &RHS) const {
-      return LHS < RHS->getOffset();
+      return LHS < RHS->getNextUnitOffset();
     }
   };
 
 public:
   typedef llvm::SmallVectorImpl<std::unique_ptr<UnitType>> UnitVector;
   typedef typename UnitVector::iterator iterator;
   typedef llvm::iterator_range<typename UnitVector::iterator> iterator_range;
 
   UnitType *getUnitForOffset(uint32_t Offset) const {
-    auto *CU = std::lower_bound(this->begin(), this->end(), Offset,
+    auto *CU = std::upper_bound(this->begin(), this->end(), Offset,
                                 UnitOffsetComparator());
     if (CU != this->end())
       return CU->get();
     return nullptr;
   }
 };
 
 class DWARFUnit {