Coverage for klayout_pex/pex25d/validator.py: 96%

1# 

2# -------------------------------------------------------------------------------- 

3# SPDX-FileCopyrightText: 2024-2026 Martin Jan Köhler and Harald Pretl 

4# Johannes Kepler University, Institute for Integrated Circuits. 

5# 

6# This file is part of KPEX  

7# (see https://github.com/iic-jku/klayout-pex). 

8# 

9# This program is free software: you can redistribute it and/or modify 

10# it under the terms of the GNU General Public License as published by 

11# the Free Software Foundation, either version 3 of the License, or 

12# (at your option) any later version. 

13# 

14# This program is distributed in the hope that it will be useful, 

15# but WITHOUT ANY WARRANTY; without even the implied warranty of 

16# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 

17# GNU General Public License for more details. 

18# 

19# You should have received a copy of the GNU General Public License 

20# along with this program. If not, see <http://www.gnu.org/licenses/>. 

21# SPDX-License-Identifier: GPL-3.0-or-later 

22# -------------------------------------------------------------------------------- 

23# 

24 

25""" 

26The reference PEX25D validator. 

27 

28The point of this module is *other people's* writers: another group should be 

29able to check its output and get stable ``PEX25D-Ennnn`` codes back, without 

30depending on kpex internals or on the wording of a message. So it reports 

31everything it finds rather than stopping at the first problem, and it never 

32raises for a merely invalid file — that is what the diagnostics are for. 

33 

34Three tiers, matching ``kpex.pex25d.Diagnostic.Tier``: 

35 

36``TIER_SYNTAX`` 

37 the reader's business, and already reported by the time a message exists. 

38``TIER_SEMANTIC`` 

39 name resolution, acyclic WRAPS, depth ties, and the rules below. Most of it 

40 comes from running the resolver, which has to answer the same questions to 

41 do its job; duplicating that here would let the two drift apart. 

42``TIER_GEOMETRIC`` 

43 ring and box wellformedness, hole containment, conductor overlap. Only 

44 under ``--strict``, because it is the expensive tier. 

45""" 

46 

47from __future__ import annotations 

48 

49from dataclasses import dataclass, field 

50from fractions import Fraction 

51from typing import * 

52 

53from .diagnostics import (Diagnostic, DiagnosticsReport, Severity, Tier, 

54 source_ref) 

55from .protobuf import pex25d_dielectric_pb2, pex25d_file_pb2, pex25d_scene_pb2 

56 

57FLOATING_NET = 'FLOATING' 

58 

59# One overlapping pair per shape pair would drown the report on a layout that 

60# has the problem systematically; the count is still exact. 

61MAX_OVERLAP_REPORTS = 50 

62 

63 

64class Validator: 

65 def __init__(self, report: DiagnosticsReport, strict: bool = False): 

66 self.report = report 

67 self.strict = strict 

68 

69 def diagnose(self, 

70 code: str, 

71 message: str, 

72 tier: Tier = Tier.SEMANTIC, 

73 severity: Severity = Severity.ERROR, 

74 source: Any = None) -> None: 

75 self.report.add(Diagnostic(code=code, severity=severity, tier=tier, 

76 message=message, source=source_ref(source))) 

77 

78 # ----------------------------------------------------------------- entry 

79 

80 def validate(self, message: Any, scene: Any = None) -> None: 

81 if is_scene(message): 

82 self.validate_scene(message) 

83 else: 

84 self.validate_file(message, scene=scene) 

85 

86 def validate_file(self, pex25d_file: Any, scene: Any = None) -> None: 

87 from .resolver import ResolveError, Resolver 

88 

89 # The resolver answers every name-resolution question already, and 

90 # records the same coded diagnostics. Run it for its findings; a file 

91 # too broken to resolve still gets the checks that do not need one. 

92 # A caller that has resolved the file already passes the scene in, so 

93 # that neither the work nor the diagnostics happen twice. 

