comparison rust/hg-core/src/dirstate/status.rs @ 43271:99394e6c5d12

rust-dirstate-status: add first Rust implementation of `dirstate.status`

Note: This patch also added the rayon crate as a Cargo dependency. It will
help us immensely in making Rust code parallel and easy to maintain. It is
a stable, well-known, and supported crate maintained by people on the Rust
team.

The current `dirstate.status` method has grown over the years through bug
reports and new features to the point where it got too big and too complex.

This series does not yet improve the logic, but adds a Rust fast-path to speed
up certain cases.

Tested on mozilla-try-2019-02-18 with zstd compression:
    - `hg diff` on an empty working copy:
        - c: 1.64(+-)0.04s
        - rust+c before this change: 2.84(+-)0.1s
        - rust+c: 849(+-)40ms
    - `hg commit` when creating a file:
        - c: 5.960s
        - rust+c before this change: 5.828s
        - rust+c: 4.668s
    - `hg commit` when updating a file:
        - c: 4.866s
        - rust+c before this change: 4.371s
        - rust+c: 3.855s
    - `hg status -mard`
        - c: 1.82(+-)0.04s
        - rust+c before this change: 2.64(+-)0.1s
        - rust+c: 896(+-)30ms

The numbers are clear: the current Rust `dirstatemap` implementation is super
slow, its performance needs to be addressed.
This will be done in a future series, immediately after this one, with the goal
of getting Rust to be at least to the speed of the Python + C implementation
in all cases before the 5.2 freeze. At worse, we gate dirstatemap to only be used
in those cases.

Cases where the fast-path is not executed:
    - for commands that need ignore support (`status`, for example)
    - if subrepos are found (should not be hard to add, but winter is coming)
    - any other matcher than an `alwaysmatcher`, like patterns, etc.
    - with extensions like `sparse` and `fsmonitor`

The next step after this is to rethink the logic to be closer to
Jane Street's Valentin Gatien-Baron's Rust fast-path which does a lot less
work when possible.

Differential Revision: https://phab.mercurial-scm.org/D7058

43271:99394e6c5d12

// status.rs
//
// Copyright 2019 Raphaël Gomès <[e-mail]>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.

//! Rust implementation of dirstate.status (dirstate.py).
//! It is currently missing a lot of functionality compared to the Python one
//! and will only be triggered in narrow cases.

use crate::utils::files::HgMetadata;
use crate::utils::hg_path::{hg_path_to_path_buf, HgPath, HgPathBuf};
use crate::{DirstateEntry, DirstateMap, EntryState};
use rayon::prelude::*;
use std::collections::HashMap;
use std::fs::Metadata;
use std::path::Path;

/// Get stat data about the files explicitly specified by match.
/// TODO subrepos
fn walk_explicit(
    files: &[impl AsRef<HgPath> + Sync],
    dmap: &DirstateMap,
    root_dir: impl AsRef<Path> + Sync,
) -> std::io::Result<HashMap<HgPathBuf, Option<HgMetadata>>> {
    let mut results = HashMap::new();

    // A tuple of the normalized filename and the `Result` of the call to
    // `symlink_metadata` for separate handling.
    type WalkTuple<'a> = (&'a HgPath, std::io::Result<Metadata>);

    let stats_res: std::io::Result<Vec<WalkTuple>> = files
        .par_iter()
        .map(|filename| {
            // TODO normalization
            let normalized = filename.as_ref();

            let target_filename =
                root_dir.as_ref().join(hg_path_to_path_buf(normalized)?);

            Ok((normalized, target_filename.symlink_metadata()))
        })
        .collect();

    for res in stats_res? {
        match res {
            (normalized, Ok(stat)) => {
                if stat.is_file() {
                    results.insert(
                        normalized.to_owned(),
                        Some(HgMetadata::from_metadata(stat)),
                    );
                } else {
                    if dmap.contains_key(normalized) {
                        results.insert(normalized.to_owned(), None);
                    }
                }
            }
            (normalized, Err(_)) => {
                if dmap.contains_key(normalized) {
                    results.insert(normalized.to_owned(), None);
                }
            }
        };
    }

    Ok(results)
}

