predicates.go

     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 "go/token"
    10  
    11  // The isX predicates below report whether t is an X.
    12  // If t is a type parameter the result is false; i.e.,
    13  // these predicates don't look inside a type parameter.
    14  
    15  func isBoolean(t Type) bool        { return isBasic(t, IsBoolean) }
    16  func isInteger(t Type) bool        { return isBasic(t, IsInteger) }
    17  func isUnsigned(t Type) bool       { return isBasic(t, IsUnsigned) }
    18  func isFloat(t Type) bool          { return isBasic(t, IsFloat) }
    19  func isComplex(t Type) bool        { return isBasic(t, IsComplex) }
    20  func isNumeric(t Type) bool        { return isBasic(t, IsNumeric) }
    21  func isString(t Type) bool         { return isBasic(t, IsString) }
    22  func isIntegerOrFloat(t Type) bool { return isBasic(t, IsInteger|IsFloat) }
    23  func isConstType(t Type) bool      { return isBasic(t, IsConstType) }
    24  
    25  // isBasic reports whether under(t) is a basic type with the specified info.
    26  // If t is a type parameter the result is false; i.e.,
    27  // isBasic does not look inside a type parameter.
    28  func isBasic(t Type, info BasicInfo) bool {
    29  	u, _ := under(t).(*Basic)
    30  	return u != nil && u.info&info != 0
    31  }
    32  
    33  // The allX predicates below report whether t is an X.
    34  // If t is a type parameter the result is true if isX is true
    35  // for all specified types of the type parameter's type set.
    36  // allX is an optimized version of isX(coreType(t)) (which
    37  // is the same as underIs(t, isX)).
    38  
    39  func allBoolean(typ Type) bool         { return allBasic(typ, IsBoolean) }
    40  func allInteger(typ Type) bool         { return allBasic(typ, IsInteger) }
    41  func allUnsigned(typ Type) bool        { return allBasic(typ, IsUnsigned) }
    42  func allNumeric(typ Type) bool         { return allBasic(typ, IsNumeric) }
    43  func allString(typ Type) bool          { return allBasic(typ, IsString) }
    44  func allOrdered(typ Type) bool         { return allBasic(typ, IsOrdered) }
    45  func allNumericOrString(typ Type) bool { return allBasic(typ, IsNumeric|IsString) }
    46  
    47  // allBasic reports whether under(t) is a basic type with the specified info.
    48  // If t is a type parameter, the result is true if isBasic(t, info) is true
    49  // for all specific types of the type parameter's type set.
    50  // allBasic(t, info) is an optimized version of isBasic(coreType(t), info).
    51  func allBasic(t Type, info BasicInfo) bool {
    52  	if tpar, _ := t.(*TypeParam); tpar != nil {
    53  		return tpar.is(func(t *term) bool { return t != nil && isBasic(t.typ, info) })
    54  	}
    55  	return isBasic(t, info)
    56  }
    57  
    58  // hasName reports whether t has a name. This includes
    59  // predeclared types, defined types, and type parameters.
    60  // hasName may be called with types that are not fully set up.
    61  func hasName(t Type) bool {
    62  	switch t.(type) {
    63  	case *Basic, *Named, *TypeParam:
    64  		return true
    65  	}
    66  	return false
    67  }
    68  
    69  // isTyped reports whether t is typed; i.e., not an untyped
    70  // constant or boolean. isTyped may be called with types that
    71  // are not fully set up.
    72  func isTyped(t Type) bool {
    73  	// isTyped is called with types that are not fully
    74  	// set up. Must not call under()!
    75  	b, _ := t.(*Basic)
    76  	return b == nil || b.info&IsUntyped == 0
    77  }
    78  
    79  // isUntyped(t) is the same as !isTyped(t).
    80  func isUntyped(t Type) bool {
    81  	return !isTyped(t)
    82  }
    83  
    84  // IsInterface reports whether t is an interface type.
    85  func IsInterface(t Type) bool {
    86  	_, ok := under(t).(*Interface)
    87  	return ok
    88  }
    89  
    90  // isTypeParam reports whether t is a type parameter.
    91  func isTypeParam(t Type) bool {
    92  	_, ok := t.(*TypeParam)
    93  	return ok
    94  }
    95  
    96  // isGeneric reports whether a type is a generic, uninstantiated type
    97  // (generic signatures are not included).
    98  // TODO(gri) should we include signatures or assert that they are not present?
    99  func isGeneric(t Type) bool {
   100  	// A parameterized type is only generic if it doesn't have an instantiation already.
   101  	named, _ := t.(*Named)
   102  	return named != nil && named.obj != nil && named.targs == nil && named.TypeParams() != nil
   103  }
   104  
   105  // Comparable reports whether values of type T are comparable.
   106  func Comparable(T Type) bool {
   107  	return comparable(T, true, nil, nil)
   108  }
   109  
   110  // If dynamic is set, non-type parameter interfaces are always comparable.
   111  // If reportf != nil, it may be used to report why T is not comparable.
   112  func comparable(T Type, dynamic bool, seen map[Type]bool, reportf func(string, ...interface{})) bool {
   113  	if seen[T] {
   114  		return true
   115  	}
   116  	if seen == nil {
   117  		seen = make(map[Type]bool)
   118  	}
   119  	seen[T] = true
   120  
   121  	switch t := under(T).(type) {
   122  	case *Basic:
   123  		// assume invalid types to be comparable
   124  		// to avoid follow-up errors
   125  		return t.kind != UntypedNil
   126  	case *Pointer, *Chan:
   127  		return true
   128  	case *Struct:
   129  		for _, f := range t.fields {
   130  			if !comparable(f.typ, dynamic, seen, nil) {
   131  				if reportf != nil {
   132  					reportf("struct containing %s cannot be compared", f.typ)
   133  				}
   134  				return false
   135  			}
   136  		}
   137  		return true
   138  	case *Array:
   139  		if !comparable(t.elem, dynamic, seen, nil) {
   140  			if reportf != nil {
   141  				reportf("%s cannot be compared", t)
   142  			}
   143  			return false
   144  		}
   145  		return true
   146  	case *Interface:
   147  		return dynamic && !isTypeParam(T) || t.typeSet().IsComparable(seen)
   148  	}
   149  	return false
   150  }
   151  
   152  // hasNil reports whether type t includes the nil value.
   153  func hasNil(t Type) bool {
   154  	switch u := under(t).(type) {
   155  	case *Basic:
   156  		return u.kind == UnsafePointer
   157  	case *Slice, *Pointer, *Signature, *Map, *Chan:
   158  		return true
   159  	case *Interface:
   160  		return !isTypeParam(t) || u.typeSet().underIs(func(u Type) bool {
   161  			return u != nil && hasNil(u)
   162  		})
   163  	}
   164  	return false
   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 identical(x, y Type, cmpTags bool, p *ifacePair) bool {
   179  	if x == y {
   180  		return true
   181  	}
   182  
   183  	switch x := x.(type) {
   184  	case *Basic:
   185  		// Basic types are singletons except for the rune and byte
   186  		// aliases, thus we cannot solely rely on the x == y check
   187  		// above. See also comment in TypeName.IsAlias.
   188  		if y, ok := y.(*Basic); ok {
   189  			return x.kind == y.kind
   190  		}
   191  
   192  	case *Array:
   193  		// Two array types are identical if they have identical element types
   194  		// and the same array length.
   195  		if y, ok := y.(*Array); ok {
   196  			// If one or both array lengths are unknown (< 0) due to some error,
   197  			// assume they are the same to avoid spurious follow-on errors.
   198  			return (x.len < 0 || y.len < 0 || x.len == y.len) && identical(x.elem, y.elem, cmpTags, p)
   199  		}
   200  
   201  	case *Slice:
   202  		// Two slice types are identical if they have identical element types.
   203  		if y, ok := y.(*Slice); ok {
   204  			return identical(x.elem, y.elem, cmpTags, p)
   205  		}
   206  
   207  	case *Struct:
   208  		// Two struct types are identical if they have the same sequence of fields,
   209  		// and if corresponding fields have the same names, and identical types,
   210  		// and identical tags. Two embedded fields are considered to have the same
   211  		// name. Lower-case field names from different packages are always different.
   212  		if y, ok := y.(*Struct); ok {
   213  			if x.NumFields() == y.NumFields() {
   214  				for i, f := range x.fields {
   215  					g := y.fields[i]
   216  					if f.embedded != g.embedded ||
   217  						cmpTags && x.Tag(i) != y.Tag(i) ||
   218  						!f.sameId(g.pkg, g.name) ||
   219  						!identical(f.typ, g.typ, cmpTags, p) {
   220  						return false
   221  					}
   222  				}
   223  				return true
   224  			}
   225  		}
   226  
   227  	case *Pointer:
   228  		// Two pointer types are identical if they have identical base types.
   229  		if y, ok := y.(*Pointer); ok {
   230  			return identical(x.base, y.base, cmpTags, p)
   231  		}
   232  
   233  	case *Tuple:
   234  		// Two tuples types are identical if they have the same number of elements
   235  		// and corresponding elements have identical types.
   236  		if y, ok := y.(*Tuple); ok {
   237  			if x.Len() == y.Len() {
   238  				if x != nil {
   239  					for i, v := range x.vars {
   240  						w := y.vars[i]
   241  						if !identical(v.typ, w.typ, cmpTags, p) {
   242  							return false
   243  						}
   244  					}
   245  				}
   246  				return true
   247  			}
   248  		}
   249  
   250  	case *Signature:
   251  		y, _ := y.(*Signature)
   252  		if y == nil {
   253  			return false
   254  		}
   255  
   256  		// Two function types are identical if they have the same number of
   257  		// parameters and result values, corresponding parameter and result types
   258  		// are identical, and either both functions are variadic or neither is.
   259  		// Parameter and result names are not required to match, and type
   260  		// parameters are considered identical modulo renaming.
   261  
   262  		if x.TypeParams().Len() != y.TypeParams().Len() {
   263  			return false
   264  		}
   265  
   266  		// In the case of generic signatures, we will substitute in yparams and
   267  		// yresults.
   268  		yparams := y.params
   269  		yresults := y.results
   270  
   271  		if x.TypeParams().Len() > 0 {
   272  			// We must ignore type parameter names when comparing x and y. The
   273  			// easiest way to do this is to substitute x's type parameters for y's.
   274  			xtparams := x.TypeParams().list()
   275  			ytparams := y.TypeParams().list()
   276  
   277  			var targs []Type
   278  			for i := range xtparams {
   279  				targs = append(targs, x.TypeParams().At(i))
   280  			}
   281  			smap := makeSubstMap(ytparams, targs)
   282  
   283  			var check *Checker // ok to call subst on a nil *Checker
   284  
   285  			// Constraints must be pair-wise identical, after substitution.
   286  			for i, xtparam := range xtparams {
   287  				ybound := check.subst(token.NoPos, ytparams[i].bound, smap, nil)
   288  				if !identical(xtparam.bound, ybound, cmpTags, p) {
   289  					return false
   290  				}
   291  			}
   292  
   293  			yparams = check.subst(token.NoPos, y.params, smap, nil).(*Tuple)
   294  			yresults = check.subst(token.NoPos, y.results, smap, nil).(*Tuple)
   295  		}
   296  
   297  		return x.variadic == y.variadic &&
   298  			identical(x.params, yparams, cmpTags, p) &&
   299  			identical(x.results, yresults, cmpTags, p)
   300  
   301  	case *Union:
   302  		if y, _ := y.(*Union); y != nil {
   303  			// TODO(rfindley): can this be reached during type checking? If so,
   304  			// consider passing a type set map.
   305  			unionSets := make(map[*Union]*_TypeSet)
   306  			xset := computeUnionTypeSet(nil, unionSets, token.NoPos, x)
   307  			yset := computeUnionTypeSet(nil, unionSets, token.NoPos, y)
   308  			return xset.terms.equal(yset.terms)
   309  		}
   310  
   311  	case *Interface:
   312  		// Two interface types are identical if they describe the same type sets.
   313  		// With the existing implementation restriction, this simplifies to:
   314  		//
   315  		// Two interface types are identical if they have the same set of methods with
   316  		// the same names and identical function types, and if any type restrictions
   317  		// are the same. Lower-case method names from different packages are always
   318  		// different. The order of the methods is irrelevant.
   319  		if y, ok := y.(*Interface); ok {
   320  			xset := x.typeSet()
   321  			yset := y.typeSet()
   322  			if xset.comparable != yset.comparable {
   323  				return false
   324  			}
   325  			if !xset.terms.equal(yset.terms) {
   326  				return false
   327  			}
   328  			a := xset.methods
   329  			b := yset.methods
   330  			if len(a) == len(b) {
   331  				// Interface types are the only types where cycles can occur
   332  				// that are not "terminated" via named types; and such cycles
   333  				// can only be created via method parameter types that are
   334  				// anonymous interfaces (directly or indirectly) embedding
   335  				// the current interface. Example:
   336  				//
   337  				//    type T interface {
   338  				//        m() interface{T}
   339  				//    }
   340  				//
   341  				// If two such (differently named) interfaces are compared,
   342  				// endless recursion occurs if the cycle is not detected.
   343  				//
   344  				// If x and y were compared before, they must be equal
   345  				// (if they were not, the recursion would have stopped);
   346  				// search the ifacePair stack for the same pair.
   347  				//
   348  				// This is a quadratic algorithm, but in practice these stacks
   349  				// are extremely short (bounded by the nesting depth of interface
   350  				// type declarations that recur via parameter types, an extremely
   351  				// rare occurrence). An alternative implementation might use a
   352  				// "visited" map, but that is probably less efficient overall.
   353  				q := &ifacePair{x, y, p}
   354  				for p != nil {
   355  					if p.identical(q) {
   356  						return true // same pair was compared before
   357  					}
   358  					p = p.prev
   359  				}
   360  				if debug {
   361  					assertSortedMethods(a)
   362  					assertSortedMethods(b)
   363  				}
   364  				for i, f := range a {
   365  					g := b[i]
   366  					if f.Id() != g.Id() || !identical(f.typ, g.typ, cmpTags, q) {
   367  						return false
   368  					}
   369  				}
   370  				return true
   371  			}
   372  		}
   373  
   374  	case *Map:
   375  		// Two map types are identical if they have identical key and value types.
   376  		if y, ok := y.(*Map); ok {
   377  			return identical(x.key, y.key, cmpTags, p) && identical(x.elem, y.elem, cmpTags, p)
   378  		}
   379  
   380  	case *Chan:
   381  		// Two channel types are identical if they have identical value types
   382  		// and the same direction.
   383  		if y, ok := y.(*Chan); ok {
   384  			return x.dir == y.dir && identical(x.elem, y.elem, cmpTags, p)
   385  		}
   386  
   387  	case *Named:
   388  		// Two named types are identical if their type names originate
   389  		// in the same type declaration.
   390  		if y, ok := y.(*Named); ok {
   391  			xargs := x.TypeArgs().list()
   392  			yargs := y.TypeArgs().list()
   393  
   394  			if len(xargs) != len(yargs) {
   395  				return false
   396  			}
   397  
   398  			if len(xargs) > 0 {
   399  				// Instances are identical if their original type and type arguments
   400  				// are identical.
   401  				if !Identical(x.orig, y.orig) {
   402  					return false
   403  				}
   404  				for i, xa := range xargs {
   405  					if !Identical(xa, yargs[i]) {
   406  						return false
   407  					}
   408  				}
   409  				return true
   410  			}
   411  
   412  			// TODO(gri) Why is x == y not sufficient? And if it is,
   413  			//           we can just return false here because x == y
   414  			//           is caught in the very beginning of this function.
   415  			return x.obj == y.obj
   416  		}
   417  
   418  	case *TypeParam:
   419  		// nothing to do (x and y being equal is caught in the very beginning of this function)
   420  
   421  	case nil:
   422  		// avoid a crash in case of nil type
   423  
   424  	default:
   425  		unreachable()
   426  	}
   427  
   428  	return false
   429  }
   430  
   431  // identicalInstance reports if two type instantiations are identical.
   432  // Instantiations are identical if their origin and type arguments are
   433  // identical.
   434  func identicalInstance(xorig Type, xargs []Type, yorig Type, yargs []Type) bool {
   435  	if len(xargs) != len(yargs) {
   436  		return false
   437  	}
   438  
   439  	for i, xa := range xargs {
   440  		if !Identical(xa, yargs[i]) {
   441  			return false
   442  		}
   443  	}
   444  
   445  	return Identical(xorig, yorig)
   446  }
   447  
   448  // Default returns the default "typed" type for an "untyped" type;
   449  // it returns the incoming type for all other types. The default type
   450  // for untyped nil is untyped nil.
   451  func Default(t Type) Type {
   452  	if t, ok := t.(*Basic); ok {
   453  		switch t.kind {
   454  		case UntypedBool:
   455  			return Typ[Bool]
   456  		case UntypedInt:
   457  			return Typ[Int]
   458  		case UntypedRune:
   459  			return universeRune // use 'rune' name
   460  		case UntypedFloat:
   461  			return Typ[Float64]
   462  		case UntypedComplex:
   463  			return Typ[Complex128]
   464  		case UntypedString:
   465  			return Typ[String]
   466  		}
   467  	}
   468  	return t
   469  }
   470
View as plain text