94 if scene is None: 

95 try: 

96 # Not strict: the geometric tier below is the same code the 

97 # resolver would delegate to, and would report everything twice. 

98 scene = Resolver(pex25d_file, report=self.report).resolve() 

99 except ResolveError: 

100 pass 

101 

102 self.check_units(pex25d_file) 

103 self.check_names(pex25d_file) 

104 self.check_wrap_anchoring(pex25d_file) 

105 self.check_conductors(pex25d_file) 

106 self.check_resistance_records(pex25d_file) 

107 self.check_resistance_coverage(pex25d_file) 

108 

109 if scene is not None: 

110 self.check_depth_ties(scene) 

111 

112 if self.strict: 

113 # Wellformedness on the file, where a shape still carries the 

114 # SourceRef of the record it came from; overlap on the scene, 

115 # which is the only form that knows the z extent of a layer. 

116 self.check_shapes(shapes_of_file(pex25d_file)) 

117 if scene is not None: 

118 self.check_conductor_overlap(scene) 

119 

120 def validate_scene(self, scene: Any) -> None: 

121 self.check_units(scene) 

122 self.check_scene_layers(scene) 

123 self.check_scene_references(scene) 

124 self.check_scene_order(scene) 

125 self.check_depth_ties(scene) 

126 self.check_scene_terminals(scene) 

127 

128 if self.strict: 

129 self.check_shapes(shapes_of_scene(scene)) 

130 self.check_conductor_overlap(scene) 

131 

132 # -------------------------------------------------------------- semantic 

133 

134 def check_units(self, message: Any) -> None: 

135 units = message.units 

136 if not units.grid_denominator: 

137 self.diagnose('PEX25D-E0106', "No UNITS: the file states no grid") 

138 return 

139 

140 if not units.source_dbu_denominator: 

141 return 

142 

143 # GRID must divide source_dbu exactly when both are present: a writer 

144 # for which it does not cannot place its own geometry on the grid. 

145 # Divide-round-compare, never a modulo — the same rule as coordinates. 

146 grid = Fraction(units.grid_numerator, units.grid_denominator) 

147 source_dbu = Fraction(units.source_dbu_numerator, units.source_dbu_denominator) 

148 quotient = source_dbu / grid 

149 if abs(quotient - round(quotient)) > Fraction(1, 10 ** 6): 

150 self.diagnose('PEX25D-E0262', 

151 f"GRID ({grid}) does not divide the source DBU " 

152 f"({source_dbu}) exactly, so the writer's own geometry " 

153 f"cannot be on the grid") 

154 

155 def check_wrap_anchoring(self, pex25d_file: Any) -> None: 

156 """ 

157 A simple dielectric must wrap the OUTERMOST film anchored on its 

158 ``between_below`` object. 

159 

160 Wrapping an inner link would give the fill the same depth as a film it 

161 contains, which is exactly the tie that has no rule to break it. 

162 """ 

163 kinds = pex25d_dielectric_pb2() 

164 

165 anchored: Dict[str, List[str]] = {} 

166 for dielectric in pex25d_file.dielectrics: 

167 if dielectric.kind == kinds.DIELECTRIC_KIND_CONFORMAL: 

168 anchored.setdefault(dielectric.wraps, []).append(dielectric.name) 

169 

170 def outermost(root: str) -> str: 

171 name, seen = root, {root} 

172 while True: 

173 films = anchored.get(name, []) 

174 if len(films) != 1 or films[0] in seen: 

175 return name 

176 name = films[0] 

177 seen.add(name) 

178 

179 for dielectric in pex25d_file.dielectrics: 

180 if dielectric.kind != kinds.DIELECTRIC_KIND_SIMPLE: 

181 continue 

182 below = dielectric.simple.between_below 

183 if not below: 

184 continue 

185 expected = outermost(below) 

186 if dielectric.wraps and dielectric.wraps != expected: 

