qmk-rgb/internal/spotted/generate/main.go

// Command generate reads a checkout of VIA's public definition collection and
// writes internal/spotted/spotted.json: for every effect ID a board's
// definitions have been seen to use, which spellings occur and how often.
//
// It exists because the alternative is a name the tool made up. No definition
// file, firmware image, protocol query or version number yields the spelling of
// an effect for a board whose vendor never wrote one down, and README says so
// rather than filling the gap. What can be measured is what the boards that did
// write theirs call the same number, which is evidence and not an answer: the
// measurement this tool takes itself finds that 95 of the 123 definitions
// carrying an rgb_matrix effect list are one manufacturer's, so a bare majority
// would report one house style as a community consensus. The counts and the
// vendor concentration travel with every name for that reason.
//
// The output is generated, never hand-edited, and it carries the commit it was
// measured from. It is a snapshot of a collection that moves, so a name in it
// can be out of date; the SHA is what says how out of date.
//
// Usage:
//
//	generate <path-to-the-via/keyboards> > internal/spotted/spotted.json
package main

import (
	"encoding/json"
	"fmt"
	"io/fs"
	"os"
	"os/exec"
	"path/filepath"
	"sort"
	"strings"
)

// effectValueKeySuffix is what a VIA value key for an effect ends in. All effect
// dropdowns in the collection use a QMK value key, so keying on the suffix keeps
// this from needing a list of the keys themselves.
const effectValueKeySuffix = "_effect"

// maxCandidates is how many spellings per ID are kept. Three is what makes the
// disagreement visible: where two boards call one number different effects, the
// runner-up is the whole point, and a longer tail would only bury it.
const maxCandidates = 3

// Document is one board's effect list, keyed by the VIA value key it was under.
type Document struct {
	Vendor  string
	Effects map[string]map[int]string
}

// Candidate is one spelling seen for an effect ID, and how many boards wrote it.
type Candidate struct {
	Name  string `json:"name"`
	Count int    `json:"count"`
}

// Observation is what was seen for one effect ID under one value key.
type Observation struct {
	// Boards is how many definitions listed this ID at all. It is the sample
	// size, and a low one is why a name here is worth less than a name a
	// definition file carries.
	Boards int `json:"boards"`
	// Candidates are the spellings, most frequent first.
	Candidates []Candidate `json:"candidates"`
	// TopVendor is the manufacturer behind the most of them, and TopVendorCount
	// how many. A name whose share is nearly all one vendor is that vendor's
	// spelling, not a community one, and this is what says so.
	TopVendor      string `json:"topVendor,omitempty"`
	TopVendorCount int    `json:"topVendorCount,omitempty"`
}

// Report is the whole measurement, and what it was measured from.
type Report struct {
	// Source and Commit pin the collection. A name in here is a claim about the
	// collection at that commit, and a collection that moves means the claim
	// ages.
	Source string `json:"source"`
	Commit string `json:"commit,omitempty"`
	// Definitions is how many files were read, and EffectBoards how many of them
	// carried an effect list at all. The two differ by an order of magnitude,
	// which is the size of the problem this file cannot solve.
	Definitions  int `json:"definitions"`
	EffectBoards int `json:"effectBoards"`
	// Effects is keyed by the VIA value key, then by effect ID as a string,
	// because JSON object keys are strings and the IDs are bytes.
	Effects map[string]map[string]Observation `json:"effects"`
}

func main() {
	if len(os.Args) != 2 {
		fmt.Fprintln(os.Stderr, "usage: generate <path-to-the-via/keyboards>")
		os.Exit(2)
	}
	root := os.Args[1]
	report, err := measure(root)
	if err != nil {
		fmt.Fprintln(os.Stderr, err)
		os.Exit(1)
	}
	enc := json.NewEncoder(os.Stdout)
	enc.SetIndent("", " ")
	if err := enc.Encode(report); err != nil {
		fmt.Fprintln(os.Stderr, err)
		os.Exit(1)
	}
}

func measure(root string) (*Report, error) {
	v3 := filepath.Join(root, "v3")
	// The collection nests to a varying depth, so it is walked rather than
	// globbed: a glob of a fixed depth reads a fraction of it, and a measurement
	// over a fraction is a measurement of something else.
	var paths []string
	err := filepath.WalkDir(v3, func(path string, entry fs.DirEntry, err error) error {
		if err != nil {
			return err
		}
		if !entry.IsDir() && strings.HasSuffix(entry.Name(), ".json") {
			paths = append(paths, path)
		}
		return nil
	})
	if err != nil {
		return nil, err
	}
	sort.Strings(paths)

	report := &Report{
		Source:      "https://github.com/the-via/keyboards",
		Commit:      commitOf(root),
		Effects:     map[string]map[string]Observation{},
		Definitions: len(paths),
	}

	// spellings[valueKey][id][spelling] and vendors[valueKey][id][vendor], so one
	// pass over the collection answers every ID at once.
	spellings := map[string]map[int]map[string]int{}
	vendors := map[string]map[int]map[string]int{}

	for _, path := range paths {
		doc := readDocument(path)
		if len(doc.Effects) == 0 {
			continue
		}
		report.EffectBoards++
		for key, effects := range doc.Effects {
			if spellings[key] == nil {
				spellings[key] = map[int]map[string]int{}
				vendors[key] = map[int]map[string]int{}
			}
			for id, name := range effects {
				if spellings[key][id] == nil {
					spellings[key][id] = map[string]int{}
					vendors[key][id] = map[string]int{}
				}
				spellings[key][id][normalise(name)]++
				vendors[key][id][doc.Vendor]++
			}
		}
	}

	for key, byID := range spellings {
		ids := make([]int, 0, len(byID))
		for id := range byID {
			ids = append(ids, id)
		}
		sort.Ints(ids)
		report.Effects[key] = map[string]Observation{}
		for _, id := range ids {
			report.Effects[key][fmt.Sprint(id)] = observe(byID[id], vendors[key][id])
		}
	}
	return report, nil
}

