Document number: N4426
Date: 2015-04-10
Author: Daniel Krügler
Project: Programming Language C++, Library Working Group
Reply-to: Daniel Krügler

Adding [nothrow-]swappable traits

Discussion

This proposal suggests to add a new type trait std::is_nothrow_swappable<T> to the header <type_traits>. In addition to that this paper provides an extended resolution that proposes to also add the std::is_swappable<T>, std::is_swappable_with<T, U>, and std::is_nothrow_swappable_with<T, U> traits to the header <type_traits>. Finally a third even more extended resolution is presented that suggests to specify the two swap templates from header <utility> as constrained templates.

Related papers are the following ones:

Introduction

This paper attempts to resolve the existing library issue LWG 2456 involving broken noexcept-specifications of several member swap functions of a number of library components. It also has the objective to ensure that such an addition should be as consistent as possible in regard to existing type traits.

LWG 2456 points out that many conditional noexcept-specifications of member-swap functions in the library specification are invalid according to the language rules. As an example consider the class template synopsis of std::array:

template <class T, size_t N>
struct array 
{
  […]
  void swap(array&) noexcept(noexcept(swap(declval<T&>(), declval<T&>())));
  […]
};

This exception-specification is ill-formed, because we have an unqualified swap expression with two arguments occurring within a class-scope that has a member swap with one argument, therefore the member swap will be found and as consequence the tested expression can never by found to be valid.

With acceptance of CWG 1330 late parsing of exception-specifications had been introduced, so from this point on, a diagnostic is required in this situation, therefore even a previously possible way to rely on undefined behaviour is no longer possible (and surely never had been a good foundation for a specification).

Design Rationale

Assuming we had a suitably defined type trait is_nothrow_swappable, the above presented specification of std::array's member swap exception-specification could now be fixed by replacing it by the following form:

template <class T, size_t N>
struct array 
{
  […]
  void swap(array&) noexcept(is_nothrow_swappable<T>::value);
  […]
};

This approach would then be similar to other fundamental expression-constraints for copy/move constructions or copy/move assignments.

How many swap-related traits should be provided by the Standard Library?

The minimum number is determined by the goal to fix all Library exception-specifications that are affected by above kind of problem. It turns out that all current swap functions in the library that have a conditional noexcept specifier do only involve swapping of lvalues on objects the same type T. That means the Library should at least specify the type trait

template <class T> struct is_nothrow_swappable;

suitable to inspect lvalue swap operations. Currently the library does not define constrained templates that are constrained in terms of valid swap expression (only in combination with noexcept specifiers), therefore the corresponding is_swappable trait is technically not required to solve the aforementioned issue. This lower bound leads us to the minimalistic resolution discussed in this paper.

The maximum number of swappable-traits is determined by the variety of swappable expressions that are categorized by the library. The Library supports both homogeneous and heterogeneous Swappable requirements as provided by the paper N3048 ("Defining Swappable Requirements"). The most general swappable with requirement allows to describe mixed-type swaps and also swap-operations that (partially) involve rvalues. Some algorithms (such as swap_ranges and iter_swap) depend on this more general swappable with requirement. Those mixed-type swaps are relevant, for example, if a regular type (such as bool) is modeled by a proxy type, like the member types std::bitset::reference or vector<bool>::reference. Except for such special cases, the majority of swap expressions in the library (and in the wild) is restricted to lvalues of the same type.

Therefore the extended resolution in this paper suggests to provide the following two type-traits

template <class T, class U> struct is_swappable_with;
template <class T> struct is_swappable;

This pair of traits follows the tradition of N3048 to associate these traits to corresponding expression-based requirements from 17.6.3.2 [swappable.requirements] and to the corresponding swappable concepts from earlier working papers such as N2914:

  1. HasSwap<T, U> ⇔ "std::declval<T>() is swappable with std::declval<U>()" ⇔ is_swappable_with<T, U>::value

  2. Swappable<T> ⇔ "Lvalues of T are swappable" ⇔ is_swappable<T>::value

For expression-based traits like for operations, that are often used in exception-critical code parts, the Library generally distinguishes a trait that describes the well-formedness of an expression (is_X) and in additional to that one that determines whether the very same expression is known not to throw any exceptions (is_nothrow_X). The latter are relevant for the fixes involving noexcept-specifications within classes and this leads us to the two remaining traits proposed in the extended resolution of this paper:

template <class T, class U> struct is_nothrow_swappable_with;
template <class T> struct is_nothrow_swappable;

An earlier proposal tried to reduce the number of traits by taking advantage of default template arguments:

