WIP: defer walking function bodies to end-of-scope in SemanticIndexBuilder

This is intended to fix the one failing test from the previous commit.
And it actually does fix it! But it also causes a huge number of other
tests to fail. The minimized repro seems to be this:

```
$ cat test.py
class Foo:
    pass
foo = Foo()
$ ty check test.py
error[panic]: Panicked at crates/ty_python_semantic/src/types.rs:156:38 when checking `/tmp/test.py`: `Failed to retrieve the inferred type for an `ast::Expr` node passed to `TypeInference::expression_type()`. The `TypeInferenceBuilder` should infer and store types for all `ast::Expr` nodes in any `TypeInference` region it analyzes.`
info: This indicates a bug in ty.
info: If you could open an issue at https://github.com/astral-sh/ty/issues/new?title=%5Bpanic%5D, we'd be very appreciative!
info: Platform: linux x86_64
info: Args: ["/home/jacko/astral/ruff/target-mold/debug/ty", "check", "test.py"]
info: run with `RUST_BACKTRACE=1` environment variable to show the full backtrace information
info: query stacktrace:
   0: FunctionType < 'db >::signature_(Id(5007))
             at crates/ty_python_semantic/src/types/function.rs:595
             cycle heads: infer_scope_types(Id(c62)) -> IterationCount(0), FunctionType < 'db >::signature_(Id(5007)) -> IterationCount(0), FunctionType < 'db >::signature_(Id(5000)) -> IterationCount(0)
   1: infer_expression_types(Id(1463))
             at crates/ty_python_semantic/src/types/infer.rs:235
   2: infer_definition_types(Id(11ab))
             at crates/ty_python_semantic/src/types/infer.rs:159
   3: infer_scope_types(Id(c62))
             at crates/ty_python_semantic/src/types/infer.rs:130
             cycle heads: infer_scope_types(Id(c62)) -> IterationCount(0)
   4: FunctionType < 'db >::signature_(Id(5000))
             at crates/ty_python_semantic/src/types/function.rs:595
   5: infer_expression_types(Id(1400))
             at crates/ty_python_semantic/src/types/infer.rs:235
   6: infer_definition_types(Id(1001))
             at crates/ty_python_semantic/src/types/infer.rs:159
   7: infer_scope_types(Id(c00))
             at crates/ty_python_semantic/src/types/infer.rs:130
   8: check_file_impl(Id(800))
             at crates/ty_project/src/lib.rs:474
```

crates/ruff_linter/src/checkers/ast/mod.rs

@@ -670,7 +670,12 @@ impl SemanticSyntaxContext for Checker<'_> {
             | SemanticSyntaxErrorKind::InvalidStarExpression
             | SemanticSyntaxErrorKind::AsyncComprehensionInSyncComprehension(_)
             | SemanticSyntaxErrorKind::DuplicateParameter(_)
-            | SemanticSyntaxErrorKind::NonlocalDeclarationAtModuleLevel => {
+            | SemanticSyntaxErrorKind::NonlocalDeclarationAtModuleLevel
+            | SemanticSyntaxErrorKind::LoadBeforeNonlocalDeclaration { .. }
+            | SemanticSyntaxErrorKind::NonlocalAndGlobal(_)
+            | SemanticSyntaxErrorKind::AnnotatedGlobal(_)
+            | SemanticSyntaxErrorKind::AnnotatedNonlocal(_)
+            | SemanticSyntaxErrorKind::InvalidNonlocal(_) => {
                 self.semantic_errors.borrow_mut().push(error);
             }
         }

crates/ruff_python_parser/src/semantic_errors.rs

@@ -952,6 +952,9 @@ impl Display for SemanticSyntaxError {
             SemanticSyntaxErrorKind::LoadBeforeGlobalDeclaration { name, start: _ } => {
                 write!(f, "name `{name}` is used prior to global declaration")
             }
+            SemanticSyntaxErrorKind::LoadBeforeNonlocalDeclaration { name, start: _ } => {
+                write!(f, "name `{name}` is used prior to nonlocal declaration")
+            }
             SemanticSyntaxErrorKind::InvalidStarExpression => {
                 f.write_str("Starred expression cannot be used here")
             }
@@ -977,6 +980,18 @@ impl Display for SemanticSyntaxError {
             SemanticSyntaxErrorKind::NonlocalDeclarationAtModuleLevel => {
                 write!(f, "nonlocal declaration not allowed at module level")
             }
+            SemanticSyntaxErrorKind::NonlocalAndGlobal(name) => {
+                write!(f, "name `{name}` is nonlocal and global")
+            }
+            SemanticSyntaxErrorKind::AnnotatedGlobal(name) => {
+                write!(f, "annotated name `{name}` can't be global")
+            }
+            SemanticSyntaxErrorKind::AnnotatedNonlocal(name) => {
+                write!(f, "annotated name `{name}` can't be nonlocal")
+            }
+            SemanticSyntaxErrorKind::InvalidNonlocal(name) => {
+                write!(f, "no binding for nonlocal `{name}` found")
+            }
         }
     }
 }