// observe turns the counts for one ID into what the report carries for it.
func observe(byName map[string]int, byVendor map[string]int) Observation {
	obs := Observation{Boards: 0}
	for _, n := range byName {
		obs.Boards += n
	}
	type pair struct {
		name  string
		count int
	}
	pairs := make([]pair, 0, len(byName))
	for name, count := range byName {
		pairs = append(pairs, pair{name, count})
	}
	// Ties are broken by name so the output is the same for the same input.
	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i].count != pairs[j].count {
			return pairs[i].count > pairs[j].count
		}
		return pairs[i].name < pairs[j].name
	})
	for i, p := range pairs {
		if i >= maxCandidates {
			break
		}
		obs.Candidates = append(obs.Candidates, Candidate{Name: p.name, Count: p.count})
	}
	for vendor, count := range byVendor {
		if count > obs.TopVendorCount {
			obs.TopVendor, obs.TopVendorCount = vendor, count
		}
	}
	return obs
}

// readDocument reads one definition file and returns the effect dropdowns it
// carries. A file that does not parse, or that carries none, is not an error:
// the collection holds files for boards that do not light up, and a measurement
// that stopped at the first of them would describe nothing.
func readDocument(path string) Document {
	doc := Document{Effects: map[string]map[int]string{}}
	// The vendor is the directory above the board's, which is how the collection
	// is laid out: v3/<vendor>/<board>/.../<board>.json. For a two-segment path it
	// is the second segment.
	parts := strings.Split(filepath.ToSlash(path), "/")
	for i, p := range parts {
		if p == "v3" && i+1 < len(parts) {
			doc.Vendor = parts[i+1]
			break
		}
	}
	raw, err := os.ReadFile(path)
	if err != nil {
		return doc
	}
	var file any
	if err := json.Unmarshal(raw, &file); err != nil {
		return doc
	}
	walk(file, "", doc.Effects)
	return doc
}

// walk finds every dropdown whose value key names an effect. The key is read
// from the dropdown's own content rather than from a label, because the label is
// a display string and the key is the address.
func walk(node any, key string, out map[string]map[int]string) {
	switch n := node.(type) {
	case []any:
		for _, child := range n {
			walk(child, key, out)
		}
	case map[string]any:
		content, _ := n["content"].([]any)
		if n["type"] == "dropdown" && len(content) > 0 {
			if valueKey, ok := content[0].(string); ok && strings.HasSuffix(valueKey, effectValueKeySuffix) {
				if options, ok := n["options"].([]any); ok {
					if parsed, ok := parseOptions(options); ok {
						if out[valueKey] == nil {
							out[valueKey] = map[int]string{}
						}
						for id, name := range parsed {
							out[valueKey][id] = name
						}
					}
				}
			}
		}
		for _, child := range n {
			walk(child, key, out)
		}
	}
}

// parseOptions reads a dropdown's options as number-name pairs. An option's
// number is not its position, which is why this reads the number rather than
// counting: a board may name its first effect 1 and have no 0 at all.
func parseOptions(options []any) (map[int]string, bool) {
	out := map[int]string{}
	for _, option := range options {
		pair, ok := option.([]any)
		if !ok || len(pair) != 2 {
			return nil, false
		}
		name, ok := pair[0].(string)
		if !ok {
			return nil, false
		}
		var number int
		switch v := pair[1].(type) {
		case float64:
			number = int(v)
		case string:
			if _, err := fmt.Sscanf(v, "%d", &number); err != nil {
				return nil, false
			}
		default:
			return nil, false
		}
		out[number] = name
	}
	return out, len(out) > 0
}

// normalise reduces a display spelling to something a lookup can compare: case
// and separators are the whole difference between a manufacturer's spelling and
// the tool's, and `fixed wave` and `fixed_wave` are one effect.
//
// A leading number is decoration and is dropped. One manufacturer's definitions
// write `07. RAINBOW_MOVING_CHEVRON` on every effect, and without this the most
// frequent spelling of every ID would carry that vendor's numbering rather than
// the name, which is the opposite of what a candidate is for. Two spellings that
// differ only in such a prefix are the same name and merge.
func normalise(name string) string {
	var b strings.Builder
	for _, r := range strings.ToLower(strings.TrimSpace(name)) {
		switch {
		case r >= 'a' && r <= 'z', r >= '0' && r <= '9':
			b.WriteRune(r)
		default:
			b.WriteRune('_')
		}
	}
	return strings.TrimLeft(stripLeadingNumber(b.String()), "_")
}

// stripLeadingNumber removes a leading run of digits and the underscore after it,
// so `07__rainbow_moving_chevron` becomes `rainbow_moving_chevron` and
// `00__none` becomes `none`. A name that is only a number is left alone: that is
// not decoration, and there is nothing else in it.
func stripLeadingNumber(s string) string {
	i := 0
	for i < len(s) && s[i] >= '0' && s[i] <= '9' {
		i++
	}
	if i == 0 || i == len(s) {
		return s
	}
	for i < len(s) && s[i] == '_' {
		i++
	}
	if i == len(s) {
		return s
	}
	return s[i:]
}

// commitOf reads the commit a checkout is at, so the report says which one it
// measured. A checkout without git, or a detached one, is not a reason to fail:
// the report is still written, without the SHA, and says so in the field.
func commitOf(root string) string {
	out, err := exec.Command("git", "-C", root, "rev-parse", "HEAD").Output()
	if err != nil {
		return ""
	}
	return strings.TrimSpace(string(out))
}