#![cfg(target_os = "linux")]
extern crate deterministic;
extern crate quickcheck;
extern crate sled;
extern crate tests;

use std::{
    collections::BTreeMap,
    sync::{Arc, RwLock},
};

use deterministic::{set_seed, spawn::spawn_with_random_prio};
use quickcheck::{QuickCheck, StdGen};
use sled::*;
use tests::tree::{
    Key,
    Op::{self, *},
};

fn bytes_to_u16(v: &[u8]) -> u16 {
    assert_eq!(v.len(), 2);
    ((v[0] as u16) << 8) + v[1] as u16
}

fn u16_to_bytes(u: u16) -> Vec<u8> {
    let ret = vec![(u >> 8) as u8, u as u8];
    ret
}

// just adds up values as if they were u16's
fn test_merge_operator(
    _k: &[u8],
    old: Option<&[u8]>,
    to_merge: &[u8],
) -> Option<Vec<u8>> {
    let base = old.unwrap_or(&[0, 0]);
    let base_n = bytes_to_u16(base);
    let new_n = base_n + to_merge[0] as u16;
    let ret = u16_to_bytes(new_n);
    Some(ret)
}

fn run_ops(
    ops: Vec<Op>,
    tree: Arc<Tree>,
    reference: Arc<RwLock<BTreeMap<Key, u16>>>,
) {
    for op in ops.into_iter() {
        match op {
            Set(k, v) => {
                let mut r = reference.write().unwrap();
                tree.set(k.0.clone(), vec![0, v]).unwrap();
                r.insert(k.clone(), v as u16);
            }
            Merge(k, v) => {
                let mut r = reference.write().unwrap();
                tree.merge(k.0.clone(), vec![v]).unwrap();
                let entry = r.entry(k).or_insert(0u16);
                *entry += v as u16;
            }
            Get(k) => {
                let r = reference.read().unwrap();
                let res1 = tree
                    .get(&*k.0)
                    .unwrap()
                    .map(|v| bytes_to_u16(&v));
                let res2 = r.get(&k).cloned();
                assert_eq!(res1, res2);
            }
            GetLt(k) => {
                let r = reference.read().unwrap();
                let res1 = tree
                    .get_lt(&*k.0)
                    .unwrap()
                    .map(|v| bytes_to_u16(&*v.1));
                let res2 = r
                    .iter()
                    .rev()
                    .filter(|(key, _)| *key < &k)
                    .nth(0)
                    .map(|(_, v)| *v);
                assert_eq!(res1, res2);
            }
            GetGt(k) => {
                let r = reference.read().unwrap();
                let res1 = tree
                    .get_gt(&*k.0)
                    .unwrap()
                    .map(|v| bytes_to_u16(&*v.1));
                let res2 = r
                    .iter()
                    .filter(|(key, _)| *key > &k)
                    .nth(0)
                    .map(|(_, v)| *v);
                assert_eq!(res1, res2);
            }
            Del(k) => {
                let mut r = reference.write().unwrap();
                tree.del(&*k.0).unwrap();
                r.remove(&k);
            }
            Cas(k, old, new) => {
                let mut r = reference.write().unwrap();
                let tree_old = tree.get(&*k.0).unwrap();
                if let Some(old_tree) = tree_old {
                    if old_tree == &*vec![0, old] {
                        tree.set(k.0.clone(), vec![0, new]).unwrap();
                    }
                }

                let ref_old = r.get(&k).cloned();
                if ref_old == Some(old as u16) {
                    r.insert(k, new as u16);
                }
            }
            Scan(k, len) => {
                let r = reference.read().unwrap();
                let mut tree_iter = tree
                    .scan(&*k.0)
                    .take(len)
                    .map(|res| res.unwrap());
                let ref_iter = r
                    .iter()
                    .filter(|&(ref rk, _rv)| **rk >= k)
                    .take(len)
                    .map(|(ref rk, ref rv)| (rk.0.clone(), **rv));

                for r in ref_iter {
                    let tree_next = tree_iter.next().unwrap();
                    let lhs = (tree_next.0, &*tree_next.1);
                    let rhs = (r.0.clone(), &*u16_to_bytes(r.1));
                    assert_eq!(
                        lhs, rhs,
                        "expected iteration over the Tree \
                         to match our BTreeMap model"
                    );
                }
            }
            Restart => {
                panic!("hit restart from within thread!");
            }
        }
    }
}

