1use std::collections::{BTreeMap, BTreeSet};
27
28use agentstategraph::RepoError;
29use agentstategraph_core::ObjectId;
30use serde_json::{Map, Value};
31
32use crate::error::TaskStoreError;
33use crate::paths;
34use crate::store::TaskStore;
35use crate::types::TaskId;
36
37#[derive(Debug, Clone, Default, PartialEq, Eq)]
39pub struct Renumbering {
40 pub renamed: BTreeMap<String, Vec<(TaskId, TaskId)>>,
42 pub plan_conflicts: Vec<String>,
45 pub commits: Vec<ObjectId>,
47}
48
49impl Renumbering {
50 pub fn is_empty(&self) -> bool {
51 self.renamed.is_empty() && self.plan_conflicts.is_empty()
52 }
53
54 pub fn new_id(&self, plan: &str, old: &TaskId) -> Option<&TaskId> {
56 self.renamed
57 .get(plan)?
58 .iter()
59 .find(|(from, _)| from == old)
60 .map(|(_, to)| to)
61 }
62}
63
64fn task_entries(plan: &Value) -> impl Iterator<Item = (&String, &Value)> {
66 plan.as_object()
67 .into_iter()
68 .flatten()
69 .filter(|(key, _)| key.as_str() != paths::META_KEY)
70}
71
72fn same_task(a: &Value, b: &Value) -> bool {
75 a.get("created_at") == b.get("created_at") && a.get("created_by") == b.get("created_by")
76}
77
78fn number(id: &str) -> Option<u32> {
79 TaskId(id.to_string()).number().ok()
80}
81
82fn plan_moves(ours: &Value, theirs: &Value, base: Option<&Value>) -> Vec<(TaskId, TaskId)> {
85 let base_ids: BTreeSet<&str> = base
86 .map(|b| task_entries(b).map(|(k, _)| k.as_str()).collect())
87 .unwrap_or_default();
88 let theirs_tasks: BTreeMap<&str, &Value> =
89 task_entries(theirs).map(|(k, v)| (k.as_str(), v)).collect();
90 let mut colliding: Vec<&str> = task_entries(ours)
91 .filter(|(id, _)| !base_ids.contains(id.as_str()))
92 .filter(|(id, task)| {
93 theirs_tasks
94 .get(id.as_str())
95 .is_some_and(|their| !same_task(task, their))
96 })
97 .map(|(id, _)| id.as_str())
98 .collect();
99 if colliding.is_empty() {
100 return Vec::new();
101 }
102 colliding.sort_by_key(|id| (number(id), id.to_string()));
103 let highest = task_entries(ours)
104 .chain(task_entries(theirs))
105 .filter_map(|(id, _)| number(id))
106 .max()
107 .unwrap_or(0);
108 colliding
109 .into_iter()
110 .enumerate()
111 .map(|(i, id)| (TaskId(id.to_string()), TaskId::new(highest + 1 + i as u32)))
112 .collect()
113}
114
115fn apply_moves(plan: &Value, moves: &[(TaskId, TaskId)]) -> Value {
118 let rename = |id: &str| -> Option<String> {
119 moves
120 .iter()
121 .find(|(from, _)| from.as_str() == id)
122 .map(|(_, to)| to.as_str().to_string())
123 };
124 let mut out = Map::new();
125 for (key, value) in plan.as_object().into_iter().flatten() {
126 if key == paths::META_KEY {
127 out.insert(key.clone(), value.clone());
128 continue;
129 }
130 let mut task = value.clone();
131 if let Some(fields) = task.as_object_mut() {
132 if let Some(Value::String(parent)) = fields.get("parent_id")
133 && let Some(to) = rename(parent)
134 {
135 fields.insert("parent_id".into(), Value::String(to));
136 }
137 if let Some(Value::Array(blockers)) = fields.get_mut("blocked_by") {
138 for b in blockers.iter_mut() {
139 if let Some(to) = b.as_str().and_then(rename) {
140 *b = Value::String(to);
141 }
142 }
143 }
144 }
145 let new_key = rename(key).unwrap_or_else(|| key.clone());
146 if let Some(fields) = task.as_object_mut()
147 && new_key != *key
148 {
149 fields.insert("id".into(), Value::String(new_key.clone()));
150 }
151 out.insert(new_key, task);
152 }
153 Value::Object(out)
154}
155
156fn read(store: &TaskStore, ref_name: &str, path: &str) -> Result<Option<Value>, TaskStoreError> {
157 match store.repo().get_json(ref_name, path) {
158 Ok(v) => Ok(Some(v)),
159 Err(RepoError::Tree(agentstategraph::tree::TreeError::PathNotFound(_))) => Ok(None),
160 Err(e) => Err(e.into()),
161 }
162}
163
164impl TaskStore {
165 pub fn renumber_before_merge(
171 &self,
172 ref_name: &str,
173 theirs: &str,
174 ) -> Result<Renumbering, TaskStoreError> {
175 let mut report = Renumbering::default();
176 let Some(our_plans) = read(self, ref_name, self.prefix())? else {
177 return Ok(report);
178 };
179 let Some(their_plans) = read(self, theirs, self.prefix())? else {
180 return Ok(report);
181 };
182 let names: Vec<String> = our_plans
183 .as_object()
184 .into_iter()
185 .flatten()
186 .filter(|(name, _)| their_plans.get(name.as_str()).is_some())
187 .map(|(name, _)| name.clone())
188 .collect();
189
190 for name in names {
191 let root = paths::plan_root(self.prefix(), &name);
192 for attempt in 0..Self::MAX_CAS_RETRIES {
193 let head = self.repo().head(ref_name)?;
194 let (Some(ours), Some(theirs_plan)) =
195 (read(self, ref_name, &root)?, read(self, theirs, &root)?)
196 else {
197 break;
198 };
199 let base = self
200 .repo()
201 .get_json_at_merge_base(theirs, ref_name, &root)?;
202 if base.is_none() && ours.get(paths::META_KEY) != theirs_plan.get(paths::META_KEY) {
203 report.plan_conflicts.push(name.clone());
204 break;
205 }
206 let moves = plan_moves(&ours, &theirs_plan, base.as_ref());
207 if moves.is_empty() {
208 break;
209 }
210 let listed: Vec<String> = moves.iter().map(|(a, b)| format!("{a}→{b}")).collect();
211 let renumbered = apply_moves(&ours, &moves);
212 match self.repo().set_json_cas(
213 ref_name,
214 head,
215 &root,
216 &renumbered,
217 self.commit_opts(format!(
218 "Renumber tasks in {name} before merging {theirs}: {}",
219 listed.join(", ")
220 )),
221 ) {
222 Ok(commit) => {
223 report.commits.push(commit);
224 report.renamed.insert(name.clone(), moves);
225 break;
226 }
227 Err(RepoError::WriteConflict) if attempt + 1 < Self::MAX_CAS_RETRIES => {
228 continue;
229 }
230 Err(RepoError::WriteConflict) => return Err(TaskStoreError::WriteConflict),
231 Err(e) => return Err(e.into()),
232 }
233 }
234 }
235 Ok(report)
236 }
237}
238
239#[cfg(test)]
240mod tests {
241 use super::*;
242 use serde_json::json;
243
244 fn task(id: &str, at: &str, blocked_by: &[&str], parent: Option<&str>) -> Value {
245 json!({
246 "id": id, "title": id, "created_at": at, "created_by": "a",
247 "blocked_by": blocked_by, "parent_id": parent,
248 })
249 }
250
251 #[test]
252 fn only_new_colliding_tasks_move_past_both_sides() {
253 let base = json!({"_meta": {}, "t-001": task("t-001", "0", &[], None)});
254 let ours = json!({
255 "_meta": {},
256 "t-001": task("t-001", "0", &["t-002"], None),
257 "t-002": task("t-002", "ours", &[], None),
258 "t-003": task("t-003", "ours2", &["t-002"], Some("t-002")),
259 });
260 let theirs = json!({
261 "_meta": {},
262 "t-001": task("t-001", "0", &[], None),
263 "t-002": task("t-002", "theirs", &[], None),
264 });
265 let moves = plan_moves(&ours, &theirs, Some(&base));
266 assert_eq!(moves, vec![(TaskId::new(2), TaskId::new(4))]);
267 let out = apply_moves(&ours, &moves);
268 assert!(out.get("t-002").is_none());
269 assert_eq!(out["t-004"]["id"], "t-004");
270 assert_eq!(out["t-003"]["blocked_by"], json!(["t-004"]));
271 assert_eq!(out["t-003"]["parent_id"], "t-004");
272 assert_eq!(
273 out["t-001"]["blocked_by"],
274 json!(["t-004"]),
275 "a base task's reference to it too"
276 );
277 }
278
279 #[test]
280 fn a_task_both_sides_hold_is_not_a_collision() {
281 let same = task("t-002", "x", &[], None);
282 let ours = json!({"_meta": {}, "t-002": same.clone()});
283 let theirs = json!({"_meta": {}, "t-002": same});
284 assert!(plan_moves(&ours, &theirs, None).is_empty());
285 }
286}