This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1403

treedirstate: better iteration using visitor pattern
ClosedPublic

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

Details

Reviewers
jsgf
Group Reviewers
Restricted Project
Commits
rFBHGXe5128555cede: treedirstate: better iteration using visitor pattern
Summary

In order to allow the python interface code to perform actions on each node in
the tree without creating python-specific interfaces in the generic Rust code,
add a method of iterating over the tree, executing a closure at each file.

Use this to implement the methods that give iterators over the filenames in the
tree. This performs better than the get_first/get_next-style iterators.

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 3600.Nov 17 2017, 9:45 AM
mbthomas updated this revision to Diff 3655.Nov 20 2017, 12:21 PM
durham added a subscriber: durham.Nov 21 2017, 12:49 AM
durham added inline comments.
treedirstate/__init__.py
128

Do we eventually do the same thing for these iterators?

mbthomas added inline comments.Nov 21 2017, 6:46 AM
treedirstate/__init__.py
128

I don't have a better implementation for these iterators. For the iterators that return lists of names, building a list in one go and then returning an iterator over that list turned out to be much more performant than using the getfirst/getnext iterators (not really surprising), but is also better than core where the equivalent function iterates over the dict keys and then sorts them.

These ones are more difficult, as we need the names and the state tuples, which we construct on the fly from the data in the tree. I'm not sure that constructing the whole sequence in one iteration would be the right approach.

This seems adequate for now, and we can iterate on it later if it turns out we're spending all our time in treedirstatemapiterator.__next__.

mbthomas updated this revision to Diff 3730.Nov 21 2017, 1:35 PM
mbthomas updated this revision to Diff 3771.Nov 22 2017, 1:14 PM
jsgf accepted this revision.Nov 22 2017, 6:52 PM
jsgf added a subscriber: jsgf.
jsgf added inline comments.
rust/treedirstate/src/python.rs
186

Does the compiler complain without the annotations, or is it just for documentation?

treedirstate/__init__.py
128

There's experimental generator support in Rust nightly, which may well land in stable. It might be helpful here.

This revision is now accepted and ready to land.Nov 22 2017, 6:52 PM
mbthomas added inline comments.Nov 23 2017, 7:24 AM
rust/treedirstate/src/python.rs
186

It's needed. The compiler can't deduce the types for filepath or state without them.

mbthomas updated this revision to Diff 3824.Nov 24 2017, 11:53 AM
mbthomas updated this revision to Diff 3842.Nov 24 2017, 3:18 PM
mbthomas updated this revision to Diff 3865.Nov 27 2017, 8:00 AM
Closed by commit rFBHGXe5128555cede: treedirstate: better iteration using visitor pattern (authored by mbthomas). · Explain WhyNov 28 2017, 6:01 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 3932

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)
} }
/// Visit all tracked files with a visitor.
pub fn visit_tracked<F>(&mut self, visitor: &mut F) -> Result<()>
where
F: FnMut(&Vec<KeyRef>, &T) -> Result<()>,
{
self.store.cache()?;
self.tracked.visit(self.store.store_view(), visitor)
}
/// Get the name and state of the first file in the tracked tree. /// Get the name and state of the first file in the tracked tree.
pub fn get_first_tracked<'a>(&'a mut self) -> Result<Option<(Key, &'a T)>> { pub fn get_first_tracked<'a>(&'a mut self) -> Result<Option<(Key, &'a T)>> {
self.store.cache()?; self.store.cache()?;
self.tracked.get_first(self.store.store_view()) self.tracked.get_first(self.store.store_view())
} }
/// Get the name and state of the next file in the tracked tree after the named file. /// Get the name and state of the next file in the tracked tree after the named file.
pub fn get_next_tracked<'a>(&'a mut self, name: KeyRef) -> Result<Option<(Key, &'a T)>> { pub fn get_next_tracked<'a>(&'a mut self, name: KeyRef) -> Result<Option<(Key, &'a T)>> {
self.tracked.get_next(self.store.store_view(), name) self.tracked.get_next(self.store.store_view(), name)
} }
pub fn has_tracked_dir(&mut self, name: KeyRef) -> Result<bool> { pub fn has_tracked_dir(&mut self, name: KeyRef) -> Result<bool> {
self.tracked.has_dir(self.store.store_view(), name) self.tracked.has_dir(self.store.store_view(), name)
} }
/// Get an entry from the removed tree. /// Get an entry from the removed tree.
pub fn get_removed<'a>(&'a mut self, name: KeyRef) -> Result<Option<&'a T>> { pub fn get_removed<'a>(&'a mut self, name: KeyRef) -> Result<Option<&'a T>> {
self.removed.get(self.store.store_view(), name) self.removed.get(self.store.store_view(), name)
} }
/// Visit all removed files with a visitor.
pub fn visit_removed<F>(&mut self, visitor: &mut F) -> Result<()>
where
F: FnMut(&Vec<KeyRef>, &T) -> Result<()>,
{
self.removed.visit(self.store.store_view(), visitor)
}
/// Get the name and state of the first file in the removed tree. /// Get the name and state of the first file in the removed tree.
pub fn get_first_removed<'a>(&'a mut self) -> Result<Option<(Key, &'a T)>> { pub fn get_first_removed<'a>(&'a mut self) -> Result<Option<(Key, &'a T)>> {
self.removed.get_first(self.store.store_view()) self.removed.get_first(self.store.store_view())
} }
/// 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)

