程序代写 CMSC330 or your C project from CMSC260), or some project you found from the

# Lecture 8

## Project Introduction

Copyright By PowCoder代写 加微信 powcoder

### Project introduction
In this project, you will work with your teammate(s) to achieve some programming tasks. 30% of your final grade will come from this project. You and your teammate(s) need to propose the project you would like to work on together. The due date for this project is Dec 10 at noon.

You are welcome to choose any project that you and your teammate(s) are interested in. It could be something you have implemented in another programming language (e.g., your Ruby project from CMSC330 or your C project from CMSC260), or some project you found from the internet that is not written in Rust. You can also fix an issue or bug of an existing Rust crate or add some new functionality to an existing crate. If you want to solve some open questions in Rust, the Are We X Yet project is a good starting point.

### Groups
You must form a group of 2-3 students enrolled in this course. If you have a project idea and you’re not able to convince one or two other people to work on it, you should instead join another group.

### Workload
Your group will have five weeks to do the project. Each week, each group member should spend 2 hours on the project. The size of your proposed project should be linearly correlated with the number of people in your group. If your group has two members, your project should be five times larger than a homework assignment. If your group has three members, your project should be 7.5 times larger than a homework assignment. This is because our bi-weekly homework assignments are designed to take 4 hours to complete.

### Important deadlines:
– Nov 5 – Project proposal due
– Nov 19 – Project milestone #1 due
– Dec 10 – Final write-up due

### Project Proposal:
Each group needs to submit the proposal once. Unless you have a very good reason, you should limit the proposal to one page. You need to describe the following aspects of your proposed project:
1. The title of your project
2. Team members
3. Introduction and background (your readers might not have the background knowledge of the area you want to work on)
4. Goals. Include a 100% goal, representing what you expect to achieve, a 75% goal (if things go slower than expected), and a 125% goal (if the project turns out to be easier than you thought). You can earn an A even if you only achieve your 75% goal if you justify why the project turned out to be harder than you thought.
5. Specific aims and objectives
6. Cited references

Each group should submit only once on ELMS.

### Notes:
– Meet with your teammates frequently (at least once a week).
– Work together. Please don’t try to divide the project into independent tasks and assign them to your group members. You will have lots of problems when merging them together. We expect you to use a Git repository to manage your work and commit frequently.
– Compile frequently.
– Write unit and integration tests.
– Ask for help if you are stuck for more than two hours.

## RefCell and Interior Mutability