187 self.diagnose( 

188 'PEX25D-E0260', 

189 f"DIELECTRIC_SIMPLE '{dielectric.name}' WRAPS " 

190 f"'{dielectric.wraps}', but the outermost profile anchored on " 

191 f"'{below}' is '{expected}'; wrapping an inner link ties its " 

192 f"depth with a film it contains", 

193 source=dielectric) 

194 

195 def check_conductors(self, pex25d_file: Any) -> None: 

196 with_geometry = {shape.conductor for shape in pex25d_file.shapes} 

197 

198 for conductor in pex25d_file.conductors: 

199 if conductor.name not in with_geometry: 

200 self.diagnose('PEX25D-W0264', 

201 f"CONDUCTOR '{conductor.name}' has no geometry", 

202 severity=Severity.WARNING, source=conductor) 

203 

204 floating = {c.name for c in pex25d_file.conductors if c.net == FLOATING_NET} 

205 for terminal in pex25d_file.terminals: 

206 if terminal.conductor in floating: 

207 # A floating body is at its own unknown potential and by 

208 # construction has no port. 

209 self.diagnose('PEX25D-E0263', 

210 f"TERMINAL '{terminal.name}' is on FLOATING conductor " 

211 f"'{terminal.conductor}', which has no port", 

212 source=terminal) 

213 

214 def check_resistance_coverage(self, pex25d_file: Any) -> None: 

215 """ 

216 Once a file states any resistance, a profile carrying geometry without 

217 one is worth reporting: an adapter asked for resistance must refuse such 

218 a scene rather than solve it with a perfect conductor in it. An ANCHOR 

219 profile — declared only to give a via its zlow — carries no geometry and 

220 is exempt. 

221 """ 

222 stated = {r.metal for r in pex25d_file.metal_resistances} \ 

223 | {r.via for r in pex25d_file.via_resistances} 

224 if not stated: 

225 return 

226 

227 with_geometry = {shape.layer for shape in pex25d_file.shapes} 

228 for layer in sorted(with_geometry - stated): 

229 self.diagnose('PEX25D-W0265', 

230 f"Profile '{layer}' carries geometry but the file states " 

231 f"no resistance for it, while stating one for others", 

232 severity=Severity.WARNING) 

233 

234 def check_depth_ties(self, scene: Any) -> None: 

235 """ 

236 Two films at the same wrap depth on the same root overlap by 

237 construction, and at equal depth there is no rule to break the tie. 

238 """ 

239 kinds = pex25d_dielectric_pb2() 

240 seen: Dict[Tuple[str, int], str] = {} 

241 for dielectric in scene.dielectrics: 

242 if dielectric.kind != kinds.DIELECTRIC_KIND_CONFORMAL: 

243 continue 

244 key = (dielectric.root, dielectric.wrap_depth) 

245 if key in seen: 

246 self.diagnose( 

247 'PEX25D-E0261', 

248 f"'{dielectric.name}' and '{seen[key]}' are both at wrap depth " 

249 f"{dielectric.wrap_depth} on '{dielectric.root}'; at equal depth " 

250 f"there is no rule to decide which is visible", 

251 source=dielectric) 

252 else: 

253 seen[key] = dielectric.name 

254 

255 def check_names(self, pex25d_file: Any) -> None: 

256 """Conductor shortnames and terminal names are each unique.""" 

257 seen: Set[str] = set() 

258 for conductor in pex25d_file.conductors: 

259 if conductor.name in seen: 

260 self.diagnose('PEX25D-E0266', 

261 f"CONDUCTOR '{conductor.name}' is declared more " 

262 f"than once", source=conductor) 

263 seen.add(conductor.name) 

264 

265 seen = set() 

266 for terminal in pex25d_file.terminals: 

267 if terminal.name in seen: 

268 self.diagnose('PEX25D-E0267', 

269 f"TERMINAL '{terminal.name}' is declared more " 

270 f"than once", source=terminal) 

271 seen.add(terminal.name) 

