From patchwork Tue Oct 9 15:22:50 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [6,of,6,V2] rust: rustlazyancestors.__contains__ From: Georges Racinet X-Patchwork-Id: 35583 Message-Id: <28fdd7b9c08ebb8bdd69.1539098570@purity.tombe.racinet.fr> To: mercurial-devel@mercurial-scm.org Date: Tue, 09 Oct 2018 17:22:50 +0200 # HG changeset patch # User Georges Racinet # Date 1539018701 -7200 # Mon Oct 08 19:11:41 2018 +0200 # Node ID 28fdd7b9c08ebb8bdd692f5d6f6dd4b94dbd40b5 # Parent c5b4c3dd622ec7636eb78211b06cf86bb547444f # EXP-Topic rustancestors-contains rust: rustlazyancestors.__contains__ This changeset provides a Rust implementation of the iteration performed by lazyancestor.__contains__ It has the advantage over the Python iteration to use the 'seen' set encapsuled into the dedicated iterator (self._containsiter), rather than storing emitted items in another set (self._containsseen), and hence should reduce the memory footprint. Also, there's no need to convert intermediate emitted revisions back into Python integers. At this point, it would be tempting to implement the whole lazyancestor object in Rust, but that would lead to more C wrapping code (two objects) for little expected benefits. diff -r c5b4c3dd622e -r 28fdd7b9c08e mercurial/ancestor.py --- a/mercurial/ancestor.py Thu Sep 27 16:46:43 2018 +0200 +++ b/mercurial/ancestor.py Mon Oct 08 19:11:41 2018 +0200 @@ -395,7 +395,6 @@ # constructor (from C code) doesn't understand anything else yet self._initrevs = initrevs = list(revs) - self._containsseen = set() self._containsiter = parsers.rustlazyancestors( index, initrevs, stoprev, inclusive) @@ -404,3 +403,6 @@ self._initrevs, self._stoprev, self._inclusive) + + def __contains__(self, target): + return target in self._containsiter diff -r c5b4c3dd622e -r 28fdd7b9c08e mercurial/cext/revlog.c --- a/mercurial/cext/revlog.c Thu Sep 27 16:46:43 2018 +0200 +++ b/mercurial/cext/revlog.c Mon Oct 08 19:11:41 2018 +0200 @@ -2316,6 +2316,7 @@ int inclusive); void rustlazyancestors_drop(rustlazyancestorsObject *self); int rustlazyancestors_next(rustlazyancestorsObject *self); +int rustlazyancestors_contains(rustlazyancestorsObject *self, long rev); /* CPython instance methods */ static int rustla_init(rustlazyancestorsObject *self, @@ -2394,6 +2395,24 @@ return PyInt_FromLong(res); } +static int rustla_contains(rustlazyancestorsObject *self, PyObject *rev) { + if (!(PyInt_Check(rev))) { + return 0; + } + return rustlazyancestors_contains(self->iter, PyInt_AS_LONG(rev)); +} + +static PySequenceMethods rustla_sequence_methods = { + 0, /* sq_length */ + 0, /* sq_concat */ + 0, /* sq_repeat */ + 0, /* sq_item */ + 0, /* sq_slice */ + 0, /* sq_ass_item */ + 0, /* sq_ass_slice */ + (objobjproc)rustla_contains, /* sq_contains */ +}; + static PyTypeObject rustlazyancestorsType = { PyVarObject_HEAD_INIT(NULL, 0) /* header */ "parsers.rustlazyancestors", /* tp_name */ @@ -2406,7 +2425,7 @@ 0, /* tp_compare */ 0, /* tp_repr */ 0, /* tp_as_number */ - 0, /* tp_as_sequence */ + &rustla_sequence_methods, /* tp_as_sequence */ 0, /* tp_as_mapping */ 0, /* tp_hash */ 0, /* tp_call */ diff -r c5b4c3dd622e -r 28fdd7b9c08e mercurial/rust/src/ancestors.rs --- a/mercurial/rust/src/ancestors.rs Thu Sep 27 16:46:43 2018 +0200 +++ b/mercurial/rust/src/ancestors.rs Mon Oct 08 19:11:41 2018 +0200 @@ -81,6 +81,26 @@ self.conditionally_push_rev(parents.1); Ok(()) } + + /// Consumes partially the iterator to tell if the given target + /// revision + /// is in the ancestors it emits. + /// This is meant for iterators actually dedicated to that kind of + /// purpose + pub fn contains(&mut self, target: Revision) -> bool { + if self.seen.contains(&target) && target != NULL_REVISION { + return true; + } + for rev in self { + if rev == target { + return true; + } + if rev < target { + return false; + } + } + false + } } /// Main implementation. @@ -204,6 +224,18 @@ assert_eq!(iter.next(), None) } + #[test] + fn test_contains() { + let mut lazy = AncestorsIterator::new(Stub, vec![10, 1], 0, true) + .unwrap(); + assert!(lazy.contains(1)); + assert!(!lazy.contains(3)); + + let mut lazy = AncestorsIterator::new(Stub, vec![0], 0, false) + .unwrap(); + assert!(!lazy.contains(NULL_REVISION)); + } + /// A corrupted Graph, supporting error handling tests struct Corrupted; diff -r c5b4c3dd622e -r 28fdd7b9c08e mercurial/rust/src/cpython.rs --- a/mercurial/rust/src/cpython.rs Thu Sep 27 16:46:43 2018 +0200 +++ b/mercurial/rust/src/cpython.rs Mon Oct 08 19:11:41 2018 +0200 @@ -156,6 +156,27 @@ as_ref.next().unwrap_or(NULL_REVISION) as c_long } +#[no_mangle] +pub extern "C" fn rustlazyancestors_contains( + raw: *mut AncestorsIterator, + target: c_long, +) -> c_long { + raw_contains(raw, target) +} + +/// Testable (for any Graph) version of rustlazayancestors_next +#[inline] +fn raw_contains( + raw: *mut AncestorsIterator, + target: c_long, +) -> c_long { + let as_ref = unsafe { &mut *raw }; + if as_ref.contains(target as Revision) { + return 1; + } + 0 +} + #[cfg(test)] mod tests { use std::thread; @@ -237,4 +258,20 @@ .is_null() ); } + + #[test] + fn test_contains() { + let mut initrevs: [c_long; 2] = [5, 6]; + let raw = raw_init(Stub, initrevs.len(), initrevs.as_mut_ptr(), 0, 1); + assert_eq!(raw_contains(raw, 5), 1); + assert_eq!(raw_contains(raw, 2), 1); + } + + #[test] + fn test_contains_exclusive() { + let mut initrevs: [c_long; 2] = [5, 6]; + let raw = raw_init(Stub, initrevs.len(), initrevs.as_mut_ptr(), 0, 0); + assert_eq!(raw_contains(raw, 5), 0); + assert_eq!(raw_contains(raw, 2), 1); + } } diff -r c5b4c3dd622e -r 28fdd7b9c08e mercurial/rust/src/lib.rs --- a/mercurial/rust/src/lib.rs Thu Sep 27 16:46:43 2018 +0200 +++ b/mercurial/rust/src/lib.rs Mon Oct 08 19:11:41 2018 +0200 @@ -6,7 +6,7 @@ mod cpython; pub use cpython::{rustlazyancestors_init, rustlazyancestors_drop, - rustlazyancestors_next}; + rustlazyancestors_next, rustlazyancestors_contains}; /// Mercurial revision numbers ///