fn prop_concurrent_tree_matches_btreemap(
    ops: Vec<Op>,
    deterministic_seed: usize,
    threads_gen: u8,
) -> bool {
    let threads = std::cmp::max(threads_gen, 8) as usize;

    set_seed(deterministic_seed);

    let config = ConfigBuilder::new()
        .temporary(true)
        .snapshot_after_ops(100_000)
        .flush_every_ms(None)
        .io_buf_size(10_000)
        .blink_node_split_size(0)
        .cache_capacity(40)
        .cache_bits(0)
        .merge_operator(test_merge_operator)
        .build();

    let mut tree =
        Arc::new(sled::Tree::start(config.clone()).unwrap());
    let reference: Arc<RwLock<BTreeMap<Key, u16>>> =
        Arc::new(RwLock::new(BTreeMap::new()));

    println!("ops: {:?}", ops);
    let epochs = ops.split(|o| o.is_restart());

    // perform a restart after each sequence of epochs
    for epoch in epochs {
        if epoch.is_empty() {
            // restart
            drop(tree);
            tree =
                Arc::new(sled::Tree::start(config.clone()).unwrap());
        }

        let ops_per_thread = epoch.len() / threads;
        let op_chunks =
            epoch.chunks(std::cmp::max(1, ops_per_thread));

        // split ops amongst threads and run them
        let mut threads = vec![];
        for op_chunk in op_chunks {
            let tree = tree.clone();
            let reference = reference.clone();
            let ops = op_chunk.to_vec();
            let t = spawn_with_random_prio(move || {
                run_ops(ops, tree, reference);
            });

            threads.push(t);
        }

        for t in threads.into_iter() {
            t.join().expect("thread should finish without panicking");
        }

        // restart
        drop(tree);
        tree = Arc::new(sled::Tree::start(config.clone()).unwrap());
    }

    true
}

#[test]
#[ignore]
fn quickcheck_concurrent_tree_matches_btreemap() {
    let n_tests = 10;

    QuickCheck::new()
        .gen(StdGen::new(rand::thread_rng(), 1000))
        .tests(n_tests)
        .max_tests(100)
        .quickcheck(
            prop_concurrent_tree_matches_btreemap
                as fn(Vec<Op>, usize, u8) -> bool,
        );
}

