1 // Copyright 2014 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 // This file implements resolveOrder. 6 7 package types 8 9 import ( 10 "go/ast" 11 "sort" 12 ) 13 14 // resolveOrder computes the order in which package-level objects 15 // must be type-checked. 16 // 17 // Interface types appear first in the list, sorted topologically 18 // by dependencies on embedded interfaces that are also declared 19 // in this package, followed by all other objects sorted in source 20 // order. 21 // 22 // TODO(gri) Consider sorting all types by dependencies here, and 23 // in the process check _and_ report type cycles. This may simplify 24 // the full type-checking phase. 25 // 26 func (check *Checker) resolveOrder() []Object { 27 var ifaces, others []Object 28 29 // collect interface types with their dependencies, and all other objects 30 for obj := range check.objMap { 31 if ityp := check.interfaceFor(obj); ityp != nil { 32 ifaces = append(ifaces, obj) 33 // determine dependencies on embedded interfaces 34 for _, f := range ityp.Methods.List { 35 if len(f.Names) == 0 { 36 // Embedded interface: The type must be a (possibly 37 // qualified) identifier denoting another interface. 38 // Imported interfaces are already fully resolved, 39 // so we can ignore qualified identifiers. 40 if ident, _ := f.Type.(*ast.Ident); ident != nil { 41 embedded := check.pkg.scope.Lookup(ident.Name) 42 if check.interfaceFor(embedded) != nil { 43 check.objMap[obj].addDep(embedded) 44 } 45 } 46 } 47 } 48 } else { 49 others = append(others, obj) 50 } 51 } 52 53 // final object order 54 var order []Object 55 56 // sort interface types topologically by dependencies, 57 // and in source order if there are no dependencies 58 sort.Sort(inSourceOrder(ifaces)) 59 visited := make(objSet) 60 for _, obj := range ifaces { 61 check.appendInPostOrder(&order, obj, visited) 62 } 63 64 // sort everything else in source order 65 sort.Sort(inSourceOrder(others)) 66 67 return append(order, others...) 68 } 69 70 // interfaceFor returns the AST interface denoted by obj, or nil. 71 func (check *Checker) interfaceFor(obj Object) *ast.InterfaceType { 72 tname, _ := obj.(*TypeName) 73 if tname == nil { 74 return nil // not a type 75 } 76 d := check.objMap[obj] 77 if d == nil { 78 check.dump("%s: %s should have been declared", obj.Pos(), obj.Name()) 79 unreachable() 80 } 81 if d.typ == nil { 82 return nil // invalid AST - ignore (will be handled later) 83 } 84 ityp, _ := d.typ.(*ast.InterfaceType) 85 return ityp 86 } 87 88 func (check *Checker) appendInPostOrder(order *[]Object, obj Object, visited objSet) { 89 if visited[obj] { 90 // We've already seen this object; either because it's 91 // already added to order, or because we have a cycle. 92 // In both cases we stop. Cycle errors are reported 93 // when type-checking types. 94 return 95 } 96 visited[obj] = true 97 98 d := check.objMap[obj] 99 for _, obj := range orderedSetObjects(d.deps) { 100 check.appendInPostOrder(order, obj, visited) 101 } 102 103 *order = append(*order, obj) 104 } 105 106 func orderedSetObjects(set objSet) []Object { 107 list := make([]Object, len(set)) 108 i := 0 109 for obj := range set { 110 // we don't care about the map element value 111 list[i] = obj 112 i++ 113 } 114 sort.Sort(inSourceOrder(list)) 115 return list 116 } 117 118 // inSourceOrder implements the sort.Sort interface. 119 type inSourceOrder []Object 120 121 func (a inSourceOrder) Len() int { return len(a) } 122 func (a inSourceOrder) Less(i, j int) bool { return a[i].order() < a[j].order() } 123 func (a inSourceOrder) Swap(i, j int) { a[i], a[j] = a[j], a[i] } 124