272 

273 def check_resistance_records(self, pex25d_file: Any) -> None: 

274 has_temperature = pex25d_file.HasField('resistance_temperature') 

275 

276 for records, attribute, keyword in ( 

277 (pex25d_file.metal_resistances, 'metal', 'METAL'), 

278 (pex25d_file.via_resistances, 'via', 'VIA')): 

279 seen: Set[str] = set() 

280 for record in records: 

281 name = getattr(record, attribute) 

282 if name in seen: 

283 self.diagnose('PEX25D-E0268', 

284 f"More than one RESISTANCE {keyword} record " 

285 f"for '{name}'", source=record) 

286 seen.add(name) 

287 

288 if not has_temperature and (record.tc.tc1 or record.tc.tc2): 

289 # TC1/TC2 move a value away from a reference temperature. 

290 # Without RESISTANCE TEMPERATURE there is nothing to move 

291 # from, so a consumer can only ignore them. 

292 self.diagnose('PEX25D-W0269', 

293 f"RESISTANCE {keyword} '{name}' states " 

294 f"temperature coefficients, but the file has " 

295 f"no RESISTANCE TEMPERATURE to refer them to", 

296 severity=Severity.WARNING, source=record) 

297 

298 # ----------------------------------------------------------------- scene 

299 

300 def check_scene_layers(self, scene: Any) -> None: 

301 layer_kinds = pex25d_scene_pb2().ResolvedLayer 

302 

303 for layer in scene.layers: 

304 metal = layer.kind == layer_kinds.RESOLVED_LAYER_KIND_METAL 

305 via = layer.kind == layer_kinds.RESOLVED_LAYER_KIND_VIA 

306 

307 if not metal and not via: 

308 self.diagnose('PEX25D-E0270', 

309 f"Layer '{layer.name}' has no kind", 

310 source=layer) 

311 continue 

312 

313 # A METAL is a solid and needs a height; a VIA between two abutting 

314 # layers legitimately has none. 

315 if layer.zhigh < layer.zlow or (metal and layer.zhigh == layer.zlow): 

316 self.diagnose('PEX25D-E0271', 

317 f"Layer '{layer.name}' has z extent " 

318 f"[{layer.zlow}, {layer.zhigh}]", 

319 source=layer) 

320 

321 if via and not (layer.connects_below and layer.connects_above): 

322 self.diagnose('PEX25D-E0272', 

323 f"VIA layer '{layer.name}' does not carry its " 

324 f"resolved CONNECTS endpoints", source=layer) 

325 

326 arm = layer.WhichOneof('resistance') 

327 expected = 'metal_resistance' if metal else 'via_resistance' 

328 if arm is not None and arm != expected: 

329 self.diagnose('PEX25D-E0273', 

330 f"Layer '{layer.name}' is a " 

331 f"{'METAL' if metal else 'VIA'} but carries a " 

332 f"{arm.split('_')[0].upper()} resistance", 

333 source=layer) 

334 

335 def check_scene_references(self, scene: Any) -> None: 

336 """ 

337 Every name a resolved message states must be in the scene. 

338 

339 The resolver cannot produce a dangling one; a scene from somewhere else 

340 can, and a consumer that trusts the resolved form will crash on it 

341 rather than diagnose it. 

342 """ 

343 profiles = {layer.name for layer in scene.layers} 

344 profiles |= {d.name for d in scene.dielectrics} 

345 if scene.HasField('ground_plane'): 

346 profiles.add(scene.ground_plane.name) 

347 

348 for dielectric in scene.dielectrics: 

349 for name, clause in ((dielectric.wraps, 'WRAPS'), 

350 (dielectric.root, 'root'), 

351 (dielectric.between_below, 'BETWEEN'), 

352 (dielectric.between_above, 'BETWEEN')): 

353 if name and name not in profiles: 

