use `gix-glob` for matching; support for matching dirs only.

That way, git-like globs can be used which support nice extras, like
searching for directories only.

8 files changed, 151 insertions, 52 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 1a02b92..6e7b3dd 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -15,15 +15,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "aho-corasick"
-version = "1.1.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b2969dcb958b36655471fc61f7e416fa76033bdd4bfed0678d8fee1e2d07a1f0"
-dependencies = [
- "memchr",
-]
-
-[[package]]
 name = "allocator-api2"
 version = "0.2.16"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -119,6 +110,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "542f33a8835a0884b006a0c3df3dadd99c0c3f296ed26c2fdc8028e01ad6230c"
 dependencies = [
  "memchr",
+ "regex-automata",
  "serde",
 ]
 
@@ -315,12 +307,14 @@ version = "2.23.0"
 dependencies = [
  "anyhow",
  "atty",
+ "bstr",
  "byte-unit",
  "chrono",
  "clap",
  "crosstermion",
  "filesize",
- "globset",
+ "gix-glob",
+ "gix-path",
  "human_format",
  "itertools 0.12.0",
  "jwalk",
@@ -351,6 +345,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5443807d6dff69373d433ab9ef5378ad8df50ca6298caf15de6e52e24aaf54d5"
 
 [[package]]
+name = "faster-hex"
+version = "0.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a2a2b11eda1d40935b26cf18f6833c526845ae8c41e58d09af6adeb6f0269183"
+dependencies = [
+ "serde",
+]
+
+[[package]]
 name = "filesize"
 version = "0.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -375,25 +378,64 @@ dependencies = [
 ]
 
 [[package]]
-name = "glob"
-version = "0.3.1"
+name = "gix-features"
+version = "0.36.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "d2fabcfbdc87f4758337ca535fb41a6d701b65693ce38287d856d1674551ec9b"
+checksum = "4d46a4a5c6bb5bebec9c0d18b65ada20e6517dbd7cf855b87dd4bbdce3a771b2"
+dependencies = [
+ "gix-hash",
+ "gix-trace",
+ "libc",
+]
 
 [[package]]
-name = "globset"
-version = "0.4.14"
+name = "gix-glob"
+version = "0.14.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "57da3b9b5b85bd66f31093f8c408b90a74431672542466497dcbdfdc02034be1"
+checksum = "5db19298c5eeea2961e5b3bf190767a2d1f09b8802aeb5f258e42276350aff19"
 dependencies = [
- "aho-corasick",
+ "bitflags 2.4.1",
  "bstr",
- "log",
- "regex-automata",
- "regex-syntax",
+ "gix-features",
+ "gix-path",
+]
+
+[[package]]
+name = "gix-hash"
+version = "0.13.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1f8cf8c2266f63e582b7eb206799b63aa5fa68ee510ad349f637dfe2d0653de0"
+dependencies = [
+ "faster-hex",
+ "thiserror",
+]
+
+[[package]]
+name = "gix-path"
+version = "0.10.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d86d6fac2fabe07b67b7835f46d07571f68b11aa1aaecae94fe722ea4ef305e1"
+dependencies = [
+ "bstr",
+ "gix-trace",
+ "home",
+ "once_cell",
+ "thiserror",
 ]
 
 [[package]]
+name = "gix-trace"
+version = "0.1.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b686a35799b53a9825575ca3f06481d0a053a409c4d97ffcf5ddd67a8760b497"
+
+[[package]]
+name = "glob"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d2fabcfbdc87f4758337ca535fb41a6d701b65693ce38287d856d1674551ec9b"
+
+[[package]]
 name = "hashbrown"
 version = "0.14.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -425,6 +467,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "d77f7ec81a6d05a3abb01ab6eb7590f6083d08449fe5a1c8b1e620283546ccb7"
 
 [[package]]
+name = "home"
+version = "0.5.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e3d1354bf6b7235cb4a0576c2619fd4ed18183f689b12b006a0ee7329eeff9a5"
+dependencies = [
+ "windows-sys 0.52.0",
+]
+
+[[package]]
 name = "human_format"
 version = "1.0.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -776,17 +827,6 @@ name = "regex-automata"
 version = "0.4.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5f804c7828047e88b2d32e2d7fe5a105da8ee3264f01902f796c8e067dc2483f"
-dependencies = [
- "aho-corasick",
- "memchr",
- "regex-syntax",
-]
-
-[[package]]
-name = "regex-syntax"
-version = "0.8.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c08c74e62047bb2de4ff487b251e4a92e24f48745648451635cec7d591162d9f"
 
 [[package]]
 name = "rustversion"
@@ -908,6 +948,26 @@ dependencies = [
 ]
 
 [[package]]
