Patchwork D11616: rhg: stop manifest traversal when no more files are needed

login
register
mail settings
Submitter phabricator
Date Oct. 5, 2021, 2:16 p.m.
Message ID <differential-rev-PHID-DREV-vjzrjtynk5w3lo4no4ps-req@mercurial-scm.org>
Download mbox | patch
Permalink /patch/49939/
State Superseded
Headers show

Comments

phabricator - Oct. 5, 2021, 2:16 p.m.
aalekseyev created this revision.
Herald added a reviewer: hg-reviewers.
Herald added a subscriber: mercurial-patches.

REPOSITORY
  rHG Mercurial

BRANCH
  default

REVISION DETAIL
  https://phab.mercurial-scm.org/D11616

AFFECTED FILES
  rust/hg-core/src/operations/cat.rs

CHANGE DETAILS




To: aalekseyev, #hg-reviewers
Cc: mercurial-patches, mercurial-devel

Patch

diff --git a/rust/hg-core/src/operations/cat.rs b/rust/hg-core/src/operations/cat.rs
--- a/rust/hg-core/src/operations/cat.rs
+++ b/rust/hg-core/src/operations/cat.rs
@@ -9,10 +9,12 @@ 
 use crate::revlog::revlog::RevlogError;
 use crate::revlog::Node;
 
+use crate::utils::hg_path::HgPath;
 use crate::utils::hg_path::HgPathBuf;
 
-use itertools::EitherOrBoth::{Both, Left, Right};
-use itertools::Itertools;
+use itertools::put_back;
+use itertools::PutBack;
+use std::cmp::Ordering;
 
 pub struct CatOutput {
     /// Whether any file in the manifest matched the paths given as CLI
@@ -26,6 +28,50 @@ 
     pub node: Node,
 }
 
+// Find an item in an iterator over a sorted collection.
+fn find_item<'a, 'b, 'c, D, I: Iterator<Item = (&'a HgPath, D)>>(
+    i: &mut PutBack<I>,
+    needle: &'b HgPath,
+) -> Option<I::Item> {
+    loop {
+        match i.next() {
+            None => return None,
+            Some(val) => match needle.as_bytes().cmp(val.0.as_bytes()) {
+                Ordering::Less => {
+                    i.put_back(val);
+                    return None;
+                }
+                Ordering::Greater => continue,
+                Ordering::Equal => return Some(val),
+            },
+        }
+    }
+}
+
+fn find_files_in_manifest<
+    'a,
+    'b,
+    'c,
+    D,
+    I: Iterator<Item = (&'a HgPath, D)>,
+    J: Iterator<Item = &'b HgPath>,
+>(
+    i: I,
+    j: J,
+) -> (Vec<(&'a HgPath, D)>, Vec<&'b HgPath>) {
+    let mut manifest_iterator = put_back(i);
+    let mut res = vec![];
+    let mut missing = vec![];
+
+    for file in j {
+        match find_item(&mut manifest_iterator, file) {
+            None => missing.push(file),
+            Some(item) => res.push(item),
+        }
+    }
+    return (res, missing);
+}
+
 /// Output the given revision of files
 ///
 /// * `root`: Repository root
@@ -42,36 +88,28 @@ 
         .changelog()?
         .node_from_rev(rev)
         .expect("should succeed when repo.manifest did");
-    let mut bytes = vec![];
+    let mut bytes: Vec<u8> = vec![];
     let mut found_any = false;
+
     files.sort_unstable();
 
-    let mut missing = vec![];
+    let (found, missing) = find_files_in_manifest(
+        manifest.files_with_nodes(),
+        files.iter().map(|f| f.as_ref()),
+    );
 
-    for entry in manifest
-        .files_with_nodes()
-        .merge_join_by(files.iter(), |(manifest_file, _), file| {
-            manifest_file.cmp(&file.as_ref())
-        })
-    {
-        match entry {
-            Left(_) => (),
-            Right(path) => missing.push(path),
-            Both((manifest_file, node_bytes), _) => {
-                found_any = true;
-                let file_log = repo.filelog(manifest_file)?;
-                let file_node = Node::from_hex_for_repo(node_bytes)?;
-                let entry = file_log.data_for_node(file_node)?;
-                bytes.extend(entry.data()?)
-            }
-        }
+    for (manifest_file, node_bytes) in found {
+        found_any = true;
+        let file_log = repo.filelog(manifest_file)?;
+        let file_node = Node::from_hex_for_repo(node_bytes)?;
+        bytes.extend(file_log.data_for_node(file_node)?.data()?);
     }
 
     // make the order of the [missing] files
     // match the order they were specified on the command line
     let missing: Vec<_> = files
         .iter()
-        .filter(|file| missing.contains(file))
+        .filter(|file| missing.contains(&file.as_ref()))
         .map(|file| file.clone())
         .collect();
     Ok(CatOutput {