@@ -1207,6 +1222,24 @@ pub enum SemanticSyntaxErrorKind {
     /// [#111123]: https://github.com/python/cpython/issues/111123
     LoadBeforeGlobalDeclaration { name: String, start: TextSize },
 
+    /// Represents the use of a `nonlocal` variable before its `nonlocal` declaration.
+    ///
+    /// ## Examples
+    ///
+    /// ```python
+    /// def f():
+    ///     counter = 0
+    ///     def increment():
+    ///         print(f"Adding 1 to {counter}")
+    ///         nonlocal counter  # SyntaxError: name 'counter' is used prior to nonlocal declaration
+    ///         counter += 1
+    /// ```
+    ///
+    /// ## Known Issues
+    ///
+    /// See [`LoadBeforeGlobalDeclaration`][Self::LoadBeforeGlobalDeclaration].
+    LoadBeforeNonlocalDeclaration { name: String, start: TextSize },
+
     /// Represents the use of a starred expression in an invalid location, such as a `return` or
     /// `yield` statement.
     ///
@@ -1307,6 +1340,41 @@ pub enum SemanticSyntaxErrorKind {
 
     /// Represents a nonlocal declaration at module level
     NonlocalDeclarationAtModuleLevel,
+
+    /// Represents the same variable declared as both nonlocal and global
+    NonlocalAndGlobal(String),
+
+    /// Represents a type annotation on a variable that's been declared global
+    AnnotatedGlobal(String),
+
+    /// Represents a type annotation on a variable that's been declared nonlocal
+    AnnotatedNonlocal(String),
+
+    /// Represents a nonlocal declaration with no definition in an enclosing scope
+    ///
+    /// ## Examples
+    ///
+    /// ```python
+    /// def f():
+    ///     nonlocal x  # error
+    ///
+    /// # Global variables don't count.
+    /// x = 1
+    /// def f():
+    ///     nonlocal x  # error
+    ///
+    /// def f():
+    ///     x = 1
+    ///     def g():
+    ///         nonlocal x  # allowed
+    ///
+    /// # The definition can come later.
+    /// def f():
+    ///     def g():
+    ///         nonlocal x  # allowed
+    ///     x = 1
+    /// ```
+    InvalidNonlocal(String),
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, get_size2::GetSize)]

crates/ty_python_semantic/resources/mdtest/import/star.md

@@ -1304,7 +1304,7 @@ scope of the name that was declared `global`, can add a symbol to the global nam
 def f():
     global g, h
 
-    g: bool = True
+    g = True
 
 f()
 ```

crates/ty_python_semantic/resources/mdtest/scopes/global.md

@@ -83,7 +83,7 @@ def f():
     x = 1
     def g() -> None:
         nonlocal x
-        global x  # TODO: error: [invalid-syntax] "name 'x' is nonlocal and global"
+        global x  # error: [invalid-syntax] "name `x` is nonlocal and global"
         x = None
 ```
 
@@ -209,5 +209,18 @@ x: int = 1
 
 def f():
     global x
-    x: str = "foo"  # TODO: error: [invalid-syntax] "annotated name 'x' can't be global"
+    x: str = "foo"  # error: [invalid-syntax] "annotated name `x` can't be global"
+```
+
+## Global declarations affect the inferred type of the binding
+
+Even if the `global` declaration isn't used in an assignment, we conservatively assume it could be:
+
+```py
+x = 1
+
+def f():
+    global x
+
+# TODO: reveal_type(x)  # revealed: Unknown | Literal["1"]
 ```

crates/ty_python_semantic/resources/mdtest/scopes/nonlocal.md

@@ -43,3 +43,321 @@ def f():
         def h():
             reveal_type(x)  # revealed: Unknown | Literal[1]
 ```