#[test]
#[ignore]
fn test_concurrent_tree_01() {
    prop_concurrent_tree_matches_btreemap(
        vec![
            Del(Key(vec![])),
            Merge(Key(vec![1]), 245),
            Merge(Key(vec![17]), 168),
            Scan(Key(vec![]), 0),
            Set(
                Key(vec![
                    41, 198, 174, 28, 114, 38, 234, 52, 167, 17, 246,
                    251, 162, 186, 78, 78, 106, 96, 11, 51, 71, 38,
                    133, 103, 43, 182, 5, 43, 60, 220, 15, 135, 251,
                    103, 222, 235, 52, 237, 206, 8, 252, 68, 95, 157,
                    95, 111, 53, 163, 221, 202, 146, 199, 34, 208,
                    57, 89, 83, 166, 27, 86, 151, 165, 114, 244, 135,
                    95, 80, 191, 251, 4, 147, 242, 23, 157, 17, 92,
                    169, 64, 62, 75, 32, 136, 147, 115, 45, 250, 193,
                    65, 4, 154, 2, 185, 0, 104, 60, 208, 138, 199,
                    231, 73, 20, 162, 185, 158, 39, 193, 184, 105,
                    222, 96, 74, 16, 69, 117, 127, 17, 244, 62, 124,
                    245, 167, 0, 237, 169, 103, 96, 27, 96, 77, 218,
                    96, 51, 68, 242, 92, 51, 47, 21, 51, 238, 254,
                    189, 194, 72, 53, 37, 24, 150, 188, 83, 93, 137,
                    84, 244, 141, 32, 157, 136, 51, 65, 192, 53, 77,
                    181, 39, 124, 84, 98, 21, 104, 52, 50, 26, 242,
                    43, 242, 242, 231, 198, 203, 225, 130, 109, 224,
                    246, 79, 221, 131, 7, 193, 242, 225, 8, 203, 163,
                    106, 133, 48, 9, 86, 29, 6, 169, 76, 174, 106,
                    247, 18, 55, 110, 140, 5, 48, 149, 240, 46, 233,
                    154, 252, 105, 116, 111, 106, 214, 20, 27, 222,
                    11, 26, 54, 185, 161, 103, 187, 132, 4, 254, 4,
                    64, 254, 250, 30, 46, 38, 92, 49, 108, 7, 74,
                    176, 235, 19, 199, 62, 22, 171, 29, 38, 60, 229,
                    206, 126, 74, 145, 222, 184, 28, 181, 67, 7, 42,
                    10, 88, 146, 1, 44, 84, 127, 94, 214, 27, 78,
                    133, 19, 220, 136, 206, 24, 25, 191, 74, 181,
                    189, 100, 237, 68, 200, 74, 140, 24, 13, 181,
                    201, 187, 224, 204, 208, 67, 68, 193, 91, 26, 60,
                    151, 231, 12, 240, 55, 17, 223, 32, 21, 142, 255,
                    128, 229, 243, 212, 211, 230, 69, 208, 62, 3, 27,
                    118, 123, 75, 156, 94, 217, 58, 189, 58, 42, 60,
                    128, 3, 8, 236, 177, 37, 63, 44, 244, 122, 214,
                    81, 74, 201, 220, 27, 214, 78, 92, 217, 50, 104,
                    49, 238, 103, 83, 114,
                ]),
                237,
            ),
            Set(
                Key(vec![
                    116, 117, 195, 212, 173, 149, 187, 3, 168, 208,
                    251, 137, 144, 19, 127, 51, 195, 61, 73, 132,
                    139, 13, 235, 25, 137, 196, 39, 96, 102, 89, 189,
                    19, 205, 4, 110, 76, 143, 181, 37, 174, 231, 233,
                    135, 130, 21, 121, 37, 28, 42, 97, 123, 137, 8,
                    123, 82, 158, 57, 214, 177, 254, 194, 247, 155,
                    196, 177, 124, 206, 183, 34, 54, 119, 101, 174,
                    71, 24, 177, 86, 122, 56, 59, 27, 206, 70, 168,
                    23, 143, 85, 119, 183, 169, 236, 79, 40, 82, 226,
                    75, 220, 35, 229, 47, 97, 232, 206, 125, 113,
                    242, 38, 123, 213, 106, 232, 50, 227, 98, 50, 35,
                    254, 253, 110, 27, 198, 108, 148, 172, 159, 126,
                    79, 61, 121, 106, 15, 94, 188, 247, 144, 211,
                    229, 83, 6, 65, 38, 1, 181, 208, 219, 135, 80,
                    112, 203, 12, 38, 52, 45, 232, 10, 248, 46, 28,
                    112, 136, 247, 115, 191, 57, 39, 135, 239, 114,
                    89, 220, 40, 156, 158, 87, 60, 180, 56, 112, 5,
                    105, 44, 137, 24, 53, 34, 74, 212, 93, 165, 243,
                    47, 25, 12, 190, 78, 89, 206, 90, 82, 111, 116,
                    93, 68, 4, 0, 166, 215, 42, 241, 174, 205, 207,
                    34, 123, 14, 138, 94, 226, 140, 16, 97, 199, 187,
                    70, 172, 106, 131, 166, 7, 52, 14, 36, 208, 140,
                    115, 191, 175, 65, 119, 97, 35, 89, 251, 21, 119,
                    237, 63, 82, 77, 10, 176, 130, 114, 178, 63, 107,
                    72, 28, 89, 30, 28, 53, 2, 106, 220, 8, 81, 120,
                    19, 230, 128, 200, 79, 178, 145, 214, 166, 4,
                    114, 231, 35, 25, 54, 43, 158, 91, 228, 230, 11,
                    216, 157, 30, 17, 243, 168, 230, 125, 211, 89,
                    85, 160, 229, 177, 26, 232, 214, 157, 12, 80,
                    239, 67, 224, 153, 71, 64, 163, 80, 118, 180,
                    105, 211, 202, 188, 202, 197, 249, 254, 165, 90,
                    33, 42, 78, 119, 34, 236, 178, 90, 153, 132, 159,
                    56, 65,
                ]),
                155,
            ),
            Merge(Key(vec![]), 162),
            Set(
                Key(vec![
                    201, 56, 61, 88, 139, 150, 2, 136, 241, 120, 222,
                    9, 12, 154, 72, 238, 191, 111, 220, 77, 99, 254,
                    228, 87, 197, 152, 244, 134, 177, 250, 196, 142,
                    92, 197, 73, 51, 191, 155, 236, 204, 135, 53, 23,
                    171, 50, 63, 133, 83, 164, 20, 51, 77, 16, 135,
                    59, 135, 240, 175, 37, 45, 5, 52, 30, 174, 176,
                    175, 98, 65, 1, 90, 41, 145, 102, 20, 136, 214,
                    123, 56, 106, 218, 109, 79, 1, 186, 158, 140,
                    160, 206, 110, 208, 234, 253, 69, 246, 150, 28,
                    56, 26, 50, 40, 104, 204, 144, 229, 47, 70, 77,
                    34, 141, 78, 171, 166, 117, 127, 212, 198, 168,
                    140, 26, 173, 50, 139, 226, 43, 78, 6, 190, 204,
                    169, 169, 139, 18, 10, 162, 191, 125, 209, 13,
                    29, 105, 252, 4, 215, 48, 207, 191, 8, 92, 221,
                    236, 201, 22, 156, 96, 21, 102, 109, 216, 26,
                    184, 143, 242, 229, 115, 55, 20, 239, 238, 197,
                    136, 201, 158, 206, 1, 83, 227, 253, 202, 203, 5,
                    214, 148, 127, 230, 213, 118, 140, 235, 4, 6,
                    141, 116, 174, 242, 63, 148, 186, 238, 240, 45,
                    86, 231, 68, 158, 114, 39, 56, 61, 78, 96, 57,
                    38, 131, 143, 175, 254, 143, 47, 46, 142, 97,
                    172, 26, 119, 40, 121, 146, 47, 90, 15, 239, 146,
                    147, 24, 6, 32, 153, 85, 78, 38, 182, 170, 56,
                    176, 197, 245, 74, 250, 206, 66, 25, 49, 83, 167,
                    18, 205, 91, 30, 255, 87, 175, 106, 29, 10, 32,
                    112, 220, 21, 151, 155, 244, 129, 151, 170, 139,
                    114, 110, 236, 148, 213, 53, 168, 131, 227, 188,
                    5, 73, 28, 42, 127, 96, 11, 188, 66, 66, 52, 143,
                    28, 122, 148, 28, 66, 119, 191, 124, 88, 72, 44,
                    137, 223, 41, 222, 192, 12, 38, 63, 81, 157, 10,
                    176, 190, 249, 239, 195, 40, 92, 249, 39, 199,
                    59, 92, 141, 149, 136, 186, 170, 10, 70, 255,
                    233, 22, 133, 248, 29, 238, 156, 58, 100, 215,
                    40, 50, 48, 36, 226, 43, 189, 172, 38, 181, 72,
                    76, 160, 240, 29, 227, 146, 0, 115, 52, 5, 247,
                    13, 219, 30, 228, 83, 182, 46, 8, 144, 73, 205,
                    225, 182, 50, 123, 192, 120, 190, 186, 4, 99, 30,
                    19, 220, 44, 98, 200, 237, 238, 21, 98, 112, 234,
                    72, 140, 177, 186, 234, 148, 102, 121, 191, 170,
                    38, 53, 244, 91, 156, 33, 97, 79, 55, 74, 204,
                    205, 233, 54, 73, 137, 241, 167, 190, 161, 187,
                    197, 182, 158, 133, 164, 154, 129, 32, 110, 186,
                    243, 103, 239, 13, 55, 119, 94, 174, 183, 137,
                    23, 200, 222, 23, 162, 196, 121, 224, 82, 120,
                    133, 176, 146, 173, 108, 97, 68, 144, 131, 175,
                    225, 54, 178, 33, 27, 230, 252, 142, 39, 181,
                    200, 77, 9, 3, 20, 164, 168, 209, 217, 118, 221,
                    40, 7, 73, 67, 71, 247, 10, 198, 94, 223, 209,
                    153, 114, 44, 166, 128, 112, 121, 69, 117, 193,
                    62, 232, 245, 14, 14, 195, 17, 170, 218, 33, 26,
                    96, 230, 6, 208, 34, 81, 193, 133, 192, 93, 88,
                    81, 174, 151, 172, 122, 144, 129, 77, 72, 123,
                    193, 108, 170, 240, 86, 205, 67, 96, 109, 170,
                    127, 208, 69, 73, 229, 250, 199, 93, 228, 253,
                    234, 82, 198, 9, 136, 215, 121, 62, 221, 181,
                    137, 76, 252, 123, 10, 17, 181, 102, 108, 25, 12,
                    8, 113, 139, 244, 8, 246, 86, 244, 220, 105, 232,
                    159, 25, 233, 4, 149, 12, 240, 255, 225, 114, 96,
                    74, 223, 125, 4, 88, 108, 143, 17, 94, 152, 21,
                    249, 97, 244, 205, 46, 198, 156, 239, 157, 100,
                    194, 8, 121, 183, 222, 169, 76, 136, 174, 225,
                    12, 90, 245, 47, 69, 100, 31, 27, 46, 96, 201,
                    73, 209, 224, 72, 37, 191, 34, 49, 144, 201, 185,
                    138, 122, 223, 117, 139, 85, 176, 118, 14, 166,
                    84, 32, 102, 177, 77, 76, 33, 15, 6, 88, 7, 173,
                    42, 204, 110, 62, 235, 231, 71, 188, 255, 16,
                    156, 4, 249, 105, 178, 45, 91, 223, 25, 36, 206,
                    84, 146, 57, 8, 50, 122, 161, 114, 232, 127, 164,
                    21, 76, 235, 129, 252, 110, 170, 252, 51, 223,
                    70, 179, 136, 86, 227, 94, 188, 209, 56, 71, 97,
                    193, 225, 11, 172, 13, 56, 118, 183, 28, 156, 11,
                    187, 216, 232, 54, 150, 162, 75, 27, 6, 235, 184,
                    34, 19, 28, 51, 140, 83, 231, 64, 224, 85, 179,
                    85, 168, 128, 239, 245, 86, 206, 54, 79, 50, 244,
                    75, 165, 227, 64, 105, 49, 17, 193, 124, 64, 59,
                    164, 162, 124, 145, 38, 1, 156, 160, 119, 194,
                    67, 237, 92, 225, 130, 55, 36, 49, 145, 117, 95,
                    210, 158, 149, 181, 78, 78, 179, 219, 125, 218,
                    76, 29, 139, 179, 93, 246, 86, 203, 114, 184, 45,
                    178, 76, 43, 120, 181, 250, 242, 41, 29, 105,
                    171, 162, 185, 47, 223, 105, 74, 115, 226, 54,
                    253, 45, 106, 141, 145, 38, 53, 234, 88, 250,
                    193, 227, 87, 146, 41, 178, 160, 1, 172, 65, 222,
                    96, 163, 152, 157, 167, 46, 244, 249, 186, 157,
                    163, 188, 140, 74, 13, 25, 77, 243, 196, 112, 9,
                    180, 133, 23, 236, 231, 143, 213, 239, 59, 176,
                    180, 238, 98, 98, 216, 218, 32, 221, 136, 43,
                    206, 236, 26, 159, 155, 165, 34, 201, 226, 16,
                    185, 128, 124, 227, 184, 180, 187, 172, 165, 76,
                    95, 11, 69, 69, 179, 225, 172, 51, 144, 169, 194,
                    229, 189, 18, 89, 225, 30, 12, 15, 110, 81, 42,
                    47, 78, 61, 161, 60, 118, 91, 11, 46, 78, 133,
                    193, 144, 0, 132, 243, 253, 0, 45, 200, 31, 47,
                    137, 53, 21, 32, 12, 27, 127, 160, 89, 183, 11,
                    156, 113, 114, 72, 243, 238, 248, 218, 173, 235,
                    24, 3, 116, 136, 143, 100, 180, 232, 205, 194,
                    63, 46, 49, 24, 241, 175, 21, 161, 43, 124, 211,
                    232, 195, 97, 51, 44, 165, 163, 214, 35, 1, 15,
                    25, 232, 233, 125, 159, 6, 25, 173, 217, 197, 40,
                    188, 138, 25, 216, 225, 100, 241, 123, 55, 110,
                    243, 31, 39, 180, 90, 61, 145, 6, 229, 20, 176,
                    152, 171, 183, 178, 179, 232, 247, 31, 172, 212,
                    3, 167,
                ]),
                10,
            ),
            Restart,
            //Set(Key(vec![]), 16),
            //Merge(Key(vec![]), 129),
        ],
        0,
        0,
    );
}
