1 //! Tree structures, such as `├──` or `└──`, used in a tree view. 2 //! 3 //! ## Constructing Tree Views 4 //! 5 //! When using the `--tree` argument, instead of a vector of cells, each row 6 //! has a `depth` field that indicates how far deep in the tree it is: the top 7 //! level has depth 0, its children have depth 1, and *their* children have 8 //! depth 2, and so on. 9 //! 10 //! On top of this, it also has a `last` field that specifies whether this is 11 //! the last row of this particular consecutive set of rows. This doesn’t 12 //! affect the file’s information; it’s just used to display a different set of 13 //! Unicode tree characters! The resulting table looks like this: 14 //! 15 //! ```text 16 //! ┌───────┬───────┬───────────────────────┐ 17 //! │ Depth │ Last │ Output │ 18 //! ├───────┼───────┼───────────────────────┤ 19 //! │ 0 │ │ documents │ 20 //! │ 1 │ false │ ├── this_file.txt │ 21 //! │ 1 │ false │ ├── that_file.txt │ 22 //! │ 1 │ false │ ├── features │ 23 //! │ 2 │ false │ │ ├── feature_1.rs │ 24 //! │ 2 │ false │ │ ├── feature_2.rs │ 25 //! │ 2 │ true │ │ └── feature_3.rs │ 26 //! │ 1 │ true │ └── pictures │ 27 //! │ 2 │ false │ ├── garden.jpg │ 28 //! │ 2 │ false │ ├── flowers.jpg │ 29 //! │ 2 │ false │ ├── library.png │ 30 //! │ 2 │ true │ └── space.tiff │ 31 //! └───────┴───────┴───────────────────────┘ 32 //! ``` 33 //! 34 //! Creating the table like this means that each file has to be tested to see 35 //! if it’s the last one in the group. This is usually done by putting all the 36 //! files in a vector beforehand, getting its length, then comparing the index 37 //! of each file to see if it’s the last one. (As some files may not be 38 //! successfully `stat`ted, we don’t know how many files are going to exist in 39 //! each directory) 40 41 42 #[derive(PartialEq, Debug, Copy, Clone)] 43 pub enum TreePart { 44 45 /// Rightmost column, *not* the last in the directory. 46 Edge, 47 48 /// Not the rightmost column, and the directory has not finished yet. 49 Line, 50 51 /// Rightmost column, and the last in the directory. 52 Corner, 53 54 /// Not the rightmost column, and the directory *has* finished. 55 Blank, 56 } 57 58 impl TreePart { 59 60 /// Turn this tree part into ASCII-licious box drawing characters! 61 /// (Warning: not actually ASCII) ascii_art(self) -> &'static str62 pub fn ascii_art(self) -> &'static str { 63 match self { 64 Self::Edge => "├──", 65 Self::Line => "│ ", 66 Self::Corner => "└──", 67 Self::Blank => " ", 68 } 69 } 70 } 71 72 73 /// A **tree trunk** builds up arrays of tree parts over multiple depths. 74 #[derive(Debug, Default)] 75 pub struct TreeTrunk { 76 77 /// A stack tracks which tree characters should be printed. It’s 78 /// necessary to maintain information about the previously-printed 79 /// lines, as the output will change based on any previous entries. 80 stack: Vec<TreePart>, 81 82 /// A tuple for the last ‘depth’ and ‘last’ parameters that are passed in. 83 last_params: Option<TreeParams>, 84 } 85 86 #[derive(Debug, Copy, Clone)] 87 pub struct TreeParams { 88 89 /// How many directories deep into the tree structure this is. Directories 90 /// on top have depth 0. 91 depth: TreeDepth, 92 93 /// Whether this is the last entry in the directory. 94 last: bool, 95 } 96 97 #[derive(Debug, Copy, Clone)] 98 pub struct TreeDepth(pub usize); 99 100 impl TreeTrunk { 101 102 /// Calculates the tree parts for an entry at the given depth and 103 /// last-ness. The depth is used to determine where in the stack the tree 104 /// part should be inserted, and the last-ness is used to determine which 105 /// type of tree part to insert. 106 /// 107 /// This takes a `&mut self` because the results of each file are stored 108 /// and used in future rows. new_row(&mut self, params: TreeParams) -> &[TreePart]109 pub fn new_row(&mut self, params: TreeParams) -> &[TreePart] { 110 111 // If this isn’t our first iteration, then update the tree parts thus 112 // far to account for there being another row after it. 113 if let Some(last) = self.last_params { 114 self.stack[last.depth.0] = if last.last { TreePart::Blank } 115 else { TreePart::Line }; 116 } 117 118 // Make sure the stack has enough space, then add or modify another 119 // part into it. 120 self.stack.resize(params.depth.0 + 1, TreePart::Edge); 121 self.stack[params.depth.0] = if params.last { TreePart::Corner } 122 else { TreePart::Edge }; 123 124 self.last_params = Some(params); 125 126 // Return the tree parts as a slice of the stack. 127 // 128 // Ignore the first element here to prevent a ‘zeroth level’ from 129 // appearing before the very first directory. This level would 130 // join unrelated directories without connecting to anything: 131 // 132 // with [0..] with [1..] 133 // ========== ========== 134 // ├── folder folder 135 // │ └── file └── file 136 // └── folder folder 137 // └── file └──file 138 // 139 &self.stack[1..] 140 } 141 } 142 143 impl TreeParams { new(depth: TreeDepth, last: bool) -> Self144 pub fn new(depth: TreeDepth, last: bool) -> Self { 145 Self { depth, last } 146 } 147 is_at_root(&self) -> bool148 pub fn is_at_root(&self) -> bool { 149 self.depth.0 == 0 150 } 151 } 152 153 impl TreeDepth { root() -> Self154 pub fn root() -> Self { 155 Self(0) 156 } 157 deeper(self) -> Self158 pub fn deeper(self) -> Self { 159 Self(self.0 + 1) 160 } 161 162 /// Creates an iterator that, as well as yielding each value, yields a 163 /// `TreeParams` with the current depth and last flag filled in. iterate_over<I, T>(self, inner: I) -> Iter<I> where I: ExactSizeIterator + Iterator<Item = T>164 pub fn iterate_over<I, T>(self, inner: I) -> Iter<I> 165 where I: ExactSizeIterator + Iterator<Item = T> 166 { 167 Iter { current_depth: self, inner } 168 } 169 } 170 171 172 pub struct Iter<I> { 173 current_depth: TreeDepth, 174 inner: I, 175 } 176 177 impl<I, T> Iterator for Iter<I> 178 where I: ExactSizeIterator + Iterator<Item = T> 179 { 180 type Item = (TreeParams, T); 181 next(&mut self) -> Option<Self::Item>182 fn next(&mut self) -> Option<Self::Item> { 183 let t = self.inner.next()?; 184 185 // TODO: use exact_size_is_empty API soon 186 let params = TreeParams::new(self.current_depth, self.inner.len() == 0); 187 Some((params, t)) 188 } 189 } 190 191 192 #[cfg(test)] 193 mod trunk_test { 194 use super::*; 195 params(depth: usize, last: bool) -> TreeParams196 fn params(depth: usize, last: bool) -> TreeParams { 197 TreeParams::new(TreeDepth(depth), last) 198 } 199 200 #[test] empty_at_first()201 fn empty_at_first() { 202 let mut tt = TreeTrunk::default(); 203 assert_eq!(tt.new_row(params(0, true)), &[ ]); 204 } 205 206 #[test] one_child()207 fn one_child() { 208 let mut tt = TreeTrunk::default(); 209 assert_eq!(tt.new_row(params(0, true)), &[ ]); 210 assert_eq!(tt.new_row(params(1, true)), &[ TreePart::Corner ]); 211 } 212 213 #[test] two_children()214 fn two_children() { 215 let mut tt = TreeTrunk::default(); 216 assert_eq!(tt.new_row(params(0, true)), &[ ]); 217 assert_eq!(tt.new_row(params(1, false)), &[ TreePart::Edge ]); 218 assert_eq!(tt.new_row(params(1, true)), &[ TreePart::Corner ]); 219 } 220 221 #[test] two_times_two_children()222 fn two_times_two_children() { 223 let mut tt = TreeTrunk::default(); 224 assert_eq!(tt.new_row(params(0, false)), &[ ]); 225 assert_eq!(tt.new_row(params(1, false)), &[ TreePart::Edge ]); 226 assert_eq!(tt.new_row(params(1, true)), &[ TreePart::Corner ]); 227 228 assert_eq!(tt.new_row(params(0, true)), &[ ]); 229 assert_eq!(tt.new_row(params(1, false)), &[ TreePart::Edge ]); 230 assert_eq!(tt.new_row(params(1, true)), &[ TreePart::Corner ]); 231 } 232 233 #[test] two_times_two_nested_children()234 fn two_times_two_nested_children() { 235 let mut tt = TreeTrunk::default(); 236 assert_eq!(tt.new_row(params(0, true)), &[ ]); 237 238 assert_eq!(tt.new_row(params(1, false)), &[ TreePart::Edge ]); 239 assert_eq!(tt.new_row(params(2, false)), &[ TreePart::Line, TreePart::Edge ]); 240 assert_eq!(tt.new_row(params(2, true)), &[ TreePart::Line, TreePart::Corner ]); 241 242 assert_eq!(tt.new_row(params(1, true)), &[ TreePart::Corner ]); 243 assert_eq!(tt.new_row(params(2, false)), &[ TreePart::Blank, TreePart::Edge ]); 244 assert_eq!(tt.new_row(params(2, true)), &[ TreePart::Blank, TreePart::Corner ]); 245 } 246 } 247 248 249 #[cfg(test)] 250 mod iter_test { 251 use super::*; 252 253 #[test] test_iteration()254 fn test_iteration() { 255 let foos = &[ "first", "middle", "last" ]; 256 let mut iter = TreeDepth::root().iterate_over(foos.into_iter()); 257 258 let next = iter.next().unwrap(); 259 assert_eq!(&"first", next.1); 260 assert_eq!(false, next.0.last); 261 262 let next = iter.next().unwrap(); 263 assert_eq!(&"middle", next.1); 264 assert_eq!(false, next.0.last); 265 266 let next = iter.next().unwrap(); 267 assert_eq!(&"last", next.1); 268 assert_eq!(true, next.0.last); 269 270 assert!(iter.next().is_none()); 271 } 272 273 #[test] test_empty()274 fn test_empty() { 275 let nothing: &[usize] = &[]; 276 let mut iter = TreeDepth::root().iterate_over(nothing.into_iter()); 277 assert!(iter.next().is_none()); 278 } 279 } 280