+
+## The `nonlocal` keyword
+
+Without the `nonlocal` keyword, bindings in an inner scope shadow variables of the same name in
+enclosing scopes. This example isn't a type error, because the inner `x` shadows the outer one:
+
+```py
+def f():
+    x: int = 1
+    def g():
+        x = "hello"  # allowed
+```
+
+With `nonlocal` it is a type error, because `x` refers to the same place in both scopes:
+
+```py
+def f():
+    x: int = 1
+    def g():
+        nonlocal x
+        x = "hello"  # error: [invalid-assignment] "Object of type `Literal["hello"]` is not assignable to `int`"
+```
+
+## Local variable bindings "look ahead" to any assignment in the current scope
+
+The binding `x = 2` in `g` causes the earlier read of `x` to refer to `g`'s not-yet-initialized
+binding, rather than to `x = 1` in `f`'s scope:
+
+```py
+def f():
+    x = 1
+    def g():
+        if x == 1:  # error: [unresolved-reference] "Name `x` used when not defined"
+            x = 2
+```
+
+The `nonlocal` keyword makes this example legal (and makes the assignment `x = 2` affect the outer
+scope):
+
+```py
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        if x == 1:
+            x = 2
+```
+
+For the same reason, using the `+=` operator in an inner scope is an error without `nonlocal`
+(unless you shadow the outer variable first):
+
+```py
+def f():
+    x = 1
+    def g():
+        x += 1  # error: [unresolved-reference] "Name `x` used when not defined"
+
+def f():
+    x = 1
+    def g():
+        x = 1
+        x += 1  # allowed, but doesn't affect the outer scope
+
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        x += 1  # allowed, and affects the outer scope
+```
+
+## `nonlocal` declarations must match an outer binding
+
+`nonlocal x` isn't allowed when there's no binding for `x` in an enclosing scope:
+
+```py
+def f():
+    def g():
+        nonlocal x  # error: [invalid-syntax] "no binding for nonlocal `x` found"
+
+def f():
+    x = 1
+    def g():
+        nonlocal x, y  # error: [invalid-syntax] "no binding for nonlocal `y` found"
+```
+
+A global `x` doesn't work. The target must be in a function-like scope:
+
+```py
+x = 1
+
+def f():
+    def g():
+        nonlocal x  # error: [invalid-syntax] "no binding for nonlocal `x` found"
+
+def f():
+    global x
+    def g():
+        nonlocal x  # error: [invalid-syntax] "no binding for nonlocal `x` found"
+```
+
+A class-scoped `x` also doesn't work:
+
+```py
+class Foo:
+    x = 1
+    @staticmethod
+    def f():
+        nonlocal x  # error: [invalid-syntax] "no binding for nonlocal `x` found"
+```
+
+However, class-scoped bindings don't break the `nonlocal` chain the way `global` declarations do:
+
+```py
+def f():
+    x: int = 1
+
+    class Foo:
+        x: str = "hello"
+
+        @staticmethod
+        def g():
+            # Skips the class scope and reaches the outer function scope.
+            nonlocal x
+            x = 2  # allowed
+            x = "goodbye"  # error: [invalid-assignment]
+```
+
+## `nonlocal` uses the closest binding
+
+```py
+def f():
+    x = 1
+    def g():
+        x = 2
+        def h():
+            nonlocal x
+            reveal_type(x)  # revealed: Unknown | Literal[2]
+```
+
+## `nonlocal` "chaining"
+
+Multiple `nonlocal` statements can "chain" through nested scopes:
+
+```py
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        def h():
+            nonlocal x
+            reveal_type(x)  # revealed: Unknown | Literal[1]
+```
+
+And the `nonlocal` chain can skip over a scope that doesn't bind the variable:
+
+```py
+def f1():
+    x = 1
+    def f2():
+        nonlocal x
+        def f3():
+            # No binding; this scope gets skipped.
+            def f4():
+                nonlocal x
+                reveal_type(x)  # revealed: Unknown | Literal[1]
+```
+
+But a `global` statement breaks the chain:
+
+```py
+def f():
+    x = 1
+    def g():
+        global x
+        def h():
+            nonlocal x  # error: [invalid-syntax] "no binding for nonlocal `x` found"
+```
+
+## `nonlocal` bindings respect declared types from the defining scope, even without a binding
+
+```py
+def f():
+    x: int
+    def g():
+        nonlocal x
+        x = "string"  # error: [invalid-assignment] "Object of type `Literal["string"]` is not assignable to `int`"
+```
+
+## A complicated mixture of `nonlocal` chaining, empty scopes, class scopes, and the `global` keyword
+
+```py
+def f1():
+    # The original bindings of `x`, `y`, and `z` with type declarations.
+    x: int = 1
+    y: int = 2
+    z: int = 3
+
+    def f2():
+        # This scope doesn't touch `x`, `y`, or `z` at all.
+
+        class Foo:
+            # This class scope is totally ignored.
+            x: str = "a"
+            y: str = "b"
+            z: str = "c"
+
+            @staticmethod
+            def f3():
+                # This scope declares `x` nonlocal and `y` as global, and it shadows `z` without
+                # giving it a type declaration.
+                nonlocal x
+                x = 4
+                y = 5
+                global z
+                z = 6
+
+                def f4():
+                    # This scope sees `x` from `f1` and `y` from `f3`. It *can't* declare `z`
+                    # nonlocal, because of the global statement above, but it *can* load `z` as a
+                    # "free" variable, in which case it sees the global value.
+                    nonlocal x, y, z  # error: [invalid-syntax] "no binding for nonlocal `z` found"
+                    x = "string"  # error: [invalid-assignment]
+                    y = "string"  # allowed, because `f3`'s `y` is untyped
+                    reveal_type(z)  # revealed: Unknown | Literal[6]
+```
+
+## TODO: `nonlocal` affects the inferred type in the outer scope
+
+Without `nonlocal`, `g` can't write to `x`, and the inferred type of `x` in `f`'s scope isn't
+affected by `g`:
+
+```py
+def f():
+    x = 1
+    def g():
+        reveal_type(x)  # revealed: Unknown | Literal[1]
+    reveal_type(x)  # revealed: Literal[1]
+```
+
+But with `nonlocal`, `g` could write to `x`, and that affects its inferred type in `f`. That's true
+regardless of whether `g` actually writes to `x`. With a write:
+
+```py
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        reveal_type(x)  # revealed: Unknown | Literal[1]
+        x += 1
+        reveal_type(x)  # revealed: Unknown | Literal[2]
+    # TODO: should be `Unknown | Literal[1]`
+    reveal_type(x)  # revealed: Literal[1]
+```
+
+Without a write:
+
+```py
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        reveal_type(x)  # revealed: Unknown | Literal[1]
+    # TODO: should be `Unknown | Literal[1]`
+    reveal_type(x)  # revealed: Literal[1]
+```
+
+## Annotating a `nonlocal` binding is a syntax error
+
+```py
+def f():
+    x: int = 1
+    def g():
+        nonlocal x
+        x: str = "foo"  # error: [invalid-syntax] "annotated name `x` can't be nonlocal"
+```
+
+## Use before `nonlocal`
+
+Using a name prior to its `nonlocal` declaration in the same scope is a syntax error:
+
+```py
+def f():
+    x = 1
+    def g():
+        x = 2
+        nonlocal x  # error: [invalid-syntax] "name `x` is used prior to nonlocal declaration"
+```
+
+This is true even if there are multiple `nonlocal` declarations of the same variable, as long as any
+of them come after the usage:
+
+```py
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        x = 2
+        nonlocal x  # error: [invalid-syntax] "name `x` is used prior to nonlocal declaration"
+
+def f():
+    x = 1
+    def g():
+        nonlocal x
+        nonlocal x
+        x = 2  # allowed
+```
+
+## `nonlocal` before outer initialization
+
+`nonlocal x` works even if `x` isn't bound in the enclosing scope until afterwards:
+
+```py
+def f():
+    def g():
+        # This is allowed, because of the subsequent definition of `x`.
+        nonlocal x
+    x = 1
+```

