This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1409

treedirstate: implement casefolding maps for case insensitive filesystems
ClosedPublic

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

Details

Reviewers
quark
durham
Group Reviewers
Restricted Project
Commits
rFBHGXd00a94fe351f: treedirstate: implement casefolding maps for case insensitive filesystems
Summary

The dirfoldmap and filefoldmap on the dirstatemap object map from normalized
filename to the form it appears in the dirstate (denormalized form).

The dicts these functions return are also modified by the dirstate with
filenames discovered by examining the disk, so use an overlay dictionary backed
by the real dirstate to allow this to happen.

Diff Detail

Repository
rFBHGX Facebook Mercurial Extensions
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

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 3606.Nov 17 2017, 9:45 AM
mbthomas updated this revision to Diff 3661.Nov 20 2017, 12:21 PM
mbthomas updated this revision to Diff 3736.Nov 21 2017, 1:36 PM
mbthomas updated this revision to Diff 3776.Nov 22 2017, 1:14 PM
quark accepted this revision.Nov 23 2017, 6:30 PM
quark added a subscriber: quark.
quark added inline comments.
treedirstate/__init__.py
81

key in s is in theory more efficient - it avoids a method table lookup.

This revision is now accepted and ready to land.Nov 23 2017, 6:30 PM
mbthomas updated this revision to Diff 3830.Nov 24 2017, 11:53 AM
mbthomas updated this revision to Diff 3847.Nov 24 2017, 3:18 PM
mbthomas updated this revision to Diff 3870.Nov 27 2017, 8:00 AM
durham accepted this revision.Nov 27 2017, 1:04 PM
durham added a subscriber: durham.

Could use tests.

mbthomas updated this revision to Diff 3889.Nov 27 2017, 4:33 PM
Closed by commit rFBHGXd00a94fe351f: treedirstate: implement casefolding maps for case insensitive filesystems (authored by mbthomas). · Explain WhyNov 28 2017, 6:02 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 3938

rust/treedirstate/src/dirstate.rs

/// Get the name and state of the next file in the removed tree after the named file. /// Get the name and state of the next file in the removed tree after the named file.
pub fn get_next_removed<'a>(&'a mut self, name: KeyRef) -> Result<Option<(Key, &'a T)>> { pub fn get_next_removed<'a>(&'a mut self, name: KeyRef) -> Result<Option<(Key, &'a T)>> {
self.removed.get_next(self.store.store_view(), name) self.removed.get_next(self.store.store_view(), name)
} }
pub fn has_removed_dir(&mut self, name: KeyRef) -> Result<bool> { pub fn has_removed_dir(&mut self, name: KeyRef) -> Result<bool> {
self.removed.has_dir(self.store.store_view(), name) self.removed.has_dir(self.store.store_view(), name)
} }
pub fn clear_filtered_keys(&mut self) {
self.tracked.clear_filtered_keys();
}
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use dirstate::Dirstate; use dirstate::Dirstate;
use tempdir::TempDir; use tempdir::TempDir;
use tree::Storable; use tree::Storable;
use std::io::{Read, Write}; use std::io::{Read, Write};

rust/treedirstate/src/python.rs

