1use alloc::collections::BTreeSet;
4
5use serde_json::Value;
6
7use crate::digest::{Fingerprint, is_binary};
8use crate::errors::{MergeError, Result, list};
9use crate::format::Format;
10use crate::merge::{Driver, Merged, has_markers};
11use crate::part::{Key, Leaves, Shape, decode, display, encode, merge, overlap};
12use crate::path::RelPath;
13use crate::profile::{OnConflict, Policy};
14use crate::resolve::{Portion, Resolved};
15use crate::survey::{Entry, Survey, released};
16use crate::target::{Target, read_optional};
17use crate::tree::Tree;
18
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum Mode {
22 Apply,
24 Force,
26 Continue,
28}
29
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
32pub enum Action {
33 Keep,
35 Write,
37 Record,
39 Untrack,
42 Remove,
45 Merge,
47 Conflict,
49}
50
51impl Action {
52 #[must_use]
54 pub const fn writes(self) -> bool {
55 matches!(self, Self::Write | Self::Merge | Self::Remove)
56 }
57}
58
59impl Entry {
60 #[must_use]
64 pub fn action(&self, mode: Mode) -> Action {
65 let Some(want) = self.want else {
66 return self.released();
67 };
68 let incoming = want.fingerprint;
69 let restore = mode == Mode::Force && want.policy == Policy::Owned;
70 match (self.found, self.record) {
71 (None, None) => Action::Write,
72 (None, Some(_)) => {
73 if restore {
74 Action::Write
75 } else {
76 Action::Keep
77 }
78 },
79 (Some(found), record) if found.same_content(&incoming) => {
81 if record == Some(incoming) {
82 Action::Keep
83 } else {
84 Action::Record
85 }
86 },
87 (Some(_), None) => {
89 if restore {
90 Action::Write
91 } else {
92 Action::Record
93 }
94 },
95 (Some(found), Some(record)) if found.same_content(&record) => {
97 if want.policy == Policy::Once { Action::Keep } else { Action::Write }
98 },
99 (Some(_), Some(record)) => {
100 if restore {
101 Action::Write
102 } else if want.policy == Policy::Merge && !record.same_content(&incoming) {
103 Action::Merge
104 } else {
105 Action::Keep
106 }
107 },
108 }
109 }
110}
111
112impl Entry {
113 fn released(&self) -> Action {
116 let unchanged = matches!(
117 (self.found, self.record),
118 (Some(found), Some(record)) if found.same_content(&record)
119 );
120 if unchanged && self.recorded != Some(Policy::Once) {
121 Action::Remove
122 } else {
123 Action::Untrack
124 }
125 }
126}
127
128#[derive(Clone, Debug)]
130pub struct Step {
131 pub entry: Entry,
133 pub action: Action,
135 pub note: Option<String>,
137}
138
139#[derive(Debug)]
141pub struct Plan {
142 pub(crate) resolved: Resolved,
144 pub(crate) steps: Vec<Step>,
146 pub(crate) merged: Tree,
148 pub(crate) gone: BTreeSet<RelPath>,
150 pub(crate) held: bool,
152}
153
154impl Plan {
155 #[must_use]
157 pub const fn resolved(&self) -> &Resolved {
158 &self.resolved
159 }
160
161 #[must_use]
163 pub fn steps(&self) -> &[Step] {
164 &self.steps
165 }
166
167 #[must_use]
169 pub const fn held(&self) -> bool {
170 self.held
171 }
172}
173
174pub fn plan(survey: Survey, mode: Mode, target: &Target) -> Result<Plan> {
188 let Survey { resolved, entries } = survey;
189 let mut unresolved: Vec<RelPath> =
190 entries.iter().filter(|e| e.conflict).map(|e| e.path.clone()).collect();
191 unresolved.dedup();
192 match (mode, unresolved.is_empty()) {
193 (Mode::Continue, true) => return Err(MergeError::NothingToContinue.into()),
194 (Mode::Apply | Mode::Force, false) => {
195 return Err(MergeError::Unresolved { paths: unresolved }.into());
196 },
197 _ => {},
198 }
199 let mut planner = Planner {
200 resolved: &resolved,
201 target,
202 mode,
203 merged: Tree::default(),
204 gone: BTreeSet::new(),
205 };
206 let mut steps = Vec::with_capacity(entries.len());
207 let mut entries = entries.into_iter().peekable();
208 while let Some(first) = entries.next() {
209 let path = first.path.clone();
210 let mut file = vec![first];
211 while let Some(next) = entries.next_if(|next| next.path == path) {
212 file.push(next);
213 }
214 steps.extend(planner.file(file)?);
215 }
216 let Planner { merged, gone, .. } = planner;
217 let conflicted = steps.iter().any(|step| step.action == Action::Conflict);
218 let held = conflicted && resolved.settings().on_conflict == OnConflict::ApplyNone;
219 Ok(Plan { resolved, steps, merged, gone, held })
220}
221
222struct Planner<'a> {
224 resolved: &'a Resolved,
226 target: &'a Target,
228 mode: Mode,
230 merged: Tree,
232 gone: BTreeSet<RelPath>,
234}
235
236struct Decision<'a> {
238 action: Action,
240 content: Option<Vec<u8>>,
242 note: Option<String>,
244 clash: Option<Clash<'a>>,
246}
247
248impl Decision<'_> {
249 const fn of(action: Action, content: Option<Vec<u8>>, note: Option<String>) -> Self {
251 Self { action, content, note, clash: None }
252 }
253}
254
255struct Clash<'a> {
257 portion: &'a Portion,
259 keys: BTreeSet<Key>,
261 base: Leaves,
263 theirs: Leaves,
265}
266
267impl<'a> Planner<'a> {
268 fn file(&mut self, entries: Vec<Entry>) -> Result<Vec<Step>> {
270 if entries.first().is_some_and(|entry| entry.conflict) {
271 return self.resolution(entries);
272 }
273 let mut steps = Vec::with_capacity(entries.len());
274 let mut parts = Vec::new();
275 let whole = entries.iter().any(|entry| entry.part.is_none() && entry.want.is_some());
277 for entry in entries {
278 match (&entry.part, entry.want) {
279 (None, _) => steps.push(self.whole(entry)?),
280 (Some(_), None) if whole => {
281 steps.push(Step { entry, action: Action::Untrack, note: None });
282 },
283 (Some(_), _) => parts.push(entry),
284 }
285 }
286 if !parts.is_empty() {
287 steps.extend(self.parts(parts)?);
288 steps.sort_by(|a, b| a.entry.part.cmp(&b.entry.part));
289 }
290 Ok(steps)
291 }
292
293 fn whole(&mut self, entry: Entry) -> Result<Step> {
295 let (action, note) = match (entry.action(self.mode), entry.want, entry.record) {
296 (Action::Merge, Some(want), Some(record)) => {
297 let base = self.target.base(&record)?;
298 let ours = fs_err::read(entry.path.under(self.target.root()))?;
299 let theirs = self.resolved.payload(&entry)?;
300 let Merged { bytes, conflict } =
301 self.merge(&entry.path, base.as_deref(), &ours, theirs)?;
302 let conflict = conflict.or_else(|| {
303 want.validate
304 .check(&bytes)
305 .err()
306 .map(|why| format!("merged, but invalid: {why}"))
307 });
308 self.merged.put(entry.path.clone(), &bytes);
309 (if conflict.is_some() { Action::Conflict } else { Action::Merge }, conflict)
310 },
311 (Action::Remove, ..) => {
312 self.gone.insert(entry.path.clone());
313 (Action::Remove, None)
314 },
315 (action, ..) => (action, None),
316 };
317 Ok(Step { entry, action, note })
318 }
319
320 fn merge(
322 &self, path: &RelPath, base: Option<&[u8]>, ours: &[u8], theirs: &[u8],
323 ) -> Result<Merged> {
324 let driver = &self.resolved.settings().driver;
325 let root = self.target.root();
326 let Merged { bytes, conflict } =
327 driver.merge(root, path, base.unwrap_or_default(), ours, theirs)?;
328 let lost = base.is_none() && !is_binary(ours) && !is_binary(theirs);
331 let conflict = if lost {
332 Some("its recorded base is missing, so it merged without one".to_owned())
333 } else {
334 conflict
335 };
336 Ok(Merged { bytes, conflict })
337 }
338
339 fn parts(&mut self, entries: Vec<Entry>) -> Result<Vec<Step>> {
342 let resolved = self.resolved;
343 let Some(path) = entries.first().map(|entry| entry.path.clone()) else {
344 return Ok(Vec::new());
345 };
346 let label = path.as_str();
347 let disk = read_optional(&path.under(self.target.root()))?.unwrap_or_default();
348 let mut file = disk.clone();
349 let mut steps = Vec::with_capacity(entries.len());
350 let mut written: Vec<(usize, &Shape, Vec<u8>)> = Vec::new();
351 let mut removed: Vec<(usize, Shape, BTreeSet<Key>)> = Vec::new();
352 let mut clashes = Vec::new();
353 let claimed: Vec<Key> = entries
355 .iter()
356 .filter(|entry| entry.want.is_some())
357 .flat_map(|entry| entry.keys.iter().cloned())
358 .collect();
359 for entry in entries {
360 let Some(portion) = resolved.portion(&entry) else {
361 let taken = self.take_out(&mut file, &entry, &claimed, label)?;
362 let action = if taken.is_some() { Action::Remove } else { Action::Untrack };
363 removed.extend(taken.map(|(shape, keys)| (steps.len(), shape, keys)));
364 steps.push(Step { entry, action, note: None });
365 continue;
366 };
367 let Decision { action, content, note, clash } = self.decide(&entry, portion, &disk)?;
368 clashes.extend(clash);
369 if let Some(content) = content {
370 file = portion.splice(&file, &content, &entry.keys, label)?;
371 written.push((steps.len(), &portion.shape, content));
372 }
373 steps.push(Step { entry, action, note });
374 }
375 if written.is_empty() && removed.is_empty() {
376 return Ok(steps);
377 }
378 let marked = steps.iter().any(|step| step.action == Action::Conflict);
380 let trouble = if marked { None } else { check(&file, &steps, &written, &removed, label)? };
381 let conflicted = marked || trouble.is_some();
382 if !conflicted {
383 if !removed.is_empty() && file.trim_ascii().is_empty() {
385 self.gone.insert(path);
386 } else {
387 self.merged.put(path, &file);
388 }
389 return Ok(steps);
390 }
391 for step in &mut steps {
392 if step.action.writes() {
393 step.action = Action::Conflict;
394 step.note = trouble.clone().or_else(|| {
395 Some("waits for the conflict in another part of the file".to_owned())
396 });
397 }
398 }
399 let sidecar = self.mark(&path, &file, &clashes)?;
400 self.merged.put(path, &sidecar);
401 Ok(steps)
402 }
403
404 fn decide(&self, entry: &Entry, portion: &'a Portion, disk: &[u8]) -> Result<Decision<'a>> {
406 let (shape, theirs) = (&portion.shape, self.resolved.payload(entry)?);
407 let label = entry.path.as_str();
408 Ok(match (entry.action(self.mode), entry.record, shape) {
409 (Action::Write, ..) => Decision::of(Action::Write, Some(theirs.to_vec()), None),
410 (Action::Merge, Some(record), Shape::Keys(_)) => {
411 let base = self.target.base(&record)?;
412 let base = base.as_deref().and_then(decode).unwrap_or_default();
413 let ours = shape.view(disk, &entry.keys, label)?;
414 let ours = ours.as_deref().and_then(decode).unwrap_or_default();
415 let theirs = decode(theirs).unwrap_or_default();
416 let merged = merge(&base, &ours, &theirs, &entry.keys);
417 let content = Some(encode(&merged.leaves));
418 if merged.conflicts.is_empty() {
419 return Ok(Decision::of(Action::Merge, content, None));
420 }
421 let note = format!("both changed {}", keys(&merged.conflicts));
422 let at = |side: &Leaves| {
423 let conflicts = &merged.conflicts;
424 side.iter().filter(|(k, _)| conflicts.contains(*k)).map(clone).collect()
425 };
426 let (base, theirs) = (at(&base), at(&theirs));
427 let clash = Clash { portion, keys: merged.conflicts, base, theirs };
428 Decision { action: Action::Conflict, content, note: Some(note), clash: Some(clash) }
429 },
430 (Action::Merge, Some(record), Shape::Block(_)) => {
431 let base = self.target.base(&record)?;
432 let ours = shape.view(disk, &entry.keys, label)?.unwrap_or_default();
433 let Merged { bytes, conflict } =
434 self.merge(&entry.path, base.as_deref(), &ours, theirs)?;
435 let action = if conflict.is_some() { Action::Conflict } else { Action::Merge };
436 Decision::of(action, Some(bytes), conflict)
437 },
438 (Action::Record, None, Shape::Keys(_)) => {
441 let ours = shape.view(disk, &entry.keys, label)?;
442 let ours = ours.as_deref().and_then(decode).unwrap_or_default();
443 let mut filled = decode(theirs).unwrap_or_default();
444 filled.extend(ours.iter().map(clone));
445 if filled == ours {
446 Decision::of(Action::Record, None, None)
447 } else {
448 Decision::of(Action::Merge, Some(encode(&filled)), None)
449 }
450 },
451 (action, ..) => Decision::of(action, None, None),
452 })
453 }
454
455 fn take_out(
459 &self, file: &mut Vec<u8>, entry: &Entry, claimed: &[Key], label: &str,
460 ) -> Result<Option<(Shape, BTreeSet<Key>)>> {
461 if entry.action(self.mode) != Action::Remove {
462 return Ok(None);
463 }
464 let Some(shape) = released(self.target, entry) else {
465 return Ok(None);
466 };
467 let mut keys = entry.keys.clone();
468 keys.retain(|key| !claimed.iter().any(|kept| overlap(key, kept)));
469 *file = shape.remove(file, &keys, label)?;
470 Ok(Some((shape, keys)))
471 }
472
473 fn mark(&self, path: &RelPath, file: &[u8], clashes: &[Clash<'_>]) -> Result<Vec<u8>> {
476 if clashes.is_empty() {
477 return Ok(file.to_vec());
478 }
479 let label = path.as_str();
480 let (mut base, mut theirs) = (file.to_vec(), file.to_vec());
481 for clash in clashes {
482 base = clash.portion.splice(&base, &encode(&clash.base), &clash.keys, label)?;
483 theirs = clash.portion.splice(&theirs, &encode(&clash.theirs), &clash.keys, label)?;
484 }
485 let root = self.target.root();
486 Ok(Driver::Builtin.merge(root, path, &base, file, &theirs)?.bytes)
487 }
488
489 fn resolution(&mut self, entries: Vec<Entry>) -> Result<Vec<Step>> {
494 let path = entries.iter().find(|entry| entry.want.is_some()).map(|e| e.path.clone());
495 if let Some(path) = path {
496 let bytes = fs_err::read(self.target.sidecar(&path))?;
497 if has_markers(&bytes) {
498 return Err(MergeError::Unmerged { path }.into());
499 }
500 for want in entries.iter().filter_map(|entry| entry.want) {
501 want.validate
502 .check(&bytes)
503 .map_err(|reason| MergeError::Invalid { path: path.clone(), reason })?;
504 }
505 self.merged.put(path, &bytes);
506 }
507 let mode = self.mode;
508 let step = |entry: Entry| {
509 let action = match (entry.want, &entry.part) {
510 (None, _) => Action::Untrack,
511 (Some(_), None) => Action::Merge,
512 (Some(_), Some(_)) => match entry.action(mode) {
513 action if action.writes() => Action::Merge,
514 action => action,
515 },
516 };
517 Step { entry, action, note: None }
518 };
519 Ok(entries.into_iter().map(step).collect())
520 }
521}
522
523fn check(
526 file: &[u8], steps: &[Step], written: &[(usize, &Shape, Vec<u8>)],
527 removed: &[(usize, Shape, BTreeSet<Key>)], label: &str,
528) -> Result<Option<String>> {
529 let mut formats: Vec<Format> =
530 steps.iter().filter_map(|s| s.entry.want).map(|w| w.validate).collect();
531 formats.dedup();
532 for format in formats {
533 if let Err(why) = format.check(file) {
534 return Ok(Some(format!("with it, the file is invalid: {why}")));
535 }
536 }
537 for (index, shape, content) in written {
538 let Some(step) = steps.get(*index) else {
539 continue;
540 };
541 let back = shape.view(file, &step.entry.keys, label)?.unwrap_or_default();
542 if !Fingerprint::of(&back).same_content(&Fingerprint::of(content)) {
543 return Ok(Some("it reads back other than devset wrote it".to_owned()));
544 }
545 }
546 for (_, shape, keys) in removed {
547 let left = shape.view(file, keys, label)?;
548 if left.is_some_and(|left| decode(&left).is_none_or(|leaves| !leaves.is_empty())) {
549 return Ok(Some("a part devset removed is still in it".to_owned()));
550 }
551 }
552 Ok(None)
553}
554
555fn clone((key, value): (&Key, &Value)) -> (Key, Value) {
557 (key.clone(), value.clone())
558}
559
560fn keys(keys: &BTreeSet<Key>) -> String {
562 const NAMED: usize = 3;
563 let named = keys.iter().take(NAMED).map(|key| format!("`{}`", display(key)));
564 let rest = keys.len().saturating_sub(NAMED);
565 list(named.chain((rest > 0).then(|| format!("{rest} more"))))
566}
567
568#[cfg(test)]
569mod tests {
570 use alloc::collections::BTreeSet;
571
572 use super::{Action, Mode};
573 use crate::digest::Fingerprint;
574 use crate::format::Format;
575 use crate::path::RelPath;
576 use crate::profile::Policy;
577 use crate::survey::{Entry, Want};
578
579 fn fp(name: &str) -> Fingerprint {
584 Fingerprint::of(match name {
585 "p" => b"profile\n",
586 "p~" => b"profile \r\n\n",
587 "o" => b"old\n",
588 _ => b"edited\n",
589 })
590 }
591
592 fn entry(policy: Policy, found: Option<&str>, record: Option<&str>) -> Entry {
593 Entry {
594 path: RelPath::new("f").unwrap(),
595 part: None,
596 want: Some(Want {
597 layer: 0,
598 policy,
599 validate: Format::None,
600 executable: false,
601 fingerprint: fp("p"),
602 }),
603 record: record.map(fp),
604 recorded: record.map(|_| policy),
605 found: found.map(fp),
606 conflict: false,
607 keys: BTreeSet::new(),
608 }
609 }
610
611 #[test]
612 fn decision_table() {
613 use Action::{Keep, Merge, Record, Write};
614 use Policy::{Merge as M, Once, Owned};
615 #[rustfmt::skip]
616 let table = [
617 (Owned, None, None, Write, Write), (Owned, None, Some("p"), Keep, Write), (Owned, Some("p"), Some("p"), Keep, Keep), (Owned, Some("p~"), Some("p"), Keep, Keep), (Owned, Some("p~"), Some("o"), Record, Record), (Owned, Some("x"), None, Record, Write), (Owned, Some("o"), Some("o"), Write, Write), (Owned, Some("x"), Some("p"), Keep, Write), (Once, None, None, Write, Write),
627 (Once, None, Some("p"), Keep, Keep),
628 (Once, Some("x"), None, Record, Record),
629 (Once, Some("o"), Some("o"), Keep, Keep),
630 (Once, Some("x"), Some("p"), Keep, Keep),
631 (M, Some("x"), Some("o"), Merge, Merge),
632 (M, Some("x"), Some("p"), Keep, Keep),
633 (M, Some("o"), Some("o"), Write, Write),
634 ];
635 for (policy, found, record, apply, force) in table {
636 let entry = entry(policy, found, record);
637 let case = format!("{policy:?} found={found:?} record={record:?}");
638 assert_eq!(entry.action(Mode::Apply), apply, "apply: {case}");
639 assert_eq!(entry.action(Mode::Force), force, "force: {case}");
640 }
641 }
642
643 #[test]
644 fn a_dropped_file_goes_unless_edited_or_the_targets() {
645 use Action::{Remove, Untrack};
646 use Policy::{Merge as M, Once, Owned};
647 #[rustfmt::skip]
648 let table = [
649 (Owned, Some("p"), Some("p"), Remove), (Owned, Some("p~"), Some("p"), Remove), (M, Some("p"), Some("p"), Remove),
653 (Owned, Some("x"), Some("p"), Untrack), (Owned, None, Some("p"), Untrack), (Once, Some("p"), Some("p"), Untrack), ];
657 for (policy, found, record, action) in table {
658 let entry = Entry { want: None, ..entry(policy, found, record) };
659 let case = format!("{policy:?} found={found:?} record={record:?}");
660 assert_eq!(entry.action(Mode::Apply), action, "apply: {case}");
661 assert_eq!(entry.action(Mode::Force), action, "force: {case}");
662 }
663 }
664}