crates/ty_python_semantic/resources/mdtest/type_qualifiers/final.md

@@ -147,8 +147,7 @@ def nonlocal_use():
     X: Final[int] = 1
     def inner():
         nonlocal X
-        # TODO: this should be an error
-        X = 2
+        X = 2  # error: [invalid-assignment] "Reassignment of `Final` symbol `X` is not allowed: Reassignment of `Final` symbol"
 ```
 
 `main.py`:

crates/ty_python_semantic/src/place.rs

@@ -1421,7 +1421,7 @@ impl RequiresExplicitReExport {
 /// ```py
 /// def _():
 ///     x = 1
-///     
+///
 ///     x = 2
 ///
 ///     if flag():

crates/ty_python_semantic/src/semantic_index.rs

@@ -217,9 +217,6 @@ pub(crate) struct SemanticIndex<'db> {
     /// Map from the file-local [`FileScopeId`] to the salsa-ingredient [`ScopeId`].
     scope_ids_by_scope: IndexVec<FileScopeId, ScopeId<'db>>,
 
-    /// Map from the file-local [`FileScopeId`] to the set of explicit-global symbols it contains.
-    globals_by_scope: FxHashMap<FileScopeId, FxHashSet<ScopedPlaceId>>,
-
     /// Use-def map for each scope in this file.
     use_def_maps: IndexVec<FileScopeId, ArcUseDefMap<'db>>,
 
@@ -308,9 +305,19 @@ impl<'db> SemanticIndex<'db> {
         symbol: ScopedPlaceId,
         scope: FileScopeId,
     ) -> bool {
-        self.globals_by_scope
-            .get(&scope)
-            .is_some_and(|globals| globals.contains(&symbol))
+        self.place_table(scope)
+            .place_expr(symbol)
+            .is_marked_global()
+    }
+
+    pub(crate) fn symbol_is_nonlocal_in_scope(
+        &self,
+        symbol: ScopedPlaceId,
+        scope: FileScopeId,
+    ) -> bool {
+        self.place_table(scope)
+            .place_expr(symbol)
+            .is_marked_nonlocal()
     }
 
     /// Returns the id of the parent scope.

crates/ty_python_semantic/src/semantic_index/builder.rs

