Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

for loops maintain the same block on iteration, which is referenced in any closures generated within #1135

Closed
thehowl opened this issue Sep 16, 2023 · 7 comments
Assignees
Labels
🐞 bug Something isn't working 📦 🤖 gnovm Issues or PRs gnovm related

Comments

@thehowl
Copy link
Member

thehowl commented Sep 16, 2023

title might be confusing, but here's the example:

package main

func main() {
        var fns []func()
        for _, v := range []int{1, 2, 3} {
                x := v*100 + v
                fns = append(fns, func() { println(x) })
        }
        for _, fn := range fns {
                fn()
        }
}

(the x := declaration is used to demonstrate that this does not reference v, whereby the behaviour talked about here would actually be correct in the current go specification, though this is due to change in go1.22)

go behaviour (expected):

101
202
303

gno behaviour:

303
303
303
@ltzmaxwell
Copy link
Contributor

I have a fix in #1585, it works like this:

package main

func main() {
	var fns []func()
	for _, v := range []int{1, 2, 3} {
		x := v*100 + v
		fns = append(fns, func() { println(x) })
	}
	for _, fn := range fns {
		fn()
	}
}

// Output:
// 101
// 202
// 303

@petar-dambovaliev
Copy link
Contributor

petar-dambovaliev commented Mar 18, 2024

Closures should perform late binding on captured variables.
The values should be resolved when the closure is executed, not when it is created.
For this to happen, we need to capture by *T and the value can be ad-hoc unwrapped so we keep the T semantics.
A new type representing this should be created, which should looks something like

//Upvalue is a name for captured variables in Lua VM
type Upvalue struct {
   val *PointerValue
}

@jaekwon

Example by @ltzmaxwell that currently doesn't work

package main

func main() {
	var fns []func() int

	for i := 0; i < 5; i++ {
		x := i
		f := func() int {
			return x
		}
		fns = append(fns, f)
		x += 1
	}
	for _, fn := range fns {
		println(fn())
	}
}

// Output:
// 0
// 1
// 2
// 3
// 4

the outcome should be 1,2,3,4,5, while now get 0,1,2,3,4.

@deelawn
Copy link
Contributor

deelawn commented Apr 10, 2024

Putting this here for reference. Here are the attempts to fix this that have not been merged: #1768, #1585, deelawn#3

This is the one currently in progress: #1780

@ltzmaxwell
Copy link
Contributor

ltzmaxwell commented Apr 10, 2024

Putting this here for reference. Here are the attempts to fix this that have not been merged: #1768, #1585, deelawn#3

This is the one currently in progress: #1780

the latest attempt: #1818. #1780 has been proved not suitable for all scenarios.

@Kouteki
Copy link
Contributor

Kouteki commented May 15, 2024

@ltzmaxwell do we close #1818 or do you want to iterate on it?

@ltzmaxwell
Copy link
Contributor

@ltzmaxwell do we close #1818 or do you want to iterate on it?

it's actually ready for review. thanks.

@linear linear bot removed 🐞 bug Something isn't working 📦 🤖 gnovm Issues or PRs gnovm related labels Sep 11, 2024
@zivkovicmilos zivkovicmilos added 🐞 bug Something isn't working 📦 🤖 gnovm Issues or PRs gnovm related 🌟 must have 🌟 labels Sep 12, 2024
ltzmaxwell added a commit that referenced this issue Oct 22, 2024
# Problem Definition