+name = "thiserror"
+version = "1.0.51"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f11c217e1416d6f036b870f14e0413d480dbf28edbee1f877abaf0206af43bb7"
+dependencies = [
+ "thiserror-impl",
+]
+
+[[package]]
+name = "thiserror-impl"
+version = "1.0.51"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "01742297787513b79cf8e29d1056ede1313e2420b7b3b15d0a768b4921f549df"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
 name = "tinyvec"
 version = "1.6.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 880abdd..1df408e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -41,7 +41,9 @@ wild = "2.0.4"
 owo-colors = "3.5.0"
 human_format = "1.0.3"
 once_cell = "1.19"
-globset = "0.4.14"
+gix-glob = "0.14.1"
+gix-path = "0.10.1"
+bstr = "1.8.0"
 
 [[bin]]
 name="dua"
diff --git a/src/interactive/app/common.rs b/src/interactive/app/common.rs
index 1100cd8..3b79a9a 100644
--- a/src/interactive/app/common.rs
+++ b/src/interactive/app/common.rs
@@ -56,6 +56,8 @@ pub struct EntryDataBundle {
     pub exists: bool,
 }
 
+/// Note that with `glob_root` present, we will not obtain metadata anymore as we might be seeing
+/// a lot of entries. That way, displaying 250k entries is no problem.
 pub fn sorted_entries(
     tree: &Tree,
     node_idx: TreeIndex,
@@ -72,8 +74,15 @@ pub fn sorted_entries(
         .filter_map(|idx| {
             tree.node_weight(idx).map(|entry| {
                 let use_glob_path = glob_root.map_or(false, |glob_root| glob_root == node_idx);
-                let path = path_of(tree, idx, glob_root);
-                let meta = path.symlink_metadata();
+                let (path, exists, is_dir) = {
+                    let path = path_of(tree, idx, glob_root);
+                    if glob_root.is_some() {
+                        (path, true, entry.is_dir)
+                    } else {
+                        let meta = path.symlink_metadata();
+                        (path, meta.is_ok(), meta.ok().map_or(false, |m| m.is_dir()))
+                    }
+                };
                 EntryDataBundle {
                     index: idx,
                     name: if use_glob_path {
@@ -84,8 +93,8 @@ pub fn sorted_entries(
                     size: entry.size,
                     mtime: entry.mtime,
                     entry_count: entry.entry_count,
-                    exists: meta.is_ok(),
-                    is_dir: meta.ok().map_or(false, |m| m.is_dir()),
+                    exists,
+                    is_dir,
                 }
             })
         })
diff --git a/src/interactive/app/tests/unit.rs b/src/interactive/app/tests/unit.rs
index 95fa223..693516f 100644
--- a/src/interactive/app/tests/unit.rs
+++ b/src/interactive/app/tests/unit.rs
@@ -22,7 +22,7 @@ fn it_can_handle_ending_traversal_reaching_top_but_skipping_levels() -> Result<(
 #[test]
 fn it_can_handle_ending_traversal_without_reaching_the_top() -> Result<()> {
     let (_, app) = initialized_app_and_terminal_from_fixture(&["sample-02"])?;
-    let (expected_tree, _) = sample_02_tree();
+    let (expected_tree, _) = sample_02_tree(true);
 
     assert_eq!(
         debug(app.traversal.tree),
@@ -34,7 +34,7 @@ fn it_can_handle_ending_traversal_without_reaching_the_top() -> Result<()> {
 
 #[test]
 fn it_can_do_a_glob_search() {
-    let (tree, root_index) = sample_02_tree();
+    let (tree, root_index) = sample_02_tree(false);
     let result = glob_search(&tree, root_index, "tests/fixtures/sample-02").unwrap();
     let expected = vec![TreeIndex::from(1)];
     assert_eq!(result, expected);
diff --git a/src/interactive/app/tests/utils.rs b/src/interactive/app/tests/utils.rs
index 9aba432..5c76f17 100644
--- a/src/interactive/app/tests/utils.rs
+++ b/src/interactive/app/tests/utils.rs
@@ -255,7 +255,7 @@ pub fn sample_01_tree() -> Tree {
     tree
 }
 
-pub fn sample_02_tree() -> (Tree, TreeIndex) {
+pub fn sample_02_tree(use_native_separator: bool) -> (Tree, TreeIndex) {
     let mut tree = Tree::new();
     let root_index: TreeIndex;
     {
@@ -264,7 +264,15 @@ pub fn sample_02_tree() -> (Tree, TreeIndex) {
         root_index = add_node("", root_size, 10, None);
         {
             let sn = add_node(
-                Path::new(FIXTURE_PATH).join("sample-02").to_str().unwrap(),
+                format!(
+                    "{FIXTURE_PATH}{}sample-02",
+                    if use_native_separator {
+                        std::path::MAIN_SEPARATOR_STR
+                    } else {
+                        "/"
+                    }
+                )
+                .as_str(),
                 root_size,
                 9,
                 Some(root_index),
diff --git a/src/interactive/widgets/glob.rs b/src/interactive/widgets/glob.rs
index b02ac13..0ef95fd 100644
--- a/src/interactive/widgets/glob.rs
+++ b/src/interactive/widgets/glob.rs
@@ -1,10 +1,9 @@
-use anyhow::Result;
+use anyhow::{anyhow, Context, Result};
+use bstr::BString;
 use crosstermion::input::Key;
 use dua::traverse::{Tree, TreeIndex};
-use globset::{Glob, GlobMatcher};
 use petgraph::Direction;
 use std::borrow::Borrow;
-use std::path::PathBuf;
 use tui::backend::Backend;
 use tui::prelude::Buffer;
 use tui::{
@@ -112,7 +111,7 @@ impl GlobPane {
             has_focus,
         } = props.borrow();
 
-        let title = "Glob search from top";
+        let title = "Git-Glob";
         let block = Block::default()
             .title(title)
             .border_style(*border_style)
@@ -178,26 +177,40 @@ fn glob_search_neighbours(
     results: &mut Vec<TreeIndex>,
     tree: &Tree,
     root_index: TreeIndex,
-    glob: &GlobMatcher,
-    path: &mut PathBuf,
+    glob: &gix_glob::Pattern,
+    path: &mut BString,
 ) {
     for node_index in tree.neighbors_directed(root_index, Direction::Outgoing) {
         if let Some(node) = tree.node_weight(node_index) {
-            path.push(&node.name);
-            if glob.is_match(&path) {
+            let previous_len = path.len();
+            let basename_start = if path.is_empty() {
+                None
+            } else {
+                path.push(b'/');
+                Some(previous_len + 1)
+            };
+            path.extend_from_slice(gix_path::into_bstr(&node.name).as_ref());
+            if glob.matches_repo_relative_path(
+                path.as_ref(),
+                basename_start,
+                Some(node.is_dir),
+                gix_glob::pattern::Case::Fold,
+                gix_glob::wildmatch::Mode::NO_MATCH_SLASH_LITERAL,
+            ) {
                 results.push(node_index);
             } else {
                 glob_search_neighbours(results, tree, node_index, glob, path);
             }
-            path.pop();
+            path.truncate(previous_len);
         }
     }
 }
 
 pub fn glob_search(tree: &Tree, root_index: TreeIndex, glob: &str) -> Result<Vec<TreeIndex>> {
-    let glob = Glob::new(glob)?.compile_matcher();
+    let glob = gix_glob::Pattern::from_bytes_without_negation(glob.as_bytes())
+        .with_context(|| anyhow!("Glob was empty or only whitespace"))?;
     let mut results = Vec::new();
-    let mut path = PathBuf::new();
+    let mut path = Default::default();
     glob_search_neighbours(&mut results, tree, root_index, &glob, &mut path);
     Ok(results)
 }
diff --git a/src/interactive/widgets/help.rs b/src/interactive/widgets/help.rs
index f2d3f53..0ec8b8c 100644
--- a/src/interactive/widgets/help.rs
+++ b/src/interactive/widgets/help.rs
@@ -161,7 +161,11 @@ impl HelpPane {
                 );
                 hotkey("<Space>", "Toggle the currently selected entry", None);
                 hotkey("a", "Toggle all entries", None);
-                hotkey("/", "Glob search", None);
+                hotkey(
+                    "/",
+                    "Git-style glob search, case-insensitive, always from the top of the tree",
+                    None,
+                );
                 spacer();
             }
             title("Keys in the Mark pane");
diff --git a/src/traverse.rs b/src/traverse.rs
index b2c8724..c6026b1 100644
--- a/src/traverse.rs
+++ b/src/traverse.rs
@@ -22,6 +22,7 @@ pub struct EntryData {
     pub entry_count: Option<u64>,
     /// If set, the item meta-data could not be obtained
     pub metadata_io_error: bool,
+    pub is_dir: bool,
 }
 
 impl Default for EntryData {
@@ -32,6 +33,7 @@ impl Default for EntryData {
             mtime: UNIX_EPOCH,
             entry_count: None,
             metadata_io_error: bool::default(),
+            is_dir: false,
         }
     }
 }
@@ -191,6 +193,7 @@ impl Traversal {
                                     }
                                 } else {
                                     data.entry_count = Some(0);
+                                    data.is_dir = true;
                                 }
 
                                 match m.modified() {