1 use { 2 super::*, 3 crate::{ 4 app::AppContext, 5 errors, 6 file_sum::FileSum, 7 git::TreeGitStatus, 8 task_sync::ComputationResult, 9 task_sync::Dam, 10 tree_build::{BId, TreeBuilder}, 11 }, 12 fnv::FnvHashMap, 13 std::{ 14 cmp::Ord, 15 mem, 16 path::{Path, PathBuf}, 17 }, 18 }; 19 20 /// The tree which may be displayed, with onle line per visible line of the panel. 21 /// 22 /// In the tree structure, every "node" is just a line, there's 23 /// no link from a child to its parent or from a parent to its children. 24 #[derive(Debug, Clone)] 25 pub struct Tree { 26 pub lines: Box<[TreeLine]>, 27 pub selection: usize, // there's always a selection (starts with root, which is 0) 28 pub options: TreeOptions, 29 pub scroll: usize, // the number of lines at the top hidden because of scrolling 30 pub nb_gitignored: u32, // number of times a gitignore pattern excluded a file 31 pub total_search: bool, // whether the search was made on all children 32 pub git_status: ComputationResult<TreeGitStatus>, 33 } 34 35 impl Tree { 36 37 /// rebuild the tree with the same root, height, and options refresh( &mut self, page_height: usize, con: &AppContext, ) -> Result<(), errors::TreeBuildError>38 pub fn refresh( 39 &mut self, 40 page_height: usize, 41 con: &AppContext, 42 ) -> Result<(), errors::TreeBuildError> { 43 let builder = TreeBuilder::from( 44 self.root().to_path_buf(), 45 self.options.clone(), 46 page_height, 47 con, 48 )?; 49 let mut tree = builder 50 .build( 51 false, // on refresh we always do a non total search 52 &Dam::unlimited(), 53 ) 54 .unwrap(); // should not fail 55 // we save the old selection to try restore it 56 let selected_path = self.selected_line().path.to_path_buf(); 57 mem::swap(&mut self.lines, &mut tree.lines); 58 self.scroll = 0; 59 if !self.try_select_path(&selected_path) { 60 if self.selection >= self.lines.len() { 61 self.selection = 0; 62 } 63 } 64 self.make_selection_visible(page_height); 65 Ok(()) 66 } 67 68 /// do what must be done after line additions or removals: 69 /// - sort the lines 70 /// - compute left branchs after_lines_changed(&mut self)71 pub fn after_lines_changed(&mut self) { 72 73 // we need to order the lines to build the tree. 74 // It's a little complicated because 75 // - we want a case insensitive sort 76 // - we still don't want to confuse the children of AA and Aa 77 // - a node can come from a not parent node, when we followed a link 78 let mut bid_parents: FnvHashMap<BId, BId> = FnvHashMap::default(); 79 let mut bid_lines: FnvHashMap<BId, &TreeLine> = FnvHashMap::default(); 80 for line in self.lines[..].iter() { 81 if let Some(parent_bid) = line.parent_bid { 82 bid_parents.insert(line.bid, parent_bid); 83 } 84 bid_lines.insert(line.bid, line); 85 } 86 let mut sort_paths: FnvHashMap<BId, String> = FnvHashMap::default(); 87 for line in self.lines[1..].iter() { 88 let mut sort_path = String::new(); 89 let mut bid = line.bid; 90 loop { 91 if let Some(l) = bid_lines.get(&bid) { 92 sort_path = format!( 93 "{}-{}/{}", 94 l.path.to_string_lossy().to_lowercase(), 95 bid.index(), // to be sure to separate paths having the same lowercase 96 sort_path, 97 ); 98 } else { 99 break; 100 } 101 if let Some(&parent_bid) = bid_parents.get(&bid) { 102 bid = parent_bid; 103 } else { 104 break; 105 } 106 } 107 sort_paths.insert(line.bid, sort_path); 108 } 109 self.lines[1..].sort_by_key(|line| sort_paths.get(&line.bid).unwrap()); 110 111 let mut best_index = 0; // index of the line with the best score 112 for i in 1..self.lines.len() { 113 if self.lines[i].score > self.lines[best_index].score { 114 best_index = i; 115 } 116 for d in 0..self.lines[i].left_branchs.len() { 117 self.lines[i].left_branchs[d] = false; 118 } 119 } 120 // then we discover the branches (for the drawing) 121 // and we mark the last children as pruning, if they have unlisted brothers 122 let mut last_parent_index: usize = self.lines.len() + 1; 123 for end_index in (1..self.lines.len()).rev() { 124 let depth = (self.lines[end_index].depth - 1) as usize; 125 let start_index = { 126 let parent_index = match self.lines[end_index].parent_bid { 127 Some(parent_bid) => { 128 let mut index = end_index; 129 loop { 130 index -= 1; 131 if self.lines[index].bid == parent_bid { 132 break; 133 } 134 if index == 0 { 135 break; 136 } 137 } 138 index 139 } 140 None => end_index, // Should not happen 141 }; 142 if parent_index != last_parent_index { 143 // the line at end_index is the last listed child of the line at parent_index 144 let unlisted = self.lines[parent_index].unlisted; 145 if unlisted > 0 && self.lines[end_index].nb_kept_children == 0 { 146 if best_index == end_index { 147 //debug!("Avoiding to prune the line with best score"); 148 } else { 149 //debug!("turning {:?} into Pruning", self.lines[end_index].path); 150 self.lines[end_index].line_type = TreeLineType::Pruning; 151 self.lines[end_index].unlisted = unlisted + 1; 152 self.lines[end_index].name = format!("{} unlisted", unlisted + 1); 153 self.lines[parent_index].unlisted = 0; 154 } 155 } 156 last_parent_index = parent_index; 157 } 158 parent_index + 1 159 }; 160 for i in start_index..=end_index { 161 self.lines[i].left_branchs[depth] = true; 162 } 163 } 164 if self.options.needs_sum() { 165 time!("fetch_file_sum", self.fetch_regular_file_sums()); // not the dirs, only simple files 166 self.sort_siblings(); // does nothing when sort mode is None 167 } 168 } 169 has_branch(&self, line_index: usize, depth: usize) -> bool170 pub fn has_branch(&self, line_index: usize, depth: usize) -> bool { 171 if line_index >= self.lines.len() { 172 return false; 173 } 174 let line = &self.lines[line_index]; 175 depth < usize::from(line.depth) && line.left_branchs[depth] 176 } 177 178 /// select another line 179 /// 180 /// For example the following one if dy is 1. move_selection(&mut self, dy: i32, page_height: usize, cycle: bool)181 pub fn move_selection(&mut self, dy: i32, page_height: usize, cycle: bool) { 182 let l = self.lines.len(); 183 // we find the new line to select 184 loop { 185 if dy < 0 { 186 let ady = (-dy) as usize; 187 if !cycle && self.selection < ady { 188 break; 189 } 190 self.selection = (self.selection + l - ady) % l; 191 } else { 192 let dy = dy as usize; 193 if !cycle && self.selection + dy > l { 194 break; 195 } 196 self.selection = (self.selection + dy) % l; 197 } 198 if self.lines[self.selection].is_selectable() { 199 break; 200 } 201 } 202 // we adjust the scroll 203 if l > page_height { 204 if self.selection < 3 { 205 self.scroll = 0; 206 } else if self.selection < self.scroll + 3 { 207 self.scroll = self.selection - 3; 208 } else if self.selection + 3 > l { 209 self.scroll = l - page_height; 210 } else if self.selection + 3 > self.scroll + page_height { 211 self.scroll = self.selection + 3 - page_height; 212 } 213 } 214 } 215 216 /// Scroll the desired amount and return true, or return false if it's 217 /// already at end or the tree fits the page try_scroll(&mut self, dy: i32, page_height: usize) -> bool218 pub fn try_scroll(&mut self, dy: i32, page_height: usize) -> bool { 219 if self.lines.len() <= page_height { 220 return false; 221 } 222 if dy < 0 { // scroll up 223 if self.scroll == 0 { 224 return false; 225 } else { 226 let ady = -dy as usize; 227 if ady < self.scroll { 228 self.scroll -= ady; 229 } else { 230 self.scroll = 0; 231 } 232 } 233 } else { // scroll down 234 let max = self.lines.len() - page_height; 235 if self.scroll >= max { 236 return false; 237 } 238 self.scroll = (self.scroll + dy as usize).min(max); 239 } 240 self.select_visible_line(page_height); 241 true 242 } 243 244 /// try to select a line by index of visible line 245 /// (works if y+scroll falls on a selectable line) try_select_y(&mut self, y: usize) -> bool246 pub fn try_select_y(&mut self, y: usize) -> bool { 247 let y = y + self.scroll; 248 if y < self.lines.len() { 249 if self.lines[y].is_selectable() { 250 self.selection = y; 251 return true; 252 } 253 } 254 false 255 } 256 /// fix the selection so that it's a selectable visible line select_visible_line(&mut self, page_height: usize)257 fn select_visible_line(&mut self, page_height: usize) { 258 if self.selection < self.scroll || self.selection >= self.scroll + page_height { 259 self.selection = self.scroll; 260 let l = self.lines.len(); 261 loop { 262 self.selection = (self.selection + l + 1) % l; 263 if self.lines[self.selection].is_selectable() { 264 break; 265 } 266 } 267 } 268 } 269 make_selection_visible(&mut self, page_height: usize)270 pub fn make_selection_visible(&mut self, page_height: usize) { 271 if page_height >= self.lines.len() || self.selection < 3 { 272 self.scroll = 0; 273 } else if self.selection <= self.scroll { 274 self.scroll = self.selection - 2; 275 } else if self.selection > self.lines.len() - 2 { 276 self.scroll = self.lines.len() - page_height; 277 } else if self.selection >= self.scroll + page_height { 278 self.scroll = self.selection + 2 - page_height; 279 } 280 } selected_line(&self) -> &TreeLine281 pub fn selected_line(&self) -> &TreeLine { 282 &self.lines[self.selection] 283 } root(&self) -> &PathBuf284 pub fn root(&self) -> &PathBuf { 285 &self.lines[0].path 286 } 287 /// select the line with the best matching score try_select_best_match(&mut self)288 pub fn try_select_best_match(&mut self) { 289 let mut best_score = 0; 290 for (idx, line) in self.lines.iter().enumerate() { 291 if !line.is_selectable() { 292 continue; 293 } 294 if best_score > line.score { 295 continue; 296 } 297 if line.score == best_score { 298 // in case of equal scores, we prefer the shortest path 299 if self.lines[idx].depth >= self.lines[self.selection].depth { 300 continue; 301 } 302 } 303 best_score = line.score; 304 self.selection = idx; 305 } 306 } 307 /// return true when we could select the given path try_select_path(&mut self, path: &Path) -> bool308 pub fn try_select_path(&mut self, path: &Path) -> bool { 309 for (idx, line) in self.lines.iter().enumerate() { 310 if !line.is_selectable() { 311 continue; 312 } 313 if path == line.path { 314 self.selection = idx; 315 return true; 316 } 317 } 318 false 319 } try_select_first(&mut self) -> bool320 pub fn try_select_first(&mut self) -> bool { 321 for idx in 0..self.lines.len() { 322 let line = &self.lines[idx]; 323 if line.is_selectable() { 324 self.selection = idx; 325 self.scroll = 0; 326 return true; 327 } 328 } 329 false 330 } try_select_last(&mut self, page_height: usize) -> bool331 pub fn try_select_last(&mut self, page_height: usize) -> bool { 332 for idx in (0..self.lines.len()).rev() { 333 let line = &self.lines[idx]; 334 if line.is_selectable() { 335 self.selection = idx; 336 self.make_selection_visible(page_height); 337 return true; 338 } 339 } 340 false 341 } try_select_previous_same_depth(&mut self, page_height: usize) -> bool342 pub fn try_select_previous_same_depth(&mut self, page_height: usize) -> bool { 343 let depth = self.lines[self.selection].depth; 344 for di in (0..self.lines.len()).rev() { 345 let idx = (self.selection + di) % self.lines.len(); 346 let line = &self.lines[idx]; 347 if !line.is_selectable() || line.depth != depth { 348 continue; 349 } 350 self.selection = idx; 351 self.make_selection_visible(page_height); 352 return true; 353 } 354 false 355 } try_select_next_same_depth(&mut self, page_height: usize) -> bool356 pub fn try_select_next_same_depth(&mut self, page_height: usize) -> bool { 357 let depth = self.lines[self.selection].depth; 358 for di in 0..self.lines.len() { 359 let idx = (self.selection + di + 1) % self.lines.len(); 360 let line = &self.lines[idx]; 361 if !line.is_selectable() || line.depth != depth { 362 continue; 363 } 364 self.selection = idx; 365 self.make_selection_visible(page_height); 366 return true; 367 } 368 false 369 } try_select_previous_match(&mut self, page_height: usize) -> bool370 pub fn try_select_previous_match(&mut self, page_height: usize) -> bool { 371 for di in (0..self.lines.len()).rev() { 372 let idx = (self.selection + di) % self.lines.len(); 373 let line = &self.lines[idx]; 374 if !line.is_selectable() { 375 continue; 376 } 377 if !line.direct_match { 378 continue; 379 } 380 if line.score > 0 { 381 self.selection = idx; 382 self.make_selection_visible(page_height); 383 return true; 384 } 385 } 386 false 387 } try_select_next_match(&mut self, page_height: usize) -> bool388 pub fn try_select_next_match(&mut self, page_height: usize) -> bool { 389 for di in 0..self.lines.len() { 390 let idx = (self.selection + di + 1) % self.lines.len(); 391 let line = &self.lines[idx]; 392 if !line.is_selectable() { 393 continue; 394 } 395 if !line.direct_match { 396 continue; 397 } 398 if line.score > 0 { 399 self.selection = idx; 400 self.make_selection_visible(page_height); 401 return true; 402 } 403 } 404 false 405 } 406 has_dir_missing_sum(&self) -> bool407 pub fn has_dir_missing_sum(&self) -> bool { 408 self.options.needs_sum() 409 && self 410 .lines 411 .iter() 412 .any(|line| line.line_type == TreeLineType::Dir && line.sum.is_none()) 413 } 414 is_missing_git_status_computation(&self) -> bool415 pub fn is_missing_git_status_computation(&self) -> bool { 416 self.git_status.is_not_computed() 417 } 418 419 /// fetch the file_sums of regular files (thus avoiding the 420 /// long computation which is needed for directories) fetch_regular_file_sums(&mut self)421 pub fn fetch_regular_file_sums(&mut self) { 422 for i in 1..self.lines.len() { 423 match self.lines[i].line_type { 424 TreeLineType::Dir | TreeLineType::Pruning => {} 425 _ => { 426 self.lines[i].sum = Some(FileSum::from_file(&self.lines[i].path)); 427 } 428 } 429 } 430 self.sort_siblings(); 431 } 432 433 /// compute the file_sum of one directory 434 /// 435 /// To compute the size of all of them, this should be called until 436 /// has_dir_missing_sum returns false fetch_some_missing_dir_sum(&mut self, dam: &Dam, con: &AppContext)437 pub fn fetch_some_missing_dir_sum(&mut self, dam: &Dam, con: &AppContext) { 438 // we prefer to compute the root directory last: its computation 439 // is faster when its first level children are already computed 440 for i in (0..self.lines.len()).rev() { 441 if self.lines[i].sum.is_none() && self.lines[i].line_type == TreeLineType::Dir { 442 self.lines[i].sum = FileSum::from_dir(&self.lines[i].path, dam, con); 443 self.sort_siblings(); 444 return; 445 } 446 } 447 } 448 449 /// Sort files according to the sort option 450 /// 451 /// (does nothing if it's None) sort_siblings(&mut self)452 fn sort_siblings(&mut self) { 453 if !self.options.sort.is_some() { 454 return; 455 } 456 match self.options.sort { 457 Sort::Count => { 458 // we'll try to keep the same path selected 459 let selected_path = self.selected_line().path.to_path_buf(); 460 self.lines[1..].sort_by(|a, b| { 461 let acount = a.sum.map_or(0, |s| s.to_count()); 462 let bcount = b.sum.map_or(0, |s| s.to_count()); 463 bcount.cmp(&acount) 464 }); 465 self.try_select_path(&selected_path); 466 } 467 Sort::Date => { 468 let selected_path = self.selected_line().path.to_path_buf(); 469 self.lines[1..].sort_by(|a, b| { 470 let adate = a.sum.map_or(0, |s| s.to_seconds()); 471 let bdate = b.sum.map_or(0, |s| s.to_seconds()); 472 bdate.cmp(&adate) 473 }); 474 self.try_select_path(&selected_path); 475 } 476 Sort::Size => { 477 let selected_path = self.selected_line().path.to_path_buf(); 478 self.lines[1..].sort_by(|a, b| { 479 let asize = a.sum.map_or(0, |s| s.to_size()); 480 let bsize = b.sum.map_or(0, |s| s.to_size()); 481 bsize.cmp(&asize) 482 }); 483 self.try_select_path(&selected_path); 484 } 485 Sort::None => {} 486 } 487 } 488 489 /// compute and return the size of the root total_sum(&self) -> FileSum490 pub fn total_sum(&self) -> FileSum { 491 if let Some(sum) = self.lines[0].sum { 492 // if the real total sum is computed, it's in the root line 493 sum 494 } else { 495 // if we don't have the sum in root, the nearest estimate is 496 // the sum of sums of lines at depth 1 497 let mut sum = FileSum::zero(); 498 for i in 1..self.lines.len() { 499 if self.lines[i].depth == 1 { 500 if let Some(line_sum) = self.lines[i].sum { 501 sum += line_sum; 502 } 503 } 504 } 505 sum 506 } 507 } 508 } 509 510