path: root/src/tree_build/builder.rs

use {
    crate::{
        errors::TreeBuildError,
        flat_tree::{Tree, TreeLine},
        task_sync::TaskLifetime,
        tree_options::{TreeOptions},
    },
    id_arena::Arena,
    std::{
        collections::{BinaryHeap, VecDeque},
        fs,
        path::PathBuf,
        result::Result,
        time::{Duration, Instant},
    },
    super::{
        bline::BLine,
        bid::{BId, SortableBId},
    },
};

/// If a search found enough results to fill the screen but didn't scan
/// everything, we search a little more in case we find better matches
/// but not after the NOT_LONG duration.
static NOT_LONG: Duration = Duration::from_millis(900);

/// the result of trying to build a bline
enum BLineResult {
    Some(BId), // the only positive result
    FilteredOutAsHidden,
    FilteredOutByPattern,
    FilteredOutAsNonFolder,
    GitIgnored,
    Invalid,
}

/// The TreeBuilder builds a Tree according to options (including an optional search pattern)
/// Instead of the final TreeLine, the builder uses an internal structure: BLine.
/// All BLines used during build are stored in the blines vector and kept until the end.
/// Most operations and temporary data structures just deal with the indexes of lines in
///  the blines vector.
pub struct TreeBuilder {
    options: TreeOptions,
    targeted_size: usize, // the number of lines we should fill (height of the screen)
    nb_gitignored: u32,   // number of times a gitignore pattern excluded a file
    blines: Arena<BLine>,
    root_id: BId,
    total_search: bool,
}
impl TreeBuilder {
    pub fn from(
        path: PathBuf,
        options: TreeOptions,
        targeted_size: usize,
    ) -> Result<TreeBuilder, TreeBuildError> {
        let mut blines = Arena::new();
        let root_id = BLine::from_root(&mut blines, path, options.respect_git_ignore)?;
        Ok(TreeBuilder {
            options,
            targeted_size,
            nb_gitignored: 0,
            blines,
            root_id,
            total_search: true, // we'll set it to false if we don't look at all children
        })
    }
    /// return a bline if the direntry directly matches the options and there's no error
    fn make_line(&mut self, parent_id: BId, e: fs::DirEntry, depth: u16) -> BLineResult {
        let name = e.file_name();
        let name = match name.to_str() {
            Some(name) => name,
            None => {
                return BLineResult::Invalid;
            }
        };
        if !self.options.show_hidden && name.starts_with('.') {
            return BLineResult::FilteredOutAsHidden;
        }
        let mut has_match = true;
        let mut score = 10000 - i32::from(depth); // we dope less deep entries
        if self.options.pattern.is_some() {
            if let Some(pattern_score) = self.options.pattern.score_of(&name) {
                score += pattern_score;
            } else {
                has_match = false;
            }
        }
        let file_type = match e.file_type() {
            Ok(ft) => ft,
            Err(_) => {
                return BLineResult::Invalid;
            }
        };
        if file_type.is_file() || file_type.is_symlink() {
            if !has_match {
                return BLineResult::FilteredOutByPattern;
            }
            if self.options.only_folders {
                return BLineResult::FilteredOutAsNonFolder;
            }
        }
        let path = e.path();
        let mut ignore_filter = None;
        if let Some(gif) = &self.blines[parent_id].ignore_filter {
            if !gif.accepts(&path, &name, file_type.is_dir()) {
                return BLineResult::GitIgnored;
            }
            if file_type.is_dir() {
                ignore_filter = Some(gif.extended_to(&path));
            }
        }
        BLineResult::Some(self.blines.alloc(BLine {
            parent_id: Some(parent_id),
            path,
            depth,
            name: name.to_string(),
            file_type,
            children: None,
            next_child_idx: 0,
            has_error: false,
            has_match,
            score,
            ignore_filter,
            nb_kept_children: 0,
        }))
    }

    /// returns true when there are direct matches among children
    fn load_children(&mut self, bid: BId) -> bool {
        let mut has_child_match = false;
        match fs::read_dir(&self.blines[bid].path) {
            Ok(entries) => {
                let mut children: Vec<BId> = Vec::new();
                let child_depth = self.blines[bid].depth + 1;
                for e in entries {
                    if let Ok(e) = e {
                        let bl = self.make_line(bid, e, child_depth);
                        match bl {
                            BLineResult::Some(child_id) => {
                                if self.blines[child_id].has_match {
                                    // direct match
                                    self.blines[bid].has_match = true;
                                    has_child_match = true;
                                }
                                children.push(child_id);
                            }
                            BLineResult::GitIgnored => {
                                self.nb_gitignored += 1;
                            }
                            _ => {
                                // other reason, we don't care
                            }
                        }
                    }
                }
                children.sort_by(|&a, &b| {
                    self.blines[a]
                        .name
                        .to_lowercase()
                        .cmp(&self.blines[b].name.to_lowercase())
                });
                self.blines[bid].children = Some(children);
            }
            Err(_err) => {
                self.blines[bid].has_error = true;
                self.blines[bid].children = Some(Vec::new());
            }
        }
        has_child_match
    }

    /// return the next child.
    /// load_children must have been called before on parent_id
    fn next_child(&mut self, parent_id: BId) -> Option<BId> {
        let bline = &mut self.blines[parent_id];
        if let Some(children) = &bline.children {
            if bline.next_child_idx < children.len() {
                let next_child = children[bline.next_child_idx];
                bline.next_child_idx += 1;
                Some(next_child)
            } else {
                Option::None
            }
        } else {
            unreachable!();
        }
    }

    /// first step of the build: we explore the directories and gather lines.
    /// If there's no search pattern we stop when we have enough lines to fill the screen.
    /// If there's a pattern, we try to gather more lines that will be sorted afterwards.
    fn gather_lines(&mut self, task_lifetime: &TaskLifetime, total_search: bool) -> Option<Vec<BId>> {
        let start = Instant::now();
        let mut out_blines: Vec<BId> = Vec::new(); // the blines we want to display
        let optimal_size = self
            .options
            .pattern
            .optimal_result_number(self.targeted_size);
        out_blines.push(self.root_id);
        let mut nb_lines_ok = 1; // in out_blines
        let mut open_dirs: VecDeque<BId> = VecDeque::new();
        let mut next_level_dirs: Vec<BId> = Vec::new();
        self.load_children(self.root_id);
        open_dirs.push_back(self.root_id);
        loop {
            if
                !total_search
                && (
                    (nb_lines_ok > optimal_size)
                    || (nb_lines_ok >= self.targeted_size && start.elapsed() > NOT_LONG)
                )
            {
                self.total_search = false;
                break;
            }
            if let Some(open_dir_id) = open_dirs.pop_front() {
                if let Some(child_id) = self.next_child(open_dir_id) {
                    open_dirs.push_back(open_dir_id);
                    let child = &self.blines[child_id];
                    if child.has_match {
                        nb_lines_ok += 1;
                    }
                    if