Property tests: the order of changes never changes the state 37c299cec358

# Seeds for failure cases proptest has generated in the past. It is

# automatically read and these particular cases re-run before any

# novel cases are generated.

#

# It is recommended to check this file in to source control so that

# everyone who runs the test benefits from these saved cases.

cc 150dc6c3551a31ba699711e0bebca2b54b29cbf003a0e8e9035d978f4bcfd65d # shrinks to sessions = [[[Insert { file: 0, at: 82, word: 2 }]], [[Insert { file: 3, at: 15216962264731610119, word: 0 }, Replace { file: 1, at: 1617507299102404918, word: 0 }, Delete { file: 1, at: 6875205767748926991 }, Delete { file: 0, at: 4285533219516317091 }], [Delete { file: 0, at: 14950834157168413373 }, Delete { file: 3, at: 7384109036823047037 }, Delete { file: 0, at: 15334878224541300421 }, Insert { file: 3, at: 6722035807729590280, word: 2 }], [Insert { file: 3, at: 5966679767442278895, word: 2 }, Replace { file: 1, at: 17587470115659482894, word: 0 }]]], seed = 2287439951785091165

//! Property tests for spec §7.3: a state is a function of its set of

//! changes, never of the order they arrived in.

//!

//! Each case seeds a repository with a few files, lets two or three clones

//! diverge through random edit sessions (inserts, deletes, replacements,

//! new and removed files, so conflicts happen too), then rebuilds the

//! union of every clone's changes in many orders: arbitrary orders through

//! `State::add_unchecked` and random dependency-respecting orders through

//! `State::add`. Every order must validate and give byte-identical

//! checkpoints and identical materialized trees. Finally the clones push

//! to one origin in a random order and a fresh clone must see that state,

//! and a checkpoint of the state must restore it exactly.

use oxy_core::objects::Change;

use oxy_core::repo::Repo;

use oxy_core::state::State;

use proptest::prelude::*;

use rand::rngs::StdRng;

use rand::seq::SliceRandom;

use rand::{Rng, SeedableRng};

use std::collections::{BTreeMap, BTreeSet};

use std::path::Path;

/// Point `$OXY_HOME` at a throwaway directory once per test process.

fn hermetic() {

    static ONCE: std::sync::Once = std::sync::Once::new();

    static DIR: std::sync::OnceLock<tempfile::TempDir> = std::sync::OnceLock::new();

    ONCE.call_once(|| {

        let d = tempfile::tempdir().unwrap();

        std::env::set_var("OXY_HOME", d.path());

        DIR.set(d).ok();

    });

}

/// Files the edits address; the first `SEEDED` exist in the base state.

const FILES: [&str; 4] = ["a.txt", "b.txt", "dir/c.txt", "d.txt"];

const SEEDED: usize = 3;

/// A few short lines, so identical lines are common and the diff has

/// to choose between equally good alignments.

const WORDS: [&str; 5] = ["alpha\n", "beta\n", "gamma\n", "delta\n", "alpha\n"];

#[derive(Clone, Debug)]

enum Edit {

    Insert { file: usize, at: usize, word: usize },

    Delete { file: usize, at: usize },

    Replace { file: usize, at: usize, word: usize },

    Remove { file: usize },

}

fn edit() -> impl Strategy<Value = Edit> {

    let file = 0..FILES.len();

    prop_oneof![

        4 => (file.clone(), any::<usize>(), 0..WORDS.len()).prop_map(|(file, at, word)| Edit::Insert { file, at, word }),

        3 => (file.clone(), any::<usize>()).prop_map(|(file, at)| Edit::Delete { file, at }),

        3 => (file.clone(), any::<usize>(), 0..WORDS.len()).prop_map(|(file, at, word)| Edit::Replace { file, at, word }),

        1 => file.prop_map(|file| Edit::Remove { file }),

    ]

}

/// One clone's session: a few commits of a few edits each.

fn session() -> impl Strategy<Value = Vec<Vec<Edit>>> {

    prop::collection::vec(prop::collection::vec(edit(), 1..5), 1..4)

}

fn lines(root: &Path, rel: &str) -> Option<Vec<String>> {

    let text = std::fs::read_to_string(root.join(rel)).ok()?;

    Some(text.split_inclusive('\n').map(String::from).collect())

}

fn apply(root: &Path, e: &Edit) {

    let file = match e {

        Edit::Remove { file } => {

            let _ = std::fs::remove_file(root.join(FILES[*file]));

            return;

        }

        Edit::Insert { file, .. } | Edit::Delete { file, .. } | Edit::Replace { file, .. } => *file,

    };

    let mut l = lines(root, FILES[file]).unwrap_or_default();

    match *e {

        Edit::Insert { at, word, .. } => l.insert(at % (l.len() + 1), WORDS[word].to_string()),

        Edit::Delete { at, .. } if !l.is_empty() => {

            let i = at % l.len();

            l.remove(i);

        }

        Edit::Replace { at, word, .. } if !l.is_empty() => {

            let i = at % l.len();

            l[i] = WORDS[word].to_string();

        }

        _ => {}

    }

    let path = root.join(FILES[file]);

    std::fs::create_dir_all(path.parent().unwrap()).unwrap();

    std::fs::write(path, l.concat()).unwrap();

}

