#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum PositionMatch {
Exact,
Coercion,
Generic,
}
impl PositionMatch {
fn weight(self) -> u32 {
match self {
PositionMatch::Exact => 3,
PositionMatch::Coercion => 2,
PositionMatch::Generic => 1,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum DispatchError {
NoMatchingMethod,
AmbiguousMethod(Vec<usize>),
}
pub trait DispatchCandidate {
fn arity(&self) -> usize;
}
pub fn resolve_overload<C, F>(
candidates: &[C],
n_args: usize,
mut position_match: F,
) -> Result<usize, DispatchError>
where
C: DispatchCandidate,
F: FnMut(usize, usize) -> Option<PositionMatch>,
{
let mut viable: Vec<(usize, Vec<PositionMatch>)> = Vec::new();
for (idx, cand) in candidates.iter().enumerate() {
if cand.arity() != n_args {
continue;
}
let mut positions = Vec::with_capacity(n_args);
let mut all_match = true;
for pos in 0..n_args {
match position_match(idx, pos) {
Some(m) => positions.push(m),
None => {
all_match = false;
break;
}
}
}
if all_match {
viable.push((idx, positions));
}
}
match viable.len() {
0 => Err(DispatchError::NoMatchingMethod),
1 => Ok(viable[0].0),
_ => pick_most_specific(&viable),
}
}
fn pick_most_specific(viable: &[(usize, Vec<PositionMatch>)]) -> Result<usize, DispatchError> {
let dominates = |a: &[PositionMatch], b: &[PositionMatch]| -> bool {
debug_assert_eq!(a.len(), b.len());
let mut strictly_better_somewhere = false;
for (pa, pb) in a.iter().zip(b.iter()) {
if pa.weight() < pb.weight() {
return false; }
if pa.weight() > pb.weight() {
strictly_better_somewhere = true;
}
}
strictly_better_somewhere
};
let mut maximal: Vec<usize> = Vec::new();
for (i, (_, pi)) in viable.iter().enumerate() {
let dominated = viable
.iter()
.enumerate()
.any(|(j, (_, pj))| i != j && dominates(pj, pi));
if !dominated {
maximal.push(i);
}
}
match maximal.len() {
1 => Ok(viable[maximal[0]].0),
_ => {
let tied: Vec<usize> = maximal.iter().map(|&i| viable[i].0).collect();
Err(DispatchError::AmbiguousMethod(tied))
}
}
}
#[cfg(test)]
mod tests {
use super::*;
struct Cand {
params: Vec<Param>,
}
#[derive(Clone, PartialEq)]
enum Param {
Concrete(&'static str),
Generic,
}
impl DispatchCandidate for Cand {
fn arity(&self) -> usize {
self.params.len()
}
}
fn matcher<'a>(
cands: &'a [Cand],
args: &'a [&'static str],
) -> impl FnMut(usize, usize) -> Option<PositionMatch> + 'a {
move |ci, pos| {
let p = &cands[ci].params[pos];
let a = args[pos];
match p {
Param::Concrete(name) if *name == a => Some(PositionMatch::Exact),
Param::Concrete(_) => None,
Param::Generic => Some(PositionMatch::Generic),
}
}
}
fn c(params: &[Param]) -> Cand {
Cand {
params: params.to_vec(),
}
}
#[test]
fn selects_i32_add() {
let cands = vec![
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
c(&[Param::Concrete("f64"), Param::Concrete("f64")]),
c(&[Param::Concrete("str"), Param::Concrete("str")]),
];
let args = ["i32", "i32"];
let sel = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap();
assert_eq!(sel, 0);
}
#[test]
fn selects_f64_add() {
let cands = vec![
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
c(&[Param::Concrete("f64"), Param::Concrete("f64")]),
c(&[Param::Concrete("str"), Param::Concrete("str")]),
];
let args = ["f64", "f64"];
let sel = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap();
assert_eq!(sel, 1);
}
#[test]
fn selects_str_add() {
let cands = vec![
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
c(&[Param::Concrete("f64"), Param::Concrete("f64")]),
c(&[Param::Concrete("str"), Param::Concrete("str")]),
];
let args = ["str", "str"];
let sel = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap();
assert_eq!(sel, 2);
}
#[test]
fn dispatches_on_second_arg() {
let cands = vec![
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
c(&[Param::Concrete("i32"), Param::Concrete("f64")]),
];
let sel_ii = resolve_overload(&cands, 2, matcher(&cands, &["i32", "i32"])).unwrap();
assert_eq!(sel_ii, 0);
let sel_if = resolve_overload(&cands, 2, matcher(&cands, &["i32", "f64"])).unwrap();
assert_eq!(sel_if, 1);
}
#[test]
fn concrete_beats_generic() {
let cands = vec![
c(&[Param::Generic, Param::Generic]),
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
];
let args = ["i32", "i32"];
let sel = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap();
assert_eq!(sel, 1); }
#[test]
fn generic_used_when_no_concrete_matches() {
let cands = vec![
c(&[Param::Generic, Param::Generic]),
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
];
let args = ["f64", "f64"];
let sel = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap();
assert_eq!(sel, 0); }
#[test]
fn no_matching_method() {
let cands = vec![
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
c(&[Param::Concrete("f64"), Param::Concrete("f64")]),
];
let args = ["str", "str"];
let err = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap_err();
assert_eq!(err, DispatchError::NoMatchingMethod);
}
#[test]
fn arity_filter_excludes_wrong_length() {
let cands = vec![
c(&[Param::Concrete("i32")]),
c(&[Param::Concrete("i32"), Param::Concrete("i32")]),
];
let sel = resolve_overload(&cands, 1, matcher(&cands, &["i32"])).unwrap();
assert_eq!(sel, 0);
}
#[test]
fn ambiguous_incomparable_pair() {
let cands = vec![
c(&[Param::Concrete("i32"), Param::Generic]),
c(&[Param::Generic, Param::Concrete("i32")]),
];
let args = ["i32", "i32"];
let err = resolve_overload(&cands, 2, matcher(&cands, &args)).unwrap_err();
match err {
DispatchError::AmbiguousMethod(tied) => {
assert_eq!(tied.len(), 2);
assert!(tied.contains(&0) && tied.contains(&1));
}
other => panic!("expected AmbiguousMethod, got {:?}", other),
}
}
#[test]
fn coercion_beats_generic_but_loses_to_exact() {
struct One;
impl DispatchCandidate for One {
fn arity(&self) -> usize {
1
}
}
let cands = vec![One, One, One];
let kinds = [
PositionMatch::Exact,
PositionMatch::Coercion,
PositionMatch::Generic,
];
let sel = resolve_overload(&cands, 1, |ci, _pos| Some(kinds[ci])).unwrap();
assert_eq!(sel, 0);
let cands2 = vec![One, One];
let kinds2 = [PositionMatch::Coercion, PositionMatch::Generic];
let sel2 = resolve_overload(&cands2, 1, |ci, _pos| Some(kinds2[ci])).unwrap();
assert_eq!(sel2, 0);
}
}