#![allow(dead_code)]
use crate::sema::symbol::Known;
use crate::sema::types::parse_type_spelling;
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
pub(crate) enum Match {
Exact,
Promotion,
Conversion,
Unranked,
NotViable,
}
#[derive(Clone, Debug)]
pub(crate) struct Candidate {
pub(crate) parameters: Vec<String>,
pub(crate) variadic: bool,
pub(crate) signature: String,
pub(crate) is_a_template: bool,
pub(crate) declared: Vec<String>,
pub(crate) template_parameters: Vec<String>,
}
impl Candidate {
pub(crate) fn new(parameters: Vec<String>, variadic: bool, signature: String) -> Self {
Self {
parameters,
variadic,
signature,
is_a_template: false,
declared: Vec::new(),
template_parameters: Vec::new(),
}
}
pub(crate) fn into_a_template(mut self) -> Self {
self.is_a_template = true;
self
}
pub(crate) fn with_declaration(
mut self,
declared: Vec<String>,
template_parameters: Vec<String>,
) -> Self {
self.is_a_template = !template_parameters.is_empty();
self.declared = declared;
self.template_parameters = template_parameters;
self
}
fn takes(&self, arguments: usize) -> bool {
self.variadic || arguments <= self.parameters.len()
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum Choice {
One(usize),
Ambiguous,
None,
}
pub(crate) fn choose(argument_types: &[Known<String>], candidates: &[Candidate]) -> Choice {
let viable: Vec<usize> = (0..candidates.len())
.filter(|index| candidates[*index].takes(argument_types.len()))
.filter(|index| {
let candidate = &candidates[*index];
argument_types.iter().enumerate().all(|(at, argument)| {
match candidate.parameters.get(at) {
Some(parameter) => rank(parameter, argument) != Match::NotViable,
None => true,
}
})
})
.collect();
if viable.is_empty() {
return Choice::None;
}
if viable.len() == 1 {
return Choice::One(viable[0]);
}
let ranks = |index: usize| -> Vec<Match> {
let candidate = &candidates[index];
argument_types
.iter()
.enumerate()
.map(|(at, argument)| match candidate.parameters.get(at) {
Some(parameter) => rank(parameter, argument),
None => Match::Exact,
})
.collect()
};
let ranked: Vec<(usize, Vec<Match>)> =
viable.iter().map(|index| (*index, ranks(*index))).collect();
let strictly_better = |mine: &[Match], theirs: &[Match]| -> bool {
better_or_equal(mine, theirs) && !better_or_equal(theirs, mine)
};
let maximal: Vec<usize> = ranked
.iter()
.filter(|(index, mine)| {
!ranked
.iter()
.any(|(other, theirs)| other != index && strictly_better(theirs, mine))
})
.map(|(index, _)| *index)
.collect();
if maximal.len() == 1 {
return Choice::One(maximal[0]);
}
let ordinary: Vec<usize> = maximal
.iter()
.copied()
.filter(|index| !candidates[*index].is_a_template)
.collect();
let maximal = if ordinary.is_empty() {
maximal
} else {
ordinary
};
if maximal.len() > 1 {
let ordinary: Vec<usize> = maximal
.iter()
.copied()
.filter(|mine| {
maximal.iter().all(|other| {
other == mine || !more_specialized(&candidates[*other], &candidates[*mine])
})
})
.collect();
if !ordinary.is_empty() && ordinary.len() < maximal.len() {
return match ordinary.as_slice() {
[only] => Choice::One(*only),
_ => Choice::Ambiguous,
};
}
}
let fewest = maximal
.iter()
.map(|index| candidates[*index].parameters.len())
.min()
.unwrap_or(0);
let leaders: Vec<usize> = maximal
.iter()
.copied()
.filter(|index| candidates[*index].parameters.len() == fewest)
.collect();
match leaders.as_slice() {
[only] => Choice::One(*only),
_ => Choice::Ambiguous,
}
}
fn better_or_equal(mine: &[Match], theirs: &[Match]) -> bool {
mine.iter().zip(theirs).all(|(mine, theirs)| mine <= theirs)
}
fn better(mine: &[Match], theirs: &[Match]) -> bool {
mine.iter().zip(theirs).any(|(mine, theirs)| {
mine < theirs && *mine != Match::Unranked && *theirs != Match::Unranked
})
}
pub(crate) fn rank(parameter: &str, argument: &Known<String>) -> Match {
let argument = match argument {
Known::Yes(argument) => argument,
Known::No => return Match::NotViable,
Known::Unknown(_) => return Match::Unranked,
};
let parameter_shape = the_shape_of(parameter);
let argument_shape = the_shape_of(argument);
if parameter_shape == argument_shape {
return Match::Exact;
}
if is_a_promotion(&argument_shape, ¶meter_shape) {
return Match::Promotion;
}
match parse_type_spelling(argument).convertible_to(&parse_type_spelling(parameter)) {
Known::Yes(()) => Match::Conversion,
Known::No => Match::NotViable,
Known::Unknown(_) => Match::Unranked,
}
}
fn the_shape_of(spelling: &str) -> String {
let mut text = spelling.trim().to_string();
loop {
let trimmed = text.trim();
if let Some(before) = trimmed
.strip_suffix("&&")
.or_else(|| trimmed.strip_suffix('&'))
{
text = before.trim_end().to_string();
} else {
break;
}
}
loop {
let trimmed = text.trim_start();
if let Some(after) = trimmed
.strip_prefix("const ")
.or_else(|| trimmed.strip_prefix("volatile "))
{
text = after.trim_start().to_string();
} else {
break;
}
}
text.split_whitespace().collect::<Vec<_>>().join(" ")
}
fn is_a_promotion(from: &str, to: &str) -> bool {
const NARROW: [&str; 6] = [
"char",
"signed char",
"unsigned char",
"short",
"short int",
"unsigned short",
];
const TO_INT: [&str; 2] = ["int", "unsigned int"];
(NARROW.contains(&from) && TO_INT.contains(&to)) || (from == "float" && to == "double")
}
#[cfg(test)]
mod tests {
use super::*;
fn a_type(spelling: &str) -> Known<String> {
Known::Yes(spelling.to_string())
}
fn candidate(parameters: &[&str]) -> Candidate {
Candidate::new(
parameters
.iter()
.map(|parameter| (*parameter).to_string())
.collect(),
false,
parameters.join(", "),
)
}
#[test]
fn the_integer_overload_is_chosen_for_an_integer_and_the_floating_one_for_a_floating() {
let candidates = vec![candidate(&["int"]), candidate(&["double"])];
assert_eq!(choose(&[a_type("int")], &candidates), Choice::One(0));
assert_eq!(choose(&[a_type("double")], &candidates), Choice::One(1));
}
#[test]
fn a_promotion_beats_a_conversion() {
let candidates = vec![candidate(&["long"]), candidate(&["int"])];
assert_eq!(choose(&[a_type("short")], &candidates), Choice::One(1));
}
#[test]
fn arity_narrows_the_set_before_any_type_is_looked_at() {
let candidates = vec![candidate(&["int"]), candidate(&["int", "int"])];
assert_eq!(choose(&[a_type("int")], &candidates), Choice::One(0));
assert_eq!(
choose(&[a_type("int"), a_type("int")], &candidates),
Choice::One(1)
);
assert_eq!(choose(&[], &candidates), Choice::One(0));
}
#[test]
fn a_parameter_that_writes_const_and_a_reference_is_the_same_type() {
let candidates = vec![candidate(&["const std::string&"]), candidate(&["int"])];
assert_eq!(
choose(&[a_type("std::string")], &candidates),
Choice::One(0),
"`const std::string&` and `std::string` are one type seen two ways"
);
}
#[test]
fn an_argument_with_no_type_at_all_leaves_no_candidate_viable() {
let candidates = vec![candidate(&["int"]), candidate(&["double"])];
assert_eq!(choose(&[Known::No], &candidates), Choice::None);
}
#[test]
fn an_argument_nothing_is_known_about_makes_the_call_ambiguous_rather_than_wrong() {
let candidates = vec![candidate(&["int"]), candidate(&["double"])];
assert_eq!(
choose(&[a_type("std::string")], &candidates),
Choice::Ambiguous
);
}
#[test]
fn two_candidates_that_tie_everywhere_are_ambiguous_and_not_a_choice() {
let candidates = vec![candidate(&["int"]), candidate(&["int"])];
assert_eq!(
choose(&[a_type("int")], &candidates),
Choice::Ambiguous,
"a check must say nothing rather than pick one of two identical candidates"
);
}
#[test]
fn an_unknown_argument_neither_wins_nor_loses_but_cannot_beat_a_known_exact_one() {
let candidates = vec![candidate(&["int"]), candidate(&["double"])];
assert_eq!(
choose(
&[Known::Unknown(
crate::sema::symbol::UnknownReason::DependentName
)],
&candidates
),
Choice::Ambiguous,
"nothing is known about the argument, so nothing ranks these two apart"
);
assert_eq!(
choose(&[a_type("double")], &candidates),
Choice::One(1),
"and a known argument still decides"
);
}
#[test]
fn an_ordinary_function_beats_a_template_that_is_equally_good() {
let candidates = vec![candidate(&["T"]).into_a_template(), candidate(&["int"])];
assert_eq!(
choose(&[a_type("int")], &candidates),
Choice::One(1),
"`f(int)` is what `f(1)` means when `f(T)` is in view too"
);
let both = vec![
candidate(&["T"]).into_a_template(),
candidate(&["T"]).into_a_template(),
];
assert_eq!(choose(&[a_type("int")], &both), Choice::Ambiguous);
}
#[test]
fn a_more_parameterful_candidate_stays_viable_because_defaults_are_not_in_the_spelling() {
let candidates = vec![candidate(&["int"]), candidate(&["int", "int"])];
assert_eq!(
choose(&[a_type("int")], &candidates),
Choice::One(0),
"the one that needs no default wins, but both were viable"
);
}
}
pub(crate) fn a_type_without_its_name(parameter: &str) -> String {
let parameter = parameter.split('=').next().unwrap_or(parameter).trim();
let Some(last) = parameter.split_whitespace().last() else {
return parameter.to_string();
};
if last == parameter {
return parameter.to_string();
}
let is_a_name = last
.chars()
.all(|character| character.is_alphanumeric() || character == '_')
&& last
.chars()
.next()
.is_some_and(|character| character.is_alphabetic() || character == '_');
if is_a_name {
return parameter[..parameter.len() - last.len()]
.trim_end()
.to_string();
}
parameter.to_string()
}
pub fn parameters_in(parameter_list: &str) -> (Vec<String>, bool) {
let inner = parameter_list
.trim()
.trim_start_matches('(')
.trim_end_matches(')');
let mut parameters = Vec::new();
let mut variadic = false;
let mut depth = 0i32;
let mut current = String::new();
let take = |parameter: &str, parameters: &mut Vec<String>, variadic: &mut bool| {
let parameter = parameter.trim();
if parameter.is_empty() {
return;
}
let outside_the_arguments = {
let mut without = String::new();
let mut depth = 0i32;
for character in parameter.chars() {
match character {
'<' => depth += 1,
'>' => depth -= 1,
_ if depth > 0 => continue,
_ => {}
}
without.push(character);
}
without
};
if outside_the_arguments.contains("...") {
*variadic = true;
let element = a_type_without_its_name(&outside_the_arguments.replace("...", ""));
if !element.trim().is_empty() {
parameters.push(element);
}
return;
}
parameters.push(a_type_without_its_name(parameter));
};
for character in inner.chars() {
match character {
'<' | '(' | '[' => depth += 1,
'>' | ')' | ']' => depth -= 1,
',' if depth == 0 => {
take(¤t, &mut parameters, &mut variadic);
current.clear();
continue;
}
_ => {}
}
current.push(character);
}
take(¤t, &mut parameters, &mut variadic);
(parameters, variadic)
}
pub(crate) fn more_specialized(mine: &Candidate, theirs: &Candidate) -> bool {
let deduces = |from: &Candidate, to: &Candidate| -> bool {
from.template_parameters.is_empty()
|| to.template_parameters.is_empty()
|| to.declared.is_empty()
|| from.declared.is_empty()
|| from.declared.len() != to.declared.len()
|| from
.declared
.iter()
.zip(&to.declared)
.all(|(from_spelling, to_spelling)| {
crate::sema::deduction::deduce(
&from.template_parameters,
std::slice::from_ref(from_spelling),
&[crate::Known::Yes(to_spelling.clone())],
)
.is_some()
})
};
let theirs_deduces_into_mine = deduces(theirs, mine);
let mine_deduces_into_theirs = deduces(mine, theirs);
theirs_deduces_into_mine && !mine_deduces_into_theirs
}
#[test]
fn a_template_argument_pack_inside_a_parameter_is_not_the_parameter_pack() {
assert_eq!(
parameters_in("(const format_string<_Types...> _Fmt, _Types&&... _Args)"),
(
vec![
"const format_string<_Types...>".to_string(),
"_Types&&".to_string()
],
true
)
);
assert_eq!(
parameters_in(
"(const locale& _Loc, const wformat_string<_Types...> _Fmt, _Types&&... _Args)"
),
(
vec![
"const locale&".to_string(),
"const wformat_string<_Types...>".to_string(),
"_Types&&".to_string()
],
true
)
);
assert_eq!(
parameters_in("(int a, double b)"),
(vec!["int".to_string(), "double".to_string()], false)
);
assert_eq!(
parameters_in("(const char *format, ...)"),
(vec!["const char *format".to_string()], true),
"a C-style variadic still ends the list: {:?}",
parameters_in("(const char *format, ...)")
);
assert_eq!(
parameters_in("(Args &&... args)"),
(vec!["Args &&".to_string()], true)
);
}
#[test]
fn the_more_specialized_of_two_templates_wins() {
let by_pointer = Candidate::new(vec!["int*".to_string()], false, "take(T*)".to_string())
.with_declaration(vec!["T*".to_string()], vec!["T".to_string()]);
let by_value = Candidate::new(vec!["int*".to_string()], false, "take(T)".to_string())
.with_declaration(vec!["T".to_string()], vec!["T".to_string()]);
assert!(
more_specialized(&by_pointer, &by_value),
"`T*` is more specialized than `T`"
);
assert!(
!more_specialized(&by_value, &by_pointer),
"and the relation is not symmetric"
);
let chosen = choose(
&[crate::Known::Yes("int*".to_string())],
&[by_pointer.clone(), by_value.clone()],
);
assert_eq!(
chosen,
Choice::One(0),
"so the pointer template is the one a call means"
);
assert!(!more_specialized(&by_value, &by_value));
assert_eq!(
choose(
&[crate::Known::Yes("int*".to_string())],
&[by_value.clone(), by_value.clone()]
),
Choice::Ambiguous
);
}