Skip to content

World's first open-source enterprise world model.

59.8 KB
Raw Blame
//! 一致性检查:拿本体声明的公理去量已经落库的事实(见 `docs/decisions/0002` R0)。
//!
//! **不写 `facts` 表,也不碰数据库。** 这一层只做判断:输入是边与公理,输出是
//! 「哪几条事实互相矛盾」。取数与落库在 `utopia-store` / `utopia-server`。
//!
//! 这样分不是洁癖。ADR 说 R0 的价值在于「引擎的难点——规则表示、求值、终止——
//! 全部建成并验证,而风险面为零」,而那些难点是纯逻辑:不起数据库就能跑几百个
//! 用例,包括那些真实语料里未必凑得出来的形状(十一个节点的环、自环套在环里、
//! 同一对节点被两条不同谓词连着)。
//!
//! **没有公理就没有依据。** 四类检查每一类都由本体里的一位布尔决定要不要查,
//! 没声明就不查——不报矛盾比猜一个公理出来安全。所以一个没装本体包的库跑出来
//! 是零,那是实情不是故障。

pub mod derive;
pub mod expressions;
pub mod ontology;
pub mod rules;

use derive::TimedEdge;
use std::collections::hash_map::Entry;
use std::collections::{HashMap, HashSet};
use uuid::Uuid;

/// 一条参与检查的事实:谁、什么关系、指向谁。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Edge {
    pub fact: Uuid,
    pub predicate: Uuid,
    pub subject: Uuid,
    pub object: Uuid,
}

/// 一个谓词声明了哪些公理。四位都为假的谓词根本不进检查。
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct Axioms {
    pub transitive: bool,
    pub symmetric: bool,
    pub asymmetric: bool,
    pub irreflexive: bool,
    pub functional: bool,
    pub inverse_functional: bool,
    /// `p⁻¹ = q`:这个谓词的逆是哪一个。**跨谓词的规则从这里来**——
    /// `A p B` 推出 `B q A`,而 R0 的检查也要看它(自己是自己的逆等于对称)
    pub inverse_of: Option<Uuid>,
    /// `p ⊑ q`:断言了具体的,通用的也成立。链要防成环,R0 那边查
    pub sub_property_of: Option<Uuid>,
}

impl Axioms {
    /// 一位都没声明的谓词不必检查——**这是性能上的事,也是语义上的事**:
    /// 没有公理就没有判据,扫它只会白扫。
    fn says_nothing(&self) -> bool {
        *self == Axioms::default()
    }
}

/// 查出来的一处矛盾。落库在 `axiom_violations`——**不进 `fact_conflicts`**:
/// 那张表问的是「哪条对」,而公理违规问的是「错在数据还是错在定义」,
/// 后者的出路可能是去改本体。
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Violation {
    pub kind: Kind,
    /// 涉及的事实。**自反违反只有一条**——它跟自己矛盾,不需要第二条。
    /// 环取首尾两条(中间那些在 `path` 里);互斥的三类(asymmetry、functional、
    /// inverse_functional)取整组里 id 最小与最大的两条。
    pub left: Uuid,
    pub right: Uuid,
    /// 环的完整路径,按事实排列;互斥的三类是整组事实,按 id 排序;自环为空。
    /// 留着是因为「A→B→C→A」比「A 与 C 矛盾」有用得多——人要顺着看一遍才知道
    /// 该撤哪一条
    pub path: Vec<Uuid>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Kind {
    /// `A p A`,而 p 声明了 irreflexive
    SelfLoop,
    /// `A p B` 且 `B p A`,而 p 声明了 asymmetric
    Asymmetry,
    /// `A p B p … p A`,而 p 声明了 transitive——闭包里推出 `A p A`
    Cycle,
    /// 同一主语与谓词在同一段时间里指向两个宾语,而 p 声明了 functional
    Functional,
    /// 同一宾语在同一段时间里被两个主语指,而 p 声明了 inverse_functional。
    ///
    /// 与 `Functional` 分开记(#634):从前两个方向共用一个种类,一个项目同时有两位
    /// 负责人被写成「该只有一个值,却有两个」,人照着去主语那一侧找,找的是错的一端
    InverseFunctional,
    /// `A p B`,而 A 不在 p 声明的 domain 里、或 B 不在 range 里(#190 / #196)。
    ///
    /// **这一类不由本 crate 算出**:它要看实体的类型与 domain / range 的闭包,那是
    /// 库里的东西,`utopia-store::reasoning::signature_breaks` 用 SQL 量。列在这里
    /// 是为了与其它四类走同一条落库、清陈、裁决的路——left 与 right 同一条事实,
    /// 与自反那类同款
    Signature,
    /// 一条派生撞上了一条断言(0017):推出来的 `A p B` 与账本里的某条断言在 p 的
    /// 公理上不能并存。派生不落地,这一行把它摆到人面前。`left` 是被撞的断言,
    /// `right` 是派生的最后一条前提,`path` 是全部前提;推出来的三元组本身在
    /// `axiom_violations.detail` 里——它没有落库,没有 id 可指
    DerivedContradiction,
}

impl Kind {
    pub fn as_str(self) -> &'static str {
        match self {
            Kind::SelfLoop => "self_loop",
            Kind::Asymmetry => "asymmetry",
            Kind::Cycle => "cycle",
            Kind::Functional => "functional",
            Kind::InverseFunctional => "inverse_functional",
            Kind::Signature => "signature",
            Kind::DerivedContradiction => "derived_contradiction",
        }
    }
}

/// 环检测的深度上限。
///
/// **必须有,不是防御性编程。** 0002 在真实语料上量过:`part_of` 的传递闭包
/// 从 185 条膨胀到 828 条且**不收敛**——深度分布 `1:185 2:181 3:141 4:45
/// 5:52 6:40 7:52 8:40 9:52 10:40`,第 5 层起振荡而不是衰减,那是有环的形状。
/// 没有上限,一个环就能让求值不终止。
pub const MAX_DEPTH: usize = 12;

/// 一个谓词上最多报多少个环(#642)。
///
/// 上千个环不是上千件事:它们挤在同一团互相可达的节点里,根子多半是这个谓词不该
/// 声明 transitive,或者有一两条边方向写反了。逐个端进 Review 只会淹掉队列,与
/// `MAX_CLASHES_PER_PREDICATE` 同一个道理
pub const MAX_CYCLES_PER_PREDICATE: usize = 1000;

/// 一个谓词上找环最多走多少步(每看一条边算一步,#642)。
///
/// **环数上限管不住工作量。** 一团稠密的强连通分量里,深度 12 以内的简单路径是
/// 指数级的,大多数根本不回到起点——步数没有上限,一次检查就能把请求挂住、把内存
/// 撑满。量过:500 个节点、2000 条边、两成随机回边,从前 60 秒没跑完。
pub const MAX_CYCLE_STEPS: usize = 1_000_000;

/// 一次检查的完整结果:违规,以及哪些谓词的环没搜完。
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Checked {
    pub violations: Vec<Violation>,
    /// 撞上 `MAX_CYCLES_PER_PREDICATE` 或 `MAX_CYCLE_STEPS`、环没搜完的谓词,排过序。
    /// **必须回给调用方**:没搜完不能说没有——落库那边据此不清这些谓词上旧的环,
    /// 界面据此说「这个谓词的环太多,先看公理」
    pub cycles_capped: Vec<Uuid>,
}

