Splay tree invariants are critical to uphold

The implementation of the splay tree checks invariants about the tree in each function call and reverts if these invariants are not upheld. If the splay tree were to reach an invalid state, this would effectively freeze an order book. It is therefore crucial that any changes made to the splay tree be done with caution.

For these reasons it is crucial for the splay tree module to have adequate, varied unit tests. However, nearly all of the unit tests work on a tree with the following keys: 0, 1, 2, 3, 4, and 5. The tests check the state of the tree after or during a simple sequence of insertions and removals. We recommend that the unit tests validate the state of larger, more complex trees resulting from many insertions, removals, and splays.

Furthermore, based on the logic in the book module (especially book::can_bid_be_matched and book::can_ask_be_matched), it is important that iterating over a tree is ordered by key. We therefore recommend that iteration is checked more thoroughly. The iterator should be able to traverse a valid tree in order of increasing or decreasing key. The following is an example of a function that tests that the splay_tree module is able to properly traverse a tree:

public fun test_verify_iteration<V: store + drop>(tree: &SplayTree<V>) {
    let iter = init_iterator(false);
    let prev_key = 0;
    while (has_next(&iter)) {
        let (cur_key, _) = next(tree, &mut iter);
        assert!(prev_key <= cur_key, ENO_MESSAGE);
        prev_key = cur_key;
    };

    let rev_iter = init_iterator(true);
    let prev_key = 0xffffffffffffffff; // u64 max
    while (has_next(&rev_iter)) {
        let (cur_key, _) = next(tree, &mut rev_iter);
        assert!(prev_key >= cur_key, ENO_MESSAGE);
        prev_key = cur_key;
    };
}

This function was able to capture a bug in splay_tree::prev_node_idx that caused the iterator to not work in reverse. This bug is discussed in Section 3.1, and the current unit tests were able to pass even with this bug present.