World's first open-source enterprise world model.
Rust agent-memorybitemporalgraphragknowledge-baseknowledge-graphllmontologypgvectorpostgresqlragrustself-hostedsemantic-searchtemporal-knowledge-graphworld-model
//! R1:物化推导。**这一层会往图里加东西**,所以它的每一条约束都是必要的。
//!
//! 与 R0 的分水岭:R0 只指出问题,风险面为零;R1 写事实。ADR 0002 把这一步
//! 单列一档,并且给了三条硬性规矩,下面逐条落在代码里。
//!
//! **一、规则只从本体公理编译。** 没有用户自定义 DSL——那是另一个产品。
//! 今天能编译的只有 `TransitiveProperty` 与 `SymmetricProperty`:`inverseOf`
//! 与 `subPropertyOf` 投影侧还没落库,所以这里也就没有。**少一条规则不是
//! 缺陷,是「没声明就不推」的同一条**。
//!
//! **二、断言优先于派生,硬性。** 已经断言过的三元组不再派生一遍——不是为了
//! 省行数,是为了让「这条是谁说的」有唯一答案。
//!
//! **三、深度上限 + 环检测,实测必需。** ADR 在真实语料上量过:`part_of` 的
//! 传递闭包从 185 条膨胀到 828 条且**不收敛**,深度分布第 5 层起振荡而不是
//! 衰减——那是有环的形状。所以这里既不推自环(`A → A` 是矛盾不是知识,交给
//! R0 报),也在轮数上封顶。
//!
//! 还有一条 ADR 列在开放问题里、这里必须给出答案的:**有效时间取交集**。
//! 前提 A `[2020,2023)`、前提 B `[2022,∞)` → 派生 `[2022,2023)`。交集为空
//! 就不推——两段没有重叠的时候,链本身在任何时刻都不成立。
use crate::{Axioms, Edge, Kind, MAX_DEPTH};
use std::collections::{HashMap, HashSet};
use uuid::Uuid;
/// 单个谓词上派生的条数上限。
///
/// **不是防御性编程,是拿数量过的**:4.5 倍膨胀出现在一个 185 条边的谓词上,
/// 而膨胀是超线性的。封顶之后被截掉多少条要**说出来**(见 [`Derivation::capped`])
/// ——悄悄截断会让「推完了」和「推了一部分」长得一模一样。
pub const MAX_DERIVED_PER_PREDICATE: usize = 20_000;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Rule {
/// `A p B` ∧ `B p C` ⟹ `A p C`
Transitive,
/// `A p B` ⟹ `B p A`
Symmetric,
/// `A p B` ∧ `p⁻¹ = q` ⟹ `B q A`。**主宾对调且换谓词**——
/// 两件事一起发生,只做一件是这条规则最容易写错的地方
Inverse,
/// `A p B` ∧ `p ⊑ q` ⟹ `A q B`。主宾不动,只升谓词
SubProperty,
/// 一条业务规则推出的关系边(0047)。不是公理:`derive()` 从不产出它,
/// 它只作为**候选**进矛盾检查,让撞上断言或别的派生时能像公理派生一样被报出来。
/// 触发它的规则行在 `attribute_rules` 里,不在公理规则表里
Business,
}
impl Rule {
pub fn as_str(self) -> &'static str {
match self {
Rule::Transitive => "transitive",
Rule::Symmetric => "symmetric",
Rule::Inverse => "inverse",
Rule::SubProperty => "sub_property",
Rule::Business => "business_rule",
}
}
}
/// 一条要落地的派生事实,连同它的证明。
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Derived {
pub predicate: Uuid,
/// **哪个谓词的声明触发了它。**
///
/// 传递与对称不换谓词,`via == predicate`;而 `inverseOf` 与
/// `subPropertyOf` 换——`ceo_of ⊑ works_at` 推出的事实谓词是 `works_at`,
/// 而声明写在 `ceo_of` 上。
///
/// 落库时按 `via` 找规则行。**这里踩过一次**:原先按 `predicate` 找,
/// 前两条规则一直对(两者相同),加了跨谓词的两条之后查不到规则,
/// 于是 `continue` 静默丢弃——推出来了却不落库,最难查的那一种。
pub via: Uuid,
pub subject: Uuid,
pub object: Uuid,
pub rule: Rule,
/// 用到的前提,按推导顺序。**这是证明树的一层**——R2 展开解释时顺着它走,
/// 而前提失效时也靠它知道该让哪些派生跟着失效
pub premises: Vec<Uuid>,
}
/// 一次推导的产出。
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Derivation {
pub facts: Vec<Derived>,
/// 撞上上限、没推完的谓词。**必须回给调用方**:界面上要说得出
/// 「这个谓词太密,只推了两万条」,而不是让人以为推完了
pub capped: Vec<Uuid>,
}
/// 一条参与推导的边,比 [`Edge`] 多带有效期。
///
/// 单独一个类型而不是给 `Edge` 加字段:环与自环用不上时间,R0 的互斥三类要看
/// 两条是否同时成立(#634),R1 每一步都要算交集。
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct TimedEdge {
pub edge: Edge,
/// 半开区间 `[from, to)`。两端都可为空 = 不知道/一直
pub from: Option<i64>,
pub to: Option<i64>,
}
/// 交集。`None` 表示无界那一侧。
pub fn overlap(
a: (Option<i64>, Option<i64>),
b: (Option<i64>, Option<i64>),
) -> Option<(Option<i64>, Option<i64>)> {
let from = match (a.0, b.0) {
(Some(x), Some(y)) => Some(x.max(y)),
(Some(x), None) | (None, Some(x)) => Some(x),
(None, None) => None,
};
let to = match (a.1, b.1) {
(Some(x), Some(y)) => Some(x.min(y)),
(Some(x), None) | (None, Some(x)) => Some(x),
(None, None) => None,
};
// 空交集不推。两段没有重叠时,这条链在任何时刻都不成立——推出来的是一条
// 从不为真的事实,比不推更糟
if let (Some(f), Some(t)) = (from, to) {
if f >= t {
return None;
}
}
Some((from, to))
}
/// 邻接表里的一条边:(另一端, 起, 止, 支撑它的事实 id 列表)。
///
/// 第四项是**列表**而不是单个 id:这一项也会装进派生出来的边,而派生的证明可以
/// 有好几条前提。只留第一条的话,传递再接一条派生边时,证明就短了——链上少一条
/// 前提,而 `validity` 只对留下来的那几条求交集,于是结论的有效期比实际宽。
type Hop = (Uuid, Option<i64>, Option<i64>, Vec<Uuid>);
/// 半开区间 `[from, to)`,两端可空。
type Span = (Option<i64>, Option<i64>);
/// 派生的中间态:一个 (主语, 宾语) 对是怎么来的。
#[derive(Clone)]
struct Reached {
from: Option<i64>,
to: Option<i64>,
premises: Vec<Uuid>,
}
/// 一条三元组的身份:(谓词, 主语, 宾语)。
///
/// **谓词进了 key,这是这一版最要紧的改动。** 从前推导按谓词分组、组内自成一体,
/// 因为传递与对称都不换谓词;而 `inverseOf` 与 `subPropertyOf` 天生跨谓词——
/// `A works_at B` 推出的是 `B employs A`,落在另一个谓词上。分组一做,这两条
/// 规则就无处安放。
type Triple = (Uuid, Uuid, Uuid);
// 同一个 triple 可以有几段互不包含的有效期;被更宽区间完全覆盖的那段不再另留一份。
/// 拿公理推一遍这批边。
///
/// **全局不动点,不再按谓词分组。** 三条规则会串起来:
///
/// ```text
/// A ceo_of B --(subPropertyOf)--> A works_at B --(inverseOf)--> B employs A
/// ```
///
/// 各谓词各算各的话,这条链在第一步就断了。所以改成半朴素求值扫全集:每一轮拿上
/// 一轮的新边(frontier)再推一遍,没有新增就停。
///
/// 三条一跳规则(对称/逆/子属性)与传递放在同一轮里,因为它们互为输入——
/// 逆推出来的边可能让某条传递链接得上,反之亦然。
pub fn derive(edges: &[TimedEdge], axioms: &HashMap<Uuid, Axioms>) -> Derivation {
let mut out = Derivation::default();
// 断言过的时序三元组。**派生撞上它就让路**——asserted > derived 是硬性的;
// 判断的是区间覆盖,不只是等值,所以无时间/更宽的一段也能挡住窄的派生。
let mut asserted: HashMap<Triple, Vec<Span>> = HashMap::new();
for e in edges {
asserted
.entry((e.edge.predicate, e.edge.subject, e.edge.object))
.or_default()
.push((e.from, e.to));
}
// 已经推出来的 → 怎么来的。继续展开时既看区间也看证明长度:覆盖同一段时间
// 的短证明能在深度上限前再多走几步,不能被先到的长证明挡掉。
let mut reached: HashMap<Triple, Vec<(Span, Reached)>> = HashMap::new();
// **封顶仍按谓词计**:那个常量的含义没变(一个谓词最多推两万条),
// 而 `Derivation::capped` 回的也是谓词列表。跨谓词之后若改成全局一个数,
// 界面上「哪个谓词太密」就答不出来了
let mut per_pred: HashMap<Uuid, usize> = HashMap::new();
let mut capped: HashSet<Uuid> = HashSet::new();
// 从 (谓词, 主语) 出发能走的边,传递用。派生出来的也进来——它们已经是
// 我们的断言了,链上不该因为「来路不同」断掉
let mut adj: HashMap<(Uuid, Uuid), Vec<Hop>> = HashMap::new();
// 新边也可能是链的右半段:左半段已离开 frontier,不能等它再展开一次。
// 按宾语索引入边,才能把后到的 B→C 接到已经见过的 A→B 上。
let mut incoming: HashMap<(Uuid, Uuid), Vec<Hop>> = HashMap::new();
for e in edges {
adj.entry((e.edge.predicate, e.edge.subject))
.or_default()
.push((e.edge.object, e.from, e.to, vec![e.edge.fact]));
incoming
.entry((e.edge.predicate, e.edge.object))
.or_default()
.push((e.edge.subject, e.from, e.to, vec![e.edge.fact]));
}
let mut frontier: Vec<(Triple, Reached)> = edges
.iter()
.map(|e| {
(
(e.edge.predicate, e.edge.subject, e.edge.object),
Reached {
from: e.from,
to: e.to,
premises: vec![e.edge.fact],
},
)
})
.collect();
// 起始 frontier 的顺序跟着入参走,而入参顺序不保证——按完整事实身份排一次,
// 同一个库两次推导才给得出同一份结果
frontier.sort_by_key(|(t, acc)| (*t, acc.from, acc.to));
// 轮数上限是**兜底**,真正的界在下面那条 `premises.len() >= MAX_DEPTH`:
// 常量的含义是「路径最长 12」,按前提条数算才对得上。轮数只防病态输入
for _ in 0..MAX_DEPTH {
if frontier.is_empty() {
break;
}
let mut next: Vec<(Triple, Reached)> = Vec::new();
for (triple, acc) in frontier.drain(..) {
let (pred, subj, obj) = triple;
let Some(ax) = axioms.get(&pred) else {
continue;
};
// 再接一条就超了:这一条不再往下延,但它自己已经产出过
if acc.premises.len() >= MAX_DEPTH {
continue;
}
// ---- 一跳的三条:换主宾(对称)、换谓词(逆 / 子属性)
let mut hops: Vec<(Triple, Rule)> = Vec::new();
if ax.symmetric {
hops.push(((pred, obj, subj), Rule::Symmetric));
}
if let Some(inv) = ax.inverse_of {
// `A p B ⟹ B p⁻¹ A`。主宾对调**且**谓词换掉——两件事一起发生,
// 只做一件是这条规则最容易写错的地方
hops.push(((inv, obj, subj), Rule::Inverse));
}
if let Some(sup) = ax.sub_property_of {
// `A p B ∧ p ⊑ q ⟹ A q B`。主宾不动,只升谓词
hops.push(((sup, subj, obj), Rule::SubProperty));
}
for (t, rule) in hops {
if emit(
t,
pred,
rule,
&acc,
acc.from,
acc.to,
None,
&asserted,
&mut reached,
&mut per_pred,
&mut capped,
&mut out,
&mut next,
&mut adj,
&mut incoming,
) {
continue;
}
}
// ---- 传递:新边既能作左半段,也能作右半段
if ax.transitive {
let outs = adj.get(&(pred, obj)).cloned().unwrap_or_default();
for (c, from, to, hop_premises) in outs {
// **不推自环。** `A p A` 在一个传递+反对称的谓词上是矛盾
// 而不是知识,R0 那边会把这个环连路径一起报出来
if subj == c {
continue;
}
let Some((nf, nt)) = overlap((acc.from, acc.to), (from, to)) else {
continue;
};
emit(
(pred, subj, c),
pred,
Rule::Transitive,
&acc,
nf,
nt,
Some(&hop_premises),
&asserted,
&mut reached,
&mut per_pred,
&mut capped,
&mut out,
&mut next,
&mut adj,
&mut incoming,
);
}
let ins = incoming.get(&(pred, subj)).cloned().unwrap_or_default();
for (a, from, to, premises) in ins {
if a == obj {
continue;
}
let Some((nf, nt)) = overlap((from, to), (acc.from, acc.to)) else {
continue;
};
// emit 按左、右顺序拼证明;后到的是右边,不能把整条路径倒过来。
let prefix = Reached { from, to, premises };
emit(
(pred, a, obj),
pred,
Rule::Transitive,
&prefix,
nf,
nt,
Some(&acc.premises),
&asserted,
&mut reached,
&mut per_pred,
&mut capped,
&mut out,
&mut next,
&mut adj,
&mut incoming,
);
}
}
}
next.sort_by_key(|(t, acc)| (*t, acc.from, acc.to));
frontier = next;
}
// 窄区间可能先输出、宽区间后到。等传播结束再清理输出:较窄但更短的证明
// 仍可能是 MAX_DEPTH 内走完后续链的必要中间态,不能在传播时仅按区间删掉。
let spans = edges
.iter()
.map(|edge| (edge.edge.fact, (edge.from, edge.to)))
.collect();
retain_widest_outputs(&mut out.facts, &spans);
let mut capped: Vec<Uuid> = capped.into_iter().collect();
capped.sort();
out.capped = capped;
out
}
/// `outer` 是否覆盖 `inner`。两端都为 `None` 表示无界,因此能覆盖任何同向区间。
fn span_contains(outer: Span, inner: Span) -> bool {
outer
.0
.is_none_or(|outer| inner.0.is_some_and(|inner| outer <= inner))
&& outer
.1
.is_none_or(|outer| inner.1.is_some_and(|inner| outer >= inner))
}
fn retain_widest_outputs(facts: &mut Vec<Derived>, spans: &HashMap<Uuid, Span>) {
let mut grouped: HashMap<Triple, Vec<(usize, Span)>> = HashMap::new();
for (index, fact) in facts.iter().enumerate() {
// 无法重算有效期的输出沿用调用方原有的处理,不在清理时引入新的失败语义。
let Some(span) = validity(&fact.premises, spans) else {
continue;
};
grouped
.entry((fact.predicate, fact.subject, fact.object))
.or_default()
.push((index, span));
}
let mut keep = vec![true; facts.len()];
for outputs in grouped.values() {
for &(index, span) in outputs {
keep[index] = !outputs.iter().any(|&(other, outer)| {
// 相同区间只留先输出的一份,避免互相覆盖导致全部被删。
other != index && span_contains(outer, span) && (outer != span || other < index)
});
}
}
// 保留原顺序与整份 Derived,证明、via 和 rule 不重新拼装。
let mut index = 0;
facts.retain(|_| {
let retained = keep[index];
index += 1;
retained
});
}
/// 落一条派生,并把它接进邻接表供后续传递使用。返回 true = 这个谓词封顶了。
///
/// 参数多得难看,但把它抽出来是必要的:四条规则各自的落地动作一模一样
/// (查断言、查已推、算区间、记证明、进 frontier、进邻接表),而上一版
/// 正是因为对称与传递各写一遍,两处的「跳过条件」慢慢长得不一样了。
#[allow(clippy::too_many_arguments)]
fn emit(
t: Triple,
// 触发它的那个谓词的声明。四条规则都是「当前展开的这条边的谓词」
via: Uuid,
rule: Rule,
acc: &Reached,
from: Option<i64>,
to: Option<i64>,
// 传递多用掉的那一条边所依赖的全部前提;一跳规则没有
extra_premises: Option<&[Uuid]>,
asserted: &HashMap<Triple, Vec<Span>>,
reached: &mut HashMap<Triple, Vec<(Span, Reached)>>,
per_pred: &mut HashMap<Uuid, usize>,
capped: &mut HashSet<Uuid>,
out: &mut Derivation,
next: &mut Vec<(Triple, Reached)>,
adj: &mut HashMap<(Uuid, Uuid), Vec<Hop>>,
incoming: &mut HashMap<(Uuid, Uuid), Vec<Hop>>,
) -> bool {
let (pred, subj, obj) = t;
// 自环不推,任何规则都一样:`A p A` 是矛盾不是知识
if subj == obj {
return false;
}
let span = (from, to);
// 断言优先;无时间断言也覆盖日期的派生。
if asserted
.get(&t)
.into_iter()
.flatten()
.copied()
.any(|outer| span_contains(outer, span))
{
return false;
}
let mut premises = acc.premises.clone();
if let Some(extra) = extra_premises {
premises.extend_from_slice(extra);
}
// 深度上限在这里再判一次。展开 frontier 时那条 `premises.len() >= MAX_DEPTH`
// 只看得到当前这一份;传递接上来的那条边可能自带好几条前提,一次就能把长度
// 顶过上限,所以**拼完之后**才是判得上限的地方
if premises.len() > MAX_DEPTH {
return false;
}
let previous = reached.entry(t).or_default();
// 同一段时间的长证明只能挡住重复展示,不能挡住短证明继续展开:否则先走了
// 绕路,就可能在 12 条前提处停下,而本来存在一条 12 条以内能走完的捷径。
// 区间与长度都被覆盖才丢掉;逆的互指仍会在同长的证明处收敛。
let covered = previous
.iter()
.any(|(outer, _)| span_contains(*outer, span));
if previous
.iter()
.any(|(outer, proof)| span_contains(*outer, span) && proof.premises.len() <= premises.len())
{
return false;
}
if !covered {
let n = per_pred.entry(pred).or_insert(0);
if *n >= MAX_DERIVED_PER_PREDICATE {
capped.insert(pred);
return true;
}
*n += 1;
}
let r = Reached {
from,
to,
premises: premises.clone(),
};
previous.retain(|(old_span, proof)| {
!(span_contains(span, *old_span) && premises.len() <= proof.premises.len())
});
previous.push((span, r.clone()));
// 派生出来的边也能被后续传递接上。**整份证明都要带上**:邻接表里的这一项
// 以后会被当作前提拼进下一条派生,只留首条会让链上的证明越拼越短
if !premises.is_empty() {
for (index, key, other) in [(adj, (pred, subj), obj), (incoming, (pred, obj), subj)] {
let hops = index.entry(key).or_default();
hops.retain(|(end, f, t, proof)| {
*end != other || !(span_contains(span, (*f, *t)) && premises.len() <= proof.len())
});
hops.push((other, from, to, premises.clone()));
}
}
if !covered {
out.facts.push(Derived {
predicate: pred,
via,
subject: subj,
object: obj,
rule,
premises,
});
}
next.push((t, r));
false
}
/// 派生事实的有效期,给落库那一侧用。
///
/// 与 [`derive`] 分开是因为交集已经在推导过程里算过了,而调用方拿到的
/// [`Derived`] 只带前提——重算一次比把区间塞进结果里更省事,也更难错:
/// 前提就是那几条事实,交集是它们的函数。
pub fn validity(
premises: &[Uuid],
by_fact: &HashMap<Uuid, (Option<i64>, Option<i64>)>,
) -> Option<(Option<i64>, Option<i64>)> {
let mut acc = (None, None);
for p in premises {
let span = *by_fact.get(p)?;
acc = overlap(acc, span)?;
}
Some(acc)
}
// ===================== 矛盾:派生撞上了什么(0017) =====================
/// 一条派生撞上了一条断言。
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Clash {
/// `Derivation::facts` 里的下标
pub derived: usize,
/// 撞在哪条公理上:`Functional`、`InverseFunctional`、`Asymmetry`、`SelfLoop`
pub axiom: Kind,
/// 被撞的断言。自环没有对方,取派生的最后一条前提
pub against: Uuid,
}
/// 两条规则加在一起产出了互相矛盾的派生。
///
/// **按规则对聚合,不逐对报**:`ceo_of ⊑ works_at` 加 `works_at` functional,每个有
/// 两个 ceo 的组织就撞一对——根子是那两条声明,逐对进队列只会淹掉 Review。
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RuleClash {
/// (声明所在的谓词, 规则种类),两条按 (谓词, 种类) 排过序,a ≤ b
pub a: (Uuid, Rule),
pub b: (Uuid, Rule),
pub axiom: Kind,
/// 互撞的派生对,按 `Derivation::facts` 的下标
pub pairs: Vec<(usize, usize)>,
}
/// (谓词, 一端) → 另一端的边:(另一端, 事实, 区间)。functional 两个方向各一份
type ByEnd = HashMap<(Uuid, Uuid), Vec<(Uuid, Uuid, Span)>>;
/// 一条规则的身份:声明所在的谓词 + 规则种类
type RuleSide = (Uuid, Rule);
/// 互撞的派生对,按 (规则 a, 规则 b, 撞在哪条公理上) 分组
type Grouped = HashMap<(RuleSide, RuleSide, Kind), Vec<(usize, usize)>>;
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Contradictions {
pub with_assertions: Vec<Clash>,
pub between_derivations: Vec<RuleClash>,
}
impl Contradictions {
/// 不该落地的派生下标:撞过断言的,和撞过别的派生的。**写图宁少勿错**(0002)
pub fn blocked(&self) -> HashSet<usize> {
let mut out: HashSet<usize> = self.with_assertions.iter().map(|c| c.derived).collect();
for rc in &self.between_derivations {
for (i, j) in &rc.pairs {
out.insert(*i);
out.insert(*j);
}
}
out
}
}
/// 拿公理量一遍派生:与断言撞的逐条列出,派生之间撞的按规则对聚合。
///
/// 只查四类——`functional`(含 inverse)、`asymmetric`、`irreflexive`——因为只有它们
/// 能由**两条边**判出矛盾;传递环那类要走闭包,派生本身就是闭包的一部分,R0 对断言
/// 查过就够了。functional 与 asymmetric 都要求**有效区间重叠**:Mira 走了 Devin
/// 接任,两条 `ceo_of` 区间不交,那是接任,不是矛盾。
///
/// 撞上断言的派生一律**不落地**(asserted > derived,硬性);这一步把「让路」这件事
/// 从静默变成可见——0002 那张表里写了没做的那一行。
pub fn contradictions(
derivation: &Derivation,
edges: &[TimedEdge],
axioms: &HashMap<Uuid, Axioms>,
spans: &HashMap<Uuid, (Option<i64>, Option<i64>)>,
) -> Contradictions {
// 断言的三份索引:(谓词, 主) → 宾;(谓词, 宾) → 主;(谓词, 主, 宾) → 边
let mut by_ps: ByEnd = HashMap::new();
let mut by_po: ByEnd = HashMap::new();
let mut by_spo: HashMap<(Uuid, Uuid, Uuid), Vec<(Uuid, Span)>> = HashMap::new();
for e in edges {
let span = (e.from, e.to);
let x = e.edge;
by_ps
.entry((x.predicate, x.subject))
.or_default()
.push((x.object, x.fact, span));
by_po
.entry((x.predicate, x.object))
.or_default()
.push((x.subject, x.fact, span));
by_spo
.entry((x.predicate, x.subject, x.object))
.or_default()
.push((x.fact, span));
}
let mut out = Contradictions::default();
// 派生的区间:与落库那一侧同一个函数算,算不出的(前提区间不交)本来就不会落
let derived_spans: Vec<Option<Span>> = derivation
.facts
.iter()
.map(|d| validity(&d.premises, spans))
.collect();
for (i, d) in derivation.facts.iter().enumerate() {
let Some(span) = derived_spans[i] else {
continue;
};
let Some(ax) = axioms.get(&d.predicate) else {
continue;
};
let Some(&last) = d.premises.last() else {
continue;
};
if ax.irreflexive && d.subject == d.object {
out.with_assertions.push(Clash {
derived: i,
axiom: Kind::SelfLoop,
against: last,
});
}
if ax.asymmetric {
if let Some(v) = by_spo.get(&(d.predicate, d.object, d.subject)) {
for (fact, sp) in v {
if overlap(span, *sp).is_some() {
out.with_assertions.push(Clash {
derived: i,
axiom: Kind::Asymmetry,
against: *fact,
});
}
}
}
}
if ax.functional {
if let Some(v) = by_ps.get(&(d.predicate, d.subject)) {
for (obj, fact, sp) in v {
if *obj != d.object && overlap(span, *sp).is_some() {
out.with_assertions.push(Clash {
derived: i,
axiom: Kind::Functional,
against: *fact,
});
}
}
}
}
if ax.inverse_functional {
if let Some(v) = by_po.get(&(d.predicate, d.object)) {
for (subj, fact, sp) in v {
if *subj != d.subject && overlap(span, *sp).is_some() {
out.with_assertions.push(Clash {
derived: i,
axiom: Kind::InverseFunctional,
against: *fact,
});
}
}
}
}
}
// 派生之间:同样三份索引,只不过键的是下标
let mut d_ps: HashMap<(Uuid, Uuid), Vec<usize>> = HashMap::new();
let mut d_po: HashMap<(Uuid, Uuid), Vec<usize>> = HashMap::new();
let mut d_spo: HashMap<(Uuid, Uuid, Uuid), Vec<usize>> = HashMap::new();
for (i, d) in derivation.facts.iter().enumerate() {
if derived_spans[i].is_none() {
continue;
}
d_ps.entry((d.predicate, d.subject)).or_default().push(i);
d_po.entry((d.predicate, d.object)).or_default().push(i);
d_spo
.entry((d.predicate, d.subject, d.object))
.or_default()
.push(i);
}
let mut grouped: Grouped = HashMap::new();
let mut note = |i: usize, j: usize, axiom: Kind| {
let (i, j) = if i < j { (i, j) } else { (j, i) };
let ri = (derivation.facts[i].via, derivation.facts[i].rule);
let rj = (derivation.facts[j].via, derivation.facts[j].rule);
let (a, b) = if (ri.0, ri.1.as_str()) <= (rj.0, rj.1.as_str()) {
(ri, rj)
} else {
(rj, ri)
};
grouped.entry((a, b, axiom)).or_default().push((i, j));
};
for (i, d) in derivation.facts.iter().enumerate() {
let Some(span) = derived_spans[i] else {
continue;
};
let Some(ax) = axioms.get(&d.predicate) else {
continue;
};
let overlapping = |j: usize| derived_spans[j].is_some_and(|s| overlap(span, s).is_some());
if ax.asymmetric {
if let Some(v) = d_spo.get(&(d.predicate, d.object, d.subject)) {
for &j in v {
if j > i && overlapping(j) {
note(i, j, Kind::Asymmetry);
}
}
}
}
if ax.functional {
if let Some(v) = d_ps.get(&(d.predicate, d.subject)) {
for &j in v {
if j > i && derivation.facts[j].object != d.object && overlapping(j) {
note(i, j, Kind::Functional);
}
}
}
}
if ax.inverse_functional {
if let Some(v) = d_po.get(&(d.predicate, d.object)) {
for &j in v {
if j > i && derivation.facts[j].subject != d.subject && overlapping(j) {
note(i, j, Kind::InverseFunctional);
}
}
}
}
}
let mut rule_clashes: Vec<RuleClash> = grouped
.into_iter()
.map(|((a, b, axiom), mut pairs)| {
pairs.sort_unstable();
pairs.dedup();
RuleClash { a, b, axiom, pairs }
})
.collect();
// 输出排过序——这条路的价值有一半在确定性
rule_clashes.sort_by(|x, y| {
(x.a.0, x.a.1.as_str(), x.b.0, x.b.1.as_str()).cmp(&(
y.a.0,
y.a.1.as_str(),
y.b.0,
y.b.1.as_str(),
))
});
out.between_derivations = rule_clashes;
out
}
#[cfg(test)]
mod tests {
use super::*;
fn n(i: u8) -> Uuid {
Uuid::from_bytes([i; 16])
}
fn f(i: u8) -> Uuid {
Uuid::from_bytes([i; 16].map(|b| b ^ 0xF0))
}
/// 一条无时间的边
fn e(fact: u8, s: u8, o: u8) -> TimedEdge {
TimedEdge {
edge: Edge {
fact: f(fact),
predicate: n(99),
subject: n(s),
object: n(o),
},
from: None,
to: None,
}
}
/// 一条带区间的边
fn te(fact: u8, s: u8, o: u8, from: Option<i64>, to: Option<i64>) -> TimedEdge {
TimedEdge {
from,
to,
..e(fact, s, o)
}
}
fn with(ax: Axioms) -> HashMap<Uuid, Axioms> {
HashMap::from([(n(99), ax)])
}
fn transitive() -> HashMap<Uuid, Axioms> {
with(Axioms {
transitive: true,
..Default::default()
})
}
fn pairs(d: &Derivation) -> Vec<(u8, u8)> {
let mut p: Vec<(u8, u8)> = d
.facts
.iter()
.map(|x| (x.subject.as_bytes()[0], x.object.as_bytes()[0]))
.collect();
p.sort();
p
}
#[test]
fn nothing_declared_derives_nothing() {
let edges = [e(1, 1, 2), e(2, 2, 3)];
assert!(derive(&edges, &HashMap::new()).facts.is_empty());
// 声明了别的公理也一样——只有 transitive / symmetric 编得出规则
let irr = with(Axioms {
irreflexive: true,
..Default::default()
});
assert!(derive(&edges, &irr).facts.is_empty());
}
#[test]
fn a_chain_closes() {
// 1→2→3→4,传递应推出 1→3、1→4、2→4
let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 3, 4)];
let d = derive(&edges, &transitive());
assert_eq!(pairs(&d), vec![(1, 3), (1, 4), (2, 4)]);
assert!(d.capped.is_empty());
}
#[test]
fn the_proof_is_the_premises_in_order() {
let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 3, 4)];
let d = derive(&edges, &transitive());
let long = d
.facts
.iter()
.find(|x| x.subject == n(1) && x.object == n(4))
.unwrap();
assert_eq!(
long.premises,
vec![f(1), f(2), f(3)],
"证明要按推导顺序带上三条前提"
);
assert_eq!(long.rule, Rule::Transitive);
}
#[test]
fn a_chained_derivation_keeps_every_premise() {
// 4→1→2 推出 4→2,而 4→2 已经是一条证明;传递再接 2→3 时,那条派生边
// 自带的两条前提要一起进证明。少了任一条,`validity` 就只对留下的前提求
// 交集,结论会比实际宽
let edges = [
te(1, 1, 2, Some(0), Some(100)),
te(2, 2, 3, Some(40), Some(50)),
te(3, 4, 1, Some(0), Some(100)),
];
let d = derive(&edges, &transitive());
let to3 = d
.facts
.iter()
.find(|x| x.subject == n(4) && x.object == n(3))
.expect("4→3 应由 4→1→2→3 推出");
assert_eq!(
to3.premises,
vec![f(3), f(1), f(2)],
"证明要带上链上三条前提,中间那条派生边的两条都在内"
);
let by_fact: HashMap<Uuid, _> = edges
.iter()
.map(|x| (x.edge.fact, (x.from, x.to)))
.collect();
assert_eq!(
validity(&to3.premises, &by_fact),
Some((Some(40), Some(50))),
"有效期应是三条前提的交集,而不是漏掉中间那条的宽区间"
);
}
#[test]
fn asserted_beats_derived() {
// 1→2、2→3 已经推得出 1→3,而 1→3 也被断言过 → 不重复派生
let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 1, 3)];
let d = derive(&edges, &transitive());
assert!(d.facts.is_empty(), "断言过的三元组不该再派生一份");
}
#[test]
fn a_ring_does_not_derive_self_loops_and_does_not_hang() {
// 1→2→3→1:环。传递闭包里会推出 1→1,而那是矛盾不是知识
let edges = [e(1, 1, 2), e(2, 2, 3), e(3, 3, 1)];
let d = derive(&edges, &transitive());
assert!(
d.facts.iter().all(|x| x.subject != x.object),
"自环不该被推出来——R0 会把这个环连路径一起报"
);
// 但环上其余的推导是成立的:1→3、2→1、3→2
assert_eq!(pairs(&d), vec![(1, 3), (2, 1), (3, 2)]);
}
#[test]
fn symmetric_derives_the_other_direction_once() {
let sym = with(Axioms {
symmetric: true,
..Default::default()
});
let edges = [e(1, 1, 2)];
let d = derive(&edges, &sym);
assert_eq!(pairs(&d), vec![(2, 1)]);
assert_eq!(d.facts[0].rule, Rule::Symmetric);
assert_eq!(d.facts[0].premises, vec![f(1)]);
// 两个方向都断言过 → 无可派生
let both = [e(1, 1, 2), e(2, 2, 1)];
assert!(derive(&both, &sym).facts.is_empty());
}
#[test]
fn validity_is_the_intersection() {
// 1→2 在 [10,30),2→3 在 [20,∞) ⟹ 1→3 在 [20,30)
let edges = [te(1, 1, 2, Some(10), Some(30)), te(2, 2, 3, Some(20), None)];
let d = derive(&edges, &transitive());
assert_eq!(pairs(&d), vec![(1, 3)]);
let by_fact = HashMap::from([(f(1), (Some(10), Some(30))), (f(2), (Some(20), None))]);
assert_eq!(
validity(&d.facts[0].premises, &by_fact),
Some((Some(20), Some(30)))
);
}
#[test]
fn no_overlap_derives_nothing() {
// 1→2 只在 [10,20),2→3 只在 [30,40) —— 这条链在任何时刻都不成立
let edges = [
te(1, 1, 2, Some(10), Some(20)),
te(2, 2, 3, Some(30), Some(40)),
];
let d = derive(&edges, &transitive());
assert!(
d.facts.is_empty(),
"两段不重叠时推出来的是一条从不为真的事实"
);
}
#[test]
fn a_touching_boundary_is_not_an_overlap() {
// [10,20) 与 [20,30):半开区间,端点相接不算重叠
let edges = [
te(1, 1, 2, Some(10), Some(20)),
te(2, 2, 3, Some(20), Some(30)),
];
assert!(derive(&edges, &transitive()).facts.is_empty());
}
#[test]
fn depth_is_bounded() {
// 一条 40 跳的链,深度上限是 12
let edges: Vec<TimedEdge> = (1..=40).map(|i| e(i, i, i + 1)).collect();
let d = derive(&edges, &transitive());
let longest = d.facts.iter().map(|x| x.premises.len()).max().unwrap();
assert!(
longest <= MAX_DEPTH,
"证明长度不该超过深度上限,实际 {longest}"
);
assert!(!d.facts.is_empty(), "有上限不等于什么都不推");
}
fn edges_with_shortcuts() -> Vec<TimedEdge> {
// 21→8→16 与 14→1→7→12 都有捷径;先碰到绕路的证明,不该让
// 后到的短证明失去继续推导的机会。11→20 的最短路径恰好 12 条前提。
[
(12, 0),
(7, 12),
(15, 10),
(1, 7),
(2, 5),
(8, 16),
(13, 21),
(5, 13),
(6, 14),
(14, 12),
(21, 8),
(0, 20),
(10, 2),
(21, 16),
(14, 1),
(11, 15),
(16, 6),
]
.into_iter()
.enumerate()
.map(|(i, (s, o))| e(i as u8, s, o))
.collect()
}
#[test]
fn a_shorter_proof_keeps_a_chain_within_the_depth_limit() {
let edges = edges_with_shortcuts();
let d = derive(&edges, &transitive());
let chain = d
.facts
.iter()
.find(|x| x.subject == n(11) && x.object == n(20))
.expect("12 条前提能走完的链不能被先到的长证明挡住");
assert_eq!(chain.premises.len(), MAX_DEPTH);
assert!(d.facts.iter().all(|x| x.premises.len() <= MAX_DEPTH));
let distinct: HashSet<_> = d.facts.iter().map(|x| (x.subject, x.object)).collect();
assert_eq!(distinct.len(), d.facts.len(), "短证明不再物化同一段事实");
assert!(d.capped.is_empty());
}
#[test]
fn shorter_proofs_do_not_spend_the_output_cap_twice() {
let component = edges_with_shortcuts();
// 多个互不相连的副本共用一个谓词;每份都含需要重新展开的短证明。
// 封顶数的是实际产出的事实,不能拿这些替代证明抵扣额度。
let edges: Vec<_> = (0..300u128)
.flat_map(|copy| {
component.iter().enumerate().map(move |(i, e)| TimedEdge {
edge: Edge {
fact: Uuid::from_u128(100_000 + copy * 32 + i as u128),
predicate: e.edge.predicate,
subject: Uuid::from_u128(copy * 32 + e.edge.subject.as_bytes()[0] as u128),
object: Uuid::from_u128(copy * 32 + e.edge.object.as_bytes()[0] as u128),
},
..*e
})
})
.collect();
let d = derive(&edges, &transitive());
assert_eq!(d.facts.len(), MAX_DERIVED_PER_PREDICATE);
assert_eq!(d.capped, vec![n(99)]);
let distinct: HashSet<_> = d.facts.iter().map(|x| (x.subject, x.object)).collect();
assert_eq!(distinct.len(), d.facts.len());
assert!(d.facts.iter().all(|x| x.premises.len() <= MAX_DEPTH));
}
#[test]
fn symmetric_feeds_the_transitive_chain() {
// 同时声明对称与传递:1→2 与 3→2 断言过,对称推出 2→3,
// 于是传递能接上 1→3
let both = with(Axioms {
symmetric: true,
transitive: true,
..Default::default()
});
let edges = [e(1, 1, 2), e(2, 3, 2)];
let d = derive(&edges, &both);
let got = pairs(&d);
assert!(got.contains(&(2, 1)) && got.contains(&(2, 3)), "两条对称边");
assert!(got.contains(&(1, 3)), "对称推出来的边要能继续参与传递");
}
#[test]
fn each_predicate_is_closed_on_its_own() {
// 99 传递、98 不是:跨谓词不该接成链
let mut other = e(2, 2, 3);
other.edge.predicate = n(98);
let edges = [e(1, 1, 2), other];
let d = derive(&edges, &transitive());
assert!(d.facts.is_empty(), "1 →(99) 2 →(98) 3 推不出任何东西");
}
// ---- 跨谓词的两条规则(inverseOf / subPropertyOf)----
//
// 上面那些用的都是单谓词 `n(99)`;这两条规则天生要三个谓词才说得清,
// 所以另起一组常量与构造器
const P: Uuid = Uuid::from_bytes([1; 16]);
const Q: Uuid = Uuid::from_bytes([2; 16]);
const R: Uuid = Uuid::from_bytes([3; 16]);
/// 指定谓词的一条无时间边
fn ep(pred: Uuid, fact: u8, s: u8, o: u8) -> TimedEdge {
TimedEdge {
edge: Edge {
fact: f(fact),
predicate: pred,
subject: n(s),
object: n(o),
},
from: None,
to: None,
}
}
/// 指定谓词、带区间
fn tep(pred: Uuid, fact: u8, s: u8, o: u8, from: Option<i64>, to: Option<i64>) -> TimedEdge {
TimedEdge {
from,
to,
..ep(pred, fact, s, o)
}
}
/// `p⁻¹ = q` 且 `q⁻¹ = p`——互指,收敛性靠它测
fn inverse_pair() -> HashMap<Uuid, Axioms> {
HashMap::from([
(
P,
Axioms {
inverse_of: Some(Q),
..Default::default()
},
),
(
Q,
Axioms {
inverse_of: Some(P),
..Default::default()
},
),
])
}
/// `p ⊑ q`
fn sub_property() -> HashMap<Uuid, Axioms> {
HashMap::from([(
P,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
)])
}
/// `A works_at B` ⟹ `B employs A`:主宾对调**且**换谓词。
/// 只做一件就是这条规则最常见的写错方式,所以两件都断言。
#[test]
fn the_inverse_swaps_the_ends_and_the_predicate() {
let d = derive(&[ep(P, 1, 1, 2)], &inverse_pair());
assert_eq!(d.facts.len(), 1, "一条边只推出一条逆");
let got = &d.facts[0];
assert_eq!(got.predicate, Q, "**谓词换了**");
assert_eq!((got.subject, got.object), (n(2), n(1)), "**主宾也对调了**");
assert_eq!(got.rule, Rule::Inverse);
assert_eq!(got.via, P, "声明写在 P 上,产出落在 Q 上");
assert_eq!(got.premises, vec![f(1)], "证明就是那一条原边");
}
/// `p⁻¹ = q` 且 `q⁻¹ = p` —— 互指。推回来的那条已经断言过,
/// 必须收敛而不是来回震荡。
#[test]
fn a_mutual_inverse_settles_instead_of_bouncing() {
let d = derive(&[ep(P, 1, 1, 2), ep(Q, 2, 2, 1)], &inverse_pair());
assert!(
d.facts.is_empty(),
"两个方向都已经断言过,一条都不该推——**断言优先**"
);
}
/// `p ⊑ q`:断言具体的,通用的也成立。主宾不动。
#[test]
fn a_sub_property_lifts_the_predicate_and_keeps_the_ends() {
let d = derive(&[ep(P, 1, 1, 2)], &sub_property());
assert_eq!(d.facts.len(), 1);
let got = &d.facts[0];
assert_eq!(got.predicate, Q, "升到父属性");
assert_eq!((got.subject, got.object), (n(1), n(2)), "主宾不动");
assert_eq!(got.rule, Rule::SubProperty);
assert_eq!(
got.via, P,
"**via 是声明公理的那个谓词**,不是推出来的那个——落库按它找规则行"
);
}
/// **不换谓词的两条规则,`via` 必须等于 `predicate`。**
///
/// 这条看着是废话,而它正是那个 bug 藏得住的原因:落库从前按 `predicate`
/// 找规则行,对传递与对称一直是对的,所以没人发现键选错了。跨谓词的两条
/// 一加,`ceo_of ⊑ works_at` 推出的事实就查不到规则、被静默丢弃。
#[test]
fn for_the_same_predicate_rules_via_is_the_predicate() {
let d = derive(&[e(1, 1, 2), e(2, 2, 3)], &transitive());
assert!(!d.facts.is_empty());
for f in &d.facts {
assert_eq!(f.via, f.predicate, "传递不换谓词");
}
}
/// **这一条是整次改造的理由**:三条规则串起来。
///
/// `A ceo_of B` ∧ `ceo_of ⊑ works_at` ∧ `works_at⁻¹ = employs`
/// ⟹ `A works_at B` ⟹ `B employs A`
///
/// 按谓词分组的旧结构在第一步就断了。
#[test]
fn a_sub_property_feeds_the_inverse() {
let mut ax = HashMap::new();
// ceo_of ⊑ works_at
ax.insert(
P,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
);
// works_at⁻¹ = employs
ax.insert(
Q,
Axioms {
inverse_of: Some(R),
..Default::default()
},
);
let d = derive(&[ep(P, 1, 1, 2)], &ax);
let mut got: Vec<(Uuid, u8, u8)> = d
.facts
.iter()
.map(|x| (x.predicate, x.subject.as_bytes()[0], x.object.as_bytes()[0]))
.collect();
got.sort();
assert!(got.contains(&(Q, 1, 2)), "先升成 works_at");
assert!(
got.contains(&(R, 2, 1)),
"**再转成 employs 的反方向**——跨了两个谓词,旧结构做不到"
);
assert_eq!(got.len(), 2);
// 证明要跟着长:第二跳用掉两条前提里的第一条
let employs = d.facts.iter().find(|x| x.predicate == R).unwrap();
assert_eq!(employs.premises, vec![f(1)], "根还是那条原始断言");
}
/// 逆推出来的边要能被传递接上:`p` 传递、`q` 是它的逆,
/// `B q A` ∧ `C q B` 应当推出 `C q A`(若 q 也传递)。
#[test]
fn what_the_inverse_produces_can_still_be_chained() {
let mut ax = HashMap::new();
ax.insert(
P,
Axioms {
inverse_of: Some(Q),
..Default::default()
},
);
ax.insert(
Q,
Axioms {
transitive: true,
..Default::default()
},
);
// A p B、B p C ⟹ B q A、C q B ⟹(q 传递)⟹ C q A
let d = derive(&[ep(P, 1, 1, 2), ep(P, 2, 2, 3)], &ax);
let got: Vec<(Uuid, u8, u8)> = d
.facts
.iter()
.map(|x| (x.predicate, x.subject.as_bytes()[0], x.object.as_bytes()[0]))
.collect();
assert!(got.contains(&(Q, 2, 1)));
assert!(got.contains(&(Q, 3, 2)));
assert!(
got.contains(&(Q, 3, 1)),
"**逆产出的边要进邻接表**,否则传递接不上它"
);
}
#[test]
fn a_late_right_hand_edge_completes_an_existing_chain() {
for (source, target) in [(Q, P), (P, Q)] {
for inverse in [false, true] {
let ax = HashMap::from([
(
source,
Axioms {
inverse_of: inverse.then_some(target),
sub_property_of: (!inverse).then_some(target),
..Default::default()
},
),
(
target,
Axioms {
transitive: true,
..Default::default()
},
),
]);
let left = ep(target, 1, 1, 2);
let right = if inverse {
ep(source, 2, 3, 2)
} else {
ep(source, 2, 2, 3)
};
for edges in [[left, right], [right, left]] {
let d = derive(&edges, &ax);
let chain = d
.facts
.iter()
.find(|x| x.predicate == target && x.subject == n(1) && x.object == n(3))
.expect("右边晚一步推出,不能让已展开的左边再也接不上它");
assert_eq!(chain.rule, Rule::Transitive);
assert_eq!(chain.via, target);
assert_eq!(chain.premises, vec![f(1), f(2)]);
assert!(d.capped.is_empty());
}
}
}
}
#[test]
fn a_late_right_hand_edge_keeps_the_whole_prefix_and_its_span() {
let ax = HashMap::from([
(
P,
Axioms {
transitive: true,
..Default::default()
},
),
(
Q,
Axioms {
sub_property_of: Some(P),
..Default::default()
},
),
(
R,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
),
]);
let edges = [
tep(P, 1, 1, 2, Some(0), Some(30)),
tep(P, 2, 2, 3, Some(10), Some(40)),
tep(R, 3, 3, 4, Some(20), Some(50)),
tep(R, 4, 3, 5, Some(30), Some(50)),
];
let spans = edges
.iter()
.map(|e| (e.edge.fact, (e.from, e.to)))
.collect();
let d = derive(&edges, &ax);
let chain = d
.facts
.iter()
.find(|x| x.predicate == P && x.subject == n(1) && x.object == n(4))
.expect("右边跨两轮到达时,已派生的左边也要接得上");
assert_eq!(chain.premises, vec![f(1), f(2), f(3)]);
assert_eq!(
validity(&chain.premises, &spans),
Some((Some(20), Some(30)))
);
assert!(
!d.facts
.iter()
.any(|x| x.predicate == P && x.subject == n(1) && x.object == n(5)),
"前缀止于 30,右边始于 30,半开区间没有交集"
);
}
/// 同一个 triple 可以有几段时间都成立。第二段不能被第一段挡在传递之外,
/// 而且输入顺序怎么排,时间闭包都要一样。
#[test]
fn distinct_intervals_for_one_triple_survive_axiom_steps_in_any_order() {
let ax = HashMap::from([
(
P,
Axioms {
inverse_of: Some(Q),
..Default::default()
},
),
(
Q,
Axioms {
transitive: true,
..Default::default()
},
),
]);
let early = tep(P, 1, 1, 2, Some(0), Some(10));
let late = tep(P, 2, 1, 2, Some(20), Some(30));
let cb = tep(Q, 3, 3, 2, Some(20), Some(30));
let spans = HashMap::from([
(f(1), (Some(0), Some(10))),
(f(2), (Some(20), Some(30))),
(f(3), (Some(20), Some(30))),
]);
let closure = |edges: [TimedEdge; 3]| {
let d = derive(&edges, &ax);
let mut closure: Vec<_> = d
.facts
.iter()
.map(|x| {
let (from, to) = validity(&x.premises, &spans).expect("派生区间应当可求");
(x.predicate, x.subject, x.object, from, to)
})
.collect();
closure.sort();
closure
};
let early_first = closure([early, late, cb]);
let late_first = closure([late, early, cb]);
assert_eq!(early_first, late_first, "闭包不能随 fact 输入顺序改变");
assert!(
early_first.contains(&(Q, n(2), n(1), Some(0), Some(10))),
"第一段 B q A 也要保留"
);
assert!(
early_first.contains(&(Q, n(2), n(1), Some(20), Some(30))),
"第二段 B q A 要保留"
);
assert!(
early_first.contains(&(Q, n(3), n(1), Some(20), Some(30))),
"第二段 B q A 必须还能和 C q B 接成 C q A"
);
}
/// 断言的一段区间如果覆盖了派生出来的更窄区间,就不再留下第二条同 triple 的事实。
#[test]
fn an_asserted_interval_covers_a_narrower_derivation() {
let edges = [
te(1, 1, 2, Some(10), Some(20)),
te(2, 2, 3, Some(10), Some(20)),
te(3, 1, 3, Some(0), Some(100)),
];
let d = derive(&edges, &transitive());
assert!(
d.facts.is_empty(),
"断言 [0,100) 已覆盖推出来的 [10,20),不该再派生一份"
);
}
/// 无时间断言表示一直成立,也覆盖有日期的同 triple 派生。
#[test]
fn an_undated_assertion_covers_a_dated_derivation() {
let edges = [
te(1, 1, 2, Some(10), Some(20)),
te(2, 2, 3, Some(10), Some(20)),
te(3, 1, 3, None, None),
];
let d = derive(&edges, &transitive());
assert!(
d.facts.is_empty(),
"无时间断言覆盖 [10,20),不该推出一条说得更少的同 triple 事实"
);
}
/// 两条路径分别推出 [0,100) 与 [10,20):宽的保留,窄的丢掉;输入反序也一样。
#[test]
fn a_wider_route_suppresses_a_narrower_derivation() {
let edges = [
te(1, 1, 2, Some(0), Some(100)),
te(2, 2, 4, Some(0), Some(100)),
te(3, 1, 3, Some(10), Some(20)),
te(4, 3, 4, Some(10), Some(20)),
];
let by_fact: HashMap<_, _> = edges
.iter()
.map(|e| (e.edge.fact, (e.from, e.to)))
.collect();
let spans = |edges: [TimedEdge; 4]| {
let d = derive(&edges, &transitive());
let mut spans: Vec<_> = d
.facts
.iter()
.filter(|x| x.subject == n(1) && x.object == n(4))
.map(|x| validity(&x.premises, &by_fact).expect("派生区间应当可求"))
.collect();
spans.sort();
spans
};
let broad = (Some(0), Some(100));
assert_eq!(spans(edges), vec![broad], "只留下覆盖更宽的 [0,100)");
assert_eq!(
spans([edges[3], edges[2], edges[1], edges[0]]),
vec![broad],
"输入反序不能把被覆盖的窄区间又放回来"
);
}
fn competing_routes(
p: Uuid,
q: Uuid,
nodes: [Uuid; 4],
narrow: Span,
broad: Span,
) -> ([TimedEdge; 4], HashMap<Uuid, Axioms>) {
let [a, b, c, d] = nodes;
let edges = [
(101, p, a, d, narrow),
(102, q, a, b, broad),
(103, q, b, c, broad),
(104, q, c, d, broad),
]
.map(|(fact, predicate, subject, object, (from, to))| TimedEdge {
edge: Edge {
fact: Uuid::from_u128(fact),
predicate,
subject,
object,
},
from,
to,
});
let axioms = HashMap::from([
(
p,
Axioms {
sub_property_of: Some(q),
..Default::default()
},
),
(
q,
Axioms {
transitive: true,
..Default::default()
},
),
]);
(edges, axioms)
}
/// #1034 / #1040 留下的 follow-up:先输出子属性的窄区间,再输出传递的宽区间。
#[test]
fn a_later_wider_derivation_replaces_the_narrow_output_with_its_whole_proof() {
let p = Uuid::from_u128(1);
let q = Uuid::from_u128(2);
let [a, b, c, d] = [10, 20, 30, 40].map(Uuid::from_u128);
let (edges, axioms) = competing_routes(
p,
q,
[a, b, c, d],
(Some(10), Some(20)),
(Some(0), Some(100)),
);
let result = derive(&edges, &axioms);
let spans = spans_of(&edges);
let outputs: Vec<_> = result
.facts
.iter()
.filter(|fact| (fact.predicate, fact.subject, fact.object) == (q, a, d))
.collect();
assert_eq!(
outputs
.iter()
.map(|fact| validity(&fact.premises, &spans).unwrap())
.collect::<Vec<_>>(),
vec![(Some(0), Some(100))],
"后到的宽区间应移除先到的窄区间输出"
);
assert_eq!(
outputs[0].premises,
[102, 103, 104].map(Uuid::from_u128).to_vec()
);
assert_eq!(outputs[0].rule, Rule::Transitive);
assert_eq!(outputs[0].via, q);
assert!(result.capped.is_empty());
}
#[test]
fn final_intervals_do_not_depend_on_input_or_uuid_order() {
for (p, q) in [(1, 2), (2, 1)].map(|(p, q)| (Uuid::from_u128(p), Uuid::from_u128(q))) {
for nodes in [[10, 20, 30, 40], [40, 30, 20, 10], [20, 40, 10, 30]] {
let [a, b, c, d] = nodes.map(Uuid::from_u128);
let (edges, axioms) = competing_routes(
p,
q,
[a, b, c, d],
(Some(10), Some(20)),
(Some(0), Some(100)),
);
let spans = spans_of(&edges);
let mut expected = vec![
(q, a, c, Some(0), Some(100)),
(q, a, d, Some(0), Some(100)),
(q, b, d, Some(0), Some(100)),
];
expected.sort();
// 四条事实的全部 24 种排列;交换谓词排序时宽区间可以先到。
for i in 0..4 {
for j in 0..4 {
for k in 0..4 {
if i == j || i == k || j == k {
continue;
}
let last = (0..4).find(|x| *x != i && *x != j && *x != k).unwrap();
let result =
derive(&[edges[i], edges[j], edges[k], edges[last]], &axioms);
let mut actual: Vec<_> = result
.facts
.iter()
.map(|fact| {
let (from, to) = validity(&fact.premises, &spans).unwrap();
(fact.predicate, fact.subject, fact.object, from, to)
})
.collect();
actual.sort();
assert_eq!(actual, expected);
let wide = result
.facts
.iter()
.find(|fact| fact.object == d && fact.subject == a)
.unwrap();
assert_eq!(
wide.premises,
[102, 103, 104].map(Uuid::from_u128).to_vec()
);
assert_eq!((wide.via, wide.rule), (q, Rule::Transitive));
}
}
}
}
}
}
#[test]
fn final_outputs_keep_incomparable_spans_and_one_equal_span() {
let narrow = (Some(10), Some(20));
let cases = [
(narrow, (None, Some(100)), vec![(None, Some(100))]),
(narrow, (Some(0), None), vec![(Some(0), None)]),
(narrow, (None, None), vec![(None, None)]),
((None, Some(20)), (None, None), vec![(None, None)]),
((Some(10), None), (None, None), vec![(None, None)]),
(narrow, narrow, vec![narrow]),
((None, None), (None, None), vec![(None, None)]),
(
narrow,
(Some(15), Some(30)),
vec![narrow, (Some(15), Some(30))],
),
(
narrow,
(Some(20), Some(30)),
vec![narrow, (Some(20), Some(30))],
),
(
narrow,
(Some(30), Some(40)),
vec![narrow, (Some(30), Some(40))],
),
(
(None, Some(20)),
(Some(10), None),
vec![(None, Some(20)), (Some(10), None)],
),
];
for (narrow, broad, mut expected) in cases {
let (edges, axioms) = competing_routes(P, Q, [n(1), n(2), n(3), n(4)], narrow, broad);
let result = derive(&edges, &axioms);
let spans = spans_of(&edges);
let mut actual: Vec<_> = result
.facts
.iter()
.filter(|fact| (fact.predicate, fact.subject, fact.object) == (Q, n(1), n(4)))
.map(|fact| validity(&fact.premises, &spans).unwrap())
.collect();
actual.sort();
expected.sort();
assert_eq!(actual, expected, "区间 {narrow:?} 与 {broad:?}");
}
}
#[test]
fn a_union_of_outputs_does_not_cover_another_output() {
let target = n(100);
let intervals = [
(Some(0), Some(60)),
(Some(40), Some(100)),
(Some(20), Some(80)),
];
let edges = [P, Q, R]
.into_iter()
.zip(intervals)
.enumerate()
.map(|(i, (source, (from, to)))| tep(source, i as u8, 1, 2, from, to))
.collect::<Vec<_>>();
let axioms = [P, Q, R]
.map(|source| {
(
source,
Axioms {
sub_property_of: Some(target),
..Default::default()
},
)
})
.into_iter()
.collect();
let result = derive(&edges, &axioms);
let spans = spans_of(&edges);
let mut actual: Vec<_> = result
.facts
.iter()
.map(|fact| {
assert_eq!(
(fact.predicate, fact.subject, fact.object),
(target, n(1), n(2))
);
assert_eq!(fact.premises.len(), 1);
let source = edges
.iter()
.find(|edge| edge.edge.fact == fact.premises[0])
.unwrap();
assert_eq!(
(fact.via, fact.rule),
(source.edge.predicate, Rule::SubProperty)
);
validity(&fact.premises, &spans).unwrap()
})
.collect();
actual.sort();
let mut expected = intervals.to_vec();
expected.sort();
assert_eq!(actual, expected, "只能由单个区间覆盖,不能拿两段的并集替代");
}
#[test]
fn final_cleanup_keeps_one_equal_output_and_its_original_proof() {
let first = Derived {
predicate: Q,
subject: n(1),
object: n(2),
via: P,
rule: Rule::SubProperty,
premises: vec![f(1)],
};
let second = Derived {
via: Q,
rule: Rule::Transitive,
premises: vec![f(2), f(3)],
..first.clone()
};
let other_triple = Derived {
predicate: R,
..first.clone()
};
let spans = HashMap::from([
(f(1), (Some(10), Some(20))),
(f(2), (Some(0), Some(20))),
(f(3), (Some(10), Some(30))),
]);
let mut outputs = vec![first.clone(), other_triple.clone(), second];
retain_widest_outputs(&mut outputs, &spans);
assert_eq!(outputs, vec![first, other_triple]);
}
#[test]
fn final_cleanup_does_not_change_outputs_with_an_empty_validity() {
// 单跳规则原本允许此输入返回输出,由消费方用 validity 拒绝;清理不能改成 panic。
for to in [10, 20] {
let edges = [tep(P, 1, 1, 2, Some(20), Some(to))];
let result = derive(&edges, &sub_property());
assert_eq!(result.facts.len(), 1);
assert_eq!(result.facts[0].premises, vec![f(1)]);
assert_eq!(validity(&result.facts[0].premises, &spans_of(&edges)), None);
}
}
#[test]
fn a_narrower_shorter_proof_still_finishes_within_the_depth_limit() {
let mut edges = edges_with_shortcuts();
let shortcut = edges
.iter_mut()
.find(|edge| edge.edge.subject == n(21) && edge.edge.object == n(16))
.unwrap();
shortcut.from = Some(10);
shortcut.to = Some(20);
let shortcut_fact = shortcut.edge.fact;
let result = derive(&edges, &transitive());
let spans = spans_of(&edges);
let chain = result
.facts
.iter()
.find(|fact| fact.subject == n(11) && fact.object == n(20))
.expect("较窄的捷径证明也要在 12 条前提内走完");
assert_eq!(chain.premises.len(), MAX_DEPTH);
assert!(chain.premises.contains(&shortcut_fact));
assert_eq!(
validity(&chain.premises, &spans),
Some((Some(10), Some(20)))
);
let prefix = result
.facts
.iter()
.filter(|fact| fact.subject == n(11) && fact.object == n(16))
.collect::<Vec<_>>();
assert_eq!(
prefix.len(),
1,
"窄的中间证明参与传播,但最终只展示宽的前缀"
);
assert_eq!(validity(&prefix[0].premises, &spans), Some((None, None)));
}
/// 区间照旧取交集,跨谓词也一样。
#[test]
fn the_inverse_carries_the_same_span() {
let d = derive(&[tep(P, 1, 1, 2, Some(10), Some(20))], &inverse_pair());
assert_eq!(d.facts.len(), 1);
let v = validity(
&d.facts[0].premises,
&HashMap::from([(f(1), (Some(10), Some(20)))]),
);
assert_eq!(v, Some((Some(10), Some(20))), "逆不改变有效期");
}
/// 自己是自己的逆 = 对称,但不该推出自环。
#[test]
fn a_predicate_that_is_its_own_inverse_still_refuses_self_loops() {
let ax = HashMap::from([(
P,
Axioms {
inverse_of: Some(P),
..Default::default()
},
)]);
let d = derive(&[ep(P, 1, 1, 1)], &ax);
assert!(d.facts.is_empty(), "`A p A` 的逆还是 `A p A`——自环不推");
}
// ---------- 矛盾(0017) ----------
/// 指定谓词的一条带区间的边
fn et(pred: Uuid, fact: u8, s: u8, o: u8, from: Option<i64>, to: Option<i64>) -> TimedEdge {
TimedEdge {
edge: Edge {
fact: f(fact),
predicate: pred,
subject: n(s),
object: n(o),
},
from,
to,
}
}
fn spans_of(edges: &[TimedEdge]) -> HashMap<Uuid, (Option<i64>, Option<i64>)> {
edges
.iter()
.map(|e| (e.edge.fact, (e.from, e.to)))
.collect()
}
/// `ceo_of ⊑ works_at`,works_at functional:Mira 的 ceo_of 推出 works_at Acme,
/// 而账本里说她 works_at Globex——派生撞上断言,指名道姓
#[test]
fn a_derivation_that_breaks_functional_names_the_assertion_it_hit() {
let ax = HashMap::from([
(
P,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
),
(
Q,
Axioms {
functional: true,
..Default::default()
},
),
]);
let edges = [ep(P, 1, 1, 2), ep(Q, 2, 1, 3)];
let d = derive(&edges, &ax);
assert_eq!(d.facts.len(), 1);
let c = contradictions(&d, &edges, &ax, &spans_of(&edges));
assert_eq!(
c.with_assertions,
vec![Clash {
derived: 0,
axiom: Kind::Functional,
against: f(2)
}]
);
assert!(c.between_derivations.is_empty());
assert_eq!(c.blocked(), HashSet::from([0]));
}
/// 区间不交就不是矛盾:前任与继任
#[test]
fn disjoint_intervals_are_succession_and_stay_silent() {
let ax = HashMap::from([
(
P,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
),
(
Q,
Axioms {
functional: true,
..Default::default()
},
),
]);
let edges = [
et(P, 1, 1, 2, Some(10), Some(20)),
et(Q, 2, 1, 3, Some(30), None),
];
let d = derive(&edges, &ax);
let c = contradictions(&d, &edges, &ax, &spans_of(&edges));
assert!(c.with_assertions.is_empty(), "{c:?}");
}
/// 对称与非对称:`A p B` 对称推出 `B p A`,而 p 又声明 asymmetric——
/// 每条断言都撞上自己的镜像
#[test]
fn a_symmetric_derivation_hits_the_asymmetric_assertion() {
let ax = HashMap::from([(
P,
Axioms {
symmetric: true,
asymmetric: true,
..Default::default()
},
)]);
let edges = [ep(P, 1, 1, 2)];
let d = derive(&edges, &ax);
let c = contradictions(&d, &edges, &ax, &spans_of(&edges));
assert_eq!(c.with_assertions.len(), 1);
assert_eq!(c.with_assertions[0].axiom, Kind::Asymmetry);
assert_eq!(c.with_assertions[0].against, f(1));
}
/// 两条派生互撞时按规则对聚合,而且都不落地
#[test]
fn derivations_that_disagree_are_grouped_by_the_rules_that_made_them() {
let ax = HashMap::from([
(
P,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
),
(
Q,
Axioms {
functional: true,
..Default::default()
},
),
]);
// 1 ceo_of 2 与 1 ceo_of 3:两条 works_at 由同一条规则推出,互相排斥
let edges = [ep(P, 1, 1, 2), ep(P, 2, 1, 3), ep(P, 3, 4, 5)];
let d = derive(&edges, &ax);
assert_eq!(d.facts.len(), 3);
let c = contradictions(&d, &edges, &ax, &spans_of(&edges));
assert!(c.with_assertions.is_empty());
assert_eq!(c.between_derivations.len(), 1);
let rc = &c.between_derivations[0];
assert_eq!(rc.a, (P, Rule::SubProperty));
assert_eq!(rc.b, (P, Rule::SubProperty));
assert_eq!(rc.axiom, Kind::Functional);
assert_eq!(rc.pairs.len(), 1);
// 第三条(4 works_at 5)没跟谁撞,照常落地
assert_eq!(c.blocked().len(), 2);
assert!(!c.blocked().contains(&2));
}
/// 谓词上没有公理就没有矛盾可言
#[test]
fn a_predicate_without_axioms_cannot_contradict() {
let ax = HashMap::from([(
P,
Axioms {
sub_property_of: Some(Q),
..Default::default()
},
)]);
let edges = [ep(P, 1, 1, 2), ep(Q, 2, 1, 3)];
let d = derive(&edges, &ax);
let c = contradictions(&d, &edges, &ax, &spans_of(&edges));
assert_eq!(c, Contradictions::default());
}
}