| blob | 2c20c5eef6dfa85046f1d9befe024fbe5ffe55c3 |
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 /* C++11-style, but C++98-usable, "move references" implementation. */
9 #ifndef mozilla_Move_h
10 #define mozilla_Move_h
14 #include <utility>
18 /*
19 * "Move" References
20 *
21 * Some types can be copied much more efficiently if we know the original's
22 * value need not be preserved --- that is, if we are doing a "move", not a
23 * "copy". For example, if we have:
24 *
25 * Vector<T> u;
26 * Vector<T> v(u);
27 *
28 * the constructor for v must apply a copy constructor to each element of u ---
29 * taking time linear in the length of u. However, if we know we will not need u
30 * any more once v has been initialized, then we could initialize v very
31 * efficiently simply by stealing u's dynamically allocated buffer and giving it
32 * to v --- a constant-time operation, regardless of the size of u.
33 *
34 * Moves often appear in container implementations. For example, when we append
35 * to a vector, we may need to resize its buffer. This entails moving each of
36 * its extant elements from the old, smaller buffer to the new, larger buffer.
37 * But once the elements have been migrated, we're just going to throw away the
38 * old buffer; we don't care if they still have their values. So if the vector's
39 * element type can implement "move" more efficiently than "copy", the vector
40 * resizing should by all means use a "move" operation. Hash tables should also
41 * use moves when resizing their internal array as entries are added and
42 * removed.
43 *
44 * The details of the optimization, and whether it's worth applying, vary
45 * from one type to the next: copying an 'int' is as cheap as moving it, so
46 * there's no benefit in distinguishing 'int' moves from copies. And while
47 * some constructor calls for complex types are moves, many really have to
48 * be copies, and can't be optimized this way. So we need:
49 *
50 * 1) a way for a type (like Vector) to announce that it can be moved more
51 * efficiently than it can be copied, and provide an implementation of that
52 * move operation; and
53 *
54 * 2) a way for a particular invocation of a copy constructor to say that it's
55 * really a move, not a copy, and that the value of the original isn't
56 * important afterwards (although it must still be safe to destroy).
57 *
58 * If a constructor has a single argument of type 'T&&' (an 'rvalue reference
59 * to T'), that indicates that it is a 'move constructor'. That's 1). It should
60 * move, not copy, its argument into the object being constructed. It may leave
61 * the original in any safely-destructible state.
62 *
63 * If a constructor's argument is an rvalue, as in 'C(f(x))' or 'C(x + y)', as
64 * opposed to an lvalue, as in 'C(x)', then overload resolution will prefer the
65 * move constructor, if there is one. The 'std::move' function, defined in
66 * <utility>, is an identity function you can use in a constructor invocation to
67 * make any argument into an rvalue, like this: C(std::move(x)). That's 2). (You
68 * could use any function that works, but 'Move' indicates your intention
69 * clearly.)
70 *
71 * Where we might define a copy constructor for a class C like this:
72 *
73 * C(const C& rhs) { ... copy rhs to this ... }
74 *
75 * we would declare a move constructor like this:
76 *
77 * C(C&& rhs) { .. move rhs to this ... }
78 *
79 * And where we might perform a copy like this:
80 *
81 * C c2(c1);
82 *
83 * we would perform a move like this:
84 *
85 * C c2(std::move(c1));
86 *
87 * Note that 'T&&' implicitly converts to 'T&'. So you can pass a 'T&&' to an
88 * ordinary copy constructor for a type that doesn't support a special move
89 * constructor, and you'll just get a copy. This means that templates can use
90 * Move whenever they know they won't use the original value any more, even if
91 * they're not sure whether the type at hand has a specialized move constructor.
92 * If it doesn't, the 'T&&' will just convert to a 'T&', and the ordinary copy
93 * constructor will apply.
94 *
95 * A class with a move constructor can also provide a move assignment operator.
96 * A generic definition would run this's destructor, and then apply the move
97 * constructor to *this's memory. A typical definition:
98 *
99 * C& operator=(C&& rhs) {
100 * MOZ_ASSERT(&rhs != this, "self-moves are prohibited");
101 * this->~C();
102 * new(this) C(std::move(rhs));
103 * return *this;
104 * }
105 *
106 * With that in place, one can write move assignments like this:
107 *
108 * c2 = std::move(c1);
109 *
110 * This destroys c2, moves c1's value to c2, and leaves c1 in an undefined but
111 * destructible state.
112 *
113 * As we say, a move must leave the original in a "destructible" state. The
114 * original's destructor will still be called, so if a move doesn't
115 * actually steal all its resources, that's fine. We require only that the
116 * move destination must take on the original's value; and that destructing
117 * the original must not break the move destination.
118 *
119 * (Opinions differ on whether move assignment operators should deal with move
120 * assignment of an object onto itself. It seems wise to either handle that
121 * case, or assert that it does not occur.)
122 *
123 * Forwarding:
124 *
125 * Sometimes we want copy construction or assignment if we're passed an ordinary
126 * value, but move construction if passed an rvalue reference. For example, if
127 * our constructor takes two arguments and either could usefully be a move, it
128 * seems silly to write out all four combinations:
129 *
130 * C::C(X& x, Y& y) : x(x), y(y) { }
131 * C::C(X& x, Y&& y) : x(x), y(std::move(y)) { }
132 * C::C(X&& x, Y& y) : x(std::move(x)), y(y) { }
133 * C::C(X&& x, Y&& y) : x(std::move(x)), y(std::move(y)) { }
134 *
135 * To avoid this, C++11 has tweaks to make it possible to write what you mean.
136 * The four constructor overloads above can be written as one constructor
137 * template like so[0]:
138 *
139 * template <typename XArg, typename YArg>
140 * C::C(XArg&& x, YArg&& y) : x(std::forward<XArg>(x)),
141 * y(std::forward<YArg>(y)) { }
142 *
143 * ("'Don't Repeat Yourself'? What's that?")
144 *
145 * This takes advantage of two new rules in C++11:
146 *
147 * - First, when a function template takes an argument that is an rvalue
148 * reference to a template argument (like 'XArg&& x' and 'YArg&& y' above),
149 * then when the argument is applied to an lvalue, the template argument
150 * resolves to 'T&'; and when it is applied to an rvalue, the template
151 * argument resolves to 'T'. Thus, in a call to C::C like:
152 *
153 * X foo(int);
154 * Y yy;
155 *
156 * C(foo(5), yy)
157 *
158 * XArg would resolve to 'X', and YArg would resolve to 'Y&'.
159 *
160 * - Second, Whereas C++ used to forbid references to references, C++11 defines
161 * 'collapsing rules': 'T& &', 'T&& &', and 'T& &&' (that is, any combination
162 * involving an lvalue reference) now collapse to simply 'T&'; and 'T&& &&'
163 * collapses to 'T&&'.
164 *
165 * Thus, in the call above, 'XArg&&' is 'X&&'; and 'YArg&&' is 'Y& &&', which
166 * collapses to 'Y&'. Because the arguments are declared as rvalue references
167 * to template arguments, the lvalue-ness "shines through" where present.
168 *
169 * Then, the 'std::forward<T>' function --- you must invoke 'Forward' with its
170 * type argument --- returns an lvalue reference or an rvalue reference to its
171 * argument, depending on what T is. In our unified constructor definition, that
172 * means that we'll invoke either the copy or move constructors for x and y,
173 * depending on what we gave C's constructor. In our call, we'll move 'foo()'
174 * into 'x', but copy 'yy' into 'y'.
175 *
176 * This header file defines Move and Forward in the mozilla namespace. It's up
177 * to individual containers to annotate moves as such, by calling Move; and it's
178 * up to individual types to define move constructors and assignment operators
179 * when valuable.
180 *
181 * (C++11 says that the <utility> header file should define 'std::move' and
182 * 'std::forward', which are just like our 'Move' and 'Forward'; but those
183 * definitions aren't available in that header on all our platforms, so we
184 * define them ourselves here.)
185 *
186 * 0. This pattern is known as "perfect forwarding". Interestingly, it is not
187 * actually perfect, and it can't forward all possible argument expressions!
188 * There is a C++11 issue: you can't form a reference to a bit-field. As a
189 * workaround, assign the bit-field to a local variable and use that:
190 *
191 * // C is as above
192 * struct S { int x : 1; } s;
193 * C(s.x, 0); // BAD: s.x is a reference to a bit-field, can't form those
194 * int tmp = s.x;
195 * C(tmp, 0); // OK: tmp not a bit-field
196 */
198 /** Swap |aX| and |aY| using move-construction if possible. */
204 }