[boost] [proposal] raw move (was: [interest] underlying type library)

Subject: [boost] [proposal] raw move (was: [interest] underlying type library)
From: Julian Gonggrijp (j.gonggrijp_at_[hidden])
Date: 2011-08-23 08:06:55

Dear all,

Hereby I propose the following additions to Boost. I also volunteer to 
(help to) implement these additions.

  I. Default templates for underlying_type_traits and move_raw.
 II. Implementations of the value-permuting STL algorithms, making use 
      of move_raw.
III. Template specializations of underlying_type_traits and move_raw 
      for the STL containers.
 IV. (if deemed necessary) Matching concepts.

Part I. may reside in a Utility header, part II. could be a separate 
library, part III. should probably be an addition to Boost.Containers, 
and part IV. could either be an addition to Boost.ConceptCheck or live 
in the same Utility header as part I.

There is also an interesting option which directly involves 
Boost.Move. I'll discuss this option in more detail under part I. 
below.

Before I discuss each part in more detail, a quick review of the 
rationale for raw move. There are (at least) three possible operations 
for having a target object acquire the value of a source object, here 
presented from the strongest semantics to the weakest:

- Copy assignment: the source is guaranteed to be left unchanged.
- Move assignment: the source is guaranteed to be left in a valid 
   state.
- Raw move: nothing is guaranteed about the source, except that it 
   will be valid again when another value has been raw moved into it.

Because of the progressively weaker semantics these operations also 
have an increasing potential for efficiency.

Since raw move may leave objects in an invalid state, in general a 
chain of raw moves has to begin and end with a POD object. The 
underlying type of T is hence defined as the POD that can store and 
restore the state of T instances through raw moves.

PART I.
I think the default templates header should look like this:

template <class T>
struct underlying_type_traits {
    typedef T type;
};

#define UNDERLYING_TYPE(T) underlying_type_traits< T >::type

template <class T>
void move_raw (T& source, T& target) {
    target = source;
}

template <class T>
void move_raw (T& source, typename UNDERLYING_TYPE(T)& target) {
    target = source;
}

template <class T>
void move_raw (typename UNDERLYING_TYPE(T)& source, T& target) {
    target = source;
}

// Not shown: partial specializations for arrays, like in Boost.Swap.
// Possible refinement: partial specializations that disable 
// compilation for const types.

There are many good reasons to default to type identity and copy 
assignment:

1. it is optimal for PODs;
2. it works and is safe for copyable non-PODs;
3. from 1. and 2.: the algorithms from part II. are automatically 
    guaranteed to work for all types that can currently use the copy-
    based counterparts from the STL;
4. on top of 3., all algorithms from part II. are guaranteed to be 
    always at least as efficient as their copy-based counterparts;
5. from 3. and 4.: raw_move::swap can directly replace std::swap as 
    the default fallback for Boost.Swap, without drawbacks;
6. there is nothing to discourage programmers from implementing new 
    algorithms with raw moves, since they'll get the copy-based 
    variant of their algorithm for free;
7. from 2: authors of non-POD types are motivated but not required to 
    provide template specializations.

The interesting alternative is to use Boost.Move's move assignment as 
the default implementation for move_raw. This would further improve 
some of the benefits mentioned above. There are however some concerns 
that need to be clarified before we can make a choice:

- Can a raw move framework that uses Boost.Move as a backbone be as 
   general as the copy-based variant? Most likely, this is true if and 
   only if Boost.Move provides copying as a fallback for types that 
   are not move-aware.
- What about exception safety?
- What other potential obstacles are there?

PART II.
The following algorithms from the STL should be re-implemented with 
raw moves:

swap, iter_swap, swap_ranges, reverse, rotate, random_shuffle, 
partition, stable_partition, sort, stable_sort, partial_sort, 
inplace_merge, push_heap, pop_heap, make_heap, sort_heap, 
next_permutation, prev_permutation.

Of course, new algorithms can be provided as well. An example: 
move_raw_ranges, the raw counterpart of std::copy.

PART III.
Ideally move_raw and the underlying type should be specialized for 
every STL container. This requires knowledge of the implementation 
details, as well as the addition of matching friend declarations in 
each container class template. In other words, it can only be done 
with STL containers that are shipped with Boost.

Boost.Containers seems to be the ideal substrate, since one of its 
aims is to provide 'new advanced features'. It is also the only 
option, as it seems like a no-go to provide two alternative 
implementations of the STL containers. More opinions on this matter 
would be much appreciated.

PART IV.
I'm completely open to the question of what should be done with regard 
to raw move-related concepts. It might also partially depend on 
whether copy or move assignment is used as the default implementation 
for move_raw.

There is however an observation that I want to share: the (abstract) 
set of raw-movable types coincides exactly with the set of 'normally-
movable' types. That is, if it makes sense for type T to have move 
assignment then it also makes sense to have raw_move, and if it 
doesn't make sense for T to have move assignment then move_raw also 
doesn't make sense.

In other words, although the use cases for move assignment and raw 
move are not the same, their requirements on the type are the same in 
principle. Fitness of a particular type for usage with move_raw should 
therefore ideally be tested using the same concept check as its 
fitness for usage with move assignment (this is probably also an 
argument in favour of using move assignment as the default backbone).

I look forward to your feedback. :-)

-Julian