| 1 | // Copyright 2021 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 | // Code generated by copytermlist.go DO NOT EDIT. |
| 6 | |
| 7 | package typeparams |
| 8 | |
| 9 | import ( |
| 10 | "bytes" |
| 11 | "go/types" |
| 12 | ) |
| 13 | |
| 14 | // A termlist represents the type set represented by the union |
| 15 | // t1 ∪ y2 ∪ ... tn of the type sets of the terms t1 to tn. |
| 16 | // A termlist is in normal form if all terms are disjoint. |
| 17 | // termlist operations don't require the operands to be in |
| 18 | // normal form. |
| 19 | type termlist []*term |
| 20 | |
| 21 | // allTermlist represents the set of all types. |
| 22 | // It is in normal form. |
| 23 | var allTermlist = termlist{new(term)} |
| 24 | |
| 25 | // String prints the termlist exactly (without normalization). |
| 26 | func (xl termlist) String() string { |
| 27 | if len(xl) == 0 { |
| 28 | return "∅" |
| 29 | } |
| 30 | var buf bytes.Buffer |
| 31 | for i, x := range xl { |
| 32 | if i > 0 { |
| 33 | buf.WriteString(" ∪ ") |
| 34 | } |
| 35 | buf.WriteString(x.String()) |
| 36 | } |
| 37 | return buf.String() |
| 38 | } |
| 39 | |
| 40 | // isEmpty reports whether the termlist xl represents the empty set of types. |
| 41 | func (xl termlist) isEmpty() bool { |
| 42 | // If there's a non-nil term, the entire list is not empty. |
| 43 | // If the termlist is in normal form, this requires at most |
| 44 | // one iteration. |
| 45 | for _, x := range xl { |
| 46 | if x != nil { |
| 47 | return false |
| 48 | } |
| 49 | } |
| 50 | return true |
| 51 | } |
| 52 | |
| 53 | // isAll reports whether the termlist xl represents the set of all types. |
| 54 | func (xl termlist) isAll() bool { |
| 55 | // If there's a 𝓤 term, the entire list is 𝓤. |
| 56 | // If the termlist is in normal form, this requires at most |
| 57 | // one iteration. |
| 58 | for _, x := range xl { |
| 59 | if x != nil && x.typ == nil { |
| 60 | return true |
| 61 | } |
| 62 | } |
| 63 | return false |
| 64 | } |
| 65 | |
| 66 | // norm returns the normal form of xl. |
| 67 | func (xl termlist) norm() termlist { |
| 68 | // Quadratic algorithm, but good enough for now. |
| 69 | // TODO(gri) fix asymptotic performance |
| 70 | used := make([]bool, len(xl)) |
| 71 | var rl termlist |
| 72 | for i, xi := range xl { |
| 73 | if xi == nil || used[i] { |
| 74 | continue |
| 75 | } |
| 76 | for j := i + 1; j < len(xl); j++ { |
| 77 | xj := xl[j] |
| 78 | if xj == nil || used[j] { |
| 79 | continue |
| 80 | } |
| 81 | if u1, u2 := xi.union(xj); u2 == nil { |
| 82 | // If we encounter a 𝓤 term, the entire list is 𝓤. |
| 83 | // Exit early. |
| 84 | // (Note that this is not just an optimization; |
| 85 | // if we continue, we may end up with a 𝓤 term |
| 86 | // and other terms and the result would not be |
| 87 | // in normal form.) |
| 88 | if u1.typ == nil { |
| 89 | return allTermlist |
| 90 | } |
| 91 | xi = u1 |
| 92 | used[j] = true // xj is now unioned into xi - ignore it in future iterations |
| 93 | } |
| 94 | } |
| 95 | rl = append(rl, xi) |
| 96 | } |
| 97 | return rl |
| 98 | } |
| 99 | |
| 100 | // union returns the union xl ∪ yl. |
| 101 | func (xl termlist) union(yl termlist) termlist { |
| 102 | return append(xl, yl...).norm() |
| 103 | } |
| 104 | |
| 105 | // intersect returns the intersection xl ∩ yl. |
| 106 | func (xl termlist) intersect(yl termlist) termlist { |
| 107 | if xl.isEmpty() || yl.isEmpty() { |
| 108 | return nil |
| 109 | } |
| 110 | |
| 111 | // Quadratic algorithm, but good enough for now. |
| 112 | // TODO(gri) fix asymptotic performance |
| 113 | var rl termlist |
| 114 | for _, x := range xl { |
| 115 | for _, y := range yl { |
| 116 | if r := x.intersect(y); r != nil { |
| 117 | rl = append(rl, r) |
| 118 | } |
| 119 | } |
| 120 | } |
| 121 | return rl.norm() |
| 122 | } |
| 123 | |
| 124 | // equal reports whether xl and yl represent the same type set. |
| 125 | func (xl termlist) equal(yl termlist) bool { |
| 126 | // TODO(gri) this should be more efficient |
| 127 | return xl.subsetOf(yl) && yl.subsetOf(xl) |
| 128 | } |
| 129 | |
| 130 | // includes reports whether t ∈ xl. |
| 131 | func (xl termlist) includes(t types.Type) bool { |
| 132 | for _, x := range xl { |
| 133 | if x.includes(t) { |
| 134 | return true |
| 135 | } |
| 136 | } |
| 137 | return false |
| 138 | } |
| 139 | |
| 140 | // supersetOf reports whether y ⊆ xl. |
| 141 | func (xl termlist) supersetOf(y *term) bool { |
| 142 | for _, x := range xl { |
| 143 | if y.subsetOf(x) { |
| 144 | return true |
| 145 | } |
| 146 | } |
| 147 | return false |
| 148 | } |
| 149 | |
| 150 | // subsetOf reports whether xl ⊆ yl. |
| 151 | func (xl termlist) subsetOf(yl termlist) bool { |
| 152 | if yl.isEmpty() { |
| 153 | return xl.isEmpty() |
| 154 | } |
| 155 | |
| 156 | // each term x of xl must be a subset of yl |
| 157 | for _, x := range xl { |
| 158 | if !yl.supersetOf(x) { |
| 159 | return false // x is not a subset yl |
| 160 | } |
| 161 | } |
| 162 | return true |
| 163 | } |
| 164 |
Members