/// 拿公理量一遍这批边。
///
/// 每个谓词各查各的:公理是挂在谓词上的,跨谓词的边之间没有可比性
/// (`A part_of B` 与 `B produces A` 同时成立不是矛盾)。
///
/// **互斥的三类要求两条事实同时成立**(#634)。functional、inverse_functional、
/// asymmetric 说的都是「同一时刻」:Lin Zhao 的薪水在 2024-02-20 从 28000 变成
/// 32000,两段首尾相接,那是一次调薪。从前这里只收 `Edge`,区间在调用方就丢了,
/// 于是每一次接任都进了 Review。判据与 `derive::contradictions` 同一个——派生那一侧
/// 一直是按区间重叠判的,断言这一侧跟它对齐。
///
/// **环要整条路径在同一时刻成立**(#636)。A 在 2019–2021 年并入 B、2022 年起 B
/// 又并入 A,图在任何一刻都没有这个环;两两重叠也不够,三条边可以两两相交而三者
/// 无交。所以沿路径求交集,与 `derive::validity` 对前提做的是同一件事。
///
/// 区间照 `TimedEdge` 的读法:半开 `[from, to)`,`None` 是那一侧无界(恒常谓词两端
/// 都是 `None`,于是退回到只看形状)。自环不看时间:`A p A` 哪一刻成立都是错的。
pub fn check(edges: &[TimedEdge], axioms: &HashMap<Uuid, Axioms>) -> Vec<Violation> {
    check_all(edges, axioms).violations
}

/// 同 [`check`],另外说出哪些谓词的环没搜完(#642)。
pub fn check_all(edges: &[TimedEdge], axioms: &HashMap<Uuid, Axioms>) -> Checked {
    let mut out = Vec::new();
    let mut cycles_capped = Vec::new();
    let mut by_pred: HashMap<Uuid, Vec<TimedEdge>> = HashMap::new();
    for t in edges {
        let Some(ax) = axioms.get(&t.edge.predicate) else {
            continue;
        };
        if ax.says_nothing() {
            continue;
        }
        by_pred.entry(t.edge.predicate).or_default().push(*t);
    }
    for (pred, group) in by_pred {
        let ax = axioms[&pred];
        let shapes: Vec<Edge> = group.iter().map(|t| t.edge).collect();
        if ax.irreflexive {
            out.extend(self_loops(&shapes));
        }
        if ax.asymmetric {
            out.extend(asymmetries(&group));
        }
        if ax.transitive {
            let (found, capped) = cycles(&group);
            out.extend(found);
            if capped {
                cycles_capped.push(pred);
            }
        }
        if ax.functional {
            out.extend(clashes(
                &group,
                Kind::Functional,
                |e| (e.subject, Uuid::nil()),
                |a, b| a.object != b.object,
            ));
        }
        if ax.inverse_functional {
            out.extend(clashes(
                &group,
                Kind::InverseFunctional,
                |e| (e.object, Uuid::nil()),
                |a, b| a.subject != b.subject,
            ));
        }
    }
    cycles_capped.sort();
    Checked {
        violations: out,
        cycles_capped,
    }
}

fn self_loops(edges: &[Edge]) -> Vec<Violation> {
    edges
        .iter()
        .filter(|e| e.subject == e.object)
        .map(|e| Violation {
            kind: Kind::SelfLoop,
            // 两列填同一条:它跟自己矛盾,没有第二条事实可指
            left: e.fact,
            right: e.fact,
            path: Vec::new(),
        })
        .collect()
}

/// 反对称:同一对节点在同一段时间里两个方向都断言了。
///
/// 键是无序的那一对节点,「不同」是方向相反——与 functional 同一个形状,所以走
/// 同一个函数。
fn asymmetries(edges: &[TimedEdge]) -> Vec<Violation> {
    // 自环由 irreflexive 那一档负责;反对称在这里报一遍是重复
    let two_way: Vec<TimedEdge> = edges
        .iter()
        .filter(|t| t.edge.subject != t.edge.object)
        .copied()
        .collect();
    clashes(
        &two_way,
        Kind::Asymmetry,
        |e| (e.subject.min(e.object), e.subject.max(e.object)),
        |a, b| a.subject != b.subject,
    )
}

/// 找环。**每个环只报一次,而且只以一种形状报**:报出来的路径转到最小的那条事实
/// 起头(见 `walk` 里的注释)。
///
/// 用深度优先而不是半朴素闭包求值:两者都能发现环,但闭包只告诉你「A 推出了
/// A」,而人要的是**路径**——顺着 `A→B→C→A` 看一遍才知道该撤哪一条。闭包丢掉
/// 的正是这个。
///
/// **只在强连通分量里找,每个环只从它最小的节点找一次**(#642)。从前从每个节点出发
/// 把深度 12 以内的路径全走一遍,再按事实集合去重。环只可能落在一个强连通分量里,
/// 而真实的 `part_of` 大体是一棵层级、只有几条回边:分量很小,绝大多数路径一路往下
/// 走进 DAG、永远回不来。量过:一个宽 4、14 层的层级加一条回边(209 条边、256 个环)
/// 从前要 10 秒,2 万个节点的层级要 8 秒。先算分量、只走分量内的边,这些路径一步都
/// 不走;再规定环只从它编号最小的节点出发、途中只经过比起点大的节点,每个环恰好被
/// 走到一次,去重的集合也省了。
///
/// 真正稠密的大分量里环本身就是指数级的,这两条救不了——那时撞上
/// `MAX_CYCLES_PER_PREDICATE` / `MAX_CYCLE_STEPS` 就停,第二个返回值为真。起点与每个
/// 节点的出边都排过序,所以停在哪儿只取决于数据:同一份数据跑多少遍、以什么顺序
/// 读进来,报出来的都是同一批环。
///
/// R1 物化推导要的是闭包本身,那时再建;R0 要的是「哪几条边凑成了环」。
fn cycles(edges: &[TimedEdge]) -> (Vec<Violation>, bool) {
    // 自环不是这里的事(irreflexive 那一档管),也不可能在两个以上节点的环上
    let mut next: HashMap<Uuid, Vec<Uuid>> = HashMap::new();
    for t in edges.iter().filter(|t| t.edge.subject != t.edge.object) {
        next.entry(t.edge.subject).or_default().push(t.edge.object);
    }
    let mut nodes: Vec<Uuid> = next.keys().copied().collect();
    nodes.sort_unstable();
    let component = components(&nodes, &next);

    // 分量内的边才可能在环上;出边按 (宾语, 事实) 排,遍历顺序只取决于数据
    let mut adj: HashMap<Uuid, Vec<&TimedEdge>> = HashMap::new();
    for t in edges {
        let (s, o) = (t.edge.subject, t.edge.object);
        let same = matches!((component.get(&s), component.get(&o)), (Some(a), Some(b)) if a == b);
        if s != o && same {
            adj.entry(s).or_default().push(t);
        }
    }
    for out in adj.values_mut() {
        out.sort_unstable_by_key(|t| (t.edge.object, t.edge.fact));
    }
    let mut starts: Vec<Uuid> = adj.keys().copied().collect();
    starts.sort_unstable();

    let mut search = Search {
        adj: &adj,
        path: Vec::new(),
        on_path: HashSet::new(),
        out: Vec::new(),
        steps: 0,
        capped: false,
    };
    for start in starts {
        search.walk(start, start, (None, None));
        if search.capped {
            break;
        }
    }
    (search.out, search.capped)
}