rust/treedirstate/src/errors.rs

display("invalid store id: {}", id), display("invalid store id: {}", id),
} }
ReadOnlyStore { ReadOnlyStore {
description("store is read-only"), description("store is read-only"),
} }
CorruptTree { CorruptTree {
description("treedirstate is corrupt"), description("treedirstate is corrupt"),
} }
CallbackError(desc: String) {
description("callback error"),
display("callback error: {}", desc),
}
} }
foreign_links { foreign_links {
Io(::std::io::Error); Io(::std::io::Error);
Utf8(::std::str::Utf8Error); Utf8(::std::str::Utf8Error);
Utf8String(::std::string::FromUtf8Error); Utf8String(::std::string::FromUtf8Error);
} }
} }

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 filestate::FileState; use filestate::FileState;
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;
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(())
} }
); );
fn callback_error(py: Python, mut e: PyErr) -> ErrorKind {
let s = e.instance(py)
.extract::<String>(py)
.unwrap_or_else(|_e| "unknown exception".to_string());
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>>;
def __new__( def __new__(
_cls, _cls,
_ui: &PyObject, _ui: &PyObject,
opener: &PyObject opener: &PyObject
def hasremoveddir(&self, dirname: PyBytes) -> PyResult<bool> { def hasremoveddir(&self, dirname: PyBytes) -> PyResult<bool> {
let mut dirstate = self.dirstate(py).borrow_mut(); let mut dirstate = self.dirstate(py).borrow_mut();
dirstate dirstate
.has_removed_dir(dirname.data(py)) .has_removed_dir(dirname.data(py))
.map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description())) .map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))
} }
def visittrackedfiles(&self, target: PyObject) -> PyResult<PyObject> {
let mut dirstate = self.dirstate(py).borrow_mut();
let mut visitor = |filepath: &Vec<KeyRef>, _state: &FileState| {
jsgfUnsubmitted
Not Done

Does the compiler complain without the annotations, or is it just for documentation?

jsgf: Does the compiler complain without the annotations, or is it just for documentation?
mbthomasAuthorUnsubmitted
Not Done

It's needed. The compiler can't deduce the types for filepath or state without them.

mbthomas: It's needed. The compiler can't deduce the types for `filepath` or `state` without them.
let filename = PyBytes::new(py, &filepath.concat()).into_object();
target.call(py, (filename,), None).map_err(|e| callback_error(py, e))?;
Ok(())
};
dirstate
.visit_tracked(&mut visitor)
.map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))?;
Ok(py.None())
}
def visitremovedfiles(&self, target: PyObject) -> PyResult<PyObject> {
let mut dirstate = self.dirstate(py).borrow_mut();
let mut visitor = |filepath: &Vec<KeyRef>, _state: &FileState| {
let filename = PyBytes::new(py, &filepath.concat()).into_object();
target.call(py, (filename,), None).map_err(|e| callback_error(py, e))?;
Ok(())
};
dirstate
.visit_removed(&mut visitor)
.map_err(|e| PyErr::new::<exc::IOError, _>(py, e.description()))?;
Ok(py.None())
}
// Get the next dirstate object after the provided filename. If the filename is None, // Get the next dirstate object after the provided filename. If the filename is None,
// returns the first file in the tree. If the provided filename is the last file, returns // returns the first file in the tree. If the provided filename is the last file, returns
// None. // None.
def getnext(&self, filename: Option<PyBytes>, removed: bool) -> PyResult<PyObject> { def getnext(&self, filename: Option<PyBytes>, removed: bool) -> PyResult<PyObject> {
let mut dirstate = self.dirstate(py).borrow_mut(); let mut dirstate = self.dirstate(py).borrow_mut();
let next = if removed { let next = if removed {
match filename { match filename {
Some(filename) => { Some(filename) => {

rust/treedirstate/src/tree.rs

// Write out this node. // Write out this node.
self.write_entries(store) self.write_entries(store)
} else { } else {
// This node and its descendents have not been modified. // This node and its descendents have not been modified.
Ok(()) Ok(())
} }
} }
// Visit all of the files in under this node, by calling the visitor function on each one.
fn visit<'a, F>(
&'a mut self,
store: &StoreView,
path: &mut Vec<KeyRef<'a>>,
visitor: &mut F,
) -> Result<()>
where
F: FnMut(&Vec<KeyRef>, &T) -> Result<()>,
{
for (name, entry) in self.load_entries(store)?.iter_mut() {
path.push(name);
match entry {
&mut NodeEntry::Directory(ref mut node) => {
node.visit(store, path, visitor)?;
}
&mut NodeEntry::File(ref file) => {
visitor(path, file)?;
}
}
path.pop();
}
Ok(())
}
/// Get the first file in the subtree under this node. If the subtree is not empty, returns a /// Get the first file in the subtree under this node. If the subtree is not empty, returns a
/// pair containing the path to the file as a reversed vector of key references for each path /// pair containing the path to the file as a reversed vector of key references for each path
/// element, and a reference to the file. /// element, and a reference to the file.
fn get_first<'node>( fn get_first<'node>(
&'node mut self, &'node mut self,
store: &StoreView, store: &StoreView,
) -> Result<Option<(Vec<KeyRef<'node>>, &'node T)>> { ) -> Result<Option<(Vec<KeyRef<'node>>, &'node T)>> {
for (name, entry) in self.load_entries(store)?.iter_mut() { for (name, entry) in self.load_entries(store)?.iter_mut() {
self.root.write_delta(store)?; self.root.write_delta(store)?;
Ok(()) Ok(())
} }
pub fn get<'a>(&'a mut self, store: &StoreView, name: KeyRef) -> Result<Option<&'a T>> { pub fn get<'a>(&'a mut self, store: &StoreView, name: KeyRef) -> Result<Option<&'a T>> {
Ok(self.root.get(store, name)?) Ok(self.root.get(store, name)?)
} }
pub fn visit<F>(&mut self, store: &StoreView, visitor: &mut F) -> Result<()>
where
F: FnMut(&Vec<KeyRef>, &T) -> Result<()>,
{
let mut path = Vec::new();
self.root.visit(store, &mut path, visitor)
}
pub fn get_first<'a>(&'a mut self, store: &StoreView) -> Result<Option<(Key, &'a T)>> { pub fn get_first<'a>(&'a mut self, store: &StoreView) -> Result<Option<(Key, &'a T)>> {
Ok(self.root.get_first(store)?.map(|(mut path, file)| { Ok(self.root.get_first(store)?.map(|(mut path, file)| {
path.reverse(); path.reverse();
(path.concat(), file) (path.concat(), file)
})) }))
} }
pub fn get_next<'a>( pub fn get_next<'a>(
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use store::NullStore; use store::NullStore;
use store::tests::MapStore; use store::tests::MapStore;
use tree::Tree; use tree::{KeyRef, Tree};
use filestate::FileState; use filestate::FileState;
// 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),
let mut t2 = Tree::open(t_root, t_count); let mut t2 = Tree::open(t_root, t_count);
assert_eq!( assert_eq!(
t2.get(&ms2, b"dirB/subdira/subsubdirz/file7") t2.get(&ms2, b"dirB/subdira/subsubdirz/file7")
.expect("can get"), .expect("can get"),
Some(&FileState::new(b'n', 0o755, 7, 10007)) Some(&FileState::new(b'n', 0o755, 7, 10007))
); );
} }
#[test]
fn visit() {
let mut ms = MapStore::new();
let mut t = Tree::new();
populate(&mut t, &ms);
let mut files = Vec::new();
{
let mut v = |path: &Vec<KeyRef>, _fs: &FileState| {
files.push(path.concat());
Ok(())
};
t.visit(&mut ms, &mut v).expect("can visit");
}
assert_eq!(
files,
TEST_FILES
.iter()
.map(|t| t.0.to_vec())
.collect::<Vec<Vec<u8>>>()
);
}
} }

