use std::collections::{BTreeMap, BTreeSet};
use agentstategraph::RepoError;
use agentstategraph_core::ObjectId;
use serde_json::{Map, Value};
use crate::error::TaskStoreError;
use crate::paths;
use crate::store::TaskStore;
use crate::types::TaskId;
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Renumbering {
pub renamed: BTreeMap<String, Vec<(TaskId, TaskId)>>,
pub plan_conflicts: Vec<String>,
pub commits: Vec<ObjectId>,
}
impl Renumbering {
pub fn is_empty(&self) -> bool {
self.renamed.is_empty() && self.plan_conflicts.is_empty()
}
pub fn new_id(&self, plan: &str, old: &TaskId) -> Option<&TaskId> {
self.renamed
.get(plan)?
.iter()
.find(|(from, _)| from == old)
.map(|(_, to)| to)
}
}
fn task_entries(plan: &Value) -> impl Iterator<Item = (&String, &Value)> {
plan.as_object()
.into_iter()
.flatten()
.filter(|(key, _)| key.as_str() != paths::META_KEY)
}
fn same_task(a: &Value, b: &Value) -> bool {
a.get("created_at") == b.get("created_at") && a.get("created_by") == b.get("created_by")
}
fn number(id: &str) -> Option<u32> {
TaskId(id.to_string()).number().ok()
}
fn plan_moves(ours: &Value, theirs: &Value, base: Option<&Value>) -> Vec<(TaskId, TaskId)> {
let base_ids: BTreeSet<&str> = base
.map(|b| task_entries(b).map(|(k, _)| k.as_str()).collect())
.unwrap_or_default();
let theirs_tasks: BTreeMap<&str, &Value> =
task_entries(theirs).map(|(k, v)| (k.as_str(), v)).collect();
let mut colliding: Vec<&str> = task_entries(ours)
.filter(|(id, _)| !base_ids.contains(id.as_str()))
.filter(|(id, task)| {
theirs_tasks
.get(id.as_str())
.is_some_and(|their| !same_task(task, their))
})
.map(|(id, _)| id.as_str())
.collect();
if colliding.is_empty() {
return Vec::new();
}
colliding.sort_by_key(|id| (number(id), id.to_string()));
let highest = task_entries(ours)
.chain(task_entries(theirs))
.filter_map(|(id, _)| number(id))
.max()
.unwrap_or(0);
colliding
.into_iter()
.enumerate()
.map(|(i, id)| (TaskId(id.to_string()), TaskId::new(highest + 1 + i as u32)))
.collect()
}
fn apply_moves(plan: &Value, moves: &[(TaskId, TaskId)]) -> Value {
let rename = |id: &str| -> Option<String> {
moves
.iter()
.find(|(from, _)| from.as_str() == id)
.map(|(_, to)| to.as_str().to_string())
};
let mut out = Map::new();
for (key, value) in plan.as_object().into_iter().flatten() {
if key == paths::META_KEY {
out.insert(key.clone(), value.clone());
continue;
}
let mut task = value.clone();
if let Some(fields) = task.as_object_mut() {
if let Some(Value::String(parent)) = fields.get("parent_id")
&& let Some(to) = rename(parent)
{
fields.insert("parent_id".into(), Value::String(to));
}
if let Some(Value::Array(blockers)) = fields.get_mut("blocked_by") {
for b in blockers.iter_mut() {
if let Some(to) = b.as_str().and_then(rename) {
*b = Value::String(to);
}
}
}
}
let new_key = rename(key).unwrap_or_else(|| key.clone());
if let Some(fields) = task.as_object_mut()
&& new_key != *key
{
fields.insert("id".into(), Value::String(new_key.clone()));
}
out.insert(new_key, task);
}
Value::Object(out)
}
fn read(store: &TaskStore, ref_name: &str, path: &str) -> Result<Option<Value>, TaskStoreError> {
match store.repo().get_json(ref_name, path) {
Ok(v) => Ok(Some(v)),
Err(RepoError::Tree(agentstategraph::tree::TreeError::PathNotFound(_))) => Ok(None),
Err(e) => Err(e.into()),
}
}
impl TaskStore {
pub fn renumber_before_merge(
&self,
ref_name: &str,
theirs: &str,
) -> Result<Renumbering, TaskStoreError> {
let mut report = Renumbering::default();
let Some(our_plans) = read(self, ref_name, self.prefix())? else {
return Ok(report);
};
let Some(their_plans) = read(self, theirs, self.prefix())? else {
return Ok(report);
};
let names: Vec<String> = our_plans
.as_object()
.into_iter()
.flatten()
.filter(|(name, _)| their_plans.get(name.as_str()).is_some())
.map(|(name, _)| name.clone())
.collect();
for name in names {
let root = paths::plan_root(self.prefix(), &name);
for attempt in 0..Self::MAX_CAS_RETRIES {
let head = self.repo().head(ref_name)?;
let (Some(ours), Some(theirs_plan)) =
(read(self, ref_name, &root)?, read(self, theirs, &root)?)
else {
break;
};
let base = self
.repo()
.get_json_at_merge_base(theirs, ref_name, &root)?;
if base.is_none() && ours.get(paths::META_KEY) != theirs_plan.get(paths::META_KEY) {
report.plan_conflicts.push(name.clone());
break;
}
let moves = plan_moves(&ours, &theirs_plan, base.as_ref());
if moves.is_empty() {
break;
}
let listed: Vec<String> = moves.iter().map(|(a, b)| format!("{a}→{b}")).collect();
let renumbered = apply_moves(&ours, &moves);
match self.repo().set_json_cas(
ref_name,
head,
&root,
&renumbered,
self.commit_opts(format!(
"Renumber tasks in {name} before merging {theirs}: {}",
listed.join(", ")
)),
) {
Ok(commit) => {
report.commits.push(commit);
report.renamed.insert(name.clone(), moves);
break;
}
Err(RepoError::WriteConflict) if attempt + 1 < Self::MAX_CAS_RETRIES => {
continue;
}
Err(RepoError::WriteConflict) => return Err(TaskStoreError::WriteConflict),
Err(e) => return Err(e.into()),
}
}
}
Ok(report)
}
}
#[cfg(test)]
mod tests {
use super::*;
use serde_json::json;
fn task(id: &str, at: &str, blocked_by: &[&str], parent: Option<&str>) -> Value {
json!({
"id": id, "title": id, "created_at": at, "created_by": "a",
"blocked_by": blocked_by, "parent_id": parent,
})
}
#[test]
fn only_new_colliding_tasks_move_past_both_sides() {
let base = json!({"_meta": {}, "t-001": task("t-001", "0", &[], None)});
let ours = json!({
"_meta": {},
"t-001": task("t-001", "0", &["t-002"], None),
"t-002": task("t-002", "ours", &[], None),
"t-003": task("t-003", "ours2", &["t-002"], Some("t-002")),
});
let theirs = json!({
"_meta": {},
"t-001": task("t-001", "0", &[], None),
"t-002": task("t-002", "theirs", &[], None),
});
let moves = plan_moves(&ours, &theirs, Some(&base));
assert_eq!(moves, vec![(TaskId::new(2), TaskId::new(4))]);
let out = apply_moves(&ours, &moves);
assert!(out.get("t-002").is_none());
assert_eq!(out["t-004"]["id"], "t-004");
assert_eq!(out["t-003"]["blocked_by"], json!(["t-004"]));
assert_eq!(out["t-003"]["parent_id"], "t-004");
assert_eq!(
out["t-001"]["blocked_by"],
json!(["t-004"]),
"a base task's reference to it too"
);
}
#[test]
fn a_task_both_sides_hold_is_not_a_collision() {
let same = task("t-002", "x", &[], None);
let ours = json!({"_meta": {}, "t-002": same.clone()});
let theirs = json!({"_meta": {}, "t-002": same});
assert!(plan_moves(&ours, &theirs, None).is_empty());
}
}