1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/Move.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,250 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/* C++11-style, but C++98-usable, "move references" implementation. */
1.11 +
1.12 +#ifndef mozilla_Move_h
1.13 +#define mozilla_Move_h
1.14 +
1.15 +#include "mozilla/TypeTraits.h"
1.16 +
1.17 +namespace mozilla {
1.18 +
1.19 +/*
1.20 + * "Move" References
1.21 + *
1.22 + * Some types can be copied much more efficiently if we know the original's
1.23 + * value need not be preserved --- that is, if we are doing a "move", not a
1.24 + * "copy". For example, if we have:
1.25 + *
1.26 + * Vector<T> u;
1.27 + * Vector<T> v(u);
1.28 + *
1.29 + * the constructor for v must apply a copy constructor to each element of u ---
1.30 + * taking time linear in the length of u. However, if we know we will not need u
1.31 + * any more once v has been initialized, then we could initialize v very
1.32 + * efficiently simply by stealing u's dynamically allocated buffer and giving it
1.33 + * to v --- a constant-time operation, regardless of the size of u.
1.34 + *
1.35 + * Moves often appear in container implementations. For example, when we append
1.36 + * to a vector, we may need to resize its buffer. This entails moving each of
1.37 + * its extant elements from the old, smaller buffer to the new, larger buffer.
1.38 + * But once the elements have been migrated, we're just going to throw away the
1.39 + * old buffer; we don't care if they still have their values. So if the vector's
1.40 + * element type can implement "move" more efficiently than "copy", the vector
1.41 + * resizing should by all means use a "move" operation. Hash tables should also
1.42 + * use moves when resizing their internal array as entries are added and
1.43 + * removed.
1.44 + *
1.45 + * The details of the optimization, and whether it's worth applying, vary
1.46 + * from one type to the next: copying an 'int' is as cheap as moving it, so
1.47 + * there's no benefit in distinguishing 'int' moves from copies. And while
1.48 + * some constructor calls for complex types are moves, many really have to
1.49 + * be copies, and can't be optimized this way. So we need:
1.50 + *
1.51 + * 1) a way for a type (like Vector) to announce that it can be moved more
1.52 + * efficiently than it can be copied, and provide an implementation of that
1.53 + * move operation; and
1.54 + *
1.55 + * 2) a way for a particular invocation of a copy constructor to say that it's
1.56 + * really a move, not a copy, and that the value of the original isn't
1.57 + * important afterwards (although it must still be safe to destroy).
1.58 + *
1.59 + * If a constructor has a single argument of type 'T&&' (an 'rvalue reference
1.60 + * to T'), that indicates that it is a 'move constructor'. That's 1). It should
1.61 + * move, not copy, its argument into the object being constructed. It may leave
1.62 + * the original in any safely-destructible state.
1.63 + *
1.64 + * If a constructor's argument is an rvalue, as in 'C(f(x))' or 'C(x + y)', as
1.65 + * opposed to an lvalue, as in 'C(x)', then overload resolution will prefer the
1.66 + * move constructor, if there is one. The 'mozilla::Move' function, defined in
1.67 + * this file, is an identity function you can use in a constructor invocation to
1.68 + * make any argument into an rvalue, like this: C(Move(x)). That's 2). (You
1.69 + * could use any function that works, but 'Move' indicates your intention
1.70 + * clearly.)
1.71 + *
1.72 + * Where we might define a copy constructor for a class C like this:
1.73 + *
1.74 + * C(const C& rhs) { ... copy rhs to this ... }
1.75 + *
1.76 + * we would declare a move constructor like this:
1.77 + *
1.78 + * C(C&& rhs) { .. move rhs to this ... }
1.79 + *
1.80 + * And where we might perform a copy like this:
1.81 + *
1.82 + * C c2(c1);
1.83 + *
1.84 + * we would perform a move like this:
1.85 + *
1.86 + * C c2(Move(c1));
1.87 + *
1.88 + * Note that 'T&&' implicitly converts to 'T&'. So you can pass a 'T&&' to an
1.89 + * ordinary copy constructor for a type that doesn't support a special move
1.90 + * constructor, and you'll just get a copy. This means that templates can use
1.91 + * Move whenever they know they won't use the original value any more, even if
1.92 + * they're not sure whether the type at hand has a specialized move constructor.
1.93 + * If it doesn't, the 'T&&' will just convert to a 'T&', and the ordinary copy
1.94 + * constructor will apply.
1.95 + *
1.96 + * A class with a move constructor can also provide a move assignment operator.
1.97 + * A generic definition would run this's destructor, and then apply the move
1.98 + * constructor to *this's memory. A typical definition:
1.99 + *
1.100 + * C& operator=(C&& rhs) {
1.101 + * MOZ_ASSERT(&rhs != this, "self-moves are prohibited");
1.102 + * this->~C();
1.103 + * new(this) C(Move(rhs));
1.104 + * return *this;
1.105 + * }
1.106 + *
1.107 + * With that in place, one can write move assignments like this:
1.108 + *
1.109 + * c2 = Move(c1);
1.110 + *
1.111 + * This destroys c2, moves c1's value to c2, and leaves c1 in an undefined but
1.112 + * destructible state.
1.113 + *
1.114 + * As we say, a move must leave the original in a "destructible" state. The
1.115 + * original's destructor will still be called, so if a move doesn't
1.116 + * actually steal all its resources, that's fine. We require only that the
1.117 + * move destination must take on the original's value; and that destructing
1.118 + * the original must not break the move destination.
1.119 + *
1.120 + * (Opinions differ on whether move assignment operators should deal with move
1.121 + * assignment of an object onto itself. It seems wise to either handle that
1.122 + * case, or assert that it does not occur.)
1.123 + *
1.124 + * Forwarding:
1.125 + *
1.126 + * Sometimes we want copy construction or assignment if we're passed an ordinary
1.127 + * value, but move construction if passed an rvalue reference. For example, if
1.128 + * our constructor takes two arguments and either could usefully be a move, it
1.129 + * seems silly to write out all four combinations:
1.130 + *
1.131 + * C::C(X& x, Y& y) : x(x), y(y) { }
1.132 + * C::C(X& x, Y&& y) : x(x), y(Move(y)) { }
1.133 + * C::C(X&& x, Y& y) : x(Move(x)), y(y) { }
1.134 + * C::C(X&& x, Y&& y) : x(Move(x)), y(Move(y)) { }
1.135 + *
1.136 + * To avoid this, C++11 has tweaks to make it possible to write what you mean.
1.137 + * The four constructor overloads above can be written as one constructor
1.138 + * template like so[0]:
1.139 + *
1.140 + * template <typename XArg, typename YArg>
1.141 + * C::C(XArg&& x, YArg&& y) : x(Forward<XArg>(x)), y(Forward<YArg>(y)) { }
1.142 + *
1.143 + * ("'Don't Repeat Yourself'? What's that?")
1.144 + *
1.145 + * This takes advantage of two new rules in C++11:
1.146 + *
1.147 + * - First, when a function template takes an argument that is an rvalue
1.148 + * reference to a template argument (like 'XArg&& x' and 'YArg&& y' above),
1.149 + * then when the argument is applied to an lvalue, the template argument
1.150 + * resolves to 'T &'; and when it is applied to an rvalue, the template
1.151 + * argument resolves to 'T &&'. Thus, in a call to C::C like:
1.152 + *
1.153 + * X foo(int);
1.154 + * Y yy;
1.155 + *
1.156 + * C(foo(5), yy)
1.157 + *
1.158 + * XArg would resolve to 'X&&', and YArg would resolve to 'Y&'.
1.159 + *
1.160 + * - Second, Whereas C++ used to forbid references to references, C++11 defines
1.161 + * 'collapsing rules': 'T& &', 'T&& &', and 'T& &&' (that is, any combination
1.162 + * involving an lvalue reference) now collapse to simply 'T&'; and 'T&& &&'
1.163 + * collapses to 'T&&'.
1.164 + *
1.165 + * Thus, in the call above, 'XArg&&' is 'X&& &&', collapsing to 'X&&'; and
1.166 + * 'YArg&&' is 'Y& &&', which collapses to 'Y &'. Because the arguments are
1.167 + * declared as rvalue references to template arguments, the rvalue-ness
1.168 + * "shines through" where present.
1.169 + *
1.170 + * Then, the 'Forward<T>' function --- you must invoke 'Forward' with its type
1.171 + * argument --- returns an lvalue reference or an rvalue reference to its
1.172 + * argument, depending on what T is. In our unified constructor definition, that
1.173 + * means that we'll invoke either the copy or move constructors for x and y,
1.174 + * depending on what we gave C's constructor. In our call, we'll move 'foo()'
1.175 + * into 'x', but copy 'yy' into 'y'.
1.176 + *
1.177 + * This header file defines Move and Forward in the mozilla namespace. It's up
1.178 + * to individual containers to annotate moves as such, by calling Move; and it's
1.179 + * up to individual types to define move constructors and assignment operators
1.180 + * when valuable.
1.181 + *
1.182 + * (C++11 says that the <utility> header file should define 'std::move' and
1.183 + * 'std::forward', which are just like our 'Move' and 'Forward'; but those
1.184 + * definitions aren't available in that header on all our platforms, so we
1.185 + * define them ourselves here.)
1.186 + *
1.187 + * 0. This pattern is known as "perfect forwarding". Interestingly, it is not
1.188 + * actually perfect, and it can't forward all possible argument expressions!
1.189 + * There are two issues: one that's a C++11 issue, and one that's a legacy
1.190 + * compiler issue.
1.191 + *
1.192 + * The C++11 issue is that you can't form a reference to a bit-field. As a
1.193 + * workaround, assign the bit-field to a local variable and use that:
1.194 + *
1.195 + * // C is as above
1.196 + * struct S { int x : 1; } s;
1.197 + * C(s.x, 0); // BAD: s.x is a reference to a bit-field, can't form those
1.198 + * int tmp = s.x;
1.199 + * C(tmp, 0); // OK: tmp not a bit-field
1.200 + *
1.201 + * The legacy issue is that when we don't have true nullptr and must emulate
1.202 + * it (gcc 4.4/4.5), forwarding |nullptr| results in an |int| or |long|
1.203 + * forwarded reference. But such a reference, even if its value is a null
1.204 + * pointer constant expression, is not itself a null pointer constant
1.205 + * expression. This causes -Werror=conversion-null errors and pointer-to-
1.206 + * integer comparison errors. Until we always have true nullptr, users of
1.207 + * forwarding methods must not pass |nullptr| to them.
1.208 + */
1.209 +
1.210 +/**
1.211 + * Identical to std::Move(); this is necessary until our stlport supports
1.212 + * std::move().
1.213 + */
1.214 +template<typename T>
1.215 +inline typename RemoveReference<T>::Type&&
1.216 +Move(T&& a)
1.217 +{
1.218 + return static_cast<typename RemoveReference<T>::Type&&>(a);
1.219 +}
1.220 +
1.221 +/**
1.222 + * These two overloads are identical to std::forward(); they are necessary until
1.223 + * our stlport supports std::forward().
1.224 + */
1.225 +template<typename T>
1.226 +inline T&&
1.227 +Forward(typename RemoveReference<T>::Type& a)
1.228 +{
1.229 + return static_cast<T&&>(a);
1.230 +}
1.231 +
1.232 +template<typename T>
1.233 +inline T&&
1.234 +Forward(typename RemoveReference<T>::Type&& t)
1.235 +{
1.236 + static_assert(!IsLvalueReference<T>::value,
1.237 + "misuse of Forward detected! try the other overload");
1.238 + return static_cast<T&&>(t);
1.239 +}
1.240 +
1.241 +/** Swap |t| and |u| using move-construction if possible. */
1.242 +template<typename T>
1.243 +inline void
1.244 +Swap(T& t, T& u)
1.245 +{
1.246 + T tmp(Move(t));
1.247 + t = Move(u);
1.248 + u = Move(tmp);
1.249 +}
1.250 +
1.251 +} // namespace mozilla
1.252 +
1.253 +#endif /* mozilla_Move_h */
