This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1406

treedirstate: implement efficient case collision detection
ClosedPublic

Authored by mbthomas on Nov 14 2017, 12:39 PM.
Tags
None
Subscribers
jsgf, durham

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGX3607720eac2b: treedirstate: implement efficient case collision detection
Summary

Add a mechanism to the dirstate trees to allow lookups based on filtered views
of the keys. For a given filtering function, this returns one (if any) of the
keys for which filter(key) matches the input. The filtered values in each
directory node are cached to improve subsequent lookups.

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

mbthomas created this revision.Nov 14 2017, 12:39 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 14 2017, 12:39 PM
mbthomas updated this revision to Diff 3524.Nov 15 2017, 4:14 AM
mbthomas updated this revision to Diff 3603.Nov 17 2017, 9:45 AM
mbthomas updated this revision to Diff 3658.Nov 20 2017, 12:21 PM
durham added a subscriber: durham.Nov 21 2017, 11:48 AM

There's enough rust in here I'm not comfortable accepting just yet. Also a question inline.

rust/treedirstate/src/python.rs
342

Unrelated to this diff, but I think we may want to move more of the dirstate business logic into pure rust (not the python interop layer) in the near future. So we can get to a pure native code hg status.

rust/treedirstate/src/tree.rs
49

We might want to be explicit that only one filter can be used with a tree at a time, since we don't invalidate the cache based on the filter.

treedirstate/__init__.py
458

If we didn't have _newfiles, why would calling it twice cause a problem? Doesn't the file that was added to the dirstate the first time have the same case as the file that's trying to be added a second time? And therefore is not a conflict?

mbthomas added inline comments.Nov 21 2017, 1:29 PM
rust/treedirstate/src/python.rs
342

In this case the casefolder is a python function, which is actually a bit complicated on some platforms (in particular cygwin - see posix.py). If we do move the casefolding business logic into Rust we'll need to handle that somehow (possibly by not supporting Cygwin).

treedirstate/__init__.py
458

Nothing gets added to the dirstate until after all candidates have been audited. The collision we're protecting against is in the self._newfilesfolded map, which contains the normalized forms only, not in the dirstate.

mbthomas updated this revision to Diff 3733.Nov 21 2017, 1:35 PM
mbthomas updated this revision to Diff 3774.Nov 22 2017, 1:14 PM
mbthomas updated this revision to Diff 3827.Nov 24 2017, 11:53 AM
mbthomas updated this revision to Diff 3844.Nov 24 2017, 3:18 PM
mbthomas updated this revision to Diff 3868.Nov 27 2017, 8:00 AM
durham accepted this revision.Nov 27 2017, 1:00 PM
This revision is now accepted and ready to land.Nov 27 2017, 1:00 PM
Closed by commit rFBHGX3607720eac2b: treedirstate: implement efficient case collision detection (authored by mbthomas). · Explain WhyNov 28 2017, 6:02 PM
This revision was automatically updated to reflect the committed changes.
jsgf added a subscriber: jsgf.Dec 6 2017, 5:26 PM
jsgf added inline comments.
rust/treedirstate/src/python.rs
7–9

This could just be one line:

use errors::{self, ErrorKind};

Revision Contents
Changeset List

Diff 3603

rust/treedirstate/src/dirstate.rs

self.removed.file_count() self.removed.file_count()
} }
/// Get an entry from the tracked tree. /// Get an entry from the tracked tree.
pub fn get_tracked<'a>(&'a mut self, name: KeyRef) -> Result<Option<&'a T>> { pub fn get_tracked<'a>(&'a mut self, name: KeyRef) -> Result<Option<&'a T>> {
self.tracked.get(self.store.store_view(), name) self.tracked.get(self.store.store_view(), name)
} }
pub fn get_tracked_filtered_key<F>(
&mut self,
name: KeyRef,
filter: &mut F,
) -> Result<Option<Key>>
where
F: FnMut(KeyRef) -> Result<Key>,
{
self.tracked
.get_filtered_key(self.store.store_view(), name, filter)
}
/// Visit all tracked files with a visitor. /// Visit all tracked files with a visitor.
pub fn visit_tracked<F>(&mut self, visitor: &mut F) -> Result<()> pub fn visit_tracked<F>(&mut self, visitor: &mut F) -> Result<()>
where where
F: FnMut(&Vec<KeyRef>, &mut T) -> Result<()>, F: FnMut(&Vec<KeyRef>, &mut T) -> Result<()>,
{ {
self.store.cache()?; self.store.cache()?;
self.tracked.visit(self.store.store_view(), visitor) self.tracked.visit(self.store.store_view(), visitor)
} }