The problem originates from the issue described in
[#1135](#1135). While the full
scope of the issue is broader, it fundamentally relates to the concept
of loop variable escapes block where it's defined.

e.g. 1:
```go
package main

import "fmt"

var s1 []*int

func forLoopRef() {
	defer func() {
		for i, e := range s1 {
			fmt.Printf("s1[%d] is: %d\n", i, *e)
		}
	}()

	for i := 0; i < 3; i++ {
		z := i + 1
		s1 = append(s1, &z)
	}
}

func main() {
	forLoopRef()
}
```

e.g. 2:
```go
package main

type f func()

var fs []f

func forLoopClosure() {
	defer func() {
		for _, f := range fs {
			f()
		}
	}()

	for i := 0; i < 3; i++ {
		z := i
		fs = append(fs, func() { println(z) })
	}
}

func main() {
	forLoopClosure()
}
```

e.g. 3:
```go
package main

func main() {
	c := 0
	closures := []func(){}
loop:
	i := c
	closures = append(closures, func() {
		println(i)
	})
	c += 1
	if c < 10 {
		goto loop
	}

	for _, cl := range closures {
		cl()
	}
}
```



# Solution ideas

- **identify escaped vars in preprocess**:
Detect situations where a loop variable is defined within a loop
block(including `for/range` loops or loops constructed using `goto`
statements), and escapes the block where it's defined.

- **runtime allocation**:
Allocate a new heap item for the loop variable in each iteration to
ensure each iteration operates with its unique variable instance.

- **NOTE1**: this is consistent with Go's Strategy:
"Each iteration has its own separate declared variable (or variables)
[Go 1.22]. The variable used by the first iteration is declared by the
init statement. The variable used by each subsequent iteration is
declared implicitly before executing the post statement and initialized
to the value of the previous iteration's variable at that moment."

- **NOTE2**: the `loopvar` feature of Go 1.22 is not supported in this
version, and will be supported in next version.

    not supporting capture `i` defined in for/range clause;
```go
	for i := 0; i < 3; i++ {
		s1 = append(s1, &i)
	}
```

# Implementation Details

**Preprocess Stage(Multi-Phase Preprocessor)**:

- **Phase 1: `initStaticBlocks`**: Establish a cascading scope structure
where `predefine` is conducted. In this phase Name expressions are
initially marked as `NameExprTypeDefine`, which may later be upgraded to
`NameExprTypeHeapDefine` if it is determined that they escape the loop
block. This phase also supports other processes as a
prerequisite[#2077](#2077).
   
- **Phase 2: `preprocess1`**: This represents the original preprocessing
phase(not going into details).
   
- **Phase 3: `findGotoLoopDefines`**: By traversing the AST, any name
expression defined in a loop block (for/range, goto) with the attribute
`NameExprTypeDefine` is promoted to `NameExprTypeHeapDefine`. This is
used in later phase.
   
- **Phase 4: `findLoopUses1`**: Identify the usage of
`NameExprTypeHeapDefine` name expressions. If a name expression is used
in a function literal or is referrnced(e.g. &a), and it was previously
defined as `NameExprTypeHeapDefine`, the `used` name expression is then
given the attribute `NameExprTypeHeapUse`. This step finalizes whether a
name expression will be allocated on the heap and used from heap.
`Closures` represent a particular scenario in this context. Each
closure, defined by a funcLitExpr that captures variables, is associated
with a HeapCaptures list. This list consists of NameExprs, which are
utilized at runtime to obtain the actual variable values for each
iteration. Correspondingly, within the funcLitExpr block, a list of
placeholder values are defined. These placeholders are populated during
the doOpFuncLit phase and subsequently utilized in the `doOpCall` to
ensure that each iteration uses the correct data.


- **Phase 5: `findLoopUses2`**: Convert non-loop uses of loop-defined
names to `NameExprTypeHeapUse`. Also, demote `NameExprTypeHeapDefine`
back to `NameExprTypeDefine` if no actual usage is found. Also , as the
last phase, attributes no longer needed will be cleaned up after this
phase.

**Runtime Stage**:

1. **Variable Allocation**:
- Modify the runtime so that encountering a `NameExprTypeHeapDefine`
triggers the allocation of a new `heapItemValue` for it, which will be
used by any `NameExprTypeHeapUse`.

2. **Function Literal Handling**:
- During the execution of `doOpFuncLit`, retrieve the `HeapCapture`
values (previously allocated heap item values) and fill in the
placeholder values within the `funcLitExpr` block.
- When invoking the function (`doOpCall`), the `placeHolder`
values(fv.Captures) are used to update the execution context, ensuring
accurate and consistent results across iterations.

---------

Co-authored-by: ltzMaxwell <ltz.maxwell@gmail.com>
Co-authored-by: Morgan <morgan@morganbaz.com>
@ltzmaxwell
Copy link
Contributor

close this as solved by #2429. Go1.22 loopvar is not supported at the moment, defer for future optimization. cc: @moul @thehowl @jaekwon for visibility.

@github-project-automation github-project-automation bot moved this from In Progress to Done in 🧙‍♂️gno.land core team Oct 22, 2024
@Kouteki Kouteki added the in focus Core team is prioritizing this work label Oct 28, 2024
@Kouteki Kouteki removed the in focus Core team is prioritizing this work label Nov 4, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
🐞 bug Something isn't working 📦 🤖 gnovm Issues or PRs gnovm related
Projects
8 participants