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