metrics.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  	"cmp"
     9  	"path/filepath"
    10  	"regexp"
    11  	"simd/archsimd/_gen/specgen"
    12  	"slices"
    13  	"strings"
    14  
    15  	"gopkg.in/yaml.v3"
    16  )
    17  
    18  // specOp is one spec operation -- one function in package spec. It is the grain
    19  // spec is authored at, and the only grain at which "implemented nowhere" means
    20  // anything: one operation expands into many API names and many (receiver, name)
    21  // pairs. The API has no corresponding notion, so this is a spec-side diagnostic
    22  // rather than a fourth coverage grain (SPEC-TRANSITION.md §1.3).
    23  type specOp struct {
    24  	name     string // the operation's name in package spec
    25  	covPairs int    // pairs it generates that the API also declares
    26  }
    27  
    28  // Spec and the API are each a map from name to the set of receivers that name
    29  // is declared on. A relation is how those two sets stand for one name, and
    30  // walking the union of the two key sets classifies every name into exactly one
    31  // -- which the older "divergence classes" did not do, since a name whose sets
    32  // cross contributes to both sides at once.
    33  type relation int
    34  
    35  const (
    36  	relEqual    relation = iota // api = spec
    37  	relSubset                   // api is a proper subset of spec: spec covers more receivers
    38  	relSuperset                 // api is a proper superset of spec: spec covers fewer
    39  	relOverlap                  // they share receivers, neither contains the other
    40  	relDisjoint                 // they share the name and not one receiver
    41  	relSpecOnly                 // api = ∅: no target declares the name
    42  	relAPIOnly                  // spec = ∅: spec has never defined the name
    43  	numRelations
    44  )
    45  
    46  // shared reports whether both sides define the name. The api-only receivers of
    47  // a shared name are defects; under spec = ∅ they are ordinary coverage.
    48  func (r relation) shared() bool { return r != relSpecOnly && r != relAPIOnly }
    49  
    50  var relationName = [numRelations]string{
    51  	relEqual:    "api = spec",
    52  	relSubset:   "api ⊂ spec",
    53  	relSuperset: "api ⊃ spec",
    54  	relOverlap:  "overlapping",
    55  	relDisjoint: "disjoint",
    56  	relSpecOnly: "api = ∅",
    57  	relAPIOnly:  "spec = ∅",
    58  }
    59  
    60  // nameRel is one name, and how the two receiver sets stand under it.
    61  type nameRel struct {
    62  	name      string
    63  	rel       relation
    64  	api, spec int      // receiver-set sizes
    65  	apiOnly   []string // receivers only the API declares, sorted
    66  	specOnly  int      // receivers only spec generates
    67  }
    68  
    69  // relTotal is one row of the relation summary: how many names stand in it, and
    70  // how many receivers each side holds alone across them.
    71  type relTotal struct{ names, apiOnly, specOnly int }
    72  
    73  // fileCount pairs a filename with a count, for per-file breakdowns.
    74  type fileCount struct {
    75  	file string
    76  	n    int
    77  }
    78  
    79  // metrics is the whole report as data. Every field is a tally or a pivot, so
    80  // the summary and the sections below it read the same numbers and cannot
    81  // disagree.
    82  type metrics struct {
    83  	facts []fact
    84  	decls []*decl // the facts' declarations, deduplicated across configurations
    85  	spec  map[methodKey]*specgen.Func
    86  
    87  	// Coverage, at three grains and split two ways.
    88  	covTriple *tally[archMethodKey]
    89  	covPair   *tally[methodKey]
    90  	covName   *tally[string]
    91  	covTarget *pivot[archMethodKey]
    92  	covGen    *pivot[methodKey]
    93  	covMulti  *tally[string] // names emitted by more than one tool
    94  	covCommon *tally[string] // comments.yaml's .common_methods, spec-common's scope
    95  
    96  	specPairs, specNames int
    97  
    98  	// Divergence classes
    99  	ops                   []specOp               // spec source functions, sorted by name
   100  	specOnly              []string               // spec operations no target implements
   101  	names                 []nameRel              // every name either side defines, sorted
   102  	rel                   [numRelations]relTotal // m.names summed by relation
   103  	apiOnly, apiOnlyDecls int                    // the defect: over shared names only
   104  
   105  	// Agreement with spec where the two overlap. Names are split the way
   106  	// specdoc.Fill treats them: a named argument that disagrees with spec is a
   107  	// mismatch, and an unnamed one is a name Fill will fill in from spec.
   108  	agree, typeOK               *tally[declKey]
   109  	paramNameOK, resultNameOK   *tally[declKey]
   110  	paramsFilled, resultsFilled *tally[declKey]
   111  
   112  	// The invariant, checked without reference to spec.
   113  	consistent, typeSame, paramNameSame, resultNameSame *tally[methodKey]
   114  
   115  	// Documentation.
   116  	fromSpec           *tally[declKey]
   117  	bounded            *tally[declKey]
   118  	handConflict       int
   119  	handConflictByFile []fileCount
   120  	crossPkg           *tally[methodKey]
   121  	mirror             *tally[methodKey]
   122  
   123  	// The inputs being retired.
   124  	categories                       map[string]int
   125  	catEntries, catUniq, catExported int
   126  	catCompilerOnly                  int
   127  	catExportedFields                map[string]int
   128  	comments                         int
   129  	commentsSpecCovered              int
   130  	commutDrift                      int
   131  }
   132  
   133  func measure(api []*decl, specFuncs []*specgen.Func, genDir string) *metrics {
   134  	m := &metrics{spec: map[methodKey]*specgen.Func{}}
   135  
   136  	specNames := map[string]bool{}
   137  	for _, f := range specFuncs {
   138  		m.spec[specPair(f)] = f
   139  		specNames[f.Name] = true
   140  	}
   141  	m.specPairs, m.specNames = len(m.spec), len(specNames)
   142  
   143  	// The fact table: one row per declaration per configuration it builds in.
   144  	for _, d := range api {
   145  		if nonSpecOp(d.name) {
   146  			continue
   147  		}
   148  		m.decls = append(m.decls, d)
   149  		for _, t := range d.targets {
   150  			m.facts = append(m.facts, fact{d, t})
   151  		}
   152  	}
   153  
   154  	covered := func(f fact) bool { return m.spec[f.methodKey()] != nil }
   155  
   156  	// 1. Coverage. Same predicate, three grains, two dimensions.
   157  	m.covTriple = tallyBy(m.facts, fact.archMethodKey, covered)
   158  	m.covPair = tallyBy(m.facts, func(f fact) methodKey { return f.methodKey() }, covered)
   159  	m.covName = tallyBy(m.facts, func(f fact) string { return f.name }, func(f fact) bool { return specNames[f.name] })
   160  	m.covTarget = pivotBy(m.facts, func(f fact) string { return f.target }, fact.archMethodKey, covered)
   161  	m.covGen = pivotBy(m.facts, func(f fact) string { return f.gen }, func(f fact) methodKey { return f.methodKey() }, covered)
   162  	for _, g := range m.covGen.dims() {
   163  		if t, _, _ := strings.Cut(g, "/"); t != g {
   164  			m.covGen.fold(g, t)
   165  		}
   166  	}
   167  
   168  	// Names emitted by more than one tool are where the invariant is most
   169  	// exposed, because no single generator can see the conflict. simdgen's own
   170  	// runs share their inputs, so they do not count as more than one.
   171  	tools := groupBy(m.facts, func(f fact) string { return f.name })
   172  	m.covMulti = new(tally[string])
   173  	for name, fs := range tools {
   174  		seen := map[string]bool{}
   175  		for _, f := range fs {
   176  			if f.gen != "hand-written" {
   177  				seen[f.tool()] = true
   178  			}
   179  		}
   180  		if len(seen) > 1 {
   181  			m.covMulti.add(name, specNames[name])
   182  		}
   183  	}
   184  	m.covCommon = new(tally[string])
   185  	for _, n := range commonMethods(api) {
   186  		m.covCommon.add(n, m.covName.done(n))
   187  	}
   188  
   189  	// 2. Divergence classes.
   190  	byOp := map[string]*specOp{}
   191  	for _, f := range specFuncs {
   192  		src, _, _ := f.SpecFunc()
   193  		op := byOp[src]
   194  		if op == nil {
   195  			op = &specOp{name: src}
   196  			byOp[src] = op
   197  		}
   198  		if m.covPair.has(specPair(f)) {
   199  			op.covPairs++
   200  		}
   201  	}
   202  	for _, op := range byOp {
   203  		if op.covPairs == 0 {
   204  			// Operations implemented by spec but not by the API on any platform
   205  			// is measured at the grain spec is authored at: the source
   206  			// function. A spec operation with no covered declaration anywhere
   207  			// is likely a defect, because that takes four simultaneous
   208  			// omissions to explain away.
   209  			m.specOnly = append(m.specOnly, op.name)
   210  		}
   211  		m.ops = append(m.ops, *op)
   212  	}
   213  	slices.Sort(m.specOnly)
   214  	slices.SortFunc(m.ops, func(a, b specOp) int { return cmp.Compare(a.name, b.name) })
   215  	// The two maps the rest of this section is about, and the union of their
   216  	// keys. Everything below -- the defect count, the review queue, and the
   217  	// coverage gap -- is a statement about how one name's two receiver sets
   218  	// stand, so they are derived here once rather than counted three ways.
   219  	apiRecv, specRecv := map[string]map[string]bool{}, map[string]map[string]bool{}
   220  	add := func(m map[string]map[string]bool, name, recv string) {
   221  		if m[name] == nil {
   222  			m[name] = map[string]bool{}
   223  		}
   224  		m[name][recv] = true
   225  	}
   226  	for _, d := range m.decls {
   227  		add(apiRecv, d.name, d.recv)
   228  	}
   229  	for p := range m.spec {
   230  		if !nonSpecOp(p.name) {
   231  			add(specRecv, p.name, p.recv)
   232  		}
   233  	}
   234  	for name := range apiRecv {
   235  		m.names = append(m.names, nameRelation(name, apiRecv[name], specRecv[name]))
   236  	}
   237  	for name := range specRecv {
   238  		if apiRecv[name] == nil {
   239  			m.names = append(m.names, nameRelation(name, nil, specRecv[name]))
   240  		}
   241  	}
   242  	slices.SortFunc(m.names, func(a, b nameRel) int { return cmp.Compare(a.name, b.name) })
   243  	for _, r := range m.names {
   244  		t := &m.rel[r.rel]
   245  		t.names++
   246  		t.apiOnly += len(r.apiOnly)
   247  		t.specOnly += r.specOnly
   248  		if r.rel.shared() {
   249  			m.apiOnly += len(r.apiOnly)
   250  		}
   251  	}
   252  	// The same api-only receivers counted as declarations rather than pairs: one
   253  	// pair can be declared once per target.
   254  	m.apiOnlyDecls = countBy(filter(m.facts, func(f fact) bool {
   255  		return !covered(f) && specNames[f.name]
   256  	}), fact.declKey)
   257  
   258  	// 3. Agreement with spec, over the declarations spec covers.
   259  	overlap := filter(m.facts, covered)
   260  	specIn := func(f fact) []param { return specParams(m.spec[f.methodKey()].In) }
   261  	specOut := func(f fact) []param { return specParams(m.spec[f.methodKey()].Out) }
   262  	typeOK := func(f fact) bool {
   263  		return equalBy(f.in, specIn(f), paramType) && equalBy(f.out, specOut(f), paramType)
   264  	}
   265  	resultNameOK := func(f fact) bool { return !namesClash(f.out, specOut(f)) }
   266  	paramNameOK := func(f fact) bool { return !namesClash(f.in, specIn(f)) }
   267  	resultsFilled := func(f fact) bool { return !namesMissing(f.out, specOut(f)) }
   268  	paramsFilled := func(f fact) bool { return !namesMissing(f.in, specIn(f)) }
   269  
   270  	m.typeOK = tallyBy(overlap, fact.declKey, typeOK)
   271  	m.resultNameOK = tallyBy(overlap, fact.declKey, resultNameOK)
   272  	m.paramNameOK = tallyBy(overlap, fact.declKey, paramNameOK)
   273  	m.resultsFilled = tallyBy(overlap, fact.declKey, resultsFilled)
   274  	m.paramsFilled = tallyBy(overlap, fact.declKey, paramsFilled)
   275  	m.agree = tallyBy(overlap, fact.declKey, func(f fact) bool {
   276  		return typeOK(f) && resultNameOK(f) && paramNameOK(f)
   277  	})
   278  
   279  	// 4. The invariant: where a pair is declared more than once, do the
   280  	// declarations agree with each other? An unnamed argument agrees with any
   281  	// name, since only names that are used -- by a doc or a body -- need to agree.
   282  	m.consistent = new(tally[methodKey])
   283  	m.typeSame = new(tally[methodKey])
   284  	m.paramNameSame = new(tally[methodKey])
   285  	m.resultNameSame = new(tally[methodKey])
   286  	for p, ds := range groupBy(m.decls, (*decl).methodKey) {
   287  		if len(ds) < 2 {
   288  			continue
   289  		}
   290  		params := func(d *decl) []param { return d.in }
   291  		results := func(d *decl) []param { return d.out }
   292  		typesAgree := func(get func(*decl) []param) bool {
   293  			return !slices.ContainsFunc(ds[1:], func(d *decl) bool {
   294  				return !equalBy(get(ds[0]), get(d), paramType)
   295  			})
   296  		}
   297  		namesAgree := func(get func(*decl) []param) bool {
   298  			lists := make([][]param, len(ds))
   299  			for i, d := range ds {
   300  				lists[i] = get(d)
   301  			}
   302  			return namesConsistent(lists)
   303  		}
   304  		t := typesAgree(params) && typesAgree(results)
   305  		pn, rn := namesAgree(params), namesAgree(results)
   306  		m.typeSame.add(p, t)
   307  		m.paramNameSame.add(p, pn)
   308  		m.resultNameSame.add(p, rn)
   309  		m.consistent.add(p, t && pn && rn)
   310  	}
   311  
   312  	// 5. Documentation.
   313  	// A declaration is sourced from spec when its doc begins with spec's text --
   314  	// a prefix test, because Fill leaves the generator's notes below what it
   315  	// injects. Prose that disagrees instead is a conflict for doc-triage; a missing
   316  	// doc is not, since Fill would simply add one.
   317  	documented := filter(overlap, func(f fact) bool { return len(m.spec[f.methodKey()].Doc) > 0 })
   318  	saysSpec := func(f fact) bool {
   319  		specDoc, err := specgen.FormatComment(m.spec[f.methodKey()].Doc)
   320  		if err != nil {
   321  			return false
   322  		}
   323  		return strings.HasPrefix(f.doc, strings.TrimRight(specDoc, "\n"))
   324  	}
   325  	m.fromSpec = tallyBy(documented, fact.declKey, saysSpec)
   326  	handConflicts := filter(documented, func(f fact) bool {
   327  		return f.gen == "hand-written" && f.doc != "" && !saysSpec(f)
   328  	})
   329  	m.handConflict = countBy(handConflicts, fact.declKey)
   330  	byFile := map[string]int{}
   331  	seenByFile := map[declKey]bool{}
   332  	for _, f := range handConflicts {
   333  		dk := f.declKey()
   334  		if !seenByFile[dk] {
   335  			seenByFile[dk] = true
   336  			byFile[f.file]++
   337  		}
   338  	}
   339  	for _, k := range sortedKeys(byFile) {
   340  		m.handConflictByFile = append(m.handConflictByFile, fileCount{k, byFile[k]})
   341  	}
   342  
   343  	m.bounded = tallyBy(filter(m.facts, func(f fact) bool { return f.doc != "" }),
   344  		fact.declKey, func(f fact) bool { return f.hasSep })
   345  
   346  	// simd and archsimd document the same operations from different sources.
   347  	// Target-specific implementation notes (such as Asm: and CPU Feature:)
   348  	// and directives are ignored when comparing docs.
   349  	m.crossPkg = new(tally[methodKey])
   350  	docs := map[string]map[methodKey]string{"simd": {}, "archsimd": {}}
   351  	for _, d := range m.decls {
   352  		if d.doc != "" {
   353  			docs[d.pkg][d.methodKey()] = d.doc
   354  		}
   355  	}
   356  	for p, sd := range docs["simd"] {
   357  		if ad, ok := docs["archsimd"][p]; ok {
   358  			ssd, sad := stripDocNotes(sd), stripDocNotes(ad)
   359  			m.crossPkg.add(p, ssd != "" && ssd == sad)
   360  		}
   361  	}
   362  
   363  	// The hand-maintained mirror in package simd. This one deliberately spans
   364  	// the whole of both files, residue included: midway owns those docs too.
   365  	m.mirror = new(tally[methodKey])
   366  	stubs, emul := map[methodKey]string{}, map[methodKey]string{}
   367  	for _, d := range api {
   368  		switch d.file {
   369  		case "simd_stubs.go":
   370  			stubs[d.methodKey()] = d.doc
   371  		case "simd_emulated.go":
   372  			emul[d.methodKey()] = d.doc
   373  		}
   374  	}
   375  	for p, s := range stubs {
   376  		if e, ok := emul[p]; ok {
   377  			m.mirror.add(p, s == e)
   378  		}
   379  	}
   380  
   381  	// 7. The inputs being retired.
   382  	cat := makeCategoriesInventory(genDir)
   383  	m.categories = cat.allFields
   384  	m.catEntries = cat.entries
   385  	m.catUniq = cat.uniq
   386  	m.catExported = cat.exported
   387  	m.catCompilerOnly = cat.compilerOnly
   388  	m.catExportedFields = cat.exportedFields
   389  	m.comments = countMidwayComments(genDir)
   390  
   391  	// Comments.yaml entries that spec already covers, by name.
   392  	root := readYAML(commentsPath(genDir))
   393  	eachEntry(root, func(k, v *yaml.Node) {
   394  		if isString(v) && specNames[k.Value] {
   395  			m.commentsSpecCovered++
   396  		}
   397  	})
   398  
   399  	// Commutativity drift: spec vs categories.yaml exported entries.
   400  	m.commutDrift = commutativityDrift(genDir, m.spec)
   401  	return m
   402  }
   403  
   404  // nameRelation classifies one name by how its two receiver sets stand.
   405  func nameRelation(name string, api, spec map[string]bool) nameRel {
   406  	r := nameRel{name: name, api: len(api), spec: len(spec)}
   407  	shared := 0
   408  	for recv := range api {
   409  		if spec[recv] {
   410  			shared++
   411  		} else {
   412  			r.apiOnly = append(r.apiOnly, recv)
   413  		}
   414  	}
   415  	slices.Sort(r.apiOnly)
   416  	r.specOnly = len(spec) - shared
   417  	switch {
   418  	case len(spec) == 0:
   419  		r.rel = relAPIOnly
   420  	case len(api) == 0:
   421  		r.rel = relSpecOnly
   422  	case len(r.apiOnly) == 0 && r.specOnly == 0:
   423  		r.rel = relEqual
   424  	case len(r.apiOnly) == 0:
   425  		r.rel = relSubset
   426  	case r.specOnly == 0:
   427  		r.rel = relSuperset
   428  	case shared == 0:
   429  		r.rel = relDisjoint
   430  	default:
   431  		r.rel = relOverlap
   432  	}
   433  	return r
   434  }
   435  
   436  // commutativityDrift counts exported categories.yaml entries whose commutative field
   437  // disagrees with spec. Some go: values are regexps, so each is tried as one.
   438  func commutativityDrift(genDir string, spec map[methodKey]*specgen.Func) int {
   439  	var n int
   440  	paths, _ := filepath.Glob(filepath.Join(genDir, "simdgen", "ops", "*", "categories.yaml"))
   441  	slices.Sort(paths)
   442  	for _, p := range paths {
   443  		root := readYAML(p)
   444  		if root == nil || root.Kind != yaml.SequenceNode {
   445  			continue
   446  		}
   447  		for _, entry := range root.Content {
   448  			if entry.Kind != yaml.MappingNode {
   449  				continue
   450  			}
   451  			goName := mapValue(entry, "go")
   452  			if goName == nil {
   453  				continue
   454  			}
   455  			isExported := goName.Value != "" && !(goName.Value[0] >= 'a' && goName.Value[0] <= 'z')
   456  			if !isExported || mapValue(entry, "noTypes") != nil {
   457  				continue
   458  			}
   459  			commNode := mapValue(entry, "commutative")
   460  			if commNode == nil {
   461  				continue
   462  			}
   463  			catCommut := commNode.Value == "true"
   464  			re, err := regexp.Compile("^" + goName.Value + "$")
   465  			if err != nil {
   466  				continue
   467  			}
   468  			for p, f := range spec {
   469  				if re.MatchString(p.name) && f.Commutative != catCommut {
   470  					n++
   471  					break
   472  				}
   473  			}
   474  		}
   475  	}
   476  	return n
   477  }
   478  
   479  func filter[T any](s []T, keep func(T) bool) []T {
   480  	var out []T
   481  	for _, v := range s {
   482  		if keep(v) {
   483  			out = append(out, v)
   484  		}
   485  	}
   486  	return out
   487  }
   488  
   489  // specPair returns the (receiver, name) key for a spec function.
   490  func specPair(f *specgen.Func) methodKey {
   491  	var recv string
   492  	if f.Recv.Type != nil {
   493  		recv = f.Recv.Type.String()
   494  	}
   495  	return methodKey{recv, f.Name}
   496  }
   497  
   498  // stripDocNotes returns doc with target-specific implementation notes and
   499  // directives removed, leaving only spec-owned paragraphs.
   500  func stripDocNotes(doc string) string {
   501  	var keptParas []string
   502  	var curPara []string
   503  	flush := func() bool {
   504  		if len(curPara) == 0 {
   505  			return true
   506  		}
   507  		first := strings.TrimSpace(curPara[0])
   508  		if strings.HasPrefix(first, "//go:") || strings.HasPrefix(first, "//line ") {
   509  			return false
   510  		}
   511  		text := strings.TrimPrefix(first, "// ")
   512  		text = strings.TrimPrefix(text, "//")
   513  		if specgen.HasNotePrefix(text) {
   514  			return false
   515  		}
   516  		keptParas = append(keptParas, strings.Join(curPara, "\n"))
   517  		curPara = nil
   518  		return true
   519  	}
   520  
   521  	for _, line := range strings.Split(doc, "\n") {
   522  		trimmed := strings.TrimSpace(line)
   523  		if strings.HasPrefix(trimmed, "//go:") || strings.HasPrefix(trimmed, "//line ") {
   524  			if !flush() {
   525  				return strings.Join(keptParas, "\n//\n")
   526  			}
   527  			break
   528  		}
   529  		if trimmed == "//" {
   530  			if !flush() {
   531  				return strings.Join(keptParas, "\n//\n")
   532  			}
   533  			continue
   534  		}
   535  		curPara = append(curPara, line)
   536  	}
   537  	flush()
   538  	return strings.Join(keptParas, "\n//\n")
   539  }
   540
View as plain text