Repository: vyperlang/vyper

Issue:
Vyper compiler fails to compile long `unsafe` expression
### Version Information

* vyper Version (output of `vyper --version`): `0.3.7+commit.6020b8b`
* OS: linux
* Python Version (output of `python --version`): `3.9.2`

### What's your issue about?

The Vyper compiler fails to compile the following function (waited for around 10mins without success):

```vyper
@external
@pure
def wad_exp(x: int256) -> uint256:
    value: int256 = x
    if (x <= -42139678854452767551):
        return empty(uint256)

    assert x < 135305999368893231589, "Math: wad_exp overflow"

    value = unsafe_div(shift(x, 78), 5 ** 18)
    k: int256 = shift(unsafe_add(unsafe_div(shift(value, 96), 54916777467707473351141471128), 2 ** 95), -96)
    value = unsafe_sub(value, unsafe_mul(k, 54916777467707473351141471128))

    y: int256 = unsafe_add(shift(unsafe_mul(unsafe_add(value, 1346386616545796478920950773328), value), -96), 57155421227552351082224309758442)
    p: int256 = unsafe_add(unsafe_mul(unsafe_add(shift(unsafe_mul(unsafe_sub(unsafe_add(y, value), 94201549194550492254356042504812), y), -96), 28719021644029726153956944680412240), value), shift(4385272521454847904659076985693276, 96))

    q: int256 = unsafe_add(shift(unsafe_mul(unsafe_sub\
                (shift(unsafe_mul(unsafe_add(shift(unsafe_mul\
                (unsafe_sub(shift(unsafe_mul(unsafe_add(shift(unsafe_mul\
                (unsafe_sub(value, convert(2855989394907223263936484059900, int256)),\
                value), convert(-96, int256)), convert(50020603652535783019961831881945,\
                int256)), value), convert(-96, int256)), convert(533845033583426703283633433725380, int256)),\
                value), convert(-96, int256)), convert(3604857256930695427073651918091429, int256)), value),\
                convert(-96, int256)), convert(14423608567350463180887372962807573, int256)), value),\
                convert(-96, int256)), convert(26449188498355588339934803723976023, int256))

    r: int256 = unsafe_div(p, q)

    return convert(shift(unsafe_mul(r, 3822833074963236453042738258902158003155416615667), -unsafe_sub(195, k)), uint256)
```

### How can it be fixed?

The Vyper compiler should be able to successfully compile the above or similar long `unsafe` expressions.

Discussion:
pcaversaccio: I quickly checked, and can confirm my example compiles under a second with the following init code:

