termlist.go

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