template <class T, class U = T> struct is_swappable;
template <class T, class U = T> struct is_nothrow_swappable;

Albeit this reduction of declarations looks attractive on the first sight, it is unfortunately easy to use them incorrectly, because evaluating std::is_swappable<T> does not test whether two lvalues of type T can be swapped, instead it tests whether two rvalues of type T can be swapped — an information that is usually not of interest to the programmer. The gotcha effect of this can also be found in this section of N3619, where

static_assert(!is_swappable<X>::value_type);

should better be written as

static_assert(!is_swappable<X&>::value_type);

Instead this proposal here suggests to use a lengthier name for the more rarely used traits and a shorter name for the more often used one. The author of this paper is convinced that the asymmetric name is_swappable_with better matches its potentially heterogeneous character. Also, it is not suggested (compared to N3619) to introduce a separate header for just two or four expression traits: The existing <type_traits> header should be feasible for this. And finally, this proposal does not require that an implementation needs to include <utility> for the purpose of realizing the required swap overload-resolution conditions (In fact, the non-defining declarations of the two swap templates would be sufficient).

Why is it worth providing all these four traits?

From a technical point of view these traits can also be provided by non-experts and non-library implementors, albeit they require a bit more carefulness compared to other expression-testing traits, because of the special ADL-requirements of the Swappable constraints. As an example, take a look at this freely available code.

On the other hand, the author is convinced that swap operations have a similar elemental character comparable to move or copy operations and should therefore be provided even though the Library doesn't yet use all of them within its specification. This rather fundamental role of swap operations has lead to excellent papers from Walter E. Brown, N3553 and its successor N3746, which both contain a good survey about the basic nature of swap operations and even propose to provide built-in operators :=:.

The provision of the pure expression-validity predicates is_swappable and is_swappable_with can be considered as being not much useful given that the two swap templates from header <utility> are not constrained, so a lot of false positives are expected to be returned by these traits; those effects have also been analyzed by Andrew Morrow's paper N3619.

There are two ways of looking at this argument:

First, we would respond to this by suggesting to make these two general function templates constrained templates, which is the heart of proposal variant III. Extended + Constrained swap.

Or alternatively we refer to the fact, that the library does define is_copy/move_constructible traits, albeit many (if not most) user-provided assignment operators are not constrained (and if we would try to make them constrained in the absence of built-in concepts, it is hard to make that possible) and therefore are sensitive to a similar kind of problem; a well-known example of this are the user-defined copy/move assignment operators of std::pair and std::tuple.

When considering to constrain the two swap templates from header <utility> it should be highlighted that doing this could potentially break existing code. To demonstrate this possibility, consider the following possible implementation of a constrained swap function:

template<class T>
typename std::enable_if<
  is_move_constructible<T>::value &&
  is_move_assignable<T>::value
>::type 
swap(T& a, T& b) noexcept(
  is_nothrow_move_constructible<T>::value &&
  is_nothrow_move_assignable<T>::value)
{
  T temp = std::move(a);
  a = std::move(b);
  b = std::move(temp);
}

Lets assume now that some user-defined type N exists, that does not satisfy all of its specified requirements, e.g. it could be non-MoveAssignable like this:

struct N
{
  N& operator=(const N&) = delete;
};

The owner of N could have decided to specialize std::swap like this:

namespace std {

template<>
void swap(N&, N&) noexcept { […] }

}

Once we would decide to constrain the swap template (as shown above), this function specialization will no longer compile, because the constraints of the primary template are still applied to the specialization.

Is this potential problem an immediate show-stopper?

The intuitive answer of many readers is presumably: Yes! — But for a moment I would like to play the role of devil's advocate and present two counter-arguments to this point of view:

  1. Strictly speaking, above kind of template specialization can be considered as invalid, because of wording from 17.6.4.2.1 [namespace.std] (emphasis mine):

    […] A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.

    Obviously, type N violates the MoveAssignable constraints of the std::swap template and this requirement is not a new one. Nonetheless this code might have worked fine for many years…

  2. Furthermore, I would like to remind that C++11 did in fact silently invalidate all existing specializations of std::swap, which did not have the exact same computed exception-specification of that template, because in C++03 there was no exception-specification of std::swap! So, if there are sufficient good reasons, such a possible code-breakage can be considered.

The author of this paper emphasizes that at this point he needs feedback from Committee members for guidance to find the best compromise to resolve LWG 2456. This paper presents several choices and he is convinced that at least one of them is acceptable at this point of time, where the least controversial one (in terms of possible side-effects and implementation costs) surely is the variant denoted as "I. Minimalistic".

