Repository: benhoyt/goawk (go)

Issue:
Mutually-recursive functions without type info cause compiler panic
Per @xonixx's [comment](https://github.com/benhoyt/goawk/issues/183#issuecomment-1582459501), GoAWK can still panic on mutually-recursive functions that don't have clear type information (pass their args onto new functions without using them as a scalar or array). This doesn't happen often in real code, but it's relatively simple to create an example that breaks the compiler. Copying @xonixx's message below:

> Well, but topological sort can sort nodes only when there are no loops in the call graph. Since in the presence of mutual recursion there are loops in the graph I'm not sure that topoSort can help at all. I've played a bit with your example:

```awk
function f1(a) { if (0) f5(z1); f2(a) }
function f2(b) { if (0) f4(z2); f3(b) }
function f3(c) { if (0) f3(z3); f4(c) }
function f4(d) { if (0) f2(z4); f5(d) }
function f5(i) { if (0) f1(z5); i[1]=42 }
BEGIN { x[1]=3; f5(x); print x[1] }
```

> Still fails:

```
$ ../../proj/gron.awk/soft/goawk1.23.2 -f delme.awk 
42

$ ../../proj/gron.awk/soft/goawk1.23.2 -f delme.awk 
42

$ ../../proj/gron.awk/soft/goawk1.23.2 -f delme.awk 
panic: internal error: found scalar when expecting array "z3" [recovered]
        panic: interface conversion: interface {} is string, not *compiler.compileError [recovered]
        panic: interface conversion: interface {} is *runtime.TypeAssertionError, not *ast.PositionError

goroutine 1 [running]:
github.com/benhoyt/goawk/parser.ParseProgram.func1()
        /home/ben/h/goawk/parser/parser.go:70 +0xf4
panic({0x54b7c0, 0xc0000a09f0})
        /home/ben/sdk/go1.20.4/src/runtime/panic.go:884 +0x213
github.com/benhoyt/goawk/internal/compiler.Compile.func1()
        /home/ben/h/goawk/internal/compiler/compiler.go:66 +0x78
panic({0x544880, 0xc00009e680})
        /home/ben/sdk/go1.20.4/src/runtime/panic.go:884 +0x213
github.com/benhoyt/goawk/internal/compiler.(*compiler).arrayInfo(0x54a2c0?, {0xc0000b409a, 0x2})
        /home/ben/h/goawk/internal/compiler/compiler.go:206 +0xd4
github.com/benhoyt/goawk/internal/compiler.(*compiler).expr(0xc0000e5640, {0x59e9f8?, 0xc0000b21c0?})
        /home/ben/h/goawk/internal/compiler/compiler.go:895 +0x356a
github.com/benhoyt/goawk/internal/compiler.(*compiler).stmt(0xc0000e5640, {0x59ed00?, 0xc0000a04b0?})
        /home/ben/h/goawk/internal/compiler/compiler.go:310 +0xd9f
github.com/benhoyt/goawk/internal/compiler.(*compiler).stmts(...)
        /home/ben/h/goawk/internal/compiler/compiler.go:221
github.com/benhoyt/goawk/internal/compiler.(*compiler).stmt(0xc0000e5640, {0x59edc0?, 0xc0000cc700})
        /home/ben/h/goawk/internal/compiler/compiler.go:335 +0x31c9
github.com/benhoyt/goawk/internal/compiler.(*compiler).stmts(...)
        /home/ben/h/goawk/internal/compiler/compiler.go:221
github.com/benhoyt/goawk/internal/compiler.Compile(0xc0000cc930)
        /home/ben/h/goawk/internal/compiler/compiler.go:104 +0x1709
github.com/benhoyt/goawk/parser.ParseProgram({0xc0000dc000?, 0x7ffc83d26ea8?, 0x9?}, 0xc0000e5dd0)
        /home/ben/h/goawk/parser/parser.go:91 +0x19b
main.main()
        /home/ben/h/goawk/goawk.go:269 +0x1fd3

$ gawk -f delme.awk 
42

$ mawk -f delme.awk 
42
```

> Also note, how it passes or fails sporadically with GoAWK. I think this is due to randomized map iteration in Go.

Pull request:
Reintroduce additional resolve passes to fix complex mutual recursion
Not exactly an elegant solution, but does the job and fixes the problem with resolving mutually-recursive functions.

Historical note: prior to introducing topological sorting this was the only way the type resolver did it, regardless of call graph. See https://github.com/benhoyt/goawk/commit/0bc9499481ee7775f1cc5fcca3bcac1443811bf4.

Fixes #186

Patch:
diff --git a/internal/resolver/resolve.go b/internal/resolver/resolve.go
index 0df2346..23f7efe 100644
--- a/internal/resolver/resolve.go
+++ b/internal/resolver/resolve.go
@@ -185,12 +185,37 @@ func Resolve(prog *ast.Program, config *Config) *ResolvedProgram {
 	// information. Can't call ast.Walk on prog directly, as it will not
 	// iterate through functions in topological (call graph) order.
 	main := mainVisitor{r: &r, nativeFuncs: config.Funcs}
+	updates := r.updates
 	main.walkOrdered(prog, orderedFuncs)
 
-	// Do another pass to set parameter types in functions which don't use
-	// their parameters, such as f1's A parameter in this example:
+	// Do additional passes while we're still making type updates. Topological
+	// sorting takes care of ordinary call graphs, but additional passes are
+	// needed for at least these two cases:
+	//
+	// 1. Functions which don't use their parameters, such as f1's A parameter
+	//    in this example:
+	//
 	//  function f1(A) {}  function f2(x, A) { x[0]; f1(a); f2(a) }
-	main.walkOrdered(prog, orderedFuncs)
+	//
+	// 2. For complex mutually-recursive functions, such as this example:
+	//
+	//  function f1(a) { if (0) f5(z1); f2(a) }
+	//  function f2(b) { if (0) f4(z2); f3(b) }
+	//  function f3(c) { if (0) f3(z3); f4(c) }
+	//  function f4(d) { if (0) f2(z4); f5(d) }
+	//  function f5(i) { if (0) f1(z5); i[1]=42 }
+	//  BEGIN { x[1]=3; f5(x); print x[1] }
+	//
+	// Limit it to a sensible maximum number of iterations that almost
+	// certainly won't happen in the real world.
+	for i := 0; r.updates != updates; i++ {
+		updates = r.updates
+		main.walkOrdered(prog, orderedFuncs)
+		if i >= 100 {
+			panic(ast.PosErrorf(lexer.Position{1, 1},
+				"too many iterations trying to resolve variable types"))
+		}
+	}
 
 	// For any variables that are still unknown, set their type to scalar.
 	// This can happen for unused variables, such as in the following:
@@ -272,6 +297,7 @@ type resolver struct {
 	varInfo  map[string]map[string]VarInfo
 	funcInfo map[string]FuncInfo
 	funcs    map[string]*ast.Function
+	updates  int
 }
 
 // Look up variable from function funcName and return its scope and type
@@ -303,6 +329,7 @@ func (r *resolver) recordVar(funcName, varName string, typ Type, pos lexer.Posit
 	if !exists {
 		// Doesn't exist as a local or a global, add it as a new global.
 		r.varInfo[""][varName] = VarInfo{Type: typ}
+		r.updates++
 		if _, isFunc := r.funcs[varName]; isFunc {
 			panic(ast.PosErrorf(pos, "global var %q can't also be a function", varName))
 		}
@@ -311,8 +338,9 @@ func (r *resolver) recordVar(funcName, varName string, typ Type, pos lexer.Posit
 	if info.Type != typ && info.Type != unknown && typ != unknown {
 		panic(ast.PosErrorf(pos, "can't use %s %q as %s", info.Type, varName, typ))
 	}
-	if info.Type == unknown {
+	if info.Type == unknown && typ != unknown {
 		r.varInfo[varFunc][varName] = VarInfo{Type: typ, Index: info.Index}
+		r.updates++
 	}
 }
 


Test patch:
diff --git a/interp/interp_test.go b/interp/interp_test.go
index 1685ef7..a20d31d 100644
--- a/interp/interp_test.go
+++ b/interp/interp_test.go
@@ -764,6 +764,14 @@ function f4(d) { f5(d) }
 function f3(c) { f4(c) }
 BEGIN { x[1]=3; f5(x); print x[1] }
 `, "", "4\n", "", ""},
+	{`
+function f1(a) { if (0) f5(z1); f2(a) }
+function f2(b) { if (0) f4(z2); f3(b) }
+function f3(c) { if (0) f3(z3); f4(c) }
+function f4(d) { if (0) f2(z4); f5(d) }
+function f5(i) { if (0) f1(z5); i[1]=42 }
+BEGIN { x[1]=3; f5(x); print x[1] }
+`, "", "42\n", "", ""},
 
 	// Redirected I/O
 	{`BEGIN { getline x; print x }`, "foo", "foo\n", "", ""},