State is Send + Sync; shared lane layout; log_window 119bbf50cb86 resolution

//! Lane layout for drawing history as a graph: each change takes a lane,

//! its first dependency continues that lane, other dependencies take free

//! lanes, so edges flow from a change down to what it depends on. Shared

//! by `oxy log` and hosts, so every view draws the same picture.

use crate::hash::ChangeHash;

use std::collections::{HashMap, HashSet};

/// A row of the graph: the change's lane and the edges drawn from it.

#[derive(Clone, Debug, PartialEq, Eq)]

pub struct Row {

    pub lane: usize,

    /// `(from_lane, to_lane)` for each dependency drawn from this row to

    /// the rows below.

    pub edges: Vec<(usize, usize)>,

    /// Lanes that pass through this row without touching it.

    pub through: Vec<usize>,

}

/// `changes` newest first as `(hash, deps)`. A dependency outside the

/// list ends its lane at the bottom.

pub fn layout(changes: &[(ChangeHash, Vec<ChangeHash>)]) -> Vec<Row> {

    let mut active: Vec<Option<ChangeHash>> = Vec::new();

    let mut rows = Vec::with_capacity(changes.len());

    let known: HashSet<&ChangeHash> = changes.iter().map(|(h, _)| h).collect();

    let mut lanes: HashMap<ChangeHash, usize> = HashMap::new();

    for (hash, deps) in changes {

        let lane = match active.iter().position(|a| a.as_ref() == Some(hash)) {

            Some(l) => l,

            None => match active.iter().position(|a| a.is_none()) {

                Some(l) => {

                    active[l] = Some(*hash);

                    l

                }

                None => {

                    active.push(Some(*hash));

                    active.len() - 1

                }

            },

        };

        lanes.insert(*hash, lane);

        let mut edges = Vec::new();

        let deps: Vec<&ChangeHash> = deps.iter().filter(|d| known.contains(d)).collect();

        active[lane] = None;

        for (i, d) in deps.iter().enumerate() {

            let target = match active.iter().position(|a| a.as_ref() == Some(*d)) {

                Some(l) => l,

                None => {

                    let l = if i == 0 && active[lane].is_none() {

                        lane

                    } else {

                        match active.iter().position(|a| a.is_none()) {

                            Some(l) => l,

                            None => {

                                active.push(None);

                                active.len() - 1

                            }

                        }

                    };

                    active[l] = Some(**d);

                    l

                }

            };

            edges.push((lane, target));

        }

        let through: Vec<usize> = active

            .iter()

            .enumerate()

            .filter(|(l, a)| a.is_some() && *l != lane && !edges.iter().any(|e| e.1 == *l))

            .map(|(l, _)| l)

            .collect();

        rows.push(Row { lane, edges, through });

        while active.last().is_some_and(|a| a.is_none()) {

            active.pop();

        }

    }

    rows

}

/// The number of lanes the rows use.

pub fn width(rows: &[Row]) -> usize {

    rows.iter()

        .map(|r| r.lane.max(r.edges.iter().map(|e| e.1).max().unwrap_or(0)).max(r.through.iter().copied().max().unwrap_or(0)))

        .max()

        .map(|m| m + 1)

        .unwrap_or(1)

}

#[cfg(test)]

mod tests {

    use super::*;

    use crate::hash::ObjectRef;

    fn h(n: u8) -> ChangeHash {

        ObjectRef([n; 32])

    }

    #[test]

    fn linear_history_is_one_lane() {

        let rows = layout(&[(h(3), vec![h(2)]), (h(2), vec![h(1)]), (h(1), vec![])]);

        assert!(rows.iter().all(|r| r.lane == 0), "{rows:?}");

        assert_eq!(rows[0].edges, vec![(0, 0)]);

        assert_eq!(width(&rows), 1);

    }

    #[test]

    fn a_diamond_takes_two_lanes_and_rejoins() {

        let rows = layout(&[(h(4), vec![h(2), h(3)]), (h(2), vec![h(1)]), (h(3), vec![h(1)]), (h(1), vec![])]);

        assert_eq!(rows[0].edges, vec![(0, 0), (0, 1)]);

        assert_eq!(rows[2].lane, 1);

        assert_eq!(rows[2].edges, vec![(1, 0)], "the second branch joins the first lane");

        assert_eq!(width(&rows), 2);

    }

}

pub fn verify_challenge(

    identity: &Identity,

    sig: &Signature,

    challenge: &[u8],

) -> Result<(), VerifyError> {

    verify(

        identity,

        sig,

        Domain::Challenge,

        &challenge_target(challenge),

    )

        assert!(

            verify_challenge(&id, &sig, &[8u8; 32]).is_err(),

            "other bytes"

        );

        assert!(

            verify_challenge(&other, &sig, &challenge).is_err(),

            "other identity"

        );

pub mod lanes;

    /// A window of `log_state`: entries `offset..offset+limit` and the total

    /// count, for paginated views.

    pub fn log_window(&self, heads: &[ChangeHash], offset: usize, limit: usize) -> Result<(Vec<LogEntry>, usize)> {

        let all = self.log_state(heads)?;

        let total = all.len();

        Ok((all.into_iter().skip(offset).take(limit).collect(), total))

    }

        Ok(self

            .receive_push_report(bundle, updates, policy, tags)?

            .results)

                let heads = self

                    .store

                    .get_state(&u.new_state)

                    .map(|s| s.heads)

                    .unwrap_or_default();

                report.updated.push(RefUpdated {

                    name: u.name.clone(),

                    old_state: u.old_state,

                    new_state: u.new_state,

                    heads,

                });

use std::sync::{Arc, Mutex};

#[derive(Default)]

    /// Memoised transitive dependencies. A mutex, not a `RefCell`, so a

    /// loaded state can be shared across threads by a host that caches it.

    closure: Mutex<HashMap<ChangeHash, Arc<HashSet<ChangeHash>>>>,

impl Clone for State {

    fn clone(&self) -> State {

        State {

            changes: self.changes.clone(),

            tree: self.tree.clone(),

            files: self.files.clone(),

            replaces: self.replaces.clone(),

            closure: Mutex::new(self.closure.lock().unwrap().clone()),

        }

    }

}

        self.closure.lock().unwrap().clear();

    pub fn closure(&self, h: &ChangeHash) -> Arc<HashSet<ChangeHash>> {

        if let Some(c) = self.closure.lock().unwrap().get(h) {

        let rc = Arc::new(out);

        self.closure.lock().unwrap().insert(*h, rc.clone());

    assert_eq!(

        pushes.lock().unwrap().as_slice(),

        ["andy/app: 1 ok, 1 updated to 1 head(s), 1 imported"]

    );

- [x] `Repo::log_window` and the shared `oxy_core::lanes::layout`; `State` is `Send + Sync` (closure cache behind a mutex) so hosts can cache loaded states.

## Roadmap

The cross-product order of work is in `docs/roadmap.md`.

    let challenge = hex_bytes(challenge_hex.trim())

        .ok_or_else(|| anyhow::anyhow!("the challenge must be hex"))?;

    let sig = sk

        .sign_challenge(&key, &challenge)

        .map_err(|e| anyhow::anyhow!("{e}"))?;

        println!(

            "{{\"key\":\"{}\",\"signature\":\"{}\"}}",

            key.to_hex(),

            encoded

        );

    (0..s.len())

        .step_by(2)

        .map(|i| u8::from_str_radix(&s[i..i + 2], 16).ok())

        .collect()

            IdentityCmd::SignChallenge { challenge, json } => {

                identity::sign_challenge(&challenge, json)

            }