Resolved Issues

If either of the proposed resolutions will be accepted, the following library issues will be resolved:

Number Description
2456 Incorrect exception specifications for 'swap' throughout library

Proposed resolutions

This paper intentionally does not provide one single resolution proposal. The intention is to provide to the committee the following selected variants having different advantages and disadvantages.

The proposed wording changes refer in all cases to N4296.

I. Minimalistic

  1. Change 20.3.2 [pairs.pair] as indicated:

    void swap(pair& p) noexcept(see below);
    

    -31- Remarks: The expression inside noexcept is equivalent to:

    is_nothrow_swappable<first_type>::valuenoexcept(swap(first, p.first)) &&
    is_nothrow_swappable<second_type>::valuenoexcept(swap(second, p.second))
    

    […]

  2. Change 20.4.2.3 [tuple.swap] as indicated:

    void swap(tuple& rhs) noexcept(see below);
    

    -1- Remarks: The expression inside noexcept is equivalent to the logical and of the following expressions:

    is_nothrow_swappable<Ti>::valuenoexcept(swap(declval<Ti&>>(), declval<Ti&>()))
    

    where Ti is the ith type in Types.

  3. Change 20.10.2 [meta.type.synop], header <type_traits> synopsis, as indicated:

    namespace std {
      […]
      // 20.10.4.3, type properties:
      […]
      template <class T> struct is_nothrow_move_assignable;
    
      template <class T> struct is_nothrow_swappable;
      
      template <class T> struct is_nothrow_destructible;
      […]
    }
    
  4. Change 20.10.4.3 [meta.unary.prop], Table 49 — "Type property predicates", as indicated:

    Table 49 — Type property predicates
    Template Condition Preconditions
    template <class T>
    struct is_nothrow_swappable;
    The expression swap(declval<T&>(), declval<T&>()) is well-formed
    when treated as an unevaluated operand (Clause 5) in an overload-resolution
    context for swappable values (17.6.3.2 [swappable.requirements]) and this
    expression is known not to throw any exceptions (5.3.7 [expr.unary.noexcept]).
    Access checking is performed as if in a context unrelated to T. Only the
    validity of the immediate context of the swap expression is considered.
    [Note: The compilation of the expression can result in side effects such
    as the instantiation of class template specializations and function template
    specializations, the generation of implicitly-defined functions, and so on. Such
    side effects are not in the "immediate context" and can result in the program
    being ill-formed. — end note]
    T shall be a complete type,
    (possibly cv-qualified) void, or an
    array of unknown bound.
  5. Change 23.3.2.1 [array.overview] p3, class template array overview, as indicated:

    namespace std {
      template <class T, size_t N>
      struct array 
      {
        […]
        void swap(array&) noexcept(is_nothrow_swappable<T>::valuenoexcept(swap(declval<T&>(), declval<T&>())));
        […]
      };
    }
    
  6. Change 23.3.2.7 [array.swap] before p1 as indicated:

    void swap(array& y) noexcept(is_nothrow_swappable<T>::valuenoexcept(swap(declval<T&>(), declval<T&>())));
    
  7. Change 23.4.4.1 [map.overview] p2, class template map overview, as indicated:

    namespace std {
      template <class Key, class T, class Compare = less<Key>,
                class Allocator = allocator<pair<const Key, T> > >
      class map 
      {
        […]
        void swap(map&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Compare>::valuenoexcept(swap(declval<Compare&>(),declval<Compare&>())));
        […]
      };
    }
    
  8. Change 23.4.5.1 [multimap.overview] p2, class template multimap overview, as indicated:

    namespace std {
      template <class Key, class T, class Compare = less<Key>,
                class Allocator = allocator<pair<const Key, T> > >
      class multimap 
      {
        […]
        void swap(multimap&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Compare>::valuenoexcept(swap(declval<Compare&>(),declval<Compare&>())));
        […]
      };
    }
    
  9. Change 23.4.6.1 [set.overview] p2, class template set overview, as indicated:

    namespace std {
      template <class Key, class Compare = less<Key>,
                class Allocator = allocator<Key> >
      class set 
      {
        […]
        void swap(set&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Compare>::valuenoexcept(swap(declval<Compare&>(),declval<Compare&>())));
        […]
      };
    }
    
  10. Change 23.4.7.1 [multiset.overview] p2, class template multiset overview, as indicated:

    namespace std {
      template <class Key, class Compare = less<Key>,
                class Allocator = allocator<Key> >
      class multiset 
      {
        […]
        void swap(multiset&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Compare>::valuenoexcept(swap(declval<Compare&>(),declval<Compare&>())));
        […]
      };
    }
    
  11. Change 23.5.4.1 [unord.map.overview] p3, class template unordered_map overview, as indicated:

    namespace std {
      template <class Key, 
                class T,
                class Hash = hash<Key>,
                class Pred = std::equal_to<Key>,
                class Allocator = std::allocator<std::pair<const Key, T> > >
      class unordered_map 
      {
        […]
        void swap(unordered_map&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Hash>::valuenoexcept(swap(declval<Hash&>(),declval<Hash&>())) &&
                   is_nothrow_swappable<Pred>::valuenoexcept(swap(declval<Pred&>(),declval<Pred&>())));
        […]
      };
    }
    
  12. Change 23.5.5.1 [unord.multimap.overview] p3, class template unordered_multimap overview, as indicated:

    namespace std {
      template <class Key, 
                class T,
                class Hash = hash<Key>,
                class Pred = std::equal_to<Key>,
                class Allocator = std::allocator<std::pair<const Key, T> > >
      class unordered_multimap 
      {
        […]
        void swap(unordered_multimap&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Hash>::valuenoexcept(swap(declval<Hash&>(),declval<Hash&>())) &&
                   is_nothrow_swappable<Pred>::valuenoexcept(swap(declval<Pred&>(),declval<Pred&>())));
        […]
      };
    }
    
  13. Change 23.5.6.1 [unord.set.overview] p3, class template unordered_set overview, as indicated:

    namespace std {
      template <class Key, 
                class Hash = hash<Key>,
                class Pred = std::equal_to<Key>,
                class Allocator = std::allocator<Key> >
      class unordered_set 
      {
        […]
        void swap(unordered_set&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Hash>::valuenoexcept(swap(declval<Hash&>(),declval<Hash&>())) &&
                   is_nothrow_swappable<Pred>::valuenoexcept(swap(declval<Pred&>(),declval<Pred&>())));
        […]
      };
    }
    
  14. Change 23.5.7.1 [unord.multiset.overview] p3, class template unordered_multiset overview, as indicated:

    namespace std {
      template <class Key, 
                class Hash = hash<Key>,
                class Pred = std::equal_to<Key>,
                class Allocator = std::allocator<Key> >
      class unordered_multiset 
      {
        […]
        void swap(unordered_multiset&)
          noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                   is_nothrow_swappable<Hash>::valuenoexcept(swap(declval<Hash&>(),declval<Hash&>())) &&
                   is_nothrow_swappable<Pred>::valuenoexcept(swap(declval<Pred&>(),declval<Pred&>())));
        […]
      };
    }
    
  15. Change 23.6.3.1 [queue.defn] p1, class template queue definition, as indicated:

    namespace std {
      template <class T, class Container = deque<T> >
      class queue 
      {
        […]
      protected:
        Container c;
        
      public:
        […]
        void swap(queue& q) noexcept(is_nothrow_swappable<Container>::valuenoexcept(swap(c, q.c)))
        { using std::swap; swap(c, q.c); }
      };
    }
    
  16. Change 23.6.4 [priority.queue] p1, class template priority_queue definition, as indicated:

    namespace std {
      template <class T, class Container = vector<T>,
        class Compare = less<typename Container::value_type> >
      class priority_queue 
      {
        […]
      protected:
        Container c;
        Compare comp;
        
      public:
        […]
        void swap(priority_queue& q) noexcept(
            is_nothrow_swappable<Container>::value && is_nothrow_swappable<Compare>::value
            noexcept(swap(c, q.c)) && noexcept(swap(comp, q.comp)))
          { using std::swap; swap(c, q.c); swap(comp, q.comp); }
      };
    }
    
  17. Change 23.6.5.2 [stack.defn], class template stack definition, as indicated:

    namespace std {
      template <class T, class Container = deque<T> >
      class stack 
      {
        […]
      protected:
        Container c;
        
      public:
        […]
        void swap(stack& q) noexcept(is_nothrow_swappable<Container>::valuenoexcept(swap(c, q.c)))
          { using std::swap; swap(c, q.c); }
      };
    }
    

