Use shortest path. Still needs tests
@@ -11,6 +11,8 @@ from functools import total_ordering
from math import inf
from typing import Any, Dict, Optional
+import networkx as nx
+
import pynguin.coverage.branch.branchcoveragegoal as bcg
import pynguin.coverage.branch.branchpool as bp
from pynguin.analyses.controlflow.controldependencegraph import ControlDependenceGraph
@@ -193,42 +195,38 @@ def _get_non_root_distance(
return distance
cdg = tracer.get_known_data().existing_code_objects[branch.code_object_id].cdg
- cdg_node = _get_node_with_predicate_id(cdg, branch.predicate_id)
- while (control_dependency := _get_control_dependency(cdg, cdg_node)) is not None:
- distance.increase_approach_level()
- cdg_node = control_dependency
- if control_dependency.predicate_id in trace.executed_predicates:
- # Predicate was executed but did not lead to execution of desired predicate
- # So the remaining branch distance to the true or false branch is
- # the desired distance, right?
- # One of them has to be zero, so we can simply add them.
- distance.branch_distance = _predicate_fitness(
- branch.predicate_id, trace.true_distances
- ) + _predicate_fitness(branch.predicate_id, trace.false_distances)
- return distance
+ target_node = _get_node_with_predicate_id(cdg, branch.predicate_id)
- # No predicate executed, so fallback to diameter
distance.approach_level = (
tracer.get_known_data()
.existing_code_objects[branch.code_object_id]
.cfg.diameter
)
- return distance
-
+ for node in [
+ node
+ for node in cdg.nodes
+ if node.predicate_id is not None
+ and node.predicate_id in trace.executed_predicates
+ ]:
+ try:
+ candidate = ControlFlowDistance()
+ candidate.approach_level = nx.shortest_path_length(
+ cdg.graph, node, target_node
+ )
+ # Predicate was executed but did not lead to execution of desired predicate
+ # So the remaining branch distance to the true or false branch is
+ # the desired distance, right?
+ # One of them has to be zero, so we can simply add them.
+ assert node.predicate_id is not None
+ candidate.branch_distance = _predicate_fitness(
+ node.predicate_id, trace.true_distances
+ ) + _predicate_fitness(node.predicate_id, trace.false_distances)
+ distance = min(distance, candidate)
+ except nx.NetworkXNoPath:
+ # No path from node to target.
+ pass
-def _get_control_dependency(
- cdg: ControlDependenceGraph, node: ProgramGraphNode
-) -> Optional[ProgramGraphNode]:
- predecessors = cdg.get_predecessors(node)
- if len(predecessors) == 0:
- return None
- # Assumes there is at most one predecessor, i.e., cdg is a tree?
- assert len(predecessors) == 1
- predecessor = predecessors.pop()
- if not predecessor.predicate_id:
- # Maybe go to next predecessor instead?
- return None
- return predecessor
+ return distance
def _get_node_with_predicate_id(
