use std::collections::{BTreeMap, BTreeSet, HashMap};
use std::sync::OnceLock;
use serde::{Deserialize, Serialize};
use crate::cpn::mcard_token::{PlaceMCard, TransitionMCard};
use super::place_role_binding::{PlaceRole, VIRTUAL_BOTTOM, VIRTUAL_TOP};
use super::tarjan_scc::tarjan_scc;
use super::{extremal_names, LatticeBitset, LatticeBitsetIndex};
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PlaceTypeLattice {
pub places: BTreeMap<String, PlaceMCard>,
pub roles: BTreeMap<String, PlaceRole>,
pub sccs: Vec<Vec<String>>,
pub node_to_scc: BTreeMap<String, usize>,
pub bottom: String,
pub top: String,
pub exception_places: Vec<String>,
pub dm_cuts: Vec<String>,
reachability: BTreeMap<String, BTreeSet<String>>,
#[serde(skip)]
index: OnceLock<LatticeBitsetIndex>,
}
impl PartialEq for PlaceTypeLattice {
fn eq(&self, other: &Self) -> bool {
self.places == other.places
&& self.roles == other.roles
&& self.sccs == other.sccs
&& self.node_to_scc == other.node_to_scc
&& self.bottom == other.bottom
&& self.top == other.top
&& self.exception_places == other.exception_places
&& self.dm_cuts == other.dm_cuts
&& self.reachability == other.reachability
}
}
impl Eq for PlaceTypeLattice {}
impl PlaceTypeLattice {
fn idx(&self) -> &LatticeBitsetIndex {
self.index.get_or_init(|| LatticeBitsetIndex::from_reachability(&self.reachability, &self.bottom, &self.top))
}
pub fn from_net(
places: &[PlaceMCard],
transitions: &[TransitionMCard],
exception_place_ids: Option<&BTreeSet<String>>,
) -> Self {
Self::from_net_with_options(places, transitions, exception_place_ids, true)
}
pub fn from_net_with_options(
places: &[PlaceMCard],
transitions: &[TransitionMCard],
exception_place_ids: Option<&BTreeSet<String>>,
complete_cuts: bool,
) -> Self {
let mut place_map = BTreeMap::new();
let mut explicit_exc = exception_place_ids.cloned().unwrap_or_default();
for p in places {
place_map.insert(p.place_id.clone(), p.clone());
let low = p.place_id.to_lowercase();
if p.role == "Exception" || low.contains("exception") || low.contains("trap") {
explicit_exc.insert(p.place_id.clone());
}
}
let mut adj: BTreeMap<String, BTreeSet<String>> =
place_map.keys().map(|k| (k.clone(), BTreeSet::new())).collect();
for tr in transitions {
for u in &tr.input_places {
if !adj.contains_key(u) { continue; }
for v in &tr.output_places {
if adj.contains_key(v) { adj.get_mut(u).unwrap().insert(v.clone()); }
}
}
}
let all_nodes: Vec<String> = place_map.keys().cloned().collect();
let sccs = tarjan_scc(&all_nodes, &adj);
let mut node_to_scc = BTreeMap::new();
for (idx, comp) in sccs.iter().enumerate() {
for pid in comp { node_to_scc.insert(pid.clone(), idx); }
}
let (mut scc_in, mut scc_out_normal) = (vec![BTreeSet::new(); sccs.len()], vec![BTreeSet::new(); sccs.len()]);
for (u, nbrs) in &adj {
let su = node_to_scc[u];
for v in nbrs {
let sv = node_to_scc[v];
if su != sv {
scc_in[sv].insert(su);
if !explicit_exc.contains(v) { scc_out_normal[su].insert(sv); }
}
}
}
let mut roles = BTreeMap::new();
let (mut init_cands, mut term_cands) = (Vec::new(), Vec::new());
for (pid, p) in &place_map {
let s_idx = node_to_scc[pid];
if explicit_exc.contains(pid) {
roles.insert(pid.clone(), PlaceRole::Exception);
} else if p.role == "InitialBottom" || scc_in[s_idx].is_empty() {
roles.insert(pid.clone(), PlaceRole::InitialBottom);
init_cands.push(pid.clone());
} else if p.role == "TerminalTop" || scc_out_normal[s_idx].is_empty() {
roles.insert(pid.clone(), PlaceRole::TerminalTop);
term_cands.push(pid.clone());
} else {
roles.insert(pid.clone(), PlaceRole::Intermediate);
}
}
let bottom_id = if init_cands.len() == 1 { init_cands[0].clone() } else { VIRTUAL_BOTTOM.to_string() };
let top_id = if term_cands.len() == 1 { term_cands[0].clone() } else { VIRTUAL_TOP.to_string() };
let mut aug_set: BTreeSet<String> = all_nodes.into_iter().collect();
aug_set.insert(bottom_id.clone());
aug_set.insert(top_id.clone());
let sorted_aug: Vec<String> = aug_set.into_iter().collect();
let n0 = sorted_aug.len();
let aug_idx: HashMap<&str, usize> = sorted_aug.iter().enumerate().map(|(i, n)| (n.as_str(), i)).collect();
let (bot_i, top_i) = (aug_idx[bottom_id.as_str()], aug_idx[top_id.as_str()]);
let mut aug_adj = vec![LatticeBitset::zero(n0); n0];
for (i, name) in sorted_aug.iter().enumerate() {
if i == bot_i {
aug_adj[i] = LatticeBitset::full(n0);
} else {
aug_adj[i].set(i);
aug_adj[i].set(top_i);
if let Some(nbrs) = adj.get(name) {
for v in nbrs { aug_adj[i].set(aug_idx[v.as_str()]); }
}
}
}
let mut reach0 = vec![LatticeBitset::zero(n0); n0];
for start in (0..n0).rev() {
let mut vis = LatticeBitset::zero(n0);
vis.set(start);
let mut todo = aug_adj[start].andnot(&vis);
while let Some(nxt) = todo.first_set() {
todo.clear(nxt);
if !reach0[nxt].is_empty() {
vis.bitor_assign(&reach0[nxt]);
todo.andnot_assign(&reach0[nxt]);
} else {
vis.set(nxt);
todo.bitor_assign(&aug_adj[nxt].andnot(&vis));
}
}
reach0[start] = vis;
}
let mut down0 = vec![LatticeBitset::zero(n0); n0];
for (x, rx) in reach0.iter().enumerate() {
for y in rx.iter_ones() { down0[y].set(x); }
}
let mut dm_cuts_list = Vec::new();
let (mut final_nodes, mut final_up, mut final_down) = (sorted_aug.clone(), reach0.clone(), down0.clone());
if complete_cuts {
let existing: BTreeSet<LatticeBitset> = down0.iter().cloned().collect();
let mut all_cuts = existing.clone();
let mut queue: Vec<LatticeBitset> = existing.iter().cloned().collect();
while let Some(c1) = queue.pop() {
let snap: Vec<LatticeBitset> = all_cuts.iter().cloned().collect();
for c2 in snap {
let inter = c1.bitand(&c2);
if !inter.is_empty() && all_cuts.insert(inter.clone()) { queue.push(inter); }
}
}
if all_cuts.len() > existing.len() {
let mut cut_by_name: BTreeMap<String, LatticeBitset> =
sorted_aug.iter().enumerate().map(|(i, n)| (n.clone(), down0[i].clone())).collect();
for c_mask in &all_cuts {
if existing.contains(c_mask) { continue; }
let c_ind = c_mask.iter_ones();
let u_ind: Vec<usize> = (0..n0).filter(|&y| c_mask.is_subset(&down0[y])).collect();
let max_c = extremal_names(&c_ind, &reach0, &sorted_aug, true);
let min_u = extremal_names(&u_ind, &reach0, &sorted_aug, false);
let cut_id = format!("__dm_cut__{}__to__{}__", max_c.join("_"), min_u.join("_"));
dm_cuts_list.push(cut_id.clone());
cut_by_name.insert(cut_id.clone(), c_mask.clone());
roles.insert(cut_id, PlaceRole::Intermediate);
}
dm_cuts_list.sort();
final_nodes = cut_by_name.keys().cloned().collect();
let k = final_nodes.len();
let cut_masks: Vec<LatticeBitset> = final_nodes.iter().map(|n| cut_by_name[n].clone()).collect();
final_up = vec![LatticeBitset::zero(k); k];
final_down = vec![LatticeBitset::zero(k); k];
for i in 0..k {
for j in 0..k {
if cut_masks[i].is_subset(&cut_masks[j]) {
final_up[i].set(j);
final_down[j].set(i);
}
}
}
}
}
let reach: BTreeMap<String, BTreeSet<String>> = final_nodes.iter().enumerate().map(|(i, n)| {
(n.clone(), final_up[i].iter_ones().into_iter().map(|j| final_nodes[j].clone()).collect())
}).collect();
let idx = LatticeBitsetIndex::build(final_nodes, final_up, final_down, &bottom_id, &top_id);
let lock = OnceLock::new();
let _ = lock.set(idx);
Self {
places: place_map, roles, sccs, node_to_scc, bottom: bottom_id, top: top_id,
exception_places: explicit_exc.into_iter().collect(), dm_cuts: dm_cuts_list, reachability: reach, index: lock,
}
}
pub fn leq(&self, p1: &str, p2: &str) -> bool {
if p1 == p2 || p1 == self.bottom || p2 == self.top { return true; }
let idx = self.idx();
match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
(Some(&i), Some(&j)) => idx.up[i].test(j),
_ => false,
}
}
pub fn is_subtype(&self, p1: &str, p2: &str) -> bool { self.leq(p1, p2) }
pub fn same_scc(&self, p1: &str, p2: &str) -> bool {
if p1 == p2 { return true; }
let idx = self.idx();
match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
(Some(&i), Some(&j)) => idx.scc_rep[i] == idx.scc_rep[j],
_ => false,
}
}
pub fn join(&self, p1: &str, p2: &str) -> String {
if self.leq(p1, p2) { return p2.to_string(); }
if self.leq(p2, p1) { return p1.to_string(); }
let idx = self.idx();
match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
(Some(&i), Some(&j)) => idx.nodes[idx.join_idx(i, j)].clone(),
_ => self.top.clone(),
}
}
pub fn meet(&self, p1: &str, p2: &str) -> String {
if self.leq(p1, p2) { return p1.to_string(); }
if self.leq(p2, p1) { return p2.to_string(); }
let idx = self.idx();
match (idx.node_to_idx.get(p1), idx.node_to_idx.get(p2)) {
(Some(&i), Some(&j)) => idx.nodes[idx.meet_idx(i, j)].clone(),
_ => self.bottom.clone(),
}
}
pub fn to_type_graph(&self) -> (Vec<String>, Vec<(String, String)>, String, String) {
let idx = self.idx();
let mut edges = Vec::new();
for (i, u) in idx.nodes.iter().enumerate() {
for j in idx.up[i].iter_ones() {
edges.push((u.clone(), idx.nodes[j].clone()));
}
}
(idx.nodes.clone(), edges, self.bottom.clone(), self.top.clone())
}
pub fn verify_lattice_laws(&self) -> bool {
let idx = self.idx();
let k = idx.nodes.len();
if k == 0 { return true; }
let (Some(bot_u), Some(top_u)) = (idx.bot_idx, idx.top_idx) else { return false; };
let (bot_i, top_i) = (bot_u as usize, top_u as usize);
for a in 0..k {
let up_a = &idx.up[a];
if !up_a.test(a) || !idx.up[bot_i].test(a) || !up_a.test(top_i) { return false; }
let (down_a, rep_a) = (&idx.down[a], idx.scc_rep[a]);
for b in (a + 1)..k {
let (up_b, down_b) = (&idx.up[b], &idx.down[b]);
let (ab, ba, rep_b) = (up_a.test(b), up_b.test(a), idx.scc_rep[b]);
if ab && !ba {
if !up_b.is_subset(up_a) || !down_a.is_subset(down_b) { return false; }
continue;
}
if ba && !ab {
if !up_a.is_subset(up_b) || !down_b.is_subset(down_a) { return false; }
continue;
}
if ab && ba && (rep_a != rep_b || up_a != up_b || down_a != down_b) { return false; }
let (jab, jba, mab, mba) = (idx.join_idx(a, b), idx.join_idx(b, a), idx.meet_idx(a, b), idx.meet_idx(b, a));
let cu = up_a.bitand(up_b);
if !cu.test(jab) || !cu.test(jba) || !cu.is_subset(&idx.up[jab]) || !cu.is_subset(&idx.up[jba]) { return false; }
let cd = down_a.bitand(down_b);
if !cd.test(mab) || !cd.test(mba) || !cd.is_subset(&idx.down[mab]) || !cd.is_subset(&idx.down[mba]) { return false; }
if idx.scc_rep[jab] != idx.scc_rep[jba] || idx.scc_rep[mab] != idx.scc_rep[mba] { return false; }
if idx.scc_rep[idx.join_idx(a, mab)] != rep_a || idx.scc_rep[idx.meet_idx(a, jab)] != rep_a { return false; }
if idx.scc_rep[idx.join_idx(b, mba)] != rep_b || idx.scc_rep[idx.meet_idx(b, jba)] != rep_b { return false; }
}
}
true
}
}
#[cfg(test)]
mod tests {
use super::*;
use super::super::MAX_FAST_LATTICE_K;
use crate::cpn::mcard_token::DEFAULT_TIMESTAMP;
#[test]
fn test_place_type_lattice_laws_and_multiword_fallback() {
let mk_p = |id: &str| PlaceMCard::create(id, "any", None, "Intermediate", Some("blake3"), Some(DEFAULT_TIMESTAMP)).unwrap();
let mk_t = |id: &str, u: &str, v: &str| {
TransitionMCard::create(id, vec![u.into()], vec![v.into()], "any", "any", None, "id", Some("blake3"), Some(DEFAULT_TIMESTAMP)).unwrap()
};
let places = vec![mk_p("a"), mk_p("b"), mk_p("u"), mk_p("v")];
let transitions = vec![mk_t("t_au", "a", "u"), mk_t("t_av", "a", "v"), mk_t("t_bu", "b", "u"), mk_t("t_bv", "b", "v")];
assert!(!PlaceTypeLattice::from_net_with_options(&places, &transitions, None, false).verify_lattice_laws());
let completed = PlaceTypeLattice::from_net(&places, &transitions, None);
assert!(completed.verify_lattice_laws());
assert_eq!(completed.join("a", "b"), "__dm_cut__a_b__to__u_v__");
assert_eq!(completed.meet("u", "v"), "__dm_cut__a_b__to__u_v__");
let mut big_p: Vec<PlaceMCard> = (0..260).map(|i| mk_p(&format!("c{i:03}"))).collect();
big_p.extend(["bw_a", "bw_b", "bw_u", "bw_v"].into_iter().map(mk_p));
let mut big_t: Vec<TransitionMCard> = (0..259).map(|i| mk_t(&format!("tc{i:03}"), &format!("c{i:03}"), &format!("c{:03}", i + 1))).collect();
big_t.extend([
mk_t("tb_ia", "c010", "bw_a"), mk_t("tb_ib", "c010", "bw_b"),
mk_t("tb_au", "bw_a", "bw_u"), mk_t("tb_av", "bw_a", "bw_v"),
mk_t("tb_bu", "bw_b", "bw_u"), mk_t("tb_bv", "bw_b", "bw_v"),
mk_t("tb_ou", "bw_u", "c250"), mk_t("tb_ov", "bw_v", "c250"),
]);
let big = PlaceTypeLattice::from_net(&big_p, &big_t, None);
assert!(big.reachability.len() > MAX_FAST_LATTICE_K);
assert!(big.verify_lattice_laws());
assert_eq!(big.join("bw_a", "bw_b"), "__dm_cut__bw_a_bw_b__to__bw_u_bw_v__");
}
}