Source: [Rust book](https://doc.rust-lang.org/book/ch15-05-interior-mutability.html), [Additional notes](https://ricardomartins.cc/2016/06/08/interior-mutability)

## `RefCell`

Interior mutability is a design pattern in Rust that allows you to mutate data even when there are immutable references to that data; normally, this action is disallowed by the borrowing rules. To mutate data, the pattern uses unsafe code inside a data structure to bend Rust’s usual rules that govern mutation and borrowing.

We will explore this concept using the `RefCell` type, which follows the interior mutability pattern.

Unlike `Rc`, the `RefCell` type represents single ownership over the data it holds. So, what makes `RefCell` different from a type like `Box`?

Recall the borrowing rules we learned in previous lectures:
– At any given time, you can have either one mutable reference or any number of immutable references.
– References must always be valid.

When using `Box`, the borrowing rules’ invariants are enforced at compile time. With `RefCell`, these invariants are enforced at runtime. With references, if you break these rules, you’ll get a compiler error. With `RefCell`, if you break these rules, your program will panic and exit.

Checking borrowing rules at compile time has the advantage of catching errors sooner in the development process, and there is no impact on runtime performance because all the analysis is completed beforehand. For those reasons, checking the borrowing rules at compile time is the best choice in the majority of cases.

However, there are other scenarios where one might want to take advantage of the additional flexibility afforded by checking the borrowing rules at runtime. Because some analyses are impossible, if the Rust compiler can’t be sure the code complies with the ownership rules, it might reject a correct program; in this way, it is conservative. The `RefCell` type is useful when you’re sure your code follows the borrowing rules but the compiler is unable to understand and guarantee that.

### When to use each type?

– `Rc` enables multiple owners of the same data; `Box` and `RefCell` have single owners.
– `Box` allows immutable or mutable borrows checked at compile time; `Rc` allows only immutable borrows checked at compile time; `RefCell` allows immutable or mutable borrows checked at runtime.
– Because `RefCell` allows mutable borrows checked at runtime, you can mutate the value inside the `RefCell` even when the `RefCell` is immutable.

### Borrowing review

Will this code compile? Why?

fn main() {
let x = 5;
let y = &mut x;

However, there are situations in which it would be useful for a value to mutate itself in its methods but appear immutable to other code. Code outside the value’s methods would not be able to mutate the value. Using `RefCell` is one way to get the ability to have interior mutability. But `RefCell` doesn’t get around the borrowing rules completely: the borrow checker in the compiler allows this interior mutability, and the borrowing rules are checked at runtime instead. If you violate the rules, you’ll get a panic! instead of a compiler error.

### Interior mutability example

In this example, we’ll create a library that tracks a value against a maximum value and sends messages based on how close to the maximum value the current value is. This library could be used to keep track of a user’s quota for the number of API calls they’re allowed to make, for example. Our library will only provide the functionality of tracking how close to the maximum a value is and what the messages should be at what times. Applications that use our library will be expected to provide the mechanism for sending the messages: the application could put a message in the application, send an email, send a text message, or something else. The library doesn’t need to know that detail. It only uses a trait we’ll provide called Messenger.

pub trait Messenger {
fn send(&self, msg: &str);

pub struct LimitTracker<'a, T: Messenger> {
messenger: &’a T,
value: usize,
max: usize,

impl<'a, T> LimitTracker<'a, T>
T: Messenger,
pub fn new(messenger: &T, max: usize) -> LimitTracker {
LimitTracker {
messenger,

pub fn set_value(&mut self, value: usize) {
self.value = value;

let percentage_of_max = self.value as f64 / self.max as f64;

if percentage_of_max >= 1.0 {
self.messenger.send(“Error: You are over your quota!”);
} else if percentage_of_max >= 0.9 {
self.messenger
.send(“Urgent warning: You’ve used up over 90% of your quota!”);
} else if percentage_of_max >= 0.75 {
self.messenger
.send(“Warning: You’ve used up over 75% of your quota!”);

The Messenger trait is the interface our mock object needs to implement so that the mock can be used in the same way a real object is. The other important part is that we want to test the behavior of the set_value method on the LimitTracker. We can change what we pass in for the value parameter, but set_value doesn’t return anything for us to make assertions on. We want to be able to say that if we create a LimitTracker with something that implements the Messenger trait and a particular value for max, when we pass different numbers for value, the messenger is told to send the appropriate messages.

We need a mock object that, instead of sending an email or text message when we call send, will only keep track of the messages it’s told to send. We can create a new instance of the mock object, create a LimitTracker that uses the mock object, call the set_value method on LimitTracker, and then check that the mock object has the messages we expect. The following example shows an attempt to do this, but the borrow checker won’t allow it.

#[cfg(test)]
mod tests {
use super::*;

struct MockMessenger {
sent_messages: Vec,

impl MockMessenger {
fn new() -> MockMessenger {
MockMessenger {
sent_messages: vec![],

impl Messenger for MockMessenger {
fn send(&self, message: &str) {
self.sent_messages.push(String::from(message));

fn it_sends_an_over_75_percent_warning_message() {
let mock_messenger = MockMessenger::new();
let mut limit_tracker = LimitTracker::new(&mock_messenger, 100);

limit_tracker.set_value(80);

assert_eq!(mock_messenger.sent_messages.len(), 1);

What’s the problem with this code? Why won’t the borrow checker allow this. (Hint: Look at `send()`). When compiling this example, we get the following error:

$ cargo test
Compiling limit-tracker v0.1.0 (file:///projects/limit-tracker)
error[E0596]: cannot borrow `self.sent_messages` as mutable, as it is behind a `&` reference
–> src/lib.rs:58:13
2 | fn send(&self, msg: &str);
| —– help: consider changing that to be a mutable reference: `&mut self`
58 | self.sent_messages.push(String::from(message));
| ^^^^^^^^^^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable

error: aborting due to previous error

For more information about this error, try `rustc –explain E0596`.
error: could not compile `limit-tracker`

To learn more, run the command again with –verbose.
warning: build failed, waiting for other jobs to finish…
error: build failed

Modifying the MockMessenger to keep track of the messages, because the send method takes an immutable reference to self. We also can’t take the suggestion from the error text to use &mut self instead, because then the signature of send wouldn’t match the signature in the Messenger trait definition. However, we can fix this example by using interior mutability. We will store the sent_messsages within a `RefCell`, and then the send method will be able to modify hte sent_messages to store the messages we’ve seen. Here is an example implementation.

#[cfg(test)]
mod tests {
use super::*;
use std::cell::RefCell;

struct MockMessenger {
sent_messages: RefCell>,

impl MockMessenger {
fn new() -> MockMessenger {
MockMessenger {
sent_messages: RefCell::new(vec![]),

impl Messenger for MockMessenger {
fn send(&self, message: &str) {
self.sent_messages.borrow_mut().push(String::from(message));

fn it_sends_an_over_75_percent_warning_message() {
// –snip–

assert_eq!(mock_messenger.sent_messages.borrow().len(), 1);

The sent_messages field is now of type `RefCell>` instead of `Vec`. In the new function, we create a new `RefCell>` instance around the empty vector.

For the implementation of the send method, the first parameter is still an immutable borrow of self, which matches the trait definition. We call borrow_mut on the `RefCell>` in self.sent_messages to get a mutable reference to the value inside the `RefCell>`, which is the vector. Then we can call push on the mutable reference to the vector to keep track of the messages sent during the test.

The last change we have to make is in the assertion: to see how many items are in the inner vector, we call borrow on the `RefCell>` to get an immutable reference to the vector.

### How `Refcell` works

When creating immutable and mutable references, we use the & and &mut syntax, respectively. With `RefCell`, we use the borrow and borrow_mut methods, which are part of the safe API that belongs to `RefCell`. The borrow method returns the smart pointer type `Ref`, and borrow_mut returns the smart pointer type `RefMut`. Both types implement Deref, so we can treat them like regular references.

The `RefCell` keeps track of how many `Ref` and `RefMut` smart pointers are currently active. Every time we call borrow, the `RefCell` increases its count of how many immutable borrows are active. When a `Ref` value goes out of scope, the count of immutable borrows goes down by one. Just like the compile-time borrowing rules, `RefCell` lets us have many immutable borrows or one mutable borrow at any point in time.

Now if we violate the borrowing rules, we’ll get an error at compile time rather than at runtime. Here is an example.

impl Messenger for MockMessenger {
fn send(&self, message: &str) {
let mut one_borrow = self.sent_messages.borrow_mut();
let mut two_borrow = self.sent_messages.borrow_mut();

one_borrow.push(String::from(message));
two_borrow.push(String::from(message));

We can see that with refcell this example will compile, but when we run it the program will panic.

thread ‘main’ panicked at ‘already borrowed: BorrowMutError’, src/lib.rs:60:53
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Notice that the code panicked with the message already borrowed: BorrowMutError. This is how `RefCell` handles violations of the borrowing rules at runtime.

### Combining Rc and RefCell

It is common to use `RefCell` together with `Rc`. Recall that `Rc` lets you have multiple owners of some data, but it only gives immutable access to that data. If you have an `Rc` that holds a `RefCell`, you can get a value that can have multiple owners and that you can mutate! Because `Rc` holds only immutable values, we can’t change any of the values in the list once we’ve created them. Now we will add in `RefCell` to gain the ability to change the values.

#[derive(Debug)]
enum List {
Cons(Rc>, Rc),

use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
let value = Rc::new(RefCell::new(5));

let a = Rc::new(Cons(Rc::clone(&value), Rc::new(Nil)));

let b = Cons(Rc::new(RefCell::new(3)), Rc::clone(&a));
let c = Cons(Rc::new(RefCell::new(4)), Rc::clone(&a));

*value.borrow_mut() += 10;

println!(“a after = {:?}”, a);
println!(“b after = {:?}”, b);
println!(“c after = {:?}”, c);

Here we create a value that is an instance of `Rc>` and store it in a variable named value so we can access it directly later. Then we create a List in a with a Cons variant that holds value. We need to clone value so both a and value have ownership of the inner 5 value rather than transferring ownership from value to a or having a borrow from value.

We wrap the list a in an `Rc` so when we create lists b and c, they can both refer to a. After we’ve created the lists in a, b, and c, we add 10 to the value in value. We do this by calling borrow_mut on value, which uses automatic dereferencing to dereference the `Rc` to the inner `RefCell` value. The borrow_mut method returns a `RefMut` smart pointer, and we use the dereference operator on it to change the inner value. When we print a, b, and c, we can see that they all have the modified value of 15 rather than 5.

$ cargo run
Compiling cons-list v0.1.0 (file:///projects/cons-list)
Finished dev [unoptimized + debuginfo] target(s) in 0.63s
Running `target/debug/cons-list`
a after = Cons(RefCell { value: 15 }, Nil)
b after = Cons(RefCell { value: 3 }, Cons(RefCell { value: 15 }, Nil))
c after = Cons(RefCell { value: 4 }, Cons(RefCell { value: 15 }, Nil))

Here we have an outwardly immutable List value. But we can use the methods on `RefCell` that provide access to its interior mutability so we can modify our data when we need to. The runtime checks of the borrowing rules protect us from data races, and it’s sometimes worth trading a bit of speed for this flexibility in our data structures.

The standard library has other types that provide interior mutability, such as `Cell`, which is similar except that instead of giving references to the inner value, the value is copied in and out of the `Cell`. There’s also `Mutex`, which offers interior mutability that’s safe to use across threads.

### Memory leaks

Rust’s memory safety guarantees make it difficult, but not impossible, to accidentally create memory that is never cleaned up (known as a memory leak). Preventing memory leaks entirely is not one of Rust’s guarantees in the same way that disallowing data races at compile time is.

We can see that Rust allows memory leaks by using `Rc` and `RefCell`: it’s possible to create references where items refer to each other in a cycle. This creates memory leaks because the reference count of each item in the cycle will never reach 0, and the values will never be dropped.

We can see this in the following example.

use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
enum List {
Cons(i32, RefCell>),

impl List {
fn tail(&self) -> Option<&RefCell>> {
match self {
Cons(_, item) => Some(item),
Nil => None,

fn main() {
let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));

println!(“a initial rc count = {}”, Rc::strong_count(&a));
println!(“a next item = {:?}”, a.tail());

let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

println!(“a rc count after b creation = {}”, Rc::strong_count(&a));
println!(“b initial rc count = {}”, Rc::strong_count(&b));
println!(“b next item = {:?}”, b.tail());

if let Some(link) = a.tail() {
*link.borrow_mut() = Rc::clone(&b);

println!(“b rc count after changing a = {}”, Rc::strong_count(&b));
println!(“a rc count after changing a = {}”, Rc::strong_count(&a));

// Uncomment the next line to see that we have a cycle;
// What will happen?
// println!(“a next item = {:?}”, a.tail());

If we uncomment the println, what will happen? We will overflow the stack. The reference count of the `Rc` instances in both a and b are 2 after we change the list in a to point to b. At the end of main, Rust drops the variable b, which decreases the reference count of the `Rc` instance from 2 to 1. The memory that `Rc` has on the heap won’t be dropped at this point, because its reference count is 1, not 0. Then Rust drops a, which decreases the reference count of the a `Rc` instance from 2 to 1 as well. This can’t be dropped either, because the other `Rc` instance still refers to it.

This is an example of a reference cycle, which will result in leaked memory which

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com