| // Copyright 2022 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package types |
| |
| // Implementation of structural type computation for types. |
| |
| // TODO: we would like to depend only on the types2 computation of structural type, |
| // but we can only do that the next time we change the export format and export |
| // structural type info along with each constraint type, since the compiler imports |
| // types directly into types1 format. |
| |
| // A term describes elementary type sets: |
| // |
| // term{false, T} set of type T |
| // term{true, T} set of types with underlying type t |
| // term{} empty set (we specifically check for typ == nil) |
| type term struct { |
| tilde bool |
| typ *Type |
| } |
| |
| // StructuralType returns the structural type of an interface, or nil if it has no |
| // structural type. |
| func (t *Type) StructuralType() *Type { |
| sts, _ := specificTypes(t) |
| var su *Type |
| for _, st := range sts { |
| u := st.typ.Underlying() |
| if su != nil { |
| u = match(su, u) |
| if u == nil { |
| return nil |
| } |
| } |
| // su == nil || match(su, u) != nil |
| su = u |
| } |
| return su |
| } |
| |
| // If x and y are identical, match returns x. |
| // If x and y are identical channels but for their direction |
| // and one of them is unrestricted, match returns the channel |
| // with the restricted direction. |
| // In all other cases, match returns nil. |
| // x and y are assumed to be underlying types, hence are not named types. |
| func match(x, y *Type) *Type { |
| if IdenticalStrict(x, y) { |
| return x |
| } |
| |
| if x.IsChan() && y.IsChan() && IdenticalStrict(x.Elem(), y.Elem()) { |
| // We have channels that differ in direction only. |
| // If there's an unrestricted channel, select the restricted one. |
| // If both have the same direction, return x (either is fine). |
| switch { |
| case x.ChanDir().CanSend() && x.ChanDir().CanRecv(): |
| return y |
| case y.ChanDir().CanSend() && y.ChanDir().CanRecv(): |
| return x |
| } |
| } |
| return nil |
| } |
| |
| // specificTypes returns the list of specific types of an interface type or nil if |
| // there are none. It also returns a flag that indicates, for an empty term list |
| // result, whether it represents the empty set, or the infinite set of all types (in |
| // both cases, there are no specific types). |
| func specificTypes(t *Type) (list []term, inf bool) { |
| t.wantEtype(TINTER) |
| |
| // We have infinite term list before processing any type elements |
| // (or if there are no type elements). |
| inf = true |
| for _, m := range t.Methods().Slice() { |
| var r2 []term |
| inf2 := false |
| |
| switch { |
| case m.IsMethod(): |
| inf2 = true |
| |
| case m.Type.IsUnion(): |
| nt := m.Type.NumTerms() |
| for i := 0; i < nt; i++ { |
| t, tilde := m.Type.Term(i) |
| if t.IsInterface() { |
| r3, r3inf := specificTypes(t) |
| if r3inf { |
| // Union with an infinite set of types is |
| // infinite, so skip remaining terms. |
| r2 = nil |
| inf2 = true |
| break |
| } |
| // Add the elements of r3 to r2. |
| for _, r3e := range r3 { |
| r2 = insertType(r2, r3e) |
| } |
| } else { |
| r2 = insertType(r2, term{tilde, t}) |
| } |
| } |
| |
| case m.Type.IsInterface(): |
| r2, inf2 = specificTypes(m.Type) |
| |
| default: |
| // m.Type is a single non-interface type, so r2 is just a |
| // one-element list, inf2 is false. |
| r2 = []term{{false, m.Type}} |
| } |
| |
| if inf2 { |
| // If the current type element has infinite types, |
| // its intersection with r is just r, so skip this type element. |
| continue |
| } |
| |
| if inf { |
| // If r is infinite, then the intersection of r and r2 is just r2. |
| list = r2 |
| inf = false |
| continue |
| } |
| |
| // r and r2 are finite, so intersect r and r2. |
| var r3 []term |
| for _, re := range list { |
| for _, r2e := range r2 { |
| if tm := intersect(re, r2e); tm.typ != nil { |
| r3 = append(r3, tm) |
| } |
| } |
| } |
| list = r3 |
| } |
| return |
| } |
| |
| // insertType adds t to the returned list if it is not already in list. |
| func insertType(list []term, tm term) []term { |
| for i, elt := range list { |
| if new := union(elt, tm); new.typ != nil { |
| // Replace existing elt with the union of elt and new. |
| list[i] = new |
| return list |
| } |
| } |
| return append(list, tm) |
| } |
| |
| // If x and y are disjoint, return term with nil typ (which means the union should |
| // include both types). If x and y are not disjoint, return the single type which is |
| // the union of x and y. |
| func union(x, y term) term { |
| if disjoint(x, y) { |
| return term{false, nil} |
| } |
| if x.tilde || !y.tilde { |
| return x |
| } |
| return y |
| } |
| |
| // intersect returns the intersection x ∩ y. |
| func intersect(x, y term) term { |
| if disjoint(x, y) { |
| return term{false, nil} |
| } |
| if !x.tilde || y.tilde { |
| return x |
| } |
| return y |
| } |
| |
| // disjoint reports whether x ∩ y == ∅. |
| func disjoint(x, y term) bool { |
| ux := x.typ |
| if y.tilde { |
| ux = ux.Underlying() |
| } |
| uy := y.typ |
| if x.tilde { |
| uy = uy.Underlying() |
| } |
| return !IdenticalStrict(ux, uy) |
| } |