React
1. Readme
React
实现基本的 React 系统。
React 式编程是一种编程范例,它着重于如何根据彼此来计算值,以允许对一个值的更改,自动传播到其他值,如在电子表格中。
实现一个基本的 React 系统,其中,有带可设置值的单元(”输入”单元),还有能根据其他单元计算值的单元(”计算”单元)。实现更新,以便当输入值改变时,(关联的)值会传播,直到一个新的稳定的系统状态。
此外,计算单元应该允许,注册更改通知的回调。当单元值,从之前的稳定状态到一个新的稳定状态时,调用一个单元格的回调。
2. 开始你的表演
/// `InputCellID` is a unique identifier for an input cell. #[derive(Clone, Copy, Debug, PartialEq)] pub struct InputCellID(); /// `ComputeCellID` is a unique identifier for a compute cell. /// Values of type `InputCellID` and `ComputeCellID` should not be mutually assignable, /// demonstrated by the following tests: /// /// ```compile_fail /// let mut r = react::Reactor::new(); /// let input: react::ComputeCellID = r.create_input(111); /// ``` /// /// ```compile_fail /// let mut r = react::Reactor::new(); /// let input = r.create_input(111); /// let compute: react::InputCellID = r.create_compute(&[react::CellID::Input(input)], |_| 222).unwrap(); /// ``` #[derive(Clone, Copy, Debug, PartialEq)] pub struct ComputeCellID(); #[derive(Clone, Copy, Debug, PartialEq)] pub struct CallbackID(); #[derive(Clone, Copy, Debug, PartialEq)] pub enum CellID { Input(InputCellID), Compute(ComputeCellID), } #[derive(Debug, PartialEq)] pub enum RemoveCallbackError { NonexistentCell, NonexistentCallback, } pub struct Reactor<T> { // Just so that the compiler doesn't complain about an unused type parameter. // You probably want to delete this field. dummy: ::std::marker::PhantomData<T>, } // You are guaranteed that Reactor will only be tested against types that are Copy + PartialEq. impl<T: Copy + PartialEq> Reactor<T> { pub fn new() -> Self { unimplemented!() } // Creates an input cell with the specified initial value, returning its ID. pub fn create_input(&mut self, _initial: T) -> InputCellID { unimplemented!() } // Creates a compute cell with the specified dependencies and compute function. // The compute function is expected to take in its arguments in the same order as specified in // `dependencies`. // You do not need to reject compute functions that expect more arguments than there are // dependencies (how would you check for this, anyway?). // // If any dependency doesn't exist, returns an Err with that nonexistent dependency. // (If multiple dependencies do not exist, exactly which one is returned is not defined and // will not be tested) // // Notice that there is no way to *remove* a cell. // This means that you may assume, without checking, that if the dependencies exist at creation // time they will continue to exist as long as the Reactor exists. pub fn create_compute<F: Fn(&[T]) -> T>( &mut self, _dependencies: &[CellID], _compute_func: F, ) -> Result<ComputeCellID, CellID> { unimplemented!() } // Retrieves the current value of the cell, or None if the cell does not exist. // // You may wonder whether it is possible to implement `get(&self, id: CellID) -> Option<&Cell>` // and have a `value(&self)` method on `Cell`. // // It turns out this introduces a significant amount of extra complexity to this exercise. // We chose not to cover this here, since this exercise is probably enough work as-is. pub fn value(&self, id: CellID) -> Option<T> { unimplemented!("Get the value of the cell whose id is {:?}", id) } // Sets the value of the specified input cell. // // Returns false if the cell does not exist. // // Similarly, you may wonder about `get_mut(&mut self, id: CellID) -> Option<&mut Cell>`, with // a `set_value(&mut self, new_value: T)` method on `Cell`. // // As before, that turned out to add too much extra complexity. pub fn set_value(&mut self, _id: InputCellID, _new_value: T) -> bool { unimplemented!() } // Adds a callback to the specified compute cell. // // Returns the ID of the just-added callback, or None if the cell doesn't exist. // // Callbacks on input cells will not be tested. // // The semantics of callbacks (as will be tested): // For a single set_value call, each compute cell's callbacks should each be called: // * Zero times if the compute cell's value did not change as a result of the set_value call. // * Exactly once if the compute cell's value changed as a result of the set_value call. // The value passed to the callback should be the final value of the compute cell after the // set_value call. pub fn add_callback<F: FnMut(T) -> ()>( &mut self, _id: ComputeCellID, _callback: F, ) -> Option<CallbackID> { unimplemented!() } // Removes the specified callback, using an ID returned from add_callback. // // Returns an Err if either the cell or callback does not exist. // // A removed callback should no longer be called. pub fn remove_callback( &mut self, cell: ComputeCellID, callback: CallbackID, ) -> Result<(), RemoveCallbackError> { unimplemented!( "Remove the callback identified by the CallbackID {:?} from the cell {:?}", callback, cell, ) } }
3. 测试代码查看
# #![allow(unused_variables)] #fn main() { #[test] fn input_cells_have_a_value() { let mut reactor = Reactor::new(); let input = reactor.create_input(10); assert_eq!(reactor.value(CellID::Input(input)), Some(10)); } #[test] //#[ignore] fn an_input_cells_value_can_be_set() { let mut reactor = Reactor::new(); let input = reactor.create_input(4); assert!(reactor.set_value(input, 20)); assert_eq!(reactor.value(CellID::Input(input)), Some(20)); } #[test] //#[ignore] fn error_setting_a_nonexistent_input_cell() { let mut dummy_reactor = Reactor::new(); let input = dummy_reactor.create_input(1); assert!(!Reactor::new().set_value(input, 0)); } #[test] //#[ignore] fn compute_cells_calculate_initial_value() { let mut reactor = Reactor::new(); let input = reactor.create_input(1); let output = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); assert_eq!(reactor.value(CellID::Compute(output)), Some(2)); } #[test] //#[ignore] fn compute_cells_take_inputs_in_the_right_order() { let mut reactor = Reactor::new(); let one = reactor.create_input(1); let two = reactor.create_input(2); let output = reactor .create_compute(&[CellID::Input(one), CellID::Input(two)], |v| { v[0] + v[1] * 10 }) .unwrap(); assert_eq!(reactor.value(CellID::Compute(output)), Some(21)); } #[test] //#[ignore] fn error_creating_compute_cell_if_input_doesnt_exist() { let mut dummy_reactor = Reactor::new(); let input = dummy_reactor.create_input(1); assert_eq!( Reactor::new().create_compute(&[CellID::Input(input)], |_| 0), Err(CellID::Input(input)) ); } #[test] //#[ignore] fn do_not_break_cell_if_creating_compute_cell_with_valid_and_invalid_input() { let mut dummy_reactor = Reactor::new(); let _ = dummy_reactor.create_input(1); let dummy_cell = dummy_reactor.create_input(2); let mut reactor = Reactor::new(); let input = reactor.create_input(1); assert_eq!( reactor.create_compute(&[CellID::Input(input), CellID::Input(dummy_cell)], |_| 0), Err(CellID::Input(dummy_cell)) ); assert!(reactor.set_value(input, 5)); assert_eq!(reactor.value(CellID::Input(input)), Some(5)); } #[test] //#[ignore] fn compute_cells_update_value_when_dependencies_are_changed() { let mut reactor = Reactor::new(); let input = reactor.create_input(1); let output = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); assert_eq!(reactor.value(CellID::Compute(output)), Some(2)); assert!(reactor.set_value(input, 3)); assert_eq!(reactor.value(CellID::Compute(output)), Some(4)); } #[test] //#[ignore] fn compute_cells_can_depend_on_other_compute_cells() { let mut reactor = Reactor::new(); let input = reactor.create_input(1); let times_two = reactor .create_compute(&[CellID::Input(input)], |v| v[0] * 2) .unwrap(); let times_thirty = reactor .create_compute(&[CellID::Input(input)], |v| v[0] * 30) .unwrap(); let output = reactor .create_compute( &[CellID::Compute(times_two), CellID::Compute(times_thirty)], |v| v[0] + v[1], ) .unwrap(); assert_eq!(reactor.value(CellID::Compute(output)), Some(32)); assert!(reactor.set_value(input, 3)); assert_eq!(reactor.value(CellID::Compute(output)), Some(96)); } /// A CallbackRecorder helps tests whether callbacks get called correctly. /// You'll see it used in tests that deal with callbacks. /// The names should be descriptive enough so that the tests make sense, /// so it's not necessary to fully understand the implementation, /// though you are welcome to. struct CallbackRecorder { // Note that this `Cell` is https://doc.rust-lang.org/std/cell/ // a mechanism to allow internal mutability, // distinct from the cells (input cells, compute cells) in the reactor value: std::cell::Cell<Option<i32>>, } impl CallbackRecorder { fn new() -> Self { CallbackRecorder { value: std::cell::Cell::new(None), } } fn expect_to_have_been_called_with(&self, v: i32) { assert_ne!( self.value.get(), None, "Callback was not called, but should have been" ); assert_eq!( self.value.replace(None), Some(v), "Callback was called with incorrect value" ); } fn expect_not_to_have_been_called(&self) { assert_eq!( self.value.get(), None, "Callback was called, but should not have been" ); } fn callback_called(&self, v: i32) { assert_eq!( self.value.replace(Some(v)), None, "Callback was called too many times; can't be called with {}", v ); } } #[test] //#[ignore] fn compute_cells_fire_callbacks() { let cb = CallbackRecorder::new(); let mut reactor = Reactor::new(); let input = reactor.create_input(1); let output = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); assert!(reactor .add_callback(output, |v| cb.callback_called(v)) .is_some()); assert!(reactor.set_value(input, 3)); cb.expect_to_have_been_called_with(4); } #[test] //#[ignore] fn error_adding_callback_to_nonexistent_cell() { let mut dummy_reactor = Reactor::new(); let input = dummy_reactor.create_input(1); let output = dummy_reactor .create_compute(&[CellID::Input(input)], |_| 0) .unwrap(); assert_eq!( Reactor::new().add_callback(output, |_: u32| println!("hi")), None ); } #[test] //#[ignore] fn callbacks_only_fire_on_change() { let cb = CallbackRecorder::new(); let mut reactor = Reactor::new(); let input = reactor.create_input(1); let output = reactor .create_compute( &[CellID::Input(input)], |v| if v[0] < 3 { 111 } else { 222 }, ) .unwrap(); assert!(reactor .add_callback(output, |v| cb.callback_called(v)) .is_some()); assert!(reactor.set_value(input, 2)); cb.expect_not_to_have_been_called(); assert!(reactor.set_value(input, 4)); cb.expect_to_have_been_called_with(222); } #[test] //#[ignore] fn callbacks_can_be_added_and_removed() { let cb1 = CallbackRecorder::new(); let cb2 = CallbackRecorder::new(); let cb3 = CallbackRecorder::new(); let mut reactor = Reactor::new(); let input = reactor.create_input(11); let output = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); let callback = reactor .add_callback(output, |v| cb1.callback_called(v)) .unwrap(); assert!(reactor .add_callback(output, |v| cb2.callback_called(v)) .is_some()); assert!(reactor.set_value(input, 31)); cb1.expect_to_have_been_called_with(32); cb2.expect_to_have_been_called_with(32); assert!(reactor.remove_callback(output, callback).is_ok()); assert!(reactor .add_callback(output, |v| cb3.callback_called(v)) .is_some()); assert!(reactor.set_value(input, 41)); cb1.expect_not_to_have_been_called(); cb2.expect_to_have_been_called_with(42); cb3.expect_to_have_been_called_with(42); } #[test] //#[ignore] fn removing_a_callback_multiple_times_doesnt_interfere_with_other_callbacks() { let cb1 = CallbackRecorder::new(); let cb2 = CallbackRecorder::new(); let mut reactor = Reactor::new(); let input = reactor.create_input(1); let output = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); let callback = reactor .add_callback(output, |v| cb1.callback_called(v)) .unwrap(); assert!(reactor .add_callback(output, |v| cb2.callback_called(v)) .is_some()); // We want the first remove to be Ok, but the others should be errors. assert!(reactor.remove_callback(output, callback).is_ok()); for _ in 1..5 { assert_eq!( reactor.remove_callback(output, callback), Err(RemoveCallbackError::NonexistentCallback) ); } assert!(reactor.set_value(input, 2)); cb1.expect_not_to_have_been_called(); cb2.expect_to_have_been_called_with(3); } #[test] //#[ignore] fn callbacks_should_only_be_called_once_even_if_multiple_dependencies_change() { let cb = CallbackRecorder::new(); let mut reactor = Reactor::new(); let input = reactor.create_input(1); let plus_one = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); let minus_one1 = reactor .create_compute(&[CellID::Input(input)], |v| v[0] - 1) .unwrap(); let minus_one2 = reactor .create_compute(&[CellID::Compute(minus_one1)], |v| v[0] - 1) .unwrap(); let output = reactor .create_compute( &[CellID::Compute(plus_one), CellID::Compute(minus_one2)], |v| v[0] * v[1], ) .unwrap(); assert!(reactor .add_callback(output, |v| cb.callback_called(v)) .is_some()); assert!(reactor.set_value(input, 4)); cb.expect_to_have_been_called_with(10); } #[test] //#[ignore] fn callbacks_should_not_be_called_if_dependencies_change_but_output_value_doesnt_change() { let cb = CallbackRecorder::new(); let mut reactor = Reactor::new(); let input = reactor.create_input(1); let plus_one = reactor .create_compute(&[CellID::Input(input)], |v| v[0] + 1) .unwrap(); let minus_one = reactor .create_compute(&[CellID::Input(input)], |v| v[0] - 1) .unwrap(); let always_two = reactor .create_compute( &[CellID::Compute(plus_one), CellID::Compute(minus_one)], |v| v[0] - v[1], ) .unwrap(); assert!(reactor .add_callback(always_two, |v| cb.callback_called(v)) .is_some()); for i in 2..5 { assert!(reactor.set_value(input, i)); cb.expect_not_to_have_been_called(); } } #[test] //#[ignore] fn test_adder_with_boolean_values() { // This is a digital logic circuit called an adder: // https://en.wikipedia.org/wiki/Adder_(electronics) let mut reactor = Reactor::new(); let a = reactor.create_input(false); let b = reactor.create_input(false); let carry_in = reactor.create_input(false); let a_xor_b = reactor .create_compute(&[CellID::Input(a), CellID::Input(b)], |v| v[0] ^ v[1]) .unwrap(); let sum = reactor .create_compute(&[CellID::Compute(a_xor_b), CellID::Input(carry_in)], |v| { v[0] ^ v[1] }) .unwrap(); let a_xor_b_and_cin = reactor .create_compute(&[CellID::Compute(a_xor_b), CellID::Input(carry_in)], |v| { v[0] && v[1] }) .unwrap(); let a_and_b = reactor .create_compute(&[CellID::Input(a), CellID::Input(b)], |v| v[0] && v[1]) .unwrap(); let carry_out = reactor .create_compute( &[CellID::Compute(a_xor_b_and_cin), CellID::Compute(a_and_b)], |v| v[0] || v[1], ) .unwrap(); let tests = &[ (false, false, false, false, false), (false, false, true, false, true), (false, true, false, false, true), (false, true, true, true, false), (true, false, false, false, true), (true, false, true, true, false), (true, true, false, true, false), (true, true, true, true, true), ]; for &(aval, bval, cinval, expected_cout, expected_sum) in tests { assert!(reactor.set_value(a, aval)); assert!(reactor.set_value(b, bval)); assert!(reactor.set_value(carry_in, cinval)); assert_eq!(reactor.value(CellID::Compute(sum)), Some(expected_sum)); assert_eq!( reactor.value(CellID::Compute(carry_out)), Some(expected_cout) ); } } #}
4. 答案
# #![allow(unused_variables)] #fn main() { use std::collections::HashMap; /// `InputCellID` is a unique identifier for an input cell. #[derive(Clone, Copy, Debug, PartialEq)] pub struct InputCellID(usize); /// `ComputeCellID` is a unique identifier for a compute cell. /// Values of type `InputCellID` and `ComputeCellID` should not be mutually assignable, /// demonstrated by the following tests: /// /// ```compile_fail /// let mut r = react::Reactor::new(); /// let input: react::ComputeCellID = r.create_input(111); /// ``` /// /// ```compile_fail /// let mut r = react::Reactor::new(); /// let input = r.create_input(111); /// let compute: react::InputCellID = r.create_compute(&[react::CellID::Input(input)], |_| 222).unwrap(); /// ``` #[derive(Clone, Copy, Debug, PartialEq)] pub struct ComputeCellID(usize); #[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)] pub struct CallbackID(usize); #[derive(Clone, Copy, Debug, PartialEq)] pub enum CellID { Input(InputCellID), Compute(ComputeCellID), } #[derive(Debug, PartialEq)] pub enum RemoveCallbackError { NonexistentCell, NonexistentCallback, } struct Cell<T: Copy> { value: T, last_value: T, dependents: Vec<ComputeCellID>, } struct ComputeCell<'a, T: Copy> { cell: Cell<T>, dependencies: Vec<CellID>, f: Box<Fn(&[T]) -> T + 'a>, callbacks_issued: usize, callbacks: HashMap<CallbackID, Box<FnMut(T) -> () + 'a>>, } impl<T: Copy> Cell<T> { fn new(initial: T) -> Self { Cell { value: initial, last_value: initial, dependents: Vec::new(), } } } impl<'a, T: Copy> ComputeCell<'a, T> { fn new<F: Fn(&[T]) -> T + 'a>(initial: T, dependencies: Vec<CellID>, f: F) -> Self { ComputeCell { cell: Cell::new(initial), dependencies, f: Box::new(f), callbacks_issued: 0, callbacks: HashMap::new(), } } } pub struct Reactor<'a, T: Copy> { inputs: Vec<Cell<T>>, computes: Vec<ComputeCell<'a, T>>, } impl<'a, T: Copy + PartialEq> Reactor<'a, T> { pub fn new() -> Self { Reactor { inputs: Vec::new(), computes: Vec::new(), } } pub fn create_input(&mut self, initial: T) -> InputCellID { self.inputs.push(Cell::new(initial)); InputCellID(self.inputs.len() - 1) } pub fn create_compute<F: Fn(&[T]) -> T + 'a>( &mut self, dependencies: &[CellID], compute_func: F, ) -> Result<ComputeCellID, CellID> { // Check all dependencies' validity before modifying any of them, // so that we don't perform an incorrect partial write. for &dep in dependencies { match dep { CellID::Input(InputCellID(id)) => if id >= self.inputs.len() { return Err(dep); }, CellID::Compute(ComputeCellID(id)) => if id >= self.computes.len() { return Err(dep); }, } } let new_id = ComputeCellID(self.computes.len()); for &dep in dependencies { match dep { CellID::Input(InputCellID(id)) => self.inputs[id].dependents.push(new_id), CellID::Compute(ComputeCellID(id)) => { self.computes[id].cell.dependents.push(new_id) } } } let inputs: Vec<_> = dependencies .iter() .map(|&id| self.value(id).unwrap()) .collect(); let initial = compute_func(&inputs); self.computes.push(ComputeCell::new( initial, dependencies.to_vec(), compute_func, )); Ok(new_id) } pub fn value(&self, id: CellID) -> Option<T> { match id { CellID::Input(InputCellID(id)) => self.inputs.get(id).map(|c| c.value), CellID::Compute(ComputeCellID(id)) => self.computes.get(id).map(|c| c.cell.value), } } pub fn set_value(&mut self, id: InputCellID, new_value: T) -> bool { let InputCellID(id) = id; self.inputs .get_mut(id) .map(|c| { c.value = new_value; c.dependents.clone() }) .map(|deps| { for &d in deps.iter() { self.update_dependent(d); } // We can only fire callbacks after all dependents have updated. // So we can't combine this for loop with the one above! for d in deps { self.fire_callbacks(d); } }) .is_some() } pub fn add_callback<F: FnMut(T) -> () + 'a>( &mut self, id: ComputeCellID, callback: F, ) -> Option<CallbackID> { let ComputeCellID(id) = id; self.computes.get_mut(id).map(|c| { c.callbacks_issued += 1; let cbid = CallbackID(c.callbacks_issued); c.callbacks.insert(cbid, Box::new(callback)); cbid }) } pub fn remove_callback( &mut self, cell: ComputeCellID, callback: CallbackID, ) -> Result<(), RemoveCallbackError> { let ComputeCellID(cell) = cell; match self.computes.get_mut(cell) { Some(c) => match c.callbacks.remove(&callback) { Some(_) => Ok(()), None => Err(RemoveCallbackError::NonexistentCallback), }, None => Err(RemoveCallbackError::NonexistentCell), } } fn update_dependent(&mut self, id: ComputeCellID) { let ComputeCellID(id) = id; let (new_value, dependents) = { // This block limits the scope of the self.cells borrow. // This is necessary because we borrow it mutably below. let (dependencies, f, dependents) = match self.computes.get(id) { Some(c) => (&c.dependencies, &c.f, c.cell.dependents.clone()), None => panic!("Cell to update disappeared while querying"), }; let inputs: Vec<_> = dependencies .iter() .map(|&id| self.value(id).unwrap()) .collect(); (f(&inputs), dependents) }; match self.computes.get_mut(id) { Some(c) => { if c.cell.value == new_value { // No change here, we don't need to update our dependents. // (It wouldn't hurt to, but it would be unnecessary work) return; } c.cell.value = new_value; } None => panic!("Cell to update disappeared while updating"), } for d in dependents { self.update_dependent(d); } } fn fire_callbacks(&mut self, id: ComputeCellID) { let ComputeCellID(id) = id; let dependents = match self.computes.get_mut(id) { Some(c) => { if c.cell.value == c.cell.last_value { // Value hasn't changed since last callback fire. // We thus shouldn't fire the callbacks. return; } for cb in c.callbacks.values_mut() { cb(c.cell.value); } c.cell.last_value = c.cell.value; c.cell.dependents.clone() } None => panic!("Callback cell disappeared"), }; for d in dependents { self.fire_callbacks(d); } } } #}