rust/treedirstate/src/python.rs

// Copyright Facebook, Inc. 2017 // Copyright Facebook, Inc. 2017
//! Python bindings for treedirstate. //! Python bindings for treedirstate.
use cpython::*; use cpython::*;
use cpython::exc; use cpython::exc;
use dirstate::Dirstate; use dirstate::Dirstate;
use errors::ErrorKind; use errors::ErrorKind;
use errors;
use filestate::FileState; use filestate::FileState;
jsgfUnsubmitted
Not Done

This could just be one line:

use errors::{self, ErrorKind};
jsgf: This could just be one line: ``` use errors::{self, ErrorKind}; ```
use std::cell::RefCell; use std::cell::RefCell;
use std::path::PathBuf; use std::path::PathBuf;
use store::BlockId; use store::BlockId;
use tree::KeyRef; use tree::{Key, KeyRef};
py_module_initializer!( py_module_initializer!(
rusttreedirstate, rusttreedirstate,
initrusttreedirstate, initrusttreedirstate,
PyInit_rusttreedirstate, PyInit_rusttreedirstate,
|py, m| { |py, m| {
m.add_class::<RustDirstateMap>(py)?; m.add_class::<RustDirstateMap>(py)?;
Ok(()) Ok(())
nonnormal.call(py, (filename,), None).map_err(|e| callback_error(py, e))?; nonnormal.call(py, (filename,), None).map_err(|e| callback_error(py, e))?;
Ok(()) Ok(())
}; };
map_pyerr!(py, dirstate.visit_removed(&mut removed_visitor), exc::IOError)?; map_pyerr!(py, dirstate.visit_removed(&mut removed_visitor), exc::IOError)?;
Ok(py.None()) Ok(py.None())
} }
def getcasefoldedtracked(
&self,
filename: PyObject,
casefolder: PyObject
) -> PyResult<Option<PyObject>> {
let mut dirstate = self.dirstate(py).borrow_mut();
let filename = filename.extract::<PyBytes>(py)?;
let mut filter = |filename: KeyRef| -> errors::Result<Key> {
let unfolded = PyBytes::new(py, filename);
let folded = casefolder.call(py, (unfolded,), None)
.map_err(|e| callback_error(py, e))?
.extract::<PyBytes>(py)
.map_err(|e| callback_error(py, e))?;
Ok(folded.data(py).to_vec())
};
let filtered_key = dirstate.get_tracked_filtered_key(filename.data(py), &mut filter);
Ok(map_pyerr!(py, filtered_key, exc::IOError)?.map(|k| {
PyBytes::new(py, &k).into_object()
}))
}
durhamUnsubmitted
Not Done

Unrelated to this diff, but I think we may want to move more of the dirstate business logic into pure rust (not the python interop layer) in the near future. So we can get to a pure native code hg status.

durham: Unrelated to this diff, but I think we may want to move more of the dirstate business logic…
mbthomasAuthorUnsubmitted
Not Done

In this case the casefolder is a python function, which is actually a bit complicated on some platforms (in particular cygwin - see posix.py). If we do move the casefolding business logic into Rust we'll need to handle that somehow (possibly by not supporting Cygwin).

mbthomas: In this case the casefolder is a python function, which is actually a bit complicated on some…
}); });

rust/treedirstate/src/tree.rs

