kcode-kweb-db 0.1.0

use crate::{
    HistoryEntry, MergePair, Node, NodeData, NodeHistory, NodeId, ObjectId, Owner, TransactionId,
    WriterId, graph::Graph,
};
use std::{
    cmp::Ordering,
    collections::{BTreeMap, BTreeSet},
};

#[derive(Clone, Default)]
pub(crate) struct Projection {
    pub nodes: BTreeMap<NodeId, ProjectedNode>,
    pub histories: BTreeMap<NodeId, NodeHistory>,
    pub objects: BTreeMap<ObjectId, ProjectedObject>,
}

#[derive(Clone)]
pub(crate) struct ProjectedNode {
    pub node: Node,
    pub visible_transaction: TransactionId,
}

#[derive(Clone, Copy)]
pub(crate) struct ProjectedObject {
    pub visible_transaction: TransactionId,
}

#[derive(Clone)]
struct NodeCandidate {
    transaction: TransactionId,
    data: NodeData,
}

impl Projection {
    pub fn build(graph: &Graph, writers: &[WriterId]) -> Self {
        let active = graph.active();
        let generations = graph.generations(&active);
        let ranks = writers
            .iter()
            .copied()
            .enumerate()
            .map(|(rank, writer)| (writer, rank))
            .collect::<BTreeMap<_, _>>();
        let order = transaction_order(&active, &generations);
        let (effective_creates, effective_updates, effective_connections) =
            effective_operations(graph, &order);

        let mut node_candidates: BTreeMap<NodeId, Vec<NodeCandidate>> = BTreeMap::new();
        for ((transaction, node), data) in effective_creates.iter().chain(effective_updates.iter())
        {
            node_candidates
                .entry(*node)
                .or_default()
                .push(NodeCandidate {
                    transaction: *transaction,
                    data: data.clone(),
                });
        }

        let mut nodes = BTreeMap::new();
        let mut visible_by_node = BTreeMap::new();
        let mut frontier_by_node = BTreeMap::new();
        for (id, candidates) in node_candidates {
            let candidate_by_transaction = candidates
                .iter()
                .map(|candidate| (candidate.transaction, candidate))
                .collect::<BTreeMap<_, _>>();
            let frontier = candidate_frontier(graph, candidate_by_transaction.keys().copied());
            let visible = preferred(graph, &frontier, &ranks);
            frontier_by_node.insert(id, frontier.clone());
            let Some(visible) = visible else {
                continue;
            };
            visible_by_node.insert(id, visible);
            let candidate = candidate_by_transaction[&visible];
            let record = graph.get(visible).expect("visible record exists");
            let connections =
                projected_connections(id, graph, &effective_connections, &generations, &ranks);
            nodes.insert(
                id,
                ProjectedNode {
                    node: Node {
                        id,
                        data: candidate.data.clone(),
                        connections,
                        last_author: record.parsed.unsigned.provenance.author.clone(),
                        committed_at: record.parsed.unsigned.committed_at,
                    },
                    visible_transaction: visible,
                },
            );
        }

        let objects = project_objects(graph, &active, &ranks);
        let histories = build_histories(
            graph,
            &active,
            &generations,
            &frontier_by_node,
            &visible_by_node,
        );
        Self {
            nodes,
            histories,
            objects,
        }
    }

    pub fn node_exists(&self, id: NodeId) -> bool {
        self.nodes.contains_key(&id)
    }

    pub fn pair_update_targets(&self, pair: MergePair) -> BTreeSet<NodeId> {
        self.histories
            .iter()
            .filter_map(|(node, history)| {
                if history.frontier.contains(&pair.first) && history.frontier.contains(&pair.second)
                {
                    Some(*node)
                } else {
                    None
                }
            })
            .collect()
    }
}

fn transaction_order(
    active: &BTreeSet<TransactionId>,
    generations: &BTreeMap<TransactionId, u64>,
) -> Vec<TransactionId> {
    let mut order = active.iter().copied().collect::<Vec<_>>();
    order.sort_by_key(|id| (generations.get(id).copied().unwrap_or(0), *id));
    order
}

type EffectiveNodes = BTreeMap<(TransactionId, NodeId), NodeData>;
type EffectiveConnections = BTreeSet<(TransactionId, NodeId, NodeId)>;

