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