/// Every change reachable from `repo`'s bookmark heads.

fn changes_of(repo: &Repo, into: &mut BTreeMap<oxy_core::hash::ChangeHash, Change>) {

    let mut stack = repo.bookmark_heads().unwrap();

    while let Some(h) = stack.pop() {

        if into.contains_key(&h) {

            continue;

        }

        let c = repo.store().get_change(&h).unwrap();

        stack.extend(c.deps.iter().copied());

        into.insert(h, c);

    }

}

/// What must not depend on order: the checkpoint bytes, the heads and

/// the materialized tree.

fn fingerprint(

    state: &State,

) -> (

    Vec<u8>,

    BTreeSet<oxy_core::hash::ChangeHash>,

    oxy_core::tree::TreeView,

    BTreeMap<String, oxy_core::state::FileState>,

) {

    let snap = state.materialize();

    (

        state.checkpoint_payload(),

        state.heads().into_iter().collect(),

        snap.tree,

        snap.files,

    )

}

fn run_case(sessions: Vec<Vec<Vec<Edit>>>, seed: u64) -> Result<(), TestCaseError> {

    hermetic();

    let dir = tempfile::tempdir().unwrap();

    let root = dir.path();

    let origin_path = root.join("origin");

    Repo::init(&origin_path).unwrap();

    let url = origin_path.to_string_lossy().to_string();

    // The shared base.

    let seed_repo = Repo::clone(&url, &root.join("seed")).unwrap();

    for (i, f) in FILES.iter().take(SEEDED).enumerate() {

        let p = root.join("seed").join(f);

        std::fs::create_dir_all(p.parent().unwrap()).unwrap();

        std::fs::write(p, WORDS[..=i + 1].concat()).unwrap();

    }

    seed_repo.commit("base", &[]).unwrap();

    assert!(seed_repo

        .push("origin", false)

        .unwrap()

        .iter()

        .all(|r| r.ok));

    // Diverge.

    let mut clones = Vec::new();

    for (n, session) in sessions.iter().enumerate() {

        let wc = root.join(format!("clone{n}"));

        let repo = Repo::clone(&url, &wc).unwrap();

        for (k, commit) in session.iter().enumerate() {

            for e in commit {

                apply(&wc, e);

            }

            let s = repo.snapshot("oxy status").unwrap();

            if s.statuses.is_empty() {

                continue;

            }

            repo.commit(&format!("clone {n} commit {k}"), &[]).unwrap();

        }

        clones.push(repo);

    }

    let mut all = BTreeMap::new();

    for c in &clones {

        changes_of(c, &mut all);

    }

    let changes: Vec<Change> = all.values().cloned().collect();

    // The reference: every change, sorted by hash.

    let mut reference = State::new();

    for c in &changes {

        reference.add_unchecked(c.clone());

    }

    prop_assert!(reference.validate().is_ok());

    let want = fingerprint(&reference);

    // A checkpoint restores the same state.

    let restored = State::from_checkpoint_payload(&want.0).unwrap();

    prop_assert!(

        fingerprint(&restored) == want,

        "checkpoint round trip changed the state"

    );

    let mut rng = StdRng::seed_from_u64(seed);

    for _ in 0..4 {

        // Any order at all.

        let mut order = changes.clone();

        order.shuffle(&mut rng);

        let mut st = State::new();

        for c in order {

            st.add_unchecked(c);

        }

        prop_assert!(st.validate().is_ok());

        prop_assert!(

            fingerprint(&st) == want,

            "unchecked order changed the state"

        );

        // A random order that respects dependencies, the order a fetch sees.

        let mut pending: Vec<&Change> = changes.iter().collect();

        let mut st = State::new();

        while !pending.is_empty() {

            let ready: Vec<usize> = (0..pending.len())

                .filter(|&i| pending[i].deps.iter().all(|d| st.contains(d)))

                .collect();

            prop_assert!(!ready.is_empty(), "dependency cycle");

            let pick = ready[rng.gen_range(0..ready.len())];

            st.add(pending.swap_remove(pick).clone()).unwrap();

        }

        prop_assert!(

            fingerprint(&st) == want,

            "dependency order changed the state"

        );

    }

    // Through the protocol: push in a random order, then a fresh clone.

    let mut order: Vec<usize> = (0..clones.len()).collect();

    order.shuffle(&mut rng);

    for i in order {

        let c = &clones[i];

        // A clone behind the origin is told to pull first, as a user is.

        if !c

            .push("origin", false)

            .is_ok_and(|r| r.iter().all(|r| r.ok))

        {

            c.pull("origin").unwrap();

            prop_assert!(

                c.push("origin", false).unwrap().iter().all(|r| r.ok),

                "push after pull"

            );

        }

    }

    let fresh = Repo::clone(&url, &root.join("fresh")).unwrap();

    let heads = fresh.bookmark_heads().unwrap();

    let pushed = fresh.load_state_full(&heads).unwrap();

    prop_assert!(fingerprint(&pushed) == want, "the pushed state differs");

    Ok(())

}

