argotorg / argotorg/fe

Loop bounds with const generics

Open
#658 0 comments 0 reactions 0 assignees View on GitHub
type: RFC / discussion / question
Dominant language
Rust
Stars
1.7k
Forks
218
Avg merge
1d 7h
Merged PRs (30d)
6

Description

We've discussed this before, but there isn't an issue tracking it. The motivation is to eliminate out-of-gas (OOG) exceptions by providing reasonable upper bounds on gas usage.

In the example below, we implement `contains` on an array type using binary search. The looping part of the binary search is given a const generic parameter, which limits the number of iterations. If the loop fails to exit before hitting the iteration limit, then it would revert. But since the time complexity of binary search is `O(log n)`, we know this won't happen.

```python
struct SortedArray:
...

pub fn contains(self, elem: T) -> bool:
var l = 0
var r = SIZE - 1

# `log2(SIZE)` limits the number of iterations and is evaluated at compile-time
loop<{ log2(SIZE) }>:
if l > r:
return false

let m = (l + r) / 2

if self[m] < elem:
l = m + 1
else if self[m] > elem:
r = m + 1
else:
return true

fn log2(n: u256) -> u256:
var x = 0

loop:
if 2 ^ x >= n:
return x
else:
x += 1
```

Contributor guide

No contributing guide indexed for this repository

Research direction

The issue names no files, tests, or entry points; begin by tracing how loop syntax and const generic parameters are represented and checked in the compiler. Done means supporting a compile-time loop bound such as log2(SIZE), enforcing the iteration limit, and reverting when the bound is exhausted without an early exit.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.