predicates.go

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