treedirstate/__init__.py

node, node,
pycompat, pycompat,
registrar, registrar,
txnutil, txnutil,
util, util,
) )
from mercurial.i18n import _ from mercurial.i18n import _
import errno import errno
import heapq
import itertools import itertools
import struct import struct
from .rusttreedirstate import RustDirstateMap from .rusttreedirstate import RustDirstateMap
dirstateheader = b'########################treedirstate####' dirstateheader = b'########################treedirstate####'
treedirstateversion = 1 treedirstateversion = 1
useinnewrepos = True useinnewrepos = True
self.writeuint(len(v)) self.writeuint(len(v))
self.buffer.write(v) self.buffer.write(v)
# 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, items=False): def __init__(self, map_, removed=False):
self._rmap = map_ self._rmap = map_
self._removed = removed self._removed = removed
self._items = items
self._at = None self._at = None
def __iter__(self): def __iter__(self):
return self return self
def __next__(self): def __next__(self):
nextitem = self._rmap.getnext(self._at, self._removed) nextitem = self._rmap.getnext(self._at, self._removed)
if nextitem is None: if nextitem is None:
raise StopIteration raise StopIteration
self._at = nextitem[0] self._at = nextitem[0]
return nextitem if self._items else nextitem[0] return nextitem
def next(self): def next(self):
return self.__next__() return self.__next__()
class treedirstatemap(object): class treedirstatemap(object):
def __init__(self, ui, opener, root, importmap=None): def __init__(self, ui, opener, root, importmap=None):
self._ui = ui self._ui = ui
self._opener = opener self._opener = opener
self.setparents(node.nullid, node.nullid) self.setparents(node.nullid, node.nullid)
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, items=True) return treedirstatemapiterator(self._rmap, removed=False)
def iterremoveditems(self): def iterremoveditems(self):
""" """
Returns an iterator over (filename, (state, mode, size, mtime)) for Returns an iterator over (filename, (state, mode, size, mtime)) for
files that have been marked as removed. files that have been marked as removed.
""" """
return treedirstatemapiterator(self._rmap, removed=True, items=True) return treedirstatemapiterator(self._rmap, removed=True)
durhamUnsubmitted
Not Done

