// 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 types

import (
	
	
)

// initOrder computes the Info.InitOrder for package variables.
func ( *Checker) () {
	// An InitOrder may already have been computed if a package is
	// built from several calls to (*Checker).Files. Clear it.
	.Info.InitOrder = .Info.InitOrder[:0]

	// Compute the object dependency graph and initialize
	// a priority queue with the list of graph nodes.
	 := nodeQueue(dependencyGraph(.objMap))
	heap.Init(&)

	const  = false
	if  {
		fmt.Printf("Computing initialization order for %s\n\n", .pkg)
		fmt.Println("Object dependency graph:")
		for ,  := range .objMap {
			// only print objects that may appear in the dependency graph
			if ,  := .(dependency);  != nil {
				if len(.deps) > 0 {
					fmt.Printf("\t%s depends on\n", .Name())
					for  := range .deps {
						fmt.Printf("\t\t%s\n", .Name())
					}
				} else {
					fmt.Printf("\t%s has no dependencies\n", .Name())
				}
			}
		}
		fmt.Println()

		fmt.Println("Transposed object dependency graph (functions eliminated):")
		for ,  := range  {
			fmt.Printf("\t%s depends on %d nodes\n", .obj.Name(), .ndeps)
			for  := range .pred {
				fmt.Printf("\t\t%s is dependent\n", .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.
	 := make(map[*declInfo]bool)
	for len() > 0 {
		// get the next node
		 := heap.Pop(&).(*graphNode)

		if  {
			fmt.Printf("\t%s (src pos %d) depends on %d nodes now\n",
				.obj.Name(), .obj.order(), .ndeps)
		}

		// if n still depends on other nodes, we have a cycle
		if .ndeps > 0 {
			 := findPath(.objMap, .obj, .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  != nil {
				.reportCycle()
			}
			// 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  := range .pred {
			.ndeps--
			heap.Fix(&, .index)
		}

		// record the init order for variables with initializers only
		,  := .obj.(*Var)
		 := .objMap[]
		if  == nil || !.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 [] {
			continue // initializer already emitted, if any
		}
		[] = true

		 := .lhs // possibly nil (see declInfo.lhs field comment)
		if  == nil {
			 = []*Var{}
		}
		 := &Initializer{, .init}
		.Info.InitOrder = append(.Info.InitOrder, )
	}

	if  {
		fmt.Println()
		fmt.Println("Initialization order:")
		for ,  := range .Info.InitOrder {
			fmt.Printf("\t%s\n", )
		}
		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( map[Object]*declInfo, ,  Object,  map[Object]bool) []Object {
	if [] {
		return nil
	}
	[] = true

	for  := range [].deps {
		if  ==  {
			return []Object{}
		}
		if  := (, , , );  != nil {
			return append(, )
		}
	}

	return nil
}

// reportCycle reports an error for the given cycle.
func ( *Checker) ( []Object) {
	 := [0]
	.errorf(, _InvalidInitCycle, "initialization cycle for %s", .Name())
	// subtle loop: print cycle[i] for i = 0, n-1, n-2, ... 1 for len(cycle) = n
	for  := len() - 1;  >= 0; -- {
		.errorf(, _InvalidInitCycle, "\t%s refers to", .Name()) // secondary error, \t indented
		 = []
	}
	// print cycle[0] again to close the cycle
	.errorf(, _InvalidInitCycle, "\t%s", .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 ( *nodeSet) ( *graphNode) {
	if * == nil {
		* = make(nodeSet)
	}
	(*)[] = 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( map[Object]*declInfo) []*graphNode {
	// M is the dependency (Object) -> graphNode mapping
	 := make(map[dependency]*graphNode)
	for  := range  {
		// only consider nodes that may be an initialization dependency
		if ,  := .(dependency);  != nil {
			[] = &graphNode{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 ,  := range  {
		// for each dependency obj -> d (= deps[i]), create graph edges n->s and s->n
		for  := range [].deps {
			// only consider nodes that may be an initialization dependency
			if ,  := .(dependency);  != nil {
				 := []
				.succ.add()
				.pred.add()
			}
		}
	}

	// 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  []*graphNode
	for ,  := range  {
		if ,  := .(*Func);  {
			// connect each predecessor p of n with each successor s
			// and drop the function node (don't collect it in G)
			for  := range .pred {
				// ignore self-cycles
				if  !=  {
					// Each successor s of n becomes a successor of p, and
					// each predecessor p of n becomes a predecessor of s.
					for  := range .succ {
						// ignore self-cycles
						if  !=  {
							.succ.add()
							.pred.add()
							delete(.pred, ) // remove edge to n
						}
					}
					delete(.succ, ) // remove edge to n
				}
			}
		} else {
			// collect non-function nodes
			 = append(, )
		}
	}

	// fill in index and ndeps fields
	for ,  := range  {
		.index = 
		.ndeps = len(.succ)
	}

	return 
}

// ----------------------------------------------------------------------------
// Priority queue

// nodeQueue implements the container/heap interface;
// a nodeQueue may be used as a priority queue.
type nodeQueue []*graphNode

func ( nodeQueue) () int { return len() }

func ( nodeQueue) (,  int) {
	,  := [], []
	[], [] = , 
	.index, .index = , 
}

func ( nodeQueue) (,  int) bool {
	,  := [], []
	// nodes are prioritized by number of incoming dependencies (1st key)
	// and source order (2nd key)
	return .ndeps < .ndeps || .ndeps == .ndeps && .obj.order() < .obj.order()
}

func ( *nodeQueue) ( interface{}) {
	panic("unreachable")
}

func ( *nodeQueue) () interface{} {
	 := len(*)
	 := (*)[-1]
	.index = -1 // for safety
	* = (*)[:-1]
	return 
}