.extract::<String>(py) .extract::<String>(py)
.unwrap_or_else(|_e| "unknown exception".to_string()); .unwrap_or_else(|_e| "unknown exception".to_string());
ErrorKind::CallbackError(s) ErrorKind::CallbackError(s)
} }
py_class!(class RustDirstateMap |py| { py_class!(class RustDirstateMap |py| {
data repodir: PathBuf; data repodir: PathBuf;
data dirstate: RefCell<Dirstate<FileState>>; data dirstate: RefCell<Dirstate<FileState>>;
data casefolderid: RefCell<Option<usize>>;
def __new__( def __new__(
_cls, _cls,
_ui: &PyObject, _ui: &PyObject,
opener: &PyObject opener: &PyObject
) -> PyResult<RustDirstateMap> { ) -> PyResult<RustDirstateMap> {
let repodir = opener.getattr(py, "base")?.extract::<String>(py)?; let repodir = opener.getattr(py, "base")?.extract::<String>(py)?;
let dirstate = Dirstate::new(); let dirstate = Dirstate::new();
RustDirstateMap::create_instance( RustDirstateMap::create_instance(
py, py,
repodir.into(), repodir.into(),
RefCell::new(dirstate)) RefCell::new(dirstate),
RefCell::new(None))
} }
def clear(&self) -> PyResult<PyObject> { def clear(&self) -> PyResult<PyObject> {
let mut dirstate = self.dirstate(py).borrow_mut(); let mut dirstate = self.dirstate(py).borrow_mut();
dirstate.clear(); dirstate.clear();
Ok(py.None()) Ok(py.None())
} }
.map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))?; .map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))?;
Ok(py.None()) Ok(py.None())
} }
def getcasefoldedtracked( def getcasefoldedtracked(
&self, &self,
filename: PyBytes, filename: PyBytes,
casefolder: PyObject casefolder: PyObject,
casefolderid: usize
) -> PyResult<Option<PyObject>> { ) -> PyResult<Option<PyObject>> {
let mut dirstate = self.dirstate(py).borrow_mut(); let mut dirstate = self.dirstate(py).borrow_mut();
let mut curcasefolderid = self.casefolderid(py).borrow_mut();
let mut filter = |filename: KeyRef| -> errors::Result<Key> { let mut filter = |filename: KeyRef| -> errors::Result<Key> {
let unfolded = PyBytes::new(py, filename); let unfolded = PyBytes::new(py, filename);
let folded = casefolder.call(py, (unfolded,), None) let folded = casefolder.call(py, (unfolded,), None)
.map_err(|e| callback_error(py, e))? .map_err(|e| callback_error(py, e))?
.extract::<PyBytes>(py) .extract::<PyBytes>(py)
.map_err(|e| callback_error(py, e))?; .map_err(|e| callback_error(py, e))?;
Ok(folded.data(py).to_vec()) Ok(folded.data(py).to_vec())
}; };
if let Some(id) = *curcasefolderid {
if id != casefolderid {
dirstate.clear_filtered_keys();
}
}
*curcasefolderid = Some(casefolderid);
dirstate dirstate
.get_tracked_filtered_key(filename.data(py), &mut filter) .get_tracked_filtered_key(filename.data(py), &mut filter)
.map(|o| o.map(|k| PyBytes::new(py, &k).into_object())) .map(|o| o.map(|k| PyBytes::new(py, &k).into_object()))
.map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description())) .map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))
} }
}); });

rust/treedirstate/src/tree.rs

/// 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<NodeEntryMap<T>>, entries: Option<NodeEntryMap<T>>,
/// A map from keys that have been filtered through a case-folding filter function to the /// 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 values are cached, so /// original key. This is used for case-folded look-ups. Filtered values are cached, so
/// only a single filter function can be used with a tree. /// only a single filter function can be used with a tree. Call `clear_filtered_keys` to
/// clear the cache in order to use a different filter function.
filtered_keys: Option<VecMap<Key, Key>>, filtered_keys: Option<VecMap<Key, Key>>,
} }
/// 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,
self.filtered_keys self.filtered_keys
.as_ref() .as_ref()
.unwrap() .unwrap()
.get(elem) .get(elem)
.map(|e| vec![e.as_ref()]), .map(|e| vec![e.as_ref()]),
) )
} }
} }
fn clear_filtered_keys(&mut self) {
self.filtered_keys = None;
if let Some(ref mut entries) = self.entries {
for (_k, v) in entries.iter_mut() {
if let &mut NodeEntry::Directory(ref mut node) = v {
node.clear_filtered_keys();
}
}
}
}
} }
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,
{ {
Ok(self.root.get_filtered_key(store, name, filter)?.map( Ok(self.root.get_filtered_key(store, name, filter)?.map(
|mut path| { |mut path| {
path.reverse(); path.reverse();
path.concat() path.concat()
}, },
)) ))
} }
pub fn clear_filtered_keys(&mut self) {
self.root.clear_filtered_keys();
}
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use store::NullStore; use store::NullStore;
use store::tests::MapStore; use store::tests::MapStore;
use tree::{Key, KeyRef, Tree}; use tree::{Key, KeyRef, Tree};

treedirstate/__init__.py