/// 强连通分量:每个节点所在分量的编号。
///
/// Tarjan,**迭代版**:递归版的调用深度等于最长的那条链,几万个节点的层级在它面前
/// 就是几万层递归,栈会炸。这里自己维护调用栈 `(节点, 下一个要看的后继)`。
fn components(nodes: &[Uuid], next: &HashMap<Uuid, Vec<Uuid>>) -> HashMap<Uuid, usize> {
    let mut index: HashMap<Uuid, usize> = HashMap::new();
    let mut low: HashMap<Uuid, usize> = HashMap::new();
    let mut on_stack: HashSet<Uuid> = HashSet::new();
    let mut stack: Vec<Uuid> = Vec::new();
    let mut component: HashMap<Uuid, usize> = HashMap::new();
    let (mut counter, mut count) = (0usize, 0usize);
    for &root in nodes {
        let Entry::Vacant(slot) = index.entry(root) else {
            continue;
        };
        slot.insert(counter);
        low.insert(root, counter);
        counter += 1;
        stack.push(root);
        on_stack.insert(root);
        let mut calls: Vec<(Uuid, usize)> = vec![(root, 0)];
        while let Some(&(v, i)) = calls.last() {
            let succ = next.get(&v).map(Vec::as_slice).unwrap_or(&[]);
            if let Some(&w) = succ.get(i) {
                if let Some(frame) = calls.last_mut() {
                    frame.1 += 1;
                }
                if let Entry::Vacant(slot) = index.entry(w) {
                    slot.insert(counter);
                    low.insert(w, counter);
                    counter += 1;
                    stack.push(w);
                    on_stack.insert(w);
                    calls.push((w, 0));
                } else if on_stack.contains(&w) {
                    let lw = index[&w];
                    if let Some(lv) = low.get_mut(&v) {
                        *lv = (*lv).min(lw);
                    }
                }
                continue;
            }
            calls.pop();
            let lv = low[&v];
            if let Some(&(parent, _)) = calls.last() {
                if let Some(lp) = low.get_mut(&parent) {
                    *lp = (*lp).min(lv);
                }
            }
            if lv == index[&v] {
                while let Some(w) = stack.pop() {
                    on_stack.remove(&w);
                    component.insert(w, count);
                    if w == v {
                        break;
                    }
                }
                count += 1;
            }
        }
    }
    component
}

/// 一次找环的状态:当前路径、找到的环、走了多少步、是否撞上了上限。
struct Search<'a> {
    adj: &'a HashMap<Uuid, Vec<&'a TimedEdge>>,
    path: Vec<&'a TimedEdge>,
    on_path: HashSet<Uuid>,
    out: Vec<Violation>,
    steps: usize,
    capped: bool,
}

impl<'a> Search<'a> {
    /// 从 `at` 往下走。`span` 是路径上已走过的边的区间交集;起点是全时间
    fn walk(&mut self, start: Uuid, at: Uuid, span: (Option<i64>, Option<i64>)) {
        if self.path.len() >= MAX_DEPTH || self.capped {
            return;
        }
        let adj = self.adj;
        let Some(next) = adj.get(&at) else { return };
        for &t in next {
            self.steps += 1;
            if self.steps > MAX_CYCLE_STEPS || self.out.len() >= MAX_CYCLES_PER_PREDICATE {
                self.capped = true;
                return;
            }
            let e = &t.edge;
            // 只经过比起点大的节点:每个环只在从它最小的节点出发时被走到,恰好一次。
            // 出边按宾语排过序,这里本可以二分跳过,但出边通常只有几条
            if e.object < start {
                continue;
            }
            // 接上这条边,路径就没有哪一刻是整条成立的:不管是成环还是往下走,都不必了。
            // 没日期的事件区间为空(0031),在这里自然被剪掉
            let Some(span) = derive::overlap(span, (t.from, t.to)) else {
                continue;
            };
            if e.object == start {
                if self.path.is_empty() {
                    continue;
                }
                let mut facts: Vec<Uuid> = self.path.iter().map(|x| x.edge.fact).collect();
                facts.push(e.fact);
                // **报之前把环转到规范位置。**环是一个圈,从哪条边开始读都是同一个环;
                // 而 `axiom_violations` 里环是按整条 `path` 唯一的(0054):换一种旋转
                // 就是换一行。后果不是"多一行",是**人的裁决会悄悄失效**:重算删掉的是
                // open 的行,裁过的那行留着,同一个环以新键插成 open,重开那一支匹配
                // 不上就不会触发(#618)。起点是最小的节点,却未必是最小的事实——转到
                // 最小的事实 id 起头,键就成了环自己的函数
                let at = facts
                    .iter()
                    .enumerate()
                    .min_by_key(|(_, f)| **f)
                    .map(|(i, _)| i)
                    .unwrap();
                facts.rotate_left(at);
                self.out.push(Violation {
                    kind: Kind::Cycle,
                    left: facts[0],
                    right: *facts.last().unwrap(),
                    path: facts,
                });
                continue;
            }
            if self.on_path.contains(&e.object) {
                continue;
            }
            self.on_path.insert(e.object);
            self.path.push(t);
            self.walk(start, e.object, span);
            self.path.pop();
            self.on_path.remove(&e.object);
            if self.capped {
                return;
            }
        }
    }
}

/// 互斥:同一个键下,两条「不同」的事实同时成立。
///
/// functional(键是主语,不同是宾语不同)、inverse_functional(键是宾语,不同是
/// 主语不同)、asymmetric(键是无序的一对节点,不同是方向相反)都是这个形状,
/// 调用方给键和「不同」。
///
/// **一组报一处。** 同一个主语同一段时间里指了五个宾语,是一件事;两两组合报十处
/// 只是把它说十遍。组是冲突关系的连通块:a 与 b 同时成立、b 与 c 同时成立,三条
/// 就是一组,哪怕 a 与 c 首尾相接。先后出现、互不重叠的两场冲突是两组。
///
/// **身份只由组里有哪些事实决定**(#624)。`axiom_violations` 按
/// `(kind, left_fact, right_fact)` 唯一;从前 left/right 取遇到的头两条,而遇到的
/// 顺序来自 HashMap 与取数顺序——同一处冲突换个顺序就是另一行,人裁过的那行被绕开,
/// 与 #618 的环是同一个病。现在 `path` 是排过序的整组,left/right 是它的首尾。
fn clashes(
    edges: &[TimedEdge],
    kind: Kind,
    key: fn(&Edge) -> (Uuid, Uuid),
    differ: fn(&Edge, &Edge) -> bool,
) -> Vec<Violation> {
    let mut by_key: HashMap<(Uuid, Uuid), Vec<&TimedEdge>> = HashMap::new();
    for t in edges {
        // 空区间(没有日期的事件,0031)哪一刻都不成立,跟谁都不同时
        if matches!((t.from, t.to), (Some(f), Some(to)) if f >= to) {
            continue;
        }
        by_key.entry(key(&t.edge)).or_default().push(t);
    }
    let mut out = Vec::new();
    for mut group in by_key.into_values() {
        if group.len() < 2 {
            continue;
        }
        // 按起点扫一遍,手里留着还没结束的:它们正是与这一条同时成立的。一长串前后
        // 相接的历史值(逐月的薪水)手里始终只有一两条,不会两两比一遍
        group.sort_by_key(|t| (t.from.unwrap_or(i64::MIN), t.edge.fact));
        let mut parent: Vec<usize> = (0..group.len()).collect();
        let mut clashed = vec![false; group.len()];
        let mut open: Vec<usize> = Vec::new();
        for i in 0..group.len() {
            let start = group[i].from.unwrap_or(i64::MIN);
            // 半开区间:终点正好是这一条起点的,已经结束了——首尾相接是接任
            open.retain(|&j| group[j].to.is_none_or(|to| to > start));
            for &j in &open {
                if differ(&group[i].edge, &group[j].edge) {
                    clashed[i] = true;
                    clashed[j] = true;
                    let (a, b) = (root(&mut parent, i), root(&mut parent, j));
                    parent[a] = b;
                }
            }
            open.push(i);
        }
        let mut blocks: HashMap<usize, Vec<Uuid>> = HashMap::new();
        for i in 0..group.len() {
            if clashed[i] {
                let r = root(&mut parent, i);
                blocks.entry(r).or_default().push(group[i].edge.fact);
            }
        }
        for mut facts in blocks.into_values() {
            facts.sort_unstable();
            facts.dedup();
            out.push(Violation {
                kind,
                left: facts[0],
                right: facts[facts.len() - 1],
                path: facts,
            });
        }
    }
    out
}