354 self.diagnose('PEX25D-E0275', 

355 f"Dielectric '{dielectric.name}' names " 

356 f"'{name}' as its {clause}, which is not a " 

357 f"profile of this scene", source=dielectric) 

358 

359 layers = {layer.name for layer in scene.layers} 

360 for conductor in scene.conductors: 

361 for region in conductor.regions: 

362 if region.layer not in layers: 

363 self.diagnose('PEX25D-E0279', 

364 f"Conductor '{conductor.name}' has geometry " 

365 f"on '{region.layer}', which is not a layer " 

366 f"of this scene", source=conductor) 

367 

368 def check_scene_order(self, scene: Any) -> None: 

369 """ 

370 Dielectrics come in ascending ``wrap_depth``. 

371 

372 The order is what lets a consumer walk the list once and stop at the 

373 first dielectric claiming the point it is testing, which is the 

374 occupancy rule. Out of order, that walk silently returns the wrong 

375 material. 

376 """ 

377 previous = 0 

378 for dielectric in scene.dielectrics: 

379 if dielectric.wrap_depth < previous: 

380 self.diagnose('PEX25D-E0274', 

381 f"Dielectric '{dielectric.name}' is at wrap depth " 

382 f"{dielectric.wrap_depth} after one at depth " 

383 f"{previous}; the list must ascend", 

384 source=dielectric) 

385 return 

386 previous = dielectric.wrap_depth 

387 

388 def check_scene_terminals(self, scene: Any) -> None: 

389 layers = {layer.name for layer in scene.layers} 

390 seen: Set[str] = set() 

391 

392 for conductor in scene.conductors: 

393 regions = {region.layer for region in conductor.regions} 

394 for terminal in conductor.terminals: 

395 if terminal.name in seen: 

396 self.diagnose('PEX25D-E0267', 

397 f"TERMINAL '{terminal.name}' appears more " 

398 f"than once", source=terminal) 

399 seen.add(terminal.name) 

400 

401 if conductor.floating: 

402 self.diagnose('PEX25D-E0263', 

403 f"TERMINAL '{terminal.name}' is on FLOATING " 

404 f"conductor '{conductor.name}', which has no " 

405 f"port", source=terminal) 

406 

407 if terminal.layer not in layers: 

408 self.diagnose('PEX25D-E0276', 

409 f"TERMINAL '{terminal.name}' names layer " 

410 f"'{terminal.layer}', which is not a layer of " 

411 f"this scene", source=terminal) 

412 elif terminal.layer not in regions: 

413 self.diagnose('PEX25D-E0276', 

414 f"TERMINAL '{terminal.name}' is on layer " 

415 f"'{terminal.layer}', where conductor " 

416 f"'{conductor.name}' has no geometry", 

417 source=terminal) 

418 

419 # The node is the resolved intersection, and the resolver 

420 # rejects an empty one; an empty node here means the scene was 

421 # written by something that did not do the boolean. 

422 if not terminal.boxes and not terminal.polygons: 

423 self.diagnose('PEX25D-E0277', 

424 f"TERMINAL '{terminal.name}' has an empty " 

425 f"node: nothing was intersected", 

426 source=terminal) 

427 

428 # ------------------------------------------------------------- geometric 

429 

430 def check_shapes(self, shapes: Iterable[Shape]) -> None: 

431 for shape in shapes: 

432 if shape.is_box: 

433 self.check_box(shape) 

434 else: 

435 self.check_polygon(shape) 

436 

437 def check_box(self, shape: Shape) -> None: 

438 box = shape.geometry 

439 if box.lower_left.x >= box.upper_right.x or \ 

440 box.lower_left.y >= box.upper_right.y: 

441 self.geometric('PEX25D-E0308', 

442 f"{shape} is empty: LL ({box.lower_left.x}, " 

443 f"{box.lower_left.y}) is not below and left of UR " 

444 f"({box.upper_right.x}, {box.upper_right.y})", 

445 shape.source) 

446 

447 def check_polygon(self, shape: Shape) -> None: 

