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