termlist.go

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