448 polygon = shape.geometry 

449 outer = self.check_ring(shape, polygon.outer, 'OUTER') 

450 holes = [self.check_ring(shape, hole, f"HOLE {i + 1}") 

451 for i, hole in enumerate(polygon.holes)] 

452 if outer is None or any(hole is None for hole in holes): 

453 return 

454 

455 for i, hole in enumerate(holes): 

456 if not ring_strictly_inside(hole, outer): 

457 self.geometric('PEX25D-E0306', 

458 f"{shape}: HOLE {i + 1} is not strictly inside " 

459 f"OUTER", shape.source) 

460 

461 for i in range(len(holes)): 

462 for j in range(i + 1, len(holes)): 

463 if rings_meet(holes[i], holes[j]): 

464 self.geometric('PEX25D-E0307', 

465 f"{shape}: HOLE {i + 1} and HOLE {j + 1} " 

466 f"touch or overlap; an island inside a hole " 

467 f"is a POLYGON record of its own", shape.source) 

468 

469 def check_ring(self, shape: Shape, ring: Any, what: str) -> Optional[Ring]: 

470 """One ring, or ``None`` once it is too broken for the checks after it.""" 

471 points: Ring = [(p.x, p.y) for p in ring.points] 

472 

473 if len(points) < 3: 

474 self.geometric('PEX25D-E0301', 

475 f"{shape}: {what} has {len(points)} vertices", 

476 shape.source) 

477 return None 

478 

479 if points[0] == points[-1]: 

480 self.geometric('PEX25D-E0302', 

481 f"{shape}: {what} repeats its first vertex " 

482 f"({points[0][0]}, {points[0][1]}) at the end; a ring " 

483 f"is closed implicitly", shape.source) 

484 return None 

485 

486 for i in range(len(points) - 1): 

487 if points[i] == points[i + 1]: 

488 self.geometric('PEX25D-E0303', 

489 f"{shape}: {what} repeats the vertex " 

490 f"({points[i][0]}, {points[i][1]})", shape.source) 

491 return None 

492 

493 if ring_is_collinear(points): 

494 self.geometric('PEX25D-E0304', 

495 f"{shape}: {what} encloses no area, every vertex " 

496 f"lying on one line", shape.source) 

497 return None 

498 

499 if not ring_is_simple(points): 

500 self.geometric('PEX25D-E0305', 

501 f"{shape}: {what} intersects itself", shape.source) 

502 return None 

503 

504 return points 

505 

506 def check_conductor_overlap(self, scene: Any) -> None: 

507 """ 

508 Two conductors may not share a point. 

509 

510 Shapes are swept in x and filtered on y and z before anything exact 

511 runs, because the interesting comparison — different conductors, same 

512 height, same place — is a vanishing fraction of the pairs. Touching is 

513 not overlap: abutting shapes of different conductors are legal, and 

514 only a shared area is reported. 

515 """ 

516 layers = {layer.name: layer for layer in scene.layers} 

517 

518 items: List[Item] = [] 

519 for conductor in scene.conductors: 

520 for region in conductor.regions: 

521 layer = layers.get(region.layer) 

522 if layer is None: 

523 continue 

524 for box in region.boxes: 

525 items.append(item_of_box(conductor, region.layer, layer, box)) 

526 for polygon in region.polygons: 

527 item = item_of_polygon(conductor, region.layer, layer, polygon) 

528 if item is not None: 

529 items.append(item) 

530 

531 items.sort(key=lambda item: item.xmin) 

532 

533 active: List[Item] = [] 

534 overlaps = 0 

535 for item in items: 

536 active = [other for other in active if other.xmax >= item.xmin] 

537 for other in active: 

538 if other.conductor == item.conductor: 

539 continue 

540 if other.xmax <= item.xmin or item.xmax <= other.xmin: 

541 continue 

542 if other.ymax <= item.ymin or item.ymax <= other.ymin: 

543 continue 

