164 lines
3.8 KiB
Go
164 lines
3.8 KiB
Go
// Copyright 2021 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.
|
||
|
||
// Code generated by copytermlist.go DO NOT EDIT.
|
||
|
||
package typeparams
|
||
|
||
import (
|
||
"bytes"
|
||
"go/types"
|
||
)
|
||
|
||
// A termlist represents the type set represented by the union
|
||
// t1 ∪ y2 ∪ ... tn of the type sets of the terms t1 to tn.
|
||
// A termlist is in normal form if all terms are disjoint.
|
||
// termlist operations don't require the operands to be in
|
||
// normal form.
|
||
type termlist []*term
|
||
|
||
// allTermlist represents the set of all types.
|
||
// It is in normal form.
|
||
var allTermlist = termlist{new(term)}
|
||
|
||
// String prints the termlist exactly (without normalization).
|
||
func (xl termlist) String() string {
|
||
if len(xl) == 0 {
|
||
return "∅"
|
||
}
|
||
var buf bytes.Buffer
|
||
for i, x := range xl {
|
||
if i > 0 {
|
||
buf.WriteString(" ∪ ")
|
||
}
|
||
buf.WriteString(x.String())
|
||
}
|
||
return buf.String()
|
||
}
|
||
|
||
// isEmpty reports whether the termlist xl represents the empty set of types.
|
||
func (xl termlist) isEmpty() bool {
|
||
// If there's a non-nil term, the entire list is not empty.
|
||
// If the termlist is in normal form, this requires at most
|
||
// one iteration.
|
||
for _, x := range xl {
|
||
if x != nil {
|
||
return false
|
||
}
|
||
}
|
||
return true
|
||
}
|
||
|
||
// isAll reports whether the termlist xl represents the set of all types.
|
||
func (xl termlist) isAll() bool {
|
||
// If there's a 𝓤 term, the entire list is 𝓤.
|
||
// If the termlist is in normal form, this requires at most
|
||
// one iteration.
|
||
for _, x := range xl {
|
||
if x != nil && x.typ == nil {
|
||
return true
|
||
}
|
||
}
|
||
return false
|
||
}
|
||
|
||
// norm returns the normal form of xl.
|
||
func (xl termlist) norm() termlist {
|
||
// Quadratic algorithm, but good enough for now.
|
||
// TODO(gri) fix asymptotic performance
|
||
used := make([]bool, len(xl))
|
||
var rl termlist
|
||
for i, xi := range xl {
|
||
if xi == nil || used[i] {
|
||
continue
|
||
}
|
||
for j := i + 1; j < len(xl); j++ {
|
||
xj := xl[j]
|
||
if xj == nil || used[j] {
|
||
continue
|
||
}
|
||
if u1, u2 := xi.union(xj); u2 == nil {
|
||
// If we encounter a 𝓤 term, the entire list is 𝓤.
|
||
// Exit early.
|
||
// (Note that this is not just an optimization;
|
||
// if we continue, we may end up with a 𝓤 term
|
||
// and other terms and the result would not be
|
||
// in normal form.)
|
||
if u1.typ == nil {
|
||
return allTermlist
|
||
}
|
||
xi = u1
|
||
used[j] = true // xj is now unioned into xi - ignore it in future iterations
|
||
}
|
||
}
|
||
rl = append(rl, xi)
|
||
}
|
||
return rl
|
||
}
|
||
|
||
// union returns the union xl ∪ yl.
|
||
func (xl termlist) union(yl termlist) termlist {
|
||
return append(xl, yl...).norm()
|
||
}
|
||
|
||
// intersect returns the intersection xl ∩ yl.
|
||
func (xl termlist) intersect(yl termlist) termlist {
|
||
if xl.isEmpty() || yl.isEmpty() {
|
||
return nil
|
||
}
|
||
|
||
// Quadratic algorithm, but good enough for now.
|
||
// TODO(gri) fix asymptotic performance
|
||
var rl termlist
|
||
for _, x := range xl {
|
||
for _, y := range yl {
|
||
if r := x.intersect(y); r != nil {
|
||
rl = append(rl, r)
|
||
}
|
||
}
|
||
}
|
||
return rl.norm()
|
||
}
|
||
|
||
// equal reports whether xl and yl represent the same type set.
|
||
func (xl termlist) equal(yl termlist) bool {
|
||
// TODO(gri) this should be more efficient
|
||
return xl.subsetOf(yl) && yl.subsetOf(xl)
|
||
}
|
||
|
||
// includes reports whether t ∈ xl.
|
||
func (xl termlist) includes(t types.Type) bool {
|
||
for _, x := range xl {
|
||
if x.includes(t) {
|
||
return true
|
||
}
|
||
}
|
||
return false
|
||
}
|
||
|
||
// supersetOf reports whether y ⊆ xl.
|
||
func (xl termlist) supersetOf(y *term) bool {
|
||
for _, x := range xl {
|
||
if y.subsetOf(x) {
|
||
return true
|
||
}
|
||
}
|
||
return false
|
||
}
|
||
|
||
// subsetOf reports whether xl ⊆ yl.
|
||
func (xl termlist) subsetOf(yl termlist) bool {
|
||
if yl.isEmpty() {
|
||
return xl.isEmpty()
|
||
}
|
||
|
||
// each term x of xl must be a subset of yl
|
||
for _, x := range xl {
|
||
if !yl.supersetOf(x) {
|
||
return false // x is not a subset yl
|
||
}
|
||
}
|
||
return true
|
||
}
|