Black Lives Matter. Support the Equal Justice Initiative.

Source file src/go/types/predicates.go

Documentation: go/types

     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 types
     8  
     9  import "sort"
    10  
    11  func isNamed(typ Type) bool {
    12  	if _, ok := typ.(*Basic); ok {
    13  		return ok
    14  	}
    15  	_, ok := typ.(*Named)
    16  	return ok
    17  }
    18  
    19  func isBoolean(typ Type) bool {
    20  	t, ok := typ.Underlying().(*Basic)
    21  	return ok && t.info&IsBoolean != 0
    22  }
    23  
    24  func isInteger(typ Type) bool {
    25  	t, ok := typ.Underlying().(*Basic)
    26  	return ok && t.info&IsInteger != 0
    27  }
    28  
    29  func isUnsigned(typ Type) bool {
    30  	t, ok := typ.Underlying().(*Basic)
    31  	return ok && t.info&IsUnsigned != 0
    32  }
    33  
    34  func isFloat(typ Type) bool {
    35  	t, ok := typ.Underlying().(*Basic)
    36  	return ok && t.info&IsFloat != 0
    37  }
    38  
    39  func isComplex(typ Type) bool {
    40  	t, ok := typ.Underlying().(*Basic)
    41  	return ok && t.info&IsComplex != 0
    42  }
    43  
    44  func isNumeric(typ Type) bool {
    45  	t, ok := typ.Underlying().(*Basic)
    46  	return ok && t.info&IsNumeric != 0
    47  }
    48  
    49  func isString(typ Type) bool {
    50  	t, ok := typ.Underlying().(*Basic)
    51  	return ok && t.info&IsString != 0
    52  }
    53  
    54  func isTyped(typ Type) bool {
    55  	t, ok := typ.Underlying().(*Basic)
    56  	return !ok || t.info&IsUntyped == 0
    57  }
    58  
    59  func isUntyped(typ Type) bool {
    60  	t, ok := typ.Underlying().(*Basic)
    61  	return ok && t.info&IsUntyped != 0
    62  }
    63  
    64  func isOrdered(typ Type) bool {
    65  	t, ok := typ.Underlying().(*Basic)
    66  	return ok && t.info&IsOrdered != 0
    67  }
    68  
    69  func isConstType(typ Type) bool {
    70  	t, ok := typ.Underlying().(*Basic)
    71  	return ok && t.info&IsConstType != 0
    72  }
    73  
    74  // IsInterface reports whether typ is an interface type.
    75  func IsInterface(typ Type) bool {
    76  	_, ok := typ.Underlying().(*Interface)
    77  	return ok
    78  }
    79  
    80  // Comparable reports whether values of type T are comparable.
    81  func Comparable(T Type) bool {
    82  	return comparable(T, nil)
    83  }
    84  
    85  func comparable(T Type, seen map[Type]bool) bool {
    86  	if seen[T] {
    87  		return true
    88  	}
    89  	if seen == nil {
    90  		seen = make(map[Type]bool)
    91  	}
    92  	seen[T] = true
    93  
    94  	switch t := T.Underlying().(type) {
    95  	case *Basic:
    96  		// assume invalid types to be comparable
    97  		// to avoid follow-up errors
    98  		return t.kind != UntypedNil
    99  	case *Pointer, *Interface, *Chan:
   100  		return true
   101  	case *Struct:
   102  		for _, f := range t.fields {
   103  			if !comparable(f.typ, seen) {
   104  				return false
   105  			}
   106  		}
   107  		return true
   108  	case *Array:
   109  		return comparable(t.elem, seen)
   110  	}
   111  	return false
   112  }
   113  
   114  // hasNil reports whether a type includes the nil value.
   115  func hasNil(typ Type) bool {
   116  	switch t := typ.Underlying().(type) {
   117  	case *Basic:
   118  		return t.kind == UnsafePointer
   119  	case *Slice, *Pointer, *Signature, *Interface, *Map, *Chan:
   120  		return true
   121  	}
   122  	return false
   123  }
   124  
   125  // identical reports whether x and y are identical types.
   126  // Receivers of Signature types are ignored.
   127  func (check *Checker) identical(x, y Type) bool {
   128  	return check.identical0(x, y, true, nil)
   129  }
   130  
   131  // identicalIgnoreTags reports whether x and y are identical types if tags are ignored.
   132  // Receivers of Signature types are ignored.
   133  func (check *Checker) identicalIgnoreTags(x, y Type) bool {
   134  	return check.identical0(x, y, false, nil)
   135  }
   136  
   137  // An ifacePair is a node in a stack of interface type pairs compared for identity.
   138  type ifacePair struct {
   139  	x, y *Interface
   140  	prev *ifacePair
   141  }
   142  
   143  func (p *ifacePair) identical(q *ifacePair) bool {
   144  	return p.x == q.x && p.y == q.y || p.x == q.y && p.y == q.x
   145  }
   146  
   147  func (check *Checker) identical0(x, y Type, cmpTags bool, p *ifacePair) bool {
   148  	if x == y {
   149  		return true
   150  	}
   151  
   152  	switch x := x.(type) {
   153  	case *Basic:
   154  		// Basic types are singletons except for the rune and byte
   155  		// aliases, thus we cannot solely rely on the x == y check
   156  		// above. See also comment in TypeName.IsAlias.
   157  		if y, ok := y.(*Basic); ok {
   158  			return x.kind == y.kind
   159  		}
   160  
   161  	case *Array:
   162  		// Two array types are identical if they have identical element types
   163  		// and the same array length.
   164  		if y, ok := y.(*Array); ok {
   165  			// If one or both array lengths are unknown (< 0) due to some error,
   166  			// assume they are the same to avoid spurious follow-on errors.
   167  			return (x.len < 0 || y.len < 0 || x.len == y.len) && check.identical0(x.elem, y.elem, cmpTags, p)
   168  		}
   169  
   170  	case *Slice:
   171  		// Two slice types are identical if they have identical element types.
   172  		if y, ok := y.(*Slice); ok {
   173  			return check.identical0(x.elem, y.elem, cmpTags, p)
   174  		}
   175  
   176  	case *Struct:
   177  		// Two struct types are identical if they have the same sequence of fields,
   178  		// and if corresponding fields have the same names, and identical types,
   179  		// and identical tags. Two embedded fields are considered to have the same
   180  		// name. Lower-case field names from different packages are always different.
   181  		if y, ok := y.(*Struct); ok {
   182  			if x.NumFields() == y.NumFields() {
   183  				for i, f := range x.fields {
   184  					g := y.fields[i]
   185  					if f.embedded != g.embedded ||
   186  						cmpTags && x.Tag(i) != y.Tag(i) ||
   187  						!f.sameId(g.pkg, g.name) ||
   188  						!check.identical0(f.typ, g.typ, cmpTags, p) {
   189  						return false
   190  					}
   191  				}
   192  				return true
   193  			}
   194  		}
   195  
   196  	case *Pointer:
   197  		// Two pointer types are identical if they have identical base types.
   198  		if y, ok := y.(*Pointer); ok {
   199  			return check.identical0(x.base, y.base, cmpTags, p)
   200  		}
   201  
   202  	case *Tuple:
   203  		// Two tuples types are identical if they have the same number of elements
   204  		// and corresponding elements have identical types.
   205  		if y, ok := y.(*Tuple); ok {
   206  			if x.Len() == y.Len() {
   207  				if x != nil {
   208  					for i, v := range x.vars {
   209  						w := y.vars[i]
   210  						if !check.identical0(v.typ, w.typ, cmpTags, p) {
   211  							return false
   212  						}
   213  					}
   214  				}
   215  				return true
   216  			}
   217  		}
   218  
   219  	case *Signature:
   220  		// Two function types are identical if they have the same number of parameters
   221  		// and result values, corresponding parameter and result types are identical,
   222  		// and either both functions are variadic or neither is. Parameter and result
   223  		// names are not required to match.
   224  		if y, ok := y.(*Signature); ok {
   225  			return x.variadic == y.variadic &&
   226  				check.identical0(x.params, y.params, cmpTags, p) &&
   227  				check.identical0(x.results, y.results, cmpTags, p)
   228  		}
   229  
   230  	case *Interface:
   231  		// Two interface types are identical if they have the same set of methods with
   232  		// the same names and identical function types. Lower-case method names from
   233  		// different packages are always different. The order of the methods is irrelevant.
   234  		if y, ok := y.(*Interface); ok {
   235  			// If identical0 is called (indirectly) via an external API entry point
   236  			// (such as Identical, IdenticalIgnoreTags, etc.), check is nil. But in
   237  			// that case, interfaces are expected to be complete and lazy completion
   238  			// here is not needed.
   239  			if check != nil {
   240  				check.completeInterface(x)
   241  				check.completeInterface(y)
   242  			}
   243  			a := x.allMethods
   244  			b := y.allMethods
   245  			if len(a) == len(b) {
   246  				// Interface types are the only types where cycles can occur
   247  				// that are not "terminated" via named types; and such cycles
   248  				// can only be created via method parameter types that are
   249  				// anonymous interfaces (directly or indirectly) embedding
   250  				// the current interface. Example:
   251  				//
   252  				//    type T interface {
   253  				//        m() interface{T}
   254  				//    }
   255  				//
   256  				// If two such (differently named) interfaces are compared,
   257  				// endless recursion occurs if the cycle is not detected.
   258  				//
   259  				// If x and y were compared before, they must be equal
   260  				// (if they were not, the recursion would have stopped);
   261  				// search the ifacePair stack for the same pair.
   262  				//
   263  				// This is a quadratic algorithm, but in practice these stacks
   264  				// are extremely short (bounded by the nesting depth of interface
   265  				// type declarations that recur via parameter types, an extremely
   266  				// rare occurrence). An alternative implementation might use a
   267  				// "visited" map, but that is probably less efficient overall.
   268  				q := &ifacePair{x, y, p}
   269  				for p != nil {
   270  					if p.identical(q) {
   271  						return true // same pair was compared before
   272  					}
   273  					p = p.prev
   274  				}
   275  				if debug {
   276  					assert(sort.IsSorted(byUniqueMethodName(a)))
   277  					assert(sort.IsSorted(byUniqueMethodName(b)))
   278  				}
   279  				for i, f := range a {
   280  					g := b[i]
   281  					if f.Id() != g.Id() || !check.identical0(f.typ, g.typ, cmpTags, q) {
   282  						return false
   283  					}
   284  				}
   285  				return true
   286  			}
   287  		}
   288  
   289  	case *Map:
   290  		// Two map types are identical if they have identical key and value types.
   291  		if y, ok := y.(*Map); ok {
   292  			return check.identical0(x.key, y.key, cmpTags, p) && check.identical0(x.elem, y.elem, cmpTags, p)
   293  		}
   294  
   295  	case *Chan:
   296  		// Two channel types are identical if they have identical value types
   297  		// and the same direction.
   298  		if y, ok := y.(*Chan); ok {
   299  			return x.dir == y.dir && check.identical0(x.elem, y.elem, cmpTags, p)
   300  		}
   301  
   302  	case *Named:
   303  		// Two named types are identical if their type names originate
   304  		// in the same type declaration.
   305  		if y, ok := y.(*Named); ok {
   306  			return x.obj == y.obj
   307  		}
   308  
   309  	case nil:
   310  
   311  	default:
   312  		unreachable()
   313  	}
   314  
   315  	return false
   316  }
   317  
   318  // Default returns the default "typed" type for an "untyped" type;
   319  // it returns the incoming type for all other types. The default type
   320  // for untyped nil is untyped nil.
   321  //
   322  func Default(typ Type) Type {
   323  	if t, ok := typ.(*Basic); ok {
   324  		switch t.kind {
   325  		case UntypedBool:
   326  			return Typ[Bool]
   327  		case UntypedInt:
   328  			return Typ[Int]
   329  		case UntypedRune:
   330  			return universeRune // use 'rune' name
   331  		case UntypedFloat:
   332  			return Typ[Float64]
   333  		case UntypedComplex:
   334  			return Typ[Complex128]
   335  		case UntypedString:
   336  			return Typ[String]
   337  		}
   338  	}
   339  	return typ
   340  }
   341  

View as plain text