Do we eventually do the same thing for these iterators?

durham: Do we eventually do the same thing for these iterators?
mbthomasAuthorUnsubmitted
Not Done

I don't have a better implementation for these iterators. For the iterators that return lists of names, building a list in one go and then returning an iterator over that list turned out to be much more performant than using the getfirst/getnext iterators (not really surprising), but is also better than core where the equivalent function iterates over the dict keys and then sorts them.

These ones are more difficult, as we need the names and the state tuples, which we construct on the fly from the data in the tree. I'm not sure that constructing the whole sequence in one iteration would be the right approach.

This seems adequate for now, and we can iterate on it later if it turns out we're spending all our time in treedirstatemapiterator.__next__.

mbthomas: I don't have a better implementation for these iterators. For the iterators that return lists…
jsgfUnsubmitted
Not Done

There's experimental generator support in Rust nightly, which may well land in stable. It might be helpful here.

jsgf: There's experimental generator support in Rust nightly, which may well land in stable. It might…
def iteritems(self): def iteritems(self):
return itertools.chain(self.itertrackeditems(), return itertools.chain(self.itertrackeditems(),
self.iterremoveditems()) self.iterremoveditems())
def gettracked(self, filename, default=None): def gettracked(self, filename, default=None):
"""Returns (state, mode, size, mtime) for the tracked file.""" """Returns (state, mode, size, mtime) for the tracked file."""
return self._rmap.gettracked(filename, default) return self._rmap.gettracked(filename, default)
def hasremovedfile(self, filename): def hasremovedfile(self, filename):
"""Returns true if the file is recorded as removed in the dirstate.""" """Returns true if the file is recorded as removed in the dirstate."""
return self._rmap.hasremovedfile(filename) return self._rmap.hasremovedfile(filename)
def __contains__(self, filename): def __contains__(self, filename):
return self.hastrackedfile(filename) or self.hasremovedfile(filename) return self.hastrackedfile(filename) or self.hasremovedfile(filename)
def trackedfiles(self): def trackedfiles(self):
"""Returns an iterator of all filenames tracked by the dirstate.""" """Returns a list of all filenames tracked by the dirstate."""
return treedirstatemapiterator(self._rmap, removed=False, items=False) trackedfiles = []
self._rmap.visittrackedfiles(trackedfiles.append)
return iter(trackedfiles)
def removedfiles(self): def removedfiles(self):
"""Returns an iterator of all removed files in the dirstate.""" """Returns a list of all removed files in the dirstate."""
return treedirstatemapiterator(self._rmap, removed=True, items=False) removedfiles = []
self._rmap.visitremovedfiles(removedfiles.append)
return removedfiles
def __iter__(self): def __iter__(self):
"""Returns an iterator of all files in the dirstate.""" """Returns an iterator of all files in the dirstate."""
return itertools.chain(self.trackedfiles(), self.removedfiles()) trackedfiles = self.trackedfiles()
removedfiles = self.removedfiles()
if removedfiles:
return heapq.merge(iter(trackedfiles), iter(removedfiles))
else:
return iter(trackedfiles)
def keys(self): def keys(self):
return list(iter(self)) return list(iter(self))
def hastrackeddir(self, dirname): def hastrackeddir(self, dirname):
""" """
Returns True if the dirstate includes a directory. Returns True if the dirstate includes a directory.
""" """