Repository: algorand/pyteal (language: python)

Issue:
Pass-by-Ref / Dynamic Scratch Variables via the `loads` and `stores` opcodes
# Dynamic Scratch Variables

## New Capabilities
This PR aims to allow dynamically-indexed scratch variables. For example here are some nice-to-have examples:

### Pass-by-Reference Semantics
You can see the resulting teal (including my comments) [here](https://github.com/algorand/pyteal/blob/f67947a0916357766c424db1dbe6c64d4b3983e9/tests/teal/swapper_expected.teal).
```python
@Subroutine(TealType.none)
def swap(x: ScratchVar, y: ScratchVar):
    z = ScratchVar(TealType.anytype)
    return Seq(
        z.store(x.load()),
        x.store(y.load()),
        y.store(z.load()),
    )
```

### Use a Dynamic ScratchVar to "iterate" over other ScratchVar's

You can see the resulting [teal with comments](https://github.com/algorand/pyteal/blob/f67947a0916357766c424db1dbe6c64d4b3983e9/tests/teal/wilt_the_stilt_expected.teal) here.
```python
def wilt_the_stilt():
    player_score = DynamicScratchVar(TealType.uint64)

    wilt = ScratchVar(TealType.uint64, 129)
    kobe = ScratchVar(TealType.uint64)
    dt = ScratchVar(TealType.uint64, 131)

    return Seq(
        player_score.set_index(wilt),
        player_score.store(Int(100)),
        player_score.set_index(kobe),
        player_score.store(Int(81)),
        player_score.set_index(dt),
        player_score.store(Int(73)),
        Assert(player_score.load() == Int(73)),
        Assert(player_score.index() == Int(131)),
        player_score.set_index(wilt),
        Assert(player_score.load() == Int(100)),
        Assert(player_score.index() == Int(129)),
        Int(100),
    )
```


## Other improvements
I've also introduced another way to run end-to-end tests. The script `tests/pass_by_ref_test.py` works as follows:

* iterates over a list of PyTEAL approval functions defined in the file
* compiles the program and saves into `tests/teal` with a file name that is dynamically generated from the approval program function name
* loads pre-compiled companion TEAL with an extra `_expected` suffix in the filename
* compares the just-compiled TEAL against the expected TEAL line by line. The expected TEAL can have extra information -such as comments- but they have to start out exactly the same for the test to pass

## Testing
* Unit tests have been added to:
  * `pyteal/ast/scratch_test.py`
  * `pyteal/ast/scratchvar_test.py`
  * `pyteal/ast/subroutine_test.py`
* The end to end test `tests/pass_by_ref_test.py` has been added
* Temporary PR #203 runs all the backwards compatible tests in `tests/pass_by_ref_test.py` to ensure that the generated TEAL hasn't changes due to this PR

## Summary of Changes
* Various `__init__*`'s
  * To bubble up the visibility of the new `DynamicScratchVar` and make **mypy** happy
  * Also, modified `scripts/generate_init.py` now sorts and uniquifies `__all__`
* Resolve `mypy` complaints:
  * `pyteal/ast/multi_test.py`
* pyteal/ast/scratch.py: 
  * ability to query a slot's index at runtime via the new `ScratchIndex` class and various `index()` methods
* `pyteal/ast/scratchvar.py` - new `DynamicScratchIndex` class that allows subroutines to access and modify external `ScratchVar`'s and also allows it to act as an "iterator" over pre-existing `ScratchVar`'s. It uses the `loads` and `stores` op codes in order to achieve its capabilities.
* `pyteal/ast/subroutine.py` - modify the to allow pass-by-reference semantics
  * `SubroutineDefinition` now:
    * has a `by_ref_args` member set so one can tell if an argument is meant to be by-reference or by-value
    * allows `return` types to be any subtype of `Expr`, not just `Expr`
    * allows argument types to be `ScratchVar`'s in addition to the previous `Expr`
    * has a new `arguments()` method
  * `SubroutineCall` now can handle by-ref arguments, by detecting such arguments and calling their new `.index()` method to pass their index on the stack, instead of their value
  * `SubroutineDeclaration` now can handle by-ref arguments as well. **THIS IS THE TRICKIEST PART OF THE PR**. The code changes are deceptively small. There are some new comments which attempt to explain the goings on.
* New end-to-end test `tests/pass_by_ref_test.py`
  * Various expected outputs of compilation `tests/teal/*_expected.py`
Pass-by-Ref / Dynamic Scratch Variables via the `loads` and `stores` opcodes
# Dynamic Scratch Variables

## New Capabilities
This PR aims to allow dynamically-indexed scratch variables. For example here are some nice-to-have examples:

### Pass-by-Reference Semantics
You can see the resulting teal (including my comments) [here](https://github.com/algorand/pyteal/blob/f67947a0916357766c424db1dbe6c64d4b3983e9/tests/teal/swapper_expected.teal).
```python
@Subroutine(TealType.none)
def swap(x: ScratchVar, y: ScratchVar):
    z = ScratchVar(TealType.anytype)
    return Seq(
        z.store(x.load()),
        x.store(y.load()),
        y.store(z.load()),
    )
```

### Use a Dynamic ScratchVar to "iterate" over other ScratchVar's

You can see the resulting [teal with comments](https://github.com/algorand/pyteal/blob/f67947a0916357766c424db1dbe6c64d4b3983e9/tests/teal/wilt_the_stilt_expected.teal) here.
```python
def wilt_the_stilt():
    player_score = DynamicScratchVar(TealType.uint64)

    wilt = ScratchVar(TealType.uint64, 129)
    kobe = ScratchVar(TealType.uint64)
    dt = ScratchVar(TealType.uint64, 131)

    return Seq(
        player_score.set_index(wilt),
        player_score.store(Int(100)),
        player_score.set_index(kobe),
        player_score.store(Int(81)),
        player_score.set_index(dt),
        player_score.store(Int(73)),
        Assert(player_score.load() == Int(73)),
        Assert(player_score.index() == Int(131)),
        player_score.set_index(wilt),
        Assert(player_score.load() == Int(100)),
        Assert(player_score.index() == Int(129)),
        Int(100),
    )
```


## Other improvements
I've also introduced another way to run end-to-end tests. The script `tests/pass_by_ref_test.py` works as follows:

* iterates over a list of PyTEAL approval functions defined in the file
* compiles the program and saves into `tests/teal` with a file name that is dynamically generated from the approval program function name
* loads pre-compiled companion TEAL with an extra `_expected` suffix in the filename
* compares the just-compiled TEAL against the expected TEAL line by line. The expected TEAL can have extra information -such as comments- but they have to start out exactly the same for the test to pass

## Testing
* Unit tests have been added to:
  * `pyteal/ast/scratch_test.py`
  * `pyteal/ast/scratchvar_test.py`
  * `pyteal/ast/subroutine_test.py`
* The end to end test `tests/pass_by_ref_test.py` has been added
* Temporary PR #203 runs all the backwards compatible tests in `tests/pass_by_ref_test.py` to ensure that the generated TEAL hasn't changes due to this PR

## Summary of Changes
* Various `__init__*`'s
  * To bubble up the visibility of the new `DynamicScratchVar` and make **mypy** happy
  * Also, modified `scripts/generate_init.py` now sorts and uniquifies `__all__`
* Resolve `mypy` complaints:
  * `pyteal/ast/multi_test.py`
* pyteal/ast/scratch.py: 
  * ability to query a slot's index at runtime via the new `ScratchIndex` class and various `index()` methods
* `pyteal/ast/scratchvar.py` - new `DynamicScratchIndex` class that allows subroutines to access and modify external `ScratchVar`'s and also allows it to act as an "iterator" over pre-existing `ScratchVar`'s. It uses the `loads` and `stores` op codes in order to achieve its capabilities.
* `pyteal/ast/subroutine.py` - modify the to allow pass-by-reference semantics
  * `SubroutineDefinition` now:
    * has a `by_ref_args` member set so one can tell if an argument is meant to be by-reference or by-value
    * allows `return` types to be any subtype of `Expr`, not just `Expr`
    * allows argument types to be `ScratchVar`'s in addition to the previous `Expr`
    * has a new `arguments()` method
  * `SubroutineCall` now can handle by-ref arguments, by detecting such arguments and calling their new `.index()` method to pass their index on the stack, instead of their value
  * `SubroutineDeclaration` now can handle by-ref arguments as well. **THIS IS THE TRICKIEST PART OF THE PR**. The code changes are deceptively small. There are some new comments which attempt to explain the goings on.
* New end-to-end test `tests/pass_by_ref_test.py`
  * Various expected outputs of compilation `tests/teal/*_expected.py`


Discussion / hints:

Fix patch:
diff --git a/docs/control_structures.rst b/docs/control_structures.rst
index 46cfb26d6..f36eaed36 100644
--- a/docs/control_structures.rst
+++ b/docs/control_structures.rst
@@ -296,9 +296,11 @@ Subroutines
 .. note::
     Subroutines are only available in TEAL version 4 or higher.
 
-A subroutine is section of code that can be called multiple times from within a program. Subroutines
-are PyTeal's equivalent to functions. Subroutines can accept any number of arguments, and these
-arguments must be PyTeal expressions. Additionally, a subroutine may return a single value, or no value.
+A subroutine is section of code that can be called multiple times from within a program. Subroutines are PyTeal's equivalent to functions.  Subroutine constraints include:
+
+* Subroutines accept any number of arguments.
+* Subroutine argument types can be any `Expr` (PyTeal expression) or strictly `ScratchVar` (no subclasses allowed).  PyTeal applies pass-by-value semantics to `Expr` and pass-by-reference to `ScratchVar`.
+* Subroutines return a single value, or no value.
 
 Creating Subroutines
 --------------------
@@ -317,6 +319,24 @@ For example,
         def isEven(i):
             return i % Int(2) == Int(0)
 
+PyTeal applies these parameter type annotation constraints when compiling subroutine definitions:
+
+* :any:`ScratchVar` parameters *require* a type annotation.
+* :any:`Expr` parameters do *not* require a type annotation.  PyTeal implicitly declares unannotated parameter types as :any:`Expr`.
+
+Here's an example illustrating `ScratchVar` parameter declaration with parameter type annotations:
+
+.. code-block:: python
+
+    @Subroutine(TealType.none)
+    def swap(x: ScratchVar, y: ScratchVar):
+        z = ScratchVar(TealType.anytype)
+        return Seq(
+            z.store(x.load()),
+            x.store(y.load()),
+            y.store(z.load()),
+        )
+
 Calling Subroutines
 -------------------
 
diff --git a/docs/scratch.rst b/docs/scratch.rst
index ddb123141..d08a332ea 100644
--- a/docs/scratch.rst
+++ b/docs/scratch.rst
@@ -5,15 +5,15 @@ Scratch Space
 
 `Scratch space <https://developer.algorand.org/docs/reference/teal/specification/#scratch-space>`_
 is a temporary place to store values for later use in your program. It is temporary because any
-changes to scratch space do not persist beyond the current tranasaction. Scratch space can be used
+changes to scratch space do not persist beyond the current transaction. Scratch space can be used
 in both Application and Signature mode.
 
 Scratch space consists of 256 scratch slots, each capable of storing one integer or byte slice. When
 using the :any:`ScratchVar` class to work with scratch space, a slot is automatically assigned to
 each variable.
 
-Writing and Reading
-~~~~~~~~~~~~~~~~~~~~~~
+ScratchVar:  Writing and Reading to/from Scratch Space
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 To write to scratch space, first create a :any:`ScratchVar` object and pass in the :any:`TealType`
 of the values that you will store there. It is possible to create a :any:`ScratchVar` that can store
@@ -22,7 +22,7 @@ that no type checking takes places in this situation. It is also possible to man
 slot ID the compiler should assign the scratch slot to in the TEAL code. If no slot ID is specified,
 the compiler will assign it to any available slot. 
 
-To write or read values, use the corresponding :any:`ScratchVar.store` or :any:`ScratchVar.load` methods.
+To write or read values, use the corresponding :any:`ScratchVar.store` or :any:`ScratchVar.load` methods.  :any:`ScratchVar.store` *must* be invoked before invoking :any:`ScratchVar.load`.
 
 For example:
 
@@ -34,3 +34,25 @@ For example:
         Assert(myvar.load() == Int(5))
     ])
     anotherVar = ScratchVar(TealType.bytes, 4) # assign this scratch slot to slot #4
+
+DynamicScratchVar:  Referencing a ScratchVar
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+:any:`DynamicScratchVar` functions as a pointer to a :any:`ScratchVar` instance.
+
+Reference a :any:`ScratchVar` instance by invoking :any:`DynamicScratchVar.set_index`.  :any:`DynamicScratchVar.set_index` *must* be invoked before using :any:`DynamicScratchVar.load` and :any:`DynamicScratchVar.store`.
+
+Here's an example to motivate usage.  The example shows how a :any:`DynamicScratchVar` updates the *value* of a referenced :any:`ScratchVar` from 7 to 10.
+
+.. code-block:: python
+
+    s = ScratchVar(TealType.uint64)
+    d = DynamicScratchVar(TealType.uint64)
+
+    return Seq(
+        d.set_index(s),
+        s.store(Int(7)),
+        d.store(d.load() + Int(3)),
+        Assert(s.load() == Int(10)),
+        Int(1),
+    )


Test patch:
diff --git a/tests/pass_by_ref_test.py b/tests/pass_by_ref_test.py
index fb9a9a079..acde89b26 100644
--- a/tests/pass_by_ref_test.py
+++ b/tests/pass_by_ref_test.py
@@ -193,7 +193,13 @@ def test_old():
 
 
 if not OLD_CODE_ONLY:
-    NEW_CASES = (sub_logcat_dynamic, swapper, wilt_the_stilt, fac_by_ref, sub_mixed)
+    NEW_CASES = (
+        sub_logcat_dynamic,
+        swapper,
+        wilt_the_stilt,
+        fac_by_ref,
+        sub_mixed,
+    )
 
     def test_swapper():
         compile_and_save(swapper)
diff --git a/tests/teal/user_guide_snippet_dynamic_scratch_var_expected.teal b/tests/teal/user_guide_snippet_dynamic_scratch_var_expected.teal
new file mode 100644
index 000000000..fe74bc0a3
--- /dev/null
+++ b/tests/teal/user_guide_snippet_dynamic_scratch_var_expected.teal
@@ -0,0 +1,17 @@
+#pragma version 6
+int 0
+store 1
+int 7
+store 0
+load 1
+load 1
+loads
+int 3
++
+stores
+load 0
+int 10
+==
+assert
+int 1
+return
\ No newline at end of file
diff --git a/tests/user_guide_test.py b/tests/user_guide_test.py
new file mode 100644
index 000000000..74c4238b7
--- /dev/null
+++ b/tests/user_guide_test.py
@@ -0,0 +1,27 @@
+import pytest
+
+from pyteal import *
+
+from .compile_asserts import assert_new_v_old, compile_and_save
+
+
+def user_guide_snippet_dynamic_scratch_var() -> Expr:
+    """
+    The user guide docs use the test to illustrate `DynamicScratchVar` usage.  If the test breaks, then the user guide docs must be updated along with the test.
+    """
+
+    s = ScratchVar(TealType.uint64)
+    d = DynamicScratchVar(TealType.uint64)
+
+    return Seq(
+        d.set_index(s),
+        s.store(Int(7)),
+        d.store(d.load() + Int(3)),
+        Assert(s.load() == Int(10)),
+        Int(1),
+    )
+
+
+@pytest.mark.parametrize("snippet", [user_guide_snippet_dynamic_scratch_var])
+def test_user_guide_snippets(snippet):
+    assert_new_v_old(snippet)