/// 并查集找根,顺手压缩路径
fn root(parent: &mut [usize], mut i: usize) -> usize {
    while parent[i] != i {
        parent[i] = parent[parent[i]];
        i = parent[i];
    }
    i
}

#[cfg(test)]
mod tests {
    use super::*;

    /// 造边的简写。节点用小整数编出稳定的 uuid,读断言时看得出谁是谁。
    fn n(i: u8) -> Uuid {
        Uuid::from_bytes([i; 16])
    }
    fn f(i: u8) -> Uuid {
        // 与节点 id 分段:节点用低位,事实用高位。`u8` 装得下 0..=255,
        // 而测试里造过 30 条边的链——用 `200 + i` 会溢出
        Uuid::from_bytes([i; 16].map(|b| b ^ 0xF0))
    }
    fn e(fact: u8, s: u8, o: u8) -> Edge {
        Edge {
            fact: f(fact),
            predicate: n(99),
            subject: n(s),
            object: n(o),
        }
    }
    fn with(ax: Axioms) -> HashMap<Uuid, Axioms> {
        HashMap::from([(n(99), ax)])
    }
    /// 不带时间地查:两端都无界,任意两条都同时成立,检查只剩形状。大部分用例问的
    /// 就是形状;问时间的用例用 `at` 造边,直接调 `super::check`
    fn check(edges: &[Edge], axioms: &HashMap<Uuid, Axioms>) -> Vec<Violation> {
        let timed: Vec<TimedEdge> = edges
            .iter()
            .map(|&edge| TimedEdge {
                edge,
                from: None,
                to: None,
            })
            .collect();
        super::check(&timed, axioms)
    }
    /// 带区间的边,`[from, to)`
    fn at(fact: u8, s: u8, o: u8, from: Option<i64>, to: Option<i64>) -> TimedEdge {
        TimedEdge {
            edge: e(fact, s, o),
            from,
            to,
        }
    }
    /// 输入的全排列。顺序是这一类 bug 的全部来源,所以每种顺序都要跑到
    fn permutations<T: Copy>(items: &[T]) -> Vec<Vec<T>> {
        if items.len() <= 1 {
            return vec![items.to_vec()];
        }
        let mut out = Vec::new();
        for i in 0..items.len() {
            let mut rest = items.to_vec();
            let head = rest.remove(i);
            for mut tail in permutations(&rest) {
                tail.insert(0, head);
                out.push(tail);
            }
        }
        out
    }
    /// 一次检查的结果,排成与顺序无关的形状,好拿来比
    fn shape(v: Vec<Violation>) -> Vec<(&'static str, Uuid, Uuid, Vec<Uuid>)> {
        let mut out: Vec<_> = v
            .into_iter()
            .map(|x| (x.kind.as_str(), x.left, x.right, x.path))
            .collect();
        out.sort();
        out
    }
    fn kinds(v: &[Violation]) -> Vec<Kind> {
        let mut k: Vec<Kind> = v.iter().map(|x| x.kind).collect();
        k.sort_by_key(|x| x.as_str());
        k
    }

