Unreasonable runtime for contract with complex invalid loop range

[agroce]

Version Information

• vyper Version (output of vyper --version): 0.1.0b13+commit.da6d2a3
• OS: osx
• Python Version (output of python --version): Python 3.7.4
• Environment (output of pip freeze):
  apipkg==1.5
  asttokens==1.1.13
  atomicwrites==1.3.0
  attrdict==2.0.1
  attrs==19.3.0
  base58==1.0.3
  certifi==2019.9.11
  cffi==1.13.1
  chardet==3.0.4
  coverage==4.5.4
  coveralls==1.6.0
  cryptography==2.8
  cytoolz==0.10.0
  docopt==0.6.2
  entrypoints==0.3
  eth-abi==2.0.0b9
  eth-account==0.4.0
  eth-bloom==1.0.3
  eth-hash==0.2.0
  eth-keyfile==0.5.1
  eth-keys==0.3.1
  eth-rlp==0.1.2
  eth-tester==0.1.0b39
  eth-typing==2.1.0
  eth-utils==1.7.0
  ethpm==0.1.4a19
  execnet==1.7.1
  filelock==3.0.12
  flake8==3.7.8
  flake8-bugbear==18.8.0
  hexbytes==0.2.0
  hypothesis==4.11.7
  idna==2.8
  importlib-metadata==0.23
  ipfshttpclient==0.4.12
  isort==4.3.21
  jsonschema==2.6.0
  lru-dict==1.1.6
  mccabe==0.6.1
  more-itertools==7.2.0
  multiaddr==0.0.8
  mypy==0.701
  mypy-extensions==0.4.3
  netaddr==0.7.19
  packaging==19.2
  parsimonious==0.8.1
  pluggy==0.13.0
  protobuf==3.10.0
  py==1.8.0
  py-ecc==1.7.1
  py-evm==0.2.0a42
  pycodestyle==2.5.0
  pycparser==2.19
  pycryptodome==3.9.0
  pyethash==0.1.27
  pyflakes==2.1.1
  pyparsing==2.4.2
  pytest==5.2.1
  pytest-cov==2.4.0
  pytest-xdist==1.18.1
  PyYAML==5.1.2
  requests==2.22.0
  rlp==1.1.0
  semantic-version==2.8.2
  six==1.12.0
  toml==0.10.0
  toolz==0.10.0
  tox==3.14.0
  trie==1.4.0
  typed-ast==1.3.5
  urllib3==1.25.6
  varint==1.0.2
  virtualenv==16.7.7
  vyper==0.1.0b13
  wcwidth==0.1.7
  web3==5.0.0b2
  websockets==7.0
  zipp==0.6.0

What's your issue about?

This contract:

v0: wei_value
@public
def f0():
    for v1 in range(self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0 + self.v0):
        pass

