// Copyright 2013 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.

// This file implements Scopes.

package types

import (
	
	
	
	
	
	
)

// A Scope maintains a set of objects and links to its containing
// (parent) and contained (children) scopes. Objects may be inserted
// and looked up by name. The zero value for Scope is a ready-to-use
// empty scope.
type Scope struct {
	parent   *Scope
	children []*Scope
	elems    map[string]Object // lazily allocated
	pos, end token.Pos         // scope extent; may be invalid
	comment  string            // for debugging only
	isFunc   bool              // set if this is a function scope (internal use only)
}

// NewScope returns a new, empty scope contained in the given parent
// scope, if any. The comment is for debugging only.
func ( *Scope, ,  token.Pos,  string) *Scope {
	 := &Scope{, nil, nil, , , , false}
	// don't add children to Universe scope!
	if  != nil &&  != Universe {
		.children = append(.children, )
	}
	return 
}

// Parent returns the scope's containing (parent) scope.
func ( *Scope) () *Scope { return .parent }

// Len returns the number of scope elements.
func ( *Scope) () int { return len(.elems) }

// Names returns the scope's element names in sorted order.
func ( *Scope) () []string {
	 := make([]string, len(.elems))
	 := 0
	for  := range .elems {
		[] = 
		++
	}
	sort.Strings()
	return 
}

// NumChildren returns the number of scopes nested in s.
func ( *Scope) () int { return len(.children) }

// Child returns the i'th child scope for 0 <= i < NumChildren().
func ( *Scope) ( int) *Scope { return .children[] }

// Lookup returns the object in scope s with the given name if such an
// object exists; otherwise the result is nil.
func ( *Scope) ( string) Object {
	return .elems[]
}

// LookupParent follows the parent chain of scopes starting with s until
// it finds a scope where Lookup(name) returns a non-nil object, and then
// returns that scope and object. If a valid position pos is provided,
// only objects that were declared at or before pos are considered.
// If no such scope and object exists, the result is (nil, nil).
//
// Note that obj.Parent() may be different from the returned scope if the
// object was inserted into the scope and already had a parent at that
// time (see Insert). This can only happen for dot-imported objects
// whose scope is the scope of the package that exported them.
func ( *Scope) ( string,  token.Pos) (*Scope, Object) {
	for ;  != nil;  = .parent {
		if  := .elems[];  != nil && (!.IsValid() || .scopePos() <= ) {
			return , 
		}
	}
	return nil, nil
}

// Insert attempts to insert an object obj into scope s.
// If s already contains an alternative object alt with
// the same name, Insert leaves s unchanged and returns alt.
// Otherwise it inserts obj, sets the object's parent scope
// if not already set, and returns nil.
func ( *Scope) ( Object) Object {
	 := .Name()
	if  := .elems[];  != nil {
		return 
	}
	if .elems == nil {
		.elems = make(map[string]Object)
	}
	.elems[] = 
	if .Parent() == nil {
		.setParent()
	}
	return nil
}

// squash merges s with its parent scope p by adding all
// objects of s to p, adding all children of s to the
// children of p, and removing s from p's children.
// The function f is called for each object obj in s which
// has an object alt in p. s should be discarded after
// having been squashed.
func ( *Scope) ( func(,  Object)) {
	 := .parent
	assert( != nil)
	for ,  := range .elems {
		.setParent(nil)
		if  := .Insert();  != nil {
			(, )
		}
	}

	 := -1 // index of s in p.children
	for ,  := range .children {
		if  ==  {
			 = 
			break
		}
	}
	assert( >= 0)
	 := len(.children) - 1
	.children[] = .children[]
	.children = .children[:]

	.children = append(.children, .children...)

	.children = nil
	.elems = nil
}

// Pos and End describe the scope's source code extent [pos, end).
// The results are guaranteed to be valid only if the type-checked
// AST has complete position information. The extent is undefined
// for Universe and package scopes.
func ( *Scope) () token.Pos { return .pos }
func ( *Scope) () token.Pos { return .end }

// Contains reports whether pos is within the scope's extent.
// The result is guaranteed to be valid only if the type-checked
// AST has complete position information.
func ( *Scope) ( token.Pos) bool {
	return .pos <=  &&  < .end
}

// Innermost returns the innermost (child) scope containing
// pos. If pos is not within any scope, the result is nil.
// The result is also nil for the Universe scope.
// The result is guaranteed to be valid only if the type-checked
// AST has complete position information.
func ( *Scope) ( token.Pos) *Scope {
	// Package scopes do not have extents since they may be
	// discontiguous, so iterate over the package's files.
	if .parent == Universe {
		for ,  := range .children {
			if  := .();  != nil {
				return 
			}
		}
	}

	if .Contains() {
		for ,  := range .children {
			if .Contains() {
				return .()
			}
		}
		return 
	}
	return nil
}

// WriteTo writes a string representation of the scope to w,
// with the scope elements sorted by name.
// The level of indentation is controlled by n >= 0, with
// n == 0 for no indentation.
// If recurse is set, it also writes nested (children) scopes.
func ( *Scope) ( io.Writer,  int,  bool) {
	const  = ".  "
	 := strings.Repeat(, )

	fmt.Fprintf(, "%s%s scope %p {\n", , .comment, )

	 :=  + 
	for ,  := range .Names() {
		fmt.Fprintf(, "%s%s\n", , .elems[])
	}

	if  {
		for ,  := range .children {
			.(, +1, )
		}
	}

	fmt.Fprintf(, "%s}\n", )
}

// String returns a string representation of the scope, for debugging.
func ( *Scope) () string {
	var  bytes.Buffer
	.WriteTo(&, 0, false)
	return .String()
}