Add Guardrails Around Recursive by-Reference Subroutines

[tzaffi]

Problem: Passing Local ScratchVars Inside Subroutines By Reference Recursively DOES NOT WORK

Consider the following PyTeal Code

From a purely mathemetical perspective, it is a valid way to compute the factorial of n: n!

    @Subroutine(TealType.none)
    def factorial_BAD(n: ScratchVar):
        tmp = ScratchVar(TealType.uint64)
        return (
            If(n.load() <= Int(1))
            .Then(n.store(Int(1)))
            .Else(
                Seq(
                    tmp.store(n.load() - Int(1)),
                    factorial_BAD(tmp),
                    n.store(n.load() * tmp.load()),
                )
            )
        )

    # approval program:
    def fac_by_ref_BAD():
        n = ScratchVar(TealType.uint64)
        return Seq(
            n.store(Int(10)),
            factorial_BAD(n),
            n.load(),
        )

Generated TEAL:

#pragma version 6
int 10
store 0
int 0
callsub factorialBAD_0
load 0
return

// factorial_BAD
factorialBAD_0:
store 1
load 1
loads
int 1
<=
bnz factorialBAD_0_l2
load 1
loads
int 1
-
store 2
int 2
load 1
load 2
uncover 2
callsub factorialBAD_0
store 2
store 1
load 1
load 1
loads
load 2
*
stores
b factorialBAD_0_l3
factorialBAD_0_l2:
load 1
int 1
stores
factorialBAD_0_l3:
retsub

Dry Run Results:

Instead of computing 10!, only the first product 10*9 == 90 is computed:

App Messages: ['ApprovalProgram', 'PASS']
App Logs: None
App Trace:
pc# line# source           stack
   1    1 intcblock 1      []
   4    2 pushint 10       []
...
  64   39 retsub           []
  13    6 load 0           []
  15    7 return           [90]
  65   40                  [90]

But, we CAN MODIFY the Above to Only Pass Through Subroutine Parameters Var's By-Reference

And then everything works!

PyTeal:

    @Subroutine(TealType.none)
    def factorial(n: ScratchVar):
        tmp = ScratchVar(TealType.uint64)
        return (
            If(n.load() <= Int(1))
            .Then(n.store(Int(1)))
            .Else(
                Seq(
                    tmp.store(n.load()),
                    n.store(n.load() - Int(1)),
                    factorial(n),
                    n.store(n.load() * tmp.load()),
                )
            )
        )

    # approval program:
    def fac_by_ref():
        n = ScratchVar(TealType.uint64)
        return Seq(
            n.store(Int(10)),
            factorial(n),
            n.load(),
        )

Generated TEAL

#pragma version 6
int 10
store 0
int 0
callsub factorial_0
load 0
return

// factorial
factorial_0:
store 1
load 1
loads
int 1
<=
bnz factorial_0_l2
load 1
loads
store 2
load 1
load 1
loads
int 1
-
stores
load 1
load 1
load 2
uncover 2
callsub factorial_0
store 2
store 1
load 1
load 1
loads
load 2
*
stores
b factorial_0_l3
factorial_0_l2:
load 1
int 1
stores
factorial_0_l3:
retsub

Dry Run Results

App Messages: ['ApprovalProgram', 'PASS']
App Logs: None
App Trace:
pc# line# source           stack
...
  70   43 retsub           []
  13    6 load 0           []
  15    7 return           [3628800]
  71   44                  [3628800]

Solution:

1. Raise a TealInputError When a Local ScratchVar inside a Subroutine is passed into another Subroutine
2. Verify via Semantic E2E Tests on tons of use cases, that correctly structured programs work as expected

Dependencies

#214 (No. 2 only). Certainly Goal No. 1 can go in as a separate PR.

Urgency

Medium to High: We don't want PyTeal users to shoot themselves in the foot. On the other hand, I'm not sure how often PyTeal users would be using the brand new capability of passing by-ref which was only introduced 3/1/2022 (#183 ).

[tzaffi]

For #2 what do I mean by "tons of use cases"? Here are a few examples:

• factorial
• fibonacci
• swap
• map over a bytes variable
• reverse
• arithmetic operators such as:
  • multiplication defined from addition
  • exponentiation defined from multiplication
• euclidean algorithm

[jasonpaulos]

Here's an example of the same issue in Go (and on the playground: https://go.dev/play/p/3j78XGRwHX6)

package main

import "fmt"

func main() {

	var tmp uint64
	var factorial func(n *uint64)
	factorial = func(n *uint64) {
		if *n <= 1 {
			*n = 1
		} else {
			tmp = *n - 1
			factorial(&tmp)
			*n = *n * tmp
		}
	}

	n := uint64(4)
	factorial(&n)
	fmt.Println(n)
}

I had to make tmp a "global" variable to the factorial function in order to simulate the behavior of local variables in PyTeal subroutines.

You'll notice this code also fails to work properly, which I take as further support for the proposed restriction. (Note that the Go code produces different "wrong" results than the "wrong" PyTeal code, since PyTeal also messes with spilling and loading local scratch slots when invoking a recursive subroutine).

[tzaffi]

I'm wondering if non-chain-recursive pass-by-ref calls from inside a subroutine to another would still work? It might be only that in a recursive chain we end up having an issue. It's worth investigating this as well. Some of the examples above could probably nudged to test this situation.

[michaeldiamant]

Closing - See #242 for rationale.

[tzaffi]

closed since this has been released