Gecko [ 167.86.127.34 ]

Name	Size	Permission
builtin	[ DIR ]	drwxr-xr-x
testdata	[ DIR ]	drwxr-xr-x
alg.go	16.28 KB	-rw-r--r--
align.go	9.85 KB	-rw-r--r--
bexport.go	4.41 KB	-rw-r--r--
bimport.go	667 B	-rw-r--r--
bitset.go	1.15 KB	-rw-r--r--
bootstrap.go	311 B	-rw-r--r--
builtin.go	16.41 KB	-rw-r--r--
builtin_test.go	622 B	-rw-r--r--
bv.go	5.5 KB	-rw-r--r--
class_string.go	712 B	-rw-r--r--
closure.go	15.57 KB	-rw-r--r--
const.go	27.21 KB	-rw-r--r--
constFold_test.go	322.99 KB	-rw-r--r--
dcl.go	28.37 KB	-rw-r--r--
dep_test.go	587 B	-rw-r--r--
dump.go	6.37 KB	-rw-r--r--
dwinl.go	10.07 KB	-rw-r--r--
esc.go	12.22 KB	-rw-r--r--
escape.go	37.37 KB	-rw-r--r--
export.go	5.33 KB	-rw-r--r--
fixedbugs_test.go	2.23 KB	-rw-r--r--
float_test.go	11.51 KB	-rw-r--r--
fmt.go	41.71 KB	-rw-r--r--
gen.go	2.33 KB	-rw-r--r--
global_test.go	2.57 KB	-rw-r--r--
go.go	7.4 KB	-rw-r--r--
gsubr.go	9.08 KB	-rw-r--r--
iexport.go	31.65 KB	-rw-r--r--
iface_test.go	1.92 KB	-rw-r--r--
iimport.go	22.79 KB	-rw-r--r--
init.go	3.29 KB	-rw-r--r--
initorder.go	9.84 KB	-rw-r--r--
inl.go	35.08 KB	-rw-r--r--
inl_test.go	6.64 KB	-rw-r--r--
lang_test.go	1.46 KB	-rw-r--r--
lex.go	5.96 KB	-rw-r--r--
lex_test.go	3.63 KB	-rw-r--r--
logic_test.go	11.08 KB	-rw-r--r--
main.go	43.75 KB	-rw-r--r--
mapfile_mmap.go	1.21 KB	-rw-r--r--
mapfile_read.go	485 B	-rw-r--r--
mkbuiltin.go	5.34 KB	-rw-r--r--
mpfloat.go	6.56 KB	-rw-r--r--
mpint.go	5.34 KB	-rw-r--r--
noder.go	37.65 KB	-rw-r--r--
obj.go	11.44 KB	-rw-r--r--
op_string.go	4.88 KB	-rw-r--r--
order.go	37.39 KB	-rw-r--r--
pgen.go	21.66 KB	-rw-r--r--
pgen_test.go	6.01 KB	-rw-r--r--
phi.go	14.72 KB	-rw-r--r--
plive.go	44.51 KB	-rw-r--r--
pprof.go	274 B	-rw-r--r--
racewalk.go	2.61 KB	-rw-r--r--
range.go	13.72 KB	-rw-r--r--
reflect.go	48.07 KB	-rw-r--r--
reproduciblebuilds_test.go	1.46 KB	-rw-r--r--
scc.go	4.18 KB	-rw-r--r--
scope.go	2.8 KB	-rw-r--r--
scope_test.go	13.67 KB	-rw-r--r--
select.go	9.16 KB	-rw-r--r--
shift_test.go	21.46 KB	-rw-r--r--
sinit.go	26.75 KB	-rw-r--r--
sizeof_test.go	844 B	-rw-r--r--
ssa.go	224.4 KB	-rw-r--r--
ssa_test.go	5.1 KB	-rw-r--r--
subr.go	43.73 KB	-rw-r--r--
swt.go	18.51 KB	-rw-r--r--
syntax.go	36.41 KB	-rw-r--r--
timings.go	5.75 KB	-rw-r--r--
trace.go	494 B	-rw-r--r--
truncconst_test.go	1.76 KB	-rw-r--r--
typecheck.go	87.11 KB	-rw-r--r--
types.go	1.19 KB	-rw-r--r--
types_acc.go	491 B	-rw-r--r--
universe.go	10.88 KB	-rw-r--r--
unsafe.go	1.8 KB	-rw-r--r--
util.go	2.18 KB	-rw-r--r--
walk.go	101.89 KB	-rw-r--r--
zerorange_test.go	1.89 KB	-rw-r--r--

Code Editor : initorder.go

// Copyright 2019 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 gc

import (
	"bytes"
	"container/heap"
	"fmt"
)