fn effective_operations(
    graph: &Graph,
    order: &[TransactionId],
) -> (EffectiveNodes, EffectiveNodes, EffectiveConnections) {
    let mut creates = BTreeMap::new();
    let mut updates = BTreeMap::new();
    let mut connections = BTreeSet::new();
    for transaction in order {
        let record = graph.get(*transaction).expect("active transaction exists");
        let mut ancestor_nodes = BTreeSet::new();
        for (created_in, node) in creates.keys() {
            if graph.is_ancestor(*created_in, *transaction) {
                ancestor_nodes.insert(*node);
            }
        }
        let mut ancestor_objects = BTreeSet::new();
        for (declared_in, declared_record) in graph.records() {
            if graph.is_ancestor(*declared_in, *transaction) {
                ancestor_objects.extend(
                    declared_record
                        .parsed
                        .unsigned
                        .objects
                        .iter()
                        .map(|object| object.id),
                );
            }
        }
        let current_objects = record
            .parsed
            .unsigned
            .objects
            .iter()
            .map(|object| object.id)
            .collect::<BTreeSet<_>>();
        let proposed_nodes = record
            .parsed
            .unsigned
            .creates
            .iter()
            .map(|operation| operation.id)
            .collect::<BTreeSet<_>>();
        let all_nodes = ancestor_nodes
            .union(&proposed_nodes)
            .copied()
            .collect::<BTreeSet<_>>();
        let all_objects = ancestor_objects
            .union(&current_objects)
            .copied()
            .collect::<BTreeSet<_>>();

        for operation in &record.parsed.unsigned.creates {
            let already_exists = creates.keys().any(|(created_in, node)| {
                *node == operation.id && graph.is_ancestor(*created_in, *transaction)
            });
            if !already_exists
                && references_resolve(operation.id, &operation.data, &all_nodes, &all_objects)
            {
                creates.insert((*transaction, operation.id), operation.data.clone());
            }
        }

        let mut current_effective_nodes = BTreeSet::new();
        for created_in_and_node in creates.keys() {
            if created_in_and_node.0 == *transaction {
                current_effective_nodes.insert(created_in_and_node.1);
            }
        }
        let all_effective_nodes = ancestor_nodes
            .union(&current_effective_nodes)
            .copied()
            .collect::<BTreeSet<_>>();
        for operation in &record.parsed.unsigned.updates {
            if ancestor_nodes.contains(&operation.id)
                && references_resolve(
                    operation.id,
                    &operation.data,
                    &all_effective_nodes,
                    &all_objects,
                )
            {
                updates.insert((*transaction, operation.id), operation.data.clone());
            }
        }
        for (from, to) in &record.parsed.unsigned.connections {
            if all_effective_nodes.contains(from) && all_effective_nodes.contains(to) {
                connections.insert((*transaction, *from, *to));
            }
        }
    }
    (creates, updates, connections)
}

fn references_resolve(
    self_id: NodeId,
    data: &NodeData,
    nodes: &BTreeSet<NodeId>,
    objects: &BTreeSet<ObjectId>,
) -> bool {
    if let Owner::Node(owner) = data.owner
        && owner != self_id
        && !nodes.contains(&owner)
    {
        return false;
    }
    if data
        .fixed_connections
        .iter()
        .flatten()
        .any(|node| *node != self_id && !nodes.contains(node))
    {
        return false;
    }
    data.objects.iter().all(|object| objects.contains(object))
}

fn candidate_frontier(
    graph: &Graph,
    candidates: impl IntoIterator<Item = TransactionId>,
) -> Vec<TransactionId> {
    let candidates = candidates.into_iter().collect::<Vec<_>>();
    candidates
        .iter()
        .copied()
        .filter(|candidate| {
            !candidates
                .iter()
                .any(|other| graph.is_ancestor(*candidate, *other))
        })
        .collect()
}

fn preferred(
    graph: &Graph,
    candidates: &[TransactionId],
    ranks: &BTreeMap<WriterId, usize>,
) -> Option<TransactionId> {
    candidates
        .iter()
        .copied()
        .max_by(|left, right| compare_preference(graph, *left, *right, ranks))
}

fn compare_preference(
    graph: &Graph,
    left: TransactionId,
    right: TransactionId,
    ranks: &BTreeMap<WriterId, usize>,
) -> Ordering {
    let left_writer = graph
        .get(left)
        .expect("candidate exists")
        .parsed
        .unsigned
        .writer;
    let right_writer = graph
        .get(right)
        .expect("candidate exists")
        .parsed
        .unsigned
        .writer;
    let left_rank = ranks.get(&left_writer).copied().unwrap_or(usize::MAX);
    let right_rank = ranks.get(&right_writer).copied().unwrap_or(usize::MAX);
    right_rank.cmp(&left_rank).then_with(|| left.cmp(&right))
}