544 if other.zhigh <= item.zlow or item.zhigh <= other.zlow: 

545 continue 

546 if not items_overlap(other, item): 

547 continue 

548 

549 overlaps += 1 

550 if overlaps <= MAX_OVERLAP_REPORTS: 

551 self.geometric( 

552 'PEX25D-E0309', 

553 f"Conductors '{other.conductor}' (on '{other.layer}') " 

554 f"and '{item.conductor}' (on '{item.layer}') overlap " 

555 f"near ({max(other.xmin, item.xmin)}, " 

556 f"{max(other.ymin, item.ymin)})", item.source) 

557 active.append(item) 

558 

559 if overlaps > MAX_OVERLAP_REPORTS: 

560 self.diagnose('PEX25D-N0002', 

561 f"{overlaps - MAX_OVERLAP_REPORTS} further conductor " 

562 f"overlaps were found and not listed", 

563 tier=Tier.GEOMETRIC, severity=Severity.NOTE) 

564 

565 def geometric(self, code: str, message: str, source: Any = None) -> None: 

566 self.diagnose(code, message, tier=Tier.GEOMETRIC, source=source) 

567 

568 

569# ----------------------------------------------------------------------------- 

570# Shapes 

571# ----------------------------------------------------------------------------- 

572 

573Ring = List[Tuple[int, int]] 

574 

575 

576@dataclass(frozen=True) 

577class Shape: 

578 """A drawn shape with what the geometric tier needs to talk about it.""" 

579 

580 conductor: str 

581 layer: str 

582 is_box: bool 

583 geometry: Any # Box2D or Polygon2D 

584 source: Any = None # the record it came from, for its SourceRef 

585 

586 def __str__(self) -> str: 

587 kind = 'BOX' if self.is_box else 'POLYGON' 

588 return f"{kind} on conductor '{self.conductor}', layer '{self.layer}'" 

589 

590 

591def shapes_of_file(pex25d_file: Any) -> Iterator[Shape]: 

592 kinds = pex25d_file_pb2().ShapeRecord 

593 for shape in pex25d_file.shapes: 

594 if shape.kind == kinds.SHAPE_KIND_BOX: 

595 yield Shape(shape.conductor, shape.layer, True, shape.box, shape) 

596 elif shape.kind == kinds.SHAPE_KIND_POLYGON: 

597 yield Shape(shape.conductor, shape.layer, False, shape.polygon, shape) 

598 

599 

600def shapes_of_scene(scene: Any) -> Iterator[Shape]: 

601 for conductor in scene.conductors: 

602 for region in conductor.regions: 

603 for box in region.boxes: 

604 yield Shape(conductor.name, region.layer, True, box, conductor) 

605 for polygon in region.polygons: 

606 yield Shape(conductor.name, region.layer, False, polygon, conductor) 

607 

608 

609# ----------------------------------------------------------------------------- 

610# Integer geometry 

611# 

612# All of it is exact: coordinates are grid units, every predicate below is a 

613# comparison of integer cross and dot products, and the one place a midpoint is 

614# needed works in doubled coordinates rather than in floats. A conformance 

615# validator that answered "these two conductors overlap" from rounded 

616# arithmetic would be worse than none. 

617# ----------------------------------------------------------------------------- 

618 

619def cross3(o: Tuple[int, int], a: Tuple[int, int], b: Tuple[int, int]) -> int: 

620 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) 

621 

622 

623def dot3(o: Tuple[int, int], a: Tuple[int, int], b: Tuple[int, int]) -> int: 

624 return (a[0] - o[0]) * (b[0] - o[0]) + (a[1] - o[1]) * (b[1] - o[1]) 

625 

626 

627def edges(ring: Ring) -> Iterator[Tuple[Tuple[int, int], Tuple[int, int]]]: 

628 for i in range(len(ring)): 

629 yield ring[i], ring[(i + 1) % len(ring)] 

630 

631 