/// The ID of the directory in the store. If None, this directory has not yet been /// The ID of the directory in the store. If None, this directory has not yet been
/// written to the back-end store in its current state. /// written to the back-end store in its current state.
id: Option<BlockId>, id: Option<BlockId>,
/// The set of files and directories in this directory, indexed by their name. If None, /// The set of files and directories in this directory, indexed by their name. If None,
/// then the ID must not be None, and the entries are yet to be loaded from the back-end /// then the ID must not be None, and the entries are yet to be loaded from the back-end
/// store. /// store.
entries: Option<NodeEntryList<T>>, entries: Option<NodeEntryList<T>>,
/// A map from keys that have been filtered through a case-folding filter function to the
/// original key. This is used for case-folded look-ups.
filtered_keys: Option<VecMap<Key, Key>>,
durhamUnsubmitted
Not Done

We might want to be explicit that only one filter can be used with a tree at a time, since we don't invalidate the cache based on the filter.

durham: We might want to be explicit that only one filter can be used with a tree at a time, since we…
} }
/// The root of the tree. The count of files in the tree is maintained for fast size /// The root of the tree. The count of files in the tree is maintained for fast size
/// determination. /// determination.
pub struct Tree<T> { pub struct Tree<T> {
root: Node<T>, root: Node<T>,
file_count: u32, file_count: u32,
} }
} }
impl<T: Storable + Clone> Node<T> { impl<T: Storable + Clone> Node<T> {
/// Create a new empty Node. This has no ID as it is not yet written to the store. /// Create a new empty Node. This has no ID as it is not yet written to the store.
fn new() -> Node<T> { fn new() -> Node<T> {
Node { Node {
id: None, id: None,
entries: Some(NodeEntryList::new()), entries: Some(NodeEntryList::new()),
filtered_keys: None,
} }
} }
/// Create a new Node for an existing entry in the store. The entries are not loaded until /// Create a new Node for an existing entry in the store. The entries are not loaded until
/// the load method is called. /// the load method is called.
fn open(id: BlockId) -> Node<T> { fn open(id: BlockId) -> Node<T> {
Node { Node {
id: Some(id), id: Some(id),
entries: None, entries: None,
filtered_keys: None,
} }
} }
/// Attempt to load a node from a store. /// Attempt to load a node from a store.
fn load(&mut self, store: &StoreView) -> Result<()> { fn load(&mut self, store: &StoreView) -> Result<()> {
if self.entries.is_some() { if self.entries.is_some() {
// Already loaded. // Already loaded.
return Ok(()); return Ok(());
(Some((name.to_vec(), NodeEntry::File(info.clone()))), true) (Some((name.to_vec(), NodeEntry::File(info.clone()))), true)
} }
PathRecurse::ConflictingFile(_name, _path, _file) => { PathRecurse::ConflictingFile(_name, _path, _file) => {
unimplemented!("File/Directory conflict") unimplemented!("File/Directory conflict")
} }
}; };
if let Some((new_key, new_entry)) = new_entry { if let Some((new_key, new_entry)) = new_entry {
self.load_entries(store)?.insert(new_key, new_entry); self.load_entries(store)?.insert(new_key, new_entry);
self.filtered_keys = None;
} }
self.id = None; self.id = None;
Ok(file_added) Ok(file_added)
} }
/// Remove a file from the node. The name may contain a path, in which case sufficient /// Remove a file from the node. The name may contain a path, in which case sufficient
/// subdirectories are updated to remove the file. /// subdirectories are updated to remove the file.
/// ///
/// Returns a pair of booleans (file_removed, now_empty) indicating whether the file /// Returns a pair of booleans (file_removed, now_empty) indicating whether the file
/// was removed, and whether the diectory is now empty. /// was removed, and whether the diectory is now empty.
fn remove(&mut self, store: &StoreView, name: KeyRef) -> Result<(bool, bool)> { fn remove(&mut self, store: &StoreView, name: KeyRef) -> Result<(bool, bool)> {
let (file_removed, remove_entry) = match self.path_recurse(store, name)? { let (file_removed, remove_entry) = match self.path_recurse(store, name)? {
PathRecurse::Directory(dir, path, node) => { PathRecurse::Directory(dir, path, node) => {
let (file_removed, now_empty) = node.remove(store, path)?; let (file_removed, now_empty) = node.remove(store, path)?;
(file_removed, if now_empty { Some(dir) } else { None }) (file_removed, if now_empty { Some(dir) } else { None })
} }
PathRecurse::ExactDirectory(_dir, _node) => (false, None), PathRecurse::ExactDirectory(_dir, _node) => (false, None),
PathRecurse::MissingDirectory(_dir, _path) => (false, None), PathRecurse::MissingDirectory(_dir, _path) => (false, None),
PathRecurse::File(name, _file) => (true, Some(name)), PathRecurse::File(name, _file) => (true, Some(name)),
PathRecurse::MissingFile(_name) => (false, None), PathRecurse::MissingFile(_name) => (false, None),
PathRecurse::ConflictingFile(_name, _path, _file) => (false, None), PathRecurse::ConflictingFile(_name, _path, _file) => (false, None),
}; };
if let Some(entry) = remove_entry { if let Some(entry) = remove_entry {
self.load_entries(store)?.remove(entry); self.load_entries(store)?.remove(entry);
self.filtered_keys = None;
self.id = None; self.id = None;
} }
if file_removed { if file_removed {
self.id = None; self.id = None;
} }
Ok((file_removed, self.load_entries(store)?.is_empty())) Ok((file_removed, self.load_entries(store)?.is_empty()))
} }
/// Performs a key lookup using filtered keys.
///
/// Applies the filter function to each key in the node, then returns the real key that
/// matches the name provided. The name may contain a path, in which case the subdirectories
/// of this node are also queried.
///
/// Returns a reversed vector of key references for each path element, or None if no file
/// matches the requested name after filtering.
fn get_filtered_key<'a, F>(
&'a mut self,
store: &StoreView,
name: KeyRef,
filter: &mut F,
) -> Result<Option<Vec<KeyRef<'a>>>>
where
F: FnMut(KeyRef) -> Result<Key>,
{
let (elem, path) = split_key(name);
if self.filtered_keys.is_none() {
let new_map = {
let entries = self.load_entries(store)?;
let mut new_map = VecMap::with_capacity(entries.len());
for (k, _v) in entries.iter() {
new_map.insert(filter(k)?, k.to_vec());
}
new_map
};
self.filtered_keys = Some(new_map);
}
if let Some(path) = path {
if let Some(mapped_elem) = self.filtered_keys.as_ref().unwrap().get(elem) {
if let Some(&mut NodeEntry::Directory(ref mut node)) =
self.entries.as_mut().unwrap().get_mut(mapped_elem)
{
if let Some(mut mapped_path) = node.get_filtered_key(store, path, filter)? {
mapped_path.push(mapped_elem);
return Ok(Some(mapped_path));
}
}
}
Ok(None)
} else {
Ok(
self.filtered_keys
.as_ref()
.unwrap()
.get(elem)
.map(|e| vec![e.as_ref()]),
)
}
}
} }
impl<T: Storable + Clone> Tree<T> { impl<T: Storable + Clone> Tree<T> {
/// Create a new empty tree. /// Create a new empty tree.
pub fn new() -> Tree<T> { pub fn new() -> Tree<T> {
Tree { Tree {
root: Node::new(), root: Node::new(),
file_count: 0, file_count: 0,
pub fn remove(&mut self, store: &StoreView, name: KeyRef) -> Result<bool> { pub fn remove(&mut self, store: &StoreView, name: KeyRef) -> Result<bool> {
let removed = self.root.remove(store, name)?.0; let removed = self.root.remove(store, name)?.0;
if removed { if removed {
assert!(self.file_count > 0); assert!(self.file_count > 0);
self.file_count -= 1; self.file_count -= 1;
} }
Ok(removed) Ok(removed)
} }
pub fn get_filtered_key<F>(
&mut self,
store: &StoreView,
name: KeyRef,
filter: &mut F,
) -> Result<Option<Key>>
where
F: FnMut(KeyRef) -> Result<Key>,
{
Ok(self.root.get_filtered_key(store, name, filter)?.map(
|mut path| {
path.reverse();
path.concat()
},
))
}
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use store::NullStore; use store::NullStore;
use store::tests::MapStore; use store::tests::MapStore;
use tree::{KeyRef, Tree}; use tree::{Key, KeyRef, Tree};
use filestate::FileState; use filestate::FileState;
use errors::*;
// Test files in order. Note lexicographic ordering of file9 and file10. // Test files in order. Note lexicographic ordering of file9 and file10.
static TEST_FILES: [(&[u8], u32, i32, i32); 16] = [ static TEST_FILES: [(&[u8], u32, i32, i32); 16] = [
(b"dirA/subdira/file1", 0o644, 1, 10001), (b"dirA/subdira/file1", 0o644, 1, 10001),
(b"dirA/subdira/file2", 0o644, 2, 10002), (b"dirA/subdira/file2", 0o644, 2, 10002),
(b"dirA/subdirb/file3", 0o644, 3, 10003), (b"dirA/subdirb/file3", 0o644, 3, 10003),
(b"dirB/subdira/file4", 0o644, 4, 10004), (b"dirB/subdira/file4", 0o644, 4, 10004),
(b"dirB/subdira/subsubdirx/file5", 0o644, 5, 10005), (b"dirB/subdira/subsubdirx/file5", 0o644, 5, 10005),
assert_eq!( assert_eq!(
files, files,
TEST_FILES TEST_FILES
.iter() .iter()
.map(|t| t.0.to_vec()) .map(|t| t.0.to_vec())
.collect::<Vec<Vec<u8>>>() .collect::<Vec<Vec<u8>>>()
); );
} }
#[test]
fn filtered_keys() {
let ms = MapStore::new();
let mut t = Tree::new();
populate(&mut t, &ms);
// Define a mapping function that upper-cases 'A' characters:
fn map_upper_a(k: KeyRef) -> Result<Key> {
Ok(
k.iter()
.map(|c| if *c == b'a' { b'A' } else { *c })
.collect(),
)
}
// Look-up with normalized name should give non-normalized version.
assert_eq!(
t.get_filtered_key(&ms, b"dirA/subdirA/file1", &mut map_upper_a)
.expect("should succeed"),
Some(b"dirA/subdira/file1".to_vec())
);
// Look-up with non-normalized name should match nothing.
assert_eq!(
t.get_filtered_key(&ms, b"dirA/subdira/file1", &mut map_upper_a)
.expect("should succeed"),
None
);
}
} }

treedirstate/__init__.py

# Copyright Facebook, Inc. 2017 # Copyright Facebook, Inc. 2017
"""Tree-based Dirstate Implementation""" """Tree-based Dirstate Implementation"""
from mercurial import ( from mercurial import (
dirstate, dirstate,
encoding,
error, error,
extensions, extensions,
localrepo, localrepo,
node, node,
pycompat, pycompat,
registrar, registrar,
scmutil,
txnutil, txnutil,
util, util,
) )
from mercurial.i18n import _ from mercurial.i18n import _
import errno import errno
import heapq import heapq
import itertools import itertools
import struct import struct
def getremoved(self, filename, default=None): def getremoved(self, filename, default=None):
"""Returns (state, mode, size, mtime) for the removed file.""" """Returns (state, mode, size, mtime) for the removed file."""
return self._rmap.getremoved(filename, default) return self._rmap.getremoved(filename, default)
def get(self, filename, default=None): def get(self, filename, default=None):
return (self._rmap.gettracked(filename, None) or return (self._rmap.gettracked(filename, None) or
self._rmap.getremoved(filename, default)) self._rmap.getremoved(filename, default))
def getcasefoldedtracked(self, filename, foldfunc):
return self._rmap.getcasefoldedtracked(filename, foldfunc)
def __getitem__(self, filename): def __getitem__(self, filename):
item = (self._rmap.gettracked(filename, None) or item = (self._rmap.gettracked(filename, None) or
self._rmap.getremoved(filename, None)) self._rmap.getremoved(filename, None))
if item is None: if item is None:
raise KeyError(filename) raise KeyError(filename)
return item return item
def hastrackedfile(self, filename): def hastrackedfile(self, filename):
wlock.release() wlock.release()
def wrapdirstate(orig, self): def wrapdirstate(orig, self):
ds = orig(self) ds = orig(self)
if istreedirstate(self): if istreedirstate(self):
ds._mapcls = treedirstatemap ds._mapcls = treedirstatemap
return ds return ds
class casecollisionauditor(object):
def __init__(self, ui, abort, dirstate):
self._ui = ui
self._abort = abort
self._dirstate = dirstate
# The purpose of _newfiles is so that we don't complain about
# case collisions if someone were to call this object with the
# same filename twice.
self._newfiles = set()
durhamUnsubmitted
Not Done

If we didn't have _newfiles, why would calling it twice cause a problem? Doesn't the file that was added to the dirstate the first time have the same case as the file that's trying to be added a second time? And therefore is not a conflict?

durham: If we didn't have _newfiles, why would calling it twice cause a problem? Doesn't the file that…
mbthomasAuthorUnsubmitted
Not Done

Nothing gets added to the dirstate until after all candidates have been audited. The collision we're protecting against is in the self._newfilesfolded map, which contains the normalized forms only, not in the dirstate.

mbthomas: Nothing gets added to the dirstate until after all candidates have been audited. The collision…
self._newfilesfolded = set()
def __call__(self, f):
if f in self._newfiles:
return
fl = encoding.lower(f)
if (f not in self._dirstate and
(fl in self._newfilesfolded or
self._dirstate._map.getcasefoldedtracked(fl, encoding.lower))):
msg = _('possible case-folding collision for %s') % f
if self._abort:
raise error.Abort(msg)
self._ui.warn(_("warning: %s\n") % msg)
self._newfiles.add(f)
self._newfilesfolded.add(fl)
def wrapcca(orig, ui, abort, dirstate):
if util.safehasattr(dirstate._map, 'getcasefoldedtracked'):
return casecollisionauditor(ui, abort, dirstate)
else:
return orig(ui, abort, dirstate)
def wrapnewreporequirements(orig, repo): def wrapnewreporequirements(orig, repo):
reqs = orig(repo) reqs = orig(repo)
reqs.add('treedirstate') reqs.add('treedirstate')
return reqs return reqs
def featuresetup(ui, supported): def featuresetup(ui, supported):
supported |= {'treedirstate'} supported |= {'treedirstate'}
def extsetup(ui): def extsetup(ui):
# Check this version of Mercurial has the extension points we need # Check this version of Mercurial has the extension points we need
if not util.safehasattr(dirstate.dirstatemap, "hasdir"): if not util.safehasattr(dirstate.dirstatemap, "hasdir"):
ui.warn(_("this version of Mercurial doesn't support treedirstate\n")) ui.warn(_("this version of Mercurial doesn't support treedirstate\n"))
return return
if useinnewrepos and util.safehasattr(localrepo, 'newreporequirements'): if useinnewrepos and util.safehasattr(localrepo, 'newreporequirements'):
extensions.wrapfunction(localrepo, 'newreporequirements', extensions.wrapfunction(localrepo, 'newreporequirements',
wrapnewreporequirements) wrapnewreporequirements)
localrepo.localrepository.featuresetupfuncs.add(featuresetup) localrepo.localrepository.featuresetupfuncs.add(featuresetup)
extensions.wrapfunction(localrepo.localrepository.dirstate, 'func', extensions.wrapfunction(localrepo.localrepository.dirstate, 'func',
wrapdirstate) wrapdirstate)
extensions.wrapfunction(scmutil, 'casecollisionauditor', wrapcca)
def reposetup(ui, repo): def reposetup(ui, repo):
ui.setconfig('treedirstate', 'enabled', istreedirstate(repo)) ui.setconfig('treedirstate', 'enabled', istreedirstate(repo))
# debug commands # debug commands
cmdtable = {} cmdtable = {}
command = registrar.command(cmdtable) command = registrar.command(cmdtable)