https://github.com/SLTozer updated https://github.com/llvm/llvm-project/pull/203844
>From 37c744fb58457163c2e5cb8ce423748ca53d0470 Mon Sep 17 00:00:00 2001 From: Stephen Tozer <[email protected]> Date: Fri, 12 Jun 2026 16:24:40 +0100 Subject: [PATCH] [Dexter] Add !step node for testing stepping behaviour This patch adds a node for generating metrics based on lines stepped on. The new node has 3 versions: !step exactly, !step order, and !step never, which check an expected list of line numbers against the actual line numbers seen while the expect is active. --- .../dexter/dex/evaluation/ExpectRewriter.py | 5 +- .../dexter/dex/evaluation/Metrics.py | 81 +++++++++++- .../dexter/dex/evaluation/RunMatch.py | 122 ++++++++++++++---- .../dexter/dex/test_script/Nodes.py | 33 ++++- .../dexter/dex/test_script/Script.py | 12 ++ .../evaluation/eval_steps_penalties.cpp | 69 ++++++++++ .../scripts/evaluation/eval_steps_perfect.cpp | 46 +++++++ .../parser/step-node-expected-values.test | 19 +++ 8 files changed, 354 insertions(+), 33 deletions(-) create mode 100644 cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_penalties.cpp create mode 100644 cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_perfect.cpp create mode 100644 cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/parser/step-node-expected-values.test diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/ExpectRewriter.py b/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/ExpectRewriter.py index 2d42062a70fff..45fc4ec18e51e 100644 --- a/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/ExpectRewriter.py +++ b/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/ExpectRewriter.py @@ -231,9 +231,10 @@ def collect_expects_to_rewrite( assert expected_value is None self.scope_expect_rewrites[expect] = [] return + if expected_value is not None: + return assert isinstance(expect, Value), "Non-Value expects currently unsupported" - if expected_value is None: - self.unknown_expect_rewrites[expect] = [] + self.unknown_expect_rewrites[expect] = [] script.visit_script(visit_expect=collect_expects_to_rewrite) diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/Metrics.py b/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/Metrics.py index 1cac20303e09f..27859beab81c9 100644 --- a/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/Metrics.py +++ b/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/Metrics.py @@ -7,14 +7,14 @@ """Produce metric results from the results of a comparison of a DexterScript and debugger output. """ -from typing import Any, Dict, List, Union +from typing import Any, Dict, List, Optional, Union from dex.evaluation.ExpectMatch import ( DebuggerExpectMatch, MatchResult, get_expected_value_set, ) -from dex.test_script.Nodes import Expect, Value +from dex.test_script.Nodes import Expect, Step, Value class Metric: @@ -156,3 +156,80 @@ def get_variable_metrics( "missing_values": ScalarMetric(num_missing_values, improves_asc=False), } return metrics + + +def lcs_len(a: List[int], b: List[int]) -> int: + """Returns the length of the longest common subsequence between a and b.""" + lcs_table: List[List[int]] = [ + [0 for _ in range(len(b) + 1)] for _ in range(len(a) + 1) + ] + for a_idx in range(len(a)): + for b_idx in range(len(b)): + if a[a_idx] == b[b_idx]: + lcs_table[a_idx + 1][b_idx + 1] = 1 + lcs_table[a_idx][b_idx] + else: + lcs_table[a_idx + 1][b_idx + 1] = max( + lcs_table[a_idx + 1][b_idx], lcs_table[a_idx][b_idx + 1] + ) + return lcs_table[-1][-1] + + +def get_step_metrics( + expect: Step, expected_lines: List[int], step_lines: List[int] +) -> Dict[str, Metric]: + """Given an Expect node with its expected values and a list of all matches for that Expect in a debugger session, + returns the computed metrics for that Expect node.""" + + expected_line_set = set(expected_lines) + actual_line_set = set(step_lines) + + total_line_steps = len(step_lines) + if expect.kind == "exactly" or expect.kind == "order": + num_matching_steps = lcs_len(expected_lines, step_lines) + # Inefficient, but not to the point that we care! + num_matching_steps_ignoring_order = lcs_len( + sorted(expected_lines), sorted(step_lines) + ) + + max_possible_correct_line_steps = len(expected_lines) + correct_line_steps = num_matching_steps + misordered_line_steps = num_matching_steps_ignoring_order - num_matching_steps + missing_lines = sum(1 for e in expected_line_set if e not in actual_line_set) + if expect.kind == "exactly": + incorrect_line_steps = total_line_steps - correct_line_steps + unexpected_lines = sum( + 1 for a in actual_line_set if a not in expected_line_set + ) + else: + # For `!step order` there are no "incorrect" or "unexpected" lines, since we explicitly ignore seen lines + # outside of the expected lines. + incorrect_line_steps = 0 + unexpected_lines = 0 + else: + assert expect.kind == "never" + max_possible_correct_line_steps = total_line_steps + correct_line_steps = sum( + 1 for line in step_lines if line not in expected_line_set + ) + incorrect_line_steps = total_line_steps - correct_line_steps + unexpected_lines = sum(1 for a in actual_line_set if a in expected_line_set) + # For `!step never` there are no "missing" or "misordered" lines, since we only declare lines we *don't* want to + # see. + missing_lines = 0 + misordered_line_steps = 0 + + metrics: Dict[str, Metric] = { + "total_line_steps": ScalarMetric(total_line_steps), + "correct_line_steps": ScalarMetric(correct_line_steps), + "correct_line_score": FractionMetric( + correct_line_steps, max_possible_correct_line_steps + ), + "misordered_line_steps": ScalarMetric( + misordered_line_steps, improves_asc=False + ), + "missing_lines": ScalarMetric(missing_lines, improves_asc=False), + "incorrect_line_steps": ScalarMetric(incorrect_line_steps, improves_asc=False), + "unexpected_lines": ScalarMetric(unexpected_lines, improves_asc=False), + } + + return metrics diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/RunMatch.py b/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/RunMatch.py index 75f6e6fa81a0b..e4cf117110e37 100644 --- a/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/RunMatch.py +++ b/cross-project-tests/debuginfo-tests/dexter/dex/evaluation/RunMatch.py @@ -11,7 +11,7 @@ # aggregated, and each individual metric can be expressed in a scalar form that is considered "better" as it either # ascends or descends. from collections import defaultdict -from typing import Any, Dict, List, Tuple +from typing import Any, Dict, List, Optional, Tuple from dex.dextIR import DextIR, StepIR from dex.evaluation.ExpectMatch import ( @@ -22,12 +22,13 @@ ) from dex.evaluation.Metrics import ( Metric, + get_step_metrics, get_variable_metrics, serialize_metric_to_json, ) from dex.evaluation.StateMatch import StateMatchContext, get_active_where_matches from dex.test_script import DexterScript, Scope -from dex.test_script.Nodes import Expect, Value +from dex.test_script.Nodes import Expect, Line, Step, Value class DebuggerStepMatch: """Class used to record the match between a DexterScript and a StepIR, including the state match, determining which @@ -50,18 +51,25 @@ def __init__( for where_match in self.state_match.values() for expect in where_match.active_expects } - self.expect_matches: Dict[Expect, DebuggerExpectMatch] = {} + self.var_expect_matches: Dict[Expect, DebuggerExpectMatch] = {} + self.step_expect_matches: Dict[Step, int] = {} def add_expected_values(expect: Expect, expected_value: Any, scope: Scope): - assert isinstance(expect, Value), "Non-Value expects currently unsupported" - if expect in expects_to_match: - expect_frame_idx = expects_to_match[expect] - self.expect_matches[expect] = get_expect_match( - expect, - expected_value, - step.frames[expect_frame_idx].watches[expect.get_watched_expr()], - self.match_context, - ) + if expect not in expects_to_match: + return + expect_frame_idx = expects_to_match[expect] + if isinstance(expect, Step): + self.step_expect_matches[expect] = step.frames[ + expect_frame_idx + ].loc.lineno + return + assert isinstance(expect, Value), f"Unexpected expect node kind {expect}" + self.var_expect_matches[expect] = get_expect_match( + expect, + expected_value, + step.frames[expect_frame_idx].watches[expect.get_watched_expr()], + self.match_context, + ) script.visit_script(visit_expect=add_expected_values) @@ -79,20 +87,24 @@ def __init__(self, dex_context, dext_ir: DextIR): self.dext_ir = dext_ir self.metrics: Dict[str, Metric] = {} self.step_matches: List[DebuggerStepMatch] = [] - self.per_expect_results: Dict[ + self.per_var_expect_results: Dict[ Expect, list[Tuple[int, DebuggerExpectMatch]] ] = {} + self.per_step_expect_results: Dict[Step, list[Tuple[int, int]]] = {} script = self.dext_ir.script assert script is not None, "Trying to evaluate DextIR without attached script?" # Gather the expected values for each Expect. - expected_values = {} + self.expected_values = {} def add_expected_values(expect: Expect, expected_value: Any, scope: Scope): - assert isinstance(expect, Value), "Non-Value expects currently unsupported" - expected_values[expect] = expected_value - self.per_expect_results[expect] = [] + self.expected_values[expect] = expected_value + if isinstance(expect, Value): + self.per_var_expect_results[expect] = [] + return + assert isinstance(expect, Step), f"Unexpected expect node kind {expect}" + self.per_step_expect_results[expect] = [] script.visit_script(visit_expect=add_expected_values) @@ -105,16 +117,39 @@ def add_expected_values(expect: Expect, expected_value: Any, scope: Scope): # Then, for each expect, produce the list of results for just that variable. for step_match in self.step_matches: - for expect, expect_match in step_match.expect_matches.items(): - self.per_expect_results[expect].append( + for step_expect, line in step_match.step_expect_matches.items(): + self.per_step_expect_results[step_expect].append( + (step_match.step.step_index, line) + ) + for expect, expect_match in step_match.var_expect_matches.items(): + self.per_var_expect_results[expect].append( (step_match.step.step_index, expect_match) ) + # For !steps, once we know the file that they are in, we apply any labels. + for step_expect, step_results in self.per_step_expect_results.items(): + if not step_results: + # We may not be able to resolve any !labels in the expected value list if the expect was never active; + # as a workaround, just set any integers here - the result will be the same. + self.expected_values[step_expect] = [ + 0 for l in self.expected_values[step_expect] + ] + continue + active_path = self.dext_ir.steps[0].current_location.path + assert all( + self.dext_ir.steps[step_index].current_location.path == active_path + for step_index, line in step_results[1:] + ), "!step node unexpectedly active over multiple files" + path_labels = script.get_labels(active_path) + self.expected_values[step_expect] = [ + Line(l).to_line(path_labels) for l in self.expected_values[step_expect] + ] + # Finally, compare the match results against the expected values to produce the metrics. - for expect, expect_results in self.per_expect_results.items(): + for expect, expect_results in self.per_var_expect_results.items(): expect_matches = [match for step, match in expect_results] expect_metrics = get_variable_metrics( - expect, expected_values[expect], expect_matches + expect, self.expected_values[expect], expect_matches ) for metric_name, metric in expect_metrics.items(): if metric_name not in self.metrics: @@ -123,6 +158,18 @@ def add_expected_values(expect: Expect, expected_value: Any, scope: Scope): self.metrics[metric_name] = self.metrics[metric_name].aggregate( metric ) + for expect, lines in self.per_step_expect_results.items(): + actual_lines = [lines for step, lines in lines] + step_metrics = get_step_metrics( + expect, self.expected_values[expect], actual_lines + ) + for metric_name, metric in step_metrics.items(): + if metric_name not in self.metrics: + self.metrics[metric_name] = metric + else: + self.metrics[metric_name] = self.metrics[metric_name].aggregate( + metric + ) def dump_step_results(self) -> str: result = "" @@ -145,23 +192,42 @@ def dump_step_results(self) -> str: result += f" Active !where nodes:\n" for frame_idx, wheres in frame_active_wheres_list: result += f" Frame {frame_idx}: [{', '.join(wheres)}]\n" - if not step_match.expect_matches: + if not step_match.var_expect_matches and not step_match.step_expect_matches: continue result += f" Active !expect nodes:\n" matching_expects = [ - (expect, match) - for expect, match in step_match.expect_matches.items() + (expect, match.short_str()) + for expect, match in step_match.var_expect_matches.items() if match.match_result == MatchResult.TRUE ] non_matching_expects = [ - (expect, match) - for expect, match in step_match.expect_matches.items() + (expect, match.short_str()) + for expect, match in step_match.var_expect_matches.items() if match.match_result != MatchResult.TRUE ] + + def step_expect_matches(expect: Step, step_line: int) -> bool: + expected_lines = self.expected_values[expect] + assert isinstance(expected_lines, list) and all( + isinstance(l, int) for l in expected_lines + ) + step_line_in_expected_list = step_line in expected_lines + if expect.kind == "never": + print(f"never line hit: {step_line_in_expected_list}") + return not step_line_in_expected_list + return step_line_in_expected_list + + for step_expect, step_line in step_match.step_expect_matches.items(): + list_to_append = ( + matching_expects + if step_expect_matches(step_expect, step_line) + else non_matching_expects + ) + list_to_append.append((step_expect, str(step_line))) if matching_expects: - result += f" Matching nodes: [{', '.join(f'{expect}={match.short_str()}' for expect, match in matching_expects)}]\n" + result += f" Matching nodes: [{', '.join(f'{expect}={match}' for expect, match in matching_expects)}]\n" if non_matching_expects: - result += f" Non-matching nodes: [{', '.join(f'{expect}={match.short_str()}' for expect, match in non_matching_expects)}]\n" + result += f" Non-matching nodes: [{', '.join(f'{expect}={match}' for expect, match in non_matching_expects)}]\n" return result def get_metric_output(self): diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Nodes.py b/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Nodes.py index a3126357d8395..24370be5df7f0 100644 --- a/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Nodes.py +++ b/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Nodes.py @@ -18,7 +18,7 @@ def setup_yaml_parser(loader): - reg_classes = [Where, Value, DexRange, Label, Then, Address, ValueAll] + reg_classes = [Where, Value, DexRange, Label, Then, Address, ValueAll, Step] for c in reg_classes: c.register_yaml(loader) @@ -231,6 +231,37 @@ def register_yaml(loader): yaml.add_representer(ValueAll, ValueAll.representer) +class Step(Expect): + """Sets an expectation for stepping behaviour, with the expected value being a list of integer lines: + - !step exactly: while this !expect is active, we expect see exactly the expected lines in-order as many times as + they appear in the expected lines list. + - !step order: while this !expect is active, we expect to see each of the expected lines in-order at least as many + times as they appear in the expected list, ignoring excess lines and lines not in the expected lines list. + - !step never: while this !expect is active, we expect to not see any of the lines in the expected lines list. + """ + + def __init__(self, kind: str): + self.kind = kind + if kind not in ["exactly", "order", "never"]: + raise DexterNodeError(self, f'invalid !step kind "{self.kind}"') + + def __repr__(self): + return f"Step({self.kind})" + + @staticmethod + def constructor(loader: yaml.Loader, node): + return Step(loader.construct_scalar(node)) + + @staticmethod + def representer(dumper, data): + return dumper.represent_scalar("!step", data.kind) + + @staticmethod + def register_yaml(loader): + yaml.add_constructor("!step", Step.constructor, loader) + yaml.add_representer(Step, Step.representer) + + ############## ## Execution Nodes: Can appear as leaf nodes directly under a state node to perform debugger actions when they become ## active, to advance the debugger state. diff --git a/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Script.py b/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Script.py index f1d430ea8cf43..5546d46527cb9 100644 --- a/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Script.py +++ b/cross-project-tests/debuginfo-tests/dexter/dex/test_script/Script.py @@ -19,9 +19,11 @@ from dex.test_script.Nodes import ( Expect, FileLabels, + Label, Where, Then, ValueAll, + Step, setup_yaml_parser, ) @@ -186,6 +188,16 @@ def validate_expect(expect: Expect, expected_value, scope: Scope): raise DexterScriptError( f"!expect/all node {expect} should not have an expected value." ) + if isinstance(expect, Step): + if expected_value is None: + raise DexterScriptError(f"rewriting !step nodes not yet supported.") + if not ( + isinstance(expected_value, list) + and all(isinstance(l, (int, Label)) for l in expected_value) + ): + raise DexterScriptError( + f"Expected value for !step node {expect} must be list of integers" + ) def validate_where(where: Where, scope: Scope): if where.is_and and not scope.where: diff --git a/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_penalties.cpp b/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_penalties.cpp new file mode 100644 index 0000000000000..233aa4bfc872b --- /dev/null +++ b/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_penalties.cpp @@ -0,0 +1,69 @@ +// RUN: %dexter_regression_test_cxx_build %s -o %t +// RUN: %dexter_regression_test_run --use-script --binary %t -- %s \ +// RUN: | FileCheck %s + +// Test evaluation of !step nodes in Dexter. + +// CHECK: total_line_steps: 15 +// CHECK: correct_line_steps: 11 +// CHECK: correct_line_score: 73.3% (11/15) +// CHECK: misordered_line_steps: 2 +// CHECK: missing_lines: 1 +// CHECK: incorrect_line_steps: 2 +// CHECK: unexpected_lines: 2 + +// We want some janky formatting for the sake of this test. +// clang-format off +int doublify(int N) { return N * 2; } + +int stepBackwards(int N) { + return doublify( // !dex_label rbegin + doublify( + doublify(N))); // !dex_label rend +} + +void reportError() {} + +void pleasePassTrue(bool ShouldDefinitelyBeTrue = true) { + if (!ShouldDefinitelyBeTrue) // !dex_label error_check + reportError(); +} + +int factorial(int N) { + int Result = 1; // !dex_label fac_start + for (int I = N; I-- > 0;) { + Result *= I; + } + if (Result > 0) + return Result; + return 0; // !dex_label fac_end +} + +int main() { + stepBackwards(10); + pleasePassTrue(false); + factorial(3); + return 0; +} +// clang-format on + +/* +--- +!where {lines: !range [!label rbegin, !label rend]}: + # Actual stepping order is reversed. + # 3 steps, 1/3 correct, 2 misordered. + !step order: [!label rbegin, !label rbegin + 1, !label rbegin + 2] +!where {lines: !range [!label error_check, !label error_check + 1]}: + # "Never" line is stepped on. + # 2 steps, 1/2 correct, 1 incorrect, 1 unexpected + !step never: [!label error_check + 1] +!where {lines: !range [!label fac_start, !label fac_end]}: + # Loop iterates 4 times instead of 3, and exits on line 39 instead of 38. + # 10 steps, 9/10 correct, 1 incorrect, 1 unexpected, 1 missing + !step exactly: [!label fac_start, + !label fac_start + 1, !label fac_start + 2, + !label fac_start + 1, !label fac_start + 2, + !label fac_start + 1, !label fac_start + 2, + !label fac_start + 1, !label fac_start + 4, !label fac_start + 5] +... +*/ diff --git a/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_perfect.cpp b/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_perfect.cpp new file mode 100644 index 0000000000000..2848ae1635104 --- /dev/null +++ b/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/evaluation/eval_steps_perfect.cpp @@ -0,0 +1,46 @@ +// RUN: %dexter_regression_test_cxx_build %s -o %t +// RUN: %dexter_regression_test_run --use-script --binary %t -- %s \ +// RUN: | FileCheck %s + +// Test evaluation of !step nodes in Dexter. + +// CHECK: total_line_steps: 150 +// CHECK: correct_line_steps: 105 +// CHECK: correct_line_score: 100.0% (105/105) +// CHECK: misordered_line_steps: 0 +// CHECK: missing_lines: 0 +// CHECK: incorrect_line_steps: 0 +// CHECK: unexpected_lines: 0 + +void fizz() {} +void buzz() {} +void fizzbuzz() {} + +void doFizzbuzz(int N) { + for (int I = 1; I <= N; ++I) { + if (I % 3 == 0) { + if (I % 5 == 0) + fizzbuzz(); + else + fizz(); + } else if (I % 5 == 0) { + buzz(); + } + } +} + +int main() { + doFizzbuzz(10); + return 0; +} + +/* +--- +!where {function: doFizzbuzz}: + !step exactly: [20, 21, 26, 29, 20, 21, 26, 29, 20, 21, 22, 25, 26, 29, 20, + 21, 26, 29, 20, 21, 26, 27, 29, 20, 21, 22, 25, 26, 29, 20, 21, 26, 29, 20, + 21, 26, 29, 20, 21, 22, 25, 26, 29, 20, 21, 26, 27, 29, 20, 30] + !step order: [25, 27, 25, 25, 27] + !step never: [23] +... +*/ diff --git a/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/parser/step-node-expected-values.test b/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/parser/step-node-expected-values.test new file mode 100644 index 0000000000000..b98d4f2767dcc --- /dev/null +++ b/cross-project-tests/debuginfo-tests/dexter/feature_tests/scripts/parser/step-node-expected-values.test @@ -0,0 +1,19 @@ +RUN: not %dexter_regression_test_run --binary %s --use-script --skip-run -- %s 2>&1 | FileCheck %s + +Tests that !step expected values must not be anything other than a list of integers. + +CHECK: No valid Dexter script found in file + +CHECK: Script starting line [[# @LINE + 2]]: +CHECK: Expected value for !step node Step(order) must be list of integers +--- +!where {function: foo}: + !step order: 12 +... + +CHECK: Script starting line [[# @LINE + 2]]: +CHECK: Expected value for !step node Step(order) must be list of integers +--- +!where {function: foo}: + !step order: ["0", "1"] +... _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
