Closed Bug 1175485 Opened 4 years ago Closed 4 years ago

ReverseIterator contains undefined behavior when used with IntegerRange, EnumeratedRange and nsFrameList

Categories

(Core :: MFBT, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla42
Tracking Status
firefox38 --- affected
firefox38.0.5 --- affected
firefox39 --- affected
firefox40 --- affected
firefox41 --- affected
firefox42 --- fixed

People

(Reporter: xidorn, Assigned: xidorn)

References

Details

Attachments

(4 files, 5 obsolete files)

It seems to me that there are compiler bug in Clang and GCC which mis-optimize code combines Reversed() with MakeRange().

If we have code
> for (auto i : Reversed(MakeRange(n))) {
>   std::cout << i << std::endl;
> }
we expect that it outputs [0, n) reversely.

However, on GCC with -O1 or higher, it outputs n times of 0, and on Clang with -O2 or higher, it outputs a 0 and then (n-1) times of several weird numbers.

Interestingly, if I compile that on Clang with -fsanitize=undefined, the output would be n times of weird numbers. If compile with -fsanitize=integer, the program outputs [1,n] reversely.

What may help is compiling on Clang with -fsanitize=memory. It reports use-of-uninitialized-value error for MakeRange().

If I expand everything explicitly to:
> auto range = MakeRange(n);
> auto iter = range.begin();
> auto end = range.end();
> while (true) {
>   bool done = (iter == end);
>   std::cout << done << std::endl;
>   if (done) {
>     break;
>   }
>   auto i = *iter;
>   std::cout << i << std::endl;
>   ++iter;
> }

The memory sanitizer reports that error on the line "if (done) {", which doesn't make sense at all.
This problem is because that the current impl of ReverseIterator contains an undefined behavior that we returns a reference of a variable in the current stack frame.
Summary: Clang and GCC mis-optimize code combines Reversed() with MakeRange() → ReverseIterator contains undefined behavior when used with IntegerRange and nsFrameList
Assignee: nobody → quanxunzhen
Attachment #8624057 - Flags: review?(roc)
Attachment #8624057 - Flags: review?(jwalden+bmo)
Attachment #8624059 - Flags: review?(jwalden+bmo)
Attachment #8624060 - Flags: review?(jwalden+bmo)
Attachment #8624060 - Attachment is obsolete: true
Attachment #8624060 - Flags: review?(jwalden+bmo)
Attachment #8624112 - Flags: review?(jwalden+bmo)
Errr, EnumeratedRange has the same issue...
Summary: ReverseIterator contains undefined behavior when used with IntegerRange and nsFrameList → ReverseIterator contains undefined behavior when used with IntegerRange, EnumeratedRange and nsFrameList
Attachment #8624057 - Attachment is obsolete: true
Attachment #8624057 - Flags: review?(jwalden+bmo)
Attachment #8624601 - Flags: review?(jwalden+bmo)
Attachment #8624059 - Attachment is obsolete: true
Attachment #8624059 - Flags: review?(jwalden+bmo)
Attachment #8624603 - Flags: review?(jwalden+bmo)
Attachment #8624112 - Attachment is obsolete: true
Attachment #8624112 - Flags: review?(jwalden+bmo)
Attachment #8624604 - Flags: review?(jwalden+bmo)
Comment on attachment 8624601 [details] [diff] [review]
patch 1 - change return type of operator*() of several iterators, r=roc

Review of attachment 8624601 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/EnumeratedRange.h
@@ +24,1 @@
>  #include "mozilla/IntegerTypeTraits.h"

Flip these to preserve alphabetical ordering.

::: mfbt/ReverseIterator.h
@@ +15,2 @@
>  #include "mozilla/Attributes.h"
>  #include "mozilla/IteratorTraits.h"

Alphabetize, again.

@@ +31,5 @@
>    template<typename Iterator>
>    MOZ_IMPLICIT ReverseIterator(const ReverseIterator<Iterator>& aOther)
>      : mCurrent(aOther.mCurrent) { }
>  
> +  auto operator*() const -> decltype(*DeclVal<IteratorT>())

I think you want to uUse this decltype as the type in the ValueType typedef above, right?
Attachment #8624601 - Flags: review?(jwalden+bmo) → review+
Comment on attachment 8624058 [details] [diff] [review]
patch 2 - add static_assert to ensure MakeRange used with integer

Review of attachment 8624058 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/IntegerRange.h
@@ +190,5 @@
>  detail::IntegerRange<IntType2>
>  MakeRange(IntType1 aBegin, IntType2 aEnd)
>  {
> +  static_assert(IsIntegral<IntType1>::value && IsIntegral<IntType2>::value,
> +                "Values must both be integral");

Lowercase "value" and "values" in these, as I believe compilers generally treat the assertion message as a sentence fragment.
Attachment #8624058 - Flags: review?(jwalden+bmo) → review+
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #13)
> Comment on attachment 8624601 [details] [diff] [review]
> patch 1 - change return type of operator*() of several iterators, r=roc
> 
> Review of attachment 8624601 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/EnumeratedRange.h
> @@ +24,1 @@
> >  #include "mozilla/IntegerTypeTraits.h"
> 
> Flip these to preserve alphabetical ordering.
> 
> ::: mfbt/ReverseIterator.h
> @@ +15,2 @@
> >  #include "mozilla/Attributes.h"
> >  #include "mozilla/IteratorTraits.h"
> 
> Alphabetize, again.
> 
> @@ +31,5 @@
> >    template<typename Iterator>
> >    MOZ_IMPLICIT ReverseIterator(const ReverseIterator<Iterator>& aOther)
> >      : mCurrent(aOther.mCurrent) { }
> >  
> > +  auto operator*() const -> decltype(*DeclVal<IteratorT>())
> 
> I think you want to uUse this decltype as the type in the ValueType typedef
> above, right?

No. If we want a typedef for the return value of operator*(), it should be ReferenceType. But I don't think it helps a lot to introduce a new typedef here. Actually, I remove the useless ValueType and DifferenceType in patch 3.
Comment on attachment 8624603 [details] [diff] [review]
patch 3 - remove unused operators and traits

Review of attachment 8624603 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/ReverseIterator.h
@@ -22,5 @@
>  {
>  public:
> -  typedef typename IteratorTraits<IteratorT>::ValueType ValueType;
> -  typedef typename IteratorTraits<IteratorT>::DifferenceType DifferenceType;
> -

Ah, yes, I see you removed these later.

That said, thinking slightly more, is there a reason you have to use auto -> syntax?  Couldn't you just use |decltype(*DeclVal<IteratorT>()) operator*() const| to avoid the extra indirection of auto+trailing return type?
Attachment #8624603 - Flags: review?(jwalden+bmo) → review+
Comment on attachment 8624640 [details] [diff] [review]
patch 4 - unittest for integer range

Review of attachment 8624640 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/tests/TestIntegerRange.cpp
@@ +5,5 @@
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +#include "mozilla/Assertions.h"
> +#include "mozilla/IntegerRange.h"
> +#include <cstdlib>

What are you using from <cstdlib>?  I don't see anything here except size_t and ptrdiff_t, maybe.  But those are in <stddef.h>, and you should use that header to access them.

Also, blank line before the standard-library include.

@@ +7,5 @@
> +#include "mozilla/Assertions.h"
> +#include "mozilla/IntegerRange.h"
> +#include <cstdlib>
> +
> +using namespace mozilla;

Policy is to only |using| specific symbols, not open up the entire namespace.  Break this up:

using mozilla::IsSame;
using mozilla::MakeRange;
using mozilla::Reversed;

I think that's the full list, add others as needed.

@@ +10,5 @@
> +
> +using namespace mozilla;
> +
> +#define MAX_NUMBER 50
> +#define ARRAY_SIZE 256

const size_t for both of htese.
Attachment #8624640 - Flags: review?(jwalden+bmo) → review+
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #16)
> That said, thinking slightly more, is there a reason you have to use auto ->
> syntax?  Couldn't you just use |decltype(*DeclVal<IteratorT>()) operator*()
> const| to avoid the extra indirection of auto+trailing return type?

Yes, if you prefer that style. I thought using auto -> syntax looks more clear, though.
You need to log in before you can comment on or make changes to this bug.