use std::collections::{HashMap, HashSet, VecDeque};
use std::fmt;
use std::str::FromStr;
use serde::{Deserialize, Serialize};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum RelationKind {
Blocks,
BlockedBy,
Duplicates,
Related,
}
impl RelationKind {
pub const ALL: [RelationKind; 4] = [
RelationKind::Blocks,
RelationKind::BlockedBy,
RelationKind::Duplicates,
RelationKind::Related,
];
pub fn as_str(self) -> &'static str {
match self {
RelationKind::Blocks => "blocks",
RelationKind::BlockedBy => "blocked_by",
RelationKind::Duplicates => "duplicates",
RelationKind::Related => "related",
}
}
pub fn is_directional(self) -> bool {
!matches!(self, RelationKind::Related)
}
pub fn inverse(self) -> Option<Self> {
match self {
RelationKind::Blocks => Some(RelationKind::BlockedBy),
RelationKind::BlockedBy => Some(RelationKind::Blocks),
RelationKind::Duplicates | RelationKind::Related => None,
}
}
fn canonical(self) -> (Self, bool) {
match self {
RelationKind::BlockedBy => (RelationKind::Blocks, true),
other => (other, false),
}
}
}
impl fmt::Display for RelationKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
impl FromStr for RelationKind {
type Err = Diagnostic;
fn from_str(s: &str) -> Result<Self, Self::Err> {
match s {
"blocks" => Ok(RelationKind::Blocks),
"blocked_by" => Ok(RelationKind::BlockedBy),
"duplicates" => Ok(RelationKind::Duplicates),
"related" => Ok(RelationKind::Related),
other => Err(Diagnostic::unknown_kind(
"kind",
format!(
"unknown relation kind `{other}`; expected one of blocks, blocked_by, duplicates, related"
),
)),
}
}
}
pub type RelationshipId = String;
#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Relationship {
#[serde(default)]
pub id: RelationshipId,
pub from: u32,
pub to: u32,
pub kind: RelationKind,
#[serde(default, skip_serializing_if = "String::is_empty")]
pub display: String,
}
impl Relationship {
pub fn new(from: u32, to: u32, kind: RelationKind, target_title: &str) -> Self {
let canonical = CanonicalEdge::new(from, to, kind);
Self {
id: generate_relationship_id(),
from: canonical.from,
to: canonical.to,
kind: canonical.kind,
display: display_name(canonical.kind, canonical.to, target_title),
}
}
pub fn refresh_display(&mut self, target_title: &str) {
self.display = display_name(self.kind, self.to, target_title);
}
pub fn canonical(&self) -> CanonicalEdge {
CanonicalEdge::new(self.from, self.to, self.kind)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Duplicate {
Allowed,
Rejected,
}
pub fn display_name(kind: RelationKind, target: u32, target_title: &str) -> String {
if target_title.trim().is_empty() {
format!("{} #{target}", kind.as_str())
} else {
format!("{} #{target} {}", kind.as_str(), target_title.trim())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CanonicalEdge {
pub from: u32,
pub to: u32,
pub kind: RelationKind,
}
impl CanonicalEdge {
pub fn new(from: u32, to: u32, kind: RelationKind) -> Self {
let (kind, swap) = kind.canonical();
if swap || (!kind.is_directional() && from > to) {
Self {
from: to,
to: from,
kind,
}
} else {
Self { from, to, kind }
}
}
pub fn is_self_link(self) -> bool {
self.from == self.to
}
}
pub fn normalize(from: u32, to: u32, kind: RelationKind) -> CanonicalEdge {
CanonicalEdge::new(from, to, kind)
}
pub fn normalize_all<I>(authored: I) -> Vec<CanonicalEdge>
where
I: IntoIterator<Item = (u32, u32, RelationKind)>,
{
let mut seen: HashSet<CanonicalEdge> = HashSet::new();
for (from, to, kind) in authored {
seen.insert(CanonicalEdge::new(from, to, kind));
}
let mut edges: Vec<CanonicalEdge> = seen.into_iter().collect();
edges.sort_unstable();
edges
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum DiagnosticKind {
SelfLink,
MissingTarget,
ConflictingEdge,
Cycle,
UnknownKind,
UnknownRelation,
RetiredLinksKey,
}
impl DiagnosticKind {
pub fn as_str(self) -> &'static str {
match self {
DiagnosticKind::SelfLink => "self_link",
DiagnosticKind::MissingTarget => "missing_target",
DiagnosticKind::ConflictingEdge => "conflicting_edge",
DiagnosticKind::Cycle => "cycle",
DiagnosticKind::UnknownKind => "unknown_kind",
DiagnosticKind::UnknownRelation => "unknown_relation",
DiagnosticKind::RetiredLinksKey => "retired_links_key",
}
}
}
impl fmt::Display for DiagnosticKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct Diagnostic {
pub kind: DiagnosticKind,
pub field: String,
pub message: String,
pub issue: Option<u32>,
}
impl Diagnostic {
pub fn new(kind: DiagnosticKind, field: impl Into<String>, message: impl Into<String>) -> Self {
Self {
kind,
field: field.into(),
message: message.into(),
issue: None,
}
}
pub fn about(
issue: u32,
kind: DiagnosticKind,
field: impl Into<String>,
message: impl Into<String>,
) -> Self {
Self {
kind,
field: field.into(),
message: message.into(),
issue: Some(issue),
}
}
pub fn self_link(issue: u32) -> Self {
Self::about(
issue,
DiagnosticKind::SelfLink,
"to",
format!("#{issue} cannot block itself: a self-link is not a valid relationship"),
)
}
pub fn missing_target(issue: u32, selector: impl fmt::Display) -> Self {
Self::about(
issue,
DiagnosticKind::MissingTarget,
"to",
format!("issue #{issue} references `{selector}`, which resolves to no issue"),
)
}
pub fn unknown_kind(field: impl Into<String>, message: impl Into<String>) -> Self {
Self::new(DiagnosticKind::UnknownKind, field, message)
}
pub fn unknown_relation(id: &str) -> Self {
Self::new(
DiagnosticKind::UnknownRelation,
"id",
format!("no relationship with id `{id}`"),
)
}
}
impl fmt::Display for Diagnostic {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"{} ({}): {}",
self.kind.as_str(),
self.field,
self.message
)
}
}
#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
pub struct RelationshipValidationResult {
pub errors: Vec<Diagnostic>,
}
impl RelationshipValidationResult {
pub fn clean() -> Self {
Self::default()
}
pub fn with(diagnostic: Diagnostic) -> Self {
Self {
errors: vec![diagnostic],
}
}
pub fn is_clean(&self) -> bool {
self.errors.is_empty()
}
pub fn blocking(&self) -> bool {
!self.errors.is_empty()
}
pub fn has(&self, kind: DiagnosticKind) -> bool {
self.errors.iter().any(|d| d.kind == kind)
}
pub fn merge(&mut self, other: Self) {
self.errors.extend(other.errors);
}
pub fn sort_diagnostics(&mut self) {
self.errors
.sort_by(|a, b| (a.kind, &a.field, &a.message).cmp(&(b.kind, &b.field, &b.message)));
}
}
#[derive(Debug, Clone, Copy)]
pub struct IssueView<'a> {
pub number: u32,
pub title: &'a str,
pub status: &'a str,
pub relationships: &'a [Relationship],
pub has_retired_links_key: bool,
pub parent: Option<u32>,
}
impl<'a> IssueView<'a> {
pub fn new(
number: u32,
title: &'a str,
status: &'a str,
relationships: &'a [Relationship],
) -> Self {
Self {
number,
title,
status,
relationships,
has_retired_links_key: false,
parent: None,
}
}
pub fn with_retired_links_key(mut self, flagged: bool) -> Self {
self.has_retired_links_key = flagged;
self
}
pub fn with_parent(mut self, parent: Option<u32>) -> Self {
self.parent = parent;
self
}
}
impl crate::hierarchy::HierarchyNode for IssueView<'_> {
fn number(&self) -> u32 {
self.number
}
fn title(&self) -> &str {
self.title
}
fn status(&self) -> &str {
self.status
}
fn parent_number(&self) -> Option<u32> {
self.parent
}
}
#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
pub struct ChainNode {
pub number: u32,
pub title: String,
}
impl ChainNode {
pub fn new(number: u32, title: impl Into<String>) -> Self {
Self {
number,
title: title.into(),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
pub struct DependencyChain {
pub root: u32,
pub paths: Vec<Vec<ChainNode>>,
pub truncated: bool,
}
impl DependencyChain {
pub fn nodes(&self) -> Vec<&ChainNode> {
let mut seen = HashSet::new();
self.paths
.iter()
.flatten()
.filter(|n| seen.insert(n.number))
.collect()
}
}
#[derive(Debug, Clone, PartialEq, Eq, Default, Serialize, Deserialize)]
pub struct BlockedState {
pub is_blocked: bool,
pub blockers: Vec<ChainNode>,
pub reason: String,
}
pub const MAX_CHAIN_NODES: usize = 1_000;
#[derive(Debug)]
pub struct RelationshipGraph<'a> {
issues: HashMap<u32, IssueView<'a>>,
issues_by_number: Vec<u32>,
edges: Vec<Relationship>,
by_id: HashMap<RelationshipId, usize>,
by_issue: HashMap<u32, Vec<usize>>,
blocks_out: HashMap<u32, Vec<u32>>,
blocks_in: HashMap<u32, Vec<u32>>,
done_column: String,
validation_passes: std::sync::atomic::AtomicUsize,
}
impl Clone for RelationshipGraph<'_> {
fn clone(&self) -> Self {
Self {
issues: self.issues.clone(),
issues_by_number: self.issues_by_number.clone(),
edges: self.edges.clone(),
by_id: self.by_id.clone(),
by_issue: self.by_issue.clone(),
blocks_out: self.blocks_out.clone(),
blocks_in: self.blocks_in.clone(),
done_column: self.done_column.clone(),
validation_passes: std::sync::atomic::AtomicUsize::new(0),
}
}
}
impl<'a> RelationshipGraph<'a> {
pub fn validation_passes(&self) -> usize {
self.validation_passes
.load(std::sync::atomic::Ordering::Relaxed)
}
pub fn new(issues: &[IssueView<'a>], done_column: &str) -> Self {
let mut issues_by_number: Vec<u32> = issues.iter().map(|i| i.number).collect();
issues_by_number.sort_unstable();
let mut graph = Self {
issues: issues.iter().map(|i| (i.number, *i)).collect(),
issues_by_number,
edges: Vec::new(),
by_id: HashMap::new(),
by_issue: HashMap::new(),
blocks_out: HashMap::new(),
blocks_in: HashMap::new(),
done_column: done_column.to_string(),
validation_passes: std::sync::atomic::AtomicUsize::new(0),
};
graph.rebuild_edges();
graph
}
fn rebuild_edges(&mut self) {
let mut edges: Vec<Relationship> = Vec::new();
for number in &self.issues_by_number {
let view = self.issues[number];
for rel in view.relationships {
let mut stored = rel.clone();
let canonical = stored.canonical();
stored.from = canonical.from;
stored.to = canonical.to;
stored.kind = canonical.kind;
if let Some(target) = self.issues.get(&stored.to) {
stored.refresh_display(target.title);
}
edges.push(stored);
}
}
edges.sort_by(|a, b| (a.kind, a.to, a.from, &a.id).cmp(&(b.kind, b.to, b.from, &b.id)));
self.by_id = edges
.iter()
.enumerate()
.map(|(i, e)| (e.id.clone(), i))
.collect();
self.by_issue = HashMap::new();
self.blocks_out = HashMap::new();
self.blocks_in = HashMap::new();
for (i, edge) in edges.iter().enumerate() {
self.by_issue.entry(edge.from).or_default().push(i);
if edge.to != edge.from {
self.by_issue.entry(edge.to).or_default().push(i);
}
if edge.kind == RelationKind::Blocks && edge.from != edge.to {
self.blocks_out.entry(edge.from).or_default().push(edge.to);
self.blocks_in.entry(edge.to).or_default().push(edge.from);
}
}
for adjacency in [&mut self.blocks_out, &mut self.blocks_in] {
for targets in adjacency.values_mut() {
targets.sort_unstable();
targets.dedup();
}
}
self.edges = edges;
}
pub fn done_column(&self) -> &str {
&self.done_column
}
pub fn issue_count(&self) -> usize {
self.issues_by_number.len()
}
pub fn edge_count(&self) -> usize {
self.edges.len()
}
pub fn issue_numbers(&self) -> &[u32] {
&self.issues_by_number
}
pub fn has_issue(&self, number: u32) -> bool {
self.issues.contains_key(&number)
}
pub fn find_relationship(&self, id: &str) -> Option<&Relationship> {
self.by_id.get(id).map(|i| &self.edges[*i])
}
pub fn find_canonical(&self, from: u32, to: u32, kind: RelationKind) -> Option<&Relationship> {
let canonical = CanonicalEdge::new(from, to, kind);
self.by_issue
.get(&canonical.from)?
.iter()
.map(|i| &self.edges[*i])
.find(|edge| edge.canonical() == canonical)
}
pub fn all_relationships(&self) -> &[Relationship] {
&self.edges
}
pub fn relationships_for(&self, number: u32) -> Vec<&Relationship> {
match self.by_issue.get(&number) {
Some(indices) => indices.iter().map(|i| &self.edges[*i]).collect(),
None => Vec::new(),
}
}
pub fn relationships_of_kind(&self, number: u32, kind: RelationKind) -> Vec<&Relationship> {
self.relationships_for(number)
.into_iter()
.filter(|r| r.kind == kind)
.collect()
}
pub fn blocks(&self, number: u32) -> &[u32] {
self.blocks_out
.get(&number)
.map(Vec::as_slice)
.unwrap_or(&[])
}
pub fn blocked_by(&self, number: u32) -> &[u32] {
self.blocks_in
.get(&number)
.map(Vec::as_slice)
.unwrap_or(&[])
}
pub fn duplicates_of(&self, number: u32) -> Vec<u32> {
let mut targets: Vec<u32> = self
.relationships_of_kind(number, RelationKind::Duplicates)
.into_iter()
.filter(|edge| edge.from == number)
.map(|edge| edge.to)
.collect();
targets.sort_unstable();
targets
}
pub fn related_to(&self, number: u32) -> Vec<u32> {
let mut others: Vec<u32> = self
.relationships_of_kind(number, RelationKind::Related)
.into_iter()
.map(|edge| {
if edge.from == number {
edge.to
} else {
edge.from
}
})
.collect();
others.sort_unstable();
others.dedup();
others
}
pub fn open_blockers(&self, number: u32) -> Vec<ChainNode> {
self.blocked_by(number)
.iter()
.filter(|blocker| self.is_open_blocker(number, **blocker))
.map(|blocker| self.chain_node(*blocker))
.collect()
}
fn is_open_blocker(&self, subject: u32, blocker: u32) -> bool {
if blocker == subject {
return false;
}
let Some(blocker) = self.issues.get(&blocker) else {
return false;
};
self.done_column.is_empty() || blocker.status != self.done_column
}
pub fn blocked_state(&self, number: u32) -> BlockedState {
let blockers = self.open_blockers(number);
let is_blocked = !blockers.is_empty();
BlockedState {
is_blocked,
reason: if is_blocked {
blocked_reason(&blockers)
} else {
String::new()
},
blockers,
}
}
pub fn dependency_chain(&self, root: u32) -> DependencyChain {
let mut chain = DependencyChain {
root,
paths: Vec::new(),
truncated: false,
};
if !self.has_issue(root) {
return chain;
}
let mut visited_nodes = 1usize;
let mut path = vec![self.chain_node(root)];
self.walk_downstream(root, &mut path, &mut chain.paths, &mut visited_nodes);
chain.truncated = visited_nodes >= MAX_CHAIN_NODES;
chain
}
fn walk_downstream(
&self,
node: u32,
path: &mut Vec<ChainNode>,
paths: &mut Vec<Vec<ChainNode>>,
visited_nodes: &mut usize,
) {
let downstream = self.blocks(node);
if downstream.is_empty() {
return;
}
let mut unique: Vec<u32> = Vec::new();
for target in downstream {
if !unique.contains(target) {
unique.push(*target);
}
}
for target in unique {
if *visited_nodes >= MAX_CHAIN_NODES {
return;
}
*visited_nodes += 1;
if path.iter().any(|n| n.number == target) {
continue;
}
path.push(self.chain_node(target));
if self.blocks(target).is_empty() {
paths.push(path.clone());
} else {
self.walk_downstream(target, path, paths, visited_nodes);
path.pop();
}
}
}
fn chain_node(&self, number: u32) -> ChainNode {
match self.issues.get(&number) {
Some(issue) => ChainNode::new(number, issue.title),
None => ChainNode::new(number, String::new()),
}
}
pub fn validate_snapshot(&self) -> RelationshipValidationResult {
let mut result = RelationshipValidationResult::clean();
for number in &self.issues_by_number {
let view = self.issues[number];
if view.has_retired_links_key {
result.errors.push(Diagnostic::about(
*number,
DiagnosticKind::RetiredLinksKey,
"links",
format!(
"#{number} still carries the retired `links:` key, which the typed \
model no longer reads \u{2014} remove the key, then recreate each \
relationship with `tix link <from> <to> --type <kind>` (or the \
`link_issue` tool), where `<kind>` is one of `blocks`, \
`blocked_by`, `duplicates`, or `related`"
),
));
}
}
let mut pair_kind: HashMap<(u32, u32), RelationKind> = HashMap::new();
for edge in &self.edges {
if edge.from == edge.to {
result.errors.push(Diagnostic::self_link(edge.from));
continue;
}
if !self.has_issue(edge.to) {
result
.errors
.push(Diagnostic::missing_target(edge.from, edge.to));
continue;
}
let key = (edge.from, edge.to);
match pair_kind.get(&key) {
Some(existing) if *existing != edge.kind => {
result.errors.push(Diagnostic::about(
edge.from,
DiagnosticKind::ConflictingEdge,
"kind",
format!(
"#{from} → #{to} is already `{existing}`; refusing to store it as `{}` as well",
edge.kind.as_str(),
from = edge.from,
to = edge.to
),
));
}
Some(_) => {}
None => {
pair_kind.insert(key, edge.kind);
}
}
}
result.merge(self.validate_cycles());
result.sort_diagnostics();
result
}
pub fn validate_create(
&self,
from: u32,
to: u32,
kind: RelationKind,
) -> RelationshipValidationResult {
self.validate_authored(from, to, kind, None, Duplicate::Allowed)
}
fn validate_authored(
&self,
from: u32,
to: u32,
kind: RelationKind,
exclude: Option<&str>,
duplicate: Duplicate,
) -> RelationshipValidationResult {
let mut result = RelationshipValidationResult::clean();
let canonical = CanonicalEdge::new(from, to, kind);
if !self.has_issue(from) {
result.errors.push(Diagnostic::missing_target(to, from));
}
if canonical.is_self_link() {
result.errors.push(Diagnostic::self_link(from));
} else if !self.has_issue(to) {
result.errors.push(Diagnostic::missing_target(from, to));
}
if let Some(existing) = self.relationships_for(from).into_iter().find(|r| {
let c = r.canonical();
c.from == canonical.from
&& c.to == canonical.to
&& c.kind != canonical.kind
&& exclude != Some(r.id.as_str())
}) {
result.errors.push(Diagnostic::new(
DiagnosticKind::ConflictingEdge,
"kind",
format!(
"#{} → #{} is already `{}`; refusing to store it as `{}` as well",
canonical.from,
canonical.to,
existing.kind.as_str(),
canonical.kind.as_str()
),
));
}
if let Some(cycle) = self.cycle_if_added(canonical) {
result.errors.push(cycle);
}
if duplicate == Duplicate::Rejected {
if let Some(clash) = self
.relationships_for(from)
.into_iter()
.find(|r| r.canonical() == canonical && exclude != Some(r.id.as_str()))
{
result.errors.push(Diagnostic::new(
DiagnosticKind::ConflictingEdge,
"kind",
format!(
"#{from} already has a `{}` relationship to #{} (`{}`); this edit would store a second one — drop the existing edge or pick a different kind",
canonical.kind.as_str(),
canonical.to,
clash.id
),
));
}
}
result.sort_diagnostics();
result
}
pub fn validate_edit(
&self,
id: &str,
new_to: Option<u32>,
new_kind: Option<RelationKind>,
) -> RelationshipValidationResult {
let Some(existing) = self.find_relationship(id) else {
let mut result = RelationshipValidationResult::clean();
result.errors.push(Diagnostic::unknown_relation(id));
return result;
};
let from = existing.from;
let to = new_to.unwrap_or(existing.to);
let kind = new_kind.unwrap_or(existing.kind);
self.validate_authored(from, to, kind, Some(id), Duplicate::Rejected)
}
fn validate_cycles(&self) -> RelationshipValidationResult {
let mut result = RelationshipValidationResult::clean();
for path in self.cycles() {
result.errors.push(Diagnostic::about(
path[0],
DiagnosticKind::Cycle,
"to",
format!("cycle: {}", render_cycle(&path)),
));
}
result
}
fn cycles(&self) -> Vec<Vec<u32>> {
self.validation_passes
.fetch_add(1, std::sync::atomic::Ordering::Relaxed);
let residue = self.cyclic_residue();
if residue.is_empty() {
return Vec::new();
}
const WHITE: u8 = 0;
const GREY: u8 = 1;
const BLACK: u8 = 2;
let mut color: HashMap<u32, u8> = HashMap::new();
let mut cycles: Vec<Vec<u32>> = Vec::new();
let mut reported: HashSet<Vec<u32>> = HashSet::new();
let mut path: Vec<u32> = Vec::new();
let mut position: HashMap<u32, usize> = HashMap::new();
let mut work: Vec<(u32, usize)> = Vec::new();
for start in &self.issues_by_number {
let start = *start;
if !residue.contains(&start) || color.get(&start) == Some(&BLACK) {
continue;
}
color.insert(start, GREY);
position.insert(start, path.len());
path.push(start);
work.push((start, 0));
while let Some(top) = work.last_mut() {
let (node, cursor) = (top.0, top.1);
let downstream = self.blocks(node);
if cursor < downstream.len() {
top.1 += 1;
let next = downstream[cursor];
if !residue.contains(&next) {
continue;
}
match color.get(&next).copied().unwrap_or(WHITE) {
GREY => {
if let Some(start_at) = position.get(&next) {
let cycle = path[*start_at..].to_vec();
if reported.insert(cycle_key(&cycle)) {
cycles.push(cycle);
}
}
}
WHITE => {
color.insert(next, GREY);
position.insert(next, path.len());
path.push(next);
work.push((next, 0));
}
_ => {}
}
} else {
color.insert(node, BLACK);
position.remove(&node);
path.pop();
work.pop();
}
}
}
cycles
}
fn cyclic_residue(&self) -> HashSet<u32> {
let mut indegree: HashMap<u32, usize> =
self.issues_by_number.iter().map(|n| (*n, 0usize)).collect();
for edge in &self.edges {
if edge.kind != RelationKind::Blocks || edge.from == edge.to {
continue;
}
if !self.has_issue(edge.from) || !self.has_issue(edge.to) {
continue;
}
*indegree.entry(edge.to).or_default() += 1;
}
let mut queue: VecDeque<u32> = indegree
.iter()
.filter(|(_, degree)| **degree == 0)
.map(|(node, _)| *node)
.collect();
while let Some(node) = queue.pop_front() {
for next in self.blocks(node) {
if let Some(degree) = indegree.get_mut(next) {
if *degree > 0 {
*degree -= 1;
if *degree == 0 {
queue.push_back(*next);
}
}
}
}
}
indegree
.into_iter()
.filter(|(_, degree)| *degree > 0)
.map(|(node, _)| node)
.collect()
}
fn cycle_if_added(&self, edge: CanonicalEdge) -> Option<Diagnostic> {
if edge.is_self_link() {
return Some(Diagnostic::self_link(edge.from));
}
if edge.kind != RelationKind::Blocks {
return None;
}
if !self.has_issue(edge.to) {
return None;
}
let path = self.shortest_path(edge.to, edge.from)?;
let mut full = Vec::with_capacity(path.len() + 1);
full.push(edge.from);
full.extend(path);
Some(Diagnostic::new(
DiagnosticKind::Cycle,
"to",
format!("cycle: {}", render_cycle(&full)),
))
}
fn shortest_path(&self, start: u32, goal: u32) -> Option<Vec<u32>> {
if start == goal {
return Some(vec![start]);
}
let mut previous: HashMap<u32, u32> = HashMap::new();
let mut seen: HashSet<u32> = HashSet::new();
let mut queue: std::collections::VecDeque<u32> = std::collections::VecDeque::new();
seen.insert(start);
queue.push_back(start);
while let Some(node) = queue.pop_front() {
for next in self.blocks(node) {
if !seen.insert(*next) {
continue;
}
previous.insert(*next, node);
if *next == goal {
let mut path = vec![goal];
let mut cursor = goal;
while let Some(step) = previous.get(&cursor) {
path.push(*step);
cursor = *step;
}
path.reverse();
return Some(path);
}
queue.push_back(*next);
}
}
None
}
}
pub fn blocked_reason(blockers: &[ChainNode]) -> String {
if blockers.len() == 1 {
let node = &blockers[0];
return format!("Blocked by #{} {}", node.number, node.title)
.trim_end()
.to_string();
}
let list = blockers
.iter()
.map(|n| format!("#{} {}", n.number, n.title).trim_end().to_string())
.collect::<Vec<_>>()
.join(", ");
format!("Blocked by {} issues: {list}", blockers.len())
}
fn render_cycle(path: &[u32]) -> String {
let rendered = path
.iter()
.map(u32::to_string)
.collect::<Vec<_>>()
.join(" -> ");
format!("{rendered} -> #{}", path[0])
}
fn cycle_key(path: &[u32]) -> Vec<u32> {
let Some(min_position) = path
.iter()
.enumerate()
.min_by_key(|(_, n)| **n)
.map(|(i, _)| i)
else {
return path.to_vec();
};
let mut rotated = path[min_position..].to_vec();
rotated.extend_from_slice(&path[..min_position]);
rotated
}
pub fn generate_relationship_id() -> RelationshipId {
use std::hash::{BuildHasher, Hasher};
use std::sync::atomic::{AtomicU64, Ordering};
use std::time::{SystemTime, UNIX_EPOCH};
static COUNTER: AtomicU64 = AtomicU64::new(0);
let millis = SystemTime::now()
.duration_since(UNIX_EPOCH)
.map(|d| d.as_millis())
.unwrap_or(0);
let counter = COUNTER.fetch_add(1, Ordering::Relaxed);
let mut hasher = std::collections::hash_map::RandomState::new().build_hasher();
hasher.write_u128(millis);
hasher.write_u64(counter);
let entropy = hasher.finish();
let mut second = std::collections::hash_map::RandomState::new().build_hasher();
second.write_u64(entropy);
second.write_u64(counter.wrapping_mul(0x9E37_79B9_7F4A_7C15));
let high = second.finish() & 0xFFFF;
let value = (millis << 80u32) | (u128::from(entropy) << 16) | u128::from(high);
format!("rel_{}", crate::id::crockford(value, 26))
}
#[cfg(test)]
mod tests {
#[allow(clippy::wildcard_imports)]
use super::*;
#[derive(Clone)]
struct Owned {
number: u32,
title: String,
status: String,
relationships: Vec<Relationship>,
retired: bool,
}
impl Owned {
fn new(number: u32, title: &str, status: &str) -> Self {
Self {
number,
title: title.to_string(),
status: status.to_string(),
relationships: Vec::new(),
retired: false,
}
}
fn blocking(mut self, to: u32, title: &str) -> Self {
self.relationships.push(Relationship::new(
self.number,
to,
RelationKind::Blocks,
title,
));
self
}
fn push_block(&mut self, to: u32, title: &str) {
self.relationships.push(Relationship::new(
self.number,
to,
RelationKind::Blocks,
title,
));
}
fn with_related(self, to: u32, title: &str) -> Self {
let mut this = self;
this.relationships.push(Relationship::new(
this.number,
to,
RelationKind::Related,
title,
));
this
}
fn with_retired_links_key(mut self) -> Self {
self.retired = true;
self
}
fn view(&self) -> IssueView<'_> {
IssueView::new(self.number, &self.title, &self.status, &self.relationships)
.with_retired_links_key(self.retired)
}
}
fn graph_of<'x>(owned: &'x [Owned], done_column: &str) -> RelationshipGraph<'x> {
let views: Vec<IssueView<'x>> = owned.iter().map(Owned::view).collect();
RelationshipGraph::new(&views, done_column)
}
#[test]
fn relation_kind_has_exactly_four_variants_with_canonical_spellings() {
let spellings: Vec<&str> = RelationKind::ALL.iter().map(|k| k.as_str()).collect();
assert_eq!(spellings, ["blocks", "blocked_by", "duplicates", "related"]);
}
#[test]
fn is_directional_is_false_only_for_related() {
for kind in RelationKind::ALL {
assert_eq!(
kind.is_directional(),
kind != RelationKind::Related,
"{kind} directionality"
);
}
}
#[test]
fn inverse_truth_table_matches_the_contract() {
assert_eq!(
RelationKind::Blocks.inverse(),
Some(RelationKind::BlockedBy)
);
assert_eq!(
RelationKind::BlockedBy.inverse(),
Some(RelationKind::Blocks)
);
assert_eq!(RelationKind::Duplicates.inverse(), None);
assert_eq!(RelationKind::Related.inverse(), None);
}
#[test]
fn from_str_parses_every_canonical_spelling() {
for kind in RelationKind::ALL {
assert_eq!(kind.as_str().parse::<RelationKind>().unwrap(), kind);
}
}
#[test]
fn unknown_kind_is_rejected_and_never_coerced_to_related() {
let err = "depends_on".parse::<RelationKind>().unwrap_err();
assert_eq!(err.kind, DiagnosticKind::UnknownKind);
assert!(err.message.contains("depends_on"));
assert!(err.message.contains("blocks"));
}
#[test]
fn relationship_serde_round_trip_is_stable() {
let rel = Relationship::new(42, 51, RelationKind::Blocks, "Refactor store");
let yaml = serde_yaml::to_string(&rel).unwrap();
let parsed: Relationship = serde_yaml::from_str(&yaml).unwrap();
assert_eq!(rel, parsed);
assert_eq!(serde_yaml::to_string(&parsed).unwrap(), yaml);
}
#[test]
fn relationship_parses_with_display_omitted() {
let yaml = "id: rel_1\nfrom: 1\nto: 2\nkind: blocks\n";
let rel: Relationship = serde_yaml::from_str(yaml).unwrap();
assert_eq!(rel.display, "");
assert!(!serde_yaml::to_string(&rel).unwrap().contains("display"));
}
#[test]
fn display_name_combines_kind_number_and_title() {
assert_eq!(
display_name(RelationKind::Blocks, 42, "Fix flaky test"),
"blocks #42 Fix flaky test"
);
assert_eq!(
display_name(RelationKind::Related, 7, " "),
"related #7",
"a blank title must not leave a trailing space"
);
}
#[test]
fn stable_ids_are_unique_across_a_batch_and_prefixed() {
let mut seen = std::collections::HashSet::new();
for _ in 0..2_000 {
let id = generate_relationship_id();
assert!(id.starts_with("rel_"), "unexpected id shape: {id}");
assert_eq!(id.len(), "rel_".len() + 26, "unexpected id length: {id}");
assert!(
id["rel_".len()..]
.bytes()
.all(|b| crate::id::CROCKFORD.contains(&b)),
"non-Crockford character in {id}"
);
assert!(seen.insert(id), "duplicate relationship id generated");
}
}
#[test]
fn both_spellings_of_a_blocking_pair_normalize_to_one_canonical_edge() {
let forward = normalize(1, 2, RelationKind::Blocks);
let inverse = normalize(1, 2, RelationKind::BlockedBy);
assert_eq!(
forward,
CanonicalEdge {
from: 1,
to: 2,
kind: RelationKind::Blocks
}
);
assert_eq!(
inverse,
CanonicalEdge {
from: 2,
to: 1,
kind: RelationKind::Blocks
},
"blocked_by must swap the endpoints into the canonical blocks form"
);
assert_eq!(
forward.to, inverse.from,
"the two spellings are the same edge"
);
}
#[test]
fn a_persisted_blocking_edge_never_carries_the_blocked_by_kind() {
let stored = Relationship::new(1, 2, RelationKind::BlockedBy, "T");
assert_eq!(stored.kind, RelationKind::Blocks);
assert_eq!((stored.from, stored.to), (2, 1));
}
#[test]
fn normalize_all_deduplicates_both_spellings_and_is_idempotent() {
let authored = [
(1, 2, RelationKind::Blocks),
(2, 1, RelationKind::BlockedBy),
(3, 4, RelationKind::Related),
];
let once = normalize_all(authored);
assert_eq!(once.len(), 2, "the two spellings collapse to one edge");
assert_eq!(
once,
normalize_all(authored),
"normalization is deterministic"
);
assert_eq!(
once,
normalize_all(
once.iter()
.map(|e| (e.from, e.to, e.kind))
.collect::<Vec<_>>()
)
);
}
#[test]
fn related_and_duplicates_never_swap_endpoints() {
for kind in [RelationKind::Related, RelationKind::Duplicates] {
let edge = normalize(1, 2, kind);
assert_eq!((edge.from, edge.to, edge.kind), (1, 2, kind));
}
}
#[test]
fn a_reciprocal_blocking_pair_is_rejected_as_a_cycle() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let b = Owned::new(2, "B", "todo").blocking(1, "A");
let owned = vec![a, b];
let graph = graph_of(&owned, "done");
let result = graph.validate_snapshot();
assert!(
result.has(DiagnosticKind::Cycle),
"expected a cycle diagnostic: {result:?}"
);
assert!(result.blocking(), "a reciprocal pair must be blocking");
}
#[test]
fn a_conflicting_kind_for_the_same_pair_is_reported() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let mut a = a;
a.relationships
.push(Relationship::new(1, 2, RelationKind::Related, "B"));
let owned = vec![a, Owned::new(2, "B", "todo")];
let result = graph_of(&owned, "done").validate_snapshot();
assert!(
result.has(DiagnosticKind::ConflictingEdge),
"expected conflicting_edge: {result:?}"
);
}
#[test]
fn edges_are_returned_from_both_endpoints() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
assert_eq!(graph.relationships_for(1).len(), 1);
assert_eq!(
graph.relationships_for(2).len(),
1,
"the target sees the edge too"
);
}
#[test]
fn ordering_is_stable_across_repeated_builds() {
let a = Owned::new(1, "A", "todo")
.blocking(4, "D")
.blocking(2, "B")
.blocking(3, "C");
let owned = vec![
a,
Owned::new(2, "B", "todo"),
Owned::new(3, "C", "todo"),
Owned::new(4, "D", "todo"),
];
let first: Vec<(RelationKind, u32)> = graph_of(&owned, "done")
.relationships_for(1)
.iter()
.map(|r| (r.kind, r.to))
.collect();
let second: Vec<(RelationKind, u32)> = graph_of(&owned, "done")
.relationships_for(1)
.iter()
.map(|r| (r.kind, r.to))
.collect();
assert_eq!(first, second, "repeated builds must be byte-comparable");
assert_eq!(
first,
vec![
(RelationKind::Blocks, 2),
(RelationKind::Blocks, 3),
(RelationKind::Blocks, 4)
],
"edges are ordered by (kind, target)"
);
}
#[test]
fn related_and_duplicates_never_enter_blocked_adjacency() {
let mut a = Owned::new(1, "A", "todo");
a.relationships
.push(Relationship::new(1, 2, RelationKind::Related, "B"));
a.relationships
.push(Relationship::new(1, 3, RelationKind::Duplicates, "C"));
let owned = vec![a, Owned::new(2, "B", "todo"), Owned::new(3, "C", "todo")];
let graph = graph_of(&owned, "done");
assert!(
graph.blocks(1).is_empty(),
"related/duplicates are not blockers"
);
assert_eq!(graph.blocked_by(2), [] as [u32; 0]);
assert_eq!(graph.blocked_by(3), [] as [u32; 0]);
assert_eq!(graph.duplicates_of(1), vec![3]);
assert_eq!(graph.related_to(1), vec![2]);
}
#[test]
fn an_issue_with_no_edges_yields_empty_results_not_an_error() {
let owned = vec![Owned::new(1, "A", "todo")];
let graph = graph_of(&owned, "done");
assert_eq!(
graph.relationships_for(1),
[] as [&crate::relationships::Relationship; 0]
);
assert_eq!(graph.blocks(1), [] as [u32; 0]);
assert_eq!(graph.blocked_by(1), [] as [u32; 0]);
assert_eq!(
graph.open_blockers(1),
[] as [crate::relationships::ChainNode; 0]
);
assert!(graph.dependencies_are_empty_for_unknown_issue());
}
impl RelationshipGraph<'_> {
fn dependencies_are_empty_for_unknown_issue(&self) -> bool {
self.dependency_chain(9_999).paths.is_empty()
}
}
#[test]
fn an_empty_snapshot_validates_clean() {
let owned = vec![Owned::new(1, "A", "todo")];
let result = graph_of(&owned, "done").validate_snapshot();
assert!(result.is_clean(), "unexpected diagnostics: {result:?}");
assert!(!result.blocking());
}
#[test]
fn self_link_create_is_rejected() {
let owned = vec![Owned::new(1, "A", "todo")];
let result = graph_of(&owned, "done").validate_create(1, 1, RelationKind::Blocks);
assert!(result.has(DiagnosticKind::SelfLink), "{result:?}");
assert!(result.blocking());
}
#[test]
fn missing_target_create_is_rejected() {
let owned = vec![Owned::new(1, "A", "todo")];
let result = graph_of(&owned, "done").validate_create(1, 99, RelationKind::Blocks);
assert!(result.has(DiagnosticKind::MissingTarget), "{result:?}");
}
#[test]
fn validate_create_accepts_both_spellings_of_the_same_pair() {
let owned = vec![Owned::new(1, "A", "todo"), Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
assert!(graph.validate_create(1, 2, RelationKind::Blocks).is_clean());
assert!(
graph
.validate_create(1, 2, RelationKind::BlockedBy)
.is_clean(),
"the inverse spelling is the same edge, not a conflict"
);
}
#[test]
fn editing_an_unknown_relationship_id_is_reported() {
let owned = vec![Owned::new(1, "A", "todo")];
let result = graph_of(&owned, "done").validate_edit("rel_missing", None, None);
assert!(result.has(DiagnosticKind::UnknownRelation), "{result:?}");
}
#[test]
fn a_retired_links_key_is_reported_and_never_read_as_typed_data() {
let owned = vec![
Owned::new(1, "A", "todo").with_retired_links_key(),
Owned::new(2, "B", "todo"),
];
let result = graph_of(&owned, "done").validate_snapshot();
assert!(result.has(DiagnosticKind::RetiredLinksKey), "{result:?}");
assert_eq!(
result
.errors
.iter()
.find(|d| d.kind == DiagnosticKind::RetiredLinksKey)
.map(|d| d.field.as_str()),
Some("links")
);
}
#[test]
fn a_snapshot_with_three_distinct_problems_reports_exactly_three_diagnostics() {
let mut self_linked = Owned::new(1, "A", "todo");
self_linked
.relationships
.push(Relationship::new(3, 3, RelationKind::Blocks, "C"));
let mut dangling = Owned::new(2, "B", "todo");
dangling
.relationships
.push(Relationship::new(2, 404, RelationKind::Blocks, "gone"));
let owned = vec![
self_linked,
dangling,
Owned::new(3, "C", "todo").with_retired_links_key(),
];
let result = graph_of(&owned, "done").validate_snapshot();
assert_eq!(
result.errors.len(),
3,
"expected no duplicate or implied reports: {result:?}"
);
}
#[test]
fn a_three_chain_returns_the_ordered_path() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let b = Owned::new(2, "B", "todo").blocking(3, "C");
let owned = vec![a, b, Owned::new(3, "C", "todo")];
let chain = graph_of(&owned, "done").dependency_chain(1);
assert_eq!(chain.root, 1);
assert_eq!(chain.paths.len(), 1);
assert_eq!(
chain.paths[0].iter().map(|n| n.number).collect::<Vec<_>>(),
vec![1, 2, 3],
"the chain walks upstream from the root toward its blockers"
);
assert!(!chain.truncated);
}
#[test]
fn a_cycle_closing_edge_is_rejected() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let b = Owned::new(2, "B", "todo").blocking(3, "C");
let owned = vec![a, b, Owned::new(3, "C", "todo")];
let result = graph_of(&owned, "done").validate_create(3, 1, RelationKind::Blocks);
assert!(result.has(DiagnosticKind::Cycle), "{result:?}");
assert!(result.blocking());
}
#[test]
fn blocked_state_is_true_only_for_an_open_inbound_blocks_edge() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
let state = graph.blocked_state(2);
assert!(state.is_blocked);
assert_eq!(
state.blockers.iter().map(|n| n.number).collect::<Vec<_>>(),
vec![1]
);
assert!(
state.reason.contains("#1"),
"the reason names the blocker: {}",
state.reason
);
assert!(
!graph.blocked_state(1).is_blocked,
"the blocker is not itself blocked"
);
}
#[test]
fn moving_the_blocker_into_the_configured_done_column_clears_blocked_state() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "shipped");
assert!(
graph.blocked_state(2).is_blocked,
"A is not in the shipped column yet"
);
let mut moved = owned.clone();
moved[0].status = "shipped".to_string();
let after = graph_of(&moved, "shipped");
assert!(
!after.blocked_state(2).is_blocked,
"a blocker in the configured done_column stops blocking"
);
}
#[test]
fn a_blocker_in_a_non_completion_column_keeps_blocking() {
let a = Owned::new(1, "A", "in review").blocking(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "shipped");
assert!(graph.blocked_state(2).is_blocked);
assert_ne!(graph.blocked_state(2).reason, "");
}
#[test]
fn a_dangling_edge_is_diagnosed_but_does_not_freeze_the_issue() {
let mut blocker = Owned::new(1, "A", "todo");
blocker
.relationships
.push(Relationship::new(1, 404, RelationKind::Blocks, "gone"));
let owned = vec![blocker, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
let result = graph.validate_snapshot();
assert!(
result.has(DiagnosticKind::MissingTarget),
"the dangling edge is still reported: {result:?}"
);
assert!(
!graph.blocked_state(2).is_blocked,
"invalid data must not permanently freeze an issue"
);
}
#[test]
fn a_hand_edited_cyclic_file_terminates_instead_of_hanging() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let b = Owned::new(2, "B", "todo").blocking(1, "A");
let owned = vec![a, b];
let graph = graph_of(&owned, "done");
assert!(graph.validate_snapshot().has(DiagnosticKind::Cycle));
let chain = graph.dependency_chain(1);
assert!(
chain.paths.iter().all(|p| p.len() <= owned.len()),
"the visited-set guard must bound every path"
);
}
#[test]
fn a_ten_thousand_edge_graph_validates_in_one_pass() {
const ISSUES: u32 = 2_000;
const PER_ISSUE: u32 = 6;
let mut owned: Vec<Owned> = (0..ISSUES)
.map(|n| Owned::new(n + 1, &format!("Issue {n}"), "todo"))
.collect();
for n in 0..ISSUES {
for k in 1..=PER_ISSUE {
let target = n + k;
if target < ISSUES {
owned[n as usize].push_block(target + 1, "Target");
}
}
}
let graph = graph_of(&owned, "done");
assert!(
graph.edge_count() >= 10_000,
"expected a 10,000-edge graph, built {}",
graph.edge_count()
);
let result = graph.validate_snapshot();
assert!(
result.is_clean(),
"a well-formed graph validates clean: {result:?}"
);
assert_eq!(graph.issue_count(), ISSUES as usize);
assert!(graph.blocked_state(2).is_blocked);
}
#[test]
fn a_ten_thousand_node_chain_does_not_overflow_the_stack() {
const DEPTH: u32 = 10_000;
let mut owned: Vec<Owned> = (0..DEPTH)
.map(|n| Owned::new(n + 1, &format!("Node {n}"), "todo"))
.collect();
for n in 0..DEPTH - 1 {
owned[n as usize].push_block(n + 2, "Next");
}
let graph = graph_of(&owned, "done");
assert!(graph.validate_snapshot().is_clean());
let chain = graph.dependency_chain(1);
assert!(chain.truncated, "the defensive node bound engages");
assert!(
graph
.cycle_if_added(CanonicalEdge {
from: DEPTH,
to: 1,
kind: RelationKind::Blocks
})
.is_some()
);
}
#[test]
fn d1_inverse_spellings_find_the_same_row() {
let owned = vec![
Owned::new(1, "A", "todo").blocking(2, "B"),
Owned::new(2, "B", "todo"),
];
let graph = graph_of(&owned, "done");
let forward = graph
.find_canonical(1, 2, RelationKind::Blocks)
.map(|r| r.id.clone());
let inverse = graph
.find_canonical(2, 1, RelationKind::BlockedBy)
.map(|r| r.id.clone());
assert!(forward.is_some(), "the stored edge must be found");
assert_eq!(
forward, inverse,
"1 blocks 2 and 2 blocked_by 1 name one relationship"
);
assert_ne!(
forward,
graph
.find_canonical(1, 2, RelationKind::BlockedBy)
.map(|r| r.id.clone()),
"1 blocked_by 2 is the inverse of the stored edge, so it must not match"
);
}
#[test]
fn d1_related_is_found_from_either_orientation() {
let mut two = Owned::new(2, "B", "todo");
two.relationships
.push(Relationship::new(2, 1, RelationKind::Related, "A"));
let owned = vec![Owned::new(1, "A", "todo"), two];
let graph = graph_of(&owned, "done");
let a = graph
.find_canonical(1, 2, RelationKind::Related)
.map(|r| r.id.clone());
let b = graph
.find_canonical(2, 1, RelationKind::Related)
.map(|r| r.id.clone());
assert!(a.is_some(), "related is order-normalized, so it is found");
assert_eq!(a, b);
}
#[test]
fn d1_a_self_link_or_unrelated_pair_does_not_match() {
let owned = vec![
Owned::new(1, "A", "todo").blocking(2, "B"),
Owned::new(2, "B", "todo"),
Owned::new(3, "C", "todo"),
];
let graph = graph_of(&owned, "done");
assert!(graph.find_canonical(1, 1, RelationKind::Blocks).is_none());
assert!(graph.find_canonical(1, 3, RelationKind::Blocks).is_none());
assert!(graph.find_canonical(3, 1, RelationKind::Blocks).is_none());
assert!(graph.find_canonical(1, 2, RelationKind::Related).is_none());
assert!(
graph.find_canonical(1, 2, RelationKind::Blocks).is_some(),
"the real edge still resolves"
);
}
#[test]
fn d1_redundant_rows_resolve_to_the_same_row_every_time() {
let one = Owned::new(1, "A", "todo").with_related(2, "B");
let two = Owned::new(2, "B", "todo").with_related(1, "A");
let owned = vec![one, two];
let first = graph_of(&owned, "done")
.find_canonical(1, 2, RelationKind::Related)
.map(|r| r.id.clone());
let second = graph_of(&owned, "done")
.find_canonical(1, 2, RelationKind::Related)
.map(|r| r.id.clone());
assert!(first.is_some());
assert_eq!(first, second, "the answer must be stable, not arbitrary");
}
#[test]
fn d1_an_unknown_pair_returns_none() {
let owned = vec![Owned::new(1, "A", "todo")];
let graph = graph_of(&owned, "done");
assert!(graph.find_canonical(1, 404, RelationKind::Blocks).is_none());
assert!(graph.find_canonical(404, 1, RelationKind::Blocks).is_none());
}
#[test]
fn p1_related_reads_as_one_association_across_orientations() {
let one = Owned::new(1, "A", "todo").with_related(2, "B");
let two = Owned::new(2, "B", "todo").with_related(1, "A");
let owned = vec![one, two];
let graph = graph_of(&owned, "done");
assert_eq!(graph.related_to(1), vec![2], "one association, not two");
assert_eq!(graph.related_to(2), vec![1]);
assert_eq!(
normalize_all([(1, 2, RelationKind::Related), (2, 1, RelationKind::Related),]).len(),
1,
"both authorings normalize to one canonical edge"
);
}
#[test]
fn a3_no_stored_relationship_id_silently_stops_resolving() {
let one = Owned::new(1, "A", "todo").with_related(2, "B");
let two = Owned::new(2, "B", "todo").with_related(1, "A");
let owned = vec![one, two];
let graph = graph_of(&owned, "done");
let ids: Vec<String> = graph
.all_relationships()
.iter()
.filter(|r| r.kind == RelationKind::Related)
.map(|r| r.id.clone())
.collect();
assert_eq!(ids.len(), 2, "both stored rows are retained");
for id in &ids {
assert!(
graph.find_relationship(id).is_some(),
"stored id {id} must still resolve"
);
assert!(
!graph
.validate_edit(id, None, None)
.has(DiagnosticKind::UnknownRelation),
"editing by a stored id must not report it unknown"
);
}
}
#[test]
fn a3_the_blocked_adjacency_does_not_repeat_a_neighbour() {
let mut one = Owned::new(1, "A", "todo");
for _ in 0..3 {
one.push_block(2, "B");
}
let owned = vec![one, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
assert_eq!(graph.blocks(1), &[2], "no repeated neighbour");
assert_eq!(graph.blocked_by(2), &[1], "no repeated blocker");
assert_eq!(
graph.blocked_state(2).blockers.len(),
1,
"one blocker is reported once, not once per stored row"
);
}
#[test]
fn c_an_unconfigured_done_column_fails_closed() {
let mut one = Owned::new(1, "A", "");
one.push_block(2, "B");
let owned = vec![one, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "");
assert!(
graph.blocked_state(2).is_blocked,
"an unconfigured completion column must not mark anything done"
);
}
#[test]
fn p1_duplicates_orientation_is_preserved() {
assert_eq!(
normalize_all([
(1, 2, RelationKind::Duplicates),
(2, 1, RelationKind::Duplicates),
])
.len(),
2
);
}
#[test]
fn p2_an_edit_cannot_land_on_a_triple_another_edge_occupies() {
let mut a = Owned::new(1, "A", "todo");
a.push_block(2, "B");
a.relationships
.push(Relationship::new(1, 2, RelationKind::Related, "B"));
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
let blocks_id = graph
.relationships_for(1)
.iter()
.find(|r| r.kind == RelationKind::Blocks)
.expect("a blocks edge")
.id
.clone();
let res = graph.validate_edit(&blocks_id, None, Some(RelationKind::Related));
assert!(
res.has(DiagnosticKind::ConflictingEdge),
"re-kinding onto an occupied triple must be rejected: {res:?}"
);
assert!(
res.errors
.iter()
.any(|d| d.message.contains("would store a second one")),
"the message must name the duplicate case: {res:?}"
);
}
#[test]
fn p2_creating_an_edge_that_already_exists_stays_idempotent() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
assert!(
graph.validate_create(1, 2, RelationKind::Blocks).is_clean(),
"re-asserting an existing edge is the idempotent path"
);
}
#[test]
fn p3_p4_the_other_endpoint_is_returned_in_both_orientations() {
let mut two = Owned::new(2, "B", "todo");
two.relationships
.push(Relationship::new(2, 1, RelationKind::Related, "A"));
two.relationships
.push(Relationship::new(2, 1, RelationKind::Duplicates, "A"));
let owned = vec![Owned::new(1, "A", "todo"), two];
let graph = graph_of(&owned, "done");
assert_eq!(graph.related_to(1), vec![2], "never the subject itself");
assert_eq!(graph.related_to(2), vec![1]);
assert!(
graph.duplicates_of(1).is_empty(),
"a directional edge pointing at #1 does not mean #1 duplicates it: {:?}",
graph.duplicates_of(1)
);
assert_eq!(graph.duplicates_of(2), vec![1]);
}
#[test]
fn p5_the_blocked_adjacency_never_contains_the_subject() {
let mut a = Owned::new(1, "A", "todo");
a.relationships
.push(Relationship::new(1, 1, RelationKind::Blocks, "A"));
a.push_block(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
for number in [1, 2] {
assert!(
!graph.blocked_by(number).contains(&number),
"issue #{number} must never appear in its own inbound blocks adjacency"
);
}
}
#[test]
fn r1_display_is_refreshed_when_the_target_is_renamed() {
let a = Owned::new(1, "A", "todo").blocking(2, "Old title");
let owned = vec![a, Owned::new(2, "New title", "todo")];
let graph = graph_of(&owned, "done");
assert_eq!(
graph.relationships_for(1)[0].display,
"blocks #2 New title",
"a persisted display must not outlive the title it was built from"
);
}
#[test]
fn r1_a_dangling_edge_keeps_its_persisted_display() {
let mut a = Owned::new(1, "A", "todo");
a.relationships
.push(Relationship::new(1, 404, RelationKind::Blocks, "gone"));
let owned = vec![a];
assert_eq!(
graph_of(&owned, "done").relationships_for(1)[0].display,
"blocks #404 gone"
);
}
#[test]
fn r2_a_self_link_is_reported_once_not_twice() {
let mut a = Owned::new(1, "A", "todo");
a.relationships
.push(Relationship::new(1, 1, RelationKind::Blocks, "A"));
let owned = vec![a];
let graph = graph_of(&owned, "done");
assert_eq!(graph.edge_count(), 1);
assert_eq!(
graph.relationships_for(1).len(),
1,
"a self-link has one endpoint, so it must be registered once"
);
}
#[test]
fn r3_an_issue_is_never_blocked_by_itself() {
let mut a = Owned::new(1, "A", "todo");
a.relationships
.push(Relationship::new(1, 1, RelationKind::Blocks, "A"));
let owned = vec![a];
let graph = graph_of(&owned, "done");
assert!(graph.validate_snapshot().has(DiagnosticKind::SelfLink));
assert_eq!(graph.blocks(1), [] as [u32; 0]);
let state = graph.blocked_state(1);
assert!(!state.is_blocked, "an issue must not block itself");
assert_eq!(state.reason, "");
}
#[test]
fn r4_validate_edit_does_not_hide_a_pre_existing_conflict() {
let mut a = Owned::new(1, "A", "todo");
a.push_block(2, "B");
a.relationships
.push(Relationship::new(1, 2, RelationKind::Related, "B"));
let owned = vec![a, Owned::new(2, "B", "todo")];
let graph = graph_of(&owned, "done");
let blocks_id = graph
.relationships_for(1)
.iter()
.find(|r| r.kind == RelationKind::Blocks)
.expect("a blocks edge")
.id
.clone();
assert!(
graph
.validate_snapshot()
.has(DiagnosticKind::ConflictingEdge)
);
let edit = graph.validate_edit(&blocks_id, None, None);
assert!(
edit.has(DiagnosticKind::ConflictingEdge),
"editing an unrelated field must not return a clean verdict on corrupt data: {edit:?}"
);
}
#[test]
fn r4_an_edit_does_not_conflict_with_itself() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let owned = vec![a, Owned::new(2, "B", "todo"), Owned::new(3, "C", "todo")];
let graph = graph_of(&owned, "done");
let id = graph.relationships_for(1)[0].id.clone();
assert!(
graph.validate_edit(&id, None, None).is_clean(),
"an edge never conflicts with itself"
);
assert!(
graph.validate_edit(&id, Some(3), None).is_clean(),
"retargeting to an unrelated issue is not a conflict"
);
}
#[test]
fn every_contract_diagnostic_kind_exists_with_its_exact_name() {
let names: Vec<&str> = [
DiagnosticKind::SelfLink,
DiagnosticKind::MissingTarget,
DiagnosticKind::ConflictingEdge,
DiagnosticKind::Cycle,
DiagnosticKind::UnknownKind,
DiagnosticKind::UnknownRelation,
DiagnosticKind::RetiredLinksKey,
]
.iter()
.map(|k| k.as_str())
.collect();
assert_eq!(
names,
[
"self_link",
"missing_target",
"conflicting_edge",
"cycle",
"unknown_kind",
"unknown_relation",
"retired_links_key"
]
);
}
#[test]
fn validate_snapshot_never_returns_an_err() {
let owned = vec![Owned::new(1, "A", "todo").with_retired_links_key()];
let result: RelationshipValidationResult = graph_of(&owned, "done").validate_snapshot();
assert!(result.blocking());
}
#[test]
fn diagnostics_sort_deterministically() {
let mut a = RelationshipValidationResult::with(Diagnostic::self_link(1));
a.merge(RelationshipValidationResult::with(
Diagnostic::unknown_relation("rel_x"),
));
let mut b = a.clone();
b.sort_diagnostics();
a.sort_diagnostics();
assert_eq!(a, b);
}
#[test]
fn blocked_reason_is_shared_by_every_surface() {
let single = vec![ChainNode::new(1, "A")];
assert_eq!(blocked_reason(&single), "Blocked by #1 A");
let many = vec![ChainNode::new(1, "A"), ChainNode::new(2, "B")];
assert_eq!(blocked_reason(&many), "Blocked by 2 issues: #1 A, #2 B");
}
#[test]
fn cycle_paths_are_reported_once_regardless_of_starting_node() {
let a = Owned::new(1, "A", "todo").blocking(2, "B");
let b = Owned::new(2, "B", "todo").blocking(3, "C");
let c = Owned::new(3, "C", "todo").blocking(1, "A");
let owned = vec![a, b, c];
let result = graph_of(&owned, "done").validate_snapshot();
let cycles: Vec<&Diagnostic> = result
.errors
.iter()
.filter(|d| d.kind == DiagnosticKind::Cycle)
.collect();
assert_eq!(
cycles.len(),
1,
"one distinct cycle, one diagnostic: {result:?}"
);
}
#[test]
fn hand_edited_blocked_by_persisted_edges_still_block() {
let mut owner = Owned::new(2, "B", "todo");
owner.relationships.push(Relationship {
id: "rel_hand".to_string(),
from: 1,
to: 2,
kind: RelationKind::BlockedBy,
display: String::new(),
});
let owned = vec![Owned::new(1, "A", "todo"), owner];
let graph = graph_of(&owned, "done");
assert!(
graph.blocked_state(1).is_blocked,
"the normalized adjacency must still carry the edge"
);
assert_eq!(graph.blocks(2), &[1], "stored in canonical blocks form");
}
}