d7cf64af26dd51eeb9eac35def234186dcab7e06
[rust-101.git] / src / part05.rs
1 // Rust-101, Part 05: Clone
2 // ========================
3
4 // ## Big Numbers
5 // In the course of the next few parts, we are going to build a data-structure for
6 // computations with *bug* numbers. We would like to not have an upper bound
7 // to how large these numbers can get, with the memory of the machine being the
8 // only limit.
9 // 
10 // We start by deciding how to represent such big numbers. One possibility here is
11 // to use a vector of "small" numbers, which we will then consider the "digits"
12 // of the big number. This is like "1337" being a vector of 4 small numbers (1, 3, 3, 7),
13 // except that we will use `u64` as type of our base numbers. Now we just have to decide
14 // the order in which we store numbers. I decided that we will store the least significant
15 // digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
16 // Finally, we declare that there must not be any trailing zeros (corresponding to
17 // useless leading zeros in our usual way of writing numbers). This is to ensure that
18 // the same number can only be stored in one way.
19
20 // To write this down in Rust, we use a `struct`, which is a lot like structs in C:
21 // Just a collection of a bunch of named fields. Every field can be private to the current module
22 // (which is the default), or public (which would be indicated by a `pub` in front of the name).
23 // For the sake of the tutorial, we make `dat` public - otherwise, the next parts of this
24 // course could not work on `BigInt`s. Of course, in a real program, one would make the field
25 // private to ensure that the invariant (no trailing zeros) is maintained.
26 pub struct BigInt {
27     pub data: Vec<u64>,
28 }
29
30 // Now that we fixed the data representation, we can start implementing methods on it.
31 impl BigInt {
32     // Let's start with a constructor, creating a `BigInt` from an ordinary integer.
33     // To create an instance of a struct, we write its name followed by a list of
34     // fields and initial values assigned to them.
35     pub fn new(x: u64) -> Self {
36         if x == 0 {
37             BigInt { data: vec![] }
38         } else {
39             BigInt { data: vec![x] }
40         }
41     }
42
43     // It can often be useful to encode the invariant of a data-structure in code, so here
44     // is a check that detects useless trailing zeros.
45     pub fn test_invariant(&self) -> bool {
46         if self.data.len() == 0 {
47             true
48         } else {
49             self.data[self.data.len() - 1] != 0
50         }
51     }
52
53     // We can convert any vector of digits into a number, by removing trailing zeros. The `mut`
54     // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally
55     // change the vector `v`. In this case, we need to make that annotation to be able to call `pop`
56     // on `v`.
57     pub fn from_vec(mut v: Vec<u64>) -> Self {
58         while v.len() > 0 && v[v.len()-1] == 0 {
59             v.pop();
60         }
61         BigInt { data: v }
62     }
63 }
64
65 // ## Cloning
66 // If you have a close look at the type of `BigInt::from_vec`, you will notice that it
67 // consumes the vector `v`. The caller hence loses access. There is however something
68 // we can do if we don't want that to happen: We can explicitly `clone` the vector,
69 // which means that a full (or *deep*) copy will be performed. Technically,
70 // `clone` takes a borrowed vector, and returns a fully owned one.
71 fn clone_demo() {
72     let v = vec![0,1 << 16];
73     let b1 = BigInt::from_vec((&v).clone());
74     let b2 = BigInt::from_vec(v);
75 }
76 // Rust has special treatment for methods that borrow its `self` argument (like `clone`, or
77 // like `test_invariant` above): It is not necessary to explicitly borrow the receiver of the
78 // method. Hence you could replace `(&v).clone()` by `v.clone()` above. Just try it!
79
80 // To be clonable is a property of a type, and as such, naturally expressed with a trait.
81 // In fact, Rust already comes with a trait `Clone` for exactly this purpose. We can hence
82 // make our `BigInt` clonable as well.
83 impl Clone for BigInt {
84     fn clone(&self) -> Self {
85         BigInt { data: self.data.clone() }
86     }
87 }
88 // Making a type clonable is such a common exercise that Rust can even help you doing it:
89 // If you add `#[derive(Clone)]` right in front of the definition of `BigInt`, Rust will
90 // generate an implementation of `Clone` that simply clones all the fields. Try it!
91
92 // We can also make the type `SomethingOrNothing<T>` implement `Clone`. However, that
93 // can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce
94 // the type variable.
95 use part02::{SomethingOrNothing,Something,Nothing};
96 impl<T: Clone> Clone for SomethingOrNothing<T> {
97     fn clone(&self) -> Self {
98         match *self {
99             Nothing => Nothing,
100             // In the second arm of the match, we need to talk about the value `v`
101             // that's stored in `self`. However, if we would write the pattern as
102             // `Something(v)`, that would indicate that we *own* `v` in the code
103             // after the arrow. That can't work though, we have to leave `v` owned by
104             // whoever called us - after all, we don't even own `self`, we just borrowed it.
105             // By writing `Something(ref v)`, we borrow `v` for the duration of the match
106             // arm. That's good enough for cloning it.
107             Something(ref v) => Something(v.clone()),
108         }
109     }
110 }
111 // Again, Rust will generate this implementation automatically if you add
112 // `#[derive(Clone)]` right before the definition of `SomethingOrNothing`.
113
114 // ## Mutation + aliasing considered harmful (part 2)
115 // Now that we know how to borrow a part of an `enum` (like `v` above), there's another example for why we
116 // have to rule out mutation in the presence of aliasing. First, we define an `enum` that can hold either
117 // a number, or a string.
118 enum Variant {
119     Number(i32),
120     Text(String),
121 }
122 // Now consider the following piece of code. Like above, `n` will be a borrow of a part of `var`,
123 // and since we wrote `ref mut`, they will be mutable borrows. In other words, right after the match, `ptr`
124 // points to the number that's stored in `var`, where `var` is a `Number`. Remember that `_` means
125 // "we don't care".
126 fn work_on_variant(mut var: Variant, text: String) {
127     let mut ptr: &mut i32;
128     match var {
129         Variant::Number(ref mut n) => ptr = n,
130         Variant::Text(_) => return,
131     }
132     /* var = Variant::Text(text); */
133     *ptr = 1337;
134 }
135 // Now, imagine what would happen if we were permitted to also mutate `var`. We could, for example,
136 // make it a `Text`. However, `ptr` still points to the old location! Hence `ptr` now points somewhere
137 // into the representation of a `String`. By changing `ptr`, we manipulate the string in completely
138 // unpredictable ways, and anything could happen if we were to use it again! (Technically, the first field
139 // of a `String` is a pointer to its character data, so by overwriting that pointer with an integer,
140 // we make it a completely invalid address. When the destructor of `var` runs, it would try to deallocate
141 // that address, and Rust would eat your laundry - or whatever.)
142 // 
143 // I hope this example clarifies why Rust has to rule out mutation in the presence of aliasing *in general*,
144 // not just for the specific 
145
146 // [index](main.html) | [previous](part04.html) | [next](part06.html)