[dev.typeparams] cmd/compile/internal/importer, types2: initial check-in of types2 and importer

This is a copy of the importer and types2 (unreviewed) prototype version
excluding the testdata directory containing tests (see below). Each file
is marked with the comment

// UNREVIEWED

on the first line. The plan is to check in this code wholesale (it runs and
passes all tests) and then review the code file-by-file via subsequent CLs
and remove the "// UNREVIEWED" comments as we review the files.

Since most tests are unchanged from the original go/types, the next CL will
commit those tests as they don't need to be reviewed again. (Eventually we
may want to factor them out and share them from a single place, e.g. the
test directory.)

The existing file fmtmap_test.go was updated.

Change-Id: I9bd0ad1a7e7188b501423483a44d18e623c0fe71
Reviewed-on: https://go-review.googlesource.com/c/go/+/263624
Trust: Robert Griesemer <gri@golang.org>
Trust: Keith Randall <khr@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

1 files changed, 298 insertions, 0 deletions

diff --git a/src/cmd/compile/internal/types2/initorder.go b/src/cmd/compile/internal/types2/initorder.go
new file mode 100644
index 0000000000..3bb92d9622
--- /dev/null
+++ b/src/cmd/compile/internal/types2/initorder.go
@@ -0,0 +1,298 @@
+// UNREVIEWED
+// Copyright 2014 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package types2
+
+import (
+	"container/heap"
+	"fmt"
+)
+
+// initOrder computes the Info.InitOrder for package variables.
+func (check *Checker) initOrder() {
+	// An InitOrder may already have been computed if a package is
+	// built from several calls to (*Checker).Files. Clear it.
+	check.Info.InitOrder = check.Info.InitOrder[:0]
+
+	// Compute the object dependency graph and initialize
+	// a priority queue with the list of graph nodes.
+	pq := nodeQueue(dependencyGraph(check.objMap))
+	heap.Init(&pq)
+
+	const debug = false
+	if debug {
+		fmt.Printf("Computing initialization order for %s\n\n", check.pkg)
+		fmt.Println("Object dependency graph:")
+		for obj, d := range check.objMap {
+			// only print objects that may appear in the dependency graph
+			if obj, _ := obj.(dependency); obj != nil {
+				if len(d.deps) > 0 {
+					fmt.Printf("\t%s depends on\n", obj.Name())
+					for dep := range d.deps {
+						fmt.Printf("\t\t%s\n", dep.Name())
+					}
+				} else {
+					fmt.Printf("\t%s has no dependencies\n", obj.Name())
+				}
+			}
+		}
+		fmt.Println()
+
+		fmt.Println("Transposed object dependency graph (functions eliminated):")
+		for _, n := range pq {
+			fmt.Printf("\t%s depends on %d nodes\n", n.obj.Name(), n.ndeps)
+			for p := range n.pred {
+				fmt.Printf("\t\t%s is dependent\n", p.obj.Name())
+			}
+		}
+		fmt.Println()
+
+		fmt.Println("Processing nodes:")
+	}
+
+	// Determine initialization order by removing the highest priority node
+	// (the one with the fewest dependencies) and its edges from the graph,
+	// repeatedly, until there are no nodes left.
+	// In a valid Go program, those nodes always have zero dependencies (after
+	// removing all incoming dependencies), otherwise there are initialization
+	// cycles.
+	emitted := make(map[*declInfo]bool)
+	for len(pq) > 0 {
+		// get the next node
+		n := heap.Pop(&pq).(*graphNode)
+
+		if debug {
+			fmt.Printf("\t%s (src pos %d) depends on %d nodes now\n",
+				n.obj.Name(), n.obj.order(), n.ndeps)
+		}
+
+		// if n still depends on other nodes, we have a cycle
+		if n.ndeps > 0 {
+			cycle := findPath(check.objMap, n.obj, n.obj, make(map[Object]bool))
+			// If n.obj is not part of the cycle (e.g., n.obj->b->c->d->c),
+			// cycle will be nil. Don't report anything in that case since
+			// the cycle is reported when the algorithm gets to an object
+			// in the cycle.
+			// Furthermore, once an object in the cycle is encountered,
+			// the cycle will be broken (dependency count will be reduced
+			// below), and so the remaining nodes in the cycle don't trigger
+			// another error (unless they are part of multiple cycles).
+			if cycle != nil {
+				check.reportCycle(cycle)
+			}
+			// Ok to continue, but the variable initialization order
+			// will be incorrect at this point since it assumes no
+			// cycle errors.
+		}
+
+		// reduce dependency count of all dependent nodes
+		// and update priority queue
+		for p := range n.pred {
+			p.ndeps--
+			heap.Fix(&pq, p.index)
+		}
+
+		// record the init order for variables with initializers only
+		v, _ := n.obj.(*Var)
+		info := check.objMap[v]
+		if v == nil || !info.hasInitializer() {
+			continue
+		}
+
+		// n:1 variable declarations such as: a, b = f()
+		// introduce a node for each lhs variable (here: a, b);
+		// but they all have the same initializer - emit only
+		// one, for the first variable seen
+		if emitted[info] {
+			continue // initializer already emitted, if any
+		}
+		emitted[info] = true
+
+		infoLhs := info.lhs // possibly nil (see declInfo.lhs field comment)
+		if infoLhs == nil {
+			infoLhs = []*Var{v}
+		}
+		init := &Initializer{infoLhs, info.init}
+		check.Info.InitOrder = append(check.Info.InitOrder, init)
+	}
+
+	if debug {
+		fmt.Println()
+		fmt.Println("Initialization order:")
+		for _, init := range check.Info.InitOrder {
+			fmt.Printf("\t%s\n", init)
+		}
+		fmt.Println()
+	}
+}
+
+// findPath returns the (reversed) list of objects []Object{to, ... from}
+// such that there is a path of object dependencies from 'from' to 'to'.
+// If there is no such path, the result is nil.
+func findPath(objMap map[Object]*declInfo, from, to Object, seen map[Object]bool) []Object {
+	if seen[from] {
+		return nil
+	}
+	seen[from] = true
+
+	for d := range objMap[from].deps {
+		if d == to {
+			return []Object{d}
+		}
+		if P := findPath(objMap, d, to, seen); P != nil {
+			return append(P, d)
+		}
+	}
+
+	return nil
+}
+
+// reportCycle reports an error for the given cycle.
+func (check *Checker) reportCycle(cycle []Object) {
+	obj := cycle[0]
+	check.errorf(obj, "initialization cycle for %s", obj.Name())
+	// subtle loop: print cycle[i] for i = 0, n-1, n-2, ... 1 for len(cycle) = n
+	for i := len(cycle) - 1; i >= 0; i-- {
+		check.errorf(obj, "\t%s refers to", obj.Name()) // secondary error, \t indented
+		obj = cycle[i]
+	}
+	// print cycle[0] again to close the cycle
+	check.errorf(obj, "\t%s", obj.Name())
+}
+
+// ----------------------------------------------------------------------------
+// Object dependency graph
+
+// A dependency is an object that may be a dependency in an initialization
+// expression. Only constants, variables, and functions can be dependencies.
+// Constants are here because constant expression cycles are reported during
+// initialization order computation.
+type dependency interface {
+	Object
+	isDependency()
+}
+
+// A graphNode represents a node in the object dependency graph.
+// Each node p in n.pred represents an edge p->n, and each node
+// s in n.succ represents an edge n->s; with a->b indicating that
+// a depends on b.
+type graphNode struct {
+	obj        dependency // object represented by this node
+	pred, succ nodeSet    // consumers and dependencies of this node (lazily initialized)
+	index      int        // node index in graph slice/priority queue
+	ndeps      int        // number of outstanding dependencies before this object can be initialized
+}
+
+type nodeSet map[*graphNode]bool
+
+func (s *nodeSet) add(p *graphNode) {
+	if *s == nil {
+		*s = make(nodeSet)
+	}
+	(*s)[p] = true
+}
+
+// dependencyGraph computes the object dependency graph from the given objMap,
+// with any function nodes removed. The resulting graph contains only constants
+// and variables.
+func dependencyGraph(objMap map[Object]*declInfo) []*graphNode {
+	// M is the dependency (Object) -> graphNode mapping
+	M := make(map[dependency]*graphNode)
+	for obj := range objMap {
+		// only consider nodes that may be an initialization dependency
+		if obj, _ := obj.(dependency); obj != nil {
+			M[obj] = &graphNode{obj: obj}
+		}
+	}
+
+	// compute edges for graph M
+	// (We need to include all nodes, even isolated ones, because they still need
+	// to be scheduled for initialization in correct order relative to other nodes.)
+	for obj, n := range M {
+		// for each dependency obj -> d (= deps[i]), create graph edges n->s and s->n
+		for d := range objMap[obj].deps {
+			// only consider nodes that may be an initialization dependency
+			if d, _ := d.(dependency); d != nil {
+				d := M[d]
+				n.succ.add(d)
+				d.pred.add(n)
+			}
+		}
+	}
+
+	// remove function nodes and collect remaining graph nodes in G
+	// (Mutually recursive functions may introduce cycles among themselves
+	// which are permitted. Yet such cycles may incorrectly inflate the dependency
+	// count for variables which in turn may not get scheduled for initialization
+	// in correct order.)
+	var G []*graphNode
+	for obj, n := range M {
+		if _, ok := obj.(*Func); ok {
+			// connect each predecessor p of n with each successor s
+			// and drop the function node (don't collect it in G)
+			for p := range n.pred {
+				// ignore self-cycles
+				if p != n {
+					// Each successor s of n becomes a successor of p, and
+					// each predecessor p of n becomes a predecessor of s.
+					for s := range n.succ {
+						// ignore self-cycles
+						if s != n {
+							p.succ.add(s)
+							s.pred.add(p)
+							delete(s.pred, n) // remove edge to n
+						}
+					}
+					delete(p.succ, n) // remove edge to n
+				}
+			}
+		} else {
+			// collect non-function nodes
+			G = append(G, n)
+		}
+	}
+
+	// fill in index and ndeps fields
+	for i, n := range G {
+		n.index = i
+		n.ndeps = len(n.succ)
+	}
+
+	return G
+}
+
+// ----------------------------------------------------------------------------
+// Priority queue
+
+// nodeQueue implements the container/heap interface;
+// a nodeQueue may be used as a priority queue.
+type nodeQueue []*graphNode
+
+func (a nodeQueue) Len() int { return len(a) }
+
+func (a nodeQueue) Swap(i, j int) {
+	x, y := a[i], a[j]
+	a[i], a[j] = y, x
+	x.index, y.index = j, i
+}
+
+func (a nodeQueue) Less(i, j int) bool {
+	x, y := a[i], a[j]
+	// nodes are prioritized by number of incoming dependencies (1st key)
+	// and source order (2nd key)
+	return x.ndeps < y.ndeps || x.ndeps == y.ndeps && x.obj.order() < y.obj.order()
+}
+
+func (a *nodeQueue) Push(x interface{}) {
+	panic("unreachable")
+}
+
+func (a *nodeQueue) Pop() interface{} {
+	n := len(*a)
+	x := (*a)[n-1]
+	x.index = -1 // for safety
+	*a = (*a)[:n-1]
+	return x
+}