F601 multi-value-repeated-key-literal various issues

[dylwil3]

This is an extension of #12772.

Observed issues

Playground Link

• F601 should only be triggered for Expr's whose leaves are literals of some kind - the following two examples ought to fall under F602 instead.

{(foo, bar): "a", (foo, bar): "b"}

{
    f"{foo}": "a",
    f"{foo}": "b",
}

• As in F601: Repeated int keys not detected with booleans #12772 booleans and numbers that are equal should trigger this rule.

{
    True: "a",
    1: "b",
    1.0: "c",
    1.0
    + 0.0j: "d",  # <-- this may be out of scope depending on the implementation of the fix
    2: "e",
    2.0: "f",
}

• (Maybe a feature request rather than a bug) It would be nice to extend F601 to situations like this, where expression ASTs have literal leaves and internal nodes do not involve a function call

{
    -1: "a",
    -1: "b",
}

{
    1 + 1: "a",
    1 + 1: "b",
}

# but _not_ to situations which require any kind of actual evaluation
{
    1 + 1: "a",
    2: "b",
}

# except maybe this, which appears above as well
# and which is arguably a casting/type promotion
{
    1: "a",
    1.0 + 0.0j: "b",
}

• There is also an issue with the suggested fix for values which are the "same", as there could be side effects, eg

# Suggested fix is unsafe, since we can't know
# which value of iterator was desired
{
    1: next(it),
    1: next(it),
}

• Finally, a minor issue: the name of the rule does not seem quite right, since the linter complains if a key is repeated even if the same value appears.

Potential Solution

I propose that the logic of this check (independently of the implementation) should be as follows:

