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