II. Extended

The changes are the same as I. Minimalistic, except for the bullets (3) and (4) that have to be replaced by the following wording changes:

  1. […]

  2. Change 20.10.2 [meta.type.synop], header <type_traits> synopsis, as indicated:

    namespace std {
      […]
      // 20.10.4.3, type properties:
      […]
      template <class T> struct is_move_assignable;
      
      template <class T, class U> struct is_swappable_with;
      template <class T> struct is_swappable;
      
      template <class T> struct is_destructible;
      […]
      template <class T> struct is_nothrow_move_assignable;
    
      template <class T, class U> struct is_nothrow_swappable_with;
      template <class T> struct is_nothrow_swappable;
      
      template <class T> struct is_nothrow_destructible;
      […]
    }
    
  3. Change 20.10.4.3 [meta.unary.prop], Table 49 — "Type property predicates", as indicated:

    [Drafting notes:

    1. The term referenceable type, referred to below, is defined in 17.3.19 [defns.referenceable]. — end drafting notes]

    2. The specification below allows, but does not require, that an implementation defines the traits is_swappable and is_nothrow_swappable, respectively, in terms of the more general traits is_swappable_with and is_nothrow_swappable_with, respectively.

    Table 49 — Type property predicates
    Template Condition Preconditions
    template <class T, class U>
    struct is_swappable_with;
    The expressions swap(declval<T>(), declval<U>()) and
    swap(declval<U>(), declval<T>()) are each well-formed
    when treated as an unevaluated operand (Clause 5) in an overload-resolution
    context for swappable values (17.6.3.2 [swappable.requirements]). Access
    checking is performed as if in a context unrelated to T and U. Only the
    validity of the immediate context of the swap expressions is considered.
    [Note: The compilation of the expressions can result in side effects such
    as the instantiation of class template specializations and function template
    specializations, the generation of implicitly-defined functions, and so on. Such
    side effects are not in the "immediate context" and can result in the program
    being ill-formed. — end note]
    T and U shall be complete types,
    (possibly cv-qualified) void, or
    arrays of unknown bound.
    template <class T>
    struct is_swappable;
    For a referenceable type T, the same result
    as is_swappable_with<T&, T&>::value,
    otherwise false.
    T shall be a complete type,
    (possibly cv-qualified) void, or an
    array of unknown bound.
    template <class T, class U>
    struct is_nothrow_swappable_with;
    is_swappable_with<T, U>::value is true
    and each swap expression of the definition of
    is_swappable_with<T, U> is known not to throw
    any exceptions (5.3.7 [expr.unary.noexcept]).
    T and U shall be complete types,
    (possibly cv-qualified) void, or
    arrays of unknown bound.
    template <class T>
    struct is_nothrow_swappable;
    For a referenceable type T, the same result
    as is_nothrow_swappable_with<T&, T&>::value,
    otherwise false.
    T shall be a complete type,
    (possibly cv-qualified) void, or an
    array of unknown bound.
  4. […]

