subcircuit_recognizer.py — Layer 1

Part 1 · What problem is "recognition" even solving?

The one job: "Given a flat bag of transistors, find every sub-group that looks like a known building block — a differential pair, a current mirror, a bias reference."

A flattened opamp netlist is just a pile of 20–40 transistors. No labels. No hierarchy.

But an analog designer looking at it instantly sees: "those two share a tail — differential pair. Those two share a gate and one's diode-connected — current mirror."

Recognition teaches the computer to see the same shapes.

The everyday analogy: cookie cutters on rolled dough

Picture the netlist as a big sheet of dough (all the devices). The pattern library is a drawer of cookie cutters (templates). Recognition presses every cutter everywhere it fits and keeps a record of each stamp — even where two cutters overlap.

Part 2 · The cast of characters

Before diving in, here's who calls whom. Hover a box to trace its link.

Part 3 · Loading the rulebook

The one job: "Read the pattern templates from three YAML files, in dependency order."

load_patterns() stitches three files into one list, and the order is deliberate:

_load_file() is a straight YAML-to-dataclass map: each dict entry becomes a PatternDef, with nested devices and children lists rebuilt as PatternDevice and ChildDef. Nothing clever — just faithful hydration.

Part 4 · same_net — the one constraint that defines a pattern

The one job: "Does this tentative assignment respect the wiring the pattern demands?"

A differential pair isn't just "two nmos transistors." It's two nmos transistors whose sources share a net (the tail). That "share a net" requirement is a same_net group:

same_net = [["m1.s", "m2.s"]]  # m1's source == m2's source

_check_same_net() verifies it. The subtle, clever part is that it accepts partial assignments:

for group in pattern.same_net:
    nets = set()
    for ref_term in group:
        ref, term = ref_term.split(".")
        dev = assignment.get(ref)
        if dev is None:
            break            # ref not bound yet → skip this group
        nets.add(dev.terminals[term])
    else:
        if len(nets) != 1:   # all bound, but ≠1 distinct net → fail
            return False
return True

The for…else is the trick.

The else runs only if the loop didn't break — i.e. only when every ref in the group is already bound. A group that's half-assigned is neither passed nor failed; it's simply skipped. That lets the search call this check after every single binding and prune bad branches the instant they become provably bad.

Part 5 · Backtracking search, traced by hand

The one job: "Find every way to assign the pattern's template devices to real devices such that all constraints hold."

This is the single most important function in the file. It's a depth-first search that binds template devices one at a time, checking constraints as it goes and undoing bindings that lead nowhere.

The concrete example

Pattern differential_pair_nmos: two template devices m1, m2 (both type nmos), constraint m1.s == m2.s. The netlist has three nmos devices:

We want the search to find exactly {mA, mB} — the only pair sharing a source net.

The code, with the three moving parts marked:

def backtrack(i, assignment, used):
    if i == len(pattern.devices):
        yield dict(assignment)          # complete → emit a copy
        return
    template_dev = pattern.devices[i]
    for dev in devices:
        if dev.ref in used or dev.type != template_dev.type:
            continue                     # wrong type or already used
        assignment[template_dev.ref] = dev
        used.add(dev.ref)
        if _check_same_net(pattern, assignment):   # prune early
            yield from backtrack(i + 1, assignment, used)
        used.discard(dev.ref)             # UNDO — this is backtracking
        del assignment[template_dev.ref]

Why the frozenset de-dup?

Swapping m1↔m2 gives the same physical pair. Keying seen by the frozenset of device refs means {mA,mB} and {mB,mA} collapse to one match — no duplicate structures for symmetric templates.

The docstring is honest about scale: "Patterns are 1–4 devices, so plain backtracking (no graph library) is sufficient." A hand-rolled DFS is exactly right here — reaching for a subgraph-isomorphism library would be over-engineering.

Part 6 · Levels — a topological sort so children come first

The one job: "A composite pattern needs its children to already be recognized. What order do we process patterns in?"

Some patterns are composites: they declare children that must already exist as matches before the parent can be accepted. So we must recognize the children first. _compute_levels() assigns each pattern a level by recursion + memoization:

_match_children() then does the verification: for each declared child, it looks for a previously-recognized structure whose device set equals the child's device set (resolved through the current assignment) and whose name matches. If any child is missing, the whole parent match is rejected (return None).

Part 7 · recognize() — the three passes

Now everything assembles. recognize() runs three distinct passes over the netlist:

Pass 0 — exclusive, priority-sorted

Exclusive patterns are sorted by descending priority, then each device is offered to them in turn. The first match wins and the device is recorded in device_map, so no later exclusive pattern can claim it. This is how diode_connected_nmos (priority 10) beats bare nmos (priority 0) for the same transistor.

Passes 1+ — composites with hooks

For each level, for each pattern, for each assignment: resolve pins, optionally run the pattern's hook (which may reject or append extra devices/pins), verify children, then emit a structure. prev_level_structures is threaded forward so level N can see level N−1's results.

The last pass and unrecognized_devices

The non-exclusive level-0 pass runs the MVP composite patterns unchanged. Finally:

claimed_refs = {d.ref for s in all_structures for d in s.devices}
unrecognized = [d for d in netlist.devices if d.ref not in claimed_refs]

Any device no pattern touched lands in unrecognized_devices. For a netlist round-tripped from a known synthesized circuit this should be empty — a non-empty list is a signal that the pattern library has a gap.

Part 8 · The hidden problem it's really solving

Although the file never writes it down, _find_assignments() is solving a constrained subgraph matching problem:

Find an injective map φ from template devices to netlist devices such that every device's type is preserved and every same_net equality holds.

That's the classic sub-graph isomorphism problem — NP-hard in general — but tamed here by three facts the code exploits:

• patterns are tiny (1–4 devices), so the search tree is shallow;
• _check_same_net prunes branches the instant a constraint is violable;
• type-matching filters most candidates before any constraint check.

And the architectural masterstroke: SR refuses to disambiguate. It emits every overlapping candidate and defers all judgement to Layer 2. That keeps this file a pure, total, easily-tested function of (netlist, patterns) — no context, no guessing.

In one sentence: subcircuit_recognizer.py presses a library of tiny cookie-cutter templates onto the netlist with a pruned backtracking search, in level order so composites see their children, and reports every stamp — overlaps and all — for Layer 2 to sort out.

Looking ahead → Part 4 · hooks.py unpacks the escape hatch we glossed over: hooks that let a pattern discover a variable number of extra devices (like a bias generator's "legs") at match time.