1

Does Rust borrow checker analyze the program locally or globally?

In other words does borrow checker need information about the whole program or it works locally within the function scope?

I'm asking because I want to quantify it's algorithmic complexity. I'm wondering if the size of the borrow checking problem is the whole program of just the function.

ciechowoj
  • 914
  • 6
  • 26
  • 2
    Does https://rustc-dev-guide.rust-lang.org/borrow_check.html help? It's an explanation of how the borrow checker works from the rustc dev guide. – Teymour Aug 07 '20 at 11:52

2 Answers2

3

One of the tenets of Rust is Local Reasoning, both for static analysis (compiler) and human reader.

This is why function signatures are so specific, and potentially verbose, with:

  • Types for every argument, and return type, explicitly spelled out.
  • Constraints explicitly spelled out (on generic code).
  • Lifetimes annotations.

The latter is subject to Lifetime Elision rules, as syntactic sugar, but those rules are themselves strictly limited to the signature of the function.

The end result is that there is never a need to peek inside the function to perform semantic checks.

Note: on the other hand, with -> impl Trait, code generation needs to peek inside the function to know the exact type; it's not about reasoning though, so it gets a pass.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
2

The borrow checker operates purely on a single function at a time.

Sebastian Redl
  • 69,373
  • 8
  • 123
  • 157
  • 2
    Commenting to link to [Why are explicit lifetimes needed in Rust?](/q/31609137/3650362) which contains some rationale: *Functions are a natural boundary to firewall the effects of changing code.* – trent Aug 07 '20 at 14:12