```vyper
0x6102fd610011610000396102fd610000f360003560e01c346102eb576381d18d8781186102e457602436106102eb576004356040527ffffffffffffffffffffffffffffffffffffffffffffffffdb731c958f34d94c16004351361005a576000606052602060606102e2565b680755bf798b4a1bf1e460043513156100ca5760166060527f4d6174683a207761645f657870206f766572666c6f770000000000000000000060805260605060605180608001601f826000031636823750506308c379a06020526020604052601f19601f6060510116604401603cfd5b6503782dace9d960043580604e1b9050056040526b8000000000000000000000006bb17217f7d1cf79abc9e3b3986040518060601b905005018060601d90506060526bb17217f7d1cf79abc9e3b39860605102604051036040526d02d16720577bd19bf614176fe9ea6040516c10fe68e7fd37d0007b713f765060405101028060601d90500160805279d835ebba824c98fb31b83b2ca45c0000000000000000000000006040516e0587f503bb6ea29d25fcb7401964506080516d04a4fd9f2a8b96949216d2255a6c6040516080510103028060601d905001020160a0526e05180bb14799ab47a8a8cb2a527d576040516e02c72388d9f74f51a9331fed693f156040516db1bbb201f443cf962f1a1d3db4a56040516d1a521255e34f6a5061b25ef1c9c46040516d0277594991cfc85f6e2461837cd96040516c240c330e9fb2d9cbaf0fd5aafc60405103028060601d905001028060601d905003028060601d905001028060601d905003028060601d90500160c05260c05160a0510560e05274029d9dc38563c32e5c2f6dc192ee70ef65f9978af360e0510260605160c3037f800000000000000000000000000000000000000000000000000000000000000081146102eb576000037fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff8113156102c55781811b6102cc565b81816000031d5b90509050600081126102eb576101005260206101005bf35b5060006000fd5b600080fda165767970657283000302000b
```
codecov-commenter: ## [Codecov](https://codecov.io/gh/vyperlang/vyper/pull/3318?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang) Report
> Merging [#3318](https://codecov.io/gh/vyperlang/vyper/pull/3318?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang) (099ed39) into [master](https://codecov.io/gh/vyperlang/vyper/commit/7a64d4b0a5b5bbec367fdfd63640be637ab9f66f?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang) (7a64d4b) will **decrease** coverage by `37.76%`.
> The diff coverage is `80.00%`.

:mega: This organization is not using Codecov’s [GitHub App Integration](https://github.com/apps/codecov). We recommend you install it so Codecov can continue to function properly for your repositories. [Learn more](https://about.codecov.io/blog/codecov-is-updating-its-github-integration/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang)

```diff
@@             Coverage Diff             @@
##           master    #3318       +/-   ##
===========================================
- Coverage   88.79%   51.03%   -37.76%     
===========================================
  Files          84       84               
  Lines       10637    10640        +3     
  Branches     2221     2223        +2     
===========================================
- Hits         9445     5430     -4015     
- Misses        790     4692     +3902     
- Partials      402      518      +116     
```


| [Impacted Files](https://codecov.io/gh/vyperlang/vyper/pull/3318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang) | Coverage Δ | |
|---|---|---|
| [vyper/semantics/analysis/utils.py](https://codecov.io/gh/vyperlang/vyper/pull/3318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang#diff-dnlwZXIvc2VtYW50aWNzL2FuYWx5c2lzL3V0aWxzLnB5) | `46.42% <76.19%> (-45.63%)` | :arrow_down: |
| [vyper/semantics/namespace.py](https://codecov.io/gh/vyperlang/vyper/pull/3318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang#diff-dnlwZXIvc2VtYW50aWNzL25hbWVzcGFjZS5weQ==) | `76.38% <100.00%> (-20.84%)` | :arrow_down: |
| [vyper/semantics/types/\_\_init\_\_.py](https://codecov.io/gh/vyperlang/vyper/pull/3318?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang#diff-dnlwZXIvc2VtYW50aWNzL3R5cGVzL19faW5pdF9fLnB5) | `100.00% <100.00%> (ø)` | |

... and [66 files with indirect coverage changes](https://codecov.io/gh/vyperlang/vyper/pull/3318/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang)

:mega: We’re building smart automated test selection to slash your CI/CD build times. [Learn more](https://about.codecov.io/iterative-testing/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=vyperlang)


Patch:
diff --git a/vyper/semantics/analysis/__init__.py b/vyper/semantics/analysis/__init__.py
index 0b580a83..306f8765 100644
--- a/vyper/semantics/analysis/__init__.py
+++ b/vyper/semantics/analysis/__init__.py
@@ -2,6 +2,7 @@ from .. import types  # break a dependency cycle.
 from ..namespace import get_namespace
 from .local import validate_functions
 from .module import add_module_namespace
+from .utils import _ExprAnalyser
 
 
 def validate_semantics(vyper_ast, interface_codes):
@@ -11,3 +12,6 @@ def validate_semantics(vyper_ast, interface_codes):
     with namespace.enter_scope():
         add_module_namespace(vyper_ast, interface_codes)
         validate_functions(vyper_ast)
+
+    # clean up. not sure if this is necessary, but do it for hygiene's sake.
+    _ExprAnalyser._reset_taint()
diff --git a/vyper/semantics/analysis/local.py b/vyper/semantics/analysis/local.py
index ae90f825..73fb5c91 100644
--- a/vyper/semantics/analysis/local.py
+++ b/vyper/semantics/analysis/local.py
@@ -21,6 +21,7 @@ from vyper.semantics.analysis.annotation import StatementAnnotationVisitor
 from vyper.semantics.analysis.base import DataLocation, VarInfo
 from vyper.semantics.analysis.common import VyperNodeVisitorBase
 from vyper.semantics.analysis.utils import (
+    _ExprAnalyser,
     get_common_types,
     get_exact_type_from_node,
     get_expr_info,
@@ -454,12 +455,23 @@ class FunctionNodeVisitor(VyperNodeVisitorBase):
                 try:
                     for n in node.body:
                         self.visit(n)
-                    # type information is applied directly because the scope is
-                    # closed prior to the call to `StatementAnnotationVisitor`
-                    node.target._metadata["type"] = type_
-                    return
                 except (TypeMismatch, InvalidOperation) as exc:
                     for_loop_exceptions.append(exc)
+                    # rollback any changes to the tree
+                    _ExprAnalyser._rollback_taint()
+                else:
+                    # type information is applied directly here because the
+                    # scope is closed prior to the call to
+                    # `StatementAnnotationVisitor`
+                    node.target._metadata["type"] = type_
+
+                    # perf - persist all calculated types
+                    _ExprAnalyser._commit_taint()
+                    # success -- bail out instead of error handling.
+                    return
+
+        # if we have gotten here, there was an error for
+        # every type tried for the iterator
 
         if len(set(str(i) for i in for_loop_exceptions)) == 1:
             # if every attempt at type checking raised the same exception
diff --git a/vyper/semantics/analysis/utils.py b/vyper/semantics/analysis/utils.py
index 0ae59e4e..ae154e98 100644
--- a/vyper/semantics/analysis/utils.py
+++ b/vyper/semantics/analysis/utils.py
@@ -57,6 +57,13 @@ class _ExprAnalyser:
     class's method resolution order is examined to decide which method to call.
     """
 
+    # this allows for a very simple commit/rollback scheme for metadata
+    # caching. in the case that an exception is thrown and caught during
+    # type checking (currently, only during for loop iterator variable
+    # type inference), we can roll back any state updates due to type
+    # checking.
+    _tainted_nodes: set[tuple[vy_ast.VyperNode, str]] = set()
+
     def __init__(self):
         self.namespace = get_namespace()
 
@@ -123,6 +130,7 @@ class _ExprAnalyser:
 
         if len(types_list) > 1:
             raise StructureException("Ambiguous type", node)
+
         return types_list[0]
 
     def get_possible_types_from_node(self, node, include_type_exprs=False):
@@ -145,20 +153,44 @@ class _ExprAnalyser:
         if "type" in node._metadata:
             return [node._metadata["type"]]
 
-        fn = self._find_fn(node)
-        ret = fn(node)
-
-        if not include_type_exprs:
-            invalid = next((i for i in ret if isinstance(i, TYPE_T)), None)
-            if invalid is not None:
-                raise InvalidReference(f"not a variable or literal: '{invalid.typedef}'", node)
-
-        if all(isinstance(i, IntegerT) for i in ret):
-            # for numeric types, sort according by number of bits descending
-            # this ensures literals are cast with the largest possible type
-            ret.sort(key=lambda k: (k.bits, not k.is_signed), reverse=True)
-
-        return ret
+        # this method is a perf hotspot, so we cache the result and
+        # try to return it if found.
+        k = f"possible_types_from_node_{include_type_exprs}"
+        if k not in node._metadata:
+            fn = self._find_fn(node)
+            ret = fn(node)
+
+            if not include_type_exprs:
+                invalid = next((i for i in ret if isinstance(i, TYPE_T)), None)
+                if invalid is not None:
+                    raise InvalidReference(f"not a variable or literal: '{invalid.typedef}'", node)
+
+            if all(isinstance(i, IntegerT) for i in ret):
+                # for numeric types, sort according by number of bits descending
+                # this ensures literals are cast with the largest possible type
+                ret.sort(key=lambda k: (k.bits, not k.is_signed), reverse=True)
+
+            node._metadata[k] = ret
+            # register with list of tainted nodes, in case the cache
+            # needs to be invalidated in case of a state rollback
+            self._tainted_nodes.add((node, k))
+
+        return node._metadata[k].copy()
+
+    @classmethod
+    def _rollback_taint(cls):
+        for node, k in cls._tainted_nodes:
+            node._metadata.pop(k, None)
+        # taint has been rolled back, no need to track it anymore
+        cls._reset_taint()
+
+    @classmethod
+    def _commit_taint(cls):
+        cls._reset_taint()
+
+    @classmethod
+    def _reset_taint(cls):
+        cls._tainted_nodes.clear()
 
     def _find_fn(self, node):
         # look for a type-check method for each class in the given class mro
@@ -268,7 +300,7 @@ class _ExprAnalyser:
     def types_from_Constant(self, node):
         # literal value (integer, string, etc)
         types_list = []
-        for t in types.get_primitive_types().values():
+        for t in types.PRIMITIVE_TYPES.values():
             try:
                 # clarity and perf note: will be better to construct a
                 # map from node types to valid vyper types
@@ -302,7 +334,7 @@ class _ExprAnalyser:
         if _is_empty_list(node):
             # empty list literal `[]`
             # subtype can be anything
-            types_list = types.get_types()
+            types_list = types.PRIMITIVE_TYPES
             # 1 is minimum possible length for dynarray, assignable to anything
             ret = [DArrayT(t, 1) for t in types_list.values()]
             return ret
@@ -421,7 +453,6 @@ def get_exact_type_from_node(node):
     BaseType
         Type object.
     """
-
     return _ExprAnalyser().get_exact_type_from_node(node, include_type_exprs=True)
 
 
@@ -451,6 +482,7 @@ def get_common_types(*nodes: vy_ast.VyperNode, filter_fn: Callable = None) -> Li
         new_types = _ExprAnalyser().get_possible_types_from_node(item)
 
         common = [i for i in common_types if _is_type_in_list(i, new_types)]
+
         rejected = [i for i in common_types if i not in common]
         common += [i for i in new_types if _is_type_in_list(i, rejected)]
 
diff --git a/vyper/semantics/namespace.py b/vyper/semantics/namespace.py
index 9fd4e1f3..bb37c06c 100644
--- a/vyper/semantics/namespace.py
+++ b/vyper/semantics/namespace.py
@@ -28,9 +28,9 @@ class Namespace(dict):
         from vyper.builtins.functions import get_builtin_functions
         from vyper.semantics import environment
         from vyper.semantics.analysis.base import VarInfo
-        from vyper.semantics.types import get_types
+        from vyper.semantics.types import PRIMITIVE_TYPES
 
-        self.update(get_types())
+        self.update(PRIMITIVE_TYPES)
         self.update(environment.get_constant_vars())
         self.update({k: VarInfo(b) for (k, b) in get_builtin_functions().items()})
 
diff --git a/vyper/semantics/types/__init__.py b/vyper/semantics/types/__init__.py
index 246dcfdf..ad470718 100644
--- a/vyper/semantics/types/__init__.py
+++ b/vyper/semantics/types/__init__.py
@@ -7,7 +7,7 @@ from .subscriptable import DArrayT, HashMapT, SArrayT, TupleT
 from .user import EnumT, EventT, InterfaceT, StructT
 
 
-def get_primitive_types():
+def _get_primitive_types():
     res = [BoolT(), DecimalT()]
 
     res.extend(IntegerT.all())
@@ -46,8 +46,5 @@ def _get_sequence_types():
     return ret
 
 
-def get_types():
-    result = {}
-    result.update(get_primitive_types())
-
-    return result
+# note: it might be good to make this a frozen dict of some sort
+PRIMITIVE_TYPES = _get_primitive_types()


Test patch:
diff --git a/tests/functional/semantics/test_namespace.py b/tests/functional/semantics/test_namespace.py
index 5cb942ca..10fca3a0 100644
--- a/tests/functional/semantics/test_namespace.py
+++ b/tests/functional/semantics/test_namespace.py
@@ -3,7 +3,7 @@ import pytest
 from vyper.exceptions import CompilerPanic, NamespaceCollision, UndeclaredDefinition
 from vyper.semantics import environment
 from vyper.semantics.namespace import get_namespace
-from vyper.semantics.types import get_types
+from vyper.semantics.types import PRIMITIVE_TYPES
 
 
 def test_get_namespace():
@@ -22,13 +22,13 @@ def test_builtin_context_manager(namespace):
 
 
 def test_builtin_types(namespace):
-    for key, value in get_types().items():
+    for key, value in PRIMITIVE_TYPES.items():
         assert namespace[key] == value
 
 
 def test_builtin_types_persist_after_clear(namespace):
     namespace.clear()
-    for key, value in get_types().items():
+    for key, value in PRIMITIVE_TYPES.items():
         assert namespace[key] == value
 
 
diff --git a/tests/functional/semantics/types/test_type_from_abi.py b/tests/functional/semantics/types/test_type_from_abi.py
index c1606d23..be021f69 100644
--- a/tests/functional/semantics/types/test_type_from_abi.py
+++ b/tests/functional/semantics/types/test_type_from_abi.py
@@ -1,7 +1,7 @@
 import pytest
 
 from vyper.exceptions import UnknownType
-from vyper.semantics.types import SArrayT, get_primitive_types
+from vyper.semantics.types import PRIMITIVE_TYPES, SArrayT
 from vyper.semantics.types.utils import type_from_abi
 
 BASE_TYPES = ["int128", "uint256", "bool", "address", "bytes32"]
@@ -9,7 +9,7 @@ BASE_TYPES = ["int128", "uint256", "bool", "address", "bytes32"]
 
 @pytest.mark.parametrize("type_str", BASE_TYPES)
 def test_base_types(type_str):
-    base_t = get_primitive_types()[type_str]
+    base_t = PRIMITIVE_TYPES[type_str]
     type_t = type_from_abi({"type": type_str})
 
     assert base_t == type_t
@@ -17,7 +17,7 @@ def test_base_types(type_str):
 
 @pytest.mark.parametrize("type_str", BASE_TYPES)
 def test_base_types_as_arrays(type_str):
-    base_t = get_primitive_types()[type_str]
+    base_t = PRIMITIVE_TYPES[type_str]
     type_t = type_from_abi({"type": f"{type_str}[3]"})
 
     assert type_t == SArrayT(base_t, 3)
@@ -25,7 +25,7 @@ def test_base_types_as_arrays(type_str):
 
 @pytest.mark.parametrize("type_str", BASE_TYPES)
 def test_base_types_as_multidimensional_arrays(type_str):
-    base_t = get_primitive_types()[type_str]
+    base_t = PRIMITIVE_TYPES[type_str]
 
     type_t = type_from_abi({"type": f"{type_str}[3][5]"})
 
diff --git a/tests/functional/semantics/types/test_type_from_annotation.py b/tests/functional/semantics/types/test_type_from_annotation.py
index c308c126..200d2bbc 100644
--- a/tests/functional/semantics/types/test_type_from_annotation.py
+++ b/tests/functional/semantics/types/test_type_from_annotation.py
@@ -6,7 +6,7 @@ from vyper.exceptions import (
     StructureException,
     UndeclaredDefinition,
 )
-from vyper.semantics.types import HashMapT, SArrayT, get_primitive_types
+from vyper.semantics.types import PRIMITIVE_TYPES, HashMapT, SArrayT
 from vyper.semantics.types.utils import type_from_annotation
 
 BASE_TYPES = ["int128", "uint256", "bool", "address", "bytes32"]
@@ -16,7 +16,7 @@ BYTESTRING_TYPES = ["String", "Bytes"]
 @pytest.mark.parametrize("type_str", BASE_TYPES)
 def test_base_types(build_node, type_str):
     node = build_node(type_str)
-    base_t = get_primitive_types()[type_str]
+    base_t = PRIMITIVE_TYPES[type_str]
 
     ann_t = type_from_annotation(node)
 
@@ -26,7 +26,7 @@ def test_base_types(build_node, type_str):
 @pytest.mark.parametrize("type_str", BYTESTRING_TYPES)
 def test_array_value_types(build_node, type_str):
     node = build_node(f"{type_str}[1]")
-    base_t = get_primitive_types()[type_str](1)
+    base_t = PRIMITIVE_TYPES[type_str](1)
 
     ann_t = type_from_annotation(node)
 
@@ -36,7 +36,7 @@ def test_array_value_types(build_node, type_str):
 @pytest.mark.parametrize("type_str", BASE_TYPES)
 def test_base_types_as_arrays(build_node, type_str):
     node = build_node(f"{type_str}[3]")
-    base_t = get_primitive_types()[type_str]
+    base_t = PRIMITIVE_TYPES[type_str]
 
     ann_t = type_from_annotation(node)
 
@@ -54,7 +54,7 @@ def test_array_value_types_as_arrays(build_node, type_str):
 @pytest.mark.parametrize("type_str", BASE_TYPES)
 def test_base_types_as_multidimensional_arrays(build_node, namespace, type_str):
     node = build_node(f"{type_str}[3][5]")
-    base_t = get_primitive_types()[type_str]
+    base_t = PRIMITIVE_TYPES[type_str]
 
     ann_t = type_from_annotation(node)
 
@@ -75,7 +75,7 @@ def test_invalid_index(build_node, idx, type_str):
 @pytest.mark.parametrize("type_str2", BASE_TYPES)
 def test_mapping(build_node, type_str, type_str2):
     node = build_node(f"HashMap[{type_str}, {type_str2}]")
-    types = get_primitive_types()
+    types = PRIMITIVE_TYPES
 
     ann_t = type_from_annotation(node)
 
@@ -89,7 +89,7 @@ def test_mapping(build_node, type_str, type_str2):
 @pytest.mark.parametrize("type_str2", BASE_TYPES)
 def test_multidimensional_mapping(build_node, type_str, type_str2):
     node = build_node(f"HashMap[{type_str}, HashMap[{type_str}, {type_str2}]]")
-    types = get_primitive_types()
+    types = PRIMITIVE_TYPES
 
     ann_t = type_from_annotation(node)