# Introduction
Hi! I am Ivan Veselov and this website is a collection of notes on different topics which interest me or are otherwise useful.
This site is maintained via [GitBook](https://www.gitbook.com/), its source code is stored in Markdown format on [GitHub](https://github.com/sphynx/notes).
You might be also interested in visiting my other blog/homepage [here.](http://iveselov.info/)
# Programming
# Cheatsheet: Option (in Rust) vs Maybe (in Haskell)
Correspondence of common combinators
This is meant to be for people coming from Haskell to Rust or vice versa who want to quickly find the name of corresponding function on optional values. For example, I keep forgetting the names of Rust combinators. Which one I have to use in a particular situation? Is it `or_else`, `unwrap_or` or`unwrap_or_else`? I can imagine that other people may experience similar problems, hence the cheatsheet. You can find examples and more detailed description in the official documentation by clicking on function names.
**Update 1**: as [/u/jkachmar](https://www.reddit.com/user/jkachmar) points out on Reddit that there is a [`note`](https://hackage.haskell.org/package/errors-2.3.0/docs/Control-Error-Util.html#v:note) function in some of alternative Preludes in Haskell (or in `errors` package), which is an analog of `ok_or` in Rust. Added to the cheatsheet.
**Update 2:** [/u/masklinn](https://www.reddit.com/user/masklinn) says that Haskell `listToMaybe` is akin to calling `next` on an `Iterator` and `maybeToList` is an `Option` implementing `IntoIterator`. I agree with that, since lists in Haskell, being lazy, more or less correspond to Rust iterators. Also, you can iterate over `Option` in Rust by calling `iter`.
**Update 3:** fixed several typos and errors spotted by Reddit readers. Thank you [/u/jroller](https://www.reddit.com/user/jroller/), [/u/jlombera](https://www.reddit.com/user/jlombera/), [/u/gabedamien](https://www.reddit.com/user/gabedamien/), [/u/george\_\_\_\_t](https://www.reddit.com/user/george_____t/)
**Update 4:** use `flatten` from Iterator to implement `catMaybe`, thanks to [/u/MysteryManEusine](https://www.reddit.com/user/MysteryManEusine/).
### Cheatsheet
| Haskell | Rust | Purpose | Type (Haskell style) |
| ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------- | ------------------------------------------ |
| [Maybe](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#t:Maybe) | [Option](https://doc.rust-lang.org/std/option/enum.Option.html) | type name | |
| [Just](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:Just) | [Some](https://doc.rust-lang.org/std/option/enum.Option.html#variant.Some) | constructor for value | `a -> Maybe a` |
| [Nothing](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:Nothing) | [None](https://doc.rust-lang.org/std/option/enum.Option.html#variant.None) | constructor for no value | `Maybe a` |
| [isJust](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:isJust) | [is\_some](https://doc.rust-lang.org/std/option/enum.Option.html#method.is_some) | check if has value | `Maybe a -> Bool` |
| [isNothing](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:isNothing) | [is\_none](https://doc.rust-lang.org/std/option/enum.Option.html#method.is_none) | check if has no value | `Maybe a -> Bool` |
| [fmap](https://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Functor.html#v:fmap) from Functor | [map](https://doc.rust-lang.org/std/option/enum.Option.html#method.map) | apply function to value inside | `(a -> b) -> Maybe a -> Maybe b` |
| [fromJust](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:fromJust) | [unwrap](https://doc.rust-lang.org/std/option/enum.Option.html#method.unwrap) | extract a value, fail if there is none | `Maybe a -> a` |
| [fromMaybe](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:fromMaybe) | [unwrap\_or](https://doc.rust-lang.org/std/option/enum.Option.html#method.unwrap_or) | extract a value or return a given default | `a -> Maybe a -> a` |
| [(>>=)](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Monad.html#v:-62--62--61-) from Monad | [and\_then](https://doc.rust-lang.org/std/option/enum.Option.html#method.and_then) | propagate "no value", apply a function to a value, function can return no value too | `Maybe a -> (a -> Maybe b) -> Maybe b` |
| [(<\|>)](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Applicative.html#v:-60--124--62-) from Alternative | [or](https://doc.rust-lang.org/std/option/enum.Option.html#method.or) | return first value if present or second if not | `Maybe a -> Maybe a -> Maybe a` |
| [(>>)](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Monad.html#v:-62--62-) from Monad | [and](https://doc.rust-lang.org/std/option/enum.Option.html#method.and) | return first value if none or second if not | `Maybe a -> Maybe b -> Maybe b` |
| [maybe](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:maybe) | [map\_or](https://doc.rust-lang.org/std/option/enum.Option.html#method.map_or) | takes function and default. Apply function to the value or return default if there is no value | `b -> (a -> b) -> Maybe a -> b` |
|
| [ok\_or](https://doc.rust-lang.org/std/option/enum.Option.html#method.ok_or) | transforms optional value to possible error | `b -> Maybe a -> Either b a` |
| [mapMaybe](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:mapMaybe) | [filter\_map](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.filter_map) from Iterator | applies filter and map simultaneously | `(a -> Maybe b) -> [a] -> [b]` |
| [catMaybe](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Maybe.html#v:catMaybe) | [flatten](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.flatten) from Iterator | extracts only values from the list, drops no values | `[Maybe a] -> [a]` |
| [join](https://hackage.haskell.org/package/base-4.12.0.0/docs/Control-Monad.html#v:join) from Monad | [flatten](https://doc.rust-lang.org/std/option/enum.Option.html#method.flatten) | squashes two layers of optionality into one | `Maybe (Maybe a) -> Maybe a` |
| [sequence](http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-Traversable.html#v:sequence) from Traversable | [transpose](https://doc.rust-lang.org/std/option/enum.Option.html#method.transpose) | transposes Option and Result layers (or Either and Maybe in Haskell terms) | `Maybe (Either e a) -> Either e (Maybe a)` |
### Notes
In Rust, all combinators with `or` at the end have a variant with `or_else` at the end: `unwrap_or_else` or `or_else` etc. Those variants take a closure for the default value and are lazily evaluated. They are recommended when you have a function call returning default value. In Haskell there is no need for this, since it is a lazy language by default.
In Rust there are many different ways for extracting the optional value:
* `unwrap` which just fails if there is no value
* `unwrap_or` which provides a default for that
* `unwrap_or_else` where this default is calculated by a closure
* `unwrap_default` where default is taken from `Default` trait implemented on the type
* `unwrap_none` which fails if the value is **not** `None` and returns nothing
* `expect` which is the same as `unwrap`, but takes a custom error message
* `expect_none` which is the same as `unwrap_none` but takes a custom error message
Another very useful method in Rust is `as_ref` which converts from `&Option` to `Option<&T>` which is very handy for pattern matching. `as_mut` plays a similar role for mutable references.
In Rust there are several methods related to ownership of the value in the `Option`, like `take` and `replace`, they have no analogs in Haskell that does not have the ownership concept.
In Rust we sometimes want to copy or clone values, it's possible to do so on optional references (`Option<&T>`) to get `Option` from those by cloning or copying the referenced value. There are `copied` and `cloned` methods for this.
It's possible to mutate optional values in Rust. For that we have `get_or_insert` and `get_or_insert_with` methods which allow to insert a new (possibly computed) value into `None` or just use the value which was there.
`transpose` method in Rust is interesting, since it reminds me of `sequence` from `Traversable` in Haskell. It basically transpose two layers: `Result` (or `Either` in Haskell) and `Option`. `sequence` in Haskell does approximately the same, but in a more generic fashion.
In addition to `and` and `or` Rust has a method `xor`, perhaps just for the completeness. You've probably guessed that it returns `Some` if and only if there is only one `Some` in its arguments.
Haskell has two functions `listToMaybe` and `maybeToList` that convert between trivial lists (with 0 or 1 elements) and `Maybe` values. Rust doesn't have those, since lists are not that ubiquitous, but see the Update 2 above.
### Summary
Rust has more functions to work with `Option` than Haskell because it has to support references, mutability and ownership. On the other hand Haskell outsources some of the combinators to its generic typeclasses: `Semigroup`, `Alternative`, `Monoid`etc. so its combinator library seems thinner.
# printf() and floating point numbers
Help! My printf is producing digits out of thin air!
### Problem setup
One day we had a certain mismatch between two floating point numbers. One number when inspected in an IDE looked much longer than the other, having lots of extra digits. Then a colleague of mine said that it's fine, they might still be the same number, and produced some code similar to this:
```c
#include
int main(void)
{
double d = 0.1234567890123456; // 16 digits
printf("%.16f\n", d);
printf("%.55f\n", d);
return 0;
}
```
What do you think it will print? Most programmers know that double precision has about 16 significant decimal digits when numbers are in that range (i.e between 0 and 1). So I am printing here 16 digits first and then some more just to see what comes next. It prints this:
```bash
➜ gcc 1.c && ./a.out
0.1234567890123456
0.1234567890123455941031593852130754385143518447875976562
```
This looked like quite a lot of extra digits and it did not even stop there!
I know that we represent real decimal numbers with bits stored according to IEEE 754 floating point standard, so our decimal literal is somewhat imprecisely stored in binary representation. Now it looks like `printf` is printing that decimal representation. However, what was surprising to me is that this imprecise representation can be expanded to so many new decimal digits.
**TL;DR** `printf` prints decimal expansion of the binary number corresponding to our original literal. That binary number approximates the literal. There can be maximum `53 - binary exponent` digits in the decimal expansion (at least for "normal" numbers less than 1). Read below for the details.
### Plan of attack
Let's figure out step by step what's happening in this little program. The interesting steps with accompanying questions I had are as follows:
1. C compiler has to convert that string representing a decimal C-literal into a double. How that should be done? Are there any restrictions on the literal length?
2. That double is represented with some bits. What bits exactly? How they are laid out in memory? Can I build them by hand?
3. Those bits can be converted back to decimal and printed with `printf`. How many digits can I expect in this decimal expansion?
Let's first address the representation question, then we'll have terminology to discuss parsing of the literals and finally converting back to decimal with `printf`.
### Representing doubles with IEEE 754
I assume that you more or less know what a floating number is. As a quick reminder, it's a number which is represented as follows: `sign * significand * (base ^ exponent)`
* *Sign* here can be either -1 or 1.
* *Significand* (also called *mantissa*) always starts with '**1.**' (note the dot at the end!). Since it always starts with 1, there is no need to store that 1 in actual bit representation when we get to it.
* *Base* is 2 in our case.
* *Exponent* is a scaling factor, it is the number of positions we have to move the point "." to the right or to the left to get back to our number.
For example binary 101.1 can be represented as `1 * 1.011 * (base ^ 2)`, sign is 1, significand is 1.011 and we need to scale it two positions to the right, so exponent is `+2`.
In order to convert a real decimal number into bits of `double` we can do the following steps.
#### 1. Get exact binary representation of the decimal number we are trying to convert.
It will most likely contain the repeating fractional part unless it can be represented as `P / Q` where `Q` is an exact power of 2 and `P` is an integer.
In our case `0.1234567890123456` corresponds to this binary (I calculated it with [online converter](https://www.exploringbinary.com/binary-converter/)):
`0.0001111110011010110111010011011101000110111101100101100101101100110...`
We haven't even got to the repeating part, but that's alright since we only need the beginning.
#### 2. Take 53 bits starting from the first digit 1 (and including it).
This is because IEEE 754 double has 53 bits of precision. You can look up those numbers in corresponding Wikipedia table.
So we take this 53-bits long part in the middle:
`0.000 11111100110101101110100110111010001101111011001011001 011011...`
If the next bit after those 53 is `1` we should also add `1` to that large part for rounding purposes. In our case it's `0` so we are fine.
#### 3. Figure out what the exponent should be.
Our first `1` is 4 positions to the right from the binary point. So in our case the exponent will be `-4`. However, in IEEE 754 exponents are stored with a particular bias which has to be added before we store it in bits. For double precision this bias is 1023, so we have to add that to -4 getting `1019` which we need to store as unsigned integer in 11 bits of exponent (those numbers can also be taken from the table above). Why to store the exponent with a bias and not as "sign + absolute value" or "two complement"? The main reason that with this way we can use integer comparator to compare floating-point numbers. Also, it leads to a nice zero representation with all 0 bits. See [here](https://en.wikipedia.org/wiki/Exponent_bias) for the details.
#### 4. Combine the parts
The memory layout for doubles is as follows (assumes Big Endian order):
Our number is positive, so we use `0` for sign. Exponent is `1019` which is `01111111011` if represented with 11 bits. And we've got our 53 precision bits of the significand which we need to pack into 52 bits. This is easily done, since the first bit is always 1, so we never store it (it's called "hidden" or "implicit" bit). In the end we get this:
`0 01111111011 1111100110101101110100110111010001101111011001011001`
which should be 64 bits representing our double `0.1234567890123456` in memory! Whoa, that was a lot of work. Let's check if we did it right with some Rust code (it's easier to print bits in Rust than in C):
```rust
fn main() {
let d: f64 = 0.1234567890123456;
d.to_be_bytes().iter().for_each(|b| print!("{:08b}", b));
println!();
}
```
When we run this we get exactly the bits we calculated before, success!
```bash
➜ rustc a.rs && ./a
0011111110111111100110101101110100110111010001101111011001011001
```
### Literals conversion
Now we have the terminology to tackle the next question: how C literals from the program are parsed into doubles? Are there any limitations on length? What if I write a very long literal:
`double d = 1.111111111111111111111111111111111111111111111111;`
Will it fail? How many ones will be preserved?
Apparently, according to this StackOverflow [answer](https://stackoverflow.com/a/649108/211906) and [C99 standard](http://c0x.coding-guidelines.com/6.4.4.2.html), there are no limitations on length of double literals (at least I don't see it in the grammar and I can use literals with thousands digits and it compiles just fine). The double representation we'll get should be the closest representable number or one before or after it, depending on the implementation. So yes, you can use literals like 0.123456789012345678901234567890 with 30 digits, but most of those digits would be wasted since it's too precise to be represented in double precision format.
To quote from C99 standard:
> For decimal floating constants \[...] the result is either the nearest representable value, or the larger or smaller representable value immediately adjacent to the nearest representable value, chosen in an implementation-defined manner.
### Conversion back to decimal with printf
Now let's see what happens with that `printf`. It takes all those bits we used for binary representation, converts it back to exact decimal and prints it with specified precision.
How long we can expect the decimal representation to be, i.e. how many digits does it have before starting the string of zeroes at the end?
Originally I thought that since we have 53 binary digits in significand (mantissa) for numbers close in scale to 1 (with exponent = 0), the smallest number we can represent is about $$2^{-53} \approx 10^{-16}$$ And I thought that it should mean that we should have approximately 16 digits or slightly more in the decimal representation of those bits and if we ask for more we should get zeros. But that is not true. To get an idea why, we can just look at $$2^{-3}$$ which is 0.125. It has 3 digits after the point in its decimal expansion, even though it's very close to $$10^{-1}$$ and by reasoning above should have about 1 or "slightly more" digits.
Let's look at the table of decimal expansions for $$1 / 2^i$$ values for consecutive `i`s. This corresponds to the value of `i`-th bit in the significand.
| Bit number | Fraction | Decimal expansion |
| ---------- | -------- | ----------------- |
| Bit 1 | 1 / 2 | 0.5 |
| Bit 2 | 1 / 4 | 0.25 |
| Bit 3 | 1 / 8 | 0.125 |
| Bit 4 | 1 / 16 | 0.0625 |
| Bit 5 | 1 / 32 | 0.03125 |
| Bit 6 | 1 / 64 | 0.015625 |
It looks like every new bit adds a new digit to the decimal! So, if we have 53 bits in the significand, we can have up to 53 digits in the decimal expansion! (For now we disregard the exponent, which can be just zero for those examples).
Let's prove that $$1 / 2^n$$has n digits after the point in its decimal representation. My friend [Igor](http://www.chornous.com/) suggested a nice and easy proof by induction! Basis is always easy: 1/2 = 0.5 and it has 1 digit. Then let's assume by induction hypothesis that $$1/2^n$$ has $$n$$ digits and let's see what happens with $$1/2^{n+1}$$. This is just $$1/2^n$$ divided by $$2$$, and so for every of n digits of the original number we'll have a corresponding digit in the new number (divided by two with truncation and carry-over to the right) plus an extra digit for the last "5" (since it is odd and no carry-over will fix that). Illustration:
```bash
.125
----- / 2
.0625
```
Proving that it always ends with 5 can also be done by induction: every 5 at the end leads to another 5 when divided by 2 and we start with 5 for the basis.
And since $$1/2^n$$is the finest unit of precision for n-bit number we can be sure that other higher bits are "coarser", i.e. that they will have less decimal digits in their individual representation.
So now we can see that it's completely fine to have so many digits from `printf` and we also have an upper bound on them. For example in our case we should expect no more than 53 + 4 digits after the point. "+4" because we use `-4` exponent, which can add more digits. Indeed, if we add some more precision to our original program, we can see that decimal representation of our double has 56 digits (and zeros after that):
```bash
➜ printf "%.60f\n" 0.1234567890123456
0.123456789012345594103159385213075438514351844787597656250000
```
### References and further reading
* A [tool](https://float.exposed/) to explore floating point numbers, where you can toggle bits and see how it affects the value, inspect decimal representations and do many other things
* A very readable and well written article on Wikipedia: ["Floating-point arithmetic"](https://en.wikipedia.org/wiki/Floating-point_arithmetic)
* ["Floating point guide"](https://floating-point-gui.de/) if you don't want to overload yourself with details and want easy answers
* A famous long article ["What Every Computer Scientist Should Know About Floating Point Arithmetic."](https://cr.yp.to/2005-590/goldberg.pdf) if you **want** to overload yourself with details and want rigorous answers
# More advanced aspects of pattern matching in Rust
\`ref\` keyword, match ergonomics, box patterns, references patterns and other interesting stuff
## Introduction
In Haskell, pattern matching is mostly nice and easy. It might be made more complicated by strictness annotations (i.e. whether to evaluate sub-patterns lazily or strictly) or irrefutability annotations, but it doesn't have any special interactions with ownership, borrowing and mutability which are bread and butter of Rust. So, naturally, pattern matching in Rust has additional complexity which I want to investigate here. Interestingly enough, some of this material is not covered by current edition of the Rust Book.
The plan of attack is as follows:
* Reference patterns: things like `let &x = &1`
* `ref` keyword: what's the difference between using `Some(ref x) =>` and `Some(&x) =>` in patterns? Maybe no difference?
* So called "match ergonomics": what the Rust compiler does under the hood to make our lives easier? (and maybe less predictable?)
* Box patterns: things like `box (x, y) =>` in patterns
* Other useful auxiliary notes: binding modes, patterns (ir-)refutability, auto dereferencing, printing types for debugging purposes, etc.
## Reference patterns
As the Rust Book tells us, `match` is not the only place where pattern matching occurs. It also happens in many other places: `let`, `if let`, `while let`, `for`, function arguments, etc. Even a simple `let x = 1` exhibits pattern matching: we match 1 against pattern `x`. This is called the *identifier pattern* and it never fails, hence it is called a *irrefutable pattern*. We must use irrefutable patterns with function parameters, `let` statements, and `for` loops. If we try to write something like `let Some(x) = Some(1)`, it will fail to compile since the match could fail and we aren't covering all the cases. A pattern which may fail is called a *refutable pattern*. I am reminding you about those `let` patterns here just because it's easier to use them in examples rather than in a fully fledged `match` even though such examples may feel more contrived.
Let's move to the next class of patterns called *reference patterns*. It's a pattern starting with one or two `&`'s like this: `let &y = &1`. After that we can use `y` and its value would be 1, no surprises:
```rust
fn test() {
let x = 1;
print_type!(x);
println!("x: {}", x);
let &y = &1;
print_type!(y);
println!("y: {}", y);
}
```
When run it prints:
```
type of x: i32
x: 1
type of y: i32
y: 1
```
A quick aside: here I am using a little helper for printing types which uses the `std::any::type_name::()` function from stable Rust. This is useful for investigating pattern matching, auto-dereferencing, and other situations when the compiler may do something strange and the type might not be clear from context:
```rust
fn print_type_of(msg: &str, _: &T) {
println!("type of {}: {}", msg, std::any::type_name::())
}
macro_rules! print_type {
( $x:expr ) => {
print_type_of(stringify!($x), &$x)
}
}
```
Okay, back to reference patterns. When do we use this kind of pattern? It's used for dereferencing pointers which are being matched. Or you can say that they are used to "destructure" the pointer. For example, let's look at a common idiom for mapping a function with an iterator: `xs.iter().map(|&x| x + 1).collect()`. Note how we use the `&x` pattern here to dereference (deconstruct) the pointer returned by the iterator. We can also use `map(|x| *x + 1)` for that, making dereference explicit, but I prefer the first variant since one can immediately see from the `&x` pattern that a parameter is a reference without looking at its usage. I've run a quick `grep` over Rust standard library looking for iter/map combinations and it feels like the first variant is more popular when we need to dereference, but it's probably a matter of taste.
An exercise for the reader: what error message do you expect if you try `let &x = 1`?
## Binding modes and \`ref\` keyword
When we pattern match some expressions against patterns, for example `let x = y`, we have several options with respect to binding modes.
A *binding mode* determines how values are bound to identifiers in patterns. The default binding mode is to move, i.e., we just move those values: `y` is moved into `x` and we can't use it again. If `y` implements the `Copy` trait then we copy. Those two binding modes are normally called *binding by value*. There is also *binding by reference*, which is introduced with `ref` keyword attached to an identifier pattern like this: `let ref x = y`. This means that we want to borrow `y` instead of moving/copying it, so `x` will be a reference. It is exactly the same as `let x = &y`. For mutable reference there is `ref mut`, i.e., `let ref mut x = y` which is the same as `let x = &mut y`.
{% hint style="info" %}
A thing to remember. Those two statements are identical:
`let ref x = y;`
`let x = &y;`
{% endhint %}
Now the question is: if `ref` is just a funky way of saying that you want to borrow, why is it needed? Is just using `&` not enough? `ref` becomes more useful when used in nested patterns.
When I first saw `ref` in Rust code, I thought that it was an antiquated way of borrowing, a remnant from previous Rust versions. It is indeed so, mostly because of the feature called "match ergonomics" which we look into in the next section. This feature mostly obsoleted the need for `ref` and so in modern Rust using `ref` is rarely needed, but no doubt you'll see it a lot in existing codebases. I think it's easy to understand it better by contrasting with other patterns. Let's say we pattern match on an Option with `match`
Then the difference between `Some(ref y) =>` and `Some(&y) =>` in patterns is that the first borrows whatever is in `Some` and the second dereferences the pointer in Some (remember that we've already covered reference patterns in previous section).
The difference between `Some(ref y) =>` and some `Some(y) =>` is that in the first case we borrow and in the second case we move/copy into `y`.
## Match ergonomics
In older versions of Rust (up to [1.26](https://blog.rust-lang.org/2018/05/10/Rust-1.26.html) which was released in May 2018) when you had a reference to Option and wanted to pattern match against it, your life was hard. You had two choices:
* Use reference patterns and `ref` because: a) you needed to match references with reference patterns b) you had to use `ref` because you couldn't move part of Option into `s`, since you only had a borrowed version of Option:
```rust
fn f(x: &Option) {
match x {
&Some(ref s) => // do something with `s`
&None => {}
}
}
```
* Dereference the Option pointer and still use `ref` for the same reasons as in (1).
```rust
fn f(x: &Option) {
match *x {
Some(ref s) => // do something with `s`
None => {}
}
}
```
Both of those choices were unsatisfactory and too verbose for such a common operation. Hence, RFC-2005 "Match Ergonomics" has been proposed and implemented. It allowed one to just write the following code, without `ref` and reference patterns:
```rust
fn f(x: &Option) {
match x {
Some(s) => // do something with `s`
None => {}
}
}
```
It works like this: it sees that `x` is a *reference* which is matched by *non-reference* patterns. Therefore it automatically dereferences `x` and uses appropriate binding modes for identifiers in that pattern, in this case "bind by reference". In other words, it automatically inserts `ref` for you, since it's the only sensible thing to do in this situation.
You can learn more details in the [original RFC](https://github.com/rust-lang/rfcs/blob/master/text/2005-match-ergonomics.md), it's amazingly readable and has nice motivating examples and links (actually I've stolen my example from there). Here is a memorable quote from that RFC:
> Match expressions are an area where programmers often end up playing 'type Tetris': adding operators until the compiler stops complaining, without understanding the underlying issues. This serves little benefit - we can make match expressions much more ergonomic without sacrificing safety or readability.
## Case study: tree traversal
Let's start with a case study which actually led me to writing this note. Say I want to implement a data structure for full binary trees (i.e. each node has either 0 or 2 children) and traverse it recursively. Of course I'll need pattern matching for that! Armed with our knowledge from previous sections it now seems like an easy task:
```rust
struct T {
data: u8,
children: Option>,
}
fn traverse(s: &T) {
match &s.children {
None => {}, // TODO: do something
Some(ch) => {
traverse(&ch.0);
traverse(&ch.1);
}
}
}
```
I'll additionally comment on some relatively subtle points to make sure we understand what's going on in this example.
First, what is the type of `s.children`? It is a little bit non-obvious, since `s` is a reference and the we have a field accessor. Knowing that Rust likes to do things automatically for us, we may suspect that something "auto-" is happening here. Indeed, here we have an example of auto-dereferencing. If the left hand side of `.` operator is a pointer, it's dereferenced as many times as needed to get access to the field, as described [here](https://doc.rust-lang.org/reference/expressions/field-expr.html). So basically `s.children` is equivalent to `(*s).children`. And therefore its type is `Option>`.
Next, since we only have a reference to `T` and can't move out of it (and don't want to) we need to match a reference to `s.children` (as opposed to `s.children` itself) to kick-in the match ergonomics process. Note that we don't need `&` before `None` and `Some` or `ref` keyword.
Then what is the type of `ch` when it is bound? Remember that we bind by reference here, so it is `&Box<(T, T)>`. You can easily check it with `print_type!` macro listed above.
Now we want to recur and to get access to our tuple which is hidden behind two references (`&` and `Box`). Auto-dereferencing to the rescue! We can just say `ch.0` and this will add \*\* automatically. Finally, we need to borrow that with `&`: this operator has lower precedence than field accessors, so `&a.b` is identical to `&(a.b)` In order to appreciate how much "auto-" is happening here let's look at the fully parenthesised unambiguous analog of `&ch.0` (it even broke my Markdown renderer!):
```rust
&((**ch).0)
```
## Box patterns
Finally, let's look if we can make previous code slightly nicer by further binding the tuple elements to names like `(left, right)`. How do we do this?
```rust
Some(ch) => {
// type of ch: &Box<(T, T)>
//
// and we want bind it to something like (left, right)
}
```
Being emboldened by impressive deductive powers of match ergonomics we quickly type the following code and expect it to work:
```rust
Some((left, right)) => {
traverse(left);
traverse(right);
}
```
After all, we have a reference and we match it against a non-reference tuple pattern, so match ergonomics should auto-dereference twice and use appropriate binding modes for `left` and `right`. But not so fast: unfortunately, match ergonomics only works for ordinary references and we have a `Box` there! So, we have two options: either use `box_patterns` feature from unstable Rust or wait for match ergonomics starting to work for anything implementing `Deref` including Boxes as discussed [here](https://github.com/rust-lang/rust/issues/29641#issuecomment-360574042).
Solution with `box_patterns` looks like this:
```rust
#![feature(box_patterns)]
struct T {
data: u8,
children: Option>,
}
fn traverse(s: &T) {
match &s.children {
None => {},
Some(box (left, right)) => {
traverse(left);
traverse(right);
}
}
}
```
And the tracking issue for `box_patterns` feature along with interesting discussions on the subject can be found [here](https://github.com/rust-lang/rust/issues/29641).
This note is already getting too long, so there won't be any summary or references section: enjoy the ergonomics!
# time\_it: a Case Study in Rust Macros
My adventures in Declarative Macros Land
### Problem setup
One day I wanted to quickly print for how long certain pieces of code run without setting up the whole profiling business.
I used [`std::time::Instant`](https://doc.rust-lang.org/std/time/struct.Instant.html) for that, it's nice and easy and gives access to monotonic clock on your OS:
```rust
let timer = std::time::Instant::now();
let x = do_stuff();
println!("do_stuff: {:?}", timer.elapsed());
// Output:
// do_stuff: 2.12s
```
Then I thought that it would be convenient to have a macro `time_it` which I can use to wrap any statement, block of code or even many statements and measure their timings. I had in mind something like context managers in Python, where you can do this:
```python
with Timer("part 1"):
do_a()
do_b()
do_c()
```
Context managers can "automatically" run some code before starting evaluation of that block (e.g. start a timer) and do something after leaving the block (e.g. stop the timer and print elapsed time).
So, let's try to declare a macro in Rust which does something similar. My goal is to be able to annotate the code with `time_it!` macro in the least intrusive way (ideally without changing the measured lines at all).
### Macro for timing a single statement
```rust
macro_rules! time_it {
($context:literal, $s:stmt) => {
let timer = std::time::Instant::now();
$s
println!("{}: {:?}", $context, timer.elapsed());
};
}
// Let's test it:
fn main() {
time_it!("println", println!("hello, world!"));
let x = 1;
time_it!("let", let _y = x + 2);
}
/* This will print:
hello, world!
println: 31.143µs
let: 43ns
*/
```
So far so good. I'm giving `time_it` a context: string literal to describe what we measure and one statement and it prints timings nicely (even with fancy Greek letters in "µs" for microseconds!).
However, even this simple macro contains several things which puzzled me and didn't work as expected.
### First nuance: \`stmt\` fragment specifier and semicolons
The first thing is that statement argument of the macro does not have a trailing semicolon, which is not ideal, since when I'm wrapping an existing statement terminated with a semicolon I have to remove it:
```rust
// before:
println!("x"); // must be terminated with a semicolon
// after wrapping:
time_it!("println",
println!("x") // <- no semicolon here
)
```
What happens if I leave the semicolon in the macro argument? It fails with this error:
```rust
time_it!("println",
println!("hello, world!"); // with semi-colon
);
error: no rules expected the token `;`
--> src/main.rs:31:50
|
1 | macro_rules! time_it {
| -------------------- when calling this macro
...
31 | time_it!("println", println!("hello, world!"););
| ^ no rules expected this token in macro call
```
What's going on here? Isn't semicolon supposed to be an integral part of the statement? If so, it should be consumed by `$s:stmt` without any problem... However, it turns out that no, in [Rust reference](https://doc.rust-lang.org/reference/macros-by-example.html) it's said that `stmt` fragment specifier works like this:
> `stmt`: a [*Statement*](https://doc.rust-lang.org/reference/statements.html) without the trailing semicolon (except for item statements that require semicolons)
Hm, ok. I'm not actually sure which item statements requiring semicolons are meant here, but it looks like `println!(...)` or `let _y = x + 1` is not one of them.
### Second nuance: no semicolon in the expansion: \`$s\`
Another thing about semicolons is that `$s` in the macro expansion part does **not** have a trailing semicolon. If I put a semicolon there (i.e. write `$s;`) the compiler will complain:
```rust
macro_rules! time_it {
($context:literal, $s:stmt) => {
let timer = std::time::Instant::now();
$s; // <- now I'm adding a semicolon here
println!("{}: {:?}", $context, timer.elapsed());
};
}
warning: unnecessary trailing semicolon
--> src/main.rs:19:11
|
19 | $s;
| ^ help: remove this semicolon
...
31 | time_it!("println", println!("hello, world!"));
| ----------------------------------------------- in this macro invocation
|
= note: `#[warn(redundant_semicolon)]` on by default
```
This looks strange again: if `$s` matched our tokens without trailing semicolon, won't it be logical to add that semicolon in the expansion part to compensate?
The reason that it doesn't work like that is as follows. When we expand the macro, matched `$s` is not a token stream anymore! Since its tokens have been fully matched by `stmt` specifier, it's now a fully formed AST statement node! As you probably know, macro expansion in Rust happens not after the lexical stage (as it does with `#define`in C), but after the parsing stage, i.e. when we have a parsed abstract syntax tree of the program. That's the reason why we can use all those nice specifiers like `expr` , `stmt` and so on: we have access to the syntactic information. This is [very well explained](https://danielkeep.github.io/tlborm/book/mbe-syn-source-analysis.html) in "The Little Book of Rust Macros".
Therefore, when we plug `$s` it's already a fully formed statement and adding an extra semicolon feels redundant to the compiler, so it complains.
### Handling multiple statements
Ok, now let's say we want to wrap several statements in `time_it`. I've tried several approaches before making it work.
### With block specifier
My first naive attempt was to use `block` specifier (since I didn't want to deal with all those nasty semicolons):
```rust
($context:literal, $b:block) => {
let timer = std::time::Instant::now();
$b
println!("{}: {:?}", $context, timer.elapsed());
}
fn main() {
time_it!("two println", {
println!("- hello, world!");
println!("- hi, programmer!");
});
}
- hello, world!
- hi, programmer!
two println: 35.549µs
```
Again, it looks good at first glance. But there is a problem with scoping. If you had `let` assignments in the original code and wrapped them in the block just to pass it to `time_it` - it's not possible to use them again, since the scope has changed:
```rust
// Before:
fn main() {
let x = 1;
let y = 2;
let z = x + y;
println!("z = {}", z);
}
// After:
fn main() {
time_it!("let", {
let x = 1;
let y = 2;
let z = x + y;
});
println!("z = {}", z);
}
// Error:
error[E0425]: cannot find value `z` in this scope
--> src/main.rs:42:24
|
42 | println!("z = {}", z);
| ^ not found in this scope
```
Not good. Let's try to use macro repetitions feature to actually say that we want multiple statements.
### With \`stmt\` repetitions
```rust
macro_rules! time_it {
($context:literal, $($s:stmt);+) => {
let timer = std::time::Instant::now();
$(
$s
)*
println!("{}: {:?}", $context, timer.elapsed());
}
}
fn main() {
time_it!("let",
let x = 1;
let y = 2;
let z = x + y
);
println!("z = {}", z);
}
// Output:
// let: 206ns
// z = 3
```
Now I know that `stmt` are parsed without trailing semicolon, so I'm just using this semicolon as a separator in a repetition: `$($s:stmt);+`. Here I say that I want one or more statements separated by semicolons. Also, I don't use any semicolons after `$s` in the expansion part due to the same reasons as before.
It works almost perfectly, but note that the last statement `let z = x + y` still can't have a trailing semicolon when wrapped. That's expected, because it's the last one and repetitions syntax only allows separators **between** the items, not after the last one. One way to fix this is just to add that last semicolon explicitly: `$($s:stmt);+ ;` It works fine, because semicolons are allowed after `stmt` specifier (not all symbols are, only `;` `,` and `=>` ), see ["Follow-set Ambiguity Restrictions"](https://doc.rust-lang.org/reference/macros-by-example.html#follow-set-ambiguity-restrictions) in Rust reference for details.
**UPDATE:** Another option suggested by several people on Reddit is to use a question mark for zero or one repetition of the semicolon at the end like this: `$($s:stmt);+ $(;)?` Note that repeating groups do not necessarily need to contain bindings, e.g. here we just repeat semicolon tokens without capturing them.
### With \`tt\` specifier
Another way of achieving this would be to use a sledgehammer of Rust declarative macros: `tt` specifier. This just matches any token tree. What is a token tree? It's either a single token or a group of any number of token trees wrapped in `()`, `[]` or `{}`. So we can just say: take many arbitrary token trees, prepend `Instant` creation to that, paste all the tokens and then print elapsed time:
```rust
($context:literal, $($tt:tt)+) => {
let timer = std::time::Instant::now();
$(
$tt
)+
println!("{}: {:?}", $context, timer.elapsed());
}
```
This also works and doesn't require any special treatment of semicolons, but is probably overly generic, allowing more token types than we actually want to allow.
### Summary
I hope this exposed and clarified some nuances of working with Rust declarative macros. There are lots of other interesting nuances when one digs deeper. An interesting and illuminating reading about that is ["The Little Book of Rust Macros"](https://danielkeep.github.io/tlborm/book/README.html) which I recommended above. It's a little bit dated but still a very good read. And of course, Rust reference itself has an[ informative section](https://doc.rust-lang.org/reference/macros-by-example.html) on macros.
# Rust Closures: Returning \`impl Fn\` for \`move\` closures
## Problem setup
Recently I've had to write some `nom` code (it is a parser combinator [library](https://docs.rs/nom/5.1.1/nom/) for Rust). To my surprise I discovered that there is no combinator for creating a parser which always succeeds returning a certain given value. At least not without using macros which is [discouraged](https://github.com/Geal/nom/blob/master/doc/upgrading_to_nom_5.md#from-macros-to-functions) in nom v5. That combinator would be something like `pure` in Haskell Parsec. It's not very useful on its own, but can be used as part of other combinators, say providing a default alternative for `alt`.
So I decided to add `success` to nom. After looking at the library code, I realised that it uses closures quite heavily and I didn't use them much in Rust, so I had some questions. Here is my version of `success` basically copy-pasted from a similar combinator `value`:
```rust
pub fn success>, O: Clone, E: ParseError>(val: O) -> impl Fn(I) -> IResult
{
move |input: I| {
Ok((input, val.clone()))
}
}
```
That type signature looks a little scary, eh? However, since we are not going to focus on `I` or `E` arguments here (input and error types), we can just rewrite it like this, omitting irrelevant details:
```rust
pub fn success(val: O) -> impl Fn(I) -> IResult
{
move |input: I| {
Ok((input, val.clone()))
}
}
```
## Questions
I had three questions here:
1. Why do we need to clone `val`? After all it looks like l I have a value and just want to pass the ownership to the parser, no need to clone anything.
2. Why we have `move` closure, but return type of the function is `impl Fn(something)` and not `impl FnOnce(something)` I thought that when we use `move` then we move the captured environment into the closure and `FnOnce` trait matches that behaviour.
3. Can we omit `move` or change the type to `FnOnce` or remove `Clone` i.e. to remove any of those things which I didn't understand and still make it work? Are they actually necessary?
**TL;DR** `move` determines how captured variables are **moved** into the returned closure. Then returned `impl Fn/FnMut/FnOnce` puts restrictions on how they are **used** inside that closure (which in turn defines whether the closure can be used once or more). We can `move` into closure but still only use the captured values by reference and return `impl Fn` to allow multiple calls of the returned closure. And yes, everything in the code above was necessary :)
## More detailed answers
I assume here that you know the basics about closures. If not, you can read a corresponding chapter in the Rust book. Also, on top of that I would recommend reading Steven Donovan's post ["Why Rust Closures are (Somewhat) Hard"](https://stevedonovan.github.io/rustifications/2018/08/18/rust-closures-are-hard.html).
That post (and Rust reference) tells you that a closure basically corresponds to an anonymous structure of some concrete but unknown type which has fields corresponding to the captured variables. The capture mode of those fields (i.e. whether they are `&T`, `&mut T` or `T`) is determined by the usage of the captured variables inside the closure. Or it can be forced to be `T`, i.e. to passing the ownership to the closure, by using `move` keyword.
I'll repeat the code above for your convenience:
```rust
pub fn success(val: O) -> impl Fn(I) -> IResult
{
move |input: I| {
Ok((input, val.clone()))
}
}
```
So, in our case we implicitly have the following structure for our `move` closure, it only captures a single variable `val` of generic type `O`:
```rust
struct ClosureType {
// where it's O, &O or &mut O is defined by
// `val` usages in the closure and presence of `move` keyword
val: O;
}
```
Then we know that this closure should implement `Fn` trait, since this is what is returned from `success` function. As described in the [documentation](https://doc.rust-lang.org/std/ops/trait.Fn.html), it will look like this (note the helpful comment):
```rust
impl Fn for ClosureType {
type Output = IResult;
// This `&self` here is because we implement Fn, not FnOnce!
// In FnOnce it would be `self`, owning the structure fields.
fn call(&self, input: I) -> Output {
Ok((input, self.val.clone()));
}
}
```
Now we can answer our **question 1**: why do we have to clone? If we didn't clone, we would be moving out of `self.val` which is behind a reference. So we can't do that for `Fn`.
Another way of resolving this issue (i.e. if we don't want to clone) would be to use FnOnce as the result type which would in effect give us `self` instead of `&self` in the call method, so we can pass the ownership further with `Ok((input, self.val))`. However, using FnOnce means that we can use the resulting closure just once, perhaps that's not we want in a parser. Why? I don't know for sure, but I suspect that we may want to do certain lookaheads while parsing and this means invoking the closure and then backtracking if it doesn't match. But this mean we would have spoiled the parser closure and can't use it again for another run. So let's assume that our parsers should be `Fn`s which is indeed Nom's API.
The **question 2:** how `move` can coexist with returning `Fn` is also clear now. `move` determines how values are **captured** into that closure-structure, i.e. which type they have there (refs, mutable refs or owned values) while `Fn/FnOnce/FnMut` trait is determined by the way they are **used** in that closure (in our `call` method above). For example, we can `move` into a closure but still only use the captured values by reference and return `impl Fn` to allow multiple calls of the returned closure.
The remaining part of **question 3** is why we want to use `move` closure here if we only access the variable by reference anyway. The explanation is that we are **returning** this closure, but `val` will be dropped immediately on return and the closure can't outlive it. In other words, if we didn't use `move`, we would have `val: &'a O` in that closure structure field. But that reference would immediately become invalid since when we return our closure, `val` is dropped, so no references to that are allowed, including inside our returned closure. So that won't work and we would get "val does not live long enough" error message.
Therefore, it looks like all the bells and whistles in that `success` combinator were actually needed.
## Summary
I think the main conclusion of this investigation is that explicitly writing out implicit structures and Fn/FnMut/FnOnce implementations is very useful for making sense of compiler errors and understanding what's going on under the hood in the world of closures. At least for the first time.
## Further reading
* Rust reference: ["Closure expressions"](https://doc.rust-lang.org/stable/reference/expressions/closure-expr.html), ["Closure types"](https://doc.rust-lang.org/stable/reference/types/closure.html) (it even has a special note about combination of `move` closures and `Fn` [here](https://doc.rust-lang.org/stable/reference/types/closure.html#call-traits-and-coercions)).
* ["Why Rust Closure are (Somewhat) Hard"](https://stevedonovan.github.io/rustifications/2018/08/18/rust-closures-are-hard.html) blog post
* [Fn](https://doc.rust-lang.org/std/ops/trait.Fn.html), [FnMut](https://doc.rust-lang.org/std/ops/trait.FnMut.html) and [FnOnce](https://doc.rust-lang.org/std/ops/trait.FnOnce.html) in standard documentation
**Update**: as [/u/CUViper](https://www.reddit.com/user/CUViper/) has suggested on Reddit, there is also a very nice blog post ["Closures: Magic Functions"](https://rustyyato.github.io/rust/syntactic/sugar/2019/01/17/Closures-Magic-Functions.html) which meticulously demonstrates the desugaring of various types of closures.
# Allocation API, allocators and virtual memory
Exploring allocators in general and their Rust API in particular.
## Introduction
I like to look at standard libraries of programming languages! It feels like being in a candy store: there are so many interesting functions and nice tools one can use! Some of them may feel useless at a particular moment, but may come handy later to save on some typing, to avoid reinventing the wheel, or even to guide a design choice.
In Rust, [standard library documentation](https://doc.rust-lang.org/std/) is extremely readable and even has a section "How to read this documentation" for people like me. Let me quote from it:
> If this is your first time, the documentation for the standard library is written to be casually perused. Clicking on interesting things should generally lead you to interesting places.
So, I started reading and here we go. The very first module in the documentation is:
| [alloc](https://doc.rust-lang.org/std/alloc/index.html) | Memory allocation APIs |
| ------------------------------------------------------- | ---------------------- |
This definitely sounded interesting, so I decided to take a closer look and this post summarizes what I've learnt about allocators so far.
We will:
* run some code experiments, registering toy allocators as global Rust allocators
* see that Rust programs allocate dynamic memory even before running `main`
* see how to collect and print information about memory allocations
* learn about virtual memory basics and paging
* learn how `malloc` gets its memory by using `brk` and `mmap` system calls
* learn how to get memory under your allocator's management
## Registering a dummy allocator as global
`std::alloc` module provides us with means to write our own memory allocators and register them as the default global allocator for our programs. Moreover, this is easy to do: you just have to implement a trait with two methods: `alloc` and `dealloc`and register it with `#[global_allocator]` annotation, that's it. Of course, writing the allocator and making it do something reasonable is much less easier.
After that, every time you allocate anything (say, use a `Box` or `Vec` or anything else which allocates on the heap) you'll be using your own allocator.
Let's try to break the system and write a `NullAllocator` (which just pretends that there is no more memory and immediately gives up), register it gobally and see what happens.
```rust
use std::alloc::{GlobalAlloc, Layout};
struct NullAllocator;
unsafe impl GlobalAlloc for NullAllocator {
unsafe fn alloc(&self, _lt: Layout) -> *mut u8 {
std::ptr::null_mut()
}
unsafe fn dealloc(&self, _ptr: *mut u8, _lt: Layout) {
panic!("won't deallocate: we never allocated!");
}
}
#[global_allocator]
static A: NullAllocator = NullAllocator;
fn main() {}
```
Several comments along the way:
`Layout` specifies size and alignment of the memory you want to get. I.e. you can say: "I want 16 bytes with alignment of 2". This means that you'll get 16 bytes at an address divisible by 2. Or you can use "turbofish" and say `Layout::new::()` which means just give me memory which is good enough to store `u32`.
Note that we also have `layout` as a parameter for **de**allocation, not only a pointer (as is the case with `free(ptr)` function in C).
Of course if you are implementing your own allocator, there isn't much Rust can do to protect you in terms of memory safety, so not only the trait functions are `unsafe`, but even the trait impl itself is `unsafe`. Unsafe impl means that you have to provide certain guarantees on the whole allocator logic, while `alloc` function is unsafe because it will result in Undefined Behaviour if you request zero bytes. `dealloc` is unsafe, because for example if you fail to provide it with an address which was given to you by the allocator it can lead to Undefined Behaviour.
We returned null pointer from our `alloc`, which is a way to tell that we are out of memory. Let's try to run our program and see what happens.
```
> cargo run
Finished dev [unoptimized + debuginfo] target(s) in 0.00s
Running `target/debug/alloc-blog`
memory allocation of 4 bytes failed[1] 8113 abort cargo run
```
Wow, and we didn't even allocate anything, note that my `main` function was **empty**: `fn main() { }`
So, what's going on? Who requested those 4 bytes, is it that minimalist Rust runtime? I thought it should only allocate arguments to `main` on stack and the stack itself is provided by OS... Let's investigate.
## Allocation before \`main\`
For this we can write one more allocator which wraps the system allocator and additionally counts number of bytes it allocated! I've shamelessly stolen this example from `std::alloc::System` documentation:
```rust
use std::alloc::{GlobalAlloc, Layout, System};
use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
static ALLOCATED: AtomicUsize = AtomicUsize::new(0);
struct Counter;
unsafe impl GlobalAlloc for Counter {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let ret = System.alloc(layout);
if !ret.is_null() {
ALLOCATED.fetch_add(layout.size(), SeqCst);
}
return ret;
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
System.dealloc(ptr, layout);
ALLOCATED.fetch_sub(layout.size(), SeqCst);
}
}
#[global_allocator]
static A: Counter = Counter;
fn main() {
println!("allocated bytes before main: {}", ALLOCATED.load(SeqCst));
}
```
Here we use atomics, recently there was [a post](https://www.nickwilcox.com/blog/arm_vs_x86_memory_model/) in "This Week in Rust" about atomics, memory model and different implementation on ARM and x86 processors, you may want to check it out. But for now, we just need to know that atomics represent shared memory for threads to communicate. And `Ordering::SeqCst` represent the highest barrier between those threads, so that they definitely see the previous value before updating it and everything works well for our example.
Also note that we use `std::alloc::System` which is a system allocator. What's that, say, on macOS? In the libstd [source code](https://github.com/rust-lang/rust/blob/f844ea1e561475e6023282ef167e76bc973773ef/src/libstd/sys/unix/alloc.rs#L14) we can see that it basically amounts to calling `malloc` library function from `libc` on UNIX systems (including macOS).
So what's the answer? How many bytes, do you think have been allocated before `main`? Click on this black-box to reveal the answer: ⬛. Hm, I need some JavaScript to make it happen and it doesn't work on Gitbook, so ok, I'll tell you without clicking: 237 bytes on my macOS machine. And 241 if we don't subtract for deallocating (so apparently 4 bytes have even been deallocated). Just for fun I've also asked my friend to test it on Windows and Linux:
| OS | RT Allocated, bytes | Remaining in use, bytes |
| ------- | ------------------- | ----------------------- |
| macOS | 241 | 237 |
| Windows | 441 | 173 |
| Linux | 177 | 173 |
Again, there recently was an [interesting post](https://blog.mgattozzi.dev/rusts-runtime/) by Michael Gattozzi in "This Week in Rust" about all the details of Rust runtime. It guides you through the code and it can be seen that at least the runtime uses `Vec` to allocate `std::env::args` from `argv`pointer. Also have `"main".to_owned()` to name the main thread there. And `String` allocates just the same as `Vec`. Presumably there are other structures which allocate and all of this is of course OS-dependent.
I've also tried to just search for that error message in Rust codebase:
```
> rg "memory allocation of"
src/libstd/alloc.rs
270: dumb_print(format_args!("memory allocation of {} bytes failed", layout.size()));
```
The error messages comes from `default_alloc_error_hook` function which gets called when there is an allocation error. Apparently we can also override the error hook and install our own.
## Tracing in allocators
Now, we played enough with the dummy and system allocators and want to write our own. However, first it would be nice to have some tracing ability to be able to monitor the allocation and to help with debugging.
Just naively using `println!("allocated {} bytes", layout.size())` in `alloc` function doesn't work and leads to this scary error: `illegal hardware instruction`. Oh well, joys of unsafe code.
As you may have guessed this happens because `println!` allocates. And allocating within the allocator itself presumably leads to some kind of stack overflow masking as that scary error above.
But where exactly it allocates? First, I thought that it happens while building the formatted string, but no. Let me show you the tracing code which works fine inside `alloc`:
```rust
// This fn works fine when used like this:
// print(format_args!("hello {}", 1));
fn print(args: std::fmt::Arguments<'_>) {
std::io::stderr().write_fmt(args).unwrap()
}
// so I can use it inside allocator's `alloc`:
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
let ret = System.alloc(layout);
if !ret.is_null() {
ALLOCATED.fetch_add(layout.size(), SeqCst);
print(format_args!(
"allocated {} bytes with align {}\n",
layout.size(),
layout.align()
));
}
return ret;
}
// ...
```
This code uses `format_args!` and still it doesn't allocate. Both `print!` and `eprint!` also use `format_args!`
Apparently, both `print!` and `eprint!` (and their `-ln` variants) allocate when they create their local versions of stderr/stdout: judging from the [source code](https://github.com/rust-lang/rust/blob/f844ea1e561475e6023282ef167e76bc973773ef/src/libstd/io/stdio.rs#L16) there is a `Box` there and it alone allocates eight bytes. If we just use `std::io::stderr()` directly, this doesn't happen.
Note also that using `stderr` (as opposed to `stdout`) is also important, because using `std::io::stdout()` also allocates!
I've used this code to actually measure the number of bytes allocated by different constructs on macOS:
```rust
fn main() {
let before_main = ALLOCATED.load(SeqCst);
print(format_args!(
"allocated bytes before main: {}\n",
before_main
));
std::io::stderr().write(b"hello").unwrap();
print(format_args!(
"allocated bytes for the construct: {}\n",
ALLOCATED.load(SeqCst) - before_main
));
}
```
| Code | Bytes allocated |
| --------------------------------------------------- | --------------- |
| `println!()` | 1240 |
| `eprintln!()` | 32 |
| `std::io::stdout().write(b"")` | 1208 |
| `std::io::stderr().write(b"hello")` | 0 |
| `std::io::stderr().write_fmt(format_args!("{}", 1)` | 0 |
I think that the difference between `stderr` and `stdout` in terms of allocations can be explained by [this comment](https://github.com/rust-lang/rust/blob/f844ea1e561475e6023282ef167e76bc973773ef/src/libstd/io/stdio.rs#L762) from libstd:
> Note that unlike `stdout()` we don't use `Lazy` here which registers a destructor. Stderr is not buffered nor does the `stderr_raw` type consume any owned resources, so there's no need to run any destructors at some point in the future.
>
> This has the added benefit of allowing `stderr` to be usable during process shutdown as well!
Now we also know that one more benefit is that it can be used in `alloc`along with `format_args!`
## Using custom allocators for standard collections
Of course it's entirely optional to register allocator with `#[global_allocator]`, you can continue using the standard allocator and only use custom allocators for specific goals by directly calling their `alloc` and `dealloc`methods.
This raises an interesting question: if you want to allocate a Box, Vec or HashMap using a custom allocator, how would you do this? I was surprised to discover that there is no such API in `Vec`, even on nightly. However, the work and discussion on this are ongoing, I think the latest relevant places to check is the [repository](https://github.com/rust-lang/wg-allocators) of "Rust Allocators Working Group". It looks like the proposed version of API adds `new_in` [function](https://timdiekmann.github.io/alloc-wg/alloc_wg/vec/struct.Vec.html#method.new_in) which will receive an allocator (i.e. something implementing `AllocRef`, another allocator trait) as a parameter, so you can have `Vec::new_in(my_allocator)` or `Box::new_in(2, my_allocator)`.
## How to get memory from inside the allocator
If we want to write a more realistic allocator which actually does some allocation and not just returns `null_ptr` or counts whatever system allocator returns us, we need to face another serious question: what's the proper way to actually get memory in our allocator then? If we just call `libc::malloc` doesn't it defeat the point? I.e. don't we just delegate the work to another allocator this way? In order to answer this question, we probably need some overview of memory management first.
## General overview of memory management
As you probably know, memory management conceptually happens on two levels.
1. Operating system manages physical memory of the whole machine giving it to processes and using it for its own purposes.
2. Programs manage their dynamic memory for their own purposes (for example to create dynamic data structures).
We can manage memory in fixed size chunks or in variable size chunks.
On the first level, operating systems normally use *fixed* size approach called *paging:* memory is given out to processes in fixed size pages, usually 4k in size (you can run `pagesize` on macOS to check the page size). OS and relevant hardware also has to manage for each process the mapping between virtual *pages* (which are fixed size parts of the process virtual address space) and physical *page frames* which are parts of actual physical memory. The mapping itself may be rather large, so in order to resolve lookups efficiently OS uses help of the hardware which basically caches part of the pages mapping in Memory Management Unit of the CPU. Without hardware support, paging would be prohibitively slow due to extra indirections involved in the address translation.
On the second level, programs normally request memory in chunks of *variable* sizes, which makes it harder to manage than using *fixed* size chunks. Variable size leads to *fragmentation* and requires certain algorithms to handle it. This also entails additional performance costs associated with such algorithms. Hence, there is a need for an allocator library which provides API for allocating and deallocating memory of any size, so that the complexity can be abstracted away and hidden from programmers.
If it's abstacted away, then we need some API to work with it.`malloc` and `free` from C is an example of such API, `allocate` and `deallocate` from `std::alloc` in Rust we are looking at is another.
Now it should make some sense that `malloc` is *not* an OS system call, but a library function. And allocators implementing `malloc` are part of C standard library (i.e. [GNU libc](https://www.gnu.org/software/libc/manual/html_node/The-GNU-Allocator.html) or [musl libc](https://git.musl-libc.org/cgit/musl/tree/src/malloc/mallocng/malloc.c)). When you link to that library, you get a clever allocator for free.
## \`malloc\` and getting new memory
How does `malloc` gets new memory under its management? It has two options: to adjust the program break with `brk` or to map new pages of memory with `mmap`. Let's look at those in more details.
Above you can see a typical process memory layout, which describes which areas of the process virtual address space are assigned to which segments. The *program break* is basically the address of the end of data segments of the program. Past program break there are unallocated addresses and if we try to access them we will get "segmentation violation" error. When the process is created, its program break is set to the top of uninitialised data segment (BSS), so the heap size is effectively 0.
### brk/sbrk
`malloc` then can increase the available heap area by moving program break further up. This is done by `brk` or `sbrk` system calls on UNIX. [Those calls](https://linux.die.net/man/2/sbrk) just update the address, they don't do any actual memory mapping. Their effect in essence is that they make new virtual memory addresses available for the process to use (so we won't get segmentation violation anymore). The actual pages mapping is made by OS kernel when we try to access that memory for the first time. Since OS virtual memory operates on pages, actual changes in program break are multiples of the system page size.
Allocators can also decrease the amount of mapped memory by moving the program break down (say, when all the blocks at the top were freed).
By the way, I was always puzzled why those calls had such strange names for something heap-related. Now I know that that's because they manipulate that "program break", which is some ancient programming term.
### mmap
Another option for `malloc` is to use `mmap` which is a system call which can be used for many purposes: to implement memory-mapped file I/O, to allocate memory or to organize shared memory for inter-process communication. If we use `mmap` like this:
```c
mmap(
NULL, // let OS decide where to place it in virtual address space
size, // size of the memory we need, in bytes
PROT_READ | PROT_WRITE, // read/write memory
MAP_ANON | MAP_PRIVATE, // zero-filled, used only by this process
-1, // unused for anonymous memory
0 // unused for anonymous memory
);
```
We are basically asking OS to give us a zero-initialised chunk of memory with size `size` so that we can read/write it for any private needs in our process. This memory will be mapped to an virtual address of the process at OS discretion.
`mmap` is normally used by `malloc` for allocating larger blocks of memory, it's controlled by certain threshold which can be adjusted.
I think the principal differences between `mmap` and `brk` are as follows:
* with `mmap` we can have many memory blocks (for example one for each thread), while with `brk` and program break - we maintain a large monolitic block of memory - the heap.
* with `mmap` we can give back the memory of a particular block back to the OS (with `munmap`) when everything in that block has been freed. It's trickier to return memory with `sbrk` approach, since we can't return freed memory from the middle of the monolitic heap (we can only decrease the program break when end of the monolitic block is freed).
## Back to the "getting memory in our allocator" question
So, now we've seen how `malloc` does it, we have some ideas how to do it in our own allocator program.
The easiest approach is probably just to use the system allocator `std::alloc::System` and ask it for some large memory area which we can then micro-manage with our allocator (which presumably has some specific goals).
If we want to get lower than that we can emulate what `malloc` is doing and use OS-based system calls (most likely `mmap` on UNIX-based systems, [VirtualAlloc](https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc) on Windows or something else on WebAssembly). For example you can see how `wee_alloc` [does it ](https://github.com/rustwasm/wee_alloc/blob/f26c431df6fb6c7df0d6f8e0675471b9c56d8787/wee_alloc/src/imp_unix.rs#L11)on UNIX with `mmap`.
Finally, if we don't have any OS at all and are running on some bare-metal embedded device, we can just use a statically allocated larged array to manage:
```rust
static mut HEAP: [u8; 8192] = [0; 8192];
```
## Summary
This post is already getting rather long, so I think I need to wrap up, even though we've just scratched the surface of the allocators and didn't even start to implement one.
However, now we are equipped with important tools and ideas: we know the basics about virtual memory and paging, how to get memory from the OS, how to register our allocator within Rust and how to add tracing which should help with the debugging. I hope this whetted your appetite to dive deeper into the allocators.
There seem to be a ton of interesting algorithms and decisions to be made when implementing an allocator. Also, the staggering amount of different approaches suggests that there is no silver bullet and it's impossible to write an allocator which will scale well and satisfy all the possible needs, so we need to specialise.
If you want to read more about virtual memory and operating systems in general I highly recommend a [free book](http://pages.cs.wisc.edu/~remzi/OSTEP/) "Operating Systems: Three Easy Pieces". It's an amazing textbook which is quite entertaining to read just for fun. Some of the relevant chapters are ["Address Translation"](http://pages.cs.wisc.edu/~remzi/OSTEP/vm-mechanism.pdf), ["Free-Space Management"](http://pages.cs.wisc.edu/~remzi/OSTEP/vm-mechanism.pdf) and ["Paging: Introduction"](http://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf).
If you want to see more Rust code examples and some actual implementations of educational allocators you can read those two pages from the wonderful blog "Writing OS in Rust" by Philipp Oppermann: ["Heap Allocation"](https://os.phil-opp.com/heap-allocation/) and ["Allocator Designs"](https://os.phil-opp.com/allocator-designs/), it's very very good.
If you want to take a look at some popular real-world allocators written in Rust, you can start with the following:
* [wee\_alloc](https://github.com/rustwasm/wee_alloc) - "The **W**asm-**E**nabled, **E**lfin Allocator". 333 ⭐. This allocator specialises for WASM, trying to be simple (so that the generated WASM size will be smaller). It can also be run on UNIX, Windows or just with static array as a heap.
* [bumpalo](https://github.com/fitzgen/bumpalo) - "A fast bump allocation arena for Rust". 339 ⭐. Bump allocation is a good place to start, since this is one of the simplest allocation strategies you can implement, while still being useful. Also the code is very well commented.
That's it, I hope you've learnt something useful. If you want to comment you can either [discuss it](https://www.reddit.com/r/rust/comments/hlv7o8/allocation_api_allocators_and_virtual_memory/) on Reddit or [create an issue](https://github.com/sphynx/notes/issues/new/choose) on Github. Or if you want to send me a pull request on this "Notes" [repository](https://github.com/sphynx/notes) with any proposed changes or mistakes you've found, I'd be extremely grateful.
# Checking status of Rust features
RFC process, features lifecycle and the Algorithm
## Problem: How to find a feature status?
Sometimes I want to quickly tell whether a particular feature in Rust is supported and if so, to what extent? Is it:
* in nightly (for how long then?)
* stabilised (since when?)
* just being discussed?
The goal of this post is to provide a simple algorithm for finding relevant feature details, learning its status and for how long the feature was in that status. If it's stuck in nightly for years, then it's not very likely that it will be stabilised soon.
Along the way, I'll also describe lifecycle of a typical feature and the RFC process.
{% hint style="info" %}
**TL;DR** The algorithm is to just follow the feature lifecycle, noting the feature gate, relevant Github labels and dates when state changes. Then double check in [The Unstable Book](https://doc.rust-lang.org/unstable-book/the-unstable-book.html) and potentially in rustc source code in [`src/librustc_feature`](https://github.com/rust-lang/rust/tree/master/src/librustc_feature)
{% endhint %}
## Lifecycle of a typical feature
Understanding features lifecycle is important when making sense of different feature states.
1. Someone has a new idea for Rust feature :bulb:
2. If it's *substantial,* they need to prepare an RFC. If not, they just create a Github issue for the feature.
{% hint style="success" %}
**Q**: What is RFC?
**A**: It stands for "Request for Comments". It's a well structured document summarising a feature, motivation behind it, its usefulness, potential drawbacks and alternatives. Its goal is to advertise the feature and to persuade other people to include it in the language. [Example.](https://github.com/rust-lang/rfcs/blob/master/text/2298-macro-at-most-once-rep.md)
{% endhint %}
3\. When the RFC is ready, they send a pull request to [RFC repo](https://github.com/rust-lang/rfcs).
4\. People discuss the RFC and eventually propose to start so called *FCP* - Final Comment Period, along with current disposition (merge, close, postpone). It lasts 10 days.
5\. FCP ends and RFC pull request is either merged, closed or gets back to the previous state (if some new ideas or issues are discovered during FCP). You can find all merged RFCs starting from 0001 in [The RFC Book](https://rust-lang.github.io/rfcs/).
{% hint style="danger" %}
Potential confusion: if you see RFC pull request in status "Merged" on GitHub -- this means only that: RFC is merged. This **doesn't** mean that the feature *itself* is implemented.
{% endhint %}
6\. When RFC is merged, it gets its "*tracking issue*", the link to that is added to RFC header:
Tracking issue is used to track the progress of implementation, questions which need to be resolved, etc. Further discussions normally happen here. The issue has a plan with checkboxes:
7\. Eventually the feature is implemented and merged into `master`. It becomes part of the next `nightly` release. Since it's not yet stable we don't want people to accidentally use it (since it can still be seriously changed and then their code may break). So, one has to explicitly add a *feature gate* to the source file, like this: `#![feature(box_syntax)]`. Normally, identifier for feature gate is the same as feature name in RFC.
All unstable nightly feature gates are available in [The Unstable Book.](https://doc.rust-lang.org/unstable-book/the-unstable-book.html) Remember that: we'ill use it later.
8\. While features are used in `nightly` people collect feedback, resolve questions, check more chekboxes in the plan and if everything goes well, prepare features for stabilization. That involves creating one more document and one more Final Comment Period, oh well. Eventually, everyone is happy and the feature is considered stable.
## Useful labels in Rust repo
How do we know the current state of a particule issue? One of the easy way is to check its Github labels that look like this:
Useful labels for our cause are under "B-":
* B-RFC-approved - Approved by a merged RFC but not yet implemented
* B-RFC-implemented - Approved by a merged RFC and implemented
* B-unstable - Implemented in nightly compiler and unstable
## The Algorithm
Still with me? Now I am going to present the Algorithm. Its idea is to just follow the feature lifecycle, keeping track of dates when states change. This way we can understand what the current state is and how much time was spent in different stages.
To help us we will use Labels, issue checkboxes and The Unstable Book.
### Steps
Starting point: you want to know about some feature, for example "Unicode characters in variable names".
1. Just google that and identify relevant RFC on Github, if there is one
2. Check status of its pull request, note feature name and tracking issue
3. Go to tracking issue, see what labels are there, look for "B-RFC-approved", "B-RFC-implemented", "B-unstable"
4. Look at checkboxes in the tracking issus, particularly for "implementation" and "stabilization" steps.
5. Double check in The Unstable Book looking for feature gate from (2). If it's there: you have unstable feature available on nightly. If it's not there, it's either stabilised or not implemented (you can usually tell from step 4).
That's it. We will take a look at examples in the next section.
**UPDATE:** As suggested by [u/moltonel](https://www.reddit.com/user/moltonel/) on Reddit, [caniuse.rs](https://caniuse.rs/) is another amazing starting point which might work better than googling for stable features in step 1. It provides stabilization date, Rust version on which it was stabilized, feature gate and the links to relevant PRs and tracking issues.
There is another starting point: you just see unstable feature in the documentation, like this:
Then you immediately have a link to tracking issue, know the feature gate and know that it's unstable, so you basically don't need to do anything else :)
## Examples of applying the Algorithm
### Unicode identifiers
Let's say we want to know if we can use Greek characters for naming variables like αβ.
1. Googling "unicode characters in rust variables" gives me this RFC:
2. If it's in RFC book, this means that its RFC is merged, that's encouraging. I note the feature name: `non_ascii_idents` and go to the tracking issue:
3. I can see the label "B-unstable" which means that it's implemented and is at least unstable (but it may have stabilized later)
4. I then cross check by looking up `non_ascii_idents` in The Unstable Book: - it's there, great.
**Conclusion**: feature status is "implemented, unstable", i.e. in nightly
### Minimum supported Rust version
This feature is about being able to specify minimum version of Rust in `Cargo.toml` using something like `rust = "1.35"`.
1. Start from RFC PR: -- which I googled and found through Reddit
2. We can see that it's merged, so RFC is approved. Note feature\_name from rendered RFC: `min_rust_version`
3. Now I would normally check Rust Unstable book looking for that feature gate. But in the case there is no point, since this feature is for Cargo.toml, not for Rust code
4. Now we follow tracking issue:
5. We can see here that it's open and that "Implement the RFC" is not checked, so no luck, it's not even implemented yet. We can also see that it was created on Oct 2019, about 10 months ago.
**Conclusion**: RFC accepted, feature not implemented yet
### Others
I won't bore you with repeating the steps for other cases, just give you links to issues, so that you can see how they look:
* [Stabilized feature](https://github.com/rust-lang/rust/issues/48075)
## :warning:Potential problems
It all looked nice and easy, I was inspired and even wanted to automatically prepare some statistics about Rust unstable features. But when I started looking at features case by case, I found irregularities. Trying to make sense of those irregularities actually led me to writing this post. Let's look at potential problems and solutions.
#### It a feature has "B-unstable" label, it might already be stable, the tag is just never removed
Look in "Unstable book" and for "Stabilization" checkbox in the tracking issue to understand whether its stabilized.
#### If RFC PR is Closed (not Merged), this still can mean that it was actually approved for implementation
Not sure how it works, but I've seen this a couple of times.
#### Some features have several tracking issues (because there are too many comments)
Usually they are cross-referenced, so it's fine, we can just go to the latest one.
#### Some issues do not have RFCs
If it's not that large and debatable, there is just a tracking issue for a particular feature gate, without any RFC.
#### Some feature have so many comments they start whole new "working groups" with separate repositories
For example, if you look for "allocators for containers" you'll get to the relevant RFC and tracking issue, but that leads to "Rust Allocators Working Group" [repo](https://github.com/rust-lang/wg-allocators) which has its own set of issues.
**"Stabilization checklist" may be still not checked in the tracking issue, even though it's stabilized**
For example [here](https://github.com/rust-lang/rust/issues/27389)
## Bonus: feature gates in \`rustc\` source code
Features gates have to be enforced by the compiler, so the list of features has to be somewhere in the code. For language features it's here: [src/librustc\_feature](https://github.com/rust-lang/rust/tree/master/src/librustc_feature)
There are three modules:
* active.rs - for unstable features
* accepted.rs - for stabilised features
* removed.rs - for, well, removed features (which were once active)
Looking at [accepted.rs](https://github.com/rust-lang/rust/blob/master/src/librustc_feature/accepted.rs) quickly shows when features were stabilized:
```rust
/// Allows the use of `if` and `match` in constants.
(accepted, const_if_match, "1.45.0", Some(49146), None),
/// Allows the use of `loop` and `while` in constants.
(accepted, const_loop, "1.45.0", Some(52000), None),
/// Allows `#[track_caller]` to be used which provides
/// accurate caller location reporting during panic (RFC 2091).
(accepted, track_caller, "1.46.0", Some(47809), None),
```
Note, that this covers only *language features* affecting Rust compiler. *Library features* are normally just introduced like this:
```rust
#[unstable(feature = "slice_ptr_range", issue = "65807")]
pub fn as_ptr_range(&self) -> Range<*const T> {
```
Here we have a stability annotation that has a feature gate and refers to a tracking issue. When the feature is stabilised that annotation is changed to `#[stable(feature = "slice_ptr_range", since = "1.0.79")]`
## Useful links :paperclips:
* All details of the RFC process and features lifecycle are well described in Rustc Developer Guide: ["Implementing new features"](https://rustc-dev-guide.rust-lang.org/implementing_new_features.html), ["Stability attributes"](https://rustc-dev-guide.rust-lang.org/stability.html), ["Stabilizing features" ](https://rustc-dev-guide.rust-lang.org/stabilization_guide.html)
* ["This Week in Rust"](https://this-week-in-rust.org/) publishes not only links to new exciting Rust blog posts, but also new RFCs, approved RFC, new tracking issues and RFCs entering Final Comment Period on that particular week.
## Outro
I hope you've liked this post and can now navigate the labyrinths of RFCs and tracking issues more confidently.
I am interested in ways of improving the clarity of this whole process. If you want to comment you can either [create an issue](https://github.com/sphynx/notes/issues/new/choose) on Github or drop me an email. Also please send pull requests to this [repository](https://github.com/sphynx/notes) if you want to improve something. Thank you!
# Mathematics
Entry point to my math explorations.
# LaTeX test
Let's see if TeX markup works properly here:
$$
f(x) = x \* e^{2 pi i \xi x}
$$
$$
x \in \mathbb{Z}
$$
And now some inlined text $$f(x) = x \* e^{2 pi i \xi x}$$ and another one: $$g(x) = x \* e^{2 pi i \xi x}$$
And now let's have a block:
$$
f(x) = x \* e^{2 pi i \xi x}
\newline
g(x) = x ^2
$$
# Game Development
# Snake: an exercise in game development
7 days plan for creating a Snake game
I was inspired by GMTK's video "How I learned Unity without following tutorials". His idea was to learn the very basics of Unity game engine (things like game objects, components, transforms, scene editor controls) and then create several simple game clones and learn the rest "on demand", when it's needed in the game. This resonated with me, so I decided to go with Snake which I liked a lot as a kid. I came up with a plan for 7 days to keep me focused and produce a finished game that I can publish it on itch.io and send it to friends or strangers to play.
My take on the classic
I've managed to stick to my plan, see [my published game on itch.io](https://dsphynx.itch.io/snake) and source code on [GitHub](https://github.com/sphynx/snake/). Some of those seven "days" were short (1-2 hours of work), some were longer (5-6 hours), but overall the planning was good, the process was fun, so I decided to share it along with some Unity/C# knowledge I've learnt (something for next posts).
I think it may be also useful for people who want a large but structured exercise in game development.
### Game Design Document
Before implementing a game clone, I think it's very important to understand in advance what you want to implement: which features/power-ups of the original game to support. This will limit your scope and make possible to actually finish the project. It is also useful to set some time limits for things like game sprites or sounds: one may spend ages tinkering with the visuals and never attain perfection! As someone in the Internet said: "Your first game will be ugly", so there is no need to focus on that too much.
Also, before coming up with a plan I went to itch.io and looked at existing Snake implementations to get ideas and remind myself of the gameplay, see how people display scores, endgame screens and other stuff.
I ended up with this "design document":
> Create a clone of a basic Snake game, with a snake, apples, and walls on a rectangular 2D grid. The player can press arrow keys to move the snake. Speed of the snake should gradually increase. The game should keep the score: number of eaten apples. It should also keep high-score (fine to keep it in memory).
>
> There should be different sprites for snake head and snake body, they should be properly oriented.
>
> There should be basic 2-frame animations on some sprites (snake head, apples).
>
> There should be background music, plus sounds for eating an apple and hitting the wall. It can be sourced from free game assets.
>
> There should be title game screen with some nice picture, the main "level" where gameplay is happening, and the end game screen displaying the score and high score when snake dies.
It's not a proper Game Design Document of course, just a list of points that must be implemented to consider the game done. To get a feel of a real GDD, you can look at [this](https://www.cs.unc.edu/Courses/comp585-s15/DesignDocTemplate.pdf) template from a course in University of North Carolina.
### Plan
When working on the items from the list below, I kept a dev log, adding short notes about difficulties I had, resources used, things learnt, and rough amount of time I spent. It was useful and allows me to resurrect those experiences now.
I also used version control system and committed the state of the project at the end of each day.
#### Day 1
* [ ] Come up with a data structure to represent a rectangular grid.
* [ ] Come up with a data structure to represent the snake. In Unity, those two may be just plain C# classes or GameObjects.
* [ ] Think about and choose a coordinate system to use to refer to your grid positions.
* [ ] Display the grid and the snake (motionless for now) on the screen. Just use simple 2D square tiles: say white square for the snake, black square for empty space and gray square for the walls.
My version at the end of Day 1:
After Day 1
#### Day 2
* [ ] Implement the snake moving logic, i.e. what happens to your data structure after one step of the snake movement. You also need to save the current direction of movement somewhere.
* [ ] Make the snake move on the screen.
* [ ] Take input from the keyboard: just arrow keys for now. Make it affect the movement.
* [ ] Add game controller support for extra challenge (and if you have one).
After Day 2
#### Day 3
* [ ] Spawn apples.
* [ ] Add score and "apple eating" logic, i.e. what happens if snake's head hits an apple: it should increase the score and spawn a new apple.
* [ ] Detect hitting the wall or itself, which is a game over condition. For now we can just print a log message on game over.
#### Day 4
* [ ] Add basic UI: a line displaying current score.
* [ ] Add separate GameOver screen: another scene/level, that shows the final score and the high score.
* [ ] Add a hotkey to restart the game from GameOver screen (say, on pressing "R").
* [ ] Preserve high score between games.
My first version of Simple GameOver screen:
Game Over screen
#### Day 5
* [ ] Find sprites for snake head, body, apples and walls. Use assets from itch.io, OpenGameArt, or other sources listed here: [https://www.freegameassets.com](https://www.freegameassets.com/)
* [ ] Fugure out how to deal with spritesheets
* [ ] Use the new sprites in the game
* [ ] Orient them properly so that the head looks in the right direction
After Day 5
#### Day 6
* [ ] Add simple 2-frame animation (for apples for example, so that they are more attracting, or maybe for hitting the obstacle)
* [ ] Create the start screen that should display the game title, authors and ask to press Enter to start the game
* [ ] Find a nice Snake-themed free picture for the start screen
* [ ] Find and use sounds when apple is eaten and wall is hit
* [ ] Find and use background music, probably a chiptune from OpenGameArt
#### Day 7
* [ ] Polish: adjust colors, sizes, game speed progression, etc.
* [ ] Fix remaining bugs
* [ ] Figure out how to build the game for itch.io (WebGL-based build, playable in the browser)
* [ ] Upload to itch.io, test and make sure it works in the browser
The final version played on itch.io [it looks somewhat laggy due to GIF recording]
### Conclusion: now it's your turn!
As you may have noticed, there is almost nothing Unity-specific in this plan, so it can be easily applied to learning any other game engine. Admittedly Snake is a very simple game, so if you just want to make Snake (and not to learn Unity), then it may even make sense to code it in a simpler 2D engine.
So give it a go, try to follow the plan or adjust it to your taste and see where it takes you! Please feel free to send links to your published games to my email: "veselov" at google mail, I'll be happy to see them.
In the next posts I plan to cover how I fared with that plan, reflecting on my dev log and sharing insights, so you can come back later and compare our experiences.
### Bonus: materials for learning basics of Unity
If you are really new to Unity and want to learn those basics I mentioned in the very beginning, I found those resources helpful:
* Brackey's playlist "[How to make a game in Unity](https://www.youtube.com/playlist?list=PLPV2KyIb3jR53Jce9hP7G5xC4O9AgnOuL)" - 10 short videos (each about 10 minutes), fast paced, well explained and to the point. It covers the basics: game objects, components, transforms, C# scripting and using the Scene editor. And at the end you have quite a fun 3D (!) game!
* For people with some experience with programming, I found Unity documentation quite good: you can start from "[Game Object](https://docs.unity3d.com/Manual/GameObjects.html)" section in Unity Manual. Another good reference is "[Important classes](https://docs.unity3d.com/Manual/ScriptingImportantClasses.html)" page which explains the classes you will see used in Unity code all the time. There are also simpler official Unity tutorials, ava
* CatLikeCoding tutorials are text-based and usually quite in-depth. [This one](https://catlikecoding.com/unity/tutorials/basics/game-objects-and-scripts/) explains how game objects and scripts work in Unity, creating a 3D clock in Unity as an example.
# Miscellaneous
# Technical newsletters
A list of interesting newsletters (mostly about programming)
I find weekly newsletters a convenient way for digesting information. It works as follows: someone knowledgeable prepares a curated list of links on a particular topic: articles, blog posts, news, pull requests, etc. and sends it weekly by e-mail to all subscribers. Then you can save time by skimming through the best links on, say, Friday instead of reading them one by one throughout the week.
### Currently subscribed to:
* [Hacker Newsletter](https://hackernewsletter.com/) - "Best articles on startups, technology, programming, and more. All links are curated by hand from Hacker News". If you choose the only one of those I recommend this newsletter, it's simply the best.
* [Better Dev Link](https://betterdev.link/) - "Weekly links to help you become a better developer"
* [This Week in Rust](https://this-week-in-rust.org/) - "Handpicked Rust updates, delivered to your inbox"
* [Haskell Weekly](https://haskellweekly.news/) - "Each issue features several hand-picked links to interesting content about Haskell from around the web."
* [Julia Evans blog weekly digest](https://jvns.ca/newsletter/) - great technical blog covering many topics in a simple to understand manner, I would call it project-oriented.
### Others
* - for further inspiration, see this large collection of newsletters from "Awesome" network
# Roguelikes
Various interesting links related to my long-standing hobby: roguelikes!
### My favourite games
* [Dungeon Crawl Stone Soup](https://crawl.develz.org/): played this since 2009! One of the most polished roguelikes in constant active development for more than 15 years! It has a lot of variety even by roguelikes standard: species and god combinations can lead to very interesting gameplays. Can be played in browser.
* [Caves of Qud](https://www.cavesofqud.com/) - relatively new roguelike with a large overworld in addition to usual dungeons: deserts, jungles, quests and quite interesting gameplay based on mutations. Thematically it reminds me of Dune or maybe even Fallout. Also, works of Gene Wolfe has been quoted an influence.
* [Sil](https://www.amirrorclear.net/flowers/game/sil/) (or a more modern Sil-Q) - a streamlined version of Angband (one of the major roguelikes). I like its combat system, and realistic magic system (implemented as "songs"), based on Tolkien's work -- i.e. no fireballs or other craziness.
* [Brogue](https://sites.google.com/site/broguegame/) - a quicker and shorter roguelike with an interesting take on ASCII rendering.
### Dev blogs and resources
* [/r/roguelikedev](https://www.reddit.com/r/roguelikedev/) - popular subreddit, fully of insightful discussions and advice
* [RogueBasin](http://roguebasin.com) - a wiki about roguelike development. It has a nice [news](http://roguebasin.com/index.php/News) section, which allows one to track progress of developed roguelikes. And also it has ["Featured roguelikes"](http://www.roguebasin.com/index.php/Category:Featured_Roguelikes) category which highlights interesting but less known games.
* [Blog](https://www.markrjohnsongames.com/blog/) of Mark R Johnson - author of "Ultima Ratio Regum"
* [Blog](https://www.gridsagegames.com/blog/) of Josh Ge of "Grid Sage Games", developer of Cogmind
* [Blog](https://journal.stuffwithstuff.com/category/game-dev/) of Bob Nystrom, author of "Game Programming Patterns" and "Crafting Interpreters" books. Has an interesting [post](https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/) about dungeon map generation
* ["@Play"](https://nethackwiki.com/wiki/@Play) column by John - a series of articles about classical roguelikes. Note that most of them should be accessed via way web.archive.org, since the magazine in which they were published no longer exists: [Wayback Machine link](https://web.archive.org/web/20130719223011/http://www.gamesetwatch.com/column_at_play).
* ASCII Tilesets and colorscheme [browser](https://extended-ascii-viewer.herokuapp.com/), also featuring many dungeon map generation algorithms from rot.js library.
### Roguelike dev tutorials
* ["Roguelike tutorial in Rust"](https://bfnightly.bracketproductions.com/) -- quite detailed, covers a lot of ground and gets to a nice game at the end! Uses `bracket-lib` (formerly known as `rltk`) - Rust library for roguelike development.
* [Python tutorial with libtcod](https://rogueliketutorials.com/tutorials/tcod/v2/) -- I think this is the most popular one, given that Python is an easy language to pick up. It's also quite well done and is regularly updated. Also, from time to time there are special events on /r/rogueliedev subreddit when people are developing games following that tutorial and share their experience.
* ["RuggRogue Source Code Guide"](https://tung.github.io/ruggrogue/source-code-guide/) -- a book about source code and design decision of RuggRogue - a simple roguelike game, that the author developed following one of the tutorials. It's Rust based.
# Travel
# Torres del Paine
Long distance hikes in Patagonia
There are two popular routes: "W" (shorter) and "O" (longer). Camping is allowed only in official spots. All accommodation has to be booked in advance, it is strictly enforced, otherwise you won't be allowed to enter the park.
There are three companies providing camping sites and accommodation: CONAF (governmental), Fantastico Sur and Vertice.
Lifehack: book "Chileno" camp site first, since it tends to be very busy, adjust the rest of the tour to that.
## Links
* [StingyNomads](https://stingynomads.com/torres-del-paine-hiking-guide/) - great reference site
* [BestHike.com](https://besthike.com/s-america/patagonian-andes/paine-circuit/) - another reference site
## Maps
{% file src="/files/-Lxq65xd4-QyOqVt\_i1H" %}
Torres del Paine official map PDF
{% endfile %}
## Campsites
### CONAF (free, governmental, very quick to fill out)
[Link for reservations](https://wubook.net/wbkd/wbk/?lcode=1470832720) -- currently (early Jan 2020) January and February 2020 are fully booked, the first available day is 7th of March.
* Italiano (on "W")
* Paso (on "O")
* Torres (on "W") - closed?
### Vertice Patagonia
[Link for reservations](https://reservas.verticepatagonia.cl/index.xhtml)
* Dickson
* Grey
* Los perros
* Paine Grande
### Fantastico Sur
[Link for reservations](http://int.fantasticosur.com/en/online) -- it looks like the web site is down on weekends!
* Chileno
* Frances
* Los Cuernos
* Seron
* Las Torres ("Campsite Central" on the image below)
## Routes, times and distances
### Distances
### "O" Route
* Day 1. Las Torres - Seron. 16.5 km. 4 hr.
* Day 2. Seron - Dickson. 18 km. 6 hr
* Day 3. Dickson - Los Perros. 12 km. 4:30 hr
* Day 4. Los Perros - Paso. 8 km. 6 hr. 680 m ascent. 800 m descent. **Paso is already fully booked for Jan/Feb 2020**
* Day 5. Paso - Grey. 10 km, 4 hr.
* Day 6. Grey - Paine Grande. 11 km. 3-4 hr. 300m ascent. 300m descent.
* Day 7. Paine Grande - Los Cuernos. 13 km. 4 hr.
* Day 8. Los Cuernos - Las Torres. 11km. 3 hr. 160m ascent. 100m descent.
### "W" route (east to west)
* Day 1. Las Torres - Torres Lookout - Las Torres (4 hours x 2)
* Day 2. Las Torres - Los Cuernos. 11.6 km. 4:30. (or camp Francese). 100m ascent. 160m descent.
* Day 3. Valle des Frances. Camp at Britanico or Italiano. 520 m ascent/descent.
* Day 4. Britanico/Italian to Paine Grande.
* Day 5. Paine Grande - Grey. (and back?)
* Day 6. Grey - Administracia.
### "W" route (DK version)
* Night 1. Lake Pehoe.
* Night 2. Paine Grande.
* Night 3. Grey.
* Night 4. Paine Grande.
* Night 5. Frances.
* Night 6. Chileno.
### "W" route (StingyNomads version) - 5 days version.
{% embed url="" %}
* Night 1. Grey. (coming from Puerto Natales in the morning).
* Night 2. Paine Grande.
* Night 3. Italiano/Frances.
* Night 4. Chileno.
* Night 5. Puerto Natales.
# Tents
An overview of lightweight backpacking tents in 2019.
In December 2019 I decided that it's time to replace my old and battered tent Trimm HimLite DSL (its details [below](/travel/tents#trimm-himlite-dsl)). We used it in many places for more than 5 years:
* Iceland (twice) - strong winds, rain
* Lake District (UK)
* Isle of Skye (Scotland) - strong winds, rain
* Burning Man festival (Nevada, US) - daily sandstorms, desert conditions
* Yellowstone National Park (US)
* King's Canyon National Park (US)
* Carpathian mountains - Gorgany (Ukraine)
It worked well most of the time and I still like it, it is a reliable tent, but since it was battered by winds and had a developed a small hole in the floor it was time to look at something new.
My main criteria were:
* a three season tent, suitable for relatively difficult weather conditions (think Iceland, Scotland, Patagonia in summer)
* within reasonable limits in terms of weight (I've got spoiled by under 2kg tents)
* enough space for two skinny people of average height
So I've created this note to help me with the choice and consolidate reviews/technical data about potential candidates here, in one place.
I think the choice was mostly influenced by many reviews I've read and personal experience of using my previous tents.
Spoiler: after all the research and several days of hesitation I bought Hilleberg Anjan 2 (I managed to get the price down to 598 £ which is still quite a lot!), hopefully I'll test it soon!
## Overview table
| Name | Weight, g | Floor, m² | Vestibule, m² | Materials (floor/outer/inner), D | Price, £ |
| -------------------- | --------- | --------- | --------------- | -------------------------------- | -------- |
| MSR Hubba Hubba NX | 1720 | 2.7 | 1.62 = 0.81 x 2 | 30/20/20+15(mesh) | 385 |
| Nemo Dragonfly 2P | 1410 | 2.7 | 1.8 = 0.9 x 2 | 20/15/10 | 420 |
| Trimm HimLite DSL | 1600 | 2.5 | 0.65 | 10k H₂O / 4k H₂O | 370 € |
| Exped Mira II HL | 1500 | 2.7 | 1.3 | 20/20/15 | 380 |
| Hilleberg Niak | 1700 | 2.6 | 0.75 | 50(12k H₂O)/20/10 | 790 |
| ✅ Hilleberg Anjan 2 | 1800 | 2.6 | 1.2 | 50/20/10 | 715 |
| Hilleberg Anjan 2 GT | 2100 | 2.6 | 2.5 | 50/20/10 | 827 |
| Hilleberg Rogen | 2100 | 2.8 | 2.0 = 1.0 x 2 | 50/20/20 | 835 |
## MSR Hubba Hubba NX
[Official manufacturer link](https://www.msrgear.com/ie/products/tents/hubba-hubba-nx-2-person-backpackingandnbsp%3Btent/06204.html?srd=true)
I've kept this tent in the back of my mind all the time since reading a very favourable review on "ProPohody" site (see below). Then came the next review on the same website, which was less favourable: it covered the changes made to this tent in a new version of this model. This tent is very popular, you can often see it outdoors, in campsites or in random hiking videos on YouTube, I think this tells something about it. Also, it's nice that it doesn't come with additional cost when sold in the UK as opposed to other American tents: for example Nemo tents can cost about 150 GBP more than in the US!
In terms of materials it looks like this tent is in the middle between really lightweight tents from Nemo and more "heavy duty" tents from Hilleberg.
### Reviews
* [ProPohody](https://propohody.com/msr-hubba-hubba-nx-review/) (in Russian)
* [ProPohody #2](https://propohody.com/msr-hubba-hubba-nx-2016/) (in Russian)
* [OutdoorGearLab](https://www.outdoorgearlab.com/reviews/camping-and-hiking/backpacking-tent/msr-hubba-hubba-nx) (in English)
### Buy
[385 GBP](https://www.ultralightoutdoorgear.co.uk/equipment-c3/tents-shelters-c25/two-person-tents-c26/hubba-hubba-nx-tent-p2405)
### Data
* floor area: 2.7 m² (29 sq ft)
* vestibule area: 1.62 m² (17 sq ft)
* weight: 1720 g
* rain fly: 20D nylon ripstop, PU coating (1200mm)
* inner tent: 20D nylon ripstop, 15D nylon mesh
* floor: 30D ripstop nylon, PU coating (3000mm), DWR coating
## Nemo Dragonfly 2p
[Official manufacturer link](https://www.nemoequipment.com/product/dragonfly/)
This tent got seriously raving reviews both from ProPohody and OutdoorGearLab. It is super lightweight (1410 g!) which still being spacious and convenient. However, I was put off by a delicate rain fly (outer tent), it is just 15D = 15 denier (it's a measure of fabric density) and by a weird cut in a rainfly on the side of the tent (a screenshot from the [video review below](https://propohody.com/nemo-dragonfly-2p-review/)):
This cut is suspiciously never visible on pictures from Nemo official website. According to the reviewers it's completely fine, since the bathtub floor is high and completely waterproof, but still, I don't like the look of it and don't see much point of it except for saving the weight, but for that price?
However, the comfort, total area and attention to details of this tent almost persuaded me to buy it, but then I realised that it might not be the best for Iceland/Scotland and other not so weather-friendly places I tend to visit.
### Reviews
* [ProPohody](https://propohody.com/nemo-dragonfly-2p-review/) (in Ukrainian, video review)
* [OutdoorGearLab](https://www.outdoorgearlab.com/reviews/camping-and-hiking/backpacking-tent/nemo-dragonfly-2) (in English)
### Buy
[420 GBP](https://www.ultralightoutdoorgear.co.uk/equipment-c3/tents-shelters-c25/two-person-tents-c26/dragonfly-2p-tent-p11473)
### Data
* floor area: 2.7 m² (29 sq ft)
* vestibule area: 1.8 m² (20 sq ft) = (0.9 m² x 2)
* weight: 1410 g
* rain fly: 15D nylon ripstop
* inner tent: 10D nylon ripstop
* floor: 20D nylon
* poles: 8.7mm
## Trimm HimLite DSL
[Official manufacturer link](https://www.trimm.cz/en/catalog/himlite-dsl-c1247.htm)
This is my current tent: I bought it around 6 years ago and described its usage in the introduction to this note. I decided to buy it after reading the review on ProPohody web site (it's a great website by the way, if you happen to read Russian or Ukrainian) and it hasn't disappointed! The ventilation is great, it's stable and tolerated quite serious winds in the Isle of Skye (one pole has been slightly bent though), the size - not so great: it feels somewhat cramped, especially with the backpacks inside, the vestibule is also on the smallish side.
### Reviews
* [ProPohody](https://propohody.com/trimm-himlite-dsl-review/) (in Russian)
### Data
* floor area: 2.5 m²
* vestibule area: 0.65 m²
* weight: \~1600 g (my version).
* floor: 10,000 mm H₂O
* rain fly: 4000 mm H₂O, nylon PU
* poles: 8.5mm
* height: 95 cm
## Exped Mira II HL
[Official manufacturer link](http://www.exped.com/italy/en/product-category/tents/mira-ii-hl)
This Swiss tent is a relatively late addition to the list, it looks like it's in the same class as [Nemo Dragonfly](/travel/tents#nemo-dragonfly-2p) but without the "weird cut": attention to details, lightweight, roomy and somewhat delicate. I'm using a simple waterproof urban backpack from Exped and I quite like it, so I'm already feeling somewhat loyal to the brand. However, when I added it to the list, I was already looking forward towards something more windproof, i.e. no fully mesh inner tent.
### Reviews
* [ProPohody](https://propohody.com/exped-mira-ii-hl-review/) (in Russian)
### Buy
[380 GBP](https://www.ultralightoutdoorgear.co.uk/equipment-c3/tents-shelters-c25/two-person-tents-c26/mira-ii-hl-tent-p3894)
### Data
* floor area: 2.7 m²
* vestibule area: 1.3 m²
* weight: 1500 g
* floor: 20D ripstop nylon, 1500 mm H₂O
* rain fly: 20D ripstop nylon
* inner tent: 15D nylon / 15D mesh
* poles: 8.5/9 mm
* height: 118 cm
## Hilleberg Niak
[Official manufacturer link](https://hilleberg.com/eng/tent/yellow-label-tents/niak/)
### Notes
Niak and other Hilleberg tents are apparently better equipped for bad weather: strong wind and long rain and since we are usually traveling to more challenging destinations (like Iceland, Scotland, Patagonia, Lake District, etc.), it might have more sense to invest in something more robust.
In particular, Hilleberg tents are set up "outer tent first", i.e. inner tent is already connected to an outer tent and you start pitching by just putting poles into sleeves of an outer tent, which make much more sense in rainy weather. Other tents in this list (including our current one) are "inner tent goes first", hence one either has to pitch the tent super quickly in the rain to minimise amount of rain getting into the tent or just wait until the rain stops or becomes less intense. The same goes about packing the tent: in Hilleberg you can even go inside, completely remove the inner tent under protection of the outer tent, pack it in the bag and only then start to dismantle the outer tent.
Niak was the first Hilleberg tent I started looking at, since it's the lightest. It comes from their "Yellow label" series, which are positioned as lightweight 3-season tents. But what is lightweight for Hilleberg, is not necessarily that for other produces in this list :) I think the extra weight mainly comes from the thicker floor (50D and 12000 mm H2O waterproof) and more reliable furniture (for example metal/alloy strap fasteners).
Details about the fabric used in Hilleberg tents:
However, I was not very impressed by the area and width of this tent (just 120 cm). A single vestibule was also rather small. In the past it was even named Niak 1.5 to stress that it's not super comfortable for two people. So, after all I decided to pass on that and look at [Hilleberg Anjan](/travel/tents#hilleberg-anjan-2) which is more spacious.
### Reviews
[SwitchbackTravel](https://www.switchbacktravel.com/reviews/hilleberg-niak) (in English)
### Buy
In some shops it comes with a free footprint (but you have to order it separately, it will be discounted from the price).
* [790 GBP](https://www.ultralightoutdoorgear.co.uk/equipment-c3/tents-shelters-c25/all-tents-c148/niak-2-person-tent-p10986)
* [790 GBP - Taunton](https://www.tauntonleisure.com/hilleberg-niak-tent-green.html) - has free DPD delivery (next working day) and free footprint.
### Data
* floor area: 2.6 m²
* vestibule area: 0.75 m²
* weight: 1700 g
* outer tent: 20D ripstop nylon, 5000 H₂O, [Kerlon 1000](https://hilleberg.com/eng/about-our-tents/materials-uncompromising-quality/#kerlon1000r)
* inner tent: 10D ripstop nylon, DWR
* floor: 50D, 12 000 mm H₂O
* poles: 9mm
## Hilleberg Anjan 2
[Official manufacturer link](https://hilleberg.com/eng/tent/yellow-label-tents/anjan-2/)
As you can see this tent has tunnel shape, I never used them before, so initially I was freaked out. However, after watching [pitching instructions video](https://www.youtube.com/watch?v=0HEP5jzXRBA) from Hilleberg and reading some articles "dome vs tunnel tents" I was fine. Even though dome-shaped tents are more popular now, there is nothing wrong with tunnel shaped tents, they both have pros and cons. Those pros and cons suspiciously vary from article to article though :)
I've decided to buy this tent because of the following considerations:
* almost all reviewers claimed that it was extremely weatherproof (if you compare to other lightweight tents of course, not in absolute values), OutdoorGearLab [gave it 10/10](https://www.outdoorgearlab.com/reviews/camping-and-hiking/backpacking-tent/hilleberg-anjan-2-gt#weather-resistance) for weather resistance
* it is still well under two kilos (1800 g), lighter than a typical Hilleberg tent
* it is pitched in "outer tent first" manner which looks very useful and reasonable in bad weather
* furniture looks amazing and reliable, allowing lots of adjustments
* Hilleberg seems to be a serious brand in the tents world and I'm a sucker for respectable brands :)
It seems that there are several models of this tent, corresponding to different years. Amazingly (and as opposed to the story with MSR Hubba Hubba NX) Hilleberg has improved certain design shortcomings which were highlighted by older reviews: for example in my relatively new version of the tent they've seriously improved vestibule zipper protection against rain and replaced the pegs with better ones (those two aspects were common weak points from older reviews).
I am going to test the tent in Patagonia soon, hopefully I'll update this note with my own positive experience.
### Buy
* [650 GBP](https://www.ellis-brigham.com/hilleberg-anjan-2-tent-256218) - I was able to find it cheaper on Ellis Brigham in their Covent Garden shop in London! Moreover, I've got 10% discount because of my BMC membership, it was a great deal!
* [715 GBP](https://www.ultralightoutdoorgear.co.uk/equipment-c3/tents-shelters-c25/all-tents-c148/anjan-2-tent-p10499) - that's the standard price for it in the UK :(
* Overall Hilleberg has [many dealers](https://hilleberg.com/eng/contact-support/dealers/) in the UK, but no one could sell me a red tent, the only available colour was dark green!
### Data
* floor area: 2.6 m² (28 sq ft)
* vestibule area: 1.2 m²
* weight: 1800 g
* outer tent: 20D ripstop nylon, 5000 H₂O, [Kerlon 1000](https://hilleberg.com/eng/about-our-tents/materials-uncompromising-quality/#kerlon1000r)
* inner tent: 10D ripstop nylon, DWR
* floor: 50D, PU, 12 000 mm H₂O
## Hilleberg Anjan 2 GT
[Official manufacturer link](https://hilleberg.com/eng/tent/yellow-label-tents/anjan-2-gt/)
This is just a version of [Anjan 2](/travel/tents#hilleberg-anjan-2) with an extended vestibule. I decided that there we don't need that much space for 300 extra grams and £112. Also, the extra length of the vestibule requires more space to pitch the tent, thus limiting the number of suitable areas for pitching.
### Buy
[827 GBP](https://www.alpinetrek.co.uk/hilleberg-anjan-2-gt-2-man-tent/)
### Reviews
[OutdoorGearLab](https://www.outdoorgearlab.com/reviews/camping-and-hiking/backpacking-tent/hilleberg-anjan-2-gt) (in English)
### Data
* floor area: 2.6 m² (28 sq ft)
* vestibule area: 2.5 m²
* weight: 2100 g
* outer tent: 20D ripstop nylon, 5000 H₂O, [Kerlon 1000](https://hilleberg.com/eng/about-our-tents/materials-uncompromising-quality/#kerlon1000r)
* inner tent: 10D ripstop nylon, DWR
* floor: 50D, PU, 12 000 mm H₂O
## Hilleberg Rogen
[Official manufacturer link](https://hilleberg.com/eng/tent/yellow-label-tents/rogen/)
The last out of four "Yellow Label" tents from Hilleberg, the heaviest and the only one with 20D inner tent (others are 15D), probably this explains the difference in weight. Since it's heavier than I was willing to accept, I decided not to consider it seriously, even though two entrances/vestibules looked quite attractive.
### Buy
[835 GBP](https://www.ultralightoutdoorgear.co.uk/equipment-c3/tents-shelters-c25/all-tents-c148/rogen-2-person-tent-p10987)
### Data
* floor area: 2.8 m² (28 sq ft)
* vestibule area: 2.0 m² = 1.0 x 2
* weight: 2100 g
* outer tent: 20D ripstop nylon, 5000 H₂O, [Kerlon 1000](https://hilleberg.com/eng/about-our-tents/materials-uncompromising-quality/#kerlon1000r)
* inner tent: 20D ripstop nylon, DWR
* floor: 50D, PU, 12 000 mm H₂O
## Other tents
I've also looked at several other interesting tents, but decided to dismiss it quickly due to various reasons:
* [Big Agnes Copper Spur HV UL 2](https://www.outdoorgearlab.com/reviews/camping-and-hiking/backpacking-tent/big-agnes-copper-spur-hv-ul2) - it is "Editor Choice" and seems to be popular, but they keep calling it "very delicate" and I don't want to be afraid to damage my tent by just mishandling it somewhat, so I decided to pass on that.
* [Nordisk Telemark 2](https://nordisk.co.uk/telemark-2-ulw/forest-green/p/364?ccode=true) - super lightweight and windproof, but too cramped and experimental as to my taste.
## Other reviews and comparisons
* [Generate a new comparison on OutdoorGearLab](https://www.outdoorgearlab.com/topics/camping-and-hiking/best-backpacking-tent/ratings?checkedid_array%5B%5D=54670)
* [SwitchbackTravel 5 tents comparison](https://www.switchbacktravel.com/reviews/hilleberg-niak#table)
* [SwitchbackTravel backpacking tents](https://www.switchbacktravel.com/best-tents-backpacking)
# Rust
Bits and pieces of Rust
### Useful commands
* To override default toolchain for a particular project: `rustup override set nightly`. The directory is stored in `~/.rustup/settings.toml` (in `overrides` section) separately from the project itself.
* To print all package dependencies as a nice tree in the command line, we can use `cargo tree` - more details [here](https://doc.rust-lang.org/beta/cargo/commands/cargo-tree.html) (works starting from Rust 1.44)
### Closures
* A [good post](https://stevedonovan.github.io/rustifications/2018/08/18/rust-closures-are-hard.html) by Steven Donovan about closures in Rust. It makes the connection between closures and structs, explains why `move |...|` is sometimes needed and why we have to add lifetimes annotations like `where F: Fn(i32) -> i32 + 'a>`
* All the nitty-gritty details are available in the Rust language reference (sections ["Closure expressions"](https://doc.rust-lang.org/stable/reference/expressions/closure-expr.html) and ["Closure types"](https://doc.rust-lang.org/stable/reference/types/closure.html)).
### Common/standard traits, conversion
* ["Rust's Built-in Traits, the When, How & Why"](https://llogiq.github.io/2015/07/30/traits.html) by Lloqiq (2015)
* ["The Common Rust Traits"](https://stevedonovan.github.io/rustifications/2018/09/08/common-rust-traits.html) by Steve Donovan (2018)
* ["Use conversion traits"](https://deterministic.space/elegant-apis-in-rust.html#use-conversion-traits) part from "Designing elegant APIs in Rust" by Pascal Hertleif (a very insightful post!) (2016)
* ["Conversion" ](https://doc.rust-lang.org/stable/rust-by-example/conversion.html)section in "Rust by Example"
* ["Convenient and idiomatic conversions in Rust"](https://ricardomartins.cc/2016/08/03/convenient_and_idiomatic_conversions_in_rust) by Ricardo Martins (2016)
* Rust reference: ["Special types and traits"](https://doc.rust-lang.org/reference/special-types-and-traits.html)
### Lifetimes, NLL
* [RFC-2094](https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md) about Non-Lexical Lifetimes: why and when they are needed, design
* ["Lifetimes"](https://doc.rust-lang.org/nomicon/lifetimes.html) and the following sections in Rustonomicon
* ["Understanding Rust Lifetimes"](https://medium.com/nearprotocol/understanding-rust-lifetimes-e813bcd405fa) by Maksym Zavershynskyi
* [Common Rust lifetimes misconceptions](https://github.com/pretzelhammer/rust-blog/blob/master/posts/common-rust-lifetime-misconceptions.md)
### Error handling
* [Error handling survey - 13 Nov 2019](https://blog.yoshuawuyts.com/error-handling-survey/) - many error handling packages reviewed and compared
* [Structuring and handling errors in 2020](https://nick.groenen.me/posts/rust-error-handling/)
* [Error handling in Rust](https://blog.burntsushi.net/rust-error-handling/) by Andrew Gallant (burntsushi)
* [The state of error handling in Rust 2018 edition](https://users.rust-lang.org/t/the-state-of-error-handling-in-the-2018-edition/23263)
* [Notice: failure is deprecated](https://www.reddit.com/r/rust/comments/gcbcew/notice_failure_is_deprecated/) on Reddit
### Profiling on Mac
* [Profiling with](https://gist.github.com/loderunner/36724cc9ee8db66db305#profiling-with-sample) `sample`
* ["Rust profiling with DTrace and FlameGraph on MacOs"](https://carol-nichols.com/2017/04/20/rust-profiling-with-dtrace-on-osx/) by Carol Nichols, a simple easy to follow reference
* [Inferno](https://docs.rs/inferno/0.9.5/inferno/) by Jon Gjengset for producing flame-graphs from process samples. Rust port of [flame-graph](https://github.com/brendangregg/FlameGraph) tools. Its README.md on GitHub has lots of useful information. Btw, there is a 5 hours [video stream](https://www.youtube.com/watch?v=jTpK-bNZiA4) of how this tool was actually coded live!
### Misc
* ["Rust Tidbits: What is a Lang Item?"](https://manishearth.github.io/blog/2017/01/11/rust-tidbits-what-is-a-lang-item/) - an interesting explanation about traits and other items known to the Rust compiler and marked with `#[lang]` annotation. I really enjoyed this article, but for some reason it was quite hard to google to find it again (perhaps because I googled "traits" and "lang" is not a very googleable term).
# Command line
* `rsync` is a better `cp`. You can easily get a copy with progress bar by just using `rsync -P file_a file_b` It also has a ton of other useful functions. Originally picked it up from this post:
* To get the full processor name on Mac:
```
➜ sysctl -n machdep.cpu.brand_string
Intel(R) Core(TM) i7-3740QM CPU @ 2.70GHz
```
* To create a zero-filled file of specified size:
```bash
dd if=/dev/zero of=32mb.bin bs=32m count=1
```
* To run a program and report its maximum memory usage and other interesting things we can use usual GNU `time`(on Mac: `brew install gnu-time` will install it as `gtime`).
```
➜ gtime -v target/release/c
iterator returned: 384
Command being timed: "target/release/c"
User time (seconds): 0.77
System time (seconds): 0.62
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:01.40
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 3125868
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 781620
Voluntary context switches: 3
Involuntary context switches: 112
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
```
* Or even simpler, to just print maximum resident set size at the end: `gtime -f %M program_name`
* Convert an SVG files to multiple PNG files with different resolutions and pack them all in an ICO file:
```
# install `svgexport` and `imagemagick`:
brew install imagemagick
npm install -g svgexport
# this worked better than ImageMagick for me:
svgexport favicon.svg 16.png 16:16
svgexport favicon.svg 32.png 32:32
# and so on, and then combine them:
convert 16.png 24.png 32.png -colors 256 favicon.ico
```
* Run a command every 5 seconds: `watch -n5 command`
* Convert GPS routes from .gpx to .kml without creating lots of points:
```
gpsbabel -i gpx -f input.gpx -o kml,points=0 -F output.kml
```
# GMail backup
How to get all your email from Google Mail in a nice searchable format
## Attempt #1: Google Takeout - didn't fully work
Google has a special service called [Google Takeout](https://takeout.google.com/settings/takeout) designed to download all your user data from Google accounts, including GMail and Google Photos. It's easy to use: you just choose what labels you want to export and in which format, they will take some time to prepare a zip archive with a single .mbox file. Mbox is just a giant text file containing all your messages concatenated (including chat messages from Google Talk). In my case the archive was around 2 Gb and .mbox file was around 7 Gb. Then you can import that file in an email client (say Mozilla Thunderbird) to read, search and index your email.
So far so good, but it didn't quite work for me, since most of my e-mail is in Russian. It has turned out that this .mbox file is encoded in UTF-8 and before preparing it, Google has just converted every symbol which is not ASCII or UTF-8 into � (which is a Unicode character for "replacement character"), ignoring charset field in "Content-Type" MIME headers. It has also happened [to someone else](https://webapps.stackexchange.com/questions/71153/takeout-breaks-my-non-ascii). Hence, that contents of non-UTF-8 messages was basically lost and my Thunderbird was unable to read any messages in KOI8-R or Windows-1251 encodings used for Russian language before UTF-8 era.
However, if your email is mostly in English or in UTF-8 you'll be fine and I think this is the easiest way to go.
## Attempt #2: GYB (Got Your Back) - worked fine!
["Got Your Back"](https://github.com/jay0lee/got-your-back) is an open source command line tool working with Google Mail through Google API over HTTPS. It's written in Python, works on Mac, Win and Linux and authorises itself through some Google services, obtaining OAuth 2.0 token and stuff. It sounds complicated, but the tool will guide you through the process. The user manual is [here](https://github.com/jay0lee/got-your-back/wiki).
The tool synced my email under one hour: it created a hierarchy of directories of this shape: `year/month/day/some-email-id.eml`. That .eml format is just plain text containing message headers and plain text email content in the original encoding (no automatic conversion to �!). Also it has created an sqlite database for correspondence between GMail labels and messages. It's possible to incrementally update the backup, so it doesn't take long to update the backup.
Then again, it's possible to search through those .eml files with just `ripgrep` or other text searching utilities. Or you can import it all in Mozzila Thunderbird (using their Import/Export add-on available from `Options -> Extensions`) and search from there. However, note that labels will be lost in this way (since they are in the sqlite database). I don't care much about labels to be fair.
## Other solutions
* I've also tried `offlineimap` which looked good, but it took forever to sync my email (after a week it was still working on it!) and it was often failing with intermittent errors, so I ditched it. Also it required setting up a non-trivial config for GMail before you can even start using it.
* A friend of mine has successfully used [mbsync](http://isync.sourceforge.net/) to sync his Google email into MailDir format in about an hour. I haven't tried this solution.
# Git
Useful commands which I had to google
* To pull and merge master from origin without leaving the current branch: `git fetch origin master:master`
* To push a new branch to origin (assuming it's checked out now): `git push -u origin HEAD`
# CSS
## References
* Mozilla Developers Network: [Web Docs](https://developer.mozilla.org/en-US/docs/Web/CSS): amazing high-quality reference, HTML/CSS/JS tutorials, browser compatibility tables
* css-tricks.com [guides archive](https://css-tricks.com/guides/): guides to Flexbox, Grid, Centering CSS and many others
## Flexbox
* [flexbugs](https://github.com/philipwalton/flexbugs) - a Github repository tracking browsers bugs and their fixes related to Flexbox
* [CSS spec](https://drafts.csswg.org/css-flexbox/) on Flexbox - quite readable and nice!
# Resizing video with ffmpeg
How to make a large video smaller
## Intro
I've recorded a video on a MacBook Pro 2019, 16'' in QuickTime player. It's about 100 Mb.
I wanted to convert it to something smaller without losing much quality.
## TLDR
Use this:
```
ffmpeg -i input.mov -vcodec libx264 -crf 28 -f mov -acodec copy output.mov
```
CRF parameter - *constant rate factor* - defines the quality (the lower the number, the better quality), it can take values from 0 to 53. For x264, sane values are between 18 and 28. Above I use 28, which is the lowest quality, which is still kinda acceptable.
## Details
First I've looked at this answer:
Which gives some command line using `ffmpeg`.
I've installed ffmpeg (`brew install ffmpeg`) and became interested in what codecs/containers it supports and what all this stuff generally means.
Also, by following advice from the article above I could convert my file easily from 100 Mb to 9 Mb using this command line:
```
ffmpeg -i input.mov -vcodec libx265 -crf 28 output.mp4
```
However, when I tried to send it via WhatsApp, it was sent fine (although I need to send it as a document, it's not recoginised when I try to send it as audio/video, i.e. the file is just not visible, so I can't select it as a video), but when I tried to open it on iPhone SE, it didn't work.
So ok, I googled a little bit: iPhones should be opening .mp4 containers without any issues, so I was not sure why it didn't work.
Eventually it turned out that the problem was with H.265 codec (which is more efficient, but less supported), in fact for better support one should use more popular H.264 codec which is supported well on iPhones (and presumably other devices).
If I encode my files like this:
```
ffmpeg -i input.mov -vcodec libx264 -crf 28 -f mov output.mov
```
It works fine, on macOS I can immediately see preview of the video, I can send it as a video in WhatsApp and it's played normally on iPhone.
Also, if you want to keep the sound as is, there is `-c:a copy` option (which means "codec:audio = copy":
```
ffmpeg -i input.mov -vcodec libx264 -crf 28 -f mov -acodec copy output.mov
```
## Useful command for inspecting files information
```
ffprobe -show_streams
```
## Links
-- ffmpeg doc
-- a nice description of CRF parameter with plots
-- containers and codecs big table
# Mono to stereo
How to change a video file, so that you can hear the audio in both channels, even when it was recorded with mono equipment
## Introduction
Normally when you record an audio or a video with an external microphone -- it just records one channel. For example this happens to me if I record a video using QuickTime player and use my external microphone plugged into an audio interface. Then, as a result, when you listen to that video with your headphones, you can just hear the sound in one ear: either left or right. This is of course, not what you want, you want to hear the same channel in both left and right ears.
I've tried to figure out how to do it using different tools: iMovie, DaVinci Resolve and command line `ffmpeg` tool.
iMovie can't do it right now (as per version 10.2.1), in DaVinci Resolve you can do it, by changing the clip attributes (setting both channels to the same input), which is explained here:
But I must admit that's it's rather an overkill: to install several gegabytes of a serious video editing tool DaVince Resolve to just do a simple thing like this. So I'd prefer to quickly do it with a couple of `ffmpeg` commands. However, as usual, `ffmpeg` options quite difficult to get right if you are not a regular user of that tool. So I had to spent some time on that, but at the end I think I've found a simple sequence of commands which I can understand and that do the job.
## ffmpeg way
We start with `i.mov` file which was recorded by QuickTime player (File -> New Movie Recording) using an external microphone.
* First we need to extract the audio portion of that file:
```
ffmpeg -i i.mov -vn -acodec copy orig.aac
```
This takes `i.mov` files, disables the video (`-vn`) and copies the audio (`-acodec copy`) and produces a new audio file `orig.aac` I am doing all of this on a Mac, so my videos are recorded using typical formats and codecs used by Apple.
* Now, we can look at this file and see the streams and their properties:
```
> ffprobe -show_streams orig.aac
...
codec_name=aac
channels=2
channel_layout=stereo
...
```
You can see that interestingly enough, this is actualy a "stereo" file, i.e. it has two channels. Probably the second channel is just silence. This was actually causing the problems with other methods from StackOverflow or "Manipulating audio channels" [page](https://trac.ffmpeg.org/wiki/AudioChannelManipulation). I.e. I expected it to be a real mono, but in fact it was stereo with an empty channel.
* Now let's convert it to a real mono, since that's what it is. I do this using advice from "Manipulating audio channels" page above. I combine both channels into a single mono stream.
```
ffmpeg -i orig.aac -ac 1 mono.aac
```
Let's look again at the result:
```
> ffprobe -show_streams mono.aac
...
channels=1
channel_layout=mono
...
```
Now it's mono, and when players will play this, they will know that they need to play the same channel in both ears of the headphones. You can quickly try playing with, say, `ffplay mono.aac`
* Finally, we need to replace our original audio stream in our starting video file with this updated stream. We don't need to remix anything, since we haven't actually changed much, so we just copy video stream from the original file `i.mov` and copy audio stream from the `mono.aac` file to get the final result.
```
ffmpeg -i i.mov -i mono.aac -c copy -map 0:v:0 -map 1:a:0 new.mov
```
This involves doing some mapping. The numeration there starts from zero, somewhat confusingly, but it just maps the video of the first stream (`i.mov`) to the first video stream of the output (`-map 0:v:0`), and the audio of the second stream to the first audio stream of the resulting file (`-map 1:a:0`).
That's it, you can just combine those commands into a handy shell script and use it to quickly fix your files.