Repository: pkolaczk/fclones (language: rust)

Issue:
The number of files to be removed is incorrect when --isolate option is present
```
# Report by fclones 0.17.1
# Timestamp: 2022-02-26 17:02:34.697 +0100
# Command: /home/pkolaczk/.cargo/target/debug/fclones group --isolate test/root1 test/root2 -o report.txt
# Base dir: /home/pkolaczk/Projekty/fclones
# Found 1 file groups
# 12 B (12 B) in 3 redundant files can be removed   // <------- this is incorrect, only 2 files can be removed when  --isolate is present
6109f093b3fd5eb1060989c990d1226f, 4 B (4 B) * 4:
    /home/pkolaczk/Projekty/fclones/test/root1/foo1
    /home/pkolaczk/Projekty/fclones/test/root1/foo2
    /home/pkolaczk/Projekty/fclones/test/root2/foo1
    /home/pkolaczk/Projekty/fclones/test/root2/foo2
```



Discussion / hints:

Fix patch:
diff --git a/src/config.rs b/src/config.rs
index b9d37da..66bb0d0 100644
--- a/src/config.rs
+++ b/src/config.rs
@@ -18,6 +18,8 @@ use crate::path::Path;
 use crate::pattern::{Pattern, PatternError, PatternOpts};
 use crate::selector::PathSelector;
 use crate::transform::Transform;
+use crate::FileGroupFilter;
+use crate::Replication::{Overreplicated, Underreplicated};
 
 #[derive(Debug, Clone, Copy)]
 pub enum OutputFormat {
@@ -341,6 +343,23 @@ impl GroupConfig {
             .exclude_paths(exclude_paths?))
     }
 
+    pub fn group_filter(&self) -> FileGroupFilter {
+        FileGroupFilter {
+            replication: if self.unique {
+                Underreplicated(2)
+            } else if let Some(rf) = self.rf_under {
+                Underreplicated(rf)
+            } else {
+                Overreplicated(self.rf_over())
+            },
+            root_paths: if self.isolate {
+                self.input_paths().collect()
+            } else {
+                vec![]
+            },
+        }
+    }
+
     pub fn rf_over(&self) -> usize {
         // don't prune small groups if:
         // - there is transformation defined
diff --git a/src/dedupe.rs b/src/dedupe.rs
index cbb5972..365f3b5 100644
--- a/src/dedupe.rs
+++ b/src/dedupe.rs
@@ -22,8 +22,7 @@ use crate::lock::FileLock;
 use crate::log::Log;
 use crate::path::Path;
 use crate::util::{max_result, min_result, try_sort_by_key};
-use crate::{root_of, Error, FileGroup, TIMESTAMP_FMT};
-use itertools::Itertools;
+use crate::{AsPath, Error, FileGroup, FileSubGroup, TIMESTAMP_FMT};
 use std::collections::HashMap;
 use std::time::SystemTime;
 
@@ -74,6 +73,12 @@ impl FileMetadata {
     }
 }
 
