Source file src/pkg/cmd/compile/internal/gc/initorder.go

     1	// Copyright 2019 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package gc
     6	
     7	import (
     8		"bytes"
     9		"container/heap"
    10		"fmt"
    11	)
    12	
    13	// Package initialization
    14	//
    15	// Here we implement the algorithm for ordering package-level variable
    16	// initialization. The spec is written in terms of variable
    17	// initialization, but multiple variables initialized by a single
    18	// assignment are handled together, so here we instead focus on
    19	// ordering initialization assignments. Conveniently, this maps well
    20	// to how we represent package-level initializations using the Node
    21	// AST.
    22	//
    23	// Assignments are in one of three phases: NotStarted, Pending, or
    24	// Done. For assignments in the Pending phase, we use Xoffset to
    25	// record the number of unique variable dependencies whose
    26	// initialization assignment is not yet Done. We also maintain a
    27	// "blocking" map that maps assignments back to all of the assignments
    28	// that depend on it.
    29	//
    30	// For example, for an initialization like:
    31	//
    32	//     var x = f(a, b, b)
    33	//     var a, b = g()
    34	//
    35	// the "x = f(a, b, b)" assignment depends on two variables (a and b),
    36	// so its Xoffset will be 2. Correspondingly, the "a, b = g()"
    37	// assignment's "blocking" entry will have two entries back to x's
    38	// assignment.
    39	//
    40	// Logically, initialization works by (1) taking all NotStarted
    41	// assignments, calculating their dependencies, and marking them
    42	// Pending; (2) adding all Pending assignments with Xoffset==0 to a
    43	// "ready" priority queue (ordered by variable declaration position);
    44	// and (3) iteratively processing the next Pending assignment from the
    45	// queue, decreasing the Xoffset of assignments it's blocking, and
    46	// adding them to the queue if decremented to 0.
    47	//
    48	// As an optimization, we actually apply each of these three steps for
    49	// each assignment. This yields the same order, but keeps queue size
    50	// down and thus also heap operation costs.
    51	
    52	// Static initialization phase.
    53	// These values are stored in two bits in Node.flags.
    54	const (
    55		InitNotStarted = iota
    56		InitDone
    57		InitPending
    58	)
    59	
    60	type InitOrder struct {
    61		// blocking maps initialization assignments to the assignments
    62		// that depend on it.
    63		blocking map[*Node][]*Node
    64	
    65		// ready is the queue of Pending initialization assignments
    66		// that are ready for initialization.
    67		ready declOrder
    68	}
    69	
    70	// initOrder computes initialization order for a list l of
    71	// package-level declarations (in declaration order) and outputs the
    72	// corresponding list of statements to include in the init() function
    73	// body.
    74	func initOrder(l []*Node) []*Node {
    75		s := InitSchedule{
    76			initplans: make(map[*Node]*InitPlan),
    77			inittemps: make(map[*Node]*Node),
    78		}
    79		o := InitOrder{
    80			blocking: make(map[*Node][]*Node),
    81		}
    82	
    83		// Process all package-level assignment in declaration order.
    84		for _, n := range l {
    85			switch n.Op {
    86			case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
    87				o.processAssign(n)
    88				o.flushReady(s.staticInit)
    89			case ODCLCONST, ODCLFUNC, ODCLTYPE:
    90				// nop
    91			default:
    92				Fatalf("unexpected package-level statement: %v", n)
    93			}
    94		}
    95	
    96		// Check that all assignments are now Done; if not, there must
    97		// have been a dependency cycle.
    98		for _, n := range l {
    99			switch n.Op {
   100			case OAS, OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
   101				if n.Initorder() != InitDone {
   102					// If there have already been errors
   103					// printed, those errors may have
   104					// confused us and there might not be
   105					// a loop. Let the user fix those
   106					// first.
   107					if nerrors > 0 {
   108						errorexit()
   109					}
   110	
   111					findInitLoopAndExit(firstLHS(n), new([]*Node))
   112					Fatalf("initialization unfinished, but failed to identify loop")
   113				}
   114			}
   115		}
   116	
   117		// Invariant consistency check. If this is non-zero, then we
   118		// should have found a cycle above.
   119		if len(o.blocking) != 0 {
   120			Fatalf("expected empty map: %v", o.blocking)
   121		}
   122	
   123		return s.out
   124	}
   125	
   126	func (o *InitOrder) processAssign(n *Node) {
   127		if n.Initorder() != InitNotStarted || n.Xoffset != BADWIDTH {
   128			Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
   129		}
   130	
   131		n.SetInitorder(InitPending)
   132		n.Xoffset = 0
   133	
   134		// Compute number of variable dependencies and build the
   135		// inverse dependency ("blocking") graph.
   136		for dep := range collectDeps(n, true) {
   137			defn := dep.Name.Defn
   138			// Skip dependencies on functions (PFUNC) and
   139			// variables already initialized (InitDone).
   140			if dep.Class() != PEXTERN || defn.Initorder() == InitDone {
   141				continue
   142			}
   143			n.Xoffset++
   144			o.blocking[defn] = append(o.blocking[defn], n)
   145		}
   146	
   147		if n.Xoffset == 0 {
   148			heap.Push(&o.ready, n)
   149		}
   150	}
   151	
   152	// flushReady repeatedly applies initialize to the earliest (in
   153	// declaration order) assignment ready for initialization and updates
   154	// the inverse dependency ("blocking") graph.
   155	func (o *InitOrder) flushReady(initialize func(*Node)) {
   156		for o.ready.Len() != 0 {
   157			n := heap.Pop(&o.ready).(*Node)
   158			if n.Initorder() != InitPending || n.Xoffset != 0 {
   159				Fatalf("unexpected state: %v, %v, %v", n, n.Initorder(), n.Xoffset)
   160			}
   161	
   162			initialize(n)
   163			n.SetInitorder(InitDone)
   164			n.Xoffset = BADWIDTH
   165	
   166			blocked := o.blocking[n]
   167			delete(o.blocking, n)
   168	
   169			for _, m := range blocked {
   170				m.Xoffset--
   171				if m.Xoffset == 0 {
   172					heap.Push(&o.ready, m)
   173				}
   174			}
   175		}
   176	}
   177	
   178	// findInitLoopAndExit searches for an initialization loop involving variable
   179	// or function n. If one is found, it reports the loop as an error and exits.
   180	//
   181	// path points to a slice used for tracking the sequence of
   182	// variables/functions visited. Using a pointer to a slice allows the
   183	// slice capacity to grow and limit reallocations.
   184	func findInitLoopAndExit(n *Node, path *[]*Node) {
   185		// We implement a simple DFS loop-finding algorithm. This
   186		// could be faster, but initialization cycles are rare.
   187	
   188		for i, x := range *path {
   189			if x == n {
   190				reportInitLoopAndExit((*path)[i:])
   191				return
   192			}
   193		}
   194	
   195		// There might be multiple loops involving n; by sorting
   196		// references, we deterministically pick the one reported.
   197		refers := collectDeps(n.Name.Defn, false).Sorted(func(ni, nj *Node) bool {
   198			return ni.Pos.Before(nj.Pos)
   199		})
   200	
   201		*path = append(*path, n)
   202		for _, ref := range refers {
   203			// Short-circuit variables that were initialized.
   204			if ref.Class() == PEXTERN && ref.Name.Defn.Initorder() == InitDone {
   205				continue
   206			}
   207	
   208			findInitLoopAndExit(ref, path)
   209		}
   210		*path = (*path)[:len(*path)-1]
   211	}
   212	
   213	// reportInitLoopAndExit reports and initialization loop as an error
   214	// and exits. However, if l is not actually an initialization loop, it
   215	// simply returns instead.
   216	func reportInitLoopAndExit(l []*Node) {
   217		// Rotate loop so that the earliest variable declaration is at
   218		// the start.
   219		i := -1
   220		for j, n := range l {
   221			if n.Class() == PEXTERN && (i == -1 || n.Pos.Before(l[i].Pos)) {
   222				i = j
   223			}
   224		}
   225		if i == -1 {
   226			// False positive: loop only involves recursive
   227			// functions. Return so that findInitLoop can continue
   228			// searching.
   229			return
   230		}
   231		l = append(l[i:], l[:i]...)
   232	
   233		// TODO(mdempsky): Method values are printed as "T.m-fm"
   234		// rather than "T.m". Figure out how to avoid that.
   235	
   236		var msg bytes.Buffer
   237		fmt.Fprintf(&msg, "initialization loop:\n")
   238		for _, n := range l {
   239			fmt.Fprintf(&msg, "\t%v: %v refers to\n", n.Line(), n)
   240		}
   241		fmt.Fprintf(&msg, "\t%v: %v", l[0].Line(), l[0])
   242	
   243		yyerrorl(l[0].Pos, msg.String())
   244		errorexit()
   245	}
   246	
   247	// collectDeps returns all of the package-level functions and
   248	// variables that declaration n depends on. If transitive is true,
   249	// then it also includes the transitive dependencies of any depended
   250	// upon functions (but not variables).
   251	func collectDeps(n *Node, transitive bool) NodeSet {
   252		d := initDeps{transitive: transitive}
   253		switch n.Op {
   254		case OAS:
   255			d.inspect(n.Right)
   256		case OAS2DOTTYPE, OAS2FUNC, OAS2MAPR, OAS2RECV:
   257			d.inspect(n.Rlist.First())
   258		case ODCLFUNC:
   259			d.inspectList(n.Nbody)
   260		default:
   261			Fatalf("unexpected Op: %v", n.Op)
   262		}
   263		return d.seen
   264	}
   265	
   266	type initDeps struct {
   267		transitive bool
   268		seen       NodeSet
   269	}
   270	
   271	func (d *initDeps) inspect(n *Node)     { inspect(n, d.visit) }
   272	func (d *initDeps) inspectList(l Nodes) { inspectList(l, d.visit) }
   273	
   274	// visit calls foundDep on any package-level functions or variables
   275	// referenced by n, if any.
   276	func (d *initDeps) visit(n *Node) bool {
   277		switch n.Op {
   278		case ONAME:
   279			if n.isMethodExpression() {
   280				d.foundDep(asNode(n.Type.FuncType().Nname))
   281				return false
   282			}
   283	
   284			switch n.Class() {
   285			case PEXTERN, PFUNC:
   286				d.foundDep(n)
   287			}
   288	
   289		case OCLOSURE:
   290			d.inspectList(n.Func.Closure.Nbody)
   291	
   292		case ODOTMETH, OCALLPART:
   293			d.foundDep(asNode(n.Type.FuncType().Nname))
   294		}
   295	
   296		return true
   297	}
   298	
   299	// foundDep records that we've found a dependency on n by adding it to
   300	// seen.
   301	func (d *initDeps) foundDep(n *Node) {
   302		// Can happen with method expressions involving interface
   303		// types; e.g., fixedbugs/issue4495.go.
   304		if n == nil {
   305			return
   306		}
   307	
   308		// Names without definitions aren't interesting as far as
   309		// initialization ordering goes.
   310		if n.Name.Defn == nil {
   311			return
   312		}
   313	
   314		if d.seen.Has(n) {
   315			return
   316		}
   317		d.seen.Add(n)
   318		if d.transitive && n.Class() == PFUNC {
   319			d.inspectList(n.Name.Defn.Nbody)
   320		}
   321	}
   322	
   323	// declOrder implements heap.Interface, ordering assignment statements
   324	// by the position of their first LHS expression.
   325	//
   326	// N.B., the Pos of the first LHS expression is used because because
   327	// an OAS node's Pos may not be unique. For example, given the
   328	// declaration "var a, b = f(), g()", "a" must be ordered before "b",
   329	// but both OAS nodes use the "=" token's position as their Pos.
   330	type declOrder []*Node
   331	
   332	func (s declOrder) Len() int           { return len(s) }
   333	func (s declOrder) Less(i, j int) bool { return firstLHS(s[i]).Pos.Before(firstLHS(s[j]).Pos) }
   334	func (s declOrder) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
   335	
   336	func (s *declOrder) Push(x interface{}) { *s = append(*s, x.(*Node)) }
   337	func (s *declOrder) Pop() interface{} {
   338		n := (*s)[len(*s)-1]
   339		*s = (*s)[:len(*s)-1]
   340		return n
   341	}
   342	
   343	// firstLHS returns the first expression on the left-hand side of
   344	// assignment n.
   345	func firstLHS(n *Node) *Node {
   346		switch n.Op {
   347		case OAS:
   348			return n.Left
   349		case OAS2DOTTYPE, OAS2FUNC, OAS2RECV, OAS2MAPR:
   350			return n.List.First()
   351		}
   352	
   353		Fatalf("unexpected Op: %v", n.Op)
   354		return nil
   355	}
   356	

View as plain text