def writeuint(self, v): def writeuint(self, v):
self.buffer.write(struct.pack(">L", v)) self.buffer.write(struct.pack(">L", v))
def writestr(self, v): def writestr(self, v):
self.writeuint(len(v)) self.writeuint(len(v))
self.buffer.write(v) self.buffer.write(v)
class _overlaydict(dict):
def __init__(self, lookup, *args, **kwargs):
super(_overlaydict, self).__init__(*args, **kwargs)
self.lookup = lookup
def get(self, key, default=None):
s = super(_overlaydict, self)
if s.__contains__(key):
quarkUnsubmitted
Not Done

key in s is in theory more efficient - it avoids a method table lookup.

quark: `key in s` is in theory more efficient - it avoids a method table lookup.
return s.__getitem__(key)
r = self.lookup(key)
if r is not None:
return r
return default
def __getitem__(self, key):
s = super(_overlaydict, self)
if s.__contains__(key):
return s[key]
r = self.lookup(key)
if r is not None:
return r
raise KeyError(key)
# The treedirstatemap iterator uses the getnext method on the dirstatemap # The treedirstatemap iterator uses the getnext method on the dirstatemap
# to find the next item on each call. This involves searching down the # to find the next item on each call. This involves searching down the
# tree each time. A future improvement is to keep the state between each # tree each time. A future improvement is to keep the state between each
# call to avoid these extra searches. # call to avoid these extra searches.
class treedirstatemapiterator(object): class treedirstatemapiterator(object):
def __init__(self, map_, removed=False): def __init__(self, map_, removed=False):
self._rmap = map_ self._rmap = map_
self._removed = removed self._removed = removed
pass pass
def clear(self): def clear(self):
self._rmap.clear() self._rmap.clear()
self.copymap.clear() self.copymap.clear()
self._nonnormalset.clear() self._nonnormalset.clear()
self._otherparentset.clear() self._otherparentset.clear()
self.setparents(node.nullid, node.nullid) self.setparents(node.nullid, node.nullid)
util.clearcachedproperty(self, "filefoldmap")
util.clearcachedproperty(self, "dirfoldmap")
def __len__(self): def __len__(self):
"""Returns the number of files, including removed files.""" """Returns the number of files, including removed files."""
return self._rmap.filecount() return self._rmap.filecount()
def itertrackeditems(self): def itertrackeditems(self):
"""Returns an iterator over (filename, (state, mode, size, mtime)).""" """Returns an iterator over (filename, (state, mode, size, mtime))."""
return treedirstatemapiterator(self._rmap, removed=False) return treedirstatemapiterator(self._rmap, removed=False)
"""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): def getcasefoldedtracked(self, filename, foldfunc):
return self._rmap.getcasefoldedtracked(filename, foldfunc) return self._rmap.getcasefoldedtracked(filename, foldfunc, id(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
return self._nonnormalset return self._nonnormalset
@property @property
def otherparentset(self): def otherparentset(self):
if self._otherparentset is None: if self._otherparentset is None:
self._computenonnormals() self._computenonnormals()
return self._otherparentset return self._otherparentset
def getfilefoldmap(self): @util.propertycache
def filefoldmap(self):
"""Returns a dictionary mapping normalized case paths to their """Returns a dictionary mapping normalized case paths to their
non-normalized versions. non-normalized versions.
""" """
raise NotImplementedError() def lookup(key):
f = self.getcasefoldedtracked(key, util.normcase)
if f is not None and self._rmap.hastrackedfile(f):
return f
else:
return None
return _overlaydict(lookup)
def getdirfoldmap(self): @util.propertycache
def dirfoldmap(self):
""" """
Returns a dictionary mapping normalized case paths to their Returns a dictionary mapping normalized case paths to their
non-normalized versions for directories. non-normalized versions for directories.
""" """
raise NotImplementedError() def lookup(key):
d = self.getcasefoldedtracked(key + '/', util.normcase)
if d is not None and self._rmap.hastrackeddir(d):
return d.rstrip('/')
else:
return None
return _overlaydict(lookup)
def identity(self): def identity(self):
if self._identity is None: if self._identity is None:
self.read() self.read()
return self._identity return self._identity
def _opendirstatefile(self): def _opendirstatefile(self):
fp, _mode = txnutil.trypending(self._root, self._opener, self._filename) fp, _mode = txnutil.trypending(self._root, self._opener, self._filename)