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