libgo/go/go/types/ordering.go

   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] }