Coverage for pyTooling/ControlFlow/__init_

1# ==================================================================================================================== #

2# _____ _ _ ____ _ _ _____ _ #

3# _ __ _ |_ _|__ ___ | (_)_ __ __ _ / ___|___ _ __ | |_ _ __ ___ | | ___| | _____ __ #

4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` || | / _ \| '_ \| __| '__/ _ \| | |_ | |/ _ \ \ /\ / / #

5# | |_) | |_| || | (_) | (_) | | | | | | (_| || |__| (_) | | | | |_| | | (_) | | _| | | (_) \ V V / #

6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)____\___/|_| |_|\__|_| \___/|_|_| |_|\___/ \_/\_/ #

7# |_| |___/ |___/ #

8# ==================================================================================================================== #

9# Authors: #

10# Patrick Lehmann #

11# #

12# License: #

13# ==================================================================================================================== #

15# #

16# Licensed under the Apache License, Version 2.0 (the "License"); #

17# you may not use this file except in compliance with the License. #

18# You may obtain a copy of the License at #

19# #

20# http://www.apache.org/licenses/LICENSE-2.0 #

21# #

22# Unless required by applicable law or agreed to in writing, software #

23# distributed under the License is distributed on an "AS IS" BASIS, #

24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #

25# See the License for the specific language governing permissions and #

26# limitations under the License. #

27# #

28# SPDX-License-Identifier: Apache-2.0 #

29# ==================================================================================================================== #

30#

31"""

32A data structure to describe the **control flow graph** of a function: its basic blocks and the edges between them.

34A :class:`ControlFlowGraph` describes one function, e.g. a C or C++ function or a Python code object. A

35:class:`BasicBlock` is a sequence of code, which control enters at its top and leaves at its bottom. An :class:`Edge`

36leads from a block to a block control continues with, so a block with several outbound edges branches - a ``switch``

37has an edge per target. An :class:`EdgeKind` says why control continues there.

39Every graph has an entry block and an exit block. An exception is an :attr:`EdgeKind.Exception` edge: to the block of

40the handler catching it - a C++ ``catch`` or a Python ``except`` clause - or, if none does, to the graph's unwind

41block, through which it leaves the function.

43Blocks and edges carry an optional execution count, e.g. from a code coverage report, and an optional value of any

44type, e.g. the source lines of a block. Graphs, blocks and edges carry key-value-pairs, e.g. the results of an

45analysis. :meth:`ControlFlowGraph.ToGraph` converts a control flow graph into a :class:`~pyTooling.Graph.Graph`.

47.. hint::

49 See :ref:`high-level help <STRUCT/ControlFlow>` for explanations and usage examples.

51.. seealso::

53 :mod:`pyTooling.CallGraph`

54 |rarr| The call graph of a program, whose calls are made from the blocks of control flow graphs.

55 :mod:`pyTooling.Graph`

56 |rarr| The graph data structure a control flow graph is converted into.

57 :mod:`pyTooling.Graph.GraphML`

58 |rarr| Writing a graph as a GraphML document.

59"""

60from __future__ import annotations

62from enum import Enum

63from typing import Any, Generator, Hashable, Mapping, Optional as Nullable

65from pyTooling.Common import getFullyQualifiedName

66from pyTooling.DataModel import KeyValuePairsMixin, Predicate

67from pyTooling.Decorators import export, readonly

68from pyTooling.Exceptions import DuplicateElementError, ToolingException

69from pyTooling.Graph import Graph, Vertex

70from pyTooling.MetaClasses import ExtendedType

73@export

74class BlockKind(Enum):

75 """

76 Kind of a basic block.

78 A :class:`ControlFlowGraph` has exactly one entry block and one exit block, and at most one unwind block. Every other

79 block holds code.

80 """

81 Code = 0 #: A block of code, which control enters at its top and leaves at its bottom.

82 Entry = 1 #: The block control enters the function through.

83 Exit = 2 #: The block control leaves the function through, when the function returns.

84 Unwind = 3 #: The block an exception leaves the function through, when no handler in the function catches it.

86 def __str__(self) -> str:

87 """

88 Return the member's name.

90 :returns: Name of the member, e.g. ``Entry``.

91 """

92 return self.name

95@export

96class EdgeKind(Enum):

97 """

98 Kind of an edge: why control continues with the edge's destination.

99 """

100 Default = 0 #: The edge wasn't classified, e.g. an arc between two lines a code coverage tool reports.

101 FallThrough = 1 #: Control continues with the next block in code order, e.g. the side of a condition not jumping.

102 Jump = 2 #: Control jumps to the destination, e.g. a taken branch, a ``goto``, or a ``switch`` case.

103 Exception = 3 #: An exception leaves the block, e.g. by a C++ ``throw``, a Python ``raise``, or from a call.

104 Abnormal = 4 #: Control leaves the block without a jump or an exception, e.g. by calling ``exit()``.

105

106 def __str__(self) -> str:

107 """

108 Return the member's name.

109

110 :returns: Name of the member, e.g. ``FallThrough``.

111 """

112 return self.name

113

114

115@export

116class ControlFlowError(ToolingException):

117 """Base-exception of all exceptions raised by :mod:`pyTooling.ControlFlow`."""

118

119

120@export

121class DuplicateBlockError(ControlFlowError, DuplicateElementError):

122 """The exception raised for a block a graph has already: one with the same ID, or a second entry, exit or unwind."""

123

124 _blockID: Nullable[Hashable] #: ID of the rejected block.

125 _kind: Nullable[BlockKind] #: Kind of the rejected block, if a graph has one block of that kind at most.

126

127 def __init__(self, message: str, /, *, blockID: Nullable[Hashable] = None, kind: Nullable[BlockKind] = None) -> None:

128 """

129 Initializes the exception with the ID and kind of the rejected block.

130

131 :param message: The exception's message.

132 :param blockID: Optional, the ID of the rejected block.

133 :param kind: Optional, the kind of the rejected block, if a graph has one block of that kind at most.

134 """

135 super().__init__(message)

136 self._blockID = blockID

137 self._kind = kind

138

139 @readonly

140 def BlockID(self) -> Nullable[Hashable]:

141 """

142 Read-only property to access the ID of the rejected block (:attr:`_blockID`).

143

144 :returns: The block's ID, or ``None`` if it wasn't recorded.

145 """

146 return self._blockID

147

148 @readonly

149 def Kind(self) -> Nullable[BlockKind]:

150 """

151 Read-only property to access the kind of the rejected block, if a graph has one block of that kind at most

152 (:attr:`_kind`).

153

154 :returns: The block's kind (``None`` for a duplicate ID), or ``None`` if it wasn't recorded.

155 """

156 return self._kind

157

158

159@export

160class DuplicateEdgeError(ControlFlowError, DuplicateElementError):

161 """The exception raised for an edge, which connects the same two blocks as an edge of the same kind."""

162

163 _existingEdge: Nullable[Edge] #: Edge connecting the same two blocks with the same kind already.

164

165 def __init__(self, message: str, /, *, existingEdge: Nullable[Edge] = None) -> None:

166 """

167 Initializes the exception with the edge connecting the same two blocks already.

168

169 :param message: The exception's message.

170 :param existingEdge: Optional, the edge connecting the same two blocks with the same kind already.

171 """

172 super().__init__(message)

173 self._existingEdge = existingEdge

174

175 @readonly

176 def ExistingEdge(self) -> Nullable[Edge]:

177 """

178 Read-only property to access the edge connecting the same two blocks with the same kind already

179 (:attr:`_existingEdge`).

180

181 :returns: The existing edge, or ``None`` if it wasn't recorded.

182 """

183 return self._existingEdge

184

185

186@export

187class Base(KeyValuePairsMixin, metaclass=ExtendedType, slots=True):

188 """

189 Base-class of all control flow graph elements, adding a dictionary of arbitrary key-value-pairs to them.

190

191 Every graph, block and edge can carry data attached by its user, e.g. the results of an analysis under a key of the

192 analysis' choice: :pycode:`block["dominator"] = entry`. The element's dunder methods serve this dictionary.

193 """

194

195

196@export

197class BaseWithCountAndValue(Base):

198 """

199 Base-class of elements carrying an execution count and a value.

200

201 Basic blocks and edges are such elements.

202 """

203 _count: Nullable[int] #: How often the element was executed, or ``None`` if that's unknown.

204 _value: Nullable[Any] #: Any value attached to the element, or ``None``.

205

206 def __init__(

207 self,

208 count: Nullable[int] = None,

209 value: Nullable[Any] = None,

210 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None

211 ) -> None:

212 """

213 Initializes the execution count, the value and the key-value-pairs of an element.

214

215 :param count: Optional, how often the element was executed. Default: ``None``.

216 :param value: Optional, any value attached to the element. Default: ``None``.

217 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs. Default: ``None``.

218 :raises TypeError: If parameter 'count' is not of type :class:`int`.

219 :raises ValueError: If parameter 'count' is negative.

220 """

221 super().__init__(keyValuePairs)

222

223 self.Count = count

224 self._value = value

225

226 @property

227 def Count(self) -> Nullable[int]:

228 """

229 Property to access how often the element was executed (:attr:`_count`).

230

231 :returns: The execution count, or ``None`` if it's unknown.

232 :raises TypeError: If the assigned count is not of type :class:`int`.

233 :raises ValueError: If the assigned count is negative.

234 """

235 return self._count

236

237 @Count.setter

238 def Count(self, count: Nullable[int]) -> None:

239 if count is not None:

240 if not isinstance(count, int) or isinstance(count, bool):

241 ex = TypeError("Parameter 'count' is not of type 'int'.")

242 ex.add_note(f"Got type '{getFullyQualifiedName(count)}'.")

243 raise ex

244 elif count < 0:

245 ex = ValueError("Parameter 'count' is negative.")

246 ex.add_note(f"Got value '{count}'.")

247 raise ex

248

249 self._count = count

250

251 @property

252 def Value(self) -> Nullable[Any]:

253 """

254 Property to access the value attached to the element (:attr:`_value`).

255

256 :returns: The value, or ``None`` if none is attached.

257 """

258 return self._value

259

260 @Value.setter

261 def Value(self, value: Nullable[Any]) -> None:

262 self._value = value

263

264

265@export

266class BasicBlock(BaseWithCountAndValue):

267 """

268 A basic block of a control flow graph: a sequence of code, which control enters at its top and leaves at its bottom.

269

270 A block is identified by an ID unique within its graph, e.g. a compiler's block number or a line number. Its outbound

271 edges lead to the blocks control continues with.

272 """

273 _controlFlowGraph: _ControlFlowGraph #: The control flow graph this block belongs to.

274 _id: Hashable #: ID of the block, unique within its graph.

275 _kind: BlockKind #: Kind of the block.

276 _inboundEdges: list[Edge] #: Edges leading to this block.

277 _outboundEdges: list[Edge] #: Edges leading from this block to the blocks control continues with.

278

279 def __init__(

280 self,

281 controlFlowGraph: _ControlFlowGraph,

282 blockID: Hashable,

283 *,

284 kind: BlockKind = BlockKind.Code,

285 count: Nullable[int] = None,

286 value: Nullable[Any] = None,

287 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None

288 ) -> None:

289 """

290 Initializes a basic block and adds it to its graph.

291

292 A graph creates its entry and exit block itself. A block of :attr:`BlockKind.Unwind` becomes the graph's unwind

293 block.

294

295 :param controlFlowGraph: The control flow graph the block belongs to.

296 :param blockID: ID of the block, unique within its graph.

297 :param kind: Optional, kind of the block. Default: :attr:`BlockKind.Code`.

298 :param count: Optional, how often the block was executed. Default: ``None``.

299 :param value: Optional, any value attached to the block, e.g. its source lines. Default: ``None``.

300 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs. Default: ``None``.

301 :raises TypeError: If parameter 'count' is not of type :class:`int`.

302 :raises ValueError: If parameter 'count' is negative.

303 :raises ValueError: If parameter 'controlFlowGraph' is None.

304 :raises TypeError: If parameter 'controlFlowGraph' is not of type :class:`ControlFlowGraph`.

305 :raises ValueError: If parameter 'blockID' is None.

306 :raises TypeError: If parameter 'blockID' is not hashable.

307 :raises ValueError: If parameter 'kind' is None.

308 :raises TypeError: If parameter 'kind' is not of type :class:`BlockKind`.

309 :raises DuplicateBlockError: If the graph has a block with that ID already.

310 :raises DuplicateBlockError: If the block is an entry, exit or unwind block, and the graph has one already.

311 """

312 super().__init__(count, value, keyValuePairs)

313

314 if controlFlowGraph is None:

315 raise ValueError("Parameter 'controlFlowGraph' is None.")

316 elif not isinstance(controlFlowGraph, _ControlFlowGraph):

317 ex = TypeError("Parameter 'controlFlowGraph' is not of type 'ControlFlowGraph'.")

318 ex.add_note(f"Got type '{getFullyQualifiedName(controlFlowGraph)}'.")

319 raise ex

320

321 if blockID is None:

322 raise ValueError("Parameter 'blockID' is None.")

323 elif not isinstance(blockID, Hashable):

324 ex = TypeError("Parameter 'blockID' is not hashable.")

325 ex.add_note(f"Got type '{getFullyQualifiedName(blockID)}'.")

326 raise ex

327 elif blockID in controlFlowGraph._blocks:

328 raise DuplicateBlockError(

329 f"Control flow graph '{controlFlowGraph._name}' has a block '{blockID}' already.",

330 blockID=blockID

331 )

332

333 if kind is None:

334 raise ValueError("Parameter 'kind' is None.")

335 elif not isinstance(kind, BlockKind):

336 ex = TypeError("Parameter 'kind' is not of type 'BlockKind'.")

337 ex.add_note(f"Got type '{getFullyQualifiedName(kind)}'.")

338 raise ex

339 elif kind is BlockKind.Entry and len(controlFlowGraph._blocks) > 0:

340 raise DuplicateBlockError(

341 f"Control flow graph '{controlFlowGraph._name}' has an entry block already.",

342 blockID=blockID,

343 kind=kind

344 )

345 elif kind is BlockKind.Exit and len(controlFlowGraph._blocks) > 1:

346 raise DuplicateBlockError(

347 f"Control flow graph '{controlFlowGraph._name}' has an exit block already.",

348 blockID=blockID,

349 kind=kind

350 )

351 elif kind is BlockKind.Unwind and controlFlowGraph._unwind is not None:

352 raise DuplicateBlockError(

353 f"Control flow graph '{controlFlowGraph._name}' has an unwind block already.",

354 blockID=blockID,

355 kind=kind

356 )

357

358 self._controlFlowGraph = controlFlowGraph

359 self._id = blockID

360 self._kind = kind

361 self._inboundEdges = []

362 self._outboundEdges = []

363

364 controlFlowGraph._blocks[blockID] = self

365 if kind is BlockKind.Unwind:

366 controlFlowGraph._unwind = self

367

368 @readonly

369 def ControlFlowGraph(self) -> _ControlFlowGraph:

370 """

371 Read-only property to access the control flow graph this block belongs to (:attr:`_controlFlowGraph`).

372

373 :returns: The control flow graph.

374 """

375 return self._controlFlowGraph

376

377 @readonly

378 def ID(self) -> Hashable:

379 """

380 Read-only property to access the block's ID (:attr:`_id`).

381

382 :returns: ID of the block, unique within its graph.

383 """

384 return self._id

385

386 @readonly

387 def Kind(self) -> BlockKind:

388 """

389 Read-only property to access the block's kind (:attr:`_kind`).

390

391 :returns: Kind of the block.

392 """

393 return self._kind

394

395 @readonly

396 def InboundEdges(self) -> tuple[Edge, ...]:

397 """

398 Read-only property to return the edges leading to this block.

399

400 :returns: The inbound edges, in the order they were created.

401 """

402 return tuple(self._inboundEdges)

403

404 @readonly

405 def OutboundEdges(self) -> tuple[Edge, ...]:

406 """

407 Read-only property to return the edges leading from this block to the blocks control continues with.

408

409 :returns: The outbound edges, in the order they were created.

410 """

411 return tuple(self._outboundEdges)

412

413 def EdgeTo(

414 self,

415 destination: BasicBlock,

416 edgeCount: Nullable[int] = None,

417 edgeValue: Nullable[Any] = None,

418 edgeKind: EdgeKind = EdgeKind.Default,

419 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None

420 ) -> Edge:

421 """

422 Create an outbound edge from this block to the block control continues with.

423

424 :param destination: The block control continues with.

425 :param edgeCount: Optional, how often control took the edge. Default: ``None``.

426 :param edgeValue: Optional, any value attached to the edge, e.g. a ``case`` label. Default: ``None``.

427 :param edgeKind: Optional, kind of the edge. Default: :attr:`EdgeKind.Default`.

428 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the edge. Default: ``None``.

429 :returns: The edge leading from this block to the destination.

430 :raises ValueError: If this block is an exit or unwind block.

431 :raises ValueError: If parameter 'destination' is None.

432 :raises TypeError: If parameter 'destination' is not of type :class:`BasicBlock`.

433 :raises ValueError: If parameter 'destination' is an entry block.

434 :raises ValueError: If parameter 'destination' belongs to another graph than this block.

435 :raises TypeError: If parameter 'edgeCount' is not of type :class:`int`.

436 :raises ValueError: If parameter 'edgeCount' is negative.

437 :raises ValueError: If parameter 'edgeKind' is None.

438 :raises TypeError: If parameter 'edgeKind' is not of type :class:`EdgeKind`.

439 :raises DuplicateEdgeError: If an edge of the same kind connects the two blocks already.

440

441 .. seealso::

442

443 :meth:`EdgeFrom`

444 |rarr| Create an inbound edge from a block to this block.

445 """

446 return Edge(self, destination, edgeKind, count=edgeCount, value=edgeValue, keyValuePairs=keyValuePairs)

447

448 def EdgeFrom(

449 self,

450 source: BasicBlock,

451 edgeCount: Nullable[int] = None,

452 edgeValue: Nullable[Any] = None,

453 edgeKind: EdgeKind = EdgeKind.Default,

454 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None

455 ) -> Edge:

456 """

457 Create an inbound edge from the block control leaves to this block.

458

459 :param source: The block control leaves.

460 :param edgeCount: Optional, how often control took the edge. Default: ``None``.

461 :param edgeValue: Optional, any value attached to the edge, e.g. a ``case`` label. Default: ``None``.

462 :param edgeKind: Optional, kind of the edge. Default: :attr:`EdgeKind.Default`.

463 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs for the edge. Default: ``None``.

464 :returns: The edge leading from the source to this block.

465 :raises ValueError: If parameter 'source' is None.

466 :raises TypeError: If parameter 'source' is not of type :class:`BasicBlock`.

467 :raises ValueError: If parameter 'source' is an exit or unwind block.

468 :raises ValueError: If this block is an entry block.

469 :raises ValueError: If this block belongs to another graph than parameter 'source'.

470 :raises TypeError: If parameter 'edgeCount' is not of type :class:`int`.

471 :raises ValueError: If parameter 'edgeCount' is negative.

472 :raises ValueError: If parameter 'edgeKind' is None.

473 :raises TypeError: If parameter 'edgeKind' is not of type :class:`EdgeKind`.

474 :raises DuplicateEdgeError: If an edge of the same kind connects the two blocks already.

475

476 .. seealso::

477

478 :meth:`EdgeTo`

479 |rarr| Create an outbound edge from this block to a block control continues with.

480 """

481 return Edge(source, self, edgeKind, count=edgeCount, value=edgeValue, keyValuePairs=keyValuePairs)

482

483

484@export

485class Edge(BaseWithCountAndValue):

486 """

487 An edge of a control flow graph, leading from a block to a block control continues with.

488

489 The edge's :class:`EdgeKind` says why control continues there. Two blocks can be connected by edges of different

490 kinds, but only by one edge of each kind.

491 """

492 _source: BasicBlock #: The block control leaves.

493 _destination: BasicBlock #: The block control continues with.

494 _kind: EdgeKind #: Kind of the edge.

495

496 def __init__(

497 self,

498 source: BasicBlock,

499 destination: BasicBlock,

500 kind: EdgeKind = EdgeKind.Default,

501 *,

502 count: Nullable[int] = None,

503 value: Nullable[Any] = None,

504 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None

505 ) -> None:

506 """

507 Initializes an edge between two blocks of a graph and adds it to the graph.

508

509 :param source: The block control leaves.

510 :param destination: The block control continues with.

511 :param kind: Optional, kind of the edge. Default: :attr:`EdgeKind.Default`.

512 :param count: Optional, how often control took the edge. Default: ``None``.

513 :param value: Optional, any value attached to the edge, e.g. a ``case`` label. Default: ``None``.

514 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs. Default: ``None``.

515 :raises TypeError: If parameter 'count' is not of type :class:`int`.

516 :raises ValueError: If parameter 'count' is negative.

517 :raises ValueError: If parameter 'source' is None.

518 :raises TypeError: If parameter 'source' is not of type :class:`BasicBlock`.

519 :raises ValueError: If parameter 'source' is an exit or unwind block.

520 :raises ValueError: If parameter 'destination' is None.

521 :raises TypeError: If parameter 'destination' is not of type :class:`BasicBlock`.

522 :raises ValueError: If parameter 'destination' is an entry block.

523 :raises ValueError: If parameter 'destination' belongs to another graph than parameter 'source'.

524 :raises ValueError: If parameter 'kind' is None.

525 :raises TypeError: If parameter 'kind' is not of type :class:`EdgeKind`.

526 :raises DuplicateEdgeError: If an edge of the same kind connects the two blocks already.

527 """

528 super().__init__(count, value, keyValuePairs)

529

530 if source is None:

531 raise ValueError("Parameter 'source' is None.")

532 elif not isinstance(source, BasicBlock):

533 ex = TypeError("Parameter 'source' is not of type 'BasicBlock'.")

534 ex.add_note(f"Got type '{getFullyQualifiedName(source)}'.")

535 raise ex

536 elif source._kind is BlockKind.Exit or source._kind is BlockKind.Unwind:

537 ex = ValueError("Parameter 'source' is an exit or unwind block.")

538 ex.add_note(f"Got block '{source._id}' of kind '{source._kind}'.")

539 raise ex

540

541 if destination is None:

542 raise ValueError("Parameter 'destination' is None.")

543 elif not isinstance(destination, BasicBlock):

544 ex = TypeError("Parameter 'destination' is not of type 'BasicBlock'.")

545 ex.add_note(f"Got type '{getFullyQualifiedName(destination)}'.")

546 raise ex

547 elif destination._kind is BlockKind.Entry:

548 ex = ValueError("Parameter 'destination' is an entry block.")

549 ex.add_note(f"Got block '{destination._id}'.")

550 raise ex

551 elif destination._controlFlowGraph is not source._controlFlowGraph:

552 ex = ValueError("Parameter 'destination' belongs to another graph than parameter 'source'.")

553 ex.add_note(f"Got graphs '{source._controlFlowGraph._name}' and '{destination._controlFlowGraph._name}'.")

554 raise ex

555

556 if kind is None:

557 raise ValueError("Parameter 'kind' is None.")

558 elif not isinstance(kind, EdgeKind):

559 ex = TypeError("Parameter 'kind' is not of type 'EdgeKind'.")

560 ex.add_note(f"Got type '{getFullyQualifiedName(kind)}'.")

561 raise ex

562

563 for edge in source._outboundEdges:

564 if edge._destination is destination and edge._kind is kind:

565 ex = DuplicateEdgeError(

566 f"Blocks '{source._id}' and '{destination._id}' are connected by such an edge already.",

567 existingEdge=edge

568 )

569 ex.add_note(f"Got edge kind '{kind}'.")

570 raise ex

571

572 self._source = source

573 self._destination = destination

574 self._kind = kind

575

576 source._outboundEdges.append(self)

577 destination._inboundEdges.append(self)

578 source._controlFlowGraph._edges.append(self)

579

580 @readonly

581 def Source(self) -> BasicBlock:

582 """

583 Read-only property to access the block control leaves (:attr:`_source`).

584

585 :returns: The source block.

586 """

587 return self._source

588

589 @readonly

590 def Destination(self) -> BasicBlock:

591 """

592 Read-only property to access the block control continues with (:attr:`_destination`).

593

594 :returns: The destination block.

595 """

596 return self._destination

597

598 @readonly

599 def Kind(self) -> EdgeKind:

600 """

601 Read-only property to access the edge's kind (:attr:`_kind`).

602

603 :returns: Kind of the edge.

604 """

605 return self._kind

606

607

608@export

609class ControlFlowGraph(Base):

610 """

611 The control flow graph of a function: its basic blocks, the edges between them, and its entry and exit block.

612

613 A block is looked up by its ID: :pycode:`graph.GetBlock(3)` returns the block with ID ``3``, and

614 :pycode:`graph.ContainsBlock(3)` checks if the graph has one. :meth:`IterateBlocks` yields the blocks in the order

615 they were created. The graph's dunder methods serve its key-value-pairs, like a block's or an edge's.

616 """

617 _name: str #: Name of the function.

618 _blocks: dict[Hashable, BasicBlock] #: Blocks of the graph by ID, in the order they were created.

619 _edges: list[Edge] #: Edges of the graph, in the order they were created.

620 _entry: BasicBlock #: The block control enters the function through.

621 _exit: BasicBlock #: The block control leaves the function through, when the function returns.

622 _unwind: Nullable[BasicBlock] #: The block an exception leaves the function through, if the graph has one.

623

624 def __init__(

625 self,

626 name: str,

627 *,

628 entryID: Hashable = "entry",

629 exitID: Hashable = "exit",

630 keyValuePairs: Nullable[Mapping[Hashable, Any]] = None

631 ) -> None:

632 """

633 Initializes a control flow graph of a function, with an entry and an exit block.

634

635 The entry and the exit are the graph's first two blocks. An unwind block is created like any other block, as a

636 block of :attr:`BlockKind.Unwind`.

637

638 :param name: Name of the function.

639 :param entryID: Optional, ID of the entry block. Default: ``"entry"``.

640 :param exitID: Optional, ID of the exit block. Default: ``"exit"``.

641 :param keyValuePairs: Optional, mapping (dictionary) of key-value-pairs. Default: ``None``.

642 :raises ValueError: If parameter 'name' is None.

643 :raises TypeError: If parameter 'name' is not of type :class:`str`.

644 :raises ValueError: If parameter 'name' is empty.

645 :raises ValueError: If parameter 'entryID' is None.

646 :raises TypeError: If parameter 'entryID' is not hashable.

647 :raises ValueError: If parameter 'exitID' is None.

648 :raises TypeError: If parameter 'exitID' is not hashable.

649 :raises ValueError: If parameter 'exitID' equals parameter 'entryID'.

650 """

651 super().__init__(keyValuePairs)

652

653 if name is None:

654 raise ValueError("Parameter 'name' is None.")

655 elif not isinstance(name, str):

656 ex = TypeError("Parameter 'name' is not of type 'str'.")

657 ex.add_note(f"Got type '{getFullyQualifiedName(name)}'.")

658 raise ex

659 elif name == "":

660 raise ValueError("Parameter 'name' is empty.")

661

662 for parameterName, blockID in (

663 ("entryID", entryID),

664 ("exitID", exitID)

665 ):

666 if blockID is None:

667 raise ValueError(f"Parameter '{parameterName}' is None.")

668 elif not isinstance(blockID, Hashable):

669 ex = TypeError(f"Parameter '{parameterName}' is not hashable.")

670 ex.add_note(f"Got type '{getFullyQualifiedName(blockID)}'.")

671 raise ex

672

673 if exitID == entryID:

674 ex = ValueError("Parameter 'exitID' equals parameter 'entryID'.")

675 ex.add_note(f"Got value '{exitID}'.")

676 raise ex

677

678 self._name = name

679 self._blocks = {}

680 self._edges = []

681 self._unwind = None

682 self._entry = BasicBlock(self, entryID, kind=BlockKind.Entry)

683 self._exit = BasicBlock(self, exitID, kind=BlockKind.Exit)

684

685 @readonly

686 def Name(self) -> str:

687 """

688 Read-only property to access the name of the function (:attr:`_name`).

689

690 :returns: Name of the function.

691 """

692 return self._name

693

694 @readonly

695 def Entry(self) -> BasicBlock:

696 """

697 Read-only property to access the block control enters the function through (:attr:`_entry`).

698

699 :returns: The entry block.

700 """

701 return self._entry

702

703 @readonly

704 def Exit(self) -> BasicBlock:

705 """

706 Read-only property to access the block control leaves the function through, when it returns (:attr:`_exit`).

707

708 :returns: The exit block.

709 """

710 return self._exit

711

712 @readonly

713 def Unwind(self) -> Nullable[BasicBlock]:

714 """

715 Read-only property to access the block an exception leaves the function through (:attr:`_unwind`).

716

717 :returns: The unwind block, or ``None`` if the graph has none.

718 """

719 return self._unwind

720

721 @readonly

722 def Blocks(self) -> dict[Hashable, BasicBlock]:

723 """

724 Read-only property to access the blocks of the graph by ID (:attr:`_blocks`).

725

726 :returns: The blocks, in the order they were created.

727 """

728 return self._blocks

729

730 @readonly

731 def Edges(self) -> list[Edge]:

732 """

733 Read-only property to access the edges of the graph (:attr:`_edges`).

734

735 :returns: The edges, in the order they were created.

736 """

737 return self._edges

738

739 @readonly

740 def BlockCount(self) -> int:

741 """

742 Read-only property to return the number of blocks in the graph, including its entry, exit and unwind block.

743

744 :returns: Number of blocks.

745 """

746 return len(self._blocks)

747

748 def ContainsBlock(self, blockID: Hashable) -> bool:

749 """

750 Check if the graph has a block with the given ID.

751

752 :param blockID: ID of the block.

753 :returns: ``True``, if the graph has a block with that ID.

754 """

755 return blockID in self._blocks

756

757 def GetBlock(self, blockID: Hashable) -> BasicBlock:

758 """

759 Return the block with the given ID.

760

761 :param blockID: ID of the block.

762 :returns: The block with that ID.

763 :raises KeyError: If the graph has no block with that ID.

764 """

765 return self._blocks[blockID]

766

767 def IterateBlocks(

768 self,

769 predicate: Nullable[Predicate[BasicBlock]] = None

770 ) -> Generator[BasicBlock, None, None]:

771 """

772 Iterate all or selected blocks of the graph.

773

774 If parameter ``predicate`` is not None, the given filter function is used to skip blocks in the generator.

775

776 :param predicate: Optional, filter function accepting any block and returning a boolean.

777 :returns: A generator to iterate the blocks, in the order they were created.

778 """

779 if predicate is None:

780 yield from self._blocks.values()

781 else:

782 for block in self._blocks.values():

783 if predicate(block):

784 yield block

785

786 def ToGraph(self) -> Graph:

787 """

788 Convert the control flow graph into a :class:`~pyTooling.Graph.Graph`.

789

790 Every block becomes a :class:`~pyTooling.Graph.Vertex` with the block's ID as

791 :attr:`~pyTooling.Graph.Vertex.ID` and the block's value as :attr:`~pyTooling.Graph.Vertex.Value`, so

792 :meth:`Graph.GetVertexByID <pyTooling.Graph.Graph.GetVertexByID>` finds a block's vertex. Every edge becomes an

793 :class:`~pyTooling.Graph.Edge` in the direction control flows, with the edge's kind as

794 :attr:`~pyTooling.Graph.BaseEdge.Kind` and the edge's value as value.

795

796 The graph, its vertices and its edges carry a copy of the key-value-pairs of the control flow graph, its blocks and

797 its edges. Vertices and edges carry two key-value-pairs more, which a writer like :mod:`pyTooling.Graph.GraphML`

798 writes out:

799

800 * ``kind``: the block's :class:`BlockKind` or the edge's :class:`EdgeKind` member, whose :func:`str` is its name.

801 * ``count``: the execution count; only if it's known.

802

803 :returns: The graph, named like the control flow graph.

804 """

805 graph = Graph(name=self._name, keyValuePairs=self._dict)

806

807 vertices: dict[Hashable, Vertex] = {}

808 for block in self._blocks.values():

809 keyValuePairs: dict[Hashable, Any] = {**block._dict, "kind": block._kind}

810 if block._count is not None:

811 keyValuePairs["count"] = block._count

812

813 vertices[block._id] = Vertex(vertexID=block._id, value=block._value, keyValuePairs=keyValuePairs, graph=graph)

814

815 for edge in self._edges:

816 keyValuePairs = {**edge._dict, "kind": edge._kind}

817 if edge._count is not None:

818 keyValuePairs["count"] = edge._count

819

820 vertices[edge._source._id].EdgeToVertex(

821 vertices[edge._destination._id],

822 edgeValue=edge._value,

823 edgeKind=edge._kind,

824 keyValuePairs=keyValuePairs

825 )

826

827 return graph

828

829

830# A class with a property named like a class - ``ControlFlowGraph`` - can't name that class in the annotation of a

831# field: the class body's namespace, where annotations are evaluated, binds the name to the property.

832_ControlFlowGraph = ControlFlowGraph

Coverage for pyTooling/ControlFlow/init.py: 100%

282 statements