diff options
Diffstat (limited to 'filetreelist')
-rw-r--r-- | filetreelist/Cargo.toml | 18 | ||||
l--------- | filetreelist/LICENSE.md | 1 | ||||
-rw-r--r-- | filetreelist/src/error.rs | 16 | ||||
-rw-r--r-- | filetreelist/src/filetree.rs | 495 | ||||
-rw-r--r-- | filetreelist/src/filetreeitems.rs | 816 | ||||
-rw-r--r-- | filetreelist/src/item.rs | 207 | ||||
-rw-r--r-- | filetreelist/src/lib.rs | 33 | ||||
-rw-r--r-- | filetreelist/src/tree_iter.rs | 33 | ||||
-rw-r--r-- | filetreelist/src/treeitems_iter.rs | 60 |
9 files changed, 1679 insertions, 0 deletions
diff --git a/filetreelist/Cargo.toml b/filetreelist/Cargo.toml new file mode 100644 index 00000000..6d5037a6 --- /dev/null +++ b/filetreelist/Cargo.toml @@ -0,0 +1,18 @@ +[package] +name = "filetreelist" +version = "0.1.0" +authors = ["Stephan Dilly <dilly.stephan@gmail.com>"] +edition = "2018" +description = "filetree abstraction based on a sorted path list, supports key based navigation events, folding, scrolling and more" +homepage = "https://github.com/extrawurst/gitui" +repository = "https://github.com/extrawurst/gitui" +readme = "README.md" +license-file = "LICENSE.md" +categories = ["command-line-utilities"] +keywords = ["gui","cli","terminal","ui","tui"] + +[dependencies] +thiserror = "1.0" + +[dev-dependencies] +pretty_assertions = "0.7"
\ No newline at end of file diff --git a/filetreelist/LICENSE.md b/filetreelist/LICENSE.md new file mode 120000 index 00000000..7eabdb1c --- /dev/null +++ b/filetreelist/LICENSE.md @@ -0,0 +1 @@ +../LICENSE.md
\ No newline at end of file diff --git a/filetreelist/src/error.rs b/filetreelist/src/error.rs new file mode 100644 index 00000000..a68fcaf3 --- /dev/null +++ b/filetreelist/src/error.rs @@ -0,0 +1,16 @@ +use std::{num::TryFromIntError, path::PathBuf}; +use thiserror::Error; + +#[derive(Error, Debug)] +pub enum Error { + #[error("InvalidPath: `{0}`")] + InvalidPath(PathBuf), + + #[error("InvalidFilePath: `{0}`")] + InvalidFilePath(String), + + #[error("TryFromInt error:{0}")] + IntConversion(#[from] TryFromIntError), +} + +pub type Result<T> = std::result::Result<T, Error>; diff --git a/filetreelist/src/filetree.rs b/filetreelist/src/filetree.rs new file mode 100644 index 00000000..26c7a5af --- /dev/null +++ b/filetreelist/src/filetree.rs @@ -0,0 +1,495 @@ +use crate::{ + error::Result, filetreeitems::FileTreeItems, + tree_iter::TreeIterator, TreeItemInfo, +}; +use std::{collections::BTreeSet, usize}; + +/// +#[derive(Copy, Clone, Debug)] +pub enum MoveSelection { + Up, + Down, + Left, + Right, + Top, + End, + PageDown, + PageUp, +} + +#[derive(Debug, Clone, Copy)] +pub struct VisualSelection { + pub count: usize, + pub index: usize, +} + +/// wraps `FileTreeItems` as a datastore and adds selection functionality +#[derive(Default)] +pub struct FileTree { + items: FileTreeItems, + selection: Option<usize>, + // caches the absolute selection translated to visual index + visual_selection: Option<VisualSelection>, +} + +impl FileTree { + /// + pub fn new( + list: &[&str], + collapsed: &BTreeSet<&String>, + ) -> Result<Self> { + let mut new_self = Self { + items: FileTreeItems::new(list, collapsed)?, + selection: if list.is_empty() { None } else { Some(0) }, + visual_selection: None, + }; + new_self.visual_selection = new_self.calc_visual_selection(); + + Ok(new_self) + } + + /// + pub const fn is_empty(&self) -> bool { + self.items.file_count() == 0 + } + + /// + pub fn collapse_but_root(&mut self) { + self.items.collapse(0, true); + self.items.expand(0, false); + } + + /// iterates visible elements starting from `start_index_visual` + pub fn iterate( + &self, + start_index_visual: usize, + max_amount: usize, + ) -> TreeIterator<'_> { + let start = self + .visual_index_to_absolute(start_index_visual) + .unwrap_or_default(); + TreeIterator::new( + self.items.iterate(start, max_amount), + self.selection, + ) + } + + /// + pub const fn visual_selection(&self) -> Option<&VisualSelection> { + self.visual_selection.as_ref() + } + + /// + pub fn selected_file(&self) -> Option<&TreeItemInfo> { + self.selection.and_then(|index| { + let item = &self.items.tree_items[index]; + if item.kind().is_path() { + None + } else { + Some(item.info()) + } + }) + } + + /// + pub fn collapse_recursive(&mut self) { + if let Some(selection) = self.selection { + self.items.collapse(selection, true); + } + } + + /// + pub fn expand_recursive(&mut self) { + if let Some(selection) = self.selection { + self.items.expand(selection, true); + } + } + + /// + pub fn move_selection(&mut self, dir: MoveSelection) -> bool { + self.selection.map_or(false, |selection| { + let new_index = match dir { + MoveSelection::Up => { + self.selection_updown(selection, true) + } + MoveSelection::Down => { + self.selection_updown(selection, false) + } + MoveSelection::Left => self.selection_left(selection), + MoveSelection::Right => { + self.selection_right(selection) + } + MoveSelection::Top => { + Self::selection_start(selection) + } + MoveSelection::End => self.selection_end(selection), + MoveSelection::PageDown | MoveSelection::PageUp => { + None + } + }; + + let changed_index = + new_index.map(|i| i != selection).unwrap_or_default(); + + if changed_index { + self.selection = new_index; + self.visual_selection = self.calc_visual_selection(); + } + + changed_index || new_index.is_some() + }) + } + + fn visual_index_to_absolute( + &self, + visual_index: usize, + ) -> Option<usize> { + self.items + .iterate(0, self.items.len()) + .enumerate() + .find_map(|(i, (abs, _))| { + if i == visual_index { + Some(abs) + } else { + None + } + }) + } + + fn calc_visual_selection(&self) -> Option<VisualSelection> { + self.selection.map(|selection_absolute| { + let mut count = 0; + let mut visual_index = 0; + for (index, _item) in + self.items.iterate(0, self.items.len()) + { + if selection_absolute == index { + visual_index = count; + } + + count += 1; + } + + VisualSelection { + index: visual_index, + count, + } + }) + } + + const fn selection_start(current_index: usize) -> Option<usize> { + if current_index == 0 { + None + } else { + Some(0) + } + } + + fn selection_end(&self, current_index: usize) -> Option<usize> { + let items_max = self.items.len().saturating_sub(1); + + let mut new_index = items_max; + + loop { + if self.is_visible_index(new_index) { + break; + } + + if new_index == 0 { + break; + } + + new_index = new_index.saturating_sub(1); + new_index = std::cmp::min(new_index, items_max); + } + + if new_index == current_index { + None + } else { + Some(new_index) + } + } + + fn selection_updown( + &self, + current_index: usize, + up: bool, + ) -> Option<usize> { + let mut index = current_index; + + loop { + index = { + let new_index = if up { + index.saturating_sub(1) + } else { + index.saturating_add(1) + }; + + // when reaching usize bounds + if new_index == index { + break; + } + + if new_index >= self.items.len() { + break; + } + + new_index + }; + + if self.is_visible_index(index) { + break; + } + } + + if index == current_index { + None + } else { + Some(index) + } + } + + fn select_parent( + &mut self, + current_index: usize, + ) -> Option<usize> { + let indent = + self.items.tree_items[current_index].info().indent(); + + let mut index = current_index; + + while let Some(selection) = self.selection_updown(index, true) + { + index = selection; + + if self.items.tree_items[index].info().indent() < indent { + break; + } + } + + if index == current_index { + None + } else { + Some(index) + } + } + + fn selection_left( + &mut self, + current_index: usize, + ) -> Option<usize> { + let item = &mut self.items.tree_items[current_index]; + + if item.kind().is_path() && !item.kind().is_path_collapsed() { + self.items.collapse(current_index, false); + return Some(current_index); + } + + self.select_parent(current_index) + } + + fn selection_right( + &mut self, + current_selection: usize, + ) -> Option<usize> { + let item = &mut self.items.tree_items[current_selection]; + + if item.kind().is_path() { + if item.kind().is_path_collapsed() { + self.items.expand(current_selection, false); + return Some(current_selection); + } + return self.selection_updown(current_selection, false); + } + + None + } + + fn is_visible_index(&self, index: usize) -> bool { + self.items + .tree_items + .get(index) + .map(|item| item.info().is_visible()) + .unwrap_or_default() + } +} + +#[cfg(test)] +mod test { + use crate::{FileTree, MoveSelection}; + use pretty_assertions::assert_eq; + use std::collections::BTreeSet; + + #[test] + fn test_selection() { + let items = vec![ + "a/b", // + ]; + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + assert!(tree.move_selection(MoveSelection::Down)); + + assert_eq!(tree.selection, Some(1)); + + assert!(!tree.move_selection(MoveSelection::Down)); + + assert_eq!(tree.selection, Some(1)); + } + + #[test] + fn test_selection_skips_collapsed() { + let items = vec![ + "a/b/c", // + "a/d", // + ]; + + //0 a/ + //1 b/ + //2 c + //3 d + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + tree.items.collapse(1, false); + tree.selection = Some(1); + + assert!(tree.move_selection(MoveSelection::Down)); + + assert_eq!(tree.selection, Some(3)); + } + + #[test] + fn test_selection_left_collapse() { + let items = vec![ + "a/b/c", // + "a/d", // + ]; + + //0 a/ + //1 b/ + //2 c + //3 d + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + tree.selection = Some(1); + + //collapses 1 + assert!(tree.move_selection(MoveSelection::Left)); + // index will not change + assert_eq!(tree.selection, Some(1)); + + assert!(tree.items.tree_items[1].kind().is_path_collapsed()); + assert!(!tree.items.tree_items[2].info().is_visible()); + } + + #[test] + fn test_selection_left_parent() { + let items = vec![ + "a/b/c", // + "a/d", // + ]; + + //0 a/ + //1 b/ + //2 c + //3 d + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + tree.selection = Some(2); + + assert!(tree.move_selection(MoveSelection::Left)); + assert_eq!(tree.selection, Some(1)); + + assert!(tree.move_selection(MoveSelection::Left)); + assert_eq!(tree.selection, Some(1)); + + assert!(tree.move_selection(MoveSelection::Left)); + assert_eq!(tree.selection, Some(0)); + } + + #[test] + fn test_selection_right_expand() { + let items = vec![ + "a/b/c", // + "a/d", // + ]; + + //0 a/ + //1 b/ + //2 c + //3 d + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + tree.items.collapse(1, false); + tree.items.collapse(0, false); + tree.selection = Some(0); + + assert!(tree.move_selection(MoveSelection::Right)); + assert_eq!(tree.selection, Some(0)); + assert!(!tree.items.tree_items[0].kind().is_path_collapsed()); + + assert!(tree.move_selection(MoveSelection::Right)); + assert_eq!(tree.selection, Some(1)); + assert!(tree.items.tree_items[1].kind().is_path_collapsed()); + + assert!(tree.move_selection(MoveSelection::Right)); + assert_eq!(tree.selection, Some(1)); + assert!(!tree.items.tree_items[1].kind().is_path_collapsed()); + } + + #[test] + fn test_selection_top() { + let items = vec![ + "a/b/c", // + "a/d", // + ]; + + //0 a/ + //1 b/ + //2 c + //3 d + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + tree.selection = Some(3); + + assert!(tree.move_selection(MoveSelection::Top)); + assert_eq!(tree.selection, Some(0)); + } + + #[test] + fn test_visible_selection() { + let items = vec![ + "a/b/c", // + "a/b/c2", // + "a/d", // + ]; + + //0 a/ + //1 b/ + //2 c + //3 c2 + //4 d + + let mut tree = + FileTree::new(&items, &BTreeSet::new()).unwrap(); + + tree.selection = Some(1); + assert!(tree.move_selection(MoveSelection::Left)); + assert!(tree.move_selection(MoveSelection::Down)); + let s = tree.visual_selection().unwrap(); + + assert_eq!(s.count, 3); + assert_eq!(s.index, 2); + } +} diff --git a/filetreelist/src/filetreeitems.rs b/filetreelist/src/filetreeitems.rs new file mode 100644 index 00000000..d966afef --- /dev/null +++ b/filetreelist/src/filetreeitems.rs @@ -0,0 +1,816 @@ +use crate::{ + error::Error, + item::{FileTreeItemKind, PathCollapsed}, + FileTreeItem, +}; +use crate::{error::Result, treeitems_iter::TreeItemsIterator}; +use std::{ + collections::{BTreeMap, BTreeSet}, + path::Path, + usize, +}; + +/// +#[derive(Default)] +pub struct FileTreeItems { + pub tree_items: Vec<FileTreeItem>, + files: usize, +} + +impl FileTreeItems { + /// + pub fn new( + list: &[&str], + collapsed: &BTreeSet<&String>, + ) -> Result<Self> { + let (mut items, paths) = Self::create_items(list, collapsed)?; + + Self::fold_paths(&mut items, &paths); + + Ok(Self { + tree_items: items, + files: list.len(), + }) + } + + fn create_items<'a>( + list: &'a [&str], + collapsed: &BTreeSet<&String>, + ) -> Result<(Vec<FileTreeItem>, BTreeMap<&'a Path, usize>)> { + let mut items = Vec::with_capacity(list.len()); + let mut paths_added: BTreeMap<&Path, usize> = BTreeMap::new(); + + for e in list { + { + let item_path = Path::new(e); + Self::push_dirs( + item_path, + &mut items, + &mut paths_added, + collapsed, + )?; + } + + items.push(FileTreeItem::new_file(e)?); + } + + Ok((items, paths_added)) + } + + /// how many individual items (files/paths) are in the list + pub fn len(&self) -> usize { + self.tree_items.len() + } + + /// how many files were added to this list + pub const fn file_count(&self) -> usize { + self.files + } + + /// iterates visible elements + pub const fn iterate( + &self, + start: usize, + max_amount: usize, + ) -> TreeItemsIterator<'_> { + TreeItemsIterator::new(self, start, max_amount) + } + + fn push_dirs<'a>( + item_path: &'a Path, + nodes: &mut Vec<FileTreeItem>, + // helps to only add new nodes for paths that were not added before + // we also count the number of children a node has for later folding + paths_added: &mut BTreeMap<&'a Path, usize>, + collapsed: &BTreeSet<&String>, + ) -> Result<()> { + let mut ancestors = + item_path.ancestors().skip(1).collect::<Vec<_>>(); + ancestors.reverse(); + + for c in &ancestors { + if c.parent().is_some() && !paths_added.contains_key(c) { + // add node and set count to have no children + paths_added.entry(c).or_insert(0); + + // increase the number of children in the parent node count + if let Some(parent) = c.parent() { + if !parent.as_os_str().is_empty() { + *paths_added.entry(parent).or_insert(0) += 1; + } + } + + let path_string = Self::path_to_string(c)?; + let is_collapsed = collapsed.contains(&path_string); + nodes.push(FileTreeItem::new_path( + c, + path_string, + is_collapsed, + )?); + } + } + + // increase child count in parent node (the above ancenstor ignores the leaf component) + if let Some(parent) = item_path.parent() { + *paths_added.entry(parent).or_insert(0) += 1; + } + + Ok(()) + } + + fn path_to_string(p: &Path) -> Result<String> { + Ok(p.to_str() + .map_or_else( + || Err(Error::InvalidPath(p.to_path_buf())), + Ok, + )? + .to_string()) + } + + pub fn collapse(&mut self, index: usize, recursive: bool) { + if self.tree_items[index].kind().is_path() { + self.tree_items[index].collapse_path(); + + let path = format!( + "{}/", + self.tree_items[index].info().full_path() + ); + + for i in index + 1..self.tree_items.len() { + let item = &mut self.tree_items[i]; + + if recursive && item.kind().is_path() { + item.collapse_path(); + } + + let item_path = &item.info().full_path(); + + if item_path.starts_with(&path) { + item.hide(); + } else { + return; + } + } + } + } + + pub fn expand(&mut self, index: usize, recursive: bool) { + if self.tree_items[index].kind().is_path() { + self.tree_items[index].expand_path(); + + let full_path = format!( + "{}/", + self.tree_items[index].info().full_path() + ); + + if recursive { + for i in index + 1..self.tree_items.len() { + let item = &mut self.tree_items[i]; + + if !item + .info() + .full_path() + .starts_with(&full_path) + { + break; + } + + if item.kind().is_path() + && item.kind().is_path_collapsed() + { + item.expand_path(); + } + } + } + + self.update_visibility( + Some(full_path.as_str()), + index + 1, + false, + ); + } + } + + fn update_visibility( + &mut self, + prefix: Option<&str>, + start_idx: usize, + set_defaults: bool, + ) { + // if we are in any subpath that is collapsed we keep skipping over it + let mut inner_collapsed: Option<String> = None; + + for i in start_idx..self.tree_items.len() { + if let Some(ref collapsed_path) = inner_collapsed { + let p = self.tree_items[i].info().full_path(); + if p.starts_with(collapsed_path) { + if set_defaults { + self.tree_items[i] + .info_mut() + .set_visible(false); + } + // we are still in a collapsed inner path + continue; + } + inner_collapsed = None; + } + + let item_kind = self.tree_items[i].kind().clone(); + let item_path = self.tree_items[i].info().full_path(); + + if matches!(item_kind, FileTreeItemKind::Path(PathCollapsed(collapsed)) if collapsed) + { + // we encountered an inner path that is still collapsed + inner_collapsed = Some(format!("{}/", &item_path)); + } + + if prefix + .map_or(true, |prefix| item_path.starts_with(prefix)) + { + self.tree_items[i].info_mut().set_visible(true); + } else { + // if we do not set defaults we can early out + if set_defaults { + self.tree_items[i].info_mut().set_visible(false); + } else { + return; + } + } + } + } + + fn fold_paths( + items: &mut Vec<FileTreeItem>, + paths: &BTreeMap<&Path, usize>, + ) { + let mut i = 0; + + while i < items.len() { + let item = &items[i]; + if item.kind().is_path() { + let children = + paths.get(&Path::new(item.info().full_path())); + + if let Some(children) = children { + if *children == 1 { + if i + 1 >= items.len() { + return; + } + + if items + .get(i + 1) + .map(|item| item.kind().is_path()) + .unwrap_or_default() + { + let next_item = items.remove(i + 1); + let item_mut = &mut items[i]; + item_mut.fold(next_item); + + let prefix = item_mut + .info() + .full_path() + .to_owned(); + + Self::unindent(items, &prefix, i + 1); + continue; + } + } + } + } + + i += 1; + } + } + + fn unindent( + items: &mut Vec<FileTreeItem>, + prefix: &str, + start: usize, + ) { + for elem in items.iter_mut().skip(start) { + if elem.info().full_path().starts_with(prefix) { + elem.info_mut().unindent(); + } else { + return; + } + } + } +} + +#[cfg(test)] +mod tests { + use super::*; + use pretty_assertions::assert_eq; + + #[test] + fn test_simple() { + let items = vec![ + "file.txt", // + ]; + + let res = + FileTreeItems::new(&items, &BTreeSet::new()).unwrap(); + + assert!(res.tree_items[0].info().is_visible()); + assert_eq!(res.tree_items[0].info().indent(), 0); + assert_eq!(res.tree_items[0].info().path(), items[0]); + assert_eq!(res.tree_items[0].info().full_path(), items[0]); + + let items = vec![ + "file.txt", // + "file2.txt", // + ]; + + let res = + FileTreeItems::new(&items, &BTreeSet::new()).unwrap(); + + assert_eq!(res.tree_items.len(), 2); + assert_eq!(res.tree_items.len(), res.len()); + assert_eq!( + res.tree_items[1].info().path(), + items[1].to_string() + ); + } + + #[test] + fn test_push_path() { + let mut items = Vec::new(); + let mut paths: BTreeMap<&Path, usize> = BTreeMap::new(); + + FileTreeItems::push_dirs( + Path::new("a/b/c"), + &mut items, + &mut paths, + &BTreeSet::new(), + ) + .unwrap(); + + assert_eq!(*paths.get(&Path::new("a")).unwrap(), 1); + + FileTreeItems::push_dirs( + Path::new("a/b2/c"), + &mut items, + &mut paths, + &BTreeSet::new(), + ) + .unwrap(); + + assert_eq!(*paths.get(&Path::new("a")).unwrap(), 2); + } + + #[test] + fn test_push_path2() { + let mut items = Vec::new(); + let mut paths: BTreeMap<&Path, usize> = BTreeMap::new(); + + FileTreeItems::push_dirs( + Path::new("a/b/c"), + &mut items, + &mut paths, + &BTreeSet::new(), + ) + .unwrap(); + + assert_eq!(*paths.get(&Path::new("a")).unwrap(), 1); + assert_eq!(*paths.get(&Path::new("a/b")).unwrap(), 1); + + FileTreeItems::push_dirs( + Path::new("a/b/d"), + &mut items, + &mut paths, + &BTreeSet::new(), + ) + .unwrap(); + + assert_eq!(*paths.get(&Path::new("a")).unwrap(), 1); + assert_eq!(*paths.get(&Path::new("a/b")).unwrap(), 2); + } + + #[test] + fn test_folder() { + let items = vec![ + "a/file.txt", // + ]; + + let res = FileTreeItems::new(&items, &BTreeSet::new()) + .unwrap() + .tree_items + .iter() + .map(|i| i.info().full_path().to_string()) + .collect::<Vec<_>>(); + + assert_eq!( + res, + vec![String::from("a"), String::from("a/file.txt"),] + ); + } + + #[test] + fn test_indent() { + let items = vec![ + "a/b/file.txt", // + ]; + + let list = + FileTreeItems::new(&items, &BTreeSet::new()).unwrap(); + let mut res = list + .tree_items + .iter() + .map(|i| (i.info().indent(), i.info().path())); + + assert_eq!(res.next(), Some((0, "a/b"))); + assert_eq!(res.next(), Some((1, "file.txt"))); + } + + #[test] + fn test_indent_folder_file_name() { + let items = vec![ + "a/b", // + "a.txt", // + ]; + + let list = + FileTreeItems::new(&items, &BTreeSet::new()).unwrap(); + let mut res = list + .tree_items + .iter() + .map(|i| (i.info().indent(), i.info().path())); + + assert_eq!(res.next(), Some((0, "a"))); + assert_eq!(res.next(), Some((1, "b"))); + assert_eq!(res.next(), Some((0, "a.txt"))); + } + + #[test] + fn test_folder_dup() { + let items = vec![ + "a/file.txt", // + "a/file2.txt", // + ]; + + let tree = + FileTreeItems::new(&items, &BTreeSet::new()).unwrap(); + + assert_eq!(tree.file_count(), 2); + assert_eq!(tree.len(), 3); + + let res = tree + .tree_items + .iter() + .map(|i| i.info().full_path().to_string()) + .collect::<Vec<_>>(); + + assert_eq!( + res, + vec![ + String::from("a"), + String::from("a/file.txt"), + String::from("a/file2.txt"), + ] + ); + } + + #[test] + fn test_collapse() { + let items = vec![ + "a/file1.txt", // + "b/file2.txt", // + ]; + + let mut tree = + FileTreeItems::new(&items, &BTreeSet::new()).unwrap(); + + assert!(tree.tree_items[1].info().is_visible()); + + tree.collapse(0, false); + + assert!(!tree.tree_items[1].info().is_visible()); + } + + #[test] + fn test_iterate_collapsed() { + let items = vec![ + "a/file1.txt", // + "b/file2.txt", // + ]; + + |