Source file src/go/types/predicates.go

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

View as plain text