fn project_objects(
    graph: &Graph,
    active: &BTreeSet<TransactionId>,
    ranks: &BTreeMap<WriterId, usize>,
) -> BTreeMap<ObjectId, ProjectedObject> {
    let mut candidates: BTreeMap<ObjectId, Vec<TransactionId>> = BTreeMap::new();
    for transaction in active {
        let record = graph.get(*transaction).expect("active transaction exists");
        for object in &record.parsed.unsigned.objects {
            candidates.entry(object.id).or_default().push(*transaction);
        }
    }
    candidates
        .into_iter()
        .filter_map(|(id, candidates)| {
            let frontier = candidate_frontier(graph, candidates);
            preferred(graph, &frontier, ranks).map(|visible_transaction| {
                (
                    id,
                    ProjectedObject {
                        visible_transaction,
                    },
                )
            })
        })
        .collect()
}

fn projected_connections(
    node: NodeId,
    graph: &Graph,
    connections: &EffectiveConnections,
    generations: &BTreeMap<TransactionId, u64>,
    ranks: &BTreeMap<WriterId, usize>,
) -> Vec<NodeId> {
    let mut latest = BTreeMap::<NodeId, TransactionId>::new();
    for (transaction, from, to) in connections {
        if *from != node {
            continue;
        }
        latest
            .entry(*to)
            .and_modify(|current| {
                if compare_connection(graph, *transaction, *current, generations, ranks)
                    == Ordering::Greater
                {
                    *current = *transaction;
                }
            })
            .or_insert(*transaction);
    }
    let mut values = latest.into_iter().collect::<Vec<_>>();
    values.sort_by(|(_, left), (_, right)| {
        compare_connection(graph, *right, *left, generations, ranks)
    });
    values.into_iter().map(|(target, _)| target).collect()
}

fn compare_connection(
    graph: &Graph,
    left: TransactionId,
    right: TransactionId,
    generations: &BTreeMap<TransactionId, u64>,
    ranks: &BTreeMap<WriterId, usize>,
) -> Ordering {
    generations[&left]
        .cmp(&generations[&right])
        .then_with(|| compare_preference(graph, left, right, ranks))
}

fn build_histories(
    graph: &Graph,
    active: &BTreeSet<TransactionId>,
    generations: &BTreeMap<TransactionId, u64>,
    frontiers: &BTreeMap<NodeId, Vec<TransactionId>>,
    visible: &BTreeMap<NodeId, TransactionId>,
) -> BTreeMap<NodeId, NodeHistory> {
    let mut entries = BTreeMap::<NodeId, Vec<HistoryEntry>>::new();
    for (transaction, record) in graph.records() {
        let created = record
            .parsed
            .unsigned
            .creates
            .iter()
            .map(|operation| operation.id)
            .collect::<BTreeSet<_>>();
        let updated = record
            .parsed
            .unsigned
            .updates
            .iter()
            .map(|operation| operation.id)
            .collect::<BTreeSet<_>>();
        let mut touched = created.union(&updated).copied().collect::<BTreeSet<_>>();
        for (from, to) in &record.parsed.unsigned.connections {
            touched.insert(*from);
            touched.insert(*to);
        }
        for node in touched {
            let connections = record
                .parsed
                .unsigned
                .connections
                .iter()
                .copied()
                .filter(|(from, to)| *from == node || *to == node)
                .collect();
            entries.entry(node).or_default().push(HistoryEntry {
                transaction_id: *transaction,
                writer: record.parsed.unsigned.writer,
                committed_at: record.parsed.unsigned.committed_at,
                provenance: record.parsed.unsigned.provenance.clone(),
                active: active.contains(transaction),
                created: created.contains(&node),
                updated: updated.contains(&node),
                connections,
                merge_pairs: record.parsed.unsigned.merge_pairs.clone(),
            });
        }
    }
    entries
        .into_iter()
        .map(|(node_id, mut entries)| {
            entries.sort_by(|left, right| {
                history_key(right, generations).cmp(&history_key(left, generations))
            });
            let history = NodeHistory {
                node_id,
                frontier: frontiers.get(&node_id).cloned().unwrap_or_default(),
                visible: visible.get(&node_id).copied(),
                entries,
            };
            (node_id, history)
        })
        .collect()
}

fn history_key(
    entry: &HistoryEntry,
    generations: &BTreeMap<TransactionId, u64>,
) -> (bool, u64, TransactionId) {
    (
        entry.active,
        generations.get(&entry.transaction_id).copied().unwrap_or(0),
        entry.transaction_id,
    )
}