proptest! {

    #![proptest_config(ProptestConfig { cases: 32, ..ProptestConfig::default() })]

    #[test]

    fn order_of_changes_is_irrelevant(sessions in prop::collection::vec(session(), 2..4), seed in any::<u64>()) {

        run_case(sessions, seed)?;

    }

}

name = "bit-set"

version = "0.8.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "08807e080ed7f9d5433fa9b275196cfc35414f66a0c79d864dc51a0d825231a3"

dependencies = [

 "bit-vec 0.8.0",

]

[[package]]

version = "0.8.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "5e764a1d40d510daf35e07be9eb06e75770908c27d411ee6c92109c9840eaaf7"

[[package]]

name = "bit-vec"

version = "0.3.4"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "899def5c37c4fd7b2664648c28120ecec138e4d395b459e5ca34f9cce2dd77fd"

dependencies = [

 "cfg-if",

 "libc",

 "r-efi 5.3.0",

 "wasip2",

]

[[package]]

name = "getrandom"

 "r-efi 6.0.0",

 "proptest",

 "rand 0.8.8",

name = "proptest"

version = "1.11.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "4b45fcc2344c680f5025fe57779faef368840d0bd1f42f216291f0dc4ace4744"

dependencies = [

 "bit-set",

 "bit-vec 0.8.0",

 "bitflags",

 "num-traits",

 "rand 0.9.5",

 "rand_chacha 0.9.0",

 "rand_xorshift",

 "regex-syntax",

 "rusty-fork",

 "tempfile",

 "unarray",

]

[[package]]

name = "quick-error"

version = "1.2.3"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"

[[package]]

version = "5.3.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "69cdb34c158ceb288df11e18b4bd39de994f6657d83847bdffdbd7f346754b0f"

[[package]]

name = "r-efi"

 "rand_chacha 0.3.1",

name = "rand"

version = "0.9.5"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "b9ef1d0d795eb7d84685bca4f72f3649f064e6641543d3a8c415898726a57b41"

dependencies = [

 "rand_chacha 0.9.0",

 "rand_core 0.9.5",

]

[[package]]

name = "rand_chacha"

version = "0.9.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "d3022b5f1df60f26e1ffddd6c66e8aa15de382ae63b3a0c1bfc0e4d3e3f325cb"

dependencies = [

 "ppv-lite86",

 "rand_core 0.9.5",

]

[[package]]

version = "0.9.5"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "76afc826de14238e6e8c374ddcc1fa19e374fd8dd986b0d2af0d02377261d83c"

dependencies = [

 "getrandom 0.3.4",

]

[[package]]

name = "rand_core"

name = "rand_xorshift"

version = "0.4.0"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "513962919efc330f829edb2535844d1b912b0fbe2ca165d613e4e8788bb05a5a"

dependencies = [

 "rand_core 0.9.5",

]

[[package]]

name = "rusty-fork"

version = "0.3.1"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "cc6bf79ff24e648f6da1f8d1f011e9cac26491b619e6b9280f2b47f1774e6ee2"

dependencies = [

 "fnv",

 "quick-error",

 "tempfile",

 "wait-timeout",

]

[[package]]

name = "unarray"

version = "0.1.4"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "eaea85b334db583fe3274d12b4cd1880032beab409c0d774be044d4480ab9a94"

[[package]]

name = "wait-timeout"

version = "0.2.1"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "09ac3b126d3914f9849036f826e054cbabdc8519970b8998ddaf3b5bd3c65f11"

dependencies = [

 "libc",

]

[[package]]

name = "wasip2"

version = "1.0.4+wasi-0.2.12"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "b67efb37e106e55ce722a510d6b5f9c17f083e5fc79afc2badeb12cc313d9487"

dependencies = [

 "wit-bindgen",

]

[[package]]

name = "wit-bindgen"

version = "0.57.1"

source = "registry+https://github.com/rust-lang/crates.io-index"

checksum = "1ebf944e87a7c253233ad6766e082e3cd714b5d03812acc24c318f549614536e"

[[package]]

 "bit-vec 0.9.1",

proptest = "1"