1. F601 should ignore keys which do not satisfy all of the following:
   • They are expressions that have only literals as leaves
   • They are expressions where no node is a Name (that may be redundant since Name's are terminal?)
2. F601 should consider keys duplicated if the corresponding ComparableExpr's are equal after further replacing all boolean and numeric literals with their complex-valued equivalent (for these purposes, I think "large" integers should be left as is).
3. F601 should not propose a fix if the "unique" value found has possible side effects - for example, we could just never propose a fix if the value found involves a function call.
4. Change the name of the rule to repeated-key-literal (and similarly for F602).

[dylwil3]

By the way, I'm happy to work on this I just wanna pin down the "assignment" first.

[MichaReiser]

F601 should only be triggered for Expr's whose leaves are literals of some kind - the following two examples ought to fall under F602 instead.

Can you tell me a bit more about the reasons why not:

{(foo, bar): "a", (foo, bar): "b"}

Is it because the keys are tuples or because the tuples contain names?

{
    f"{foo}": "a",
    f"{foo}": "b",
}

Is it because the f-strings have replacements? What about f-strings without replacements?

[dylwil3]

Sure - I may be misinterpreting the rule descriptions, but I thought that F602 was meant to catch repeated keys that involve names, whereas F601 was restricted to expressions involving literals alone. It just so happens that, in the implementation of F601/F602, keys which are tuples or f-strings are always treated by F601:

ruff/crates/ruff_linter/src/rules/pyflakes/rules/repeated_keys.rs

Lines 156 to 160 in 9b73532

	| Expr::Tuple(_)
	| Expr::FString(_) => {
	if checker.enabled(Rule::MultiValueRepeatedKeyLiteral) {
	let mut diagnostic = Diagnostic::new(
	MultiValueRepeatedKeyLiteral {

[MichaReiser]

Ah yeah, that seems incorrect. I think it should only handle constant-tuples and fstrings.

[MichaReiser]

 {
     -1: "a",
     -1: "b",
 }
 
 {
     1 + 1: "a",
     1 + 1: "b",
 }
 
 # but _not_ to situations which require any kind of actual evaluation
 {
     1 + 1: "a",
     2: "b",
 }
 
 # except maybe this, which appears above as well
 # and which is arguably a casting/type promotion
 {
     1: "a",
     1.0 + 0.0j: "b",
 }

IMO, explaining why the rule detects 1 + 1 and 1 + 1 but not 2 and 1 + 1 seems more difficult than just implementing the rule with some basic static-evaluation. Especially because the rule is about detecting identical literals (although it might need to be renamed because static evaluation goes slightly beyond).

[dylwil3]

I would be okay with that, in theory. It's not clear to me how difficult/expensive it is to perform this evaluation. Philosophically, this might also blur the line between "linter" and "type checker" (or even "compiler"), but that's also fine.

[MichaReiser]

Yeah. I also wonder if we already have something like that. @charliermarsh might now?

[MichaReiser]

This might be the closest that ruff has today (not very helpful in this context)

ruff/crates/ruff_python_ast/src/helpers.rs

Lines 1103 to 1218 in aa0db33

	#[derive(Copy, Clone, Debug, PartialEq, is_macro::Is)]
	pub enum Truthiness {
	/// The expression is `True`.
	True,
	/// The expression is `False`.
	False,
	/// The expression evaluates to a `False`-like value (e.g., `None`, `0`, `[]`, `""`).
	Falsey,
	/// The expression evaluates to a `True`-like value (e.g., `1`, `"foo"`).
	Truthy,
	/// The expression evaluates to an unknown value (e.g., a variable `x` of unknown type).
	Unknown,
	}
	impl Truthiness {
	/// Return the truthiness of an expression.
	pub fn from_expr<F>(expr: &Expr, is_builtin: F) -> Self
	where
	F: Fn(&str) -> bool,
	{
	match expr {
	Expr::StringLiteral(ast::ExprStringLiteral { value, .. }) => {
	if value.is_empty() {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	Expr::BytesLiteral(ast::ExprBytesLiteral { value, .. }) => {
	if value.is_empty() {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	Expr::NumberLiteral(ast::ExprNumberLiteral { value, .. }) => match value {
	ast::Number::Int(int) => {
	if *int == 0 {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	ast::Number::Float(float) => {
	if *float == 0.0 {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	ast::Number::Complex { real, imag, .. } => {
	if *real == 0.0 && *imag == 0.0 {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	},
	Expr::BooleanLiteral(ast::ExprBooleanLiteral { value, .. }) => {
	if *value {
	Self::True
	} else {
	Self::False
	}
	}
	Expr::NoneLiteral(_) => Self::Falsey,
	Expr::EllipsisLiteral(_) => Self::Truthy,
	Expr::FString(f_string) => {
	if is_empty_f_string(f_string) {
	Self::Falsey
	} else if is_non_empty_f_string(f_string) {
	Self::Truthy
	} else {
	Self::Unknown
	}
	}
	Expr::List(ast::ExprList { elts, .. })
	| Expr::Set(ast::ExprSet { elts, .. })
	| Expr::Tuple(ast::ExprTuple { elts, .. }) => {
	if elts.is_empty() {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	Expr::Dict(dict) => {
	if dict.is_empty() {
	Self::Falsey
	} else {
	Self::Truthy
	}
	}
	Expr::Call(ast::ExprCall {
	func, arguments, ..
	}) => {
	if let Expr::Name(ast::ExprName { id, .. }) = func.as_ref() {
	if is_iterable_initializer(id.as_str(), |id| is_builtin(id)) {
	if arguments.is_empty() {
	// Ex) `list()`
	Self::Falsey
	} else if arguments.args.len() == 1 && arguments.keywords.is_empty() {
	// Ex) `list([1, 2, 3])`
	Self::from_expr(&arguments.args[0], is_builtin)
	} else {
	Self::Unknown
	}
	} else {
	Self::Unknown
	}
	} else {
	Self::Unknown
	}
	}
	_ => Self::Unknown,
	}
	}

[MichaReiser]

F601 should consider keys duplicated if the corresponding ComparableExpr's are equal after further replacing all boolean and numeric literals with their complex-valued equivalent (for these purposes, I think "large" integers should be left as is).

I overall agree with this except that allocating ad-hoc expressions is somewhat expensive. Considering that the rule only has to deal with a very limited set of expressions: would it make sense to create an ad-hoc comparison instead?

[dylwil3]

Sorry I was being a little unclear - this sentence was meant to give a criterion for an equivalence relation, but not specify how we implement checking equivalence. So I agree that two sorts of implementations would be:

1. Building a function cast_nums(x: ComparableExp) -> ComparableExpr and checking cast_nums(x) = cast_nums(y).
2. Defining the new relation $\simeq$ directly as a function is_iso: ((x,y):tuple[ComparableExpr,ComparableExpr]) -> bool

In fact, the implementation of the rule involves the creation of a hash set, so instead of (2) one probably needs a custom hash function h which satisfies $x \simeq y \Rightarrow h(x) = h(y)$. That sounds like it would be more performant, I just don't know how to do that at the moment 😄 But I'd be happy to learn how, or learn that there is an easier way!

Regarding the issue of allocation: The implementation of the rule already allocates a ComparableExpr - if this "casting" function that replaces bools and consumes it instead of borrowing it, would that resolve your concern? Sorry, I'm still developing an intuition for what's expensive and not here.

[MichaReiser]

Yeah I think a HashMap/HashSet makes sense here. You can get a custom hash function by creating a newtype-wrapper: A struct that wraps an inner type and you can implement Eq, Hash, etc. for it

[dylwil3]

Ok I'll give it a shot- sounds fun! And thanks for your help!