This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6231

rust-discovery: starting core implementation
ClosedPublic

Authored by gracinet on Apr 12 2019, 2:33 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG10b465d61556: rust-discovery: starting core implementation
Summary

Once exposed to the Python side, this core object will avoid
costly roundtrips with potentially big sets of revisions.

This changeset implements the core logic of the object only, i.e.,
manipulation of the missing, common and undefined set-like revision
attributes.

Diff Detail

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

Event Timeline

gracinet created this revision.Apr 12 2019, 2:33 PM
kevincox accepted this revision.Apr 14 2019, 4:14 PM

I'm not a huge fan of the design of this class because it has a strong protocol to use correctly. It would probably be better to have 3 classes and when you apply new information each class transitions into the next one. This allows the type system to ensure that you are using the class correctly. However it appears that this is just re-implementing an API so improving that API is probably out of scope for the time being.

Otherwise the implementation looks good.

rust/hg-core/src/discovery.rs
58

You can replace the early return by an if let. This also removed the .unwrap() which is always nice.

if let Some(ref mut undecided) = self.undecided {
    self.common.remove_ancestors_from(undecided)?;
}
74

I believe this .into_iter() is redundant because the for loop calls it for you.

94

This this imply that this method shouldn't be called until then? If so you should probably add a debug_assert!(self.is_complete()).

gracinet added a comment.Apr 15 2019, 6:09 AM

@kevincox Thanks for the reviews !

It would probably be better to have 3 classes and when you apply new information each class transitions into the next one. This allows the type system to ensure that you are using the class correctly.

That's an interesting idea. I expect it to solve my gripes with ensure_undecided() neatly. I'm not sure how it'd fare on the Python side, and probably wouldn't do it in the bindings to maintain compatibility, but I'll play with it a bit.
Maybe this could be a good topic for a follow-up ?
Note: I still have the various sampling methods to submit today or tomorrow, but I think they would play well with that idea.

kevincox added a comment.Apr 15 2019, 6:21 AM
In D6231#90744, @gracinet wrote:

That's an interesting idea. I expect it to solve my gripes with ensure_undecided() neatly. I'm not sure how it'd fare on the Python side, and probably wouldn't do it in the bindings to maintain compatibility, but I'll play with it a bit.

Well the point is to force the caller to acknowledge the state change, but in python that isn't really possible because it is dynamically typed. What I would probably do is still implement the Rust part with multiple structs but then wrap it in an enum for the python API. Then each python method call turns into.

fn do_thing() {
  match self {
    HasInfo(state) => state.do_thing()
    other => unreachable!("Invalid state for do_thing(). Expected HasInfo got {:?}.", other);
  }
}

And yes, this should allow you to avoid all of the unwraping since it would all be done at the API boundary.

I think you could also propagate this to python by having the "state" transition methods return a new object. However because you can't ensure that the code drops the access to the previous object you would have to copy everything into the new object or ensure that you don't mutate shared state. The value is still lower here though because of the dynamic nature of python.

Maybe this could be a good topic for a follow-up ?

Yeah, sounds reasonable.

gracinet added a comment.Apr 15 2019, 12:25 PM

What I would probably do is still implement the Rust part with multiple structs but then wrap it in an enum for the python API.

Yes, that's what I had in mind. Not sure where that enum would be defined (hg-cpython or hg-core) but it doesn't matter so much.

kevincox added a comment.Apr 15 2019, 12:43 PM
In D6231#90756, @gracinet wrote:

Yes, that's what I had in mind. Not sure where that enum would be defined (hg-cpython or hg-core) but it doesn't matter so much.

I would probably stick it in hg-cpython because it is a compromise for the python binding. For anyone using hg-core from rust I would hope that they directly use the structs.

But yes, not to important either way.

gracinet marked 2 inline comments as done.Apr 15 2019, 12:49 PM
gracinet updated this revision to Diff 14744.
gracinet added inline comments.Apr 15 2019, 12:49 PM
rust/hg-core/src/discovery.rs
58

ah, yes the trick is the ref mut inside the if let, I see

94

I'm not sure. It wouldn't be a straight error to call this early, as long as the caller knows what this means, but I don't have any use-case before the discovery is complete.

On the other hand, I could go as far as consume the discovery object and use self.common.into_bases_heads(), but maybe that could make things more complicated for the Python bindings.

kevincox added inline comments.Apr 15 2019, 12:59 PM
rust/hg-core/src/discovery.rs
94

If it is allowed can you document what happens what happens if you call it before then?

gracinet updated this revision to Diff 14794.Apr 17 2019, 8:16 AM
gracinet marked an inline comment as done.Apr 17 2019, 8:32 AM

