feat[lang]: add linearization check for initializers

[charles-cooper]

add a check that each init function is called after its dependencies

misc/refactor:

• additional rewrite of a few lines without changing semantics

What I did

fix https://github.com/vyperlang/vyper/issues/3779

How I did it

How to verify it

Commit message

Commit message for the final, squashed PR. (Optional, but reviewers will appreciate it! Please see our commit message style guide for what we would ideally like to see in a commit message.)

Description for the changelog

Cute Animal Picture

![Put a link to a cute animal picture inside the parenthesis-->]()

[cyberthirst]

i'm not sure this shouldn't compile:

# main
import lib1
import lib2
import lib3

initializes: lib2[lib1 := lib1]
initializes: lib3

@deploy
def __init__():
    lib3.__init__(0)
    lib2.__init__()

# lib1
a: public(uint256)

@deploy
@payable
def __init__(x: uint256):
    self.a = x

# lib2
import lib1

uses: lib1

a: uint256

@deploy
def __init__():
    # not initialized when called
    self.a = lib1.a

# lib3
import lib1

initializes: lib1

a: uint256

@deploy
@payable
def __init__(x: uint256):
    self.a = x
    lib1.__init__(0)

fails with:

vyper.exceptions.InitializerException: Tried to initialize `lib2`, but it depends on `lib1`, which has not been initialized yet.

  (hint: call `lib1.__init__()` before `lib2.__init__()`.)

  contract "tests/custom/main.vy:11", function "__init__", line 11:4 
          10     lib3.__init__(0)
  ---> 11     lib2.__init__()
  ------------^
       12

but lib3.__init__ initializes lib1

[cyberthirst]

give us recursion

# main
import lib1
import lib2
import lib3
import lib4

initializes: lib2[lib1 := lib1, lib4 := lib4]
initializes: lib3

@deploy
def __init__():
    lib3.__init__(0)
    lib2.__init__()

# lib1
import lib4

a: public(uint256)

initializes: lib4

@deploy
@payable
def __init__(x: uint256):
    self.a = x
    lib4.__init__(x)

# lib2
import lib1
import lib4

uses: lib1
uses: lib4

a: uint256

@deploy
def __init__():
    # not initialized when called
    self.a = lib1.a + lib4.a

# lib3
import lib1

initializes: lib1

a: uint256

@deploy
@payable
def __init__(x: uint256):
    self.a = x
    lib1.__init__(0)

# lib4

a: uint256

@deploy
@payable
def __init__(x: uint256):
    self.a = x

vyper.exceptions.InitializerException: Tried to initialize `lib2`, but it depends on `lib4`, which has not been initialized yet.

  (hint: call `lib4.__init__()` before `lib2.__init__()`.)

  contract "tests/custom/main.vy:12", function "__init__", line 12:4 
       11     lib3.__init__(0)
  ---> 12     lib2.__init__()
  ------------^
       13

[trocher]

The following compiles although it should not I guess?

main.vy:

import lib1
import lib2

initializes: lib2[lib1 := lib1]
initializes: lib1

@deploy
def __init__():
    for i:uint256 in range(2):
        if i == 1:
            lib1.__init__()
        if i == 0:
            lib2.__init__()

lib1.vy

counter: uint256

@deploy
def __init__():
    pass

lib2.vy

import lib1

uses: lib1

counter: uint256

@deploy
def __init__():
    pass

@internal
def foo():
    lib1.counter += 1

[EDIT] just saw this comment: https://github.com/vyperlang/vyper/issues/3779#issuecomment-2095942301

[charles-cooper]

The following compiles although it should not I guess?

main.vy:

import lib1
import lib2

initializes: lib2[lib1 := lib1]
initializes: lib1

@deploy
def __init__():
    for i:uint256 in range(2):
        if i == 1:
            lib1.__init__()
        if i == 0:
            lib2.__init__()

lib1.vy

counter: uint256

@deploy
def __init__():
    pass

lib2.vy

import lib1

uses: lib1

counter: uint256

@deploy
def __init__():
    pass

@internal
def foo():
    lib1.counter += 1

[EDIT] just saw this comment: #3779 (comment)

yea we don't really care about branches, those get weird - just about AST order

[trocher]

The following compiles on master but not on this branch since the analysis performed assumes that, given a module A which initializes a module B with some dependency C (initializes: B[C:=C]), A must also initialize C although it could be that it only uses it.

lib3.vy

counter: uint256

@deploy
def __init__():
    self.counter = 1

lib2.vy

import lib3

uses: lib3

counter: uint256

@deploy
def __init__():
    self.counter = 1

@external
def foo() ->uint256:
    return lib3.counter

lib1.vy

import lib2
import lib3

uses: lib3
initializes: lib2[lib3 := lib3]

@deploy
def __init__():
    lib2.__init__()
    lib3.counter += 1

main.vy

import lib1
import lib3

initializes: lib1[lib3 := lib3]
initializes: lib3

@deploy
def __init__():
    lib3.__init__()
    lib1.__init__()

[charles-cooper]

The following compiles on master but not on this branch since the analysis performed assumes that, given a module A which initializes a module B with some dependency C (initializes: B[C:=C]), A must also initialize C although it could be that it only uses it.

yea i guess this represents a fundamental problem with the approach in this PR, which is that lib1 initialization can depend on some other library which is not initialized until the ownership checker actually runs, which is a global constraint checker.

[charles-cooper]

The following compiles on master but not on this branch since the analysis performed assumes that, given a module A which initializes a module B with some dependency C (initializes: B[C:=C]), A must also initialize C although it could be that it only uses it.

yea i guess this represents a fundamental problem with the approach in this PR, which is that lib1 initialization can depend on some other library which is not initialized until the ownership checker actually runs, which is a global constraint checker.

actually was re-reading the spec with @cyberthirst and it seems this PR is actually enforcing item 3 from the the spec (https://github.com/vyperlang/vyper/issues/3722):

you cannot touch modules from an __init__() function unless they are already owned.

the hint could be improved, though

[charles-cooper]

i rewrote the code to enforce spec point 3. but snekmate uses the current behavior here (touch used module in __init__() function): https://github.com/pcaversaccio/snekmate/blob/modules/src%2Fsnekmate%2Fgovernance%2Ftimelock_controller.vy#L254

[pcaversaccio]

i rewrote the code to enforce spec point 3. but snekmate uses the current behavior here (touch used module in __init__() function): https://github.com/pcaversaccio/snekmate/blob/modules/src%2Fsnekmate%2Fgovernance%2Ftimelock_controller.vy#L254

This actually a very important pattern I need in snekmate and plan to use more often lol...

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 38.46154% with 16 lines in your changes are missing coverage. Please review.

Project coverage is 48.89%. Comparing base (e52241a) to head (9740de3).

:exclamation: Current head 9740de3 differs from pull request most recent head e46e535

Please upload reports for the commit e46e535 to get more accurate results.

Files	Patch %	Lines
vyper/semantics/analysis/global_.py	28.57%	14 Missing and 1 partial :warning:
vyper/semantics/analysis/module.py	75.00%	1 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #4038 +/- ## =========================================== - Coverage 91.28% 48.89% -42.39% =========================================== Files 109 109 Lines 15549 15565 +16 Branches 3416 3419 +3 =========================================== - Hits 14194 7611 -6583 - Misses 925 7340 +6415 - Partials 430 614 +184 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.