X-Git-Url: https://git.ralfj.de/rust-101.git/blobdiff_plain/188b1ec1b8528e2326791feccc8077e15bd60182..73bdc651abfbe484d9c97835efc4ad272c44d325:/src/part14.rs?ds=inline diff --git a/src/part14.rs b/src/part14.rs index 6550fe5..5c00905 100644 --- a/src/part14.rs +++ b/src/part14.rs @@ -15,8 +15,8 @@ //@ `[T]` is the type of an (unsized) *array*, with elements of type `T`. All this means is that there's a contiguous //@ region of memory, where a bunch of `T` are stored. How many? We can't tell! This is an unsized type. Just like for //@ trait objects, this means we can only operate on pointers to that type, and these pointers will carry the missing -//@ information - namely, the length. Such a pointer is called a *slice*. As we will see, a slice can be split. -//@ Our function can thus take a borrowed slice, and promise to sort all elements in there. +//@ information - namely, the length (they will be *fat pointers*). Such a reference to an array is called a *slice*. As we will see, a slice can be split. +//@ Our function can thus take a mutable slice, and promise to sort all elements in there. pub fn sort(data: &mut [T]) { if data.len() < 2 { return; } @@ -27,7 +27,7 @@ pub fn sort(data: &mut [T]) { /* Invariant: pivot is data[0]; everything with index (0,lpos) is <= pivot; [rpos,len) is >= pivot; lpos < rpos */ loop { - // **Exercise 13.1**: Complete this Quicksort loop. You can use `swap` on slices to swap two elements. Write a + // **Exercise 14.1**: Complete this Quicksort loop. You can use `swap` on slices to swap two elements. Write a // test function for `sort`. unimplemented!() } @@ -38,7 +38,7 @@ pub fn sort(data: &mut [T]) { // Finally, we split our slice to sort the two halves. The nice part about slices is that splitting them is cheap: //@ They are just a pointer to a start address, and a length. We can thus get two pointers, one at the beginning and //@ one in the middle, and set the lengths appropriately such that they don't overlap. This is what `split_at_mut` does. - //@ Since the two slices don't overlap, there is no aliasing and we can have them both mutably borrowed. + //@ Since the two slices don't overlap, there is no aliasing and we can have both of them as unique, mutable slices. let (part1, part2) = data.split_at_mut(lpos); //@ The index operation can not only be used to address certain elements, it can also be used for *slicing*: Giving a range //@ of indices, and obtaining an appropriate part of the slice we started with. Here, we remove the last element from @@ -47,8 +47,8 @@ pub fn sort(data: &mut [T]) { sort(part2); /*@*/ } -// **Exercise 13.2**: Since `String` implements `PartialEq`, you can now change the function `output_lines` in the previous part -// to call the sort function above. If you did exercise 12.1, you will have slightly more work. Make sure you sort by the matched line +// **Exercise 14.2**: Since `String` implements `PartialEq`, you can now change the function `output_lines` in the previous part +// to call the sort function above. If you did exercise 13.1, you will have slightly more work. Make sure you sort by the matched line // only, not by filename or line number! // Now, we can sort, e.g., an vector of numbers. @@ -59,7 +59,7 @@ fn sort_nums(data: &mut Vec) { } // ## Arrays -//@ An *array* in Rust is given be the type `[T; n]`, where `n` is some *fixed* number. So, `[f64; 10]` is an array of 10 floating-point +//@ An *array* in Rust is given by the type `[T; n]`, where `n` is some *fixed* number. So, `[f64; 10]` is an array of 10 floating-point //@ numbers, all one right next to the other in memory. Arrays are sized, and hence can be used like any other type. But we can also //@ borrow them as slices, e.g., to sort them. fn sort_array() { @@ -69,7 +69,7 @@ fn sort_array() { // ## External Dependencies //@ This leaves us with just one more piece to complete rgrep: Taking arguments from the command-line. We could now directly work on -//@ [`std::env::args`](http://doc.rust-lang.org/stable/std/env/fn.args.html) to gain access to those arguments, and this would become +//@ [`std::env::args`](https://doc.rust-lang.org/stable/std/env/fn.args.html) to gain access to those arguments, and this would become //@ a pretty boring lesson in string manipulation. Instead, I want to use this opportunity to show how easy it is to benefit from //@ other people's work in your program. //@ @@ -82,7 +82,7 @@ fn sort_array() { //@ arguments based on the usage string. External dependencies are declared in the `Cargo.toml` file. //@ I already prepared that file, but the declaration of the dependency is still commented out. So please open `Cargo.toml` of your workspace -//@ now, and enabled the two commented-out lines. Then do `cargo build`. Cargo will now download the crate from crates.io, compile it, +//@ now, and enable the two commented-out lines. Then do `cargo build`. Cargo will now download the crate from crates.io, compile it, //@ and link it to your program. In the future, you can do `cargo update` to make it download new versions of crates you depend on. //@ Note that crates.io is only the default location for dependencies, you can also give it the URL of a git repository or some local //@ path. All of this is explained in the [Cargo Guide](http://doc.crates.io/guide.html). @@ -91,10 +91,11 @@ fn sort_array() { // Remove the attribute of the `rgrep` module to enable compilation. #[cfg(feature = "disabled")] pub mod rgrep { - // Now that `docopt` is linked, we can first add it to the namespace and then import shorter names with `use`. We also import some other pieces that we will need. + // Now that `docopt` is linked, we can first add it to the namespace with `extern crate` and then import shorter names with `use`. + // We also import some other pieces that we will need. extern crate docopt; use self::docopt::Docopt; - use part12::{run, Options, OutputMode}; + use part13::{run, Options, OutputMode}; use std::process; // The `USAGE` string documents how the program is to be called. It's written in a format that `docopt` can parse. @@ -108,7 +109,7 @@ Options: // This function extracts the rgrep options from the command-line arguments. fn get_options() -> Options { - // Parse `argv` and exit the program with an error message if it fails. This is taken from the [`docopt` documentation](http://burntsushi.net/rustdoc/docopt/). + // This parses `argv` and exit the program with an error message if it fails. The code is taken from the [`docopt` documentation](http://burntsushi.net/rustdoc/docopt/).
//@ The function `and_then` takes a closure from `T` to `Result`, and uses it to transform a `Result` to a //@ `Result`. This way, we can chain computations that only happen if the previous one succeeded (and the error //@ type has to stay the same). In case you know about monads, this style of programming will be familiar to you. @@ -130,8 +131,8 @@ Options: //@ encoded string, that is, a bunch of bytes in memory (`[u8]`) that are valid according of UTF-8. `str` is unsized. `&str` //@ stores the address of the character data, and their length. String literals like "this one" are //@ of type `&'static str`: They point right to the constant section of the binary, so - //@ However, the borrow is valid for as long as the program runs, hence it has lifetime `'static`. Calling - //@ `to_string` will copy the string data into an owned buffer on the heap, and thus convert it to `String`. + //@ the reference is valid for the entire program. The bytes pointed to by `pattern`, on the other hand, are owned by someone else, + //@ and we call `to_string` on it to copy the string data into a buffer on the heap that we own. let mode = if count { OutputMode::Count } else if sort { @@ -153,9 +154,9 @@ Options: } } -// **Exercise 13.3**: Wouldn't it be nice if rgrep supported regular expressions? There's already a crate that does all the parsing and matching on regular +// **Exercise 14.3**: Wouldn't it be nice if rgrep supported regular expressions? There's already a crate that does all the parsing and matching on regular // expression, it's called [regex](https://crates.io/crates/regex). Add this crate to the dependencies of your workspace, add an option ("-r") to switch // the pattern to regular-expression mode, and change `filter_lines` to honor this option. The documentation of regex is available from its crates.io site. // (You won't be able to use the `regex!` macro if you are on the stable or beta channel of Rust. But it wouldn't help for our use-case anyway.) -//@ [index](main.html) | [previous](part13.html) | [next](part15.html) +//@ [index](main.html) | [previous](part13.html) | [raw source](workspace/src/part14.rs) | [next](part15.html)