Black Lives Matter. Support the Equal Justice Initiative.

Source file src/go/types/predicates.go

Documentation: go/types

     1  // Copyright 2012 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 commonly used type predicates.
     6  
     7  package types
     8  
     9  import (
    10  	"go/token"
    11  )
    12  
    13  // isNamed reports whether typ has a name.
    14  // isNamed may be called with types that are not fully set up.
    15  func isNamed(typ Type) bool {
    16  	switch typ.(type) {
    17  	case *Basic, *Named, *_TypeParam, *instance:
    18  		return true
    19  	}
    20  	return false
    21  }
    22  
    23  // isGeneric reports whether a type is a generic, uninstantiated type (generic
    24  // signatures are not included).
    25  func isGeneric(typ Type) bool {
    26  	// A parameterized type is only instantiated if it doesn't have an instantiation already.
    27  	named, _ := typ.(*Named)
    28  	return named != nil && named.obj != nil && named.tparams != nil && named.targs == nil
    29  }
    30  
    31  func is(typ Type, what BasicInfo) bool {
    32  	switch t := optype(typ).(type) {
    33  	case *Basic:
    34  		return t.info&what != 0
    35  	case *_Sum:
    36  		return t.is(func(typ Type) bool { return is(typ, what) })
    37  	}
    38  	return false
    39  }
    40  
    41  func isBoolean(typ Type) bool  { return is(typ, IsBoolean) }
    42  func isInteger(typ Type) bool  { return is(typ, IsInteger) }
    43  func isUnsigned(typ Type) bool { return is(typ, IsUnsigned) }
    44  func isFloat(typ Type) bool    { return is(typ, IsFloat) }
    45  func isComplex(typ Type) bool  { return is(typ, IsComplex) }
    46  func isNumeric(typ Type) bool  { return is(typ, IsNumeric) }
    47  func isString(typ Type) bool   { return is(typ, IsString) }
    48  
    49  // Note that if typ is a type parameter, isInteger(typ) || isFloat(typ) does not
    50  // produce the expected result because a type list that contains both an integer
    51  // and a floating-point type is neither (all) integers, nor (all) floats.
    52  // Use isIntegerOrFloat instead.
    53  func isIntegerOrFloat(typ Type) bool { return is(typ, IsInteger|IsFloat) }
    54  
    55  // isNumericOrString is the equivalent of isIntegerOrFloat for isNumeric(typ) || isString(typ).
    56  func isNumericOrString(typ Type) bool { return is(typ, IsNumeric|IsString) }
    57  
    58  // isTyped reports whether typ is typed; i.e., not an untyped
    59  // constant or boolean. isTyped may be called with types that
    60  // are not fully set up.
    61  func isTyped(typ Type) bool {
    62  	// isTyped is called with types that are not fully
    63  	// set up. Must not call asBasic()!
    64  	// A *Named or *instance type is always typed, so
    65  	// we only need to check if we have a true *Basic
    66  	// type.
    67  	t, _ := typ.(*Basic)
    68  	return t == nil || t.info&IsUntyped == 0
    69  }
    70  
    71  // isUntyped(typ) is the same as !isTyped(typ).
    72  func isUntyped(typ Type) bool {
    73  	return !isTyped(typ)
    74  }
    75  
    76  func isOrdered(typ Type) bool { return is(typ, IsOrdered) }
    77  
    78  func isConstType(typ Type) bool {
    79  	// Type parameters are never const types.
    80  	t, _ := under(typ).(*Basic)
    81  	return t != nil && t.info&IsConstType != 0
    82  }
    83  
    84  // IsInterface reports whether typ is an interface type.
    85  func IsInterface(typ Type) bool {
    86  	return asInterface(typ) != nil
    87  }
    88  
    89  // Comparable reports whether values of type T are comparable.
    90  func Comparable(T Type) bool {
    91  	return comparable(T, nil)
    92  }
    93  
    94  func comparable(T Type, seen map[Type]bool) bool {
    95  	if seen[T] {
    96  		return true
    97  	}
    98  	if seen == nil {
    99  		seen = make(map[Type]bool)
   100  	}
   101  	seen[T] = true
   102  
   103  	// If T is a type parameter not constrained by any type
   104  	// list (i.e., it's underlying type is the top type),
   105  	// T is comparable if it has the == method. Otherwise,
   106  	// the underlying type "wins". For instance
   107  	//
   108  	//     interface{ comparable; type []byte }
   109  	//
   110  	// is not comparable because []byte is not comparable.
   111  	if t := asTypeParam(T); t != nil && optype(t) == theTop {
   112  		return t.Bound()._IsComparable()
   113  	}
   114  
   115  	switch t := optype(T).(type) {
   116  	case *Basic:
   117  		// assume invalid types to be comparable
   118  		// to avoid follow-up errors
   119  		return t.kind != UntypedNil
   120  	case *Pointer, *Interface, *Chan:
   121  		return true
   122  	case *Struct:
   123  		for _, f := range t.fields {
   124  			if !comparable(f.typ, seen) {
   125  				return false
   126  			}
   127  		}
   128  		return true
   129  	case *Array:
   130  		return comparable(t.elem, seen)
   131  	case *_Sum:
   132  		pred := func(t Type) bool {
   133  			return comparable(t, seen)
   134  		}
   135  		return t.is(pred)
   136  	case *_TypeParam:
   137  		return t.Bound()._IsComparable()
   138  	}
   139  	return false
   140  }
   141  
   142  // hasNil reports whether a type includes the nil value.
   143  func hasNil(typ Type) bool {
   144  	switch t := optype(typ).(type) {
   145  	case *Basic:
   146  		return t.kind == UnsafePointer
   147  	case *Slice, *Pointer, *Signature, *Interface, *Map, *Chan:
   148  		return true
   149  	case *_Sum:
   150  		return t.is(hasNil)
   151  	}
   152  	return false
   153  }
   154  
   155  // identical reports whether x and y are identical types.
   156  // Receivers of Signature types are ignored.
   157  func (check *Checker) identical(x, y Type) bool {
   158  	return check.identical0(x, y, true, nil)
   159  }
   160  
   161  // identicalIgnoreTags reports whether x and y are identical types if tags are ignored.
   162  // Receivers of Signature types are ignored.
   163  func (check *Checker) identicalIgnoreTags(x, y Type) bool {
   164  	return check.identical0(x, y, false, nil)
   165  }
   166  
   167  // An ifacePair is a node in a stack of interface type pairs compared for identity.
   168  type ifacePair struct {
   169  	x, y *Interface
   170  	prev *ifacePair
   171  }
   172  
   173  func (p *ifacePair) identical(q *ifacePair) bool {
   174  	return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x
   175  }
   176  
   177  // For changes to this code the corresponding changes should be made to unifier.nify.
   178  func (check *Checker) identical0(x, y Type, cmpTags bool, p *ifacePair) bool {
   179  	// types must be expanded for comparison
   180  	x = expandf(x)
   181  	y = expandf(y)
   182  
   183  	if x == y {
   184  		return true
   185  	}
   186  
   187  	switch x := x.(type) {
   188  	case *Basic:
   189  		// Basic types are singletons except for the rune and byte
   190  		// aliases, thus we cannot solely rely on the x == y check
   191  		// above. See also comment in TypeName.IsAlias.
   192  		if y, ok := y.(*Basic); ok {
   193  			return x.kind == y.kind
   194  		}
   195  
   196  	case *Array:
   197  		// Two array types are identical if they have identical element types
   198  		// and the same array length.
   199  		if y, ok := y.(*Array); ok {
   200  			// If one or both array lengths are unknown (< 0) due to some error,
   201  			// assume they are the same to avoid spurious follow-on errors.
   202  			return (x.len < 0 || y.len < 0 || x.len == y.len) && check.identical0(x.elem, y.elem, cmpTags, p)
   203  		}
   204  
   205  	case *Slice:
   206  		// Two slice types are identical if they have identical element types.
   207  		if y, ok := y.(*Slice); ok {
   208  			return check.identical0(x.elem, y.elem, cmpTags, p)
   209  		}
   210  
   211  	case *Struct:
   212  		// Two struct types are identical if they have the same sequence of fields,
   213  		// and if corresponding fields have the same names, and identical types,
   214  		// and identical tags. Two embedded fields are considered to have the same
   215  		// name. Lower-case field names from different packages are always different.
   216  		if y, ok := y.(*Struct); ok {
   217  			if x.NumFields() == y.NumFields() {
   218  				for i, f := range x.fields {
   219  					g := y.fields[i]
   220  					if f.embedded != g.embedded ||
   221  						cmpTags && x.Tag(i) != y.Tag(i) ||
   222  						!f.sameId(g.pkg, g.name) ||
   223  						!check.identical0(f.typ, g.typ, cmpTags, p) {
   224  						return false
   225  					}
   226  				}
   227  				return true
   228  			}
   229  		}
   230  
   231  	case *Pointer:
   232  		// Two pointer types are identical if they have identical base types.
   233  		if y, ok := y.(*Pointer); ok {
   234  			return check.identical0(x.base, y.base, cmpTags, p)
   235  		}
   236  
   237  	case *Tuple:
   238  		// Two tuples types are identical if they have the same number of elements
   239  		// and corresponding elements have identical types.
   240  		if y, ok := y.(*Tuple); ok {
   241  			if x.Len() == y.Len() {
   242  				if x != nil {
   243  					for i, v := range x.vars {
   244  						w := y.vars[i]
   245  						if !check.identical0(v.typ, w.typ, cmpTags, p) {
   246  							return false
   247  						}
   248  					}
   249  				}
   250  				return true
   251  			}
   252  		}
   253  
   254  	case *Signature:
   255  		// Two function types are identical if they have the same number of parameters
   256  		// and result values, corresponding parameter and result types are identical,
   257  		// and either both functions are variadic or neither is. Parameter and result
   258  		// names are not required to match.
   259  		// Generic functions must also have matching type parameter lists, but for the
   260  		// parameter names.
   261  		if y, ok := y.(*Signature); ok {
   262  			return x.variadic == y.variadic &&
   263  				check.identicalTParams(x.tparams, y.tparams, cmpTags, p) &&
   264  				check.identical0(x.params, y.params, cmpTags, p) &&
   265  				check.identical0(x.results, y.results, cmpTags, p)
   266  		}
   267  
   268  	case *_Sum:
   269  		// Two sum types are identical if they contain the same types.
   270  		// (Sum types always consist of at least two types. Also, the
   271  		// the set (list) of types in a sum type consists of unique
   272  		// types - each type appears exactly once. Thus, two sum types
   273  		// must contain the same number of types to have chance of
   274  		// being equal.
   275  		if y, ok := y.(*_Sum); ok && len(x.types) == len(y.types) {
   276  			// Every type in x.types must be in y.types.
   277  			// Quadratic algorithm, but probably good enough for now.
   278  			// TODO(gri) we need a fast quick type ID/hash for all types.
   279  		L:
   280  			for _, x := range x.types {
   281  				for _, y := range y.types {
   282  					if Identical(x, y) {
   283  						continue L // x is in y.types
   284  					}
   285  				}
   286  				return false // x is not in y.types
   287  			}
   288  			return true
   289  		}
   290  
   291  	case *Interface:
   292  		// Two interface types are identical if they have the same set of methods with
   293  		// the same names and identical function types. Lower-case method names from
   294  		// different packages are always different. The order of the methods is irrelevant.
   295  		if y, ok := y.(*Interface); ok {
   296  			// If identical0 is called (indirectly) via an external API entry point
   297  			// (such as Identical, IdenticalIgnoreTags, etc.), check is nil. But in
   298  			// that case, interfaces are expected to be complete and lazy completion
   299  			// here is not needed.
   300  			if check != nil {
   301  				check.completeInterface(token.NoPos, x)
   302  				check.completeInterface(token.NoPos, y)
   303  			}
   304  			a := x.allMethods
   305  			b := y.allMethods
   306  			if len(a) == len(b) {
   307  				// Interface types are the only types where cycles can occur
   308  				// that are not "terminated" via named types; and such cycles
   309  				// can only be created via method parameter types that are
   310  				// anonymous interfaces (directly or indirectly) embedding
   311  				// the current interface. Example:
   312  				//
   313  				//    type T interface {
   314  				//        m() interface{T}
   315  				//    }
   316  				//
   317  				// If two such (differently named) interfaces are compared,
   318  				// endless recursion occurs if the cycle is not detected.
   319  				//
   320  				// If x and y were compared before, they must be equal
   321  				// (if they were not, the recursion would have stopped);
   322  				// search the ifacePair stack for the same pair.
   323  				//
   324  				// This is a quadratic algorithm, but in practice these stacks
   325  				// are extremely short (bounded by the nesting depth of interface
   326  				// type declarations that recur via parameter types, an extremely
   327  				// rare occurrence). An alternative implementation might use a
   328  				// "visited" map, but that is probably less efficient overall.
   329  				q := &ifacePair{x, y, p}
   330  				for p != nil {
   331  					if p.identical(q) {
   332  						return true // same pair was compared before
   333  					}
   334  					p = p.prev
   335  				}
   336  				if debug {
   337  					assertSortedMethods(a)
   338  					assertSortedMethods(b)
   339  				}
   340  				for i, f := range a {
   341  					g := b[i]
   342  					if f.Id() != g.Id() || !check.identical0(f.typ, g.typ, cmpTags, q) {
   343  						return false
   344  					}
   345  				}
   346  				return true
   347  			}
   348  		}
   349  
   350  	case *Map:
   351  		// Two map types are identical if they have identical key and value types.
   352  		if y, ok := y.(*Map); ok {
   353  			return check.identical0(x.key, y.key, cmpTags, p) && check.identical0(x.elem, y.elem, cmpTags, p)
   354  		}
   355  
   356  	case *Chan:
   357  		// Two channel types are identical if they have identical value types
   358  		// and the same direction.
   359  		if y, ok := y.(*Chan); ok {
   360  			return x.dir == y.dir && check.identical0(x.elem, y.elem, cmpTags, p)
   361  		}
   362  
   363  	case *Named:
   364  		// Two named types are identical if their type names originate
   365  		// in the same type declaration.
   366  		if y, ok := y.(*Named); ok {
   367  			// TODO(gri) Why is x == y not sufficient? And if it is,
   368  			//           we can just return false here because x == y
   369  			//           is caught in the very beginning of this function.
   370  			return x.obj == y.obj
   371  		}
   372  
   373  	case *_TypeParam:
   374  		// nothing to do (x and y being equal is caught in the very beginning of this function)
   375  
   376  	// case *instance:
   377  	//	unreachable since types are expanded
   378  
   379  	case *bottom, *top:
   380  		// Either both types are theBottom, or both are theTop in which
   381  		// case the initial x == y check will have caught them. Otherwise
   382  		// they are not identical.
   383  
   384  	case nil:
   385  		// avoid a crash in case of nil type
   386  
   387  	default:
   388  		unreachable()
   389  	}
   390  
   391  	return false
   392  }
   393  
   394  func (check *Checker) identicalTParams(x, y []*TypeName, cmpTags bool, p *ifacePair) bool {
   395  	if len(x) != len(y) {
   396  		return false
   397  	}
   398  	for i, x := range x {
   399  		y := y[i]
   400  		if !check.identical0(x.typ.(*_TypeParam).bound, y.typ.(*_TypeParam).bound, cmpTags, p) {
   401  			return false
   402  		}
   403  	}
   404  	return true
   405  }
   406  
   407  // Default returns the default "typed" type for an "untyped" type;
   408  // it returns the incoming type for all other types. The default type
   409  // for untyped nil is untyped nil.
   410  //
   411  func Default(typ Type) Type {
   412  	if t, ok := typ.(*Basic); ok {
   413  		switch t.kind {
   414  		case UntypedBool:
   415  			return Typ[Bool]
   416  		case UntypedInt:
   417  			return Typ[Int]
   418  		case UntypedRune:
   419  			return universeRune // use 'rune' name
   420  		case UntypedFloat:
   421  			return Typ[Float64]
   422  		case UntypedComplex:
   423  			return Typ[Complex128]
   424  		case UntypedString:
   425  			return Typ[String]
   426  		}
   427  	}
   428  	return typ
   429  }
   430  

View as plain text