+impl AsPath for FileMetadata {
+    fn path(&self) -> &Path {
+        &self.path
+    }
+}
+
 impl Display for FileMetadata {
     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
         f.pad(format!("{}", self.path).as_str())
@@ -515,26 +520,7 @@ fn may_drop(path: &Path, config: &DedupeConfig) -> bool {
         || matches_any_path()
 }
 
-/// A sub-group of files. A sub-group is treated as one entity.
-/// All files in a subgroup must be either dropped or kept.
-struct FileSubGroup {
-    files: Vec<FileMetadata>,
-}
-
-impl FileSubGroup {
-    /// Splits a group of files into subgroups.
-    /// Files sharing the same prefix found in the roots array are placed in the same subgroup.
-    pub fn group(files: Vec<FileMetadata>, roots: &[Path]) -> Vec<FileSubGroup> {
-        assert!(!files.is_empty());
-        files
-            .into_iter()
-            .map(|f| (root_of(&f.path, roots).clone(), f))
-            .into_group_map()
-            .into_values()
-            .map(|files| FileSubGroup { files })
-            .collect()
-    }
-
+impl FileSubGroup<FileMetadata> {
     /// Returns the time of the earliest creation of a file in the subgroup
     pub fn created(&self) -> Result<SystemTime, Error> {
         Ok(min_result(self.files.iter().map(|f| {
@@ -598,7 +584,7 @@ impl FileSubGroup {
 /// recently accessed, etc) are sorted last.
 /// In cases when metadata of a file cannot be accessed, an error message is pushed
 /// in the result vector and such file is placed at the beginning of the list.
-fn sort_by_priority(files: &mut [FileSubGroup], priority: &Priority) -> Vec<Error> {
+fn sort_by_priority(files: &mut [FileSubGroup<FileMetadata>], priority: &Priority) -> Vec<Error> {
     match priority {
         Priority::Newest => try_sort_by_key(files, |m| m.created()),
         Priority::Oldest => try_sort_by_key(files, |m| m.created().map(Reverse)),
diff --git a/src/files.rs b/src/files.rs
index 9a32925..5fec48b 100644
--- a/src/files.rs
+++ b/src/files.rs
@@ -181,6 +181,18 @@ pub trait AsPath {
     fn path(&self) -> &Path;
 }
 
+impl AsPath for Path {
+    fn path(&self) -> &Path {
+        self
+    }
+}
+
+impl<T: AsPath> AsPath for &T {
+    fn path(&self) -> &Path {
+        (**self).path()
+    }
+}
+
 pub trait IntoPath {
     fn into_path(self) -> Path;
 }
diff --git a/src/lib.rs b/src/lib.rs
index 0545f69..a2d1784 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,13 +1,14 @@
 use core::fmt;
 use std::cell::RefCell;
-use std::cmp::{max, Reverse};
-use std::collections::{HashMap, HashSet};
+use std::cmp::{max, min, Reverse};
+use std::collections::HashMap;
 use std::env::{args, current_dir};
 use std::ffi::{OsStr, OsString};
 use std::fmt::{Display, Formatter};
 use std::fs::File;
 use std::io;
 use std::io::BufWriter;
+use std::iter::FromIterator;
 use std::sync::atomic::{AtomicU32, Ordering};
 use std::sync::mpsc::{channel, Receiver, Sender};
 use std::sync::Arc;
@@ -94,7 +95,7 @@ impl From<&str> for Error {
 struct AppCtx<'a> {
     pub config: &'a GroupConfig,
     pub log: &'a Log,
-    input_paths: Vec<Path>,
+    group_filter: FileGroupFilter,
     devices: DiskDevices,
     transform: Option<Transform>,
     path_selector: PathSelector,
@@ -110,12 +111,7 @@ impl<'a> AppCtx<'a> {
             Some(Err(e)) => return Err(Error::new(format!("Invalid transform: {}", e))),
         };
         let base_dir = Path::from(current_dir().unwrap_or_default());
-        let base_dir_ref = Arc::new(base_dir.clone());
-        let root_paths = config
-            .paths
-            .iter()
-            .map(|p| base_dir_ref.resolve(p))
-            .collect();
+        let group_filter = config.group_filter();
         let selector = config
             .path_selector(&base_dir)
             .map_err(|e| format!("Invalid pattern: {}", e))?;
@@ -125,7 +121,7 @@ impl<'a> AppCtx<'a> {
         Ok(AppCtx {
             config,
             log,
-            input_paths: root_paths,
+            group_filter,
             devices,
             transform,
             path_selector: selector,
@@ -170,48 +166,181 @@ pub struct FileGroup<F> {
     pub files: Vec<F>,
 }
 
-/// Computes summaries of the results obtained from each grouping stage.
-pub trait StageMetrics {
-    /// Returns the total count of the files
-    fn total_count(self) -> usize;
+/// Controls the type of search by determining the number of replicas
+/// allowed in a group of identical files.
+pub enum Replication {
+    /// Looks for under-replicated files with replication factor lower than the specified number.
+    /// `Underreplicated(2)` means searching for unique files.
+    /// `Underreplicated(3)` means searching for file groups containing fewer than 3 replicas.
+    Underreplicated(usize),
+    /// Looks for over-replicated files with replication factor higher than the specified number.
+    /// `Overreplicated(1)` means searching for duplicates.
+    Overreplicated(usize),
+}
 
-    /// Returns the sum of file lengths
-    fn total_size(self) -> FileLen;
+/// Controls filtering of file groups between the search stages, as well as determines which file
+/// groups are reported in the final report.
+///
+/// For example, when searching for duplicates, groups containing only a single file can be safely
+/// discarded.
+///
+/// This is to be configured from the command line parameters set by the user.
+pub struct FileGroupFilter {
+    /// The allowed number of replicas in the group.
+    pub replication: Replication,
+    /// A list of path prefixes for grouping files into isolated sub-groups.
+    /// Files inside a single subgroup are treated like a single replica.
+    /// If empty - no subgrouping is performed.
+    /// See [`GroupConfig::isolate`].
+    pub root_paths: Vec<Path>,
+}
 
-    /// Returns the total count of redundant files
-    fn selected_count(self, rf_over: usize, rf_under: usize) -> usize;
+impl<F> FileGroup<F> {
+    /// Returns the count of all files in the group
+    pub fn file_count(&self) -> usize {
+        self.files.len()
+    }
 
-    /// Returns the amount of data in redundant files
-    fn selected_size(self, rf_over: usize, rf_under: usize) -> FileLen;
+    /// Returns the total size of all files in the group
+    pub fn total_size(&self) -> FileLen {
+        self.file_len * self.file_count() as u64
+    }
 }
 
-impl<'a, I, F> StageMetrics for I
-where
-    I: IntoIterator<Item = &'a FileGroup<F>> + 'a,
-    F: 'a,
-{
-    fn total_count(self) -> usize {
-        self.into_iter().map(|g| g.files.len()).sum()
+impl<F: AsPath> FileGroup<F> {
+    /// Returns true if the file group should be forwarded to the next grouping stage,
+    /// because the number of duplicate files is higher than the `rf_over` threshold.
+    pub fn matches(&self, filter: &FileGroupFilter) -> bool {
+        match filter.replication {
+            Replication::Overreplicated(rf) => self.subgroup_count(filter) > rf,
+            Replication::Underreplicated(_) => true,
+        }
     }
 
-    fn total_size(self) -> FileLen {
-        self.into_iter()
-            .map(|g| g.file_len * g.files.len() as u64)
-            .sum()
+    /// Returns true if the file group should be included in the final report.
+    /// The number of duplicate files must be within both the lower (`rf_over`)
+    /// and the upper bound (`rf_under`) for the desired replication factor.
+    pub fn matches_strictly(&self, filter: &FileGroupFilter) -> bool {
+        let count = self.subgroup_count(filter);
+        match filter.replication {
+            Replication::Overreplicated(rf) => count > rf,
+            Replication::Underreplicated(rf) => count < rf,
+        }
     }
 
-    fn selected_count(self, rf_over: usize, rf_under: usize) -> usize {
-        self.into_iter()
-            .filter(|&g| g.files.len() < rf_under)
-            .map(|g| g.files.len().saturating_sub(rf_over))
-            .sum()
+    /// Returns the number of missing file replicas.
+    ///
+    /// This is the difference between the desired number of replicas set by `filter.rf_under`
+    /// and the number of files in the group. If the number of files is greater than `rf_under`,
+    /// 0 is returned.
+    pub fn missing_count(&self, filter: &FileGroupFilter) -> usize {
+        match filter.replication {
+            Replication::Overreplicated(_) => 0,
+            Replication::Underreplicated(rf) => rf.saturating_sub(self.subgroup_count(filter)),
+        }
     }
 
-    fn selected_size(self, rf_over: usize, rf_under: usize) -> FileLen {
-        self.into_iter()
-            .filter(|&g| g.files.len() < rf_under)
-            .map(|g| g.file_len * g.files.len().saturating_sub(rf_over) as u64)
-            .sum()
+    /// Returns the highest number of redundant files that could be removed from the group.
+    ///
+    /// If `filter.roots` are empty, the difference between the total number of files
+    /// in the group and the desired maximum number of replicas `filter.rf_over` is returned.
+    ///
+    /// If `filter.roots` are not empty, then files in the group are split into subgroups first,
+    /// where each subgroup shares one of the roots. If the number of subgroups `N` is larger
+    /// than `filter.rf_over`, the largest `N - filter.rf_over` subgroups are considered redundant.
+    /// The total number of files in redundant subgroups is returned.
+    ///
+    /// If the result would be negative in any of the above cases, 0 is returned.
+    pub fn redundant_count(&self, filter: &FileGroupFilter) -> usize {
+        match filter.replication {
+            Replication::Underreplicated(_) => 0,
+            Replication::Overreplicated(rf) => {
+                let rf = max(rf, 1);
+                if filter.root_paths.is_empty() {
+                    // fast-path, equivalent to the code in the else branch, but way faster
+                    self.file_count().saturating_sub(rf)
+                } else {
+                    let sub_groups = FileSubGroup::group(&self.files, &filter.root_paths);
+                    let mut sub_group_lengths = sub_groups
+                        .into_iter()
+                        .map(|sg| sg.files.len())
+                        .collect_vec();
+                    sub_group_lengths.sort_unstable();
+                    let cutoff_index = min(rf, sub_group_lengths.len());
+                    sub_group_lengths[cutoff_index..].iter().sum()
+                }
+            }
+        }
+    }
+
+    /// Returns either the number of files redundant or missing, depending on the type of search.
+    pub fn reported_count(&self, filter: &FileGroupFilter) -> usize {
+        match filter.replication {
+            Replication::Overreplicated(_) => self.redundant_count(filter),
+            Replication::Underreplicated(_) => self.missing_count(filter),
+        }
+    }
+
+    /// The number of subgroups of paths with distinct root prefix.
+    fn subgroup_count(&self, filter: &FileGroupFilter) -> usize {
+        if filter.root_paths.is_empty() {
+            // optimisation: the else branch would compute the same number because each file would
+            // be placed in its own subgroup, but the else branch is more complex and likely slower
+            self.files.len()
+        } else {
+            FileSubGroup::group(&self.files, &filter.root_paths).len()
+        }
+    }
+
+    /// Sorts the files by their path names.
+    /// If filter requires grouping by roots, then groups are kept together.
+    pub fn sort(&mut self, root_paths: &[Path]) {
+        self.files.sort_by(|f1, f2| f1.path().cmp(f2.path()));
+        if !root_paths.is_empty() {
+            self.files = FileSubGroup::group(self.files.drain(..), root_paths)
+                .into_iter()
+                .flat_map(|g| g.files)
+                .collect()
+        }
+    }
+}
+
+/// A subgroup of identical files, typically smaller than a `FileGroup`.
+/// A subgroup is formed by files sharing the same path prefix, e.g. files on the same volume.
+/// In terms of file deduplication activities, a subgroup is an atomic entity -
+/// all files in a subgroup must be either dropped or kept.
+#[derive(Debug, Eq, PartialEq)]
+struct FileSubGroup<F> {
+    files: Vec<F>,
+}
+
+impl<F> FileSubGroup<F> {
+    pub fn empty() -> FileSubGroup<F> {
+        FileSubGroup { files: vec![] }
+    }
+    pub fn single(f: F) -> FileSubGroup<F> {
+        FileSubGroup { files: vec![f] }
+    }
+}
+
+impl<F: AsPath> FileSubGroup<F> {
+    /// Splits a group of files into subgroups.
+    ///
+    /// Files that share the same prefix found in the roots array are placed in the same subgroup.
+    /// The result vector is ordered primarily by the roots, and files having the same root have
+    /// the same order as they came from the input iterator.
+    pub fn group(files: impl IntoIterator<Item = F>, roots: &[Path]) -> Vec<FileSubGroup<F>> {
+        let mut sub_groups = Vec::from_iter(roots.iter().map(|_| FileSubGroup::empty()));
+        for f in files {
+            let path = f.path();
+            let root_idx = roots.iter().position(|r| r.is_prefix_of(path));
+            match root_idx {
+                Some(idx) => sub_groups[idx].files.push(f),
+                None => sub_groups.push(FileSubGroup::single(f)),
+            }
+        }
+        sub_groups.retain(|sg| !sg.files.is_empty());
+        sub_groups
     }
 }
 
@@ -430,31 +559,27 @@ fn scan_files(ctx: &AppCtx<'_>) -> Vec<Vec<FileInfo>> {
     files
 }
 
-/// Finds the path root that is a prefix of the given path.
-/// If no match is found, returns the original path.
-fn root_of<'a>(path: &'a Path, roots: &'a [Path]) -> &'a Path {
-    for p in roots {
-        if p.is_prefix_of(path) {
-            return p;
-        }
-    }
-    path
+/// Returns the sum of number of files in all groups
+fn file_count<'a, T: 'a>(groups: impl IntoIterator<Item = &'a FileGroup<T>>) -> usize {
+    groups.into_iter().map(|g| g.file_count()).sum()
+}
+
+/// Returns the sum of sizes of files in all groups, including duplicates
+fn total_size<'a, T: 'a>(groups: impl IntoIterator<Item = &'a FileGroup<T>>) -> FileLen {
+    groups.into_iter().map(|g| g.total_size()).sum()
 }
 
-/// Returns `true` if a group of files is big enough to meet the desired grouping criteria.
-/// The number of distinct files in a group must be greater than `rf-over`.
-/// If `--isolate` flag is set, file paths that start with a common input path are counted as one.
-/// Called on each result group after each stage.
-fn should_forward<P: AsPath>(ctx: &AppCtx<'_>, group: &[P]) -> bool {
-    if !ctx.config.isolate {
-        group.len() > ctx.config.rf_over()
-    } else {
-        let s: HashSet<_> = group
-            .iter()
-            .map(|p| root_of(p.path(), &ctx.input_paths))
-            .collect();
-        s.len() > ctx.config.rf_over()
+/// Returns an estimation of the number of files matching the search criteria
+fn stage_stats(groups: &[FileGroup<FileInfo>], filter: &FileGroupFilter) -> (usize, FileLen) {
+    let mut total_count = 0;
+    let mut total_size = FileLen(0);
+    for g in groups {
+        let count = g.reported_count(filter);
+        let size = g.file_len * count as u64;
+        total_count += count;
+        total_size += size;
     }
+    (total_count, total_size)
 }
 
 fn group_by_size(ctx: &AppCtx<'_>, files: Vec<Vec<FileInfo>>) -> Vec<FileGroup<FileInfo>> {
@@ -468,24 +593,21 @@ fn group_by_size(ctx: &AppCtx<'_>, files: Vec<Vec<FileInfo>>) -> Vec<FileGroup<F
             groups.add(file);
         }
     }
-    let rf_over = ctx.config.rf_over();
-    let rf_under = ctx.config.rf_under();
 
     let groups: Vec<_> = groups
         .into_iter()
-        .filter(|(_, files)| should_forward(ctx, files.as_slice()))
         .map(|(l, files)| FileGroup {
             file_len: l,
             file_hash: FileHash(0),
             files: files.into_vec(),
         })
+        .filter(|g| g.matches(&ctx.group_filter))
         .collect();
 
-    let count: usize = groups.selected_count(rf_over, rf_under);
-    let bytes: FileLen = groups.selected_size(rf_over, rf_under);
+    let stats = stage_stats(&groups, &ctx.group_filter);
     ctx.log.info(format!(
         "Found {} ({}) candidates after grouping by size",
-        count, bytes
+        stats.0, stats.1
     ));
     groups
 }
@@ -532,26 +654,21 @@ fn remove_same_files(
     ctx: &AppCtx<'_>,
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
-    let file_count: usize = groups.total_count();
     let progress = ctx
         .log
-        .progress_bar("Removing same files", file_count as u64);
-
-    let rf_over = ctx.config.rf_over();
-    let rf_under = ctx.config.rf_under();
+        .progress_bar("Removing same files", file_count(&groups) as u64);
 
     let groups: Vec<_> = groups
         .into_par_iter()
         .update(|g| deduplicate(ctx, &mut g.files, |_| progress.tick()))
-        .filter(|g| should_forward(ctx, g.files.as_slice()))
+        .filter(|g| g.matches(&ctx.group_filter))
         .collect();
 
-    let count: usize = groups.selected_count(rf_over, rf_under);
-    let bytes: FileLen = groups.selected_size(rf_over, rf_under);
+    let stats = stage_stats(&groups, &ctx.group_filter);
     ctx.log.info(format!(
         "Found {} ({}) candidates after grouping by paths {}",
-        count,
-        bytes,
+        stats.0,
+        stats.1,
         if ctx.config.hard_links {
             ""
         } else {
@@ -572,7 +689,7 @@ fn atomic_counter_vec(len: usize) -> Vec<AtomicU32> {
 fn update_file_locations(ctx: &AppCtx<'_>, groups: &mut Vec<FileGroup<FileInfo>>) {
     #[cfg(target_os = "linux")]
     {
-        let count = groups.total_count();
+        let count = file_count(groups.iter());
         let progress = ctx.log.progress_bar("Fetching extents", count as u64);
 
         let err_counters = atomic_counter_vec(ctx.devices.len());
@@ -641,18 +758,14 @@ fn group_transformed(
     transform: &Transform,
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
-    let file_count: usize = groups.total_count();
     let progress = ctx
         .log
-        .progress_bar("Transforming & grouping", file_count as u64);
-
-    let rf_over = ctx.config.rf_over();
-    let rf_under = ctx.config.rf_under();
+        .progress_bar("Transforming & grouping", file_count(&groups) as u64);
 
     let groups = rehash(
         groups,
         |_| true,
-        |g| should_forward(ctx, g.files.as_slice()),
+        |g| g.matches(&ctx.group_filter),
         &ctx.devices,
         AccessType::Sequential,
         |(fi, _)| {
@@ -667,12 +780,11 @@ fn group_transformed(
         },
     );
 
-    let count = groups.selected_count(rf_over, rf_under);
-    let bytes = groups.selected_size(rf_over, rf_under);
+    let stats = stage_stats(&groups, &ctx.group_filter);
     ctx.log.info(format!(
         "Found {} ({}) {} files",
-        count,
-        bytes,
+        stats.0,
+        stats.1,
         ctx.config.search_type()
     ));
     groups
@@ -709,18 +821,15 @@ fn group_by_prefix(
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
     let pre_filter = |g: &FileGroup<FileInfo>| g.files.len() > 1;
-    let remaining_files = groups.iter().filter(|&g| pre_filter(g)).total_count();
+    let file_count = file_count(groups.iter().filter(|&g| pre_filter(g)));
     let progress = ctx
         .log
-        .progress_bar("Grouping by prefix", remaining_files as u64);
-
-    let rf_over = ctx.config.rf_over();
-    let rf_under = ctx.config.rf_under();
+        .progress_bar("Grouping by prefix", file_count as u64);
 
     let groups = rehash(
         groups,
         pre_filter,
-        |g| should_forward(ctx, g.files.as_slice()),
+        |g| g.matches(&ctx.group_filter),
         &ctx.devices,
         AccessType::Random,
         |(fi, _)| {
@@ -745,11 +854,10 @@ fn group_by_prefix(
         },
     );
 
-    let count = groups.selected_count(rf_over, rf_under);
-    let bytes = groups.selected_size(rf_over, rf_under);
+    let stats = stage_stats(&groups, &ctx.group_filter);
     ctx.log.info(format!(
         "Found {} ({}) candidates after grouping by prefix",
-        count, bytes
+        stats.0, stats.1
     ));
     groups
 }
@@ -775,18 +883,15 @@ fn group_by_suffix(ctx: &AppCtx<'_>, groups: Vec<FileGroup<FileInfo>>) -> Vec<Fi
     let suffix_len = suffix_len(&ctx.devices, flat_iter(&groups));
     let suffix_threshold = suffix_threshold(&ctx.devices, flat_iter(&groups));
     let pre_filter = |g: &FileGroup<FileInfo>| g.file_len >= suffix_threshold && g.files.len() > 1;
-    let remaining_files = groups.iter().filter(|&g| pre_filter(g)).total_count();
+    let file_count = file_count(groups.iter().filter(|&g| pre_filter(g)));
     let progress = ctx
         .log
-        .progress_bar("Grouping by suffix", remaining_files as u64);
-
-    let rf_over = ctx.config.rf_over();
-    let rf_under = ctx.config.rf_under();
+        .progress_bar("Grouping by suffix", file_count as u64);
 
     let groups = rehash(
         groups,
         pre_filter,
-        |g| should_forward(ctx, g.files.as_slice()),
+        |g| g.matches(&ctx.group_filter),
         &ctx.devices,
         AccessType::Random,
         |(fi, old_hash)| {
@@ -806,11 +911,10 @@ fn group_by_suffix(ctx: &AppCtx<'_>, groups: Vec<FileGroup<FileInfo>>) -> Vec<Fi
         },
     );
 
-    let count = groups.selected_count(rf_over, rf_under);
-    let bytes = groups.selected_size(rf_over, rf_under);
+    let stats = stage_stats(&groups, &ctx.group_filter);
     ctx.log.info(format!(
         "Found {} ({}) candidates after grouping by suffix",
-        count, bytes
+        stats.0, stats.1
     ));
     groups
 }
@@ -821,18 +925,15 @@ fn group_by_contents(
     groups: Vec<FileGroup<FileInfo>>,
 ) -> Vec<FileGroup<FileInfo>> {
     let pre_filter = |g: &FileGroup<FileInfo>| g.files.len() > 1 && g.file_len >= min_file_len;
-    let bytes_to_scan = groups.iter().filter(|&g| pre_filter(g)).total_size();
+    let bytes_to_scan = total_size(groups.iter().filter(|&g| pre_filter(g)));
     let progress = &ctx
         .log
         .bytes_progress_bar("Grouping by contents", bytes_to_scan.0);
 
-    let rf_over = ctx.config.rf_over();
-    let rf_under = ctx.config.rf_under();
-
     let groups = rehash(
         groups,
         pre_filter,
-        |g| should_forward(ctx, g.files.as_slice()),
+        |g| g.matches_strictly(&ctx.group_filter),
         &ctx.devices,
         AccessType::Sequential,
         |(fi, _)| {
@@ -850,12 +951,11 @@ fn group_by_contents(
         },
     );
 
-    let count = groups.selected_count(rf_over, rf_under);
-    let bytes = groups.selected_size(rf_over, rf_under);
+    let stats = stage_stats(&groups, &ctx.group_filter);
     ctx.log.info(format!(
         "Found {} ({}) {} files",
-        count,
-        bytes,
+        stats.0,
+        stats.1,
         ctx.config.search_type()
     ));
     groups
@@ -955,7 +1055,9 @@ pub fn group_files(config: &GroupConfig, log: &Log) -> Result<Vec<FileGroup<Path
         .collect();
     groups.retain(|g| g.files.len() < ctx.config.rf_under());
     groups.par_sort_by_key(|g| Reverse((g.file_len, g.file_hash)));
-    groups.par_iter_mut().for_each(|g| g.files.sort());
+    groups
+        .par_iter_mut()
+        .for_each(|g| g.sort(&ctx.group_filter.root_paths));
     Ok(groups)
 }
 
@@ -971,7 +1073,19 @@ pub fn group_files(config: &GroupConfig, log: &Log) -> Result<Vec<FileGroup<Path
 /// Returns [`io::Error`] on I/O write error or if the output file cannot be created.
 pub fn write_report(config: &GroupConfig, log: &Log, groups: &[FileGroup<Path>]) -> io::Result<()> {
     let now = Local::now();
-    let rf_over = max(1, config.rf_over());
+
+    let total_count = file_count(groups.iter());
+    let total_size = total_size(groups.iter());
+
+    let (redundant_count, redundant_size) = groups.iter().fold((0, FileLen(0)), |res, g| {
+        let count = g.redundant_count(&config.group_filter());
+        (res.0 + count, res.1 + g.file_len * count as u64)
+    });
+    let (missing_count, missing_size) = groups.iter().fold((0, FileLen(0)), |res, g| {
+        let count = g.missing_count(&config.group_filter());
+        (res.0 + count, res.1 + g.file_len * count as u64)
+    });
+
     let header = ReportHeader {
         timestamp: DateTime::from_utc(now.naive_utc(), *now.offset()),
         version: env!("CARGO_PKG_VERSION").to_owned(),
@@ -979,8 +1093,12 @@ pub fn write_report(config: &GroupConfig, log: &Log, groups: &[FileGroup<Path>])
         base_dir: config.base_dir.to_string_lossy().to_string(),
         stats: Some(FileStats {
             group_count: groups.len(),
-            redundant_file_count: groups.selected_count(rf_over, usize::MAX),
-            redundant_file_size: groups.selected_size(rf_over, usize::MAX),
+            total_file_count: total_count,
+            total_file_size: total_size,
+            redundant_file_count: redundant_count,
+            redundant_file_size: redundant_size,
+            missing_file_count: missing_count,
+            missing_file_size: missing_size,
         }),
     };
 
@@ -1439,6 +1557,43 @@ mod test {
         });
     }
 
+    #[test]
+    fn split_to_subgroups() {
+        let roots = vec![Path::from("/r0"), Path::from("/r1"), Path::from("/r2")];
+        let files = vec![
+            Path::from("/r1/f1a"),
+            Path::from("/r2/f2a"),
+            Path::from("/r2/f2b"),
+            Path::from("/r1/f1b"),
+            Path::from("/r1/f1c"),
+            Path::from("/r3/f3a"),
+            Path::from("/r2/f2c"),
+        ];
+        let groups = FileSubGroup::group(files, &roots);
+        assert_eq!(
+            groups,
+            vec![
+                FileSubGroup {
+                    files: vec![
+                        Path::from("/r1/f1a"),
+                        Path::from("/r1/f1b"),
+                        Path::from("/r1/f1c"),
+                    ]
+                },
+                FileSubGroup {
+                    files: vec![
+                        Path::from("/r2/f2a"),
+                        Path::from("/r2/f2b"),
+                        Path::from("/r2/f2c")
+                    ]
+                },
+                FileSubGroup {
+                    files: vec![Path::from("/r3/f3a")]
+                }
+            ]
+        )
+    }
+
     fn write_test_file(path: &PathBuf, prefix: &[u8], mid: &[u8], suffix: &[u8]) {
         let mut file = OpenOptions::new()
             .write(true)
diff --git a/src/report.rs b/src/report.rs
index 2335b5a..7b80c20 100644
--- a/src/report.rs
+++ b/src/report.rs
@@ -26,8 +26,12 @@ use crate::{FileGroup, TIMESTAMP_FMT};
 #[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
 pub struct FileStats {
     pub group_count: usize,
+    pub total_file_count: usize,
+    pub total_file_size: FileLen,
     pub redundant_file_count: usize,
     pub redundant_file_size: FileLen,
+    pub missing_file_count: usize,
+    pub missing_file_size: FileLen,
 }
 
 /// Data in the header of the whole report.
@@ -95,24 +99,23 @@ impl<W: Write> ReportWriter<W> {
     ///
     /// # Example
     /// ```text
-    /// # Report by fclones 0.12.0
-    /// # Timestamp: Mon, 03 May 2021 13:22:51 +0000
-    /// # Command: target/debug/fclones find . -o report.txt
+    /// # Report by fclones 0.18.0
+    /// # Timestamp: 2022-03-18 08:22:00.844 +0100
+    /// # Command: fclones group .
     /// # Base dir: /home/pkolaczk/Projekty/fclones
-    /// # Found 553 file groups
-    /// # 271.8 MB in 4266 redundant files can be removed
-    /// 5649a555c131508c4a757d9e14c4aea6, 6626689 B (6.6 MB) * 5:
-    ///     /home/pkolaczk/Projekty/fclones/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.0/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.1/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.2/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.11.0/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta
-    /// f79ce189d76620fd921986943087dc3a, 5815999 B (5.8 MB) * 5:
-    ///     /home/pkolaczk/Projekty/fclones/target/debug/deps/libserde-af05e0212e5def7d.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.0/target/debug/deps/libserde-af05e0212e5def7d.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.1/target/debug/deps/libserde-af05e0212e5def7d.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.2/target/debug/deps/libserde-af05e0212e5def7d.rmeta
-    ///     /home/pkolaczk/Projekty/fclones/target/package/fclones-0.11.0/target/debug/deps/libserde-af05e0212e5def7d.rmeta
+    /// # Total: 13589 B (13.6 KB) in 31 files in 14 groups
+    /// # Redundant: 6819 B (6.8 KB) in 17 files
+    /// # Missing: 0 B (0 B) in 0 files
+    /// 49165422e775f631cca3b09124f8ee89, 6274 B (6.3 KB) * 2:
+    ///     /home/pkolaczk/Projekty/fclones/src/semaphore.rs
+    ///     /home/pkolaczk/Projekty/fclones/.git/rr-cache/d5cde6e71942982e722d6dfe41936c9036ba9f4b/postimage
+    /// dcf2e11190ccc260f2388d9a5a2ed20e, 41 B (41 B) * 2:
+    ///     /home/pkolaczk/Projekty/fclones/.git/refs/heads/diff_roots
+    ///     /home/pkolaczk/Projekty/fclones/.git/refs/remotes/origin/diff_roots
+    /// d0521f268e17c28b10c48e5f5de48f21, 41 B (41 B) * 2:
+    ///     /home/pkolaczk/Projekty/fclones/.git/refs/heads/fix_flock_freebsd
+    ///     /home/pkolaczk/Projekty/fclones/.git/refs/remotes/origin/fix_flock_freebsd
+    /// ...
     /// ```
     pub fn write_as_text<I, G, P>(&mut self, header: &ReportHeader, groups: I) -> io::Result<()>
     where
@@ -129,11 +132,21 @@ impl<W: Write> ReportWriter<W> {
         self.write_header_line(&format!("Command: {}", command))?;
         self.write_header_line(&format!("Base dir: {}", header.base_dir))?;
         if let Some(stats) = &header.stats {
-            self.write_header_line(&format!("Found {} file groups", stats.group_count))?;
             self.write_header_line(&format!(
-                "{} B ({}) in {} redundant files can be removed",
+                "Total: {} B ({}) in {} files in {} groups",
+                stats.total_file_size.0,
+                stats.total_file_size,
+                stats.total_file_count,
+                stats.group_count
+            ))?;
+            self.write_header_line(&format!(
+                "Redundant: {} B ({}) in {} files",
                 stats.redundant_file_size.0, stats.redundant_file_size, stats.redundant_file_count
             ))?;
+            self.write_header_line(&format!(
+                "Missing: {} B ({}) in {} files",
+                stats.missing_file_size.0, stats.missing_file_size, stats.missing_file_count
+            ))?;
         }
 
         for g in groups {
@@ -214,49 +227,43 @@ impl<W: Write> ReportWriter<W> {
     /// ```json
     /// {
     ///   "header": {
-    ///     "version": "0.12.0",
-    ///     "timestamp": "2021-05-03T13:20:59.285409824+00:00",
+    ///     "version": "0.18.0",
+    ///     "timestamp": "2022-03-18T08:24:28.793228077+01:00",
     ///     "command": [
-    ///       "target/debug/fclones",
-    ///       "find",
+    ///       "fclones",
+    ///       "group",
     ///       ".",
     ///       "-f",
-    ///       "JSON",
-    ///       "-o",
-    ///       "report.json"
+    ///       "json"
     ///     ],
+    ///     "base_dir": "/home/pkolaczk/Projekty/fclones",
     ///     "stats": {
-    ///       "group_count": 553,
-    ///       "redundant_file_count": 4266,
-    ///       "redundant_file_size": 271838709
+    ///       "group_count": 14,
+    ///       "total_file_count": 31,
+    ///       "total_file_size": 13589,
+    ///       "redundant_file_count": 17,
+    ///       "redundant_file_size": 6819,
+    ///       "missing_file_count": 0,
+    ///       "missing_file_size": 0
     ///     }
     ///   },
     ///   "groups": [
     ///     {
-    ///       "file_len": 6626689,
-    ///       "file_hash": "5649a555c131508c4a757d9e14c4aea6",
+    ///       "file_len": 6274,
+    ///       "file_hash": "49165422e775f631cca3b09124f8ee89",
     ///       "files": [
-    ///         "/home/pkolaczk/Projekty/fclones/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.0/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.1/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.2/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.11.0/target/debug/deps/libregex_syntax-94c84f5600b85f6e.rmeta"
+    ///         "/home/pkolaczk/Projekty/fclones/src/semaphore.rs",
+    ///         "/home/pkolaczk/Projekty/fclones/.git/rr-cache/d5cde6e71942982e722d6dfe41936c9036ba9f4b/postimage"
     ///       ]
     ///     },
     ///     {
-    ///       "file_len": 5815999,
-    ///       "file_hash": "f79ce189d76620fd921986943087dc3a",
+    ///       "file_len": 41,
+    ///       "file_hash": "dcf2e11190ccc260f2388d9a5a2ed20e",
     ///       "files": [
-    ///         "/home/pkolaczk/Projekty/fclones/target/debug/deps/libserde-af05e0212e5def7d.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.0/target/debug/deps/libserde-af05e0212e5def7d.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.1/target/debug/deps/libserde-af05e0212e5def7d.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.10.2/target/debug/deps/libserde-af05e0212e5def7d.rmeta",
-    ///         "/home/pkolaczk/Projekty/fclones/target/package/fclones-0.11.0/target/debug/deps/libserde-af05e0212e5def7d.rmeta"
+    ///         "/home/pkolaczk/Projekty/fclones/.git/refs/heads/diff_roots",
+    ///         "/home/pkolaczk/Projekty/fclones/.git/refs/remotes/origin/diff_roots"
     ///       ]
     ///     },
-    ///      ...
-    ///   ]
-    /// }
     /// ```
     pub fn write_as_json<I, P>(&mut self, header: &ReportHeader, groups: I) -> io::Result<()>
     where
@@ -448,16 +455,60 @@ impl<R: BufRead> TextReportReader<R> {
         Ok(line_buf)
     }
 
-    fn read_extract(&mut self, regex: &Regex, msg: &str) -> io::Result<Vec<String>> {
+    fn read_extract(&mut self, regex: &Regex, name: &str) -> io::Result<Vec<String>> {
         let line = self.read_line()?;
         Ok(regex
             .captures(line.trim())
-            .ok_or_else(|| Error::new(ErrorKind::InvalidData, msg.to_owned()))?
+            .ok_or_else(|| {
+                Error::new(
+                    ErrorKind::InvalidData,
+                    format!("Malformed header: Missing {}", name),
+                )
+            })?
             .iter()
             .skip(1)
             .map(|c| c.unwrap().as_str().to_owned())
             .collect())
     }
+
+    fn parse_timestamp(value: &str, name: &str) -> io::Result<DateTime<FixedOffset>> {
+        DateTime::parse_from_str(value, TIMESTAMP_FMT).map_err(|e| {
+            Error::new(
+                ErrorKind::InvalidData,
+                format!(
+                    "Malformed header: Failed to parse {}: {}. Expected timestamp format: {}",
+                    name, e, TIMESTAMP_FMT
+                ),
+            )
+        })
+    }
+
+    fn parse_u64(value: Option<&String>, name: &str) -> io::Result<u64> {
+        match value {
+            Some(value) => value.parse().map_err(|e| {
+                Error::new(
+                    ErrorKind::InvalidData,
+                    format!(
+                        "Malformed header: Failed to parse {}: {}. Expected integer value.",
+                        name, e
+                    ),
+                )
+            }),
+            None => Err(Error::new(
+                ErrorKind::InvalidData,
+                format!("Malformed header: Missing {}", name),
+            )),
+        }
+    }
+
+    fn parse_usize(value: Option<&String>, name: &str) -> io::Result<usize> {
+        Ok(Self::parse_u64(value, name)? as usize)
+    }
+
+    fn parse_file_len(value: Option<&String>, name: &str) -> io::Result<FileLen> {
+        let value = Self::parse_u64(value, name)?;
+        Ok(FileLen(value))
+    }
 }
 
 impl<R: BufRead + Send + 'static> ReportReader for TextReportReader<R> {
@@ -468,66 +519,43 @@ impl<R: BufRead + Send + 'static> ReportReader for TextReportReader<R> {
             static ref TIMESTAMP_RE: Regex = Regex::new(r"^# Timestamp: (.*)").unwrap();
             static ref COMMAND_RE: Regex = Regex::new(r"^# Command: (.*)").unwrap();
             static ref BASE_DIR_RE: Regex = Regex::new(r"^# Base dir: (.*)").unwrap();
-            static ref GROUP_COUNT_RE: Regex =
-                Regex::new(r"^# Found ([0-9]+) file groups").unwrap();
-            static ref STATS_RE: Regex =
-                Regex::new(r"^# ([0-9]+) B \([^)]+\) in ([0-9]+) redundant files can be removed")
+            static ref TOTAL_RE: Regex =
+                Regex::new(r"^# Total: ([0-9]+) B \([^)]+\) in ([0-9]+) files in ([0-9]+) groups")
                     .unwrap();
+            static ref REDUNDANT_RE: Regex =
+                Regex::new(r"^# Redundant: ([0-9]+) B \([^)]+\) in ([0-9]+) files").unwrap();
+            static ref MISSING_RE: Regex =
+                Regex::new(r"^# Missing: ([0-9]+) B \([^)]+\) in ([0-9]+) files").unwrap();
         }
 
         let version = self
-            .read_extract(&VERSION_RE, "Malformed header: Missing fclones version")?
+            .read_extract(&VERSION_RE, "fclones version")?
             .swap_remove(0);
         let timestamp = self
-            .read_extract(&TIMESTAMP_RE, "Malformed header: Missing timestamp")?
-            .swap_remove(0);
-        let timestamp = DateTime::parse_from_str(&timestamp, TIMESTAMP_FMT).map_err(|e| {
-            Error::new(
-                ErrorKind::InvalidData,
-                format!("Malformed header: Failed to parse timestamp: {}", e),
-            )
-        })?;
-        let command = self
-            .read_extract(&COMMAND_RE, "Malformed header: Missing command")?
+            .read_extract(&TIMESTAMP_RE, "timestamp")?
             .swap_remove(0);
+        let timestamp = Self::parse_timestamp(&timestamp, "timestamp")?;
+        let command = self.read_extract(&COMMAND_RE, "command")?.swap_remove(0);
         let command = shell_words::split(&command).map_err(|e| {
             Error::new(
                 ErrorKind::InvalidData,
                 format!("Malformed header: Failed to parse command arguments: {}", e),
             )
         })?;
-        let base_dir = self
-            .read_extract(&BASE_DIR_RE, "Malformed header: Missing base dir")?
-            .swap_remove(0);
-        let group_count = self
-            .read_extract(&GROUP_COUNT_RE, "Malformed header: Missing group count")?
-            .swap_remove(0);
-        let group_count: usize = group_count.parse().map_err(|e| {
-            Error::new(
-                ErrorKind::InvalidData,
-                format!("Malformed header: Failed to parse group count: {}", e),
-            )
-        })?;
-        let stats_line =
-            self.read_extract(&STATS_RE, "Malformed header: Missing file statistics line")?;
-        let redundant_file_size = FileLen(stats_line[0].parse().map_err(|e| {
-            Error::new(
-                ErrorKind::InvalidData,
-                format!(
-                    "Malformed header: Failed to parse file size {}: {}",
-                    stats_line[0], e
-                ),
-            )
-        })?);
-        let redundant_file_count: usize = stats_line[1].parse().map_err(|e| {
-            Error::new(
-                ErrorKind::InvalidData,
-                format!(
-                    "Malformed header: Failed to parse file count {}: {}",
-                    stats_line[1], e
-                ),
-            )
-        })?;
+        let base_dir = self.read_extract(&BASE_DIR_RE, "base dir")?.swap_remove(0);
+
+        let stats = self.read_extract(&TOTAL_RE, "total file statistics")?;
+        let total_file_size = Self::parse_file_len(stats.get(0), "total file size")?;
+        let total_file_count = Self::parse_usize(stats.get(1), "total file count")?;
+        let group_count = Self::parse_usize(stats.get(2), "group count")?;
+
+        let stats = self.read_extract(&REDUNDANT_RE, "redundant file statistics")?;
+        let redundant_file_size = Self::parse_file_len(stats.get(0), "redundant file size")?;
+        let redundant_file_count = Self::parse_usize(stats.get(1), "redundant file count")?;
+
+        let stats = self.read_extract(&MISSING_RE, "missing file statistics")?;
+        let missing_file_size = Self::parse_file_len(stats.get(0), "missing file size")?;
+        let missing_file_count = Self::parse_usize(stats.get(1), "missing file count")?;
 
         Ok(ReportHeader {
             version,
@@ -536,8 +564,12 @@ impl<R: BufRead + Send + 'static> ReportReader for TextReportReader<R> {
             base_dir,
             stats: Some(FileStats {
                 group_count,
+                total_file_count,
+                total_file_size,
                 redundant_file_count,
                 redundant_file_size,
+                missing_file_count,
+                missing_file_size,
             }),
         })
     }
@@ -628,8 +660,12 @@ mod test {
                 .unwrap(),
             stats: Some(FileStats {
                 group_count: 4,
+                total_file_count: 1000,
+                total_file_size: FileLen(2500),
                 redundant_file_count: 234,
                 redundant_file_size: FileLen(1000),
+                missing_file_count: 93,
+                missing_file_size: FileLen(300),
             }),
         }
     }


Test patch: