Repository: benhoyt/goawk (go)

Issue:
Resolve types using topological sort to avoid O(N^2) worst case
In `parser.resolveVars` we currently loop through functions to resolve their parameter types in Go's map iteration order (which is randomized), so if you have a whole bunch of functions with unknown types (e.g., functions that just pass their parameter to another function), only a few will get resolved each iteration, and we'll have to do many iterations. Each iteration is O(N) in the number of functions, so the overall process is O(N^2) in the worst case. This is uncommon for real AWK code, but very bad for pathological cases.

There was an iteration maximum that was 10,000. But for the pathological case of thousands of such functions that took ages (over a minute, and I didn't wait any longer). So in https://github.com/benhoyt/goawk/commit/afcb42a9f8889c2a38da7f138d673fd4da6e6a08 I reduced the max iterations to 500, which takes 100ms or so to resolve. It would be highly unlikely for AWK scripts to have 500 functions with unresolved types.

In any case, we should improve this to use topological sort or similar, so we resolve them in the most efficient order, and we don't have to do multiple iterations. Or maybe we can just loop in a defined order and then loop again backwards?

Pull request description:
Resolve types using topological sort to avoid O(N^2) worst case
Fixes #98

Patch:
diff --git a/parser/resolve.go b/parser/resolve.go
index 1fc5ce0..6d1d0ca 100644
--- a/parser/resolve.go
+++ b/parser/resolve.go
@@ -234,54 +234,46 @@ func (p *parser) printVarTypes(prog *Program) {
 	}
 }
 
-// If we can't finish resolving after this many iterations, give up (500 takes about 100ms)
-const maxResolveIterations = 500
-
 // Resolve unknown variables types and generate variable indexes and
 // name-to-index mappings for interpreter
 func (p *parser) resolveVars(prog *Program) {
 	// First go through all unknown types and try to determine the
-	// type from the parameter type in that function definition. May
-	// need multiple passes depending on the order of functions. This
-	// is not particularly efficient, but on realistic programs it's
-	// not an issue.
-	for i := 0; ; i++ {
-		progressed := false
-		for funcName, infos := range p.varTypes {
-			for name, info := range infos {
-				if info.scope == ast.ScopeSpecial || info.typ != typeUnknown {
-					// It's a special var or type is already known
-					continue
-				}
-				funcIndex, ok := p.functions[info.callName]
-				if !ok {
-					// Function being called is a native function
-					continue
-				}
-				// Determine var type based on type of this parameter
-				// in the called function (if we know that)
-				paramName := prog.Functions[funcIndex].Params[info.argIndex]
-				typ := p.varTypes[info.callName][paramName].typ
-				if typ != typeUnknown {
-					if p.debugTypes {
-						fmt.Fprintf(p.debugWriter, "resolving %s:%s to %s\n",
-							funcName, name, typ)
-					}
-					info.typ = typ
-					p.varTypes[funcName][name] = info
-					progressed = true
+	// type from the parameter type in that function definition.
+	// Iterate through functions in topological order, for example
+	// if f() calls g(), process g first, then f.
+	callGraph := make(map[string]map[string]struct{})
+	for _, call := range p.userCalls {
+		if _, ok := callGraph[call.inFunc]; !ok {
+			callGraph[call.inFunc] = make(map[string]struct{})
+		}
+		callGraph[call.inFunc][call.call.Name] = struct{}{}
+	}
+	sortedFuncs := topoSort(callGraph)
+	for _, funcName := range sortedFuncs {
+		infos := p.varTypes[funcName]
+		for name, info := range infos {
+			if info.scope == ast.ScopeSpecial || info.typ != typeUnknown {
+				// It's a special var or type is already known
+				continue
+			}
+			funcIndex, ok := p.functions[info.callName]
+			if !ok {
+				// Function being called is a native function
+				continue
+			}
+			// Determine var type based on type of this parameter
+			// in the called function (if we know that)
+			paramName := prog.Functions[funcIndex].Params[info.argIndex]
+			typ := p.varTypes[info.callName][paramName].typ
+			if typ != typeUnknown {
+				if p.debugTypes {
+					fmt.Fprintf(p.debugWriter, "resolving %s:%s to %s\n",
+						funcName, name, typ)
 				}
+				info.typ = typ
+				p.varTypes[funcName][name] = info
 			}
 		}
-		if !progressed {
-			// If we didn't progress we're done (or trying again is
-			// not going to help)
-			break
-		}
-		if i >= maxResolveIterations {
-			// TODO: we should use topological sorting here to avoid O(N^2) behavior for inputs like those in TestResolveTooManyIterations
-			panic(p.errorf("too many iterations trying to resolve variable types"))
-		}
 	}
 
 	// Resolve global variables (iteration order is undefined, so
diff --git a/parser/toposort.go b/parser/toposort.go
new file mode 100644
index 0000000..90b71fa
--- /dev/null
+++ b/parser/toposort.go
@@ -0,0 +1,72 @@
+// Topological sorting
+
+package parser
+
+/*
+This algorithm is taken from:
+https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
+
+L ← Empty list that will contain the sorted nodes
+while exists nodes without a permanent mark do
+    select an unmarked node n
+    visit(n)
+
+function visit(node n)
+    if n has a permanent mark then
+        return
+    if n has a temporary mark then
+        stop   (not a DAG)
+
+    mark n with a temporary mark
+
+    for each node m with an edge from n to m do
+        visit(m)
+
+    remove temporary mark from n
+    mark n with a permanent mark
+    add n to head of L
+*/
+
+// Perform a topological sort on the given graph.
+func topoSort(graph map[string]map[string]struct{}) []string {
+	if len(graph) == 0 {
+		return nil
+	}
+
+	unmarked := make(map[string]struct{})
+	for node := range graph {
+		unmarked[node] = struct{}{}
+	}
+	permMarks := make(map[string]struct{})
+	tempMarks := make(map[string]struct{})
+	var sorted []string
+
+	var visit func(string)
+	visit = func(n string) {
+		if _, ok := permMarks[n]; ok {
+			return
+		}
+		if _, ok := tempMarks[n]; ok {
+			return
+		}
+		tempMarks[n] = struct{}{}
+		for m := range graph[n] {
+			visit(m)
+		}
+		delete(tempMarks, n)
+		permMarks[n] = struct{}{}
+		delete(unmarked, n)
+		sorted = append(sorted, n)
+		return
+	}
+
+	for len(unmarked) > 0 {
+		var n string
+		for n = range unmarked {
+			break
+		}
+		visit(n)
+	}
+
+	return sorted
+}


Test patch:
diff --git a/parser/parser_test.go b/parser/parser_test.go
index 3d4153d..ee442d4 100644
--- a/parser/parser_test.go
+++ b/parser/parser_test.go
@@ -190,21 +190,30 @@ function set(a, k, v) {
 	}
 }
 
-func TestResolveTooManyIterations(t *testing.T) {
+func TestResolveLargeCallGraph(t *testing.T) {
+	const numCalls = 10000
+
 	var buf bytes.Buffer
 	var i int
-	for i = 0; i < 1200; i++ { // at least twice as big as maxResolveIterations in resolve.go
+	for i = 0; i < numCalls; i++ {
 		fmt.Fprintf(&buf, "function f%d(a) { return f%d(a) }\n", i, i+1)
 	}
 	fmt.Fprintf(&buf, "function f%d(a) { return a }\n", i)
-	fmt.Fprintf(&buf, "BEGIN { printf f%d(42) }\n", i)
-
+	fmt.Fprint(&buf, "BEGIN { printf f0(42) }\n")
 	_, err := parser.ParseProgram(buf.Bytes(), nil)
-	if err == nil {
-		t.Fatal("expected error")
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
 	}
-	if !strings.Contains(err.Error(), "too many iterations") {
-		t.Fatalf(`expected error to contain "too many iterations", got %q`, err.Error())
+
+	buf.Reset()
+	fmt.Fprint(&buf, "BEGIN { printf f0(42) }\n")
+	fmt.Fprintf(&buf, "function f%d(a) { return a }\n", numCalls)
+	for i = numCalls - 1; i >= 0; i-- {
+		fmt.Fprintf(&buf, "function f%d(a) { return f%d(a) }\n", i, i+1)
+	}
+	_, err = parser.ParseProgram(buf.Bytes(), nil)
+	if err != nil {
+		t.Fatalf("unexpected error: %v", err)
 	}
 }
 
diff --git a/parser/toposort_test.go b/parser/toposort_test.go
new file mode 100644
index 0000000..d8d4c4c
--- /dev/null
+++ b/parser/toposort_test.go
@@ -0,0 +1,100 @@
+package parser
+
+import (
+	"strconv"
+	"testing"
+)
+
+func TestTopoSortEmpty(t *testing.T) {
+	sorted := topoSort(nil)
+	if len(sorted) != 0 {
+		t.Fatalf("expected empty slice, got %v", sorted)
+	}
+}
+
+func TestTopoSortSimple(t *testing.T) {
+	sorted := topoSort(map[string]map[string]struct{}{
+		"a": {"b": struct{}{}},
+		"b": {"c": struct{}{}},
+	})
+	if len(sorted) != 3 {
+		t.Fatalf("expected 3 items, got %d", len(sorted))
+	}
+	assertBefore(t, sorted, "c", "b")
+	assertBefore(t, sorted, "b", "a")
+}
+
+func TestTopoSortComplex(t *testing.T) {
+	sorted := topoSort(map[string]map[string]struct{}{
+		"a": {"b": struct{}{}, "c": struct{}{}},
+		"c": {"d": struct{}{}},
+		"f": {"g": struct{}{}, "h": struct{}{}},
+		"g": {},
+		"h": {},
+	})
+	if len(sorted) != 7 {
+		t.Fatalf("expected 7 items, got %d", len(sorted))
+	}
+	assertBefore(t, sorted, "g", "f")
+	assertBefore(t, sorted, "h", "f")
+	assertBefore(t, sorted, "d", "c")
+	assertBefore(t, sorted, "c", "a")
+	assertBefore(t, sorted, "b", "a")
+}
+
+func assertBefore(t *testing.T, sorted []string, x, y string) {
+	xi := strIndex(sorted, x)
+	if xi < 0 {
+		t.Fatalf("expected %q to be in result", x)
+	}
+	yi := strIndex(sorted, y)
+	if yi < 0 {
+		t.Fatalf("expected %q to be in result", y)
+	}
+	if xi >= yi {
+		t.Fatalf("expected %q to come before %q, got indexes %d and %d", x, y, xi, yi)
+	}
+}
+
+func strIndex(slice []string, s string) int {
+	for i, item := range slice {
+		if s == item {
+			return i
+		}
+	}
+	return -1
+}
+
+func TestTopoSortCycle(t *testing.T) {
+	sorted := topoSort(map[string]map[string]struct{}{
+		"a": {"b": struct{}{}, "c": struct{}{}},
+		"c": {"a": struct{}{}},
+	})
+	if len(sorted) != 3 {
+		t.Fatalf("expected 3 items, got %d", len(sorted))
+	}
+	assertBefore(t, sorted, "b", "a")
+	c := strIndex(sorted, "a")
+	if c < 0 {
+		t.Fatalf("expected %q to be in result", c)
+	}
+}
+
+func TestTopoSortLarge(t *testing.T) {
+	const num = 1000
+	graph := make(map[string]map[string]struct{})
+	for i := 0; i < num; i++ {
+		graph[strconv.Itoa(i)] = map[string]struct{}{strconv.Itoa(i + 1): {}}
+	}
+	graph[strconv.Itoa(num)] = map[string]struct{}{}
+	sorted := topoSort(graph)
+	if len(sorted) != num+1 {
+		t.Fatalf("expected %d items, got %d", num+1, len(sorted))
+	}
+	for i := 0; i < num+1; i++ {
+		expected := num - i
+		if sorted[i] != strconv.Itoa(expected) {
+			t.Fatalf("expected %d to be at index %d, got %s", num-1, i, sorted[i])
+		}
+	}
+}