1use crate::{
2 Error, ExGuid,
3 active::{ActivePage, Changes},
4 create::{current_timestamps, properties},
5 document::{Kind, Revision},
6 edit::{editable_parents, update_title},
7 write::{PropertyObject, fresh_guid},
8};
9use std::{
10 collections::{BTreeMap, BTreeSet},
11 sync::Arc,
12};
13
14fn invalid(message: &'static str) -> Error {
15 Error { offset: 0, message }
16}
17
18#[derive(Debug, Clone, PartialEq)]
19enum Placement {
20 Delete,
21 Move {
22 parent: ExGuid,
23 before: Option<ExGuid>,
24 },
25}
26
27/// An atomic subtree move or deletion on one active page.
28#[derive(Debug, Clone, PartialEq)]
29pub(crate) struct TreeEdit {
30 guid: [u8; 16],
31 object: ExGuid,
32 placement: Placement,
33 author: String,
34}
35
36impl TreeEdit {
37 /// Removes a paragraph or ordinary outline and its descendants from the active tree.
38 /// Historical objects remain available.
39 pub(crate) fn delete(object: ExGuid, author: &str) -> Result<Self, Error> {
40 Self::new(object, Placement::Delete, author)
41 }
42
43 /// Moves before a direct child, or appends when `before` is None.
44 /// Paragraph destinations are outlines, groups, paragraphs or cells on the same page.
45 /// Outlines remain direct page children. Content and explicit list formatting are preserved.
46 pub(crate) fn move_to(
47 object: ExGuid,
48 parent: ExGuid,
49 before: Option<ExGuid>,
50 author: &str,
51 ) -> Result<Self, Error> {
52 Self::new(object, Placement::Move { parent, before }, author)
53 }
54
55 fn new(object: ExGuid, placement: Placement, author: &str) -> Result<Self, Error> {
56 let intent = Self {
57 guid: fresh_guid()?,
58 object,
59 placement,
60 author: author.to_owned(),
61 };
62 intent.validate()?;
63 Ok(intent)
64 }
65
66 fn validate(&self) -> Result<(), Error> {
67 if self.guid == [0; 16] || self.object.guid == [0; 16] || self.author.contains('\0') {
68 return Err(invalid(
69 "Choose page content and an author name without NUL",
70 ));
71 }
72 if let Placement::Move { parent, before } = self.placement
73 && (parent.guid == [0; 16] || before.is_some_and(|id| id.guid == [0; 16]))
74 {
75 return Err(invalid("Choose a destination and sibling on the same page"));
76 }
77 Ok(())
78 }
79
80 pub(crate) fn changes(&self, active: &ActivePage<'_>) -> Result<Changes, Error> {
81 let pages = &active.pages;
82 let [page] = pages.as_slice() else {
83 return Err(invalid("Tree editing requires a single active page"));
84 };
85 let mut view = active.view.clone();
86 let parents = active.editable_parents(self.object)?;
87 let path = checked_path(&view, parents, *page, self.object)?;
88 let source_parent = *path
89 .get(1)
90 .ok_or_else(|| invalid("Select a paragraph or ordinary page outline"))?;
91 let compatible = |parent: ExGuid| match view.nodes[&self.object].kind {
92 Kind::Outline { .. }
93 | Kind::Image { .. }
94 | Kind::Attachment { .. }
95 | Kind::Ink { .. } => parent == *page,
96 Kind::Paragraph { .. } => matches!(
97 view.nodes[&parent].kind,
98 Kind::Outline { .. }
99 | Kind::OutlineGroup
100 | Kind::Paragraph { .. }
101 | Kind::Cell { .. }
102 ),
103 _ => false,
104 };
105 if !compatible(source_parent) || !view.nodes[&source_parent].children.contains(&self.object)
106 {
107 return Err(invalid("Select a paragraph or ordinary page outline"));
108 }
109 let mut changed_ids = BTreeSet::from([source_parent]);
110 let mut affected = BTreeSet::from([self.object]);
111 if let Placement::Move { parent, before } = self.placement {
112 if checked_path(&view, parents, *page, parent)?.contains(&self.object) {
113 return Err(invalid("A subtree cannot move inside itself"));
114 }
115 let destination = &view.nodes[&parent];
116 if !compatible(parent) || before.is_some_and(|id| !destination.children.contains(&id)) {
117 return Err(invalid(
118 "Choose a compatible destination and one of its direct children",
119 ));
120 }
121 let previous = destination.children.clone();
122 if parent == source_parent && before == Some(self.object) {
123 return Ok(Changes::new());
124 }
125 view.nodes
126 .get_mut(&source_parent)
127 .unwrap()
128 .children
129 .retain(|id| *id != self.object);
130 let children = &mut view.nodes.get_mut(&parent).unwrap().children;
131 let position = before
132 .map(|id| children.iter().position(|child| *child == id).unwrap())
133 .unwrap_or(children.len());
134 children.insert(position, self.object);
135 if parent == source_parent && *children == previous {
136 return Ok(Changes::new());
137 }
138 changed_ids.insert(parent);
139 } else {
140 view.nodes
141 .get_mut(&source_parent)
142 .unwrap()
143 .children
144 .retain(|id| *id != self.object);
145 }
146
147 let mut at = source_parent;
148 loop {
149 let node = &view.nodes[&at];
150 if matches!(node.kind, Kind::Page { .. } | Kind::Paragraph { .. })
151 && node.children.is_empty()
152 {
153 break;
154 }
155 if node.children.is_empty() {
156 // `Section::apply` refuses an edit that ends with the cell still empty.
157 if matches!(node.kind, Kind::Cell { .. }) {
158 break;
159 }
160 if !matches!(node.kind, Kind::Outline { .. } | Kind::OutlineGroup) {
161 return Err(invalid("This container cannot be emptied by a tree edit"));
162 }
163 if node.extra[0].iter().any(|field| field.id == 0x08001d0c) {
164 return Err(invalid("The emptied container cannot be deleted"));
165 }
166 let path = checked_path(&view, parents, *page, at)?;
167 let parent = path[1];
168 view.nodes
169 .get_mut(&parent)
170 .unwrap()
171 .children
172 .retain(|id| *id != at);
173 changed_ids.remove(&at);
174 changed_ids.insert(parent);
175 at = parent;
176 continue;
177 }
178 if matches!(
179 node.kind,
180 Kind::Outline { .. } | Kind::OutlineGroup | Kind::Paragraph { .. }
181 ) && node
182 .children
183 .iter()
184 .all(|id| matches!(view.nodes[id].kind, Kind::OutlineGroup))
185 {
186 let groups = node.children.clone();
187 let minimum = groups
188 .iter()
189 .map(|id| view.nodes[id].child_level.unwrap_or(1))
190 .min()
191 .unwrap();
192 let level = node
193 .child_level
194 .unwrap_or(1)
195 .checked_add(minimum)
196 .filter(|level| *level <= 31)
197 .ok_or_else(|| {
198 invalid("Removing this group would exceed 31 child indentation levels")
199 })?;
200 let mut children = Vec::new();
201 for group in groups {
202 affected.insert(group);
203 let group_node = view.nodes.get_mut(&group).unwrap();
204 let relative = group_node.child_level.unwrap_or(1) - minimum;
205 if relative == 0 {
206 if group_node.extra[0]
207 .iter()
208 .any(|field| field.id == 0x08001d0c)
209 {
210 return Err(invalid("The redundant outline group cannot be deleted"));
211 }
212 children.extend_from_slice(&group_node.children);
213 changed_ids.remove(&group);
214 } else {
215 group_node.child_level = Some(relative);
216 children.push(group);
217 changed_ids.insert(group);
218 }
219 }
220 let node = view.nodes.get_mut(&at).unwrap();
221 node.children = children;
222 node.child_level = Some(level);
223 changed_ids.insert(at);
224 continue;
225 }
226 break;
227 }
228
229 let mut pending: Vec<_> = affected.into_iter().collect();
230 let mut checked = BTreeSet::new();
231 while let Some(id) = pending.pop() {
232 if !checked.insert(id) {
233 continue;
234 }
235 checked_path(&view, parents, *page, id)?;
236 let node = &view.nodes[&id];
237 if matches!(self.placement, Placement::Delete)
238 && node.extra[0].iter().any(|field| field.id == 0x08001d0c)
239 {
240 return Err(invalid(
241 "The selected subtree contains content that cannot be deleted",
242 ));
243 }
244 pending.extend(
245 node.children
246 .iter()
247 .chain(&node.content)
248 .chain(&node.structure)
249 .copied(),
250 );
251 }
252 let raw = &active.live.revision;
253 let active_parents = editable_parents(&view, pages, *page)?;
254 let modified = current_timestamps()?.0.to_le_bytes();
255 let mut changed = BTreeMap::new();
256 let author_id = ExGuid {
257 guid: self.guid,
258 n: 3,
259 };
260 let moved_paragraph = matches!(self.placement, Placement::Move { .. })
261 && matches!(view.nodes[&self.object].kind, Kind::Paragraph { .. });
262 if moved_paragraph {
263 changed.insert(
264 author_id,
265 PropertyObject {
266 jcid: 0x120001,
267 bytes: properties(&crate::create::author_properties(&self.author))?,
268 global_ids: Arc::new(BTreeMap::from([(0, self.guid)])),
269 },
270 );
271 }
272 if let Some(author) = changed.get(&author_id)
273 && raw.objects.get(&author_id).is_some_and(|old| {
274 old.jcid == author.jcid && old.data == crate::ObjectData::Properties(&author.bytes)
275 })
276 {
277 changed.remove(&author_id);
278 }
279 if changed.keys().any(|id| raw.objects.contains_key(id)) {
280 return Err(invalid(
281 "A tree-edit identity already exists; reconcile the existing edit",
282 ));
283 }
284 let mut ancestors = BTreeSet::new();
285 for id in &changed_ids {
286 ancestors.extend(checked_path(&view, &active_parents, *page, *id)?);
287 }
288 for id in ancestors {
289 let mut object = PropertyObject::from_object(&raw.objects[&id])?;
290 if changed_ids.contains(&id) {
291 let node = &view.nodes[&id];
292 let mut references = Vec::new();
293 for child in &node.children {
294 references.extend_from_slice(&object.reference(*child)?);
295 }
296 object.set(&[(0x24001c20, &references)])?;
297 if let Some(level) = node.child_level {
298 object.set(&[(0x0c001c03, &[level])])?;
299 }
300 }
301 object.set(&[(0x14001d7a, &modified)])?;
302 changed.insert(id, object);
303 }
304 if moved_paragraph {
305 let mut object = PropertyObject::from_object(&raw.objects[&self.object])?;
306 let author = object.reference(author_id)?;
307 object.set(&[(0x20001d79, &author), (0x14001d7a, &modified)])?;
308 changed.insert(self.object, object);
309 }
310 update_title(active, view, &mut changed)?;
311 Ok(changed)
312 }
313}
314
315fn checked_path(
316 view: &Revision<'_>,
317 parents: &BTreeMap<ExGuid, Vec<ExGuid>>,
318 page: ExGuid,
319 object: ExGuid,
320) -> Result<Vec<ExGuid>, Error> {
321 let mut path = Vec::new();
322 let mut seen = BTreeSet::new();
323 let mut id = object;
324 loop {
325 if !seen.insert(id) {
326 return Err(invalid("Tree ancestry contains a cycle"));
327 }
328 let node = view
329 .nodes
330 .get(&id)
331 .ok_or_else(|| invalid("The selected page content is unavailable"))?;
332 if matches!(node.kind, Kind::Title)
333 || node.extra[0]
334 .iter()
335 .any(|field| matches!(field.id, 0x88001cb4 | 0x88001cf9 | 0x88001cb2 | 0x88001cde))
336 {
337 return Err(invalid(
338 "Title or protected content cannot be moved or deleted here",
339 ));
340 }
341 path.push(id);
342 if id == page {
343 break;
344 }
345 let [parent] = parents.get(&id).map(Vec::as_slice).unwrap_or_default() else {
346 return Err(invalid("Tree content must have one active parent"));
347 };
348 id = *parent;
349 }
350 Ok(path)
351}
352
353#[cfg(test)]
354mod tests {
355 use super::*;
356 use crate::{
357 RevisionIndex, Store,
358 document::{Document, Format},
359 op::{
360 PageOp,
361 tests::{edited, text_paragraph},
362 },
363 write::write_revision,
364 };
365
366 #[test]
367 fn group_normalization_preserves_unequal_indentation_and_overlapping_moves() {
368 let source = crate::create_section("groups.one", "First", "Author").unwrap();
369 let store = Store::parse(&source).unwrap();
370 let index = RevisionIndex::parse(&store).unwrap();
371 let document = Document::parse(&index).unwrap();
372 let (sid, page) = document.pages().unwrap()[0];
373 let view = document.active(sid).unwrap();
374 let outline = *view.nodes[&page]
375 .children
376 .iter()
377 .find(|id| matches!(view.nodes[id].kind, Kind::Outline { .. }))
378 .unwrap();
379 let first = view.nodes[&outline].children[0];
380 let paragraphs = vec![
381 text_paragraph("Second", Format::default()),
382 text_paragraph("Third", Format::default()),
383 ];
384 let (second, third) = (paragraphs[0].id, paragraphs[1].id);
385 let insert = PageOp::Insert {
386 container: outline,
387 before: None,
388 paragraphs,
389 };
390 let source = edited(&source, sid, vec![insert]).unwrap();
391 let guid = fresh_guid().unwrap();
392 let a = ExGuid { guid, n: 1 };
393 let b = ExGuid { guid, n: 2 };
394 let source = write_revision(&source, sid, |raw| {
395 let mut changed = BTreeMap::new();
396 for (id, child, level) in [(a, first, 2), (b, second, 1)] {
397 let mut group = PropertyObject {
398 jcid: 0x60019,
399 bytes: properties(&[(0x0c001c03, vec![level])])?,
400 global_ids: Arc::new(BTreeMap::from([(0, guid)])),
401 };
402 let reference = group.reference(child)?;
403 group.set(&[(0x24001c20, &reference)])?;
404 changed.insert(id, group);
405 }
406 let mut object = PropertyObject::from_object(&raw.objects[&outline])?;
407 let mut references = Vec::new();
408 for id in [a, b, third] {
409 references.extend_from_slice(&object.reference(id)?);
410 }
411 object.set(&[(0x24001c20, &references)])?;
412 changed.insert(outline, object);
413 Ok(changed)
414 })
415 .unwrap();
416 let page = |image: &[u8]| {
417 let store = Store::parse(image).unwrap();
418 let index = RevisionIndex::parse(&store).unwrap();
419 index.validate_current().unwrap();
420 crate::page::Page::from_space(&Document::parse(&index).unwrap(), sid).unwrap()
421 };
422 let written = edited(&source, sid, vec![PageOp::Delete { object: third }]).unwrap();
423 let store = Store::parse(&written).unwrap();
424 let index = RevisionIndex::parse(&store).unwrap();
425 let document = Document::parse(&index).unwrap();
426 let view = document.active(sid).unwrap();
427 assert_eq!(view.nodes[&outline].children, [a, second]);
428 assert_eq!(view.nodes[&outline].child_level, Some(2));
429 assert_eq!(view.nodes[&a].child_level, Some(1));
430 assert_eq!(view.nodes[&a].children, [first]);
431 if let Some(output) = std::env::var_os("ONESTORE_TREE_OUTPUT") {
432 let output = std::path::PathBuf::from(output).join("unequal-groups");
433 assert!(output.is_absolute());
434 std::fs::create_dir_all(output.parent().unwrap()).unwrap();
435 std::fs::create_dir(&output).unwrap();
436 std::fs::write(output.join("groups.one"), &written).unwrap();
437 }
438 // A move keeps the paragraph's level; the writers regroup the outline around it.
439 let moved = PageOp::Move {
440 object: third,
441 parent: Some(outline),
442 before: Some(first),
443 };
444 let mut predicted = page(&source);
445 crate::op::predict(&mut predicted, &moved).unwrap();
446 assert_eq!(page(&edited(&source, sid, vec![moved]).unwrap()), predicted);
447 }
448
449 #[test]
450 fn protected_descendants_and_ambiguous_parents_reject_before_publication() {
451 let source = crate::create_section("protected.one", "Text", "Author").unwrap();
452 let store = Store::parse(&source).unwrap();
453 let index = RevisionIndex::parse(&store).unwrap();
454 let document = Document::parse(&index).unwrap();
455 let (sid, page) = document.pages().unwrap()[0];
456 let view = document.active(sid).unwrap();
457 let outline = *view.nodes[&page]
458 .children
459 .iter()
460 .find(|id| matches!(view.nodes[id].kind, Kind::Outline { .. }))
461 .unwrap();
462 let paragraph = view.nodes[&outline].children[0];
463 let text = view.nodes[&paragraph].content[0];
464 let deleted =
465 |bytes: &[u8]| edited(bytes, sid, vec![PageOp::Delete { object: paragraph }]).is_ok();
466 for target in [page, outline, paragraph, text] {
467 for property in [0x08001cde, 0x08001cb4, 0x08001cf9, 0x08001cb2] {
468 for enabled in [false, true] {
469 let bytes = write_revision(&source, sid, |raw| {
470 let mut object = PropertyObject::from_object(&raw.objects[&target])?;
471 object.set(&[(property | (u32::from(enabled) << 31), &[])])?;
472 Ok(BTreeMap::from([(target, object)]))
473 })
474 .unwrap();
475 assert_eq!(deleted(&bytes), !enabled, "{target}: {property:#x}");
476 }
477 }
478 }
479 for protected in [outline, paragraph, text] {
480 let bytes = write_revision(&source, sid, |raw| {
481 let mut object = PropertyObject::from_object(&raw.objects[&protected])?;
482 object.set(&[(0x08001d0c, &[])])?;
483 Ok(BTreeMap::from([(protected, object)]))
484 })
485 .unwrap();
486 assert!(!deleted(&bytes));
487 }
488 let bytes = write_revision(&source, sid, |raw| {
489 let mut object = PropertyObject::from_object(&raw.objects[&outline])?;
490 let reference = object.reference(paragraph)?;
491 object.set(&[(0x24001c20, &reference.repeat(2))])?;
492 Ok(BTreeMap::from([(outline, object)]))
493 })
494 .unwrap();
495 assert!(!deleted(&bytes));
496 }
497}