[boost] A tale of concept checks, multi_array and iterator_facade

From: David Abrahams (dave_at_[hidden])
Date: 2003-11-21 17:33:46

I think this might be an interesting development story.

I just got through updating multi_array to use the new
iterator_facade, and was getting errors in the concept checks with
gcc.  The error was in:

  template <typename OPtr>
  const_multi_array_ref(
      const detail::multi_array::const_sub_array<T,NumDims,OPtr>& rhs
  )
  : base_(rhs.base_)
          ^^^^^^^^^

Where rhs.base_ was int const* and base_ was an int*.

Eventually I discovered that the problem was that GCC tries to
instantiate the body of converting constructors, if they're available,
when it evaluates is_convertible.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13156 shows a simple
example of this nastiness.  Evaluating

      is_convertible<reference,value_type>

is part of the logic for choosing an old-style iterator category for
new-style iterators.  In this case, the value_type of the iterator was
some multi_array<...>, and the reference type was some
const_sub_array<...>.  There happen to be several layers of
inheritance between multi_array and const_sub_array.

So, I figured I could use enable_if_convertible on the types of base_
and rhs.base_ to simply eliminate the constructor if instantiating it
would cause an error.  All well and good, it seemed to work, but then
of course there were several layers of inheritance being used from
const_multi_array_ref, and I needed to propagate the enable_if
conditions all the way up to multi_array so that, e.g. when the
multi_array converting constructor was greedily instantiated by GCC,
its base class' constructor was missing.

When I had disabled all the "false" converting constructors, I found I
had another problem: std::copy was trying to use tag dispatching on
the iterator_category of some multi_array iterators describing its
source range, and neither of the overloaded implementation functions
was matching: one expected std::random_access_iterator_tag and the
other expected std::input_iterator_tag.

A little more investigation showed me that iterator_facade was
choosing std::output_iterator_tag as the old category; in other words,
the is_convertible<...> test shown above was returning false!

I decided to pass a class derived from std::input_iterator_tag and
std::random_access_traversal_tag to iterator_facade, to force the
std::copy dispatching to work.  It worked, but that was unsatisfying.
Something was wrong if a multi_array iterator wasn't detectably
readable.

In hindsight that shouldn't be too surprising: I just got finished
disabling lots of "false" converting constructors.  Unfortunately I
spent most of the day dickering about with the code until I realized
that what was actually wrong was the initialization I pointed out with
^^^^^^^ in the beginning.  The multi_array (derived class) constructor
just goes on to overwrite the base_ pointer.

I went back and ripped out all the extra enable_if_convertible stuff
I'd added, and looked into multi_array's concept checking code.  Why
wasn't it already failing on _all_ compilers?  Turns out it had *no*
checks for iterator concepts - it just looked to see if the MultiArray
type had nested iterator and const_iterator.  I added the appropriate
concept checks from the iterator concept library and recompiled, and
it pointed me at the error right away, with any compiler.  This time,
though, it wasn't deep inside some bit of metaprogramming in the
iterator_facade implementation.

I haven't used the concept checking library before, but guess I'm now
impressed.  If I had tried to expand the MultiArray concept checking
right away I'd have been done with this ordeal so much sooner.  I
think there are probably other lessons to learn here, but right now
I don't see 'em.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com