// Package initialization
//
// Here we implement the algorithm for ordering package-level variable
// initialization. The spec is written in terms of variable
// initialization, but multiple variables initialized by a single
// assignment are handled together, so here we instead focus on
// ordering initialization assignments. Conveniently, this maps well
// to how we represent package-level initializations using the Node
// AST.
//
// Assignments are in one of three phases: NotStarted, Pending, or
// Done. For assignments in the Pending phase, we use Xoffset to
// record the number of unique variable dependencies whose
// initialization assignment is not yet Done. We also maintain a
// "blocking" map that maps assignments back to all of the assignments
// that depend on it.
//
// For example, for an initialization like:
//
//     var x = f(a, b, b)
//     var a, b = g()
//
// the "x = f(a, b, b)" assignment depends on two variables (a and b),
// so its Xoffset will be 2. Correspondingly, the "a, b = g()"
// assignment's "blocking" entry will have two entries back to x's
// assignment.
//
// Logically, initialization works by (1) taking all NotStarted
// assignments, calculating their dependencies, and marking them
// Pending; (2) adding all Pending assignments with Xoffset==0 to a
// "ready" priority queue (ordered by variable declaration position);
// and (3) iteratively processing the next Pending assignment from the
// queue, decreasing the Xoffset of assignments it's blocking, and
// adding them to the queue if decremented to 0.
//
// As an optimization, we actually apply each of these three steps for
// each assignment. This yields the same order, but keeps queue size
// down and thus also heap operation costs.

// Static initialization phase.
// These values are stored in two bits in Node.flags.
const (
	InitNotStarted = iota
	InitDone
	InitPending
)

type InitOrder struct {
	// blocking maps initialization assignments to the assignments
	// that depend on it.
	blocking map[*Node][]*Node

// ready is the queue of Pending initialization assignments
	// that are ready for initialization.
	ready declOrder
}

// initOrder computes initialization order for a list l of
// package-level declarations (in declaration order) and outputs the
// corresponding list of statements to include in the init() function
// body.
func initOrder(l []*Node) []*Node {
	s := InitSchedule{
		initplans: make(map[*Node]*InitPlan),
		inittemps: make(map[*Node]*Node),
	}
	o := InitOrder{
		blocking: make(map[*Node][]*Node),
	}

// Process all package-level assignment in declaration order.
	for _, n := range l {
		switch n.Op {
		case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
			o.processAssign(n)
			o.flushReady(s.staticInit)
		case ODCLCONST, ODCLFUNC, ODCLTYPE:
			// nop
		default:
			Fatalf("unexpected package-level statement: %v", n)
		}
	}

// Check that all assignments are now Done; if not, there must
	// have been a dependency cycle.
	for _, n := range l {
		switch n.Op {
		case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
			if n.Initorder() != InitDone {
				// If there have already been errors
				// printed, those errors may have
				// confused us and there might not be
				// a loop. Let the user fix those
				// first.
				if nerrors > 0 {
					errorexit()
				}

findInitLoopAndExit(firstLHS(n), new([]*Node))
				Fatalf("initialization unfinished, but failed to identify loop")
			}
		}
	}

// Invariant consistency check. If this is non-zero, then we
	// should have found a cycle above.
	if len(o.blocking) != 0 {
		Fatalf("expected empty map: %v", o.blocking)
	}

return s.out
}

func (o *InitOrder) processAssign(n *Node) {
	if n.Initorder() != InitNotStarted || n.Xoffset != BADWIDTH {
		Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
	}

n.SetInitorder(InitPending)
	n.Xoffset = 0

// Compute number of variable dependencies and build the
	// inverse dependency ("blocking") graph.
	for dep := range collectDeps(n, true) {
		defn := dep.Name.Defn
		// Skip dependencies on functions (PFUNC) and
		// variables already initialized (InitDone).
		if dep.Class() != PEXTERN || defn.Initorder() == InitDone {
			continue
		}
		n.Xoffset++
		o.blocking[defn] = append(o.blocking[defn], n)
	}

if n.Xoffset == 0 {
		heap.Push(&o.ready, n)
	}
}

// flushReady repeatedly applies initialize to the earliest (in
// declaration order) assignment ready for initialization and updates
// the inverse dependency ("blocking") graph.
func (o *InitOrder) flushReady(initialize func(*Node)) {
	for o.ready.Len() != 0 {
		n := heap.Pop(&o.ready).(*Node)
		if n.Initorder() != InitPending || n.Xoffset != 0 {
			Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
		}

initialize(n)
		n.SetInitorder(InitDone)
		n.Xoffset = BADWIDTH

blocked := o.blocking[n]
		delete(o.blocking, n)

for _, m := range blocked {
			m.Xoffset--
			if m.Xoffset == 0 {
				heap.Push(&o.ready, m)
			}
		}
	}
}