III. Extended + Constrained swap

The changes are the same as II. Extended, except that an additional bullet (18) is added at the end of the list of changes:

  1. […]

    […]

  2. […]

  3. Change 20.2.2 [utility.swap] as indicated:

    [Drafting notes:

    1. The Requires elements have been left intentionally, based on the assumption that the additional semantic constraints implied by the MoveConstructible and MoveAssignable are important to keep.

    2. The replacement of the expression noexcept(swap(*a, *b)) within the noexcept-specification is not a required change, but seems to improve the symmetry between exception-specifications and template constraints and is therefore recommended by the author. In addition, a similar approach is already necessary in existing implementation headers when forward declarations of the swap templates are provided.

    3. The seemingly recursive relation between the is_[nothrow_]swappable trait definitions and especially of the second swap declaration is resolvable by a suitable sequence of (non-defining) declarations.

    end drafting notes]

    template<class T> void swap(T& a, T& b) noexcept(see below);
    

    -1- Remarks: This function shall not participate in overload resolution unless is_move_constructible<T>::value is true and is_move_assignable<T>::value is true. The expression inside noexcept is equivalent to:

    is_nothrow_move_constructible<T>::value &&
    is_nothrow_move_assignable<T>::value
    

    -2- Requires: Type T shall be MoveConstructible (Table 20) and MoveAssignable (Table 22).

    -3- Effects: […]

    template<class T, size_t N>
      void swap(T (&a)[N], T (&b)[N]) noexcept(is_nothrow_swappable<T>::valuenoexcept(swap(*a, *b)));
    

    -?- Remarks: This function shall not participate in overload resolution unless is_swappable<T>::value is true.

    -4- Requires: a[i] shall be swappable with (17.6.3.2) b[i] for all i in the range [0, N).

    -5- Effects: swap_ranges(a, a + N, b)

Feature-testing Macros

For the purposes of SG10, this paper recommends the macro name __cpp_lib_is_nothrow_swappable, if the minimalistic resolution would be accepted, or alternatively, __cpp_lib_is_swappable, if either the extended proposal or the extended plus constrained swap would be accepted.