should immediately complain the range is invalid; instead, it runs for hours (total time not known; shrinking the range suggests it's exponential, not an actual infinite loop).

Probably not important, since with a valid constant in a complex expression it compiles quickly, but FYI. Another TSTL-produced contract (https://github.com/agroce/tstl/tree/master/examples/vyper)

How can it be fixed?

Fill this in if you know how to fix it.

[agroce]

Memory use is through the roof, 62+ GB so far (new run for only a few minutes)

[agroce]

In itself uninteresting, but maybe a sign of something that matters

[fubuloubu]

That's a great find, thanks!

[jacqueswww]

Seems to be because of SafeMath

[seq,
  [seq,
    [assert,
      [ge,
        [add,
          [seq,
            [seq,
              [assert,
                [ge,
                  [add,
                    [seq,
                      [seq,
                        [assert,
                          [ge,
                            [add,
                              [sload, 0 <self.v0>],
                              [sload, 0 <self.v0>]],
                            [sload, 0 <self.v0>]]],
                        [add,
                          [sload, 0 <self.v0>],
                          [sload, 0 <self.v0>]]]],
                    [sload, 0 <self.v0>]],
                  [seq,
                    [seq,
                      [assert,
                        [ge,
                          [add,
                            [sload, 0 <self.v0>],
                            [sload, 0 <self.v0>]],
                          [sload, 0 <self.v0>]]],
                      [add,
                        [sload, 0 <self.v0>],
                        [sload, 0 <self.v0>]]]]]],
              [add,
                [seq,
                  [seq,
                    [assert,
                      [ge,
                        [add,
                          [sload, 0 <self.v0>],
                          [sload, 0 <self.v0>]],
                        [sload, 0 <self.v0>]]],
                    [add,
                      [sload, 0 <self.v0>],
                      [sload, 0 <self.v0>]]]],
                [sload, 0 <self.v0>]]]],
          [sload, 0 <self.v0>]],
        [seq,
          [seq,
            [assert,
              [ge,
                [add,
                  [seq,
                    [seq,
                      [assert,
                        [ge,
                          [add,
                            [sload, 0 <self.v0>],
                            [sload, 0 <self.v0>]],
                          [sload, 0 <self.v0>]]],
                      [add,
                        [sload, 0 <self.v0>],
                        [sload, 0 <self.v0>]]]],
                  [sload, 0 <self.v0>]],
                [seq,
                  [seq,
                    [assert,
                      [ge,
                        [add,
                          [sload, 0 <self.v0>],
                          [sload, 0 <self.v0>]],
                        [sload, 0 <self.v0>]]],
                    [add,
                      [sload, 0 <self.v0>],
                      [sload, 0 <self.v0>]]]]]],
            [add,
              [seq,
                [seq,
                  [assert,
                    [ge,
                      [add,
                        [sload, 0 <self.v0>],
                        [sload, 0 <self.v0>]],
                      [sload, 0 <self.v0>]]],
                  [add,
                    [sload, 0 <self.v0>],
                    [sload, 0 <self.v0>]]]],
              [sload, 0 <self.v0>]]]]]],
    [add,
      [seq,
        [seq,
          [assert,
            [ge,
              [add,
                [seq,
                  [seq,
                    [assert,
                      [ge,
                        [add,
                          [sload, 0 <self.v0>],
                          [sload, 0 <self.v0>]],
                        [sload, 0 <self.v0>]]],
                    [add,
                      [sload, 0 <self.v0>],
                      [sload, 0 <self.v0>]]]],
                [sload, 0 <self.v0>]],
              [seq,
                [seq,
                  [assert,
                    [ge,
                      [add,
                        [sload, 0 <self.v0>],
                        [sload, 0 <self.v0>]],
                      [sload, 0 <self.v0>]]],
                  [add,
                    [sload, 0 <self.v0>],
                    [sload, 0 <self.v0>]]]]]],
          [add,
            [seq,
              [seq,
                [assert,
                  [ge,
                    [add,
                      [sload, 0 <self.v0>],
                      [sload, 0 <self.v0>]],
                    [sload, 0 <self.v0>]]],
                [add,
                  [sload, 0 <self.v0>],
                  [sload, 0 <self.v0>]]]],
            [sload, 0 <self.v0>]]]],
      [sload, 0 <self.v0>]]]]

[jacqueswww]

Basically SafeMath has to keep checking the output of the previous calculation, causing a balloon effect.

[agroce]

Aha! I was wondering how a bunch of adds was a bad case here.

The loop presumably isn't needed then?

[fubuloubu]

can confirm (not sure why I did this lol) because of the following:

v0: wei_value
@public
def f0() -> wei_value:
    return self.v0 + self.v0 + ...

Seems like a good solution is to change SafeMath behavior to do the sum and store it in a variable (a temporary one if needed, because in this scenario all of the variables are being overwritten), and compare it to one of the "free" operands at the end of the sum (then commit and drop the temporary to the final result, if required).

Makes me wonder if Solidity would suffer from the same compiler error when using SafeMath...

[fubuloubu]

actually, scratch that because it would open a scenario where and overflow is possible anyways, just do it peicemeal in a different fashion:

a + a + a + a + a + a + a + ... = (...((((((a + a) + a) + a) + a) + a) + a) + a) + ...

[charles-cooper]

Well it has to do with how addition is constructed in expr.py. In https://github.com/ethereum/vyper/blob/f3b0b5e865572e2a64503c0fcc84dc2b03af1149/vyper/parser/expr.py#L526-L530
, the argument gets repeated, resulting in a data structure with exponential size. When I replace them with variables using with, the pathological performance disappears. It's probably better gas-wise to use variables anyways.

[charles-cooper]

You can see what I did in #1661. There are other places which might need similar treatment so I left the PR as WIP.

[agroce]

By the way, other than CompilerPanic and Fatal, are there any tell-tale strings I should look for in Vyper run output that likely indicate a crash/bug?