    /// **同一个环,每次都是同一行。**环的 `left`/`right` 从前取这一次遍历的首尾,
    /// 而起点来自 HashMap 的迭代顺序——同一份输入跑两次可以给出不同的旋转,而
    /// `axiom_violations` 按 `(kind, left_fact, right_fact)` 唯一,换个旋转就是换一行,
    /// 人裁过的那一行于是被绕开(#618)。
    ///
    /// 跑一百次而不是一次:顺序是随机的,一次跑不出问题来。
    #[test]
    fn a_cycle_is_reported_the_same_way_every_time() {
        let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 3, 1)];
        let ax = with(Axioms {
            transitive: true,
            ..Default::default()
        });
        let shapes: std::collections::HashSet<(Uuid, Uuid, Vec<Uuid>)> = (0..100)
            .map(|_| {
                let v: Vec<Violation> = check(&edges, &ax)
                    .into_iter()
                    .filter(|v| v.kind == Kind::Cycle)
                    .collect();
                assert_eq!(v.len(), 1, "一个环只报一次");
                (v[0].left, v[0].right, v[0].path.clone())
            })
            .collect();
        assert_eq!(shapes.len(), 1, "同一个环给出了不止一种形状: {shapes:?}");
        // 规范形状是从最小的事实起头,路径仍然是一圈
        let (left, right, path) = shapes.into_iter().next().unwrap();
        assert_eq!(left, *path.iter().min().unwrap());
        assert_eq!(left, path[0]);
        assert_eq!(right, *path.last().unwrap());
        assert_eq!(path.len(), 3);
    }

    /// **共用首尾两条边的两个环是两个环**(#641)。A→B 起头、X→A 收尾,中间一条走 C、
    /// 一条走 D:两个环的 left 都是 A→B、right 都是 X→A。从前库里按这两列定键,一个
    /// 覆盖另一个;这里钉的是检查器给出的就是两个、路径不同——落库那边按整条 path 定键
    #[test]
    fn two_cycles_sharing_their_ends_are_two_cycles() {
        let edges = [
            e(1, 1, 2),
            e(2, 2, 3),
            e(3, 2, 4),
            e(4, 3, 5),
            e(5, 4, 5),
            e(6, 5, 1),
        ];
        let v: Vec<Violation> = check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            }),
        )
        .into_iter()
        .filter(|v| v.kind == Kind::Cycle)
        .collect();
        let paths: HashSet<Vec<Uuid>> = v.iter().map(|c| c.path.clone()).collect();
        assert_eq!(
            paths,
            HashSet::from([vec![f(1), f(2), f(4), f(6)], vec![f(1), f(3), f(5), f(6)]])
        );
        assert!(v.iter().all(|c| (c.left, c.right) == (f(1), f(6))));
    }

    /// **层级里的一条回边,不让找环走遍整个层级**(#642)。宽 4、14 层的层级 DAG,
    /// 第 5 层一条边回到第 0 层:环只有 256 个(第 0 层那个点经四层每层四选一到第 5 层
    /// 那个点),全在前六层;而从前从每个节点出发把深度 12 以内的路径都走一遍,光一个
    /// 起点就有 4^12 条,10 秒。只在强连通分量里找,那几万条路一步都不走——这里断言
    /// 的是结果完整、没有撞上步数上限:若分量剪枝失效,这张图必然撞上
    #[test]
    fn a_back_edge_in_a_hierarchy_does_not_walk_the_hierarchy() {
        let (width, layers) = (4u16, 14u16);
        let node = |l: u16, x: u16| Uuid::from_u64_pair(0, (l * width + x) as u64);
        let mut edges = Vec::new();
        let mut fact = 0u64;
        let mut push = |s: Uuid, o: Uuid, edges: &mut Vec<TimedEdge>| {
            fact += 1;
            edges.push(TimedEdge {
                edge: Edge {
                    fact: Uuid::from_u64_pair(1, fact),
                    predicate: n(99),
                    subject: s,
                    object: o,
                },
                from: None,
                to: None,
            });
        };
        for l in 0..layers - 1 {
            for x in 0..width {
                for y in 0..width {
                    push(node(l, x), node(l + 1, y), &mut edges);
                }
            }
        }
        push(node(5, 0), node(0, 0), &mut edges);
        let checked = super::check_all(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            }),
        );
        assert!(checked.cycles_capped.is_empty(), "不该撞上上限");
        let cycles = checked
            .violations
            .iter()
            .filter(|v| v.kind == Kind::Cycle)
            .count();
        assert_eq!(
            cycles,
            4usize.pow(4),
            "第 0 层那个点经四层、每层四选一到第 5 层那个点"
        );
    }

    /// **稠密的分量里撞上上限就停,并且说出来**(#642);停下时报出的那一批环只取决于
    /// 数据,与读进来的顺序无关——否则同一份数据每跑一遍 Review 里就换一批环。
    #[test]
    fn a_dense_loop_stops_at_the_cap_and_says_so() {
        // 12 个节点两两互指:深度 12 以内的简单环是天文数字
        let mut edges = Vec::new();
        let mut fact = 0u8;
        for s in 1..=12u8 {
            for o in 1..=12u8 {
                if s != o {
                    fact += 1;
                    edges.push(TimedEdge {
                        edge: e(fact, s, o),
                        from: None,
                        to: None,
                    });
                }
            }
        }
        let ax = with(Axioms {
            transitive: true,
            ..Default::default()
        });
        let first = super::check_all(&edges, &ax);
        assert_eq!(first.cycles_capped, vec![n(99)]);
        let cycles = first
            .violations
            .iter()
            .filter(|v| v.kind == Kind::Cycle)
            .count();
        assert!(cycles <= MAX_CYCLES_PER_PREDICATE, "报出 {cycles} 个");
        assert!(cycles > 0, "撞上上限之前找到的照报");

        let mut rng = Rng(0x0642);
        for _ in 0..5 {
            let again = super::check_all(&shuffled(&mut rng, &edges), &ax);
            assert_eq!(again.cycles_capped, first.cycles_capped);
            assert_eq!(
                shape(again.violations),
                shape(first.violations.clone()),
                "撞上上限时报出的那一批环随输入顺序变了"
            );
        }
    }

    /// **没声明公理的谓词一条都不查。** 这是整套检查的地基:没有依据就不报矛盾。
    ///
    /// 反过来说也成立——一个没装本体包的库跑出来是零,那是实情不是故障。
    #[test]
    fn a_predicate_that_declares_nothing_is_never_checked() {
        let edges = [e(1, 1, 1), e(2, 1, 2), e(3, 2, 1)];
        assert!(check(&edges, &with(Axioms::default())).is_empty());
        // 连 axioms 里都没有这个谓词时同样不查(本体里没有这一行)
        assert!(check(&edges, &HashMap::new()).is_empty());
    }

    #[test]
    fn a_self_loop_needs_irreflexive_to_be_a_problem() {
        let edges = [e(1, 1, 1)];
        assert!(check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            })
        )
        .is_empty());
        let v = check(
            &edges,
            &with(Axioms {
                irreflexive: true,
                ..Default::default()
            }),
        );
        assert_eq!(kinds(&v), vec![Kind::SelfLoop]);
        // 只有一条事实:两列填同一个 id
        assert_eq!(v[0].left, v[0].right);
    }

    /// 反对称那一档**不重复报自环**。`A p A` 同时满足「有反向边」的字面意思,
    /// 不挡掉的话一条自环会在两档里各报一次,人看到两条要处理的东西而其实是一件。
    #[test]
    fn a_self_loop_is_reported_once_not_twice() {
        let edges = [e(1, 1, 1)];
        let v = check(
            &edges,
            &with(Axioms {
                irreflexive: true,
                asymmetric: true,
                ..Default::default()
            }),
        );
        assert_eq!(kinds(&v), vec![Kind::SelfLoop]);
    }

    #[test]
    fn a_pair_pointing_both_ways_needs_asymmetric() {
        let edges = [e(1, 1, 2), e(2, 2, 1)];
        assert!(check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            })
        )
        .iter()
        .all(|v| v.kind != Kind::Asymmetry));
        let v = check(
            &edges,
            &with(Axioms {
                asymmetric: true,
                ..Default::default()
            }),
        );
        assert_eq!(kinds(&v), vec![Kind::Asymmetry]);
        assert_eq!((v[0].left, v[0].right), (f(1), f(2)));
    }

    /// 长环要报出**路径**,而不只是「首尾矛盾」——人要顺着看一遍才知道撤哪一条。
    #[test]
    fn a_long_cycle_reports_the_whole_path() {
        let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 3, 4), e(4, 4, 1)];
        let v = check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            }),
        );
        assert_eq!(v.len(), 1, "一个环只报一次");
        assert_eq!(v[0].path.len(), 4, "四条边都该在路径里");
    }

    /// **同一个环从不同节点出发会被走到 n 次。** 去重是这个函数存在的一半理由:
    /// 报四遍就是让人把同一件事看四遍。
    #[test]
    fn one_cycle_is_one_finding_however_many_ways_in() {
        let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 3, 1)];
        let v = check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            }),
        );
        assert_eq!(v.len(), 1);
    }

    /// 两个互不相干的环各报一次。
    #[test]
    fn separate_cycles_stay_separate() {
        let edges = [e(1, 1, 2), e(2, 2, 1), e(3, 5, 6), e(4, 6, 5)];
        let v = check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            }),
        );
        assert_eq!(v.len(), 2);
    }

    /// **深度上限挡得住不收敛。** 0002 在真实语料上量到 `part_of` 闭包深度到 10
    /// 仍在振荡;没有上限,一条长链加一个环就能让求值不终止。
    ///
    /// 这里造一条比上限更长的链再闭合——它不该让检查挂住,报不报得出那个环是
    /// 次要的,**不挂住是首要的**。
    #[test]
    fn a_chain_longer_than_the_limit_still_terminates() {
        let mut edges: Vec<Edge> = (0..30).map(|i| e(i, i, i + 1)).collect();
        edges.push(e(60, 30, 0));
        let v = check(
            &edges,
            &with(Axioms {
                transitive: true,
                ..Default::default()
            }),
        );
        // 断言的是"跑完了",长度不作要求
        assert!(v.len() <= 1);
    }

    #[test]
    fn functional_and_its_inverse_are_two_directions_of_one_check() {
        // 同一个主语指了两个宾语
        let out = [e(1, 1, 2), e(2, 1, 3)];
        assert_eq!(
            kinds(&check(
                &out,
                &with(Axioms {
                    functional: true,
                    ..Default::default()
                })
            )),
            vec![Kind::Functional]
        );
        assert!(check(
            &out,
            &with(Axioms {
                inverse_functional: true,
                ..Default::default()
            })
        )
        .is_empty());

        // 同一个宾语被两个主语指:记成它自己的种类,不冒充 functional(#634)
        let inn = [e(1, 2, 1), e(2, 3, 1)];
        assert_eq!(
            kinds(&check(
                &inn,
                &with(Axioms {
                    inverse_functional: true,
                    ..Default::default()
                })
            )),
            vec![Kind::InverseFunctional]
        );
        assert!(check(
            &inn,
            &with(Axioms {
                functional: true,
                ..Default::default()
            })
        )
        .is_empty());
    }

    /// 同一个主语指五个宾语只报一处。报十处(两两组合)是把同一件事说十遍;
    /// 那一处带着全部五条,人撤哪条都有按钮。
    #[test]
    fn one_finding_per_conflicting_key_not_one_per_pair() {
        let edges = [e(1, 1, 2), e(2, 1, 3), e(3, 1, 4), e(4, 1, 5), e(5, 1, 6)];
        let v = check(
            &edges,
            &with(Axioms {
                functional: true,
                ..Default::default()
            }),
        );
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].path, vec![f(1), f(2), f(3), f(4), f(5)]);
        assert_eq!((v[0].left, v[0].right), (f(1), f(5)));
    }

    /// **一处冲突,不管以什么顺序读进来,都是同一行**(#624)。从前 left/right 取
    /// 遇到的头两条:三个值的六种顺序给出六种键,反对称两种顺序给出两种键——而
    /// `axiom_violations` 按键唯一,换个顺序,人裁过的那行就被绕开了。
    ///
    /// 跑全排列而不是跑一百次:顺序是这里唯一的变量,每一种都要到。
    #[test]
    fn the_same_clash_is_the_same_row_whatever_the_order() {
        let functional = with(Axioms {
            functional: true,
            ..Default::default()
        });
        let inverse = with(Axioms {
            inverse_functional: true,
            ..Default::default()
        });
        let asymmetric = with(Axioms {
            asymmetric: true,
            ..Default::default()
        });
        let cases: [(&[Edge], &HashMap<Uuid, Axioms>); 3] = [
            (&[e(1, 1, 2), e(2, 1, 3), e(3, 1, 4)], &functional),
            (&[e(1, 2, 1), e(2, 3, 1), e(3, 4, 1)], &inverse),
            (&[e(1, 1, 2), e(2, 2, 1), e(3, 1, 2)], &asymmetric),
        ];
        for (edges, ax) in cases {
            let shapes: HashSet<_> = permutations(edges)
                .iter()
                .map(|p| shape(check(p, ax)))
                .collect();
            assert_eq!(shapes.len(), 1, "顺序换出了不同的行: {shapes:?}");
            let only = shapes.into_iter().next().unwrap();
            assert_eq!(only.len(), 1);
            let (_, left, right, path) = &only[0];
            assert_eq!(path, &vec![f(1), f(2), f(3)], "整组,按 id 排序");
            assert_eq!((*left, *right), (f(1), f(3)), "首尾是最小与最大");
        }
    }

    /// **环要整条路径同一时刻成立**(#636)。A 在 2019–2021 年属于 B,2022 年起 B
    /// 属于 A:图在任何一刻都没有这个环。三元环更容易看走眼——三条边可以两两重叠,
    /// 三者却没有共同的一刻,这时逐对比较会误报,只有沿路径求交才对。
    #[test]
    fn a_cycle_must_hold_at_one_moment() {
        let transitive = with(Axioms {
            transitive: true,
            ..Default::default()
        });
        let cycles = |edges: &[TimedEdge]| -> Vec<Violation> {
            super::check(edges, &transitive)
                .into_iter()
                .filter(|v| v.kind == Kind::Cycle)
                .collect()
        };

        // 两条边一前一后
        let swapped = [
            at(1, 1, 2, Some(0), Some(100)),
            at(2, 2, 1, Some(100), None),
        ];
        assert!(cycles(&swapped).is_empty(), "前后相接的两段凑不成环");

        // 三条边两两重叠,三者无交:[0,100) ∩ [50,150) ∩ [100,200) = ∅
        let pairwise = [
            at(1, 1, 2, Some(0), Some(100)),
            at(2, 2, 3, Some(50), Some(150)),
            at(3, 3, 1, Some(100), Some(200)),
        ];
        assert!(cycles(&pairwise).is_empty(), "两两重叠不等于同时成立");

        // 三者共有 [90,100) 这一段:是环,而且照旧只报一次、规范形状
        let together = [
            at(1, 1, 2, Some(0), Some(100)),
            at(2, 2, 3, Some(50), Some(150)),
            at(3, 3, 1, Some(90), Some(200)),
        ];
        let v = cycles(&together);
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].path, vec![f(1), f(2), f(3)]);

        // 没日期的事件哪一刻都不成立,不进任何环
        let undated = [at(1, 1, 2, Some(50), Some(50)), at(2, 2, 1, None, None)];
        assert!(cycles(&undated).is_empty());
    }

    // ---------- 对拍:随机小图上,与暴力做法逐个比 ----------

    /// 确定性的伪随机数(xorshift64*)。对拍要可复现:挂了的那一张图,种子一样就能
    /// 原样再造出来;不为这个引依赖
    struct Rng(u64);
    impl Rng {
        fn next(&mut self) -> u64 {
            let mut x = self.0;
            x ^= x >> 12;
            x ^= x << 25;
            x ^= x >> 27;
            self.0 = x;
            x.wrapping_mul(0x2545_F491_4F6C_DD1D)
        }
        fn below(&mut self, n: u64) -> u64 {
            self.next() % n
        }
    }

    /// 一张随机小图:节点少、边多,平行边、自环、反向边都常见。端点落在 0..=60 的
    /// 十格上,于是首尾相接、完全重合、空区间(起点不早于终点)、无界都经常出现——
    /// 这些正是边界
    fn random_graph(rng: &mut Rng, nodes: u64, max_edges: u64) -> Vec<TimedEdge> {
        let count = rng.below(max_edges + 1) as u8;
        let bound = |rng: &mut Rng| {
            if rng.below(4) == 0 {
                None
            } else {
                Some(rng.below(7) as i64 * 10)
            }
        };
        (1..=count)
            .map(|i| {
                let (s, o) = (rng.below(nodes) as u8 + 1, rng.below(nodes) as u8 + 1);
                let (from, to) = (bound(rng), bound(rng));
                at(i, s, o, from, to)
            })
            .collect()
    }

    fn shuffled(rng: &mut Rng, edges: &[TimedEdge]) -> Vec<TimedEdge> {
        let mut v = edges.to_vec();
        for i in (1..v.len()).rev() {
            v.swap(i, rng.below(i as u64 + 1) as usize);
        }
        v
    }

    /// 暴力找环:从每个节点起,枚举所有节点不重复、至少两条边的回路,整条路径的
    /// 区间交集非空才算。不剪枝,不看遍历顺序,结果按事实集合收
    fn cycles_by_brute_force(edges: &[TimedEdge]) -> HashSet<Vec<Uuid>> {
        fn extend(
            edges: &[TimedEdge],
            start: Uuid,
            at: Uuid,
            path: &mut Vec<usize>,
            seen: &mut Vec<Uuid>,
            out: &mut HashSet<Vec<Uuid>>,
        ) {
            for (i, t) in edges.iter().enumerate() {
                if t.edge.subject != at {
                    continue;
                }
                if t.edge.object == start {
                    if path.is_empty() {
                        continue;
                    }
                    let mut all = path.clone();
                    all.push(i);
                    let holds = all.iter().try_fold((None, None), |acc, &j| {
                        derive::overlap(acc, (edges[j].from, edges[j].to))
                    });
                    if holds.is_some() {
                        let mut facts: Vec<Uuid> =
                            all.iter().map(|&j| edges[j].edge.fact).collect();
                        facts.sort();
                        out.insert(facts);
                    }
                    continue;
                }
                if seen.contains(&t.edge.object) {
                    continue;
                }
                seen.push(t.edge.object);
                path.push(i);
                extend(edges, start, t.edge.object, path, seen, out);
                path.pop();
                seen.pop();
            }
        }
        let mut out = HashSet::new();
        let starts: HashSet<Uuid> = edges.iter().map(|t| t.edge.subject).collect();
        for start in starts {
            extend(
                edges,
                start,
                start,
                &mut Vec::new(),
                &mut vec![start],
                &mut out,
            );
        }
        out
    }

    /// 暴力分组:两两比,同键、「不同」、区间有交就连一条,取连通块
    fn groups_by_brute_force(
        edges: &[TimedEdge],
        conflict: impl Fn(&Edge, &Edge) -> bool,
    ) -> HashSet<Vec<Uuid>> {
        let n = edges.len();
        let mut parent: Vec<usize> = (0..n).collect();
        let mut clashed = vec![false; n];
        for i in 0..n {
            for j in i + 1..n {
                let (a, b) = (&edges[i], &edges[j]);
                if conflict(&a.edge, &b.edge)
                    && derive::overlap((a.from, a.to), (b.from, b.to)).is_some()
                {
                    clashed[i] = true;
                    clashed[j] = true;
                    let (x, y) = (root(&mut parent, i), root(&mut parent, j));
                    parent[x] = y;
                }
            }
        }
        let mut blocks: HashMap<usize, Vec<Uuid>> = HashMap::new();
        for i in 0..n {
            if clashed[i] {
                let r = root(&mut parent, i);
                blocks.entry(r).or_default().push(edges[i].edge.fact);
            }
        }
        blocks
            .into_values()
            .map(|mut v| {
                v.sort();
                v
            })
            .collect()
    }

    fn found(v: &[Violation], kind: Kind) -> Vec<Vec<Uuid>> {
        v.iter()
            .filter(|x| x.kind == kind)
            .map(|x| {
                let mut facts = x.path.clone();
                facts.sort();
                facts
            })
            .collect()
    }

    /// **环:几千张随机小图上与暴力枚举逐个一致**(#636)。剪枝是个"证明了才敢做"的
    /// 优化——交集只会越求越窄,所以剪掉的分支凑不出真环。这里不信证明,信对拍:
    /// 带剪枝的深搜报出的环集合必须与不剪枝、整条求交的暴力枚举完全相同,一个不多
    /// 一个不少;每个环只报一次,报出来的形状是规范的(从最小事实起头、首尾对得上
    /// 路径、路径真的首尾相连);把输入打乱,输出逐字节不变。
    #[test]
    fn cycles_agree_with_brute_force_on_random_graphs() {
        let transitive = with(Axioms {
            transitive: true,
            ..Default::default()
        });
        let mut rng = Rng(0x0636_C0FF_EE00_0001);
        let (mut with_cycles, mut filtered_by_time) = (0, 0);
        for round in 0..6000 {
            let (nodes, max_edges) = if round % 2 == 0 { (3, 9) } else { (4, 12) };
            let edges = random_graph(&mut rng, nodes, max_edges);
            let v = super::check(&edges, &transitive);
            let got = found(&v, Kind::Cycle);
            let unique: HashSet<Vec<Uuid>> = got.iter().cloned().collect();
            assert_eq!(got.len(), unique.len(), "同一个环报了两次: {edges:?}");
            assert_eq!(
                unique,
                cycles_by_brute_force(&edges),
                "与暴力枚举不一致: {edges:?}"
            );
            if !unique.is_empty() {
                with_cycles += 1;
            }
            // 同一张图抹掉时间再暴力找一遍:形状上的环比带时间的多,说明这张图上
            // 时间真的起了作用——剪枝与求交走到了
            let timeless: Vec<TimedEdge> = edges
                .iter()
                .map(|t| TimedEdge {
                    from: None,
                    to: None,
                    ..*t
                })
                .collect();
            if cycles_by_brute_force(&timeless).len() > unique.len() {
                filtered_by_time += 1;
            }

            let by_fact: HashMap<Uuid, &TimedEdge> =
                edges.iter().map(|t| (t.edge.fact, t)).collect();
            for c in v.iter().filter(|x| x.kind == Kind::Cycle) {
                assert_eq!(c.left, *c.path.iter().min().unwrap(), "从最小的事实起头");
                assert_eq!((c.left, c.right), (c.path[0], *c.path.last().unwrap()));
                for w in 0..c.path.len() {
                    let here = by_fact[&c.path[w]].edge;
                    let next = by_fact[&c.path[(w + 1) % c.path.len()]].edge;
                    assert_eq!(here.object, next.subject, "路径要真的首尾相连: {c:?}");
                }
            }

            assert_eq!(
                shape(v),
                shape(super::check(&shuffled(&mut rng, &edges), &transitive)),
                "打乱输入换了输出: {edges:?}"
            );
        }
        // 对拍要真的碰到环才算数:随机图若几乎不成环,这个测试什么也没证明
        eprintln!("{with_cycles} 张图有环,{filtered_by_time} 张图上时间筛掉过环");
        assert!(with_cycles > 1000, "只有 {with_cycles} 张图有环,样本太稀");
        assert!(
            filtered_by_time > 1000,
            "只有 {filtered_by_time} 张图上时间筛掉过环,剪枝没怎么走到"
        );
    }

    /// **互斥三类:几千张随机小图上与两两比较的暴力分组逐个一致**(#634、#624)。
    /// 按起点扫一遍、手里只留还没结束的——这个扫描省掉了两两比较,也最容易在边界上
    /// 错:首尾相接、无界的起点、空区间、同一时刻开始的几条。暴力做法把每一对都比
    /// 一遍再取连通块,两边给出的组必须完全相同;打乱输入,输出逐字节不变。
    #[test]
    fn clashes_agree_with_brute_force_on_random_graphs() {
        let all = with(Axioms {
            asymmetric: true,
            functional: true,
            inverse_functional: true,
            ..Default::default()
        });
        let mut rng = Rng(0x0634_BEEF_0000_0002);
        let mut seen = [0usize; 3];
        for round in 0..4000 {
            let (nodes, max_edges) = if round % 2 == 0 { (2, 8) } else { (4, 12) };
            let edges = random_graph(&mut rng, nodes, max_edges);
            let v = super::check(&edges, &all);
            // 不捕获任何东西的闭包就是函数指针
            type Conflict = fn(&Edge, &Edge) -> bool;
            let cases: [(Kind, Conflict); 3] = [
                (Kind::Functional, |a, b| {
                    a.subject == b.subject && a.object != b.object
                }),
                (Kind::InverseFunctional, |a, b| {
                    a.object == b.object && a.subject != b.subject
                }),
                (Kind::Asymmetry, |a, b| {
                    a.subject != a.object && a.subject == b.object && a.object == b.subject
                }),
            ];
            for (k, (kind, conflict)) in cases.into_iter().enumerate() {
                let got = found(&v, kind);
                let unique: HashSet<Vec<Uuid>> = got.iter().cloned().collect();
                assert_eq!(
                    got.len(),
                    unique.len(),
                    "{kind:?} 同一组报了两次: {edges:?}"
                );
                assert_eq!(
                    unique,
                    groups_by_brute_force(&edges, conflict),
                    "{kind:?} 与暴力分组不一致: {edges:?}"
                );
                seen[k] += unique.len();
            }
            for x in v.iter().filter(|x| x.kind != Kind::Cycle) {
                let mut sorted = x.path.clone();
                sorted.sort();
                assert_eq!(x.path, sorted, "组按 id 排序");
                assert_eq!((x.left, x.right), (x.path[0], *x.path.last().unwrap()));
            }
            assert_eq!(
                shape(v),
                shape(super::check(&shuffled(&mut rng, &edges), &all)),
                "打乱输入换了输出: {edges:?}"
            );
        }
        assert!(seen.iter().all(|&n| n > 500), "有一类几乎没碰到: {seen:?}");
    }

    /// **剪枝丢不了真环。** 同一对节点之间有两条边,一条的区间让路径无交、另一条
    /// 不会:前一条被剪掉之后,后一条照样把环走出来。输入的每一种顺序都要到——
    /// 剪枝发生在遍历里,顺序决定先碰到哪一条。
    #[test]
    fn pruning_a_dead_branch_keeps_the_live_one() {
        let transitive = with(Axioms {
            transitive: true,
            ..Default::default()
        });
        let edges = [
            at(1, 1, 2, Some(0), Some(100)),
            // 与 1 无交:经过它的路径被剪掉
            at(2, 2, 3, Some(200), Some(300)),
            // 与 1 有交:环走这一条
            at(3, 2, 3, Some(50), Some(150)),
            at(4, 3, 1, Some(60), None),
        ];
        for order in permutations(&edges) {
            let v: Vec<Violation> = super::check(&order, &transitive)
                .into_iter()
                .filter(|v| v.kind == Kind::Cycle)
                .collect();
            assert_eq!(v.len(), 1, "{order:?}");
            assert_eq!(v[0].path, vec![f(1), f(3), f(4)]);
        }
    }

    /// **前后相接是接任,不是矛盾**(#634)。Lin Zhao 的薪水 `[2023-06, 2024-02)`
    /// 是 28000、`[2024-02, 现在)` 是 32000:一个人任何一刻都只有一份薪水。从前
    /// 检查不看时间,每次调薪都进 Review。重叠哪怕一秒,才是同时有两个值。
    #[test]
    fn a_succession_is_not_a_contradiction() {
        let functional = with(Axioms {
            functional: true,
            ..Default::default()
        });
        let (jun23, feb24) = (1_685_577_600, 1_708_387_200);

        let raise = [
            at(1, 1, 2, Some(jun23), Some(feb24)),
            at(2, 1, 3, Some(feb24), None),
        ];
        assert!(super::check(&raise, &functional).is_empty(), "首尾相接");

        let overlap = [
            at(1, 1, 2, Some(jun23), Some(feb24 + 1)),
            at(2, 1, 3, Some(feb24), None),
        ];
        assert_eq!(
            kinds(&super::check(&overlap, &functional)),
            vec![Kind::Functional]
        );

        // 宾语侧同理:一个项目换了负责人,中间还空了一年
        let handover = [
            at(1, 2, 9, Some(jun23), Some(feb24)),
            at(2, 3, 9, Some(feb24 + 31_536_000), None),
        ];
        let inverse = with(Axioms {
            inverse_functional: true,
            ..Default::default()
        });
        assert!(super::check(&handover, &inverse).is_empty());

        // 反对称同理:先是 A 管 B,后来 B 管 A
        let reversal = [
            at(1, 1, 2, Some(jun23), Some(feb24)),
            at(2, 2, 1, Some(feb24), None),
        ];
        let asymmetric = with(Axioms {
            asymmetric: true,
            ..Default::default()
        });
        assert!(super::check(&reversal, &asymmetric).is_empty());
    }

    /// 无界的那一侧跟谁都重叠:一条不知道从何时起、一直成立的事实,与任何一段
    /// 都同时成立。没有日期的事件区间为空(0031),哪一刻都不成立,跟谁都不冲突。
    #[test]
    fn an_unbounded_span_meets_everything_and_an_empty_one_meets_nothing() {
        let functional = with(Axioms {
            functional: true,
            ..Default::default()
        });
        let always = [at(1, 1, 2, None, None), at(2, 1, 3, Some(100), Some(200))];
        assert_eq!(
            kinds(&super::check(&always, &functional)),
            vec![Kind::Functional]
        );

        let undated_event = [
            at(1, 1, 2, Some(150), Some(150)),
            at(2, 1, 3, Some(100), Some(200)),
        ];
        assert!(super::check(&undated_event, &functional).is_empty());
    }

    /// **组是冲突的连通块。** a 与 b 重叠、b 与 c 重叠,a 与 c 首尾相接:三条是一组
    /// ——撤掉 b 两场冲突一起消失,分开报会让人以为是两件事。两场彼此隔开的冲突是两组。
    #[test]
    fn a_clash_is_a_connected_group_and_separate_clashes_stay_separate() {
        let functional = with(Axioms {
            functional: true,
            ..Default::default()
        });
        let chained = [
            at(1, 1, 2, Some(0), Some(100)),
            at(2, 1, 3, Some(50), Some(150)),
            at(3, 1, 4, Some(100), Some(200)),
        ];
        let v = super::check(&chained, &functional);
        assert_eq!(v.len(), 1);
        assert_eq!(v[0].path, vec![f(1), f(2), f(3)]);

        let apart = [
            at(1, 1, 2, Some(0), Some(100)),
            at(2, 1, 3, Some(50), Some(100)),
            at(3, 1, 4, Some(500), Some(600)),
            at(4, 1, 5, Some(550), Some(600)),
            // 与谁都不重叠的一条不进任何一组
            at(5, 1, 6, Some(300), Some(400)),
        ];
        let v = shape(super::check(&apart, &functional));
        assert_eq!(v.len(), 2);
        assert_eq!(v[0].3, vec![f(1), f(2)]);
        assert_eq!(v[1].3, vec![f(3), f(4)]);
    }

    /// 同一个主语两次指向**同一个**宾语不是冲突——重复断言而已。
    #[test]
    fn saying_the_same_thing_twice_is_not_a_contradiction() {
        let edges = [e(1, 1, 2), e(2, 1, 2)];
        assert!(check(
            &edges,
            &with(Axioms {
                functional: true,
                ..Default::default()
            })
        )
        .is_empty());
    }

    /// **公理挂在谓词上,跨谓词的边之间没有可比性。**
    /// `A p B` 与 `B q A` 同时成立不是矛盾,哪怕 p 声明了反对称。
    #[test]
    fn axioms_do_not_leak_across_predicates() {
        let a = Edge {
            fact: f(1),
            predicate: n(90),
            subject: n(1),
            object: n(2),
        };
        let b = Edge {
            fact: f(2),
            predicate: n(91),
            subject: n(2),
            object: n(1),
        };
        let ax = HashMap::from([
            (
                n(90),
                Axioms {
                    asymmetric: true,
                    ..Default::default()
                },
            ),
            (
                n(91),
                Axioms {
                    asymmetric: true,
                    ..Default::default()
                },
            ),
        ]);
        assert!(check(&[a, b], &ax).is_empty());
    }
}