Patchwork [2,of,2,V4] rust: rustlazyancestors.__contains__

login
register
mail settings
Submitter Georges Racinet
Date Oct. 14, 2018, 1:22 p.m.
Message ID <50d03c9079ffe3932955.1539523327@ishtar>
Download mbox | patch
Permalink /patch/35994/
State Accepted
Headers show

Comments

Georges Racinet - Oct. 14, 2018, 1:22 p.m.
# HG changeset patch
# User Georges Racinet <gracinet@anybox.fr>
# Date 1539018701 -7200
#      Mon Oct 08 19:11:41 2018 +0200
# Node ID 50d03c9079ffe3932955353be076ff24c4e87804
# Parent  c04176c0f8b9aeaf196bd1eac00207d526f3d53b
# 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.
Yuya Nishihara - Oct. 14, 2018, 3:42 p.m.
On Sun, 14 Oct 2018 15:22:07 +0200, Georges Racinet wrote:
> # HG changeset patch
> # User Georges Racinet <gracinet@anybox.fr>
> # Date 1539018701 -7200
> #      Mon Oct 08 19:11:41 2018 +0200
> # Node ID 50d03c9079ffe3932955353be076ff24c4e87804
> # Parent  c04176c0f8b9aeaf196bd1eac00207d526f3d53b
> # EXP-Topic rustancestors-contains
> rust: rustlazyancestors.__contains__

> +static int rustla_contains(rustlazyancestorsObject *self, PyObject *rev) {
> +  if (!(PyInt_Check(rev))) {
> +    return 0;
> +  }
> +  return rustlazyancestors_contains(self->iter, PyInt_AS_LONG(rev));
> +}

Need tabs ;)

> --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
> +++ b/rust/hg-direct-ffi/rustfmt.toml	Mon Oct 08 19:11:41 2018 +0200
> @@ -0,0 +1,3 @@
> +max_width = 79
> +wrap_comments = true
> +error_on_line_overflow = true

Can you send a separate patch for this?

> +int rustlazyancestors_contains(rustlazyancestorsObject *self, long rev);

> +#[no_mangle]
> +pub extern "C" fn rustlazyancestors_contains(
> +    raw: *mut AncestorsIterator<Index>,
> +    target: c_long,
> +) -> c_long {
> +    raw_contains(raw, target)
> +}

s/-> c_long/-> c_int/
Georges Racinet - Oct. 15, 2018, 9:53 a.m.
On 10/14/2018 05:42 PM, Yuya Nishihara wrote:
> On Sun, 14 Oct 2018 15:22:07 +0200, Georges Racinet wrote:
>> # HG changeset patch
>> # User Georges Racinet <gracinet@anybox.fr>
>> # Date 1539018701 -7200
>> #      Mon Oct 08 19:11:41 2018 +0200
>> # Node ID 50d03c9079ffe3932955353be076ff24c4e87804
>> # Parent  c04176c0f8b9aeaf196bd1eac00207d526f3d53b
>> # EXP-Topic rustancestors-contains
>> rust: rustlazyancestors.__contains__
>> +static int rustla_contains(rustlazyancestorsObject *self, PyObject *rev) {
>> +  if (!(PyInt_Check(rev))) {
>> +    return 0;
>> +  }
>> +  return rustlazyancestors_contains(self->iter, PyInt_AS_LONG(rev));
>> +}
> Need tabs ;)
yup, sorry, forgot to check that one.
>
>> --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
>> +++ b/rust/hg-direct-ffi/rustfmt.toml	Mon Oct 08 19:11:41 2018 +0200
>> @@ -0,0 +1,3 @@
>> +max_width = 79
>> +wrap_comments = true
>> +error_on_line_overflow = true
> Can you send a separate patch for this?
Yes, it has nothing to do in this one
>
>> +int rustlazyancestors_contains(rustlazyancestorsObject *self, long rev);
>> +#[no_mangle]
>> +pub extern "C" fn rustlazyancestors_contains(
>> +    raw: *mut AncestorsIterator<Index>,
>> +    target: c_long,
>> +) -> c_long {
>> +    raw_contains(raw, target)
>> +}
> s/-> c_long/-> c_int/

Should be done in V5. Good catch, again

Patch

