Testing Cursors
是时候找出我在上一节中犯了多少令人尴尬的错误了！
哦，天哪，我们的 API 既不像标准版，也不像旧版。好吧，那我打算从这两个地方拼凑一些东西吧。是的，让我们 "借用 " 标准版中的这些测试：
#![allow(unused)] fn main() { #[test] fn test_cursor_move_peek() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 1)); assert_eq!(cursor.peek_next(), Some(&mut 2)); assert_eq!(cursor.peek_prev(), None); assert_eq!(cursor.index(), Some(0)); cursor.move_prev(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); assert_eq!(cursor.peek_prev(), Some(&mut 6)); assert_eq!(cursor.index(), None); cursor.move_next(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 2)); assert_eq!(cursor.peek_next(), Some(&mut 3)); assert_eq!(cursor.peek_prev(), Some(&mut 1)); assert_eq!(cursor.index(), Some(1)); let mut cursor = m.cursor_mut(); cursor.move_prev(); assert_eq!(cursor.current(), Some(&mut 6)); assert_eq!(cursor.peek_next(), None); assert_eq!(cursor.peek_prev(), Some(&mut 5)); assert_eq!(cursor.index(), Some(5)); cursor.move_next(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); assert_eq!(cursor.peek_prev(), Some(&mut 6)); assert_eq!(cursor.index(), None); cursor.move_prev(); cursor.move_prev(); assert_eq!(cursor.current(), Some(&mut 5)); assert_eq!(cursor.peek_next(), Some(&mut 6)); assert_eq!(cursor.peek_prev(), Some(&mut 4)); assert_eq!(cursor.index(), Some(4)); } #[test] fn test_cursor_mut_insert() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.splice_before(Some(7).into_iter().collect()); cursor.splice_after(Some(8).into_iter().collect()); // check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); cursor.splice_before(Some(9).into_iter().collect()); cursor.splice_after(Some(10).into_iter().collect()); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]); /* remove_current not impl'd let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); assert_eq!(cursor.remove_current(), None); cursor.move_next(); cursor.move_next(); assert_eq!(cursor.remove_current(), Some(7)); cursor.move_prev(); cursor.move_prev(); cursor.move_prev(); assert_eq!(cursor.remove_current(), Some(9)); cursor.move_next(); assert_eq!(cursor.remove_current(), Some(10)); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]); */ let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 8, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); let mut p: LinkedList<u32> = LinkedList::new(); p.extend([100, 101, 102, 103]); let mut q: LinkedList<u32> = LinkedList::new(); q.extend([200, 201, 202, 203]); cursor.splice_after(p); cursor.splice_before(q); check_links(&m); assert_eq!( m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6] ); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); let tmp = cursor.split_before(); assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]); m = tmp; let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); let tmp = cursor.split_after(); assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]); } fn check_links<T>(_list: &LinkedList<T>) { // would be good to do this! } }
见证奇迹的时候！
cargo test
Compiling linked-list v0.0.3
Finished test [unoptimized + debuginfo] target(s) in 1.03s
Running unittests src\lib.rs
running 14 tests
test test::test_basic_front ... ok
test test::test_basic ... ok
test test::test_debug ... ok
test test::test_iterator_mut_double_end ... ok
test test::test_ord ... ok
test test::test_cursor_move_peek ... FAILED
test test::test_cursor_mut_insert ... FAILED
test test::test_iterator ... ok
test test::test_mut_iter ... ok
test test::test_eq ... ok
test test::test_rev_iter ... ok
test test::test_iterator_double_end ... ok
test test::test_hashmap ... ok
test test::test_ord_nan ... ok
failures:
---- test::test_cursor_move_peek stdout ----
thread 'test::test_cursor_move_peek' panicked at 'assertion failed: `(left == right)`
left: `None`,
right: `Some(1)`', src\lib.rs:1079:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- test::test_cursor_mut_insert stdout ----
thread 'test::test_cursor_mut_insert' panicked at 'assertion failed: `(left == right)`
left: `[200, 201, 202, 203, 10, 100, 101, 102, 103, 7, 1, 8, 2, 3, 4, 5, 6, 9]`,
right: `[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]`', src\lib.rs:1153:9
failures:
test::test_cursor_move_peek
test::test_cursor_mut_insert
test result: FAILED. 12 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
我得承认，我在这里有些自负，希望自己能成功。这就是我们写测试的原因（但也许我只是在移植测试时做得不好？）
第一次失败是什么？
#![allow(unused)] fn main() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 1)); assert_eq!(cursor.peek_next(), Some(&mut 2)); assert_eq!(cursor.peek_prev(), None); assert_eq!(cursor.index(), Some(0)); cursor.move_prev(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); // DIES HERE }
#![allow(unused)] fn main() { pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).back) .map(|node| &mut (*node.as_ptr()).elem) } } }
就是这错了。如果 self.cur 是 None, 我们不应该就这样放弃，我们还需要检查 self.list.front，因为我们在幽灵节点上！因此，我们只需在链中添加一个 or_else：
#![allow(unused)] fn main() { pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).back) .or_else(|| self.list.front) .map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).front) .or_else(|| self.list.back) .map(|node| &mut (*node.as_ptr()).elem) } } }
这样就修复好了吗？
---- test::test_cursor_move_peek stdout ----
thread 'test::test_cursor_move_peek' panicked at 'assertion failed: `(left == right)`
left: `Some(6)`,
right: `None`', src\lib.rs:1078:9
又错了。好吧，显然这比我想象的要难得多。盲目地把这些情况串联起来简直是一场灾难，让我们对幽灵节点与非幽灵节点的情况做不同的判断吧：
#![allow(unused)] fn main() { pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { let next = if let Some(cur) = self.cur { // Normal case, try to follow the cur node's back pointer (*cur.as_ptr()).back } else { // Ghost case, try to use the list's front pointer self.list.front }; // Yield the element if the next node exists next.map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { let prev = if let Some(cur) = self.cur { // Normal case, try to follow the cur node's front pointer (*cur.as_ptr()).front } else { // Ghost case, try to use the list's back pointer self.list.back }; // Yield the element if the prev node exists prev.map(|node| &mut (*node.as_ptr()).elem) } } }
我对这一次充满信心！
#![allow(unused)] fn main() { cargo test Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 0.70s Running unittests src\lib.rs running 14 tests test test::test_basic_front ... ok test test::test_basic ... ok test test::test_cursor_move_peek ... ok test test::test_eq ... ok test test::test_cursor_mut_insert ... ok test test::test_iterator ... ok test test::test_iterator_double_end ... ok test test::test_ord_nan ... ok test test::test_mut_iter ... ok test test::test_hashmap ... ok test test::test_debug ... ok test test::test_ord ... ok test test::test_iterator_mut_double_end ... ok test test::test_rev_iter ... ok test result: ok. 14 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s Doc-tests linked-list running 1 test test src\lib.rs - assert_properties::iter_mut_invariant (line 803) - compile fail ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.12s }
嘿嘿，看看这个......好吧，现在我开始疑神疑鬼了。让我们正确填写 check_links，并在 miri 下进行测试：
#![allow(unused)] fn main() { fn check_links<T: Eq + std::fmt::Debug>(list: &LinkedList<T>) { let from_front: Vec<_> = list.iter().collect(); let from_back: Vec<_> = list.iter().rev().collect(); let re_reved: Vec<_> = from_back.into_iter().rev().collect(); assert_eq!(from_front, re_reved); } }
$env:MIRIFLAGS="-Zmiri-tag-raw-pointers"
cargo miri test
Compiling linked-list v0.0.3
Finished test [unoptimized + debuginfo] target(s) in 0.25s
Running unittests src\lib.rs
running 14 tests
test test::test_basic ... ok
test test::test_basic_front ... ok
test test::test_cursor_move_peek ... ok
test test::test_cursor_mut_insert ... ok
test test::test_debug ... ok
test test::test_eq ... ok
test test::test_hashmap ... ok
test test::test_iterator ... ok
test test::test_iterator_double_end ... ok
test test::test_iterator_mut_double_end ... ok
test test::test_mut_iter ... ok
test test::test_ord ... ok
test test::test_ord_nan ... ok
test test::test_rev_iter ... ok
test result: ok. 14 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Doc-tests linked-list
running 1 test
test src\lib.rs - assert_properties::iter_mut_invariant (line 803) - compile fail ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.10s
完成。
我们成功了 我们做出了一个具有生产质量的 LinkedList，其功能与 std 中的 LinkedList 基本相同。我们是否在这里或那里缺少了一些小的便利方法？当然有。我会把它们添加到最终发布的版本中吗？也许会！
但是，我已经非常累了。
所以。我们赢了
等等 我们正在生产质量。好吧，最后一个步骤： clippy。
cargo clippy
cargo clippy
Checking linked-list v0.0.3 (C:\Users\ninte\dev\contain\linked-list)
warning: redundant pattern matching, consider using `is_some()`
--> src\lib.rs:189:19
|
189 | while let Some(_) = self.pop_front() { }
| ----------^^^^^^^------------------- help: try this: `while self.pop_front().is_some()`
|
= note: `#[warn(clippy::redundant_pattern_matching)]` on by default
= note: this will change drop order of the result, as well as all temporaries
= note: add `#[allow(clippy::redundant_pattern_matching)]` if this is important
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_pattern_matching
warning: method `into_iter` can be confused for the standard trait method `std::iter::IntoIterator::into_iter`
--> src\lib.rs:210:5
|
210 | / pub fn into_iter(self) -> IntoIter<T> {
211 | | IntoIter {
212 | | list: self
213 | | }
214 | | }
| |_____^
|
= note: `#[warn(clippy::should_implement_trait)]` on by default
= help: consider implementing the trait `std::iter::IntoIterator` or choosing a less ambiguous method name
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#should_implement_trait
warning: redundant pattern matching, consider using `is_some()`
--> src\lib.rs:228:19
|
228 | while let Some(_) = self.pop_front() { }
| ----------^^^^^^^------------------- help: try this: `while self.pop_front().is_some()`
|
= note: this will change drop order of the result, as well as all temporaries
= note: add `#[allow(clippy::redundant_pattern_matching)]` if this is important
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_pattern_matching
warning: re-implementing `PartialEq::ne` is unnecessary
--> src\lib.rs:275:5
|
275 | / fn ne(&self, other: &Self) -> bool {
276 | | self.len() != other.len() || self.iter().ne(other)
277 | | }
| |_____^
|
= note: `#[warn(clippy::partialeq_ne_impl)]` on by default
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#partialeq_ne_impl
warning: `linked-list` (lib) generated 4 warnings
Finished dev [unoptimized + debuginfo] target(s) in 0.29s
好的 clippy, 按照你的要求修改。
再来一次：
cargo clippy
Finished dev [unoptimized + debuginfo] target(s) in 0.00s
太棒了，称为生产品质的最后一件事: fmt.
cargo fmt
我们现在终于真正的完成啦!!!!!!!!!!!!!!!!!!!!!