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