diff -r c04176c0f8b9 -r 50d03c9079ff mercurial/ancestor.py
--- a/mercurial/ancestor.py	Thu Sep 27 16:55:44 2018 +0200
+++ b/mercurial/ancestor.py	Mon Oct 08 19:11:41 2018 +0200
@@ -383,7 +383,7 @@ 
             self._containsiter = None
             return False
 
-class rustlazyancestors(lazyancestors):
+class rustlazyancestors(object):
 
     def __init__(self, index, revs, stoprev=0, inclusive=False):
         self._index = index
@@ -395,12 +395,26 @@ 
         # 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)
 
+    def __nonzero__(self):
+        """False if the set is empty, True otherwise.
+
+        It's better to duplicate this essentially trivial method than
+        to subclass lazyancestors
+        """
+        try:
+            next(iter(self))
+            return True
+        except StopIteration:
+            return False
+
     def __iter__(self):
         return parsers.rustlazyancestors(self._index,
                                          self._initrevs,
                                          self._stoprev,
                                          self._inclusive)
+
+    def __contains__(self, target):
+        return target in self._containsiter
diff -r c04176c0f8b9 -r 50d03c9079ff mercurial/cext/revlog.c
--- a/mercurial/cext/revlog.c	Thu Sep 27 16:55:44 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,
@@ -2395,6 +2396,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 */
@@ -2407,7 +2426,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 c04176c0f8b9 -r 50d03c9079ff rust/hg-core/src/ancestors.rs
--- a/rust/hg-core/src/ancestors.rs	Thu Sep 27 16:55:44 2018 +0200
+++ b/rust/hg-core/src/ancestors.rs	Mon Oct 08 19:11:41 2018 +0200
@@ -80,6 +80,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.
@@ -203,6 +223,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 c04176c0f8b9 -r 50d03c9079ff rust/hg-direct-ffi/rustfmt.toml
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/hg-direct-ffi/rustfmt.toml	Mon Oct 08 19:11:41 2018 +0200
@@ -0,0 +1,3 @@ 
+max_width = 79
+wrap_comments = true
+error_on_line_overflow = true
diff -r c04176c0f8b9 -r 50d03c9079ff rust/hg-direct-ffi/src/ancestors.rs
--- a/rust/hg-direct-ffi/src/ancestors.rs	Thu Sep 27 16:55:44 2018 +0200
+++ b/rust/hg-direct-ffi/src/ancestors.rs	Mon Oct 08 19:11:41 2018 +0200
@@ -139,6 +139,27 @@ 
     as_ref.next().unwrap_or(NULL_REVISION) as c_long
 }
 
+#[no_mangle]
+pub extern "C" fn rustlazyancestors_contains(
+    raw: *mut AncestorsIterator<Index>,
+    target: c_long,
+) -> c_long {
+    raw_contains(raw, target)
+}
+
+/// Testable (for any Graph) version of rustlazayancestors_next
+#[inline]
+fn raw_contains<G: Graph>(
+    raw: *mut AncestorsIterator<G>,
+    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 super::*;
@@ -226,4 +247,18 @@ 
     fn test_init_err_out_of_range() {
         assert!(stub_raw_init_from_vec(vec![25], 0, 0).is_null());
     }
+
+    #[test]
+    fn test_contains() {
+        let raw = stub_raw_init_from_vec(vec![5, 6], 0, 1);
+        assert_eq!(raw_contains(raw, 5), 1);
+        assert_eq!(raw_contains(raw, 2), 1);
+    }
+
+    #[test]
+    fn test_contains_exclusive() {
+        let raw = stub_raw_init_from_vec(vec![5, 6], 0, 0);
+        assert_eq!(raw_contains(raw, 5), 0);
+        assert_eq!(raw_contains(raw, 2), 1);
+    }
 }
diff -r c04176c0f8b9 -r 50d03c9079ff rust/hg-direct-ffi/src/lib.rs
--- a/rust/hg-direct-ffi/src/lib.rs	Thu Sep 27 16:55:44 2018 +0200
+++ b/rust/hg-direct-ffi/src/lib.rs	Mon Oct 08 19:11:41 2018 +0200
@@ -13,4 +13,7 @@ 
 extern crate libc;
 
 mod ancestors;
-pub use ancestors::{rustlazyancestors_drop, rustlazyancestors_init, rustlazyancestors_next};
+pub use ancestors::{
+    rustlazyancestors_contains, rustlazyancestors_drop,
+    rustlazyancestors_init, rustlazyancestors_next,
+};