callsub, retsub

algorand · tsachiherman · May 14, 2021 · Mar 15, 2021 · Mar 19, 2021 · Apr 27, 2021
commit 2d8e22145e0568b36bb3f0a06f71961452e03310
diff --git a/data/transactions/logic/assembler_test.go b/data/transactions/logic/assembler_test.go
@@ -252,6 +252,12 @@ pushint 2000
 int 0
 int 2
 divw
+callsub stuff
+b next
+stuff:
+retsub
+next:
+int 1
 `
 
 var nonsense = map[uint64]string{
@@ -265,7 +271,7 @@ var compiled = map[uint64]string{
 	1: "012008b7a60cf8acd19181cf959a12f8acd19181cf951af8acd19181cf15f8acd191810f01020026050212340c68656c6c6f20776f726c6421208dae2087fbba51304eb02b91f656948397a7946390e8cb70fc9ea4d95f92251d024242047465737400320032013202320328292929292a0431003101310231043105310731083109310a310b310c310d310e310f3111311231133114311533000033000133000233000433000533000733000833000933000a33000b33000c33000d33000e33000f3300113300123300133300143300152d2e0102222324252104082209240a220b230c240d250e230f23102311231223132314181b1c2b1716154000032903494",
 	2: "022008b7a60cf8acd19181cf959a12f8acd19181cf951af8acd19181cf15f8acd191810f01020026050212340c68656c6c6f20776f726c6421208dae2087fbba51304eb02b91f656948397a7946390e8cb70fc9ea4d95f92251d024242047465737400320032013202320328292929292a0431003101310231043105310731083109310a310b310c310d310e310f3111311231133114311533000033000133000233000433000533000733000833000933000a33000b33000c33000d33000e33000f3300113300123300133300143300152d2e0102222324252104082209240a220b230c240d250e230f23102311231223132314181b1c2b171615400003290349483403350222231d4a484848482a50512a63222352410003420000432105602105612105270463484821052b62482b642b65484821052b2106662b21056721072b682b692107210570004848210771004848361c0037001a0031183119311b311d311e311f3120210721051e312131223123312431253126312731283129312a312b312c312d312e312f",
 	3: "032008b7a60cf8acd19181cf959a12f8acd19181cf951af8acd19181cf15f8acd191810f01020026050212340c68656c6c6f20776f726c6421208dae2087fbba51304eb02b91f656948397a7946390e8cb70fc9ea4d95f92251d024242047465737400320032013202320328292929292a0431003101310231043105310731083109310a310b310c310d310e310f3111311231133114311533000033000133000233000433000533000733000833000933000a33000b33000c33000d33000e33000f3300113300123300133300143300152d2e0102222324252104082209240a220b230c240d250e230f23102311231223132314181b1c2b171615400003290349483403350222231d4a484848482a50512a63222352410003420000432105602105612105270463484821052b62482b642b65484821052b2106662b21056721072b682b692107210570004848210771004848361c0037001a0031183119311b311d311e311f3120210721051e312131223123312431253126312731283129312a312b312c312d312e312f4478222105531421055427042106552105082106564c4d4b02210538212106391c0081e80780046a6f686e",
-	4: "042008b7a60cf8acd19181cf959a12f8acd19181cf951af8acd19181cf15f8acd191810f01020026050212340c68656c6c6f20776f726c6421208dae2087fbba51304eb02b91f656948397a7946390e8cb70fc9ea4d95f92251d024242047465737400320032013202320328292929292a0431003101310231043105310731083109310a310b310c310d310e310f3111311231133114311533000033000133000233000433000533000733000833000933000a33000b33000c33000d33000e33000f3300113300123300133300143300152d2e0102222324252104082209240a220b230c240d250e230f23102311231223132314181b1c2b171615400003290349483403350222231d4a484848482a50512a63222352410003420000432105602105612105270463484821052b62482b642b65484821052b2106662b21056721072b682b692107210570004848210771004848361c0037001a0031183119311b311d311e311f3120210721051e312131223123312431253126312731283129312a312b312c312d312e312f4478222105531421055427042106552105082106564c4d4b02210538212106391c0081e80780046a6f686e210581d00f210721061f",
+	4: "042008b7a60cf8acd19181cf959a12f8acd19181cf951af8acd19181cf15f8acd191810f01020026050212340c68656c6c6f20776f726c6421208dae2087fbba51304eb02b91f656948397a7946390e8cb70fc9ea4d95f92251d024242047465737400320032013202320328292929292a0431003101310231043105310731083109310a310b310c310d310e310f3111311231133114311533000033000133000233000433000533000733000833000933000a33000b33000c33000d33000e33000f3300113300123300133300143300152d2e0102222324252104082209240a220b230c240d250e230f23102311231223132314181b1c2b171615400003290349483403350222231d4a484848482a50512a63222352410003420000432105602105612105270463484821052b62482b642b65484821052b2106662b21056721072b682b692107210570004848210771004848361c0037001a0031183119311b311d311e311f3120210721051e312131223123312431253126312731283129312a312b312c312d312e312f4478222105531421055427042106552105082106564c4d4b02210538212106391c0081e80780046a6f686e210581d00f210721061f880003420001892105",
 }
 
 func pseudoOp(opcode string) bool {

diff --git a/data/transactions/logic/doc.go b/data/transactions/logic/doc.go
@@ -112,6 +112,8 @@ var opDocByName = map[string]string{
 	"asset_holding_get": "read from account specified by Txn.Accounts[A] and asset B holding field X (imm arg) => {0 or 1 (top), value}",
 	"asset_params_get":  "read from asset Txn.ForeignAssets[A] params field X (imm arg) => {0 or 1 (top), value}",
 	"assert":            "immediately fail unless value X is a non-zero number",
+	"callsub":           "branch unconditionally to TARGET, saving the next instruction on the call stack",
+	"retsub":            "pop the top instruction from the call stack and branch to it",
 }
 
 // OpDoc returns a description of the op
@@ -198,7 +200,7 @@ type OpGroup struct {
 var OpGroupList = []OpGroup{
 	{"Arithmetic", []string{"sha256", "keccak256", "sha512_256", "ed25519verify", "+", "-", "/", "*", "<", ">", "<=", ">=", "&&", "||", "==", "!=", "!", "len", "itob", "btoi", "%", "|", "&", "^", "~", "mulw", "addw", "divw", "getbit", "setbit", "getbyte", "setbyte", "concat", "substring", "substring3"}},
 	{"Loading Values", []string{"intcblock", "intc", "intc_0", "intc_1", "intc_2", "intc_3", "pushint", "bytecblock", "bytec", "bytec_0", "bytec_1", "bytec_2", "bytec_3", "pushbytes", "arg", "arg_0", "arg_1", "arg_2", "arg_3", "txn", "gtxn", "txna", "gtxna", "gtxns", "gtxnsa", "global", "load", "store"}},
-	{"Flow Control", []string{"err", "bnz", "bz", "b", "return", "pop", "dup", "dup2", "dig", "swap", "select", "assert"}},
+	{"Flow Control", []string{"err", "bnz", "bz", "b", "return", "pop", "dup", "dup2", "dig", "swap", "select", "assert", "callsub", "retsub"}},
 	{"State Access", []string{"balance", "min_balance", "app_opted_in", "app_local_get", "app_local_get_ex", "app_global_get", "app_global_get_ex", "app_local_put", "app_global_put", "app_local_del", "app_global_del", "asset_holding_get", "asset_params_get"}},
 }
 

diff --git a/data/transactions/logic/doc_test.go b/data/transactions/logic/doc_test.go
@@ -36,7 +36,7 @@ func TestOpDocs(t *testing.T) {
 	}
 	for op, seen := range opsSeen {
 		if !seen {
-			t.Errorf("error: doc for op %#v missing", op)
+			t.Errorf("error: doc for op %#v missing from opDocByName", op)
 		}
 	}
 }

diff --git a/data/transactions/logic/eval.go b/data/transactions/logic/eval.go
@@ -224,15 +224,16 @@ func (ep EvalParams) log() logging.Logger {
 type evalContext struct {
 	EvalParams
 
-	stack   []stackValue
-	program []byte // txn.Lsig.Logic ?
-	pc      int
-	nextpc  int
-	err     error
-	intc    []uint64
-	bytec   [][]byte
-	version uint64
-	scratch [256]stackValue
+	stack     []stackValue
+	callstack []int
+	program   []byte // txn.Lsig.Logic ?
+	pc        int
+	nextpc    int
+	err       error
+	intc      []uint64
+	bytec     [][]byte
+	version   uint64
+	scratch   [256]stackValue
 
 	cost int // cost incurred so far
 
@@ -1254,6 +1255,22 @@ func opB(cx *evalContext) {
 	cx.nextpc = target
 }
 
+func opCallSub(cx *evalContext) {
+	cx.callstack = append(cx.callstack, cx.pc+3)
+	opB(cx)
+}
+
+func opRetSub(cx *evalContext) {
+	top := len(cx.callstack) - 1
+	if top < 0 {
+		cx.err = errors.New("retsub with empty callstack")
+		return
+	}
+	target := cx.callstack[top]
+	cx.callstack = cx.callstack[:top]
+	cx.nextpc = target
+}
+
 func opPop(cx *evalContext) {
 	last := len(cx.stack) - 1
 	cx.stack = cx.stack[:last]

diff --git a/data/transactions/logic/eval_test.go b/data/transactions/logic/eval_test.go
@@ -4018,3 +4018,31 @@ func TestLoop(t *testing.T) {
 	// Infinite loop because multiply by one instead of two
 	testPanics(t, "int 1; loop:; int 1; *; dup; int 10; <; bnz loop; int 16; ==", 4)
 }
+
+func TestSubroutine(t *testing.T) {
+	t.Parallel()
+	testAccepts(t, "int 1; callsub double; int 2; ==; return; double: dup; +; retsub;", 4)
+	testAccepts(t, `
+b main;
+fact:
+  dup
+  int 2
+  <
+  bz recur
+  retsub
+recur:
+  dup
+  int 1
+  -
+  callsub fact
+  *
+  retsub
+
+main:
+  int 5
+  callsub fact
+  int 120
+  ==
+`, 4)
+	testPanics(t, "int 1; retsub", 4)
+}
diff --git a/data/transactions/logic/opcodes.go b/data/transactions/logic/opcodes.go
@@ -231,6 +231,16 @@ var OpSpecs = []OpSpec{
 	// Immediate bytes and ints. Smaller code size for single use of constant.
 	{0x80, "pushbytes", opPushBytes, asmPushBytes, disPushBytes, nil, oneBytes, 3, modeAny, varies(checkPushBytes, "bytes", immBytes)},
 	{0x81, "pushint", opPushInt, asmPushInt, disPushInt, nil, oneInt, 3, modeAny, varies(checkPushInt, "uint", immInt)},
+
+	// "Function oriented"
+	{0x88, "callsub", opCallSub, assembleBranch, disBranch, oneInt, nil, 4, modeAny, opBranch},
+	{0x89, "retsub", opRetSub, asmDefault, disDefault, nil, nil, 4, modeAny, opDefault},
+	// Leave a little room for indirect function calls, or similar
+
+	// More math
+	// shl, shr
+	// divw, modw convenience
+	// expmod
 }
 
 type sortByOpcode []OpSpec