// findInitLoopAndExit searches for an initialization loop involving variable
// or function n. If one is found, it reports the loop as an error and exits.
//
// path points to a slice used for tracking the sequence of
// variables/functions visited. Using a pointer to a slice allows the
// slice capacity to grow and limit reallocations.
func findInitLoopAndExit(n *Node, path *[]*Node) {
	// We implement a simple DFS loop-finding algorithm. This
	// could be faster, but initialization cycles are rare.

for i, x := range *path {
		if x == n {
			reportInitLoopAndExit((*path)[i:])
			return
		}
	}

// There might be multiple loops involving n; by sorting
	// references, we deterministically pick the one reported.
	refers := collectDeps(n.Name.Defn, false).Sorted(func(ni, nj *Node) bool {
		return ni.Pos.Before(nj.Pos)
	})

*path = append(*path, n)
	for _, ref := range refers {
		// Short-circuit variables that were initialized.
		if ref.Class() == PEXTERN && ref.Name.Defn.Initorder() == InitDone {
			continue
		}

findInitLoopAndExit(ref, path)
	}
	*path = (*path)[:len(*path)-1]
}

// reportInitLoopAndExit reports and initialization loop as an error
// and exits. However, if l is not actually an initialization loop, it
// simply returns instead.
func reportInitLoopAndExit(l []*Node) {
	// Rotate loop so that the earliest variable declaration is at
	// the start.
	i := -1
	for j, n := range l {
		if n.Class() == PEXTERN && (i == -1 || n.Pos.Before(l[i].Pos)) {
			i = j
		}
	}
	if i == -1 {
		// False positive: loop only involves recursive
		// functions. Return so that findInitLoop can continue
		// searching.
		return
	}
	l = append(l[i:], l[:i]...)

// TODO(mdempsky): Method values are printed as "T.m-fm"
	// rather than "T.m". Figure out how to avoid that.

var msg bytes.Buffer
	fmt.Fprintf(&msg, "initialization loop:\n")
	for _, n := range l {
		fmt.Fprintf(&msg, "\t%v: %v refers to\n", n.Line(), n)
	}
	fmt.Fprintf(&msg, "\t%v: %v", l[0].Line(), l[0])

yyerrorl(l[0].Pos, msg.String())
	errorexit()
}

// collectDeps returns all of the package-level functions and
// variables that declaration n depends on. If transitive is true,
// then it also includes the transitive dependencies of any depended
// upon functions (but not variables).
func collectDeps(n *Node, transitive bool) NodeSet {
	d := initDeps{transitive: transitive}
	switch n.Op {
	case OAS:
		d.inspect(n.Right)
	case OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
		d.inspect(n.Right)
	case ODCLFUNC:
		d.inspectList(n.Nbody)
	default:
		Fatalf("unexpected Op: %v", n.Op)
	}
	return d.seen
}

type initDeps struct {
	transitive bool
	seen       NodeSet
}

func (d *initDeps) inspect(n *Node)     { inspect(n, d.visit) }
func (d *initDeps) inspectList(l Nodes) { inspectList(l, d.visit) }

// visit calls foundDep on any package-level functions or variables
// referenced by n, if any.
func (d *initDeps) visit(n *Node) bool {
	switch n.Op {
	case ONAME:
		if n.isMethodExpression() {
			d.foundDep(asNode(n.Type.FuncType().Nname))
			return false
		}

switch n.Class() {
		case PEXTERN, PFUNC:
			d.foundDep(n)
		}

case OCLOSURE:
		d.inspectList(n.Func.Closure.Nbody)

case ODOTMETH, OCALLPART:
		d.foundDep(asNode(n.Type.FuncType().Nname))
	}

return true
}

// foundDep records that we've found a dependency on n by adding it to
// seen.
func (d *initDeps) foundDep(n *Node) {
	// Can happen with method expressions involving interface
	// types; e.g., fixedbugs/issue4495.go.
	if n == nil {
		return
	}

// Names without definitions aren't interesting as far as
	// initialization ordering goes.
	if n.Name.Defn == nil {
		return
	}

if d.seen.Has(n) {
		return
	}
	d.seen.Add(n)
	if d.transitive && n.Class() == PFUNC {
		d.inspectList(n.Name.Defn.Nbody)
	}
}

// declOrder implements heap.Interface, ordering assignment statements
// by the position of their first LHS expression.
//
// N.B., the Pos of the first LHS expression is used because because
// an OAS node's Pos may not be unique. For example, given the
// declaration "var a, b = f(), g()", "a" must be ordered before "b",
// but both OAS nodes use the "=" token's position as their Pos.
type declOrder []*Node

func (s declOrder) Len() int           { return len(s) }
func (s declOrder) Less(i, j int) bool { return firstLHS(s[i]).Pos.Before(firstLHS(s[j]).Pos) }
func (s declOrder) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func (s *declOrder) Push(x interface{}) { *s = append(*s, x.(*Node)) }
func (s *declOrder) Pop() interface{} {
	n := (*s)[len(*s)-1]
	*s = (*s)[:len(*s)-1]
	return n
}

// firstLHS returns the first expression on the left-hand side of
// assignment n.
func firstLHS(n *Node) *Node {
	switch n.Op {
	case OAS:
		return n.Left
	case OAS2DOTTYPE, OAS2FUNC, OAS2RECV, OAS2MAPR:
		return n.List.First()
	}

Fatalf("unexpected Op: %v", n.Op)
	return nil
}

${this.title}

Code Editor : initorder.go