Background
Recall that Swift allows mutually-recursive local functions. This lets you write algorithms like this:
func foo() {
func a(_ x: Int) -> Int {
if (x % 2 == 0)
b(x / 2)
else
a(x - 1)
}
func b(_ x: Int) -> Int {
if (x % 2 == 0)
a(x / 2)
else
b(x - 1)
}
a(100)
}
Note that the body of a references b. Normally, this kind of forward reference is not allowed in local scopes. For example this is an error:
func f() {
print(x)
let x = 10
}
Here is another example:
struct S {
let x = 123
func f() {
print(x) // refers to 'S.x' as a member of 'self'
let x = 321
print(x * x) // refers to the local 'x' above
}
}
So clearly forward references are not allowed most of the time, but the rules need to be relaxed somewhat to make local functions work properly. If we want to formalize the current name lookup rules, they look something like this:
-
First, look for all visible local definitions with the given name that precede the current source location in the buffer. If one was found, we're done.
-
If there are no local definitions with the given name that precede the current source location, and we're inside a local function or closure scope, look through all local definitions in the parent scope, even if their source location comes after the local function or closure.
-
If this doesn't resolve the name, look for an outer type definition, and perform a member lookup on
selfto resolve it as an instance member.
Proposed change
The second rule is needed to make mutually-recursive local functions to work, but it is too general, and it can also find forward references to non-functions as well. As you will see below, this causes some issues.
I'd like to tweak the rules slightly, so that rule 2 now reads:
- If there are no local definitions with the given name that precede the current source location, look through all local function definitions in the current scope, even if their source location comes after the use site.
That is, we relax the rule to allow forward references to local functions from the top level of a function body, but we tighten the rule to completely ban forward references to let bindings.
Examples
Valid -> invalid example
For example, Swift 5.3 accepts this:
func f() {
func local() {
print(x)
}
let x = 123
local()
}
We would reject this under the new rule, because the body of local cannot see x under the new rule 2.
Remains valid but has behavior change example
Here is an example where Swift 5.3 accepts the code, but the behavior would change under the new rule:
struct S {
let x = 123
func f() {
func local() {
print(x)
}
let x = 321
}
}
In Swift 5.3, the above prints 321 because when we do the lookup into the parent scope of local(), we find the local let x (rule 2) before we find the let x as a type member (rule 3).
Under the new rule, this would print 123, because lookup would only find the first let x that precedes the use location.
Remains valid, no behavior change example
Here is an example where the behavior remains the same in Swift 5.3 and the new proposed rule:
func outer() {
let x = 123
func middle() {
func local() {
print(x)
}
let x = 321
}
}
Here, the outermost let x is local, so rule 1 kicks in, so in print(x) we find the let x defined in outer(), and not the let x defined in middle(), so this code prints 123 and not 321.
Invalid -> valid example
Here is an example that Swift 5.3 rejects, and the new rule would accept:
func f() {
first()
func first() {}
}
Swift 5.3 rejects the forward reference because the old rule 2 only applies when you're already inside a local function or closure scope. The new rule 2 allows it to be found, however.
Invalid -> valid example
Swift 5.3 also rejects this example:
struct S {
let x = 123
func outer() {
let closure = { print(x) }
let x = 321
}
}
In the above code, print(x) appears inside a closure body, so rule 2 resolves the x to the local binding let x inside outer(). This code type checks! However, SIL capture analysis rejects it, because the closure attempts to capture x before its definition.
Under the new rule, the above code will both type check and pass SIL diagnostics correctly, because the closure references self.x, not the local let x.
Aside about capture diagnostics
Even with the new rule though, we still need to do the SIL capture analysis. For example, you can forward reference a function, which references a capture not yet in scope:
func f() {
func a() {
b() // valid -- rule 2
}
let x = 123
func b() {
print(x) // valid -- rule 1
}
b() // valid -- rule 1
}
Motivation
Today, we have two name lookup implementations in the compiler. Parse-time lookup resolves names that have already been parsed (precede the use location in the input source). Parse-time lookup only knows about local bindings, not members of types or top-level declarations.
Then later, the expression type checker performs a "pre-checking" pass to resolve any remaining names. This resolves members of types, but also this is where rule 2 allowing forward references from inside function bodies is implemented.
I'm currently beefing up the name lookup used by pre-checking ("ASTScope") to the point where it can replace parse-time lookup. While it would be possible to faithfully model the current behavior, it would make a lot more sense both from the standpoint of language semantics and implementation simplicity to tweak the rules as I suggested at the beginning of this pitch.
While the list of examples that now behave differently above looks a bit scary, I suspect in practice nobody is really relying on these edge cases, and mutually recursive local functions themselves are rather rare (but probably not rare enough that we can consider removing them. I'd much rather tighten up the semantics to make them more reasonable).
I ran source compatibility testing and didn't find any code that relies on the old behavior. The validation test suite has some examples, all reduced from crashers (the SIL capture analysis' added pretty recently, and we used to crash in the cases it now rejects).
Does anyone have thoughts on this?