diff options
Diffstat (limited to 'src/cmd/compile/internal/types2/union.go')
| -rw-r--r-- | src/cmd/compile/internal/types2/union.go | 206 |
1 files changed, 39 insertions, 167 deletions
diff --git a/src/cmd/compile/internal/types2/union.go b/src/cmd/compile/internal/types2/union.go index 1215ef9057..fcd83ce688 100644 --- a/src/cmd/compile/internal/types2/union.go +++ b/src/cmd/compile/internal/types2/union.go @@ -9,17 +9,17 @@ import "cmd/compile/internal/syntax" // ---------------------------------------------------------------------------- // API -// A Union represents a union of terms. +// A Union represents a union of terms embedded in an interface. type Union struct { - terms []*term + terms []*term // list of syntactical terms (not a canonicalized termlist) + tset *TypeSet // type set described by this union, computed lazily } // NewUnion returns a new Union type with the given terms (types[i], tilde[i]). -// The lengths of both arguments must match. An empty union represents the set -// of no types. +// The lengths of both arguments must match. It is an error to create an empty +// union; they are syntactically not possible. func NewUnion(types []Type, tilde []bool) *Union { return newUnion(types, tilde) } -func (u *Union) IsEmpty() bool { return len(u.terms) == 0 } func (u *Union) NumTerms() int { return len(u.terms) } func (u *Union) Term(i int) (Type, bool) { t := u.terms[i]; return t.typ, t.tilde } @@ -29,12 +29,10 @@ func (u *Union) String() string { return TypeString(u, nil) } // ---------------------------------------------------------------------------- // Implementation -var emptyUnion = new(Union) - func newUnion(types []Type, tilde []bool) *Union { assert(len(types) == len(tilde)) if len(types) == 0 { - return emptyUnion + panic("empty union") } t := new(Union) t.terms = make([]*term, len(types)) @@ -44,52 +42,23 @@ func newUnion(types []Type, tilde []bool) *Union { return t } -// is reports whether f returns true for all terms of u. -func (u *Union) is(f func(*term) bool) bool { - if u.IsEmpty() { - return false - } - for _, t := range u.terms { - if !f(t) { - return false - } - } - return true -} - -// underIs reports whether f returned true for the underlying types of all terms of u. -func (u *Union) underIs(f func(Type) bool) bool { - if u.IsEmpty() { - return false - } - for _, t := range u.terms { - if !f(under(t.typ)) { - return false - } - } - return true -} - func parseUnion(check *Checker, tlist []syntax.Expr) Type { - var types []Type - var tilde []bool + var terms []*term for _, x := range tlist { - t, d := parseTilde(check, x) - if len(tlist) == 1 && !d { - return t // single type + tilde, typ := parseTilde(check, x) + if len(tlist) == 1 && !tilde { + return typ // single type } - types = append(types, t) - tilde = append(tilde, d) + terms = append(terms, &term{tilde, typ}) } - // Ensure that each type is only present once in the type list. - // It's ok to do this check later because it's not a requirement - // for correctness of the code. + // Check validity of terms. + // Do this check later because it requires types to be set up. // Note: This is a quadratic algorithm, but unions tend to be short. check.later(func() { - for i, t := range types { - t := expand(t) - if t == Typ[Invalid] { + for i, t := range terms { + typ := expand(t.typ) + if typ == Typ[Invalid] { continue } @@ -105,16 +74,16 @@ func parseUnion(check *Checker, tlist []syntax.Expr) Type { } } - u := under(t) + u := under(typ) f, _ := u.(*Interface) - if tilde[i] { + if t.tilde { if f != nil { - check.errorf(x, "invalid use of ~ (%s is an interface)", t) + check.errorf(x, "invalid use of ~ (%s is an interface)", typ) continue // don't report another error for t } - if !Identical(u, t) { - check.errorf(x, "invalid use of ~ (underlying type of %s is %s)", t, u) + if !Identical(u, typ) { + check.errorf(x, "invalid use of ~ (underlying type of %s is %s)", typ, u) continue // don't report another error for t } } @@ -127,19 +96,18 @@ func parseUnion(check *Checker, tlist []syntax.Expr) Type { continue // don't report another error for t } - // Complain about duplicate entries a|a, but also a|~a, and ~a|~a. - // TODO(gri) We should also exclude myint|~int since myint is included in ~int. - if includes(types[:i], t) { - // TODO(gri) this currently doesn't print the ~ if present - check.softErrorf(pos, "duplicate term %s in union element", t) + // Report overlapping (non-disjoint) terms such as + // a|a, a|~a, ~a|~a, and ~a|A (where under(A) == a). + if j := overlappingTerm(terms[:i], t); j >= 0 { + check.softErrorf(pos, "overlapping terms %s and %s", t, terms[j]) } } }) - return newUnion(types, tilde) + return &Union{terms, nil} } -func parseTilde(check *Checker, x syntax.Expr) (typ Type, tilde bool) { +func parseTilde(check *Checker, x syntax.Expr) (tilde bool, typ Type) { if op, _ := x.(*syntax.Operation); op != nil && op.Op == syntax.Tilde { x = op.X tilde = true @@ -153,116 +121,20 @@ func parseTilde(check *Checker, x syntax.Expr) (typ Type, tilde bool) { return } -// intersect computes the intersection of the types x and y, -// A nil type stands for the set of all types; an empty union -// stands for the set of no types. -func intersect(x, y Type) (r Type) { - // If one of the types is nil (no restrictions) - // the result is the other type. - switch { - case x == nil: - return y - case y == nil: - return x - } - - // Compute the terms which are in both x and y. - // TODO(gri) This is not correct as it may not always compute - // the "largest" intersection. For instance, for - // x = myInt|~int, y = ~int - // we get the result myInt but we should get ~int. - xu, _ := x.(*Union) - yu, _ := y.(*Union) - switch { - case xu != nil && yu != nil: - return &Union{intersectTerms(xu.terms, yu.terms)} - - case xu != nil: - if r, _ := xu.intersect(y, false); r != nil { - return y - } - - case yu != nil: - if r, _ := yu.intersect(x, false); r != nil { - return x - } - - default: // xu == nil && yu == nil - if Identical(x, y) { - return x - } - } - - return emptyUnion -} - -// includes reports whether typ is in list. -func includes(list []Type, typ Type) bool { - for _, e := range list { - if Identical(typ, e) { - return true - } - } - return false -} - -// intersect computes the intersection of the union u and term (y, yt) -// and returns the intersection term, if any. Otherwise the result is -// (nil, false). -// TODO(gri) this needs to cleaned up/removed once we switch to lazy -// union type set computation. -func (u *Union) intersect(y Type, yt bool) (Type, bool) { - under_y := under(y) - for _, x := range u.terms { - xt := x.tilde - // determine which types xx, yy to compare - xx := x.typ - if yt { - xx = under(xx) - } - yy := y - if xt { - yy = under_y - } - if Identical(xx, yy) { - // T ∩ T = T - // T ∩ ~t = T - // ~t ∩ T = T - // ~t ∩ ~t = ~t - return xx, xt && yt - } - } - return nil, false -} - -func identicalTerms(list1, list2 []*term) bool { - if len(list1) != len(list2) { - return false - } - // Every term in list1 must be in list2. - // Quadratic algorithm, but probably good enough for now. - // TODO(gri) we need a fast quick type ID/hash for all types. -L: - for _, x := range list1 { - for _, y := range list2 { - if x.equal(y) { - continue L // x is in list2 +// overlappingTerm reports the index of the term x in terms which is +// overlapping (not disjoint) from y. The result is < 0 if there is no +// such term. +func overlappingTerm(terms []*term, y *term) int { + for i, x := range terms { + // disjoint requires non-nil, non-top arguments + if debug { + if x == nil || x.typ == nil || y == nil || y.typ == nil { + panic("internal error: empty or top union term") } } - return false - } - return true -} - -func intersectTerms(list1, list2 []*term) (list []*term) { - // Quadratic algorithm, but good enough for now. - // TODO(gri) fix asymptotic performance - for _, x := range list1 { - for _, y := range list2 { - if r := x.intersect(y); r != nil { - list = append(list, r) - } + if !x.disjoint(y) { + return i } } - return + return -1 } |