I believe to have addressed your immediate concerns.

I played with splitting in different structs for the various stages of the process. It is indeed cleaner and clearer Rust code.
However mutating in place of Enums exposed to Python is a bit of a headache, because of the wrapping in RefCell<Box<T>>, and I don't have a solution for that, so I'm gonna think about that in a follow-up.

kevincox added a comment.Apr 17 2019, 8:58 AM
In D6231#91102, @gracinet wrote:

I believe to have addressed your immediate concerns.
I played with splitting in different structs for the various stages of the process. It is indeed cleaner and clearer Rust code.
However mutating in place of Enums exposed to Python is a bit of a headache, because of the wrapping in RefCell<Box<T>>, and I don't have a solution for that, so I'm gonna think about that in a follow-up.

Thanks, it looks good for now :)

Closed by commit rHG10b465d61556: rust-discovery: starting core implementation (authored by gracinet). · Explain WhyApr 18 2019, 7:26 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
AMrust/hg-core/src/discovery.rs (196 lines)
Mrust/hg-core/src/lib.rs (1 line)

Diff 14852

rust/hg-core/src/discovery.rs

  • This file was added.
// discovery.rs
//
// Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
//! Discovery operations
//!
//! This is a Rust counterpart to the `partialdiscovery` class of
//! `mercurial.setdiscovery`
use super::{Graph, GraphError, Revision};
use crate::ancestors::MissingAncestors;
use crate::dagops;
use std::collections::HashSet;
pub struct PartialDiscovery<G: Graph + Clone> {
target_heads: Option<Vec<Revision>>,
graph: G, // plays the role of self._repo
common: MissingAncestors<G>,
undecided: Option<HashSet<Revision>>,
missing: HashSet<Revision>,
}
impl<G: Graph + Clone> PartialDiscovery<G> {
/// Create a PartialDiscovery object, with the intent
/// of comparing our `::<target_heads>` revset to the contents of another
/// repo.
///
/// For now `target_heads` is passed as a vector, and will be used
/// at the first call to `ensure_undecided()`.
///
/// If we want to make the signature more flexible,
/// we'll have to make it a type argument of `PartialDiscovery` or a trait
/// object since we'll keep it in the meanwhile
pub fn new(graph: G, target_heads: Vec<Revision>) -> Self {
PartialDiscovery {
undecided: None,
target_heads: Some(target_heads),
graph: graph.clone(),
common: MissingAncestors::new(graph, vec![]),
missing: HashSet::new(),
}
}
/// Register revisions known as being common
pub fn add_common_revisions(
&mut self,
common: impl IntoIterator<Item = Revision>,
) -> Result<(), GraphError> {
self.common.add_bases(common);
if let Some(ref mut undecided) = self.undecided {
self.common.remove_ancestors_from(undecided)?;
}
Ok(())
}
kevincoxUnsubmitted
Done

You can replace the early return by an if let. This also removed the .unwrap() which is always nice.

if let Some(ref mut undecided) = self.undecided {
    self.common.remove_ancestors_from(undecided)?;
}
kevincox: You can replace the early return by an `if let`. This also removed the `.unwrap()` which is…
gracinetAuthorUnsubmitted
Not Done

ah, yes the trick is the ref mut inside the if let, I see

gracinet: ah, yes the trick is the `ref mut` inside the `if let`, I see
/// Register revisions known as being missing
pub fn add_missing_revisions(
&mut self,
missing: impl IntoIterator<Item = Revision>,
) -> Result<(), GraphError> {
self.ensure_undecided()?;
let range = dagops::range(
&self.graph,
missing,
self.undecided.as_ref().unwrap().iter().cloned(),
)?;
let undecided_mut = self.undecided.as_mut().unwrap();
for missrev in range {
self.missing.insert(missrev);
undecided_mut.remove(&missrev);
}
kevincoxUnsubmitted
Done

I believe this .into_iter() is redundant because the for loop calls it for you.

kevincox: I believe this `.into_iter()` is redundant because the `for` loop calls it for you.
Ok(())
}
/// Do we have any information about the peer?
pub fn has_info(&self) -> bool {
self.common.has_bases()
}
/// Did we acquire full knowledge of our Revisions that the peer has?
pub fn is_complete(&self) -> bool {
self.undecided.as_ref().map_or(false, |s| s.is_empty())
}
/// Return the heads of the currently known common set of revisions.
///
/// If the discovery process is not complete (see `is_complete()`), the
/// caller must be aware that this is an intermediate state.
///
/// On the other hand, if it is complete, then this is currently
/// the only way to retrieve the end results of the discovery process.
kevincoxUnsubmitted
Not Done

This this imply that this method shouldn't be called until then? If so you should probably add a debug_assert!(self.is_complete()).

kevincox: This this imply that this method shouldn't be called until then? If so you should probably add…
gracinetAuthorUnsubmitted
Not Done

I'm not sure. It wouldn't be a straight error to call this early, as long as the caller knows what this means, but I don't have any use-case before the discovery is complete.

On the other hand, I could go as far as consume the discovery object and use self.common.into_bases_heads(), but maybe that could make things more complicated for the Python bindings.

gracinet: I'm not sure. It wouldn't be a straight error to call this early, as long as the caller knows…
kevincoxUnsubmitted
Done

If it is allowed can you document what happens what happens if you call it before then?

kevincox: If it is allowed can you document what happens what happens if you call it before then?
///
/// We may introduce in the future an `into_common_heads` call that
/// would be more appropriate for normal Rust callers, dropping `self`
/// if it is complete.
pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> {
self.common.bases_heads()
}
/// Force first computation of `self.undecided`
///
/// After this, `self.undecided.as_ref()` and `.as_mut()` can be
/// unwrapped to get workable immutable or mutable references without
/// any panic.
///
/// This is an imperative call instead of an access with added lazyness
/// to reduce easily the scope of mutable borrow for the caller,
/// compared to undecided(&'a mut self) -> &'a… that would keep it
/// as long as the resulting immutable one.
fn ensure_undecided(&mut self) -> Result<(), GraphError> {
if self.undecided.is_some() {
return Ok(());
}
let tgt = self.target_heads.take().unwrap();
self.undecided =
Some(self.common.missing_ancestors(tgt)?.into_iter().collect());
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::testing::SampleGraph;
/// A PartialDiscovery as for pushing all the heads of `SampleGraph`
fn full_disco() -> PartialDiscovery<SampleGraph> {
PartialDiscovery::new(SampleGraph, vec![10, 11, 12, 13])
}
fn sorted_undecided(
disco: &PartialDiscovery<SampleGraph>,
) -> Vec<Revision> {
let mut as_vec: Vec<Revision> =
disco.undecided.as_ref().unwrap().iter().cloned().collect();
as_vec.sort();
as_vec
}
fn sorted_missing(disco: &PartialDiscovery<SampleGraph>) -> Vec<Revision> {
let mut as_vec: Vec<Revision> =
disco.missing.iter().cloned().collect();
as_vec.sort();
as_vec
}
fn sorted_common_heads(
disco: &PartialDiscovery<SampleGraph>,
) -> Result<Vec<Revision>, GraphError> {
let mut as_vec: Vec<Revision> =
disco.common_heads()?.iter().cloned().collect();
as_vec.sort();
Ok(as_vec)
}
#[test]
fn test_add_common_get_undecided() -> Result<(), GraphError> {
let mut disco = full_disco();
assert_eq!(disco.undecided, None);
assert!(!disco.has_info());
disco.add_common_revisions(vec![11, 12])?;
assert!(disco.has_info());
assert!(!disco.is_complete());
assert!(disco.missing.is_empty());
// add_common_revisions did not trigger a premature computation
// of `undecided`, let's check that and ask for them
assert_eq!(disco.undecided, None);
disco.ensure_undecided()?;
assert_eq!(sorted_undecided(&disco), vec![5, 8, 10, 13]);
Ok(())
}
/// in this test, we pretend that our peer misses exactly (8+10)::
/// and we're comparing all our repo to it (as in a bare push)
#[test]
fn test_discovery() -> Result<(), GraphError> {
let mut disco = full_disco();
disco.add_common_revisions(vec![11, 12])?;
disco.add_missing_revisions(vec![8, 10])?;
assert_eq!(sorted_undecided(&disco), vec![5]);
assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
assert!(!disco.is_complete());
disco.add_common_revisions(vec![5])?;
assert_eq!(sorted_undecided(&disco), vec![]);
assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
assert!(disco.is_complete());
assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]);
Ok(())
}
}

rust/hg-core/src/lib.rs

// Copyright 2018 Georges Racinet <gracinet@anybox.fr> // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
mod ancestors; mod ancestors;
pub mod dagops; pub mod dagops;
pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors}; pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
pub mod testing; // unconditionally built, for use from integration tests pub mod testing; // unconditionally built, for use from integration tests
pub mod discovery;
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///
/// As noted in revlog.c, revision numbers are actually encoded in /// As noted in revlog.c, revision numbers are actually encoded in
/// 4 bytes, and are liberally converted to ints, whence the i32 /// 4 bytes, and are liberally converted to ints, whence the i32
pub type Revision = i32; pub type Revision = i32;