Files
likang 7e01147566
CI / typecheck + test + build (push) Has been cancelled
Initial commit: import VibeMake PCB Studio
2026-11-03 11:20:08 +08:00

633 lines
21 KiB
TypeScript

// SPDX-License-Identifier: GPL-3.0-or-later
// Copyright (C) 2026 ZiroEDA and contributors.
// Portions derived from KiCad, copyright The KiCad Developers. See NOTICE.md.
/**
* Junction-point analysis. Counterpart: `eeschema/junction_helpers.cpp`
* (JUNCTION_HELPERS::AnalyzePoint) and the SCH_SCREEN::IsExplicitJunction*
* predicates (`eeschema/sch_screen.cpp`).
*
* A point is a junction when three or more distinct exit directions leave it
* on the same layer (wires or buses). Everything connectable contributes:
* wire/bus ends and pass-throughs, symbol pins, sheet pins, bus entries, and
* labels. Pins and entries get unique direction tokens (a pin at 90° must not
* merge with a wire at 90°, upstream's `uniqueAngle`). Upstream first merges
* collinear overlapping lines; collecting *directions* in a set dedups the
* same cases (two collinear exits share one direction key), so the merge pass
* is not replicated.
*/
import type {
LibSymbol,
SchLabel,
SchLine,
SchSheet,
SchSymbol,
Schematic,
Vec2,
} from './types.js';
import { symbolPinPositions } from './tools/connect.js';
import { schSymbolLibraryName } from './lib_symbol.js';
export interface PointInfo {
/** 3+ same-layer exit directions meet here (wires or buses). */
isJunction: boolean;
/** A bus entry touches the point. */
hasBusEntry: boolean;
/** The bus-entry root also fans out to several wires (junction stays). */
hasBusEntryToMultipleWires: boolean;
/** An explicit junction dot item sits on the point. */
hasExplicitJunctionDot: boolean;
/** A bus passes through or ends at the point. */
hasBusAtPoint: boolean;
}
const eq = (a: Vec2, b: Vec2): boolean => a.x === b.x && a.y === b.y;
/** p strictly inside segment [a,b] (collinear, not an endpoint). */
function onSegInterior(p: Vec2, a: Vec2, b: Vec2): boolean {
const cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
if (cross !== 0) return false;
const dot = (p.x - a.x) * (b.x - a.x) + (p.y - a.y) * (b.y - a.y);
const len2 = (b.x - a.x) ** 2 + (b.y - a.y) ** 2;
return dot > 0 && dot < len2;
}
const gcd = (a: number, b: number): number => {
let x = Math.abs(a);
let y = Math.abs(b);
while (y) [x, y] = [y, x % y];
return x || 1;
};
/** Exact direction key from `p` toward `q` (upstream rounds to degrees). */
function dirKey(p: Vec2, q: Vec2): string {
const dx = q.x - p.x;
const dy = q.y - p.y;
const g = gcd(dx, dy);
return `${dx / g},${dy / g}`;
}
/** SCH_CONNECTION::IsBusLabel: a vector bus (`NAME[3..0]`) or a bus group
* (`NAME{A B}` / `{A B}`). */
export function isBusLabelText(text: string): boolean {
return /^[^\s]+\[\d+\.\.\d+\]$/.test(text) || /^[^\s{}]*\{[^{}]+\}$/.test(text);
}
/**
* Every connection point a *position-only* lookup needs, built once per
* document and reused.
*
* `analyzePoint` is called from the post-edit cleanup loop about a thousand
* times per pass — once per junction, twice per wire — and each call used to
* rescan the whole sheet. The symbol-pin walk was the expensive part:
* `symbolPinPositions` builds a transform and allocates one point per pin, so
* on the coldfire demo (118 symbols, up to 100 pins each) a single call
* allocated several thousand points. Dropping a dragged part spent **4.5
* seconds** in that loop, which is the freeze after a drop.
*
* The caches are keyed on the *arrays*, not on the `Schematic`. That is
* deliberate: the cleanup loop analyses a document it rebuilds on every call
* (`{ ...sch, lines, junctions }`), so a cache keyed on the document object
* could never hit — but `symbols`, `sheets` and `labels` keep their identity
* through that spread, and those are exactly the three walks worth caching.
* Lines and junctions genuinely change each pass and are still scanned.
*/
interface PointCounts {
symbolPins: Map<string, number>;
sheetPins: Map<string, number>;
labels: Map<string, SchLabel[]>;
}
const symbolPinCache = new WeakMap<
readonly SchSymbol[],
{ lib: ReadonlyMap<string, LibSymbol> | undefined; at: Map<string, number> }
>();
const sheetPinCache = new WeakMap<readonly SchSheet[], Map<string, number>>();
const labelCache = new WeakMap<readonly SchLabel[], Map<string, SchLabel[]>>();
function pinCountsAt(
sch: Schematic,
libById: ReadonlyMap<string, LibSymbol> | undefined,
): PointCounts {
let sym = symbolPinCache.get(sch.symbols);
// The library map is derived from the document's own `lib_symbols`, so a
// different one means different geometry and the entry has to be rebuilt.
if (!sym || sym.lib !== libById) {
const at = new Map<string, number>();
if (libById) {
for (const s of sch.symbols) {
for (const pin of symbolPinPositions(s, libById.get(schSymbolLibraryName(s)))) {
const k = `${pin.x},${pin.y}`;
at.set(k, (at.get(k) ?? 0) + 1);
}
}
}
sym = { lib: libById, at };
symbolPinCache.set(sch.symbols, sym);
}
let sheetPins = sheetPinCache.get(sch.sheets);
if (!sheetPins) {
sheetPins = new Map<string, number>();
for (const sheet of sch.sheets) {
for (const pin of sheet.pins) {
const k = `${pin.at.x},${pin.at.y}`;
sheetPins.set(k, (sheetPins.get(k) ?? 0) + 1);
}
}
sheetPinCache.set(sch.sheets, sheetPins);
}
let labels = labelCache.get(sch.labels);
if (!labels) {
labels = new Map<string, SchLabel[]>();
for (const l of sch.labels) {
const k = `${l.at.x},${l.at.y}`;
const list = labels.get(k);
if (list) list.push(l);
else labels.set(k, [l]);
}
labelCache.set(sch.labels, labels);
}
return { symbolPins: sym.at, sheetPins, labels };
}
/**
* JUNCTION_HELPERS::AnalyzePoint. `libById` resolves symbol pin positions;
* when omitted, pins are not considered (legacy callers/tests).
*/
export function analyzePoint(
sch: Schematic,
libById: ReadonlyMap<string, LibSymbol> | undefined,
p: Vec2,
breakCrossings = false,
): PointInfo {
const info: PointInfo = {
isJunction: false,
hasBusEntry: false,
hasBusEntryToMultipleWires: false,
hasExplicitJunctionDot: false,
hasBusAtPoint: false,
};
const exits = { wire: new Set<string>(), bus: new Set<string>() };
const breakLines = { wire: false, bus: false };
const midPointLines = { wire: [] as SchLine[], bus: [] as SchLine[] };
let uniqueToken = 0;
const unique = (layer: 'wire' | 'bus'): void => {
breakLines[layer] = true;
exits[layer].add(`u${uniqueToken++}`);
};
for (const j of sch.junctions) {
if (eq(j.at, p)) info.hasExplicitJunctionDot = true;
}
for (const l of sch.lines) {
if (l.kind !== 'wire' && l.kind !== 'bus') continue;
if (eq(l.start, l.end)) continue;
const layer = l.kind;
if (eq(l.start, p) || eq(l.end, p)) {
breakLines[layer] = true;
exits[layer].add(dirKey(p, eq(l.start, p) ? l.end : l.start));
if (layer === 'bus') info.hasBusAtPoint = true;
} else if (onSegInterior(p, l.start, l.end)) {
if (breakCrossings) breakLines[layer] = true;
midPointLines[layer].push(l);
if (layer === 'bus') info.hasBusAtPoint = true;
}
}
// Bus entries connect at both ends and break wires and buses alike.
for (const be of sch.busEntries) {
const end = { x: be.at.x + be.size.x, y: be.at.y + be.size.y };
if (eq(be.at, p) || eq(end, p)) {
info.hasBusEntry = true;
unique('bus');
unique('wire');
} else if (onSegInterior(p, be.at, end)) {
// Overlapping-but-not-connected entry (upstream's first-pass flag).
info.hasBusEntry = true;
}
}
// Symbol pins, sheet pins and labels are looked up by position rather than
// rescanned. See `pinCountsAt` for why this matters so much: on a 118-symbol
// sheet the pin walk alone allocated a few thousand points *per call*, and
// the cleanup loop makes about a thousand calls per pass.
const pins = pinCountsAt(sch, libById);
const key = `${p.x},${p.y}`;
for (let n = pins.symbolPins.get(key) ?? 0; n > 0; n--) unique('wire');
for (let n = pins.sheetPins.get(key) ?? 0; n > 0; n--) unique('wire');
for (const label of pins.labels.get(key) ?? []) {
if (label.kind === 'label') breakLines[isBusLabelText(label.text) ? 'bus' : 'wire'] = true;
else if (label.kind === 'global_label' || label.kind === 'hierarchical_label')
breakLines.wire = true;
}
// Pass-through lines only fan out (count both directions) once something
// else breaks the layer at this point.
for (const layer of ['wire', 'bus'] as const) {
if (!breakLines[layer]) continue;
for (const l of midPointLines[layer]) {
exits[layer].add(dirKey(p, l.start));
exits[layer].add(dirKey(p, l.end));
}
}
if (info.hasBusEntry) {
// One wire + the entry is two wire exits and exactly one bus exit; more
// wire exits mean the entry root feeds several wires.
info.hasBusEntryToMultipleWires = exits.wire.size > 2 && exits.bus.size === 1;
}
info.isJunction = exits.wire.size >= 3 || exits.bus.size >= 3;
return info;
}
/** SCH_SCREEN::IsExplicitJunction: a junction dot belongs at `p` (existing
* dots are legitimate here). */
export function isExplicitJunction(
sch: Schematic,
libById: ReadonlyMap<string, LibSymbol> | undefined,
p: Vec2,
): boolean {
const info = analyzePoint(sch, libById, p);
return info.isJunction && (!info.hasBusEntry || info.hasBusEntryToMultipleWires);
}
/**
* SCH_SCREEN::IsExplicitJunctionAllowed: whether the user may place a dot at
* `p`. Unlike the two predicates above this analyzes with crossings broken, so
* a wire crossing another counts as four exits and a dot is offered there,
* upstream's junction tool refuses the click when this is false ("Junction
* location contains no joinable wires and/or pins.").
*/
export function isExplicitJunctionAllowed(
sch: Schematic,
libById: ReadonlyMap<string, LibSymbol> | undefined,
p: Vec2,
): boolean {
const info = analyzePoint(sch, libById, p, true);
return info.isJunction && (!info.hasBusEntry || info.hasBusEntryToMultipleWires);
}
/** SCH_SCREEN::IsExplicitJunctionNeeded: a dot belongs at `p` and none is
* there yet. */
export function isExplicitJunctionNeeded(
sch: Schematic,
libById: ReadonlyMap<string, LibSymbol> | undefined,
p: Vec2,
): boolean {
const info = analyzePoint(sch, libById, p);
return (
info.isJunction &&
(!info.hasBusEntry || info.hasBusEntryToMultipleWires) &&
!info.hasExplicitJunctionDot
);
}
// ---------------------------------------------------------------------------
// `JUNCTION_HELPERS::AnalyzePoint` and `PreviewJunctions` on the live item classes
// (eeschema stage E3). Everything above is the record model's; this half merges the
// overlapping lines first, as upstream does.
// ---------------------------------------------------------------------------
import {
SKIP_STRUCT as SKIP_STRUCT_E3,
STRUCT_DELETED as STRUCT_DELETED_E3,
} from '@ziroeda/common/eda_item_flags.js';
import { SCH_LAYER_ID as SCH_LAYER_ID_E3 } from '@ziroeda/common/layer_id.js';
import { KICAD_T as KICAD_T_E3 } from '@ziroeda/core/typeinfo.js';
import type { VECTOR2I as VECTOR2I_E3 } from '@ziroeda/kimath/src/math/vector2.js';
import { IsPointOnSegment as IsPointOnSegmentE3 } from '@ziroeda/kimath/src/trigo.js';
import { IsBusLabel as IsBusLabelE3 } from './sch_bus_entry.js';
import type { SCH_ITEM as SCH_ITEM_E3 } from './sch_item.js';
import { SCH_JUNCTION as SCH_JUNCTION_E3 } from './sch_junction.js';
import type { SCH_LABEL_BASE as SCH_LABEL_BASE_E3 } from './sch_label.js';
import { SCH_LINE as SCH_LINE_E3 } from './sch_line.js';
import { EE_RTREE as EE_RTREE_E3 } from './sch_rtree.js';
import type { SCH_SCREEN as SCH_SCREEN_E3 } from './sch_screen.js';
/** `JUNCTION_HELPERS::POINT_INFO`: a description of what is at a point. */
export interface POINT_INFO {
/// True if the point has 3+ wires and/or 3+ buses meeting there
isJunction: boolean;
/// True if there is already junction dot at the point
hasExplicitJunctionDot: boolean;
/// True if there is a bus entry at the point (either end)
hasBusEntry: boolean;
/// True if there is a bus entry at the point and it connects to more than one wire
hasBusEntryToMultipleWires: boolean;
/// True if there is a bus entry at the point and three or more bus segments fork there
hasBusEntryToMultipleBuses: boolean;
/// True if there is a bus at the point
hasBusAtPoint: boolean;
/// True when an explicit junction dot is permitted here, meaning a junction that is free of a
/// bus entry or where the entry coincides with a genuine wire or bus fork.
AllowsExplicitJunction(): boolean;
}
/**
* Check a tree of items for a confluence at a given point and work out what kind of
* junction it is, if any.
*/
export function AnalyzePoint(
aItems: EE_RTREE_E3,
aPosition: VECTOR2I_E3,
aBreakCrossings: boolean,
): POINT_INFO {
const WIRES = 0;
const BUSES = 1;
const info: POINT_INFO = {
isJunction: false,
hasExplicitJunctionDot: false,
hasBusEntry: false,
hasBusEntryToMultipleWires: false,
hasBusEntryToMultipleBuses: false,
hasBusAtPoint: false,
AllowsExplicitJunction() {
return (
this.isJunction &&
(!this.hasBusEntry || this.hasBusEntryToMultipleWires || this.hasBusEntryToMultipleBuses)
);
},
};
const breakLines = [false, false];
const exitAngles = [new Set<number>(), new Set<number>()];
const midPointLines: SCH_LINE_E3[][] = [[], []];
// Synthetic bus angles injected by entries, subtracted later to find genuine bus directions
let busEntryBusAngles = 0;
// Bus segments terminating here; a real fork ends at least one bus, a crossing ends none
let busEndpointSegments = 0;
// A pair of lines is considered connected if they share an endpoint. This is the list
// of the other items that can connect.
const filtered = new EE_RTREE_E3();
let mergedLines: SCH_LINE_E3[] = [];
for (const item of aItems.Overlapping(aPosition)) {
if (item.GetEditFlags() & (SKIP_STRUCT_E3 | STRUCT_DELETED_E3)) continue;
switch (item.Type()) {
case KICAD_T_E3.SCH_LINE_T: {
const line = item as SCH_LINE_E3;
if (line.IsConnectable()) mergedLines.push(SCH_LINE_E3.copyOf(line));
break;
}
case KICAD_T_E3.SCH_JUNCTION_T:
if (item.HitTest(aPosition, -1)) info.hasExplicitJunctionDot = true;
filtered.insert(item);
break;
case KICAD_T_E3.SCH_BUS_WIRE_ENTRY_T:
info.hasBusEntry = true;
filtered.insert(item);
break;
case KICAD_T_E3.SCH_SHEET_T:
case KICAD_T_E3.SCH_SYMBOL_T:
case KICAD_T_E3.SCH_LABEL_T:
case KICAD_T_E3.SCH_HIER_LABEL_T:
case KICAD_T_E3.SCH_GLOBAL_LABEL_T:
filtered.insert(item);
break;
default:
break;
}
}
if (mergedLines.length + filtered.size() < 2) return info;
// Skip collinear merging when enough distinct endpoints already meet here.
// Merging would turn an N-way stub junction (e.g. LTspice four-wire cross:
// two opposite stubs on each axis) into an unmarked mid-segment crossing
// and hide the needed junction.
const preMergeWireExits = new Set<number>();
const preMergeBusExits = new Set<number>();
for (const line of mergedLines) {
const s = line.GetStartPoint();
const e = line.GetEndPoint();
if (s.x === e.x && s.y === e.y) continue;
if (!line.IsConnected(aPosition)) continue;
if (line.GetLayer() === SCH_LAYER_ID_E3.LAYER_WIRE)
preMergeWireExits.add(line.GetAngleFrom(aPosition));
else if (line.GetLayer() === SCH_LAYER_ID_E3.LAYER_BUS)
preMergeBusExits.add(line.GetAngleFrom(aPosition));
}
const keepStubJunction = preMergeWireExits.size >= 3 || preMergeBusExits.size >= 3;
// Merge collinear wire segments
let merged = false;
do {
if (info.hasExplicitJunctionDot || aBreakCrossings || keepStubJunction) break;
merged = false;
for (let i = 0; i < mergedLines.length && !merged; ++i) {
for (let j = i + 1; j < mergedLines.length; ++j) {
const line = mergedLines[i]!.MergeOverlap(null, mergedLines[j]!, false);
if (line) {
mergedLines[i] = line;
mergedLines = mergedLines.filter((_, k) => k !== j);
merged = true;
break;
}
}
}
} while (merged);
for (const line of mergedLines) filtered.insert(line);
// A pin or a bus entry each get their own unique exit direction.
let uniqueAngle = 10000;
for (const item of filtered) {
if (item.GetEditFlags() & STRUCT_DELETED_E3) continue;
switch (item.Type()) {
case KICAD_T_E3.SCH_JUNCTION_T:
if (item.HitTest(aPosition, -1)) info.hasExplicitJunctionDot = true;
break;
case KICAD_T_E3.SCH_LINE_T: {
const line = item as SCH_LINE_E3;
let layer: number;
const s = line.GetStartPoint();
const e = line.GetEndPoint();
if (s.x === e.x && s.y === e.y) break;
else if (line.GetLayer() === SCH_LAYER_ID_E3.LAYER_WIRE) layer = WIRES;
else if (line.GetLayer() === SCH_LAYER_ID_E3.LAYER_BUS) layer = BUSES;
else break;
if (line.IsConnected(aPosition)) {
breakLines[layer] = true;
exitAngles[layer]!.add(line.GetAngleFrom(aPosition));
if (layer === BUSES) busEndpointSegments++;
} else if (line.HitTest(aPosition, -1)) {
if (aBreakCrossings) breakLines[layer] = true;
// Defer any line midpoints until we know whether or not we're breaking them
midPointLines[layer]!.push(line);
}
if (layer === BUSES && line.HitTest(aPosition, -1)) info.hasBusAtPoint = true;
break;
}
case KICAD_T_E3.SCH_BUS_WIRE_ENTRY_T:
if (item.IsConnected(aPosition)) {
breakLines[BUSES] = true;
exitAngles[BUSES]!.add(uniqueAngle++);
busEntryBusAngles++;
breakLines[WIRES] = true;
exitAngles[WIRES]!.add(uniqueAngle++);
info.hasBusEntry = true;
}
break;
case KICAD_T_E3.SCH_SYMBOL_T:
case KICAD_T_E3.SCH_SHEET_T:
if (item.IsConnected(aPosition)) {
breakLines[WIRES] = true;
exitAngles[WIRES]!.add(uniqueAngle++);
}
break;
case KICAD_T_E3.SCH_LABEL_T:
if (item.IsConnected(aPosition)) {
if (IsBusLabelE3((item as SCH_LABEL_BASE_E3).GetText())) breakLines[BUSES] = true;
else breakLines[WIRES] = true;
}
break;
case KICAD_T_E3.SCH_HIER_LABEL_T:
case KICAD_T_E3.SCH_GLOBAL_LABEL_T:
if (item.IsConnected(aPosition)) breakLines[WIRES] = true;
break;
default:
break;
}
}
for (const layer of [WIRES, BUSES]) {
if (breakLines[layer]) {
for (const line of midPointLines[layer]!) {
exitAngles[layer]!.add(line.GetAngleFrom(aPosition));
exitAngles[layer]!.add(line.GetReverseAngleFrom(aPosition));
}
}
}
if (info.hasBusEntry) {
// The bus entry and one wire is 2 wires, and the one entry is exactly one bus
// Any more wires must be multiple wires, but any more buses means a wire
// crossing at the bus entry root.
info.hasBusEntryToMultipleWires = exitAngles[WIRES]!.size > 2 && exitAngles[BUSES]!.size === 1;
// Drop the entry's own synthetic angle; three real directions with a terminating bus is
// a fork, while crossings with no terminating bus must not be auto-joined
const realBusAngles = exitAngles[BUSES]!.size - busEntryBusAngles;
info.hasBusEntryToMultipleBuses = realBusAngles >= 3 && busEndpointSegments >= 1;
}
// Any three things of the same type is a junction of some sort
info.isJunction = exitAngles[WIRES]!.size >= 3 || exitAngles[BUSES]!.size >= 3;
return info;
}
/**
* Determine the points where explicit junctions would be required if the given
* temporary items were committed to the schematic.
*/
export function PreviewJunctions(
aScreen: SCH_SCREEN_E3,
aItems: readonly SCH_ITEM_E3[],
): SCH_JUNCTION_E3[] {
const combined = new EE_RTREE_E3();
// Existing items, except the ones being previewed (they are added below)
const previewSet = new Set<SCH_ITEM_E3>(aItems);
for (const item of aScreen.Items()) {
if (!item.IsConnectable()) continue;
if (previewSet.has(item)) continue;
combined.insert(item);
}
for (const item of aItems) {
if (!item || !item.IsConnectable()) continue;
combined.insert(item);
}
const connections = aScreen.GetConnections();
let pts: VECTOR2I_E3[] = [];
for (const item of aItems) {
if (!item || !item.IsConnectable()) continue;
pts.push(...item.GetConnectionPoints());
// If the item is a line, we also want any midpoints of other items that the line
// passes through.
if (item.Type() === KICAD_T_E3.SCH_LINE_T) {
const line = item as SCH_LINE_E3;
for (const pt of connections) {
if (IsPointOnSegmentE3(line.GetStartPoint(), line.GetEndPoint(), pt)) pts.push(pt);
}
}
}
pts.sort((a, b) =>
a.x < b.x || (a.x === b.x && a.y < b.y) ? -1 : a.x === b.x && a.y === b.y ? 0 : 1,
);
pts = pts.filter((p, i) => i === 0 || p.x !== pts[i - 1]!.x || p.y !== pts[i - 1]!.y);
const jcts: SCH_JUNCTION_E3[] = [];
for (const pt of pts) {
const info = AnalyzePoint(combined, pt, false);
if (info.isJunction && (!info.hasBusEntry || info.hasBusEntryToMultipleWires)) {
const junction = new SCH_JUNCTION_E3(pt);
if (info.hasBusAtPoint) junction.SetLayer(SCH_LAYER_ID_E3.LAYER_BUS_JUNCTION);
jcts.push(junction);
}
}
return jcts;
}