Prototyping merge algorithms

[foresterre]

Introduction

• Given two StableReleases instances (similar for other channels)
• Given a merge function merge: (StableReleases<C1>, StableReleases<C2>, resolutionfn) -> StableReleases<C3>

Questions:

• Is this the right signature?
• Should the signature be separate from the struct, or a method or trait impl on the struct?
• What should resolutionfn look like? Or: how do we resolve conflicts?
• What should the merge algorithm look like?

Discussion

Is this the right signature?

• The C{n} in the signature are for contextual data (types), where a source may provide additional data. The merged version of this contextual data is C3. Conceptually f: merge(C1, C2) -> C3.
• Tbd.

Should the signature be separate from the struct, or a method or trait impl on the struct?

Ideas:

struct MergeFn {
 // ...
}

impl<C1, C2, C3> Merge<C1, C2, C3> for MergeFn {
  fn merge(this: StableReleases<C1>, other: StableReleases<C2>, resolutionfn: impl Fn(Candiate<C1>, Candidate<C2>) -> MergeResult<C3>) -> StableReleases<C3>;
}

What should resolutionfn look like? Or: how do we resolve conflicts?

• Tbd.

Some ideas:

trait ConflictResolution {
  fn only_left<C1, C3>(&self, lhs: &Candidate<C1>) -> Candidate<C3>;

  fn only_right<C2, C3>(&self, rhs: &Candidate<C2>) -> Candidate<C3>;

  fn both<C2, C3>(&self, lhs: &Candidate<C1>, rhs: &Candidate<C2>) -> Candidate<C3>;
}

trait ConflictResolution {
  fn merge<C1, C2, C3>(&self, lhs: Option<Candidate<C1>>, rhs: Option<Candidate<C1>>) -> Candidate<C3>;
}

• Disadvantage: neither isn't really a thing, but this assumes that merge(None, None) must also be handled.
• Improve the core datastructures and traits, and make the {Stable,Beta,Nightly}Releases structs merge-able (0.1) #273
  • PR currently does this, but it felt perhaps needlessly complex; or maybe it is actually just right because complexity needs to put some place
  • PR currently does it inline without the trait

What should the merge algorithm look like?

First look at the simple idea

• Improve the core datastructures and traits, and make the {Stable,Beta,Nightly}Releases structs merge-able (0.1) #273 tries to do a single pass and copy, but also clones a few times in the resolutionfn; we'll see where we end up
• The simple idea copies more than necessary, but perhaps we should aim for simple first and improve on it later; in any case, to understand what the merge should do:

fn merge(lhs: StableReleases<C1>, rhs: StableReleases<C2>, resolutionfn: F) -> StableReleases<C3> {

  let lhs: HashSet<Stable> = lhs.toSet(); // key is the RustVersion for Stable
  let rhs: HashSet<Stable> = rhs.toSet(); 
 
  let out = HashSet::<Stable>::new();

  // BOTH

  let both = lhs.intersect(&rhs);

  for release in both {
    let l = lhs.get(&release).unwrap();
    let r = rhs.get(&release).unwrap();
    
    // Should we also allow resolutionfn to return None, i.e. don't add anything?
    let rel = resolutionfn(l, r);  
    
    out.add(rel);
  }

  // ONLY LEFT

  let only_left = lhs.difference(&rhs);

  for release in only_left {
    let l = lhs.get(&release).unwrap();
    
    // still need to transform the context from C1 into C3
    let rel = resolutionfn(l);

    out.add(rel);
  }

  // ONLY RIGHT

  let only_right = rhs.difference(&lhs);

  for release in only_right {
    let r = rhs.get(&release).unwrap();
    
    // still need to transform the context from C2 into C3
    let rel = resolutionfn(r);

    out.add(rel);
  }

  StableReleases::from(out)
}

---

Addendum: Should we really bother with Contexts C in the first new version? We can simply add a context version of the structs later on?