maporder

Documentation

Overview

Package maporder analyses this repository's serialization packages for map iteration whose order reaches the output.

Go randomises map iteration order, so a loop that ranges a map and emits as it goes produces different bytes on every run. That breaks the byte-identity promise this library is built on, and it has happened twice for real:

• C497: docx.Charts() walked d.headers/d.footers in map order, so the returned slice was ordered differently on each call even though the godoc promised document order. FormFields and Revisions already used sortedKeys for exactly this reason.
• C515: pptx embedMediaData/embedAudioPart/embedFontData deduplicated by scanning p.otherParts in map order and returning the first byte-equal part, so with two identical media parts stored under different names the relationship target varied between runs.

Both were found by accident. The established fix in this codebase is collect-then-sort:

names := make([]string, 0, len(m))
for name := range m {
    names = append(names, name)
}
sort.Strings(names)
for _, name := range names { ... }   // deterministic

A syntactic matcher cannot do this job: `range x` looks the same whether x is a map, a slice or a channel, and a purely syntactic sweep of this repository produced twelve candidates that were all false positives. So the analysis is type-directed, over golang.org/x/tools/go/packages. See Load for why that rather than go/importer.

Classification

Most map ranges are fine, so the analyser classifies rather than reporting everything. A map range is order-safe when the key and the value are only used in ways whose result does not depend on the order they arrive in:

• appended to a slice the enclosing function sorts before it is used,
• written into another map or set, or deleted from one,
• stored at a computed index of a slice or array (position, not sequence),
• folded into a commutative aggregate: a min/max guarded by a comparison, a counter, a boolean flag,
• used only inside the iteration and discarded.

It is order-dependent — and reported — when the key or the value:

• is written to a Builder, Writer, Buffer or Collector that was declared outside the loop (kindEmit), or passed to a function that writes to one,
• is appended to a slice that nothing ever sorts (kindCollect): the C497 shape, where map order becomes the order of a returned slice,
• escapes the loop by being returned or assigned outward (kindEscape): the C515 shape, where "the first entry that matches" is whichever one the runtime happened to visit first.

Locally defined closures are inlined, because the collect-then-sort helpers in this repository are frequently written as one (`add`, `mark`, `scan`), and a summary that stopped at the call would classify them all as opaque. Calls to declared functions are resolved through the call graph instead, across package boundaries as well as within one — a write hidden a package away in a helper that does not own its Builder is the same defect as one written inline.

Index

• Constants
• Variables
• func ShortPath(importPath string) string
• type Analysis
  • func Analyze(dir string, patterns []string) (*Analysis, error)
• type Finding
• type Package
• type Program
  • func Load(dir string, patterns []string) (*Program, error)
• type Stats

Constants

const (
	KindEmit    = "emit"
	KindCollect = "collect"
	KindEscape  = "escape"
)

Finding kinds.

Variables

var Patterns = []string{
	"./chart/...",
	"./common/...",
	"./docx/...",
	"./opc/...",
	"./pptx/...",
	"./xlsx/...",
}

Patterns are the package patterns whose sources are analysed: the six roots that serialize. Every OOXML part this library writes is built in one of them.

Functions

func ShortPath

func ShortPath(importPath string) string

ShortPath trims the module prefix from an import path, giving the form the exemption keys and landmarks are written in.

Types

type Analysis

type Analysis struct {
	Stats
	// Loops identifies every map range that was classified, as
	// "<relpath>:<func>:<ranged expression>". A guard can assert that a known
	// landmark is still in here, which a Findings-only result cannot show:
	// "nothing reported" and "nothing looked at" are the same picture.
	Loops    []string
	Findings []Finding
	// Prog is the parsed and type-checked source the analysis ran on, kept so a
	// caller can ask further questions of it without paying for a second
	// source-mode type check.
	Prog *Program
}

Analysis is the result of one sweep.

func Analyze

func Analyze(dir string, patterns []string) (*Analysis, error)

Analyze loads the packages matching patterns (rooted at dir) and reports every order-dependent map range in them. Positions are reported relative to dir.

type Finding

type Finding struct {
	Key    string // stable identity: "<relpath>:<func>:<range expr>:<kind>"
	Pos    string // file:line:col of the offending statement
	Loop   string // file:line:col of the range statement
	Func   string // enclosing function
	Kind   string
	Detail string
}

Finding is one order-dependent use of a map iteration variable.

type Package

type Package struct {
	ImportPath string
	Files      []*ast.File
	Info       *types.Info
	Pkg        *types.Package
}

Package is one analysed Go package: its syntax, its type information and the file set they share.

type Program

type Program struct {
	Fset     *token.FileSet
	Packages []*Package
}

Program is every analysed package plus the shared file set.

func Load

func Load(dir string, patterns []string) (*Program, error)

Load type-checks the packages matching patterns, rooted at dir.

It uses golang.org/x/tools/go/packages rather than go/importer: the module resolution, build tags and per-package configuration are handled properly, the dependency graph is loaded once from the build cache instead of being re-type-checked from source, and — the reason that matters for the call graph below — every package in one Load shares object identity, so a call from docx into opc resolves to the very *types.Func this analyser indexed from opc's own syntax. The source importer gives none of that, and took four times as long.

Loading is strict about errors. The classification cannot tell a map from a slice without types, so a package that failed to type-check would silently report clean — the exact failure a guard must not have.

type Stats

type Stats struct {
	Packages  int
	Files     int
	Funcs     int
	Exprs     int
	Ranges    int
	MapRanges int
}

Stats records how much the analyser actually looked at, so a run that degrades to seeing nothing cannot pass for a clean sweep.