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