632def on_segment(a1: Tuple[int, int], a2: Tuple[int, int], 

633 p: Tuple[int, int]) -> bool: 

634 """Whether ``p``, already known to be collinear with a1-a2, is on it.""" 

635 return min(a1[0], a2[0]) <= p[0] <= max(a1[0], a2[0]) and \ 

636 min(a1[1], a2[1]) <= p[1] <= max(a1[1], a2[1]) 

637 

638 

639def segments_meet(a1: Tuple[int, int], a2: Tuple[int, int], 

640 b1: Tuple[int, int], b2: Tuple[int, int]) -> bool: 

641 """Any common point at all, touching and collinear overlap included.""" 

642 d1 = cross3(a1, a2, b1) 

643 d2 = cross3(a1, a2, b2) 

644 d3 = cross3(b1, b2, a1) 

645 d4 = cross3(b1, b2, a2) 

646 if d1 != 0 and d2 != 0 and d3 != 0 and d4 != 0: 

647 return (d1 > 0) != (d2 > 0) and (d3 > 0) != (d4 > 0) 

648 return (d1 == 0 and on_segment(a1, a2, b1)) or \ 

649 (d2 == 0 and on_segment(a1, a2, b2)) or \ 

650 (d3 == 0 and on_segment(b1, b2, a1)) or \ 

651 (d4 == 0 and on_segment(b1, b2, a2)) 

652 

653 

654def ring_is_simple(ring: Ring) -> bool: 

655 edge_list = list(edges(ring)) 

656 n = len(edge_list) 

657 for i in range(n): 

658 a1, a2 = edge_list[i] 

659 for j in range(i + 1, n): 

660 b1, b2 = edge_list[j] 

661 if j == i + 1 or (i == 0 and j == n - 1): 

662 # Consecutive edges share one endpoint legitimately. What they 

663 # may not do is fold back along each other. 

664 shared, before, after = (a2, a1, b2) if j == i + 1 \ 

665 else (a1, a2, b1) 

666 if cross3(shared, before, after) == 0 and \ 

667 dot3(shared, before, after) > 0: 

668 return False 

669 elif segments_meet(a1, a2, b1, b2): 

670 return False 

671 return True 

672 

673 

674def ring_is_collinear(ring: Ring) -> bool: 

675 origin = ring[0] 

676 direction = next((p for p in ring[1:] if p != origin), None) 

677 if direction is None: 

678 return True 

679 return all(cross3(origin, direction, p) == 0 for p in ring) 

680 

681 

682def point_in_ring(x: Any, y: Any, ring: Ring) -> int: 

683 """ 

684 Where a point lies relative to a ring: 1 inside, 0 on it, -1 outside. 

685 

686 The ring is integer; the point may be a Fraction, and every comparison 

687 below stays exact either way. 

688 """ 

689 inside = False 

690 for (x1, y1), (x2, y2) in edges(ring): 

691 if (x2 - x1) * (y - y1) - (y2 - y1) * (x - x1) == 0 and \ 

692 min(x1, x2) <= x <= max(x1, x2) and \ 

693 min(y1, y2) <= y <= max(y1, y2): 

694 return 0 

695 if (y1 > y) != (y2 > y): 

696 # Sign of (crossing_x - x), scaled by (y2 - y1). 

697 side = (x1 - x) * (y2 - y1) + (y - y1) * (x2 - x1) 

698 if (side > 0) == (y2 > y1): 

699 inside = not inside 

700 return 1 if inside else -1 

701 

702 

703@dataclass(frozen=True) 

704class Polygon: 

705 """A resolved polygon: one outer ring and its holes, as integer rings.""" 

706 

707 outer: Ring 

708 holes: List[Ring] = field(default_factory=list) 

709 

710 def rings(self) -> Iterator[Ring]: 

711 yield self.outer 

712 yield from self.holes 

713 

714 def all_edges(self) -> Iterator[Tuple[Tuple[int, int], Tuple[int, int]]]: