f031f09960934a7f407d32e7c11c3019622bd3ed
[rust-101.git] / src / part05.rs
1 // Rust-101, Part 05: Clone, Copy
2 // ==============================
3
4 use std::cmp;
5 use std::ops;
6
7 // In the course of the next few parts, we are going to build a data-structure for
8 // computations with *bug* numbers. We would like to not have an upper bound
9 // to how large these numbers can get, with the memory of the machine being the
10 // only limit.
11 // 
12 // We start by deciding how to represent such big numbers. One possibility here is
13 // to use a vector of "small" numbers, which we will then consider the "digits"
14 // of the big number. This is like "1337" being a vector of 4 small numbers (1, 3, 3, 7),
15 // except that we will use `u64` as type of our base numbers. Now we just have to decide
16 // the order in which we store numbers. I decided that we will store the least significant
17 // digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
18 // Finally, we declare that there must not be any trailing zeros (corresponding to
19 // useless leading zeros in our usual way of writing numbers). This is to ensure that
20 // the same number can only be stored in one way.
21
22 // To write this down in Rust, we use a `struct`, which is a lot like structs in C:
23 // Just a collection of a bunch of named fields. Every field can be private to the current module
24 // (which is the default), or public (which would be indicated by a `pub` in front of the name).
25 // For the sake of the tutorial, we make `dat` public - otherwise, the next parts of this
26 // course could not work on `BigInt`s. Of course, in a real program, one would make the field
27 // private to ensure that the invariant (no trailing zeros) is maintained.
28 pub struct BigInt {
29     pub data: Vec<u64>,
30 }
31
32 // Now that we fixed the data representation, we can start implementing methods on it.
33 impl BigInt {
34     // Let's start with a constructor, creating a `BigInt` from an ordinary integer.
35     // To create an instance of a struct, we write its name followed by a list of
36     // fields and initial values assigned to them.
37     pub fn new(x: u64) -> Self {
38         if x == 0 {
39             BigInt { data: vec![] }
40         } else {
41             BigInt { data: vec![x] }
42         }
43     }
44
45     // It can often be useful to encode the invariant of a data-structure in code, so here
46     // is a check that detects useless trailing zeros.
47     pub fn test_invariant(&self) -> bool {
48         if self.data.len() == 0 {
49             true
50         } else {
51             self.data[self.data.len() - 1] != 0
52         }
53     }
54
55     // We can convert any vector of digits into a number, by removing trailing zeros. The `mut`
56     // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally
57     // change the vector `v`. In this case, we need to make that annotation to be able to call `pop`
58     // on `v`.
59     pub fn from_vec(mut v: Vec<u64>) -> Self {
60         while v.len() > 0 && v[v.len()-1] == 0 {
61             v.pop();
62         }
63         BigInt { data: v }
64     }
65 }
66
67 // If you have a close look at the type of `BigInt::from_vec`, you will notice that it
68 // consumes the vector `v`. The caller hence loses access. There is however something
69 // we can do if we don't want that to happen: We can explicitly `clone` the vector,
70 // which means that a full (or *deep*) copy will be performed. Technically,
71 // `clone` takes a borrowed vector, and returns a fully owned one.
72 fn clone_demo() {
73     let v = vec![0,1 << 16];
74     let b1 = BigInt::from_vec(v.clone());
75     let b2 = BigInt::from_vec(v);
76 }
77
78 // To be clonable is a property of a type, and as such, naturally expressed with a trait.
79 // In fact, Rust already comes with a trait `Clone` for exactly this purpose. We can hence
80 // make our `BigInt` clonable as well.
81 impl Clone for BigInt {
82     fn clone(&self) -> Self {
83         BigInt { data: self.data.clone() }
84     }
85 }
86 // Making a type clonable is such a common exercise that Rust can even help you doing it:
87 // If you add `#[derive(Clone)]' right in front of the definition of `BigInt`, Rust will
88 // generate an implementation of `clone` that simply clones all the fields. Try it!
89
90 // We can also make the type `SomethingOrNothing<T>` implement `Clone`. However, that
91 // can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce
92 // the type variable.
93 use part02::{SomethingOrNothing,Something,Nothing};
94 impl<T: Clone> Clone for SomethingOrNothing<T> {
95     fn clone(&self) -> Self {
96         match *self {
97             Nothing => Nothing,
98             // In the second arm of the match, we need to talk about the value `v`
99             // that's stored in `self`. However, if we would write the pattern as
100             // `Something(v)`, that would indicate that we *own* `v` in the code
101             // after the arrow. That can't work though, we have to leave `v` owned by
102             // whoever called us - after all, we don't even own `self`, we just borrowed it.
103             // By writing `Something(ref v)`, we just borrow `v` for the duration of the match
104             // arm. That's good enough for cloning it.
105             Something(ref v) => Something(v.clone()),
106         }
107     }
108 }
109 // Again, Rust will generate this implementation automatically if you add
110 // `#[derive(Clone)]` right before the definition of `SomethingOrNothing`.
111
112 // With `BigInt` being about numbers, we should be able to write a version of `vec_min`
113 // that computes the minimum of a list of `BigInt`. We start by writing `min` for
114 // `BigInt`. Now our assumption of having no trailing zeros comes in handy!
115 impl BigInt {
116     fn min(self, other: Self) -> Self {
117         // Just to be sure, we first check that both operands actually satisfy our invariant.
118         // `debug_assert!` is a macro that checks that its argument (must be of type `bool`)
119         // is `true`, and panics otherwise. It gets removed in release builds, which you do with
120         // `cargo build --release`.
121         // 
122         // If you carefully check the type of `BigInt::test_invariant`, you may be surprised that
123         // we can call the function this way. Doesn't it take `self` in borrowed form? Indeed,
124         // the explicit way to do that would be to call `(&other).test_invariant()`. However, the
125         // `self` argument of a method is treated specially by Rust, and borrowing happens automatically here.
126         debug_assert!(self.test_invariant() && other.test_invariant());
127         // If the lengths of the two numbers differ, we already know which is larger.
128         if self.data.len() < other.data.len() {
129             self
130         } else if self.data.len() > other.data.len() {
131             other
132         } else {
133             // **Exercise 05.1**: Fill in this code.
134             panic!("Not yet implemented.");
135         }
136     }
137 }
138
139 // Now we can write `vec_min`. In order to make it type-check, we have to write it as follows.
140 fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
141     let mut min: Option<BigInt> = None;
142     for e in v {
143         min = Some(match min {
144             None => e.clone(),
145             Some(n) => e.clone().min(n)
146         });
147     }
148     min
149 }
150 // Now, what's happening here? Why do we have to write `clone()`, and why did we not
151 // have to write that in our previous version?
152 // 
153 // The answer is already hidden in the type of `vec_min`: `v` is just borrowed, but
154 // the Option<BigInt> that it returns is *owned*. We can't just return one
155 // of the elements of `v`, as that would mean that it is no longer in the vector!
156 // In our code, this comes up when we update the intermediate variable `min`, which
157 // also has type `Option<BigInt>`. If you replace `e.clone()` in the `None` arm
158 // with `*e`, Rust will complain "Cannot move out of borrowed content". That's because
159 // `e` is a `&BigInt`. Assigning `min` to `*e` works just like a function call:
160 // Ownership of the underlying data (in this case, the digits) is transferred from
161 // the vector to `min`. But that's not allowed, since we must retain the vector
162 // in its existing state. After cloning `e`, we own the copy that was created,
163 // and hence we can store it in `min`.<br/>
164 // Of course, making such a full copy is expensive, so we'd like to avoid it.
165 // That's going to happen in the next part.
166 // 
167 // But before we go there, I should answer the second question I brought up above:
168 // Why did our old `vec_min` work? We stored the minimal `i32` locally without
169 // cloning, and Rust did not complain. That's because there isn't really much
170 // of an "ownership" when it comes to types like `i32` or `bool`: If you move
171 // the value from one place to another, then both instance are independent
172 // and complete instances of their type. This is in stark contrast to types
173 // like `Vec<i32>`, where merely moving the value results in both the old
174 // and the new vector to point to the same underlying buffer.
175 //
176 // Rust calls types like `i32` that can be freely duplicated `Copy` types.
177 // `Copy` is another trait, and it is implemented for the basic types of
178 // the language. Remember how we defined the trait `Minimum` by writing
179 // `trait Minimum : Copy { ...`? This tells Rust that every type that
180 // implements `Minimum` must also implement `Copy`, and that's why Rust
181 // accepted our generic `vec_min` in part 02.
182 // 
183 // Curiously, `Copy` is a trait that does not require any method to
184 // be implemented. Implementing `Copy` is merely a semantic statement,
185 // saying that the idea of ownership does not really apply to this type.
186 // Traits without methods are called *marker traits*. We will see some
187 // more examples of such traits later.
188 // 
189 // If you try to implement `Copy` for `BigInt`, you will notice that Rust
190 // does not let you do that. A type can only be `Copy` if all its elements
191 // are `Copy`, and that's not the case for `BigInt`. However, we can make
192 // `SomethingOrNothing<T>` copy if `T` is `Copy`.
193 impl<T: Copy> Copy for SomethingOrNothing<T>{}
194 // Again, Rust can generate implementations of `Copy` automatically. If
195 // you add `#[derive(Copy,Clone)]` right before the definition of `SomethingOrNothing`,
196 // both `Copy` and `Clone` will automatically be implemented.
197
198 // In closing this part, I'd like to give you another perspective on the
199 // move semantics (i.e., ownership passing) that Rust applies, and how
200 // `Copy` and `Clone` fit.<br/>
201 // When Rust code is executed, passing a value (like `i32` or `Vec<i32>`)
202 // to a function will always result in a shallow copy being performed: Rust
203 // just copies the bytes representing that value, and considers itself done.
204 // That's just like the default copy constructor in C++. Rust, however, will
205 // consider this a destructive operation: After copying the bytes elsewhere,
206 // the original value must no longer be used. After all, the two could not
207 // share a pointer! If, however, you mark a type `Copy`, then Rust will *not*
208 // consider a move destructive, and just like in C++, the old and new value
209 // can happily coexist. Now, Rust does not allow to to overload the copy
210 // constructor. This means that passing a value around will always be a fast
211 // operation, no allocation or copying of large data of the heap will happen.
212 // In the situations where you would write a copy constructor in C++ (and hence
213 // incur a hidden cost on every copy of this type), you'd have the type *not*
214 // implement `Copy`, but only `Clone`. This makes the cost explicit.