// Stat all entries in the `DirstateMap` and return their new metadata.
pub fn stat_dmap_entries(
    dmap: &DirstateMap,
    results: &HashMap<HgPathBuf, Option<HgMetadata>>,
    root_dir: impl AsRef<Path> + Sync,
) -> std::io::Result<Vec<(HgPathBuf, Option<HgMetadata>)>> {
    dmap.par_iter()
        .filter_map(
            // Getting file metadata is costly, so we don't do it if the
            // file is already present in the results, hence `filter_map`
            |(filename, _)| -> Option<
                std::io::Result<(HgPathBuf, Option<HgMetadata>)>
            > {
                if results.contains_key(filename) {
                    return None;
                }
                let meta = match hg_path_to_path_buf(filename) {
                    Ok(p) => root_dir.as_ref().join(p).symlink_metadata(),
                    Err(e) => return Some(Err(e.into())),
                };

                Some(match meta {
                    Ok(ref m)
                        if !(m.file_type().is_file()
                            || m.file_type().is_symlink()) =>
                    {
                        Ok((filename.to_owned(), None))
                    }
                    Ok(m) => Ok((
                        filename.to_owned(),
                        Some(HgMetadata::from_metadata(m)),
                    )),
                    Err(ref e)
                        if e.kind() == std::io::ErrorKind::NotFound
                            || e.raw_os_error() == Some(20) =>
                    {
                        // Rust does not yet have an `ErrorKind` for
                        // `NotADirectory` (errno 20)
                        // It happens if the dirstate contains `foo/bar` and
                        // foo is not a directory
                        Ok((filename.to_owned(), None))
                    }
                    Err(e) => Err(e),
                })
            },
        )
        .collect()
}

pub struct StatusResult {
    pub modified: Vec<HgPathBuf>,
    pub added: Vec<HgPathBuf>,
    pub removed: Vec<HgPathBuf>,
    pub deleted: Vec<HgPathBuf>,
    pub clean: Vec<HgPathBuf>,
    // TODO ignored
    // TODO unknown
}

fn build_response(
    dmap: &DirstateMap,
    list_clean: bool,
    last_normal_time: i64,
    check_exec: bool,
    results: HashMap<HgPathBuf, Option<HgMetadata>>,
) -> (Vec<HgPathBuf>, StatusResult) {
    let mut lookup = vec![];
    let mut modified = vec![];
    let mut added = vec![];
    let mut removed = vec![];
    let mut deleted = vec![];
    let mut clean = vec![];

    for (filename, metadata_option) in results.into_iter() {
        let DirstateEntry {
            state,
            mode,
            mtime,
            size,
        } = match dmap.get(&filename) {
            None => {
                continue;
            }
            Some(e) => *e,
        };

        match metadata_option {
            None => {
                match state {
                    EntryState::Normal
                    | EntryState::Merged
                    | EntryState::Added => deleted.push(filename),
                    EntryState::Removed => removed.push(filename),
                    _ => {}
                };
            }
            Some(HgMetadata {
                st_mode,
                st_size,
                st_mtime,
                ..
            }) => {
                match state {
                    EntryState::Normal => {
                        // Dates and times that are outside the 31-bit signed
                        // range are compared modulo 2^31. This should prevent
                        // it from behaving badly with very large files or
                        // corrupt dates while still having a high probability
                        // of detecting changes. (issue2608)
                        let range_mask = 0x7fffffff;

                        let size_changed = (size != st_size as i32)
                            && size != (st_size as i32 & range_mask);
                        let mode_changed = (mode ^ st_mode as i32) & 0o100
                            != 0o000
                            && check_exec;
                        if size >= 0
                            && (size_changed || mode_changed)
                            || size == -2  // other parent
                            || dmap.copy_map.contains_key(&filename)
                        {
                            modified.push(filename);
                        } else if mtime != st_mtime as i32
                            && mtime != (st_mtime as i32 & range_mask)
                        {
                            lookup.push(filename);
                        } else if st_mtime == last_normal_time {
                            // the file may have just been marked as normal and
                            // it may have changed in the same second without
                            // changing its size. This can happen if we quickly
                            // do multiple commits. Force lookup, so we don't
                            // miss such a racy file change.
                            lookup.push(filename);
                        } else if list_clean {
                            clean.push(filename);
                        }
                    }
                    EntryState::Merged => modified.push(filename),
                    EntryState::Added => added.push(filename),
                    EntryState::Removed => removed.push(filename),
                    EntryState::Unknown => {}
                }
            }
        }
    }

    (
        lookup,
        StatusResult {
            modified,
            added,
            removed,
            deleted,
            clean,
        },
    )
}

pub fn status(
    dmap: &DirstateMap,
    root_dir: impl AsRef<Path> + Sync + Copy,
    files: &[impl AsRef<HgPath> + Sync],
    list_clean: bool,
    last_normal_time: i64,
    check_exec: bool,
) -> std::io::Result<(Vec<HgPathBuf>, StatusResult)> {
    let mut results = walk_explicit(files, &dmap, root_dir)?;

    results.extend(stat_dmap_entries(&dmap, &results, root_dir)?);

    Ok(build_response(
        &dmap,
        list_clean,
        last_normal_time,
        check_exec,
        results,
    ))
}