Skip to main content

agentstategraph_tasks/
renumber.rs

1//! Merge-safe task ids (DESIGN.md Plan G t-010).
2//!
3//! A plan mints `t-NNN` ids one past the highest it holds, so two stores
4//! that add tasks to one plan while apart mint the same ids. Before merging
5//! the other side in, [`TaskStore::renumber_before_merge`] moves this side's
6//! colliding tasks past every id either side uses, and rewrites the
7//! `blocked_by` and `parent_id` references to them, in one commit per plan.
8//!
9//! Like a rebase, it only ever moves work the other side hasn't seen: a task
10//! already in the two sides' merge base was pushed or pulled, and keeps its
11//! id. A task both sides hold with the same creation (time and author) is
12//! the same task, not a collision. A plan both sides created apart, under
13//! one name, is reported as a conflict and left alone.
14//!
15//! Pulling with renumbering, for a store whose tasks live in `tasks`:
16//!
17//! ```ignore
18//! repo.fetch("hub", &remote, &["main"])?;
19//! let renumbered = tasks.renumber_before_merge("main", &tracking_ref("hub", "main"))?;
20//! repo.merge_fetched("hub", "main", options)?;
21//! ```
22//!
23//! An embedder that refers to tasks from elsewhere (links from sessions,
24//! say) rewrites those from [`Renumbering::renamed`].
25
26use 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/// What [`TaskStore::renumber_before_merge`] did.
38#[derive(Debug, Clone, Default, PartialEq, Eq)]
39pub struct Renumbering {
40    /// Per plan, each moved task's old id and new one.
41    pub renamed: BTreeMap<String, Vec<(TaskId, TaskId)>>,
42    /// Plans both sides created apart under the same name. They're left
43    /// as they are; merging them conflicts.
44    pub plan_conflicts: Vec<String>,
45    /// The commits that moved tasks, one per plan.
46    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    /// The id `old` in `plan` now has, if it moved.
55    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
64/// A plan's entries other than its metadata: its tasks, by id.
65fn 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
72/// Whether two versions of a task are one task: created at the same time
73/// by the same author.
74fn 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
82/// What to move in one plan: this side's version of it, the other side's,
83/// and their merge base's (`None` if the plan wasn't there).
84fn 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
115/// `plan` with each task in `moves` under its new id, and every reference
116/// to a moved task rewritten.
117fn 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    /// Before merging `theirs` into `ref_name`, renumber the tasks this
166    /// side added that collide with ones `theirs` added, as the
167    /// [module docs](crate::renumber) describe. `theirs` is typically a
168    /// remote-tracking ref after a fetch. Does nothing when nothing
169    /// collides.
170    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}