termlist.go

     1  // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
     2  
     3  // Copyright 2021 The Go Authors. All rights reserved.
     4  // Use of this source code is governed by a BSD-style
     5  // license that can be found in the LICENSE file.
     6  
     7  package types
     8  
     9  import "strings"
    10  
    11  // A termlist represents the type set represented by the union
    12  // t1 ∪ y2 ∪ ... tn of the type sets of the terms t1 to tn.
    13  // A termlist is in normal form if all terms are disjoint.
    14  // termlist operations don't require the operands to be in
    15  // normal form.
    16  type termlist []*term
    17  
    18  // allTermlist represents the set of all types.
    19  // It is in normal form.
    20  var allTermlist = termlist{new(term)}
    21  
    22  // termSep is the separator used between individual terms.
    23  const termSep = " | "
    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 strings.Builder
    31  	for i, x := range xl {
    32  		if i > 0 {
    33  			buf.WriteString(termSep)
    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 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
View as plain text