In some cases, the value of Uverse is incomplete [WIP]

[thehowl]

WIP is the bug report, as we haven't fully finished investigating; but I'm opening this bug report to get some eyes on this...

Symptoms of the bug

In pull request #2040, @ajnavarro disabled the GnoVM benchmarks, as one of them was causing a panic:

https://github.com/gnolang/gno/pull/2040/files#diff-eff7bc5631d991a2e20f1a1ebbd6b16d7ccdcffe4a6284b817a99aafb5daed3c

However, what's curious about this panic is that it happens only when you run all the benchmarks... not just the single BenchmarkBenchdata set.

This is the panic message:

panic: runtime error: index out of range [31] with length 25 [recovered]
        panic: runtime error: index out of range [31] with length 25:
--- preprocess stack ---
stack 2: func id(sz (const-type int))  [][](const-type int) { r<VPBlock(1,2)> := make<VPUverse(0)>([][]int<VPUverse(0)>, sz<VPUverse(0)>); for i<VPUverse(0
)> := range r<VPUverse(0)> { r<VPUverse(0)>[i<VPUverse(0)>] = make<VPUverse(0)>([]int<VPUverse(0)>, sz<VPUverse(0)>); r<VPUverse(0)>[i<VPUverse(0)>][i<VPUv
erse(0)>] = 1 }; return r<VPUverse(0)> }
...
1: running [Created by testing.(*B).run1 in goroutine 11 @ benchmark.go:208]
    gnolang preprocess.go:172  Preprocess.func1.1()
            panic.go:770       panic(any{0xaff2c0, 0xc000124138})
    gnolang values.go:2336     (*Block).GetPointerToInt(...)
    gnolang values.go:2366     (*Block).GetPointerTo(*Block(0xeb0367e379406e0d), Store{0x0, 0x0}, ValuePath{0x0, 0x0, 0x0, #8, 0x0})
    gnolang values.go:861      (*PackageValue).GetValueAt(*PackageValue(0xc0000fdee0), Store{0x0, 0x0}, ValuePath{0x92, 0x15, 0x3a12, #8, 0x4})
    gnolang nodes.go:1674      (*StaticBlock).GetStaticTypeOf(*StaticBlock(0xc0000db028), Store{0x0, 0x0}, Name{#8, 0x4})
    gnolang preprocess.go:3363 fillNameExprPath(BlockNode{0xd0eac0, #5}, *NameExpr(#3), true)
    gnolang preprocess.go:703  Preprocess.func1(Store{#4, 0x4, 0x20}, BlockNode(0x3), Node(#1), 0x3)
    gnolang transcribe.go:728  transcribe(Transform(#6), []Node(0x4 len=32 cap=3), TransField(0x0), 824634474144, Node{0xc0000ff117, <nil>})
    gnolang transcribe.go:162  transcribe(Transform(#6), []Node(0x3 len=32 cap=36), TransField(0x0), 824634427456, Node{0xc0000ff397, <nil>})
    gnolang transcribe.go:371  transcribe(Transform(#6), []Node(0x2 len=32 cap=70), TransField(0x0), 824634427552, Node{0xc0000ff617, <nil>})
    gnolang transcribe.go:670  transcribe(Transform(#6), []Node(0x1 len=32 cap=77), TransField(0x1), 824634617864, Node{0xc0000ff897, <nil>})
    gnolang transcribe.go:708  transcribe(Transform(#6), []Node(0x0 len=32 cap=0), TransField(0x0), 824636837640, Node{0xc0000ffb17, <nil>})
    gnolang transcribe.go:133  Transcribe(Node{#2, #9}, Transform(#6))
    gnolang preprocess.go:147  Preprocess(Store{0xd11938, 0xc000034120}, BlockNode{0xd0e6c0, 0xc000294308}, Node{#2, #9})
    gnolang machine.go:534     (*Machine).runFiles(*Machine(0xc00021e000), *FileNode(0xc00008c118), *FileNode(0x1), *FileNode(0x1))
    gnolang machine.go:489     (*Machine).RunFiles(...)
    gnolang gno_test.go:471    BenchmarkBenchdata.func1(*B(#7))
    testing benchmark.go:193   (*B).runN(*B(#7), 1)
    testing benchmark.go:215   (*B).run1.func1()
exit status 2
FAIL    github.com/gnolang/gno/gnovm/pkg/gnolang        8.056s
?       github.com/gnolang/gno/gnovm/pkg/gnolang/pb     [no test files]
FAIL

When was it introduced?

We started digging... Luckily, the original commit where the benchmarks were introduced did not show this panic; which meant that it was time for git bisect to shine; which pointed to this commit: 52485ce

Now, obviously this is a bit weird... I tried changing up the uverse initialization, first of all to instead of using a simple singleton pattern:

func UverseNode() *PackageNode {
	// Global is singleton.
	if uverseNode != nil {
		return uverseNode
	}

To using sync.Once to guard the creation of uverseNode/uverseValue; this way we could make sure that once the functions return the values are fully "finalized".

var (
	uverseNode  *PackageNode
	uverseValue *PackageValue
	uverseOnce sync.Once
)

const uversePkgPath = ".uverse"

// Always returns a new copy from the latest state of source.
func Uverse() *PackageValue {
	uverseOnce.Do(makeUverse)
	return uverseValue
}

// Always returns the same instance with possibly differing completeness.
func UverseNode() *PackageNode {
	uverseOnce.Do(makeUverse)
	return uverseNode
}

func makeUverse() {
	// NOTE: uverse node is hidden, thus the leading dot in pkgPath=".uverse".
	uverseNode = NewPackageNode("uverse", uversePkgPath, nil)

	// temporary convenience functions.
	def := func(n Name, tv TypedValue) {
		uverseNode.Define(n, tv)
	}
	defNative := uverseNode.DefineNative

...

	uverseValue = uverseNode.NewPackage()
	return 
}

However this resulted in a deadlock; because, as crazy as it may be, Uverse generation depends on itself.

The fault is not entirely on isUverseName; its usages to avoid using reserved identifiers can be overcome by making sure, before calling it, that packageOf(last).PkgPath != uversePkgPath. However, this doesn't address the ultimate problem: that uverse generation depends on itself; there are other dependency chains which eventually make Uverse() generation result in a deadlock.

The changes showing this error can be found on this branch

How can we proceed?

I think it's important that Uverse doesn't depend on itself when initialising; but DefineNative (which it extensively uses) uses Preprocess to get type information, which uses evalStaticTypeOf, which initializes a throwaway Machine, which when setting up the store wants to pre-set Uverse() in its cached packages.

What we want:

• The result of Uverse and UverseNode should always be the same, regardless of where they are first called
• As such, it cannot depend on itself (as it would necessarily yield a partial result when getting its value "half-way")
• Additionally, as we're talking about a program global, it is susceptible to race conditions; thus calling it with a thread-safe mechanism like sync.Once is preferable.

How does it tie back to the original panic message?

Working theory:

Uverse() is called while initializing UverseNode itself (yeah -- anyway...) and this sets its global value uverseValue to the value in that moment. i.e.: the result of UverseNode is incomplete when Uverse is called, and as such contains an incomplete list of values which is stored permanently in uverseValueThus, we get back to our original panic message: index out of range [31] with length 25
My theory is that a name of a builtin/uverse function is resolved through the UverseNode in preprocessing, so it's changed to a ValuePath (with index 31); but then, when the program reaches execution, it tries to get the Uverse value 31 from the Uverse PackageValue; but because it was "cached prematurely", it stops at 25 elements and doesn't have what we're looking for

Bad workarounds which cannot be considered solutions

... but may still be useful to show the problem.

Substituting the code of Uverse with the following:

func Uverse() *PackageValue {
	return UverseNode().NewPackage()
}

Resolves the problem, however it is terribly inefficient.

Doing this at the beginning of BenchmarkBenchdata:

func BenchmarkBenchdata(b *testing.B) {
	uverseValue = nil

... also solves the problem, as uverseValue will have to be re-initialized.

[deelawn]

Is this just a problem when the machine is being initialized? If the issue lies in the check whether something is a uverse name during uverse initialization, and we know what the values will be by the time initialization is complete, maybe a naive solution such as this would work. It can be cleaned up, but here is the basic idea.
https://github.com/gnolang/gno/compare/master...deelawn:bug/uverse-def?expand=1

[jaekwon]

Maybe we should split Uverse initialization into two steps; the first where the uverse default types like "int" are set,
and then after Uverse is created, define the native functions which depend on those types.

[ltzmaxwell]

• The direct cause of this issue is :
  Uverse() generates an incomplete uverseValue, which persists unchanged and is globally utilized.

• In this particular scenario, BenchmarkPreprocess initiates preprocess, which in turn triggers UverseNode() and immediately calls Uverse(), resulting in the creation of a uverseValue based on an incomplete state of uverseNode. This incomplete uverseValue is then employed as a global variable, remaining static as Uverse() functions as a singleton and does not update the value, and utilized by BenchmarkBenchdata, thereby contributing to this issue .(if you only run BenchmarkBenchdata things will be good).

• A simple workaround can be something like:

func Uverse() *PackageValue {
       // always get a new value if not complete
	if uverseValue == nil || incompleteUverseNode{
		uverseValue = UverseNode().NewPackage()
	}
	return uverseValue
}

⚠️ Not sure if it mask anything, it works tho, thinking...