pivot.go

     1  // Copyright 2026 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 main
     6  
     7  import (
     8  	"fmt"
     9  	"simd/archsimd/_gen/specgen"
    10  	"slices"
    11  )
    12  
    13  // A result is one figure: how many of how many.
    14  type result struct{ n, d int }
    15  
    16  func (r result) miss() int { return r.d - r.n }
    17  
    18  // A tally counts distinct keys at one grain, and how many of them are done. A
    19  // key counts as done if any row says so, which is well defined because every
    20  // predicate here is a function of the key rather than of the row.
    21  type tally[K comparable] struct {
    22  	all map[K]bool
    23  	hit map[K]bool
    24  }
    25  
    26  func (t *tally[K]) add(k K, done bool) {
    27  	if t.all == nil {
    28  		t.all, t.hit = map[K]bool{}, map[K]bool{}
    29  	}
    30  	t.all[k] = true
    31  	if done {
    32  		t.hit[k] = true
    33  	}
    34  }
    35  
    36  func (t *tally[K]) result() result { return result{len(t.hit), len(t.all)} }
    37  
    38  // has reports whether the key was counted at all; done, whether it is done.
    39  func (t *tally[K]) has(k K) bool  { return t.all[k] }
    40  func (t *tally[K]) done(k K) bool { return t.hit[k] }
    41  
    42  // missed returns the keys that were counted but are not done, formatted and
    43  // sorted, for reporting what keeps a count above zero.
    44  func (t *tally[K]) missed() []string {
    45  	var out []string
    46  	for k := range t.all {
    47  		if !t.hit[k] {
    48  			out = append(out, fmt.Sprint(k))
    49  		}
    50  	}
    51  	slices.Sort(out)
    52  	return out
    53  }
    54  
    55  // A pivot is a tally split by the value of some dimension: the report's
    56  // recurring shape is "for each X, what fraction of Y is done".
    57  type pivot[K comparable] struct {
    58  	by map[string]*tally[K]
    59  }
    60  
    61  func (p *pivot[K]) add(dim string, k K, done bool) {
    62  	if p.by == nil {
    63  		p.by = map[string]*tally[K]{}
    64  	}
    65  	t := p.by[dim]
    66  	if t == nil {
    67  		t = new(tally[K])
    68  		p.by[dim] = t
    69  	}
    70  	t.add(k, done)
    71  }
    72  
    73  // fold merges the tally for one dimension value into another, for reporting a
    74  // roll-up (simdgen's per-target runs) alongside its parts.
    75  func (p *pivot[K]) fold(from, to string) {
    76  	src := p.by[from]
    77  	for k := range src.all {
    78  		p.add(to, k, src.done(k))
    79  	}
    80  }
    81  
    82  func (p *pivot[K]) dims() []string { return sortedKeys(p.by) }
    83  
    84  func (p *pivot[K]) result(dim string) result {
    85  	if t := p.by[dim]; t != nil {
    86  		return t.result()
    87  	}
    88  	return result{}
    89  }
    90  
    91  // tallyBy is the common case: one pass over the fact table, keyed at a grain,
    92  // scored by a predicate.
    93  func tallyBy[K comparable](facts []fact, key func(fact) K, done func(fact) bool) *tally[K] {
    94  	t := new(tally[K])
    95  	for _, f := range facts {
    96  		t.add(key(f), done(f))
    97  	}
    98  	return t
    99  }
   100  
   101  // pivotBy is tallyBy, split by a dimension.
   102  func pivotBy[K comparable](facts []fact, dim func(fact) string, key func(fact) K, done func(fact) bool) *pivot[K] {
   103  	p := new(pivot[K])
   104  	for _, f := range facts {
   105  		p.add(dim(f), key(f), done(f))
   106  	}
   107  	return p
   108  }
   109  
   110  // countBy counts distinct keys among the rows, for figures that are a plain
   111  // count rather than a fraction.
   112  func countBy[K comparable](facts []fact, key func(fact) K) int {
   113  	seen := map[K]bool{}
   114  	for _, f := range facts {
   115  		seen[key(f)] = true
   116  	}
   117  	return len(seen)
   118  }
   119  
   120  func groupBy[T any, K comparable](s []T, key func(T) K) map[K][]T {
   121  	m := map[K][]T{}
   122  	for _, v := range s {
   123  		m[key(v)] = append(m[key(v)], v)
   124  	}
   125  	return m
   126  }
   127  
   128  func sortedKeys[V any](m map[string]V) []string {
   129  	ks := make([]string, 0, len(m))
   130  	for k := range m {
   131  		ks = append(ks, k)
   132  	}
   133  	slices.Sort(ks)
   134  	return ks
   135  }
   136  
   137  // equalBy reports whether two parameter lists agree under f. Types and names
   138  // are compared with the same code because the only difference is the field.
   139  func equalBy(a, b []param, f func(param) string) bool {
   140  	if len(a) != len(b) {
   141  		return false
   142  	}
   143  	for i := range a {
   144  		if f(a[i]) != f(b[i]) {
   145  			return false
   146  		}
   147  	}
   148  	return true
   149  }
   150  
   151  func paramType(p param) string { return p.typ }
   152  
   153  // specParams converts a spec signature's arguments to the same representation
   154  // as the API's, so one comparison serves both directions.
   155  func specParams(as []specgen.Arg) []param {
   156  	ps := make([]param, len(as))
   157  	for i, a := range as {
   158  		ps[i] = param{a.Name, a.Type.String()}
   159  	}
   160  	return ps
   161  }
   162  
   163  // named reports whether p has a name a doc or body could refer to. As in
   164  // specdoc.Fill, the blank identifier does not count.
   165  func named(p param) bool { return p.name != "" && p.name != "_" }
   166  
   167  // namesClash reports whether any argument named in both api and spec has
   168  // different names on the two sides. specdoc.Fill reports these as errors. Lists
   169  // of different lengths are a type mismatch, not a name one.
   170  func namesClash(api, spec []param) bool {
   171  	if len(api) != len(spec) {
   172  		return false
   173  	}
   174  	for i := range api {
   175  		if named(api[i]) && named(spec[i]) && api[i].name != spec[i].name {
   176  			return true
   177  		}
   178  	}
   179  	return false
   180  }
   181  
   182  // namesMissing reports whether any argument spec names is unnamed in api.
   183  // specdoc.Fill fills these in from spec.
   184  func namesMissing(api, spec []param) bool {
   185  	if len(api) != len(spec) {
   186  		return false
   187  	}
   188  	for i := range api {
   189  		if named(spec[i]) && !named(api[i]) {
   190  			return true
   191  		}
   192  	}
   193  	return false
   194  }
   195  
   196  // namesConsistent reports whether argument lists agree on names, where an
   197  // unnamed argument agrees with any name. Lists of different lengths disagree.
   198  func namesConsistent(lists [][]param) bool {
   199  	for _, l := range lists[1:] {
   200  		if len(l) != len(lists[0]) {
   201  			return false
   202  		}
   203  	}
   204  	for i := range lists[0] {
   205  		var name string
   206  		for _, l := range lists {
   207  			if !named(l[i]) {
   208  				continue
   209  			}
   210  			if name == "" {
   211  				name = l[i].name
   212  			} else if l[i].name != name {
   213  				return false
   214  			}
   215  		}
   216  	}
   217  	return true
   218  }
   219
View as plain text