structuraltype.go

     1  // Copyright 2022 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  package types
     6  
     7  // Implementation of structural type computation for types.
     8  
     9  // TODO: we would like to depend only on the types2 computation of structural type,
    10  // but we can only do that the next time we change the export format and export
    11  // structural type info along with each constraint type, since the compiler imports
    12  // types directly into types1 format.
    13  
    14  // A term describes elementary type sets:
    15  //
    16  // term{false, T}  set of type T
    17  // term{true, T}   set of types with underlying type t
    18  // term{}          empty set (we specifically check for typ == nil)
    19  type term struct {
    20  	tilde bool
    21  	typ   *Type
    22  }
    23  
    24  // StructuralType returns the structural type of an interface, or nil if it has no
    25  // structural type.
    26  func (t *Type) StructuralType() *Type {
    27  	sts, _ := specificTypes(t)
    28  	var su *Type
    29  	for _, st := range sts {
    30  		u := st.typ.Underlying()
    31  		if su != nil {
    32  			u = match(su, u)
    33  			if u == nil {
    34  				return nil
    35  			}
    36  		}
    37  		// su == nil || match(su, u) != nil
    38  		su = u
    39  	}
    40  	return su
    41  }
    42  
    43  // If x and y are identical, match returns x.
    44  // If x and y are identical channels but for their direction
    45  // and one of them is unrestricted, match returns the channel
    46  // with the restricted direction.
    47  // In all other cases, match returns nil.
    48  // x and y are assumed to be underlying types, hence are not named types.
    49  func match(x, y *Type) *Type {
    50  	if IdenticalStrict(x, y) {
    51  		return x
    52  	}
    53  
    54  	if x.IsChan() && y.IsChan() && IdenticalStrict(x.Elem(), y.Elem()) {
    55  		// We have channels that differ in direction only.
    56  		// If there's an unrestricted channel, select the restricted one.
    57  		// If both have the same direction, return x (either is fine).
    58  		switch {
    59  		case x.ChanDir().CanSend() && x.ChanDir().CanRecv():
    60  			return y
    61  		case y.ChanDir().CanSend() && y.ChanDir().CanRecv():
    62  			return x
    63  		}
    64  	}
    65  	return nil
    66  }
    67  
    68  // specificTypes returns the list of specific types of an interface type or nil if
    69  // there are none. It also returns a flag that indicates, for an empty term list
    70  // result, whether it represents the empty set, or the infinite set of all types (in
    71  // both cases, there are no specific types).
    72  func specificTypes(t *Type) (list []term, inf bool) {
    73  	t.wantEtype(TINTER)
    74  
    75  	// We have infinite term list before processing any type elements
    76  	// (or if there are no type elements).
    77  	inf = true
    78  	for _, m := range t.Methods().Slice() {
    79  		var r2 []term
    80  		inf2 := false
    81  
    82  		switch {
    83  		case m.IsMethod():
    84  			inf2 = true
    85  
    86  		case m.Type.IsUnion():
    87  			nt := m.Type.NumTerms()
    88  			for i := 0; i < nt; i++ {
    89  				t, tilde := m.Type.Term(i)
    90  				if t.IsInterface() {
    91  					r3, r3inf := specificTypes(t)
    92  					if r3inf {
    93  						// Union with an infinite set of types is
    94  						// infinite, so skip remaining terms.
    95  						r2 = nil
    96  						inf2 = true
    97  						break
    98  					}
    99  					// Add the elements of r3 to r2.
   100  					for _, r3e := range r3 {
   101  						r2 = insertType(r2, r3e)
   102  					}
   103  				} else {
   104  					r2 = insertType(r2, term{tilde, t})
   105  				}
   106  			}
   107  
   108  		case m.Type.IsInterface():
   109  			r2, inf2 = specificTypes(m.Type)
   110  
   111  		default:
   112  			// m.Type is a single non-interface type, so r2 is just a
   113  			// one-element list, inf2 is false.
   114  			r2 = []term{{false, m.Type}}
   115  		}
   116  
   117  		if inf2 {
   118  			// If the current type element has infinite types,
   119  			// its intersection with r is just r, so skip this type element.
   120  			continue
   121  		}
   122  
   123  		if inf {
   124  			// If r is infinite, then the intersection of r and r2 is just r2.
   125  			list = r2
   126  			inf = false
   127  			continue
   128  		}
   129  
   130  		// r and r2 are finite, so intersect r and r2.
   131  		var r3 []term
   132  		for _, re := range list {
   133  			for _, r2e := range r2 {
   134  				if tm := intersect(re, r2e); tm.typ != nil {
   135  					r3 = append(r3, tm)
   136  				}
   137  			}
   138  		}
   139  		list = r3
   140  	}
   141  	return
   142  }
   143  
   144  // insertType adds t to the returned list if it is not already in list.
   145  func insertType(list []term, tm term) []term {
   146  	for i, elt := range list {
   147  		if new := union(elt, tm); new.typ != nil {
   148  			// Replace existing elt with the union of elt and new.
   149  			list[i] = new
   150  			return list
   151  		}
   152  	}
   153  	return append(list, tm)
   154  }
   155  
   156  // If x and y are disjoint, return term with nil typ (which means the union should
   157  // include both types). If x and y are not disjoint, return the single type which is
   158  // the union of x and y.
   159  func union(x, y term) term {
   160  	if disjoint(x, y) {
   161  		return term{false, nil}
   162  	}
   163  	if x.tilde || !y.tilde {
   164  		return x
   165  	}
   166  	return y
   167  }
   168  
   169  // intersect returns the intersection x ∩ y.
   170  func intersect(x, y term) term {
   171  	if disjoint(x, y) {
   172  		return term{false, nil}
   173  	}
   174  	if !x.tilde || y.tilde {
   175  		return x
   176  	}
   177  	return y
   178  }
   179  
   180  // disjoint reports whether x ∩ y == ∅.
   181  func disjoint(x, y term) bool {
   182  	ux := x.typ
   183  	if y.tilde {
   184  		ux = ux.Underlying()
   185  	}
   186  	uy := y.typ
   187  	if x.tilde {
   188  		uy = uy.Underlying()
   189  	}
   190  	return !IdenticalStrict(ux, uy)
   191  }
   192
View as plain text