@@ -83,6 +83,8 @@ pub(super) struct SemanticIndexBuilder<'db, 'ast> {
     current_match_case: Option<CurrentMatchCase<'ast>>,
     /// The name of the first function parameter of the innermost function that we're currently visiting.
     current_first_parameter_name: Option<&'ast str>,
+    /// Functions defined in the current scope. We walk their bodies at the end of the scope.
+    deferred_function_bodies: Vec<&'ast ast::StmtFunctionDef>,
 
     /// Per-scope contexts regarding nested `try`/`except` statements
     try_node_context_stack_manager: TryNodeContextStackManager,
@@ -103,7 +105,6 @@ pub(super) struct SemanticIndexBuilder<'db, 'ast> {
     use_def_maps: IndexVec<FileScopeId, UseDefMapBuilder<'db>>,
     scopes_by_node: FxHashMap<NodeWithScopeKey, FileScopeId>,
     scopes_by_expression: FxHashMap<ExpressionNodeKey, FileScopeId>,
-    globals_by_scope: FxHashMap<FileScopeId, FxHashSet<ScopedPlaceId>>,
     definitions_by_node: FxHashMap<DefinitionNodeKey, Definitions<'db>>,
     expressions_by_node: FxHashMap<ExpressionNodeKey, Expression<'db>>,
     imported_modules: FxHashSet<ModuleName>,
@@ -127,6 +128,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
             current_assignments: vec![],
             current_match_case: None,
             current_first_parameter_name: None,
+            deferred_function_bodies: Vec::new(),
             try_node_context_stack_manager: TryNodeContextStackManager::default(),
 
             has_future_annotations: false,
@@ -141,7 +143,6 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
             scopes_by_node: FxHashMap::default(),
             definitions_by_node: FxHashMap::default(),
             expressions_by_node: FxHashMap::default(),
-            globals_by_scope: FxHashMap::default(),
 
             imported_modules: FxHashSet::default(),
             generator_functions: FxHashSet::default(),
@@ -349,7 +350,12 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
         popped_scope_id
     }
 
-    fn current_place_table(&mut self) -> &mut PlaceTableBuilder {
+    fn current_place_table(&self) -> &PlaceTableBuilder {
+        let scope_id = self.current_scope();
+        &self.place_tables[scope_id]
+    }
+
+    fn current_place_table_mut(&mut self) -> &mut PlaceTableBuilder {
         let scope_id = self.current_scope();
         &mut self.place_tables[scope_id]
     }
@@ -389,7 +395,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
     /// Add a symbol to the place table and the use-def map.
     /// Return the [`ScopedPlaceId`] that uniquely identifies the symbol in both.
     fn add_symbol(&mut self, name: Name) -> ScopedPlaceId {
-        let (place_id, added) = self.current_place_table().add_symbol(name);
+        let (place_id, added) = self.current_place_table_mut().add_symbol(name);
         if added {
             self.current_use_def_map_mut().add_place(place_id);
         }
@@ -399,7 +405,7 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
     /// Add a place to the place table and the use-def map.
     /// Return the [`ScopedPlaceId`] that uniquely identifies the place in both.
     fn add_place(&mut self, place_expr: PlaceExprWithFlags) -> ScopedPlaceId {
-        let (place_id, added) = self.current_place_table().add_place(place_expr);
+        let (place_id, added) = self.current_place_table_mut().add_place(place_expr);
         if added {
             self.current_use_def_map_mut().add_place(place_id);
         }
@@ -407,15 +413,15 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
     }
 
     fn mark_place_bound(&mut self, id: ScopedPlaceId) {
-        self.current_place_table().mark_place_bound(id);
+        self.current_place_table_mut().mark_place_bound(id);
     }
 
     fn mark_place_declared(&mut self, id: ScopedPlaceId) {
-        self.current_place_table().mark_place_declared(id);
+        self.current_place_table_mut().mark_place_declared(id);
     }
 
     fn mark_place_used(&mut self, id: ScopedPlaceId) {
-        self.current_place_table().mark_place_used(id);
+        self.current_place_table_mut().mark_place_used(id);
     }
 
     fn add_entry_for_definition_key(&mut self, key: DefinitionNodeKey) -> &mut Definitions<'db> {
@@ -1004,8 +1010,83 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
         }
     }
 
+    fn visit_function_body(&mut self, function_def: &'ast ast::StmtFunctionDef) {
+        let ast::StmtFunctionDef {
+            parameters,
+            type_params,
+            returns,
+            body,
+            ..
+        } = function_def;
+        self.with_type_params(
+            NodeWithScopeRef::FunctionTypeParameters(function_def),
+            type_params.as_deref(),
+            |builder| {
+                builder.visit_parameters(parameters);
+                if let Some(returns) = returns {
+                    builder.visit_annotation(returns);
+                }
+
+                builder.push_scope(NodeWithScopeRef::Function(function_def));
+
+                builder.declare_parameters(parameters);
+
+                let mut first_parameter_name = parameters
+                    .iter_non_variadic_params()
+                    .next()
+                    .map(|first_param| first_param.parameter.name.id().as_str());
+                std::mem::swap(
+                    &mut builder.current_first_parameter_name,
+                    &mut first_parameter_name,
+                );
+
+                builder.visit_scoped_body(body);
+
+                builder.current_first_parameter_name = first_parameter_name;
+                builder.pop_scope()
+            },
+        );
+    }
+
+    /// Walk the body of a scope, either the global scope or a function scope.
+    ///
+    /// When we encounter a (top-level or nested) function definition, we add the function's name
+    /// to the current scope, but we defer walking its body until the end. (See the `FunctionDef`
+    /// branch of `visit_stmt`.) This deferred approach is necessary to be able to check `nonlocal`
+    /// statements as we encounter them, for example:
+    ///
+    /// ```py
+    /// def f():
+    ///     def g():
+    ///         nonlocal x  # allowed
+    ///         nonlocal y  # SyntaxError: no binding for nonlocal 'y' found
+    ///     x = 1
+    /// ```
+    ///
+    /// See the comments in the `Nonlocal` branch of `visit_stmt`, which relies on this binding
+    /// information being present.
+    fn visit_scoped_body(&mut self, body: &'ast [ast::Stmt]) {
+        debug_assert!(
+            self.deferred_function_bodies.is_empty(),
+            "every function starts with a clean scope",
+        );
+
+        // If this scope contains function definitions, they'll be added to
+        // `self.deferred_function_bodies` as we walk each statement.
+        self.visit_body(body);
+
+        // Now that we've walked all the statements in this scope, walk any deferred function
+        // bodies. This is recursive, so we need to clear out the contents of
+        // `self.deferred_function_bodies` and give each function a fresh list (or else we'll fail
+        // the `debug_assert!` above).
+        let taken_deferred_function_bodies = std::mem::take(&mut self.deferred_function_bodies);
+        for function_def in taken_deferred_function_bodies {
+            self.visit_function_body(function_def);
+        }
+    }
+
     pub(super) fn build(mut self) -> SemanticIndex<'db> {
-        self.visit_body(self.module.suite());
+        self.visit_scoped_body(self.module.suite());
 
         // Pop the root scope
         self.pop_scope();
@@ -1042,7 +1123,6 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
         self.scopes_by_node.shrink_to_fit();
         self.generator_functions.shrink_to_fit();
         self.eager_snapshots.shrink_to_fit();
-        self.globals_by_scope.shrink_to_fit();
 
         SemanticIndex {
             place_tables,
@@ -1050,7 +1130,6 @@ impl<'db, 'ast> SemanticIndexBuilder<'db, 'ast> {
             definitions_by_node: self.definitions_by_node,
             expressions_by_node: self.expressions_by_node,
             scope_ids_by_scope: self.scope_ids_by_scope,
-            globals_by_scope: self.globals_by_scope,
             ast_ids,
             scopes_by_expression: self.scopes_by_expression,
             scopes_by_node: self.scopes_by_node,
@@ -1084,46 +1163,19 @@ impl<'ast> Visitor<'ast> for SemanticIndexBuilder<'_, 'ast> {
                 let ast::StmtFunctionDef {
                     decorator_list,
                     parameters,
-                    type_params,
                     name,
-                    returns,
-                    body,
-                    is_async: _,
-                    range: _,
-                    node_index: _,
+                    ..
                 } = function_def;
+
+                // Like Ruff, we don't walk the body of the function here. Instead, we defer it to
+                // the end of the current scope. See `visit_scoped_body`. See also the comments in
+                // the `Nonlocal` branch below about why this deferred visit order is necessary.
+                self.deferred_function_bodies.push(function_def);
+
                 for decorator in decorator_list {
                     self.visit_decorator(decorator);
                 }
 
-                self.with_type_params(
-                    NodeWithScopeRef::FunctionTypeParameters(function_def),
-                    type_params.as_deref(),
-                    |builder| {
-                        builder.visit_parameters(parameters);
-                        if let Some(returns) = returns {
-                            builder.visit_annotation(returns);
-                        }
-
-                        builder.push_scope(NodeWithScopeRef::Function(function_def));
-
-                        builder.declare_parameters(parameters);
-
-                        let mut first_parameter_name = parameters
-                            .iter_non_variadic_params()
-                            .next()
-                            .map(|first_param| first_param.parameter.name.id().as_str());
-                        std::mem::swap(
-                            &mut builder.current_first_parameter_name,
-                            &mut first_parameter_name,
-                        );
-
-                        builder.visit_body(body);
-
-                        builder.current_first_parameter_name = first_parameter_name;
-                        builder.pop_scope()
-                    },
-                );
                 // The default value of the parameters needs to be evaluated in the
                 // enclosing scope.
                 for default in parameters
@@ -1418,6 +1470,29 @@ impl<'ast> Visitor<'ast> for SemanticIndexBuilder<'_, 'ast> {
                     self.visit_expr(value);
                 }
 
+                if let ast::Expr::Name(name) = &*node.target {
+                    let symbol_id = self.add_symbol(name.id.clone());
+                    let symbol = self.current_place_table().place_expr(symbol_id);
+                    // Check whether the variable has been declared global.
+                    if symbol.is_marked_global() {
+                        self.report_semantic_error(SemanticSyntaxError {
+                            kind: SemanticSyntaxErrorKind::AnnotatedGlobal(name.id.as_str().into()),
+                            range: name.range,
+                            python_version: self.python_version,
+                        });
+                    }
+                    // Check whether the variable has been declared nonlocal.
+                    if symbol.is_marked_nonlocal() {
+                        self.report_semantic_error(SemanticSyntaxError {
+                            kind: SemanticSyntaxErrorKind::AnnotatedNonlocal(
+                                name.id.as_str().into(),
+                            ),
+                            range: name.range,
+                            python_version: self.python_version,
+                        });
+                    }
+                }
+
                 // See https://docs.python.org/3/library/ast.html#ast.AnnAssign
                 if matches!(
                     *node.target,
@@ -1858,8 +1933,8 @@ impl<'ast> Visitor<'ast> for SemanticIndexBuilder<'_, 'ast> {
             }) => {
                 for name in names {
                     let symbol_id = self.add_symbol(name.id.clone());
-                    let symbol_table = self.current_place_table();
-                    let symbol = symbol_table.place_expr(symbol_id);
+                    let symbol = self.current_place_table().place_expr(symbol_id);
+                    // Check whether the variable has already been accessed in this scope.
                     if symbol.is_bound() || symbol.is_declared() || symbol.is_used() {
                         self.report_semantic_error(SemanticSyntaxError {
                             kind: SemanticSyntaxErrorKind::LoadBeforeGlobalDeclaration {
@@ -1870,11 +1945,112 @@ impl<'ast> Visitor<'ast> for SemanticIndexBuilder<'_, 'ast> {
                             python_version: self.python_version,
                         });
                     }
-                    let scope_id = self.current_scope();
-                    self.globals_by_scope
-                        .entry(scope_id)
-                        .or_default()
-                        .insert(symbol_id);
+                    // Check whether the variable has also been declared nonlocal.
+                    if symbol.is_marked_nonlocal() {
+                        self.report_semantic_error(SemanticSyntaxError {
+                            kind: SemanticSyntaxErrorKind::NonlocalAndGlobal(name.to_string()),
+                            range: name.range,
+                            python_version: self.python_version,
+                        });
+                    }
+                    self.current_place_table_mut().mark_place_global(symbol_id);
+                }
+                walk_stmt(self, stmt);
+            }
+            ast::Stmt::Nonlocal(ast::StmtNonlocal {
+                range: _,
+                node_index: _,
+                names,
+            }) => {
+                for name in names {
+                    let local_scoped_place_id = self.add_symbol(name.id.clone());
+                    let local_place = self.current_place_table().place_expr(local_scoped_place_id);
+                    // Check whether the variable has already been accessed in this scope.
+                    if local_place.is_bound() || local_place.is_declared() || local_place.is_used()
+                    {
+                        self.report_semantic_error(SemanticSyntaxError {
+                            kind: SemanticSyntaxErrorKind::LoadBeforeNonlocalDeclaration {
+                                name: name.to_string(),
+                                start: name.range.start(),
+                            },
+                            range: name.range,
+                            python_version: self.python_version,
+                        });
+                    }
+                    // Check whether the variable has also been declared global.
+                    if local_place.is_marked_global() {
+                        self.report_semantic_error(SemanticSyntaxError {
+                            kind: SemanticSyntaxErrorKind::NonlocalAndGlobal(name.to_string()),
+                            range: name.range,
+                            python_version: self.python_version,
+                        });
+                    }
+                    // The name is required to exist in an enclosing scope, but that definition
+                    // might come later. For example, this is example legal:
+                    //
+                    // ```py
+                    // def f():
+                    //     def g():
+                    //         nonlocal x
+                    //     x = 1
+                    // ```
+                    //
+                    // To handle cases like this, we have to walk `x = 1` before we walk `nonlocal
+                    // x`. In other words, walking function bodies must be "deferred" to the end of
+                    // the scope where they're defined. See the `FunctionDef` branch above.
+                    let name_expr = PlaceExpr::name(name.id.clone());
+                    let mut found_matching_definition = false;
+                    for enclosing_scope_info in self.scope_stack.iter().rev().skip(1) {
+                        let enclosing_scope = &self.scopes[enclosing_scope_info.file_scope_id];
+                        if !enclosing_scope.kind().is_function_like() {
+                            // Skip over class scopes and the global scope.
+                            continue;
+                        }
+                        let enclosing_place_table =
+                            &self.place_tables[enclosing_scope_info.file_scope_id];
+                        let Some(enclosing_scoped_place_id) =
+                            enclosing_place_table.place_id_by_expr(&name_expr)
+                        else {
+                            // This name isn't defined in this scope. Keep going.
+                            continue;
+                        };
+                        let enclosing_place =
+                            enclosing_place_table.place_expr(enclosing_scoped_place_id);
+                        // We've found a definition for this name in an enclosing function-like
+                        // scope. Either this definition is the valid place this name refers to, or
+                        // else we'll emit a syntax error. Either way, we won't walk any more
+                        // enclosing scopes. Note that there are differences here compared to
+                        // `infer_place_load`: A regular load (e.g. `print(x)`) is allowed to refer
+                        // to a global variable (e.g. `x = 1` in the global scope), and similarly
+                        // it's allowed to refer to a variable in an enclosing function that's
+                        // declared `global` (e.g. `global x`). However, the `nonlocal` keyword
+                        // can't refer to global variables (that's a `SyntaxError`), and it also
+                        // can't refer to variables in enclosing functions that are declared
+                        // `global` (also a `SyntaxError`).
+                        if enclosing_place.is_marked_global() {
+                            // A "chain" of `nonlocal` statements is "broken" by a `global`
+                            // statement. Stop looping and report that this `nonlocal` statement is
+                            // invalid.
+                            break;
+                        }
+                        // We found a definition, and we've checked that that place isn't declared
+                        // `global` in its scope, but it's ok if it's `nonlocal`. If a chain of
+                        // `nonlocal` statements fails to lead to a valid binding, the outermost
+                        // one will be an error; we don't need to report an error for each one.
+                        found_matching_definition = true;
+                        self.current_place_table_mut()
+                            .mark_place_nonlocal(local_scoped_place_id);
+                        break;
+                    }
+                    if !found_matching_definition {
+                        // There's no matching definition in an enclosing scope. This `nonlocal`
+                        // statement is invalid.
+                        self.report_semantic_error(SemanticSyntaxError {
+                            kind: SemanticSyntaxErrorKind::InvalidNonlocal(name.to_string()),
+                            range: name.range,
+                            python_version: self.python_version,
+                        });
+                    }
                 }
                 walk_stmt(self, stmt);
             }
@@ -1888,7 +2064,7 @@ impl<'ast> Visitor<'ast> for SemanticIndexBuilder<'_, 'ast> {
                 for target in targets {
                     if let Ok(target) = PlaceExpr::try_from(target) {
                         let place_id = self.add_place(PlaceExprWithFlags::new(target));
-                        self.current_place_table().mark_place_used(place_id);
+                        self.current_place_table_mut().mark_place_used(place_id);
                         self.delete_binding(place_id);
                     }
                 }

crates/ty_python_semantic/src/semantic_index/place.rs

@@ -330,6 +330,16 @@ impl PlaceExprWithFlags {
         self.flags.contains(PlaceFlags::IS_DECLARED)
     }
 
+    /// Is the place `global` its containing scope?
+    pub fn is_marked_global(&self) -> bool {
+        self.flags.contains(PlaceFlags::MARKED_GLOBAL)
+    }
+
+    /// Is the place `nonlocal` its containing scope?
+    pub fn is_marked_nonlocal(&self) -> bool {
+        self.flags.contains(PlaceFlags::MARKED_NONLOCAL)
+    }
+
     pub(crate) fn as_name(&self) -> Option<&Name> {
         self.expr.as_name()
     }
@@ -397,9 +407,7 @@ bitflags! {
         const IS_USED               = 1 << 0;
         const IS_BOUND              = 1 << 1;
         const IS_DECLARED           = 1 << 2;
-        /// TODO: This flag is not yet set by anything
         const MARKED_GLOBAL         = 1 << 3;
-        /// TODO: This flag is not yet set by anything
         const MARKED_NONLOCAL       = 1 << 4;
         const IS_INSTANCE_ATTRIBUTE = 1 << 5;
     }
@@ -663,7 +671,7 @@ impl PlaceTable {
     }
 
     /// Returns the place named `name`.
-    #[allow(unused)] // used in tests
+    #[cfg(test)]
     pub(crate) fn place_by_name(&self, name: &str) -> Option<&PlaceExprWithFlags> {
         let id = self.place_id_by_name(name)?;
         Some(self.place_expr(id))
@@ -814,6 +822,14 @@ impl PlaceTableBuilder {
         self.table.places[id].insert_flags(PlaceFlags::IS_USED);
     }
 
+    pub(super) fn mark_place_global(&mut self, id: ScopedPlaceId) {
+        self.table.places[id].insert_flags(PlaceFlags::MARKED_GLOBAL);
+    }
+
+    pub(super) fn mark_place_nonlocal(&mut self, id: ScopedPlaceId) {
+        self.table.places[id].insert_flags(PlaceFlags::MARKED_NONLOCAL);
+    }
+
     pub(super) fn places(&self) -> impl Iterator<Item = &PlaceExprWithFlags> {
         self.table.places()
     }

crates/ty_python_semantic/src/types/infer.rs

@@ -1564,6 +1564,7 @@ impl<'db, 'ast> TypeInferenceBuilder<'db, 'ast> {
         let mut bound_ty = ty;
 
         let global_use_def_map = self.index.use_def_map(FileScopeId::global());
+        let nonlocal_use_def_map;
         let place_id = binding.place(self.db());
         let place = place_table.place_expr(place_id);
         let skip_non_global_scopes = self.skip_non_global_scopes(file_scope_id, place_id);
@@ -1574,9 +1575,58 @@ impl<'db, 'ast> TypeInferenceBuilder<'db, 'ast> {
                 .place_id_by_expr(&place.expr)
             {
                 Some(id) => (global_use_def_map.end_of_scope_declarations(id), false),
-                // This case is a syntax error (load before global declaration) but ignore that here
+                // This variable shows up in `global` declarations but doesn't have an explicit
+                // binding in the global scope.
                 None => (use_def.declarations_at_binding(binding), true),
             }
+        } else if self
+            .index
+            .symbol_is_nonlocal_in_scope(place_id, file_scope_id)
+        {
+            // If we run out of ancestor scopes without finding a definition, we'll fall back to
+            // the local scope. This will also be a syntax error in `infer_nonlocal_statement` (no
+            // binding for `nonlocal` found), but ignore that here.
+            let mut declarations = use_def.declarations_at_binding(binding);
+            let mut is_local = true;
+            // Walk up parent scopes looking for the enclosing scope that has definition of this
+            // name. `ancestor_scopes` includes the current scope, so skip that one.
+            for (enclosing_scope_file_id, enclosing_scope) in
+                self.index.ancestor_scopes(file_scope_id).skip(1)
+            {
+                // Ignore class scopes and the global scope.
+                if !enclosing_scope.kind().is_function_like() {
+                    continue;
+                }
+                let enclosing_place_table = self.index.place_table(enclosing_scope_file_id);
+                let Some(enclosing_place_id) = enclosing_place_table.place_id_by_expr(&place.expr)
+                else {
+                    // This ancestor scope doesn't have a binding. Keep going.
+                    continue;
+                };
+                if self
+                    .index
+                    .symbol_is_nonlocal_in_scope(enclosing_place_id, enclosing_scope_file_id)
+                {
+                    // The variable is `nonlocal` in this ancestor scope. Keep going.
+                    continue;
+                }
+                if self
+                    .index
+                    .symbol_is_global_in_scope(enclosing_place_id, enclosing_scope_file_id)
+                {
+                    // The variable is `global` in this ancestor scope. This breaks the `nonlocal`
+                    // chain, and it's a syntax error in `infer_nonlocal_statement`. Ignore that
+                    // here and just bail out of this loop.
+                    break;
+                }
+                // We found the closest definition. Note that (unlike in `infer_place_load`) this
+                // does *not* need to be a binding. It could be just `x: int`.
+                nonlocal_use_def_map = self.index.use_def_map(enclosing_scope_file_id);
+                declarations = nonlocal_use_def_map.end_of_scope_declarations(enclosing_place_id);
+                is_local = false;
+                break;
+            }
+            (declarations, is_local)
         } else {
             (use_def.declarations_at_binding(binding), true)
         };
@@ -5800,13 +5850,15 @@ impl<'db, 'ast> TypeInferenceBuilder<'db, 'ast> {
 
             let current_file = self.file();
 
+            let mut is_nonlocal_binding = false;
             if let Some(name) = expr.as_name() {
-                let skip_non_global_scopes = place_table
-                    .place_id_by_name(name)
-                    .is_some_and(|symbol_id| self.skip_non_global_scopes(file_scope_id, symbol_id));
-
-                if skip_non_global_scopes {
-                    return global_symbol(self.db(), self.file(), name);
+                if let Some(symbol_id) = place_table.place_id_by_name(name) {
+                    if self.skip_non_global_scopes(file_scope_id, symbol_id) {
+                        return global_symbol(self.db(), self.file(), name);
+                    }
+                    is_nonlocal_binding = self
+                        .index
+                        .symbol_is_nonlocal_in_scope(symbol_id, file_scope_id);
                 }
             }
 
@@ -5819,7 +5871,7 @@ impl<'db, 'ast> TypeInferenceBuilder<'db, 'ast> {
             // a local variable or not in function-like scopes. If a variable has any bindings in a
             // function-like scope, it is considered a local variable; it never references another
             // scope. (At runtime, it would use the `LOAD_FAST` opcode.)
-            if has_bindings_in_this_scope && scope.is_function_like(db) {
+            if has_bindings_in_this_scope && scope.is_function_like(db) && !is_nonlocal_binding {
                 return Place::Unbound.into();
             }