Skip to content

Commit d807b1e

Browse files
authored
Merge pull request #2419 from Fieldnote-Echo/perf/py-lexical-ancestor-kind
perf(python): climb the walk cursor for scope-directive and default checks
2 parents 3be5a02 + 72ab1ce commit d807b1e

3 files changed

Lines changed: 155 additions & 16 deletions

File tree

‎internal/cbm/extract_usages.c‎

Lines changed: 57 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1789,9 +1789,25 @@ static uint32_t active_lexical_scope_id(const WalkState *state) {
17891789
static uint32_t lexical_ancestor_of_kind(const WalkState *state, uint32_t start_id,
17901790
bool want_function, bool want_block);
17911791

1792-
static bool python_default_value_reference(TSNode node) {
1793-
for (TSNode parent = ts_node_parent(node); !ts_node_is_null(parent);
1794-
parent = ts_node_parent(parent)) {
1792+
/* One step up: on the occurrence cursor when there is one, else with
1793+
* ts_node_parent, which descends from the ROOT, so a climb costs O(depth^2). */
1794+
static TSNode usage_parent_step(TSTreeCursor *cursor, TSNode current) {
1795+
if (cursor) {
1796+
return ts_tree_cursor_goto_parent(cursor) ? ts_tree_cursor_current_node(cursor)
1797+
: (TSNode){0};
1798+
}
1799+
usage_slow_parent_fallback_test_note();
1800+
return ts_node_parent(current);
1801+
}
1802+
1803+
/* Asked for every Python usage, and a deep expression puts O(depth) parents
1804+
* above each one. A tree without errors climbs them on the walk cursor, like
1805+
* python_scope_directive_kind; a tree with errors keeps ts_node_parent. */
1806+
static bool python_default_value_reference(CBMExtractCtx *ctx, WalkState *state, TSNode node) {
1807+
TSTreeCursor *cursor =
1808+
ts_node_has_error(ctx->root) ? NULL : reset_occurrence_cursor(state, node);
1809+
for (TSNode parent = usage_parent_step(cursor, node); !ts_node_is_null(parent);
1810+
parent = usage_parent_step(cursor, parent)) {
17951811
const char *kind = ts_node_type(parent);
17961812
/* A nested executable scope inside the default owns its own lookups;
17971813
* only a direct default expression is evaluated in the declaring
@@ -1812,10 +1828,10 @@ static bool python_default_value_reference(TSNode node) {
18121828
return false;
18131829
}
18141830

1815-
static uint32_t usage_lexical_scope_id_for_node(CBMExtractCtx *ctx, const WalkState *state,
1816-
TSNode node) {
1831+
static uint32_t usage_lexical_scope_id_for_node(CBMExtractCtx *ctx, WalkState *state, TSNode node) {
18171832
uint32_t scope_id = active_lexical_scope_id(state);
1818-
if (!ctx || ctx->language != CBM_LANG_PYTHON || !python_default_value_reference(node)) {
1833+
if (!ctx || ctx->language != CBM_LANG_PYTHON ||
1834+
!python_default_value_reference(ctx, state, node)) {
18191835
return scope_id;
18201836
}
18211837
uint32_t function_id = lexical_ancestor_of_kind(state, scope_id, true, false);
@@ -1891,15 +1907,43 @@ static bool ensure_lexical_binding_capacity(WalkState *state) {
18911907
}
18921908

18931909
static bool lexical_ancestor_kind(TSNode node, const char *kind) {
1894-
for (TSNode parent = ts_node_parent(node); !ts_node_is_null(parent);
1895-
parent = ts_node_parent(parent)) {
1910+
for (TSNode parent = usage_parent_step(NULL, node); !ts_node_is_null(parent);
1911+
parent = usage_parent_step(NULL, parent)) {
18961912
if (strcmp(ts_node_type(parent), kind) == 0) {
18971913
return true;
18981914
}
18991915
}
19001916
return false;
19011917
}
19021918

1919+
/* Is `node` a name listed by a Python global/nonlocal statement? The grammar
1920+
* makes those names direct children of the statement, so in a tree without
1921+
* errors one parent step on the walk cursor answers it. The full climb above
1922+
* steps with ts_node_parent, which descends from the ROOT each time: O(depth^2)
1923+
* per identifier, asked for every Python identifier, so one deep arithmetic
1924+
* expression went cubic. Error recovery can put a name under an ERROR child of
1925+
* the statement, so a tree with errors keeps the full climb. */
1926+
static CBMPythonDirectiveKind python_scope_directive_kind(CBMExtractCtx *ctx, WalkState *state,
1927+
TSNode node) {
1928+
if (ts_node_has_error(ctx->root)) {
1929+
if (lexical_ancestor_kind(node, "global_statement")) {
1930+
return CBM_PYTHON_DIRECTIVE_GLOBAL;
1931+
}
1932+
return lexical_ancestor_kind(node, "nonlocal_statement") ? CBM_PYTHON_DIRECTIVE_NONLOCAL
1933+
: 0;
1934+
}
1935+
TSNode parent;
1936+
const char *field;
1937+
if (!occurrence_parent(reset_occurrence_cursor(state, node), node, &parent, &field)) {
1938+
return 0;
1939+
}
1940+
const char *kind = ts_node_type(parent);
1941+
if (strcmp(kind, "global_statement") == 0) {
1942+
return CBM_PYTHON_DIRECTIVE_GLOBAL;
1943+
}
1944+
return strcmp(kind, "nonlocal_statement") == 0 ? CBM_PYTHON_DIRECTIVE_NONLOCAL : 0;
1945+
}
1946+
19031947
static TSNode declared_function_name_owner(TSNode node, const CBMLangSpec *spec) {
19041948
for (TSNode parent = ts_node_parent(node); !ts_node_is_null(parent);
19051949
parent = ts_node_parent(parent)) {
@@ -2246,13 +2290,11 @@ static void record_lexical_binding(CBMExtractCtx *ctx, WalkState *state, TSNode
22462290
TSNode function_declaration = declared_function_name_owner(node, spec);
22472291
TSNode class_declaration = declared_class_name_owner(node, spec);
22482292

2249-
if (ctx->language == CBM_LANG_PYTHON && (lexical_ancestor_kind(node, "global_statement") ||
2250-
lexical_ancestor_kind(node, "nonlocal_statement"))) {
2293+
CBMPythonDirectiveKind scope_directive =
2294+
ctx->language == CBM_LANG_PYTHON ? python_scope_directive_kind(ctx, state, node) : 0;
2295+
if (scope_directive) {
22512296
uint32_t function_id = lexical_ancestor_of_kind(state, current_id, true, false);
2252-
CBMPythonDirectiveKind directive = lexical_ancestor_kind(node, "global_statement")
2253-
? CBM_PYTHON_DIRECTIVE_GLOBAL
2254-
: CBM_PYTHON_DIRECTIVE_NONLOCAL;
2255-
record_python_directive(state, function_id, name, directive);
2297+
record_python_directive(state, function_id, name, scope_directive);
22562298
return;
22572299
}
22582300

@@ -2719,8 +2761,7 @@ void handle_usages(CBMExtractCtx *ctx, TSNode node, const CBMLangSpec *spec, Wal
27192761
}
27202762

27212763
bool python_scope_directive =
2722-
ctx->language == CBM_LANG_PYTHON && (lexical_ancestor_kind(node, "global_statement") ||
2723-
lexical_ancestor_kind(node, "nonlocal_statement"));
2764+
ctx->language == CBM_LANG_PYTHON && python_scope_directive_kind(ctx, state, node) != 0;
27242765
if (python_scope_directive || is_binding_occurrence(ctx, node, spec, state)) {
27252766
char *binding_name = reference_name(ctx, node);
27262767
if (binding_name && binding_name[0] && !cbm_is_keyword(binding_name, ctx->language)) {

‎tests/repro/repro_lexical_binding_precision.c‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -963,6 +963,59 @@ TEST(repro_python_global_assignment_is_module_binding) {
963963
PASS();
964964
}
965965

966+
/* A global/nonlocal name is a directive, not a read (each name of `global a,
967+
* b`), and the rebinding lands where it says: the module from that point on,
968+
* or the enclosing function. Source 1 is an error tree, whose directive and
969+
* default-value checks take the ts_node_parent fallback. */
970+
TEST(repro_python_scope_directives_bind_the_named_scope) {
971+
static const char *const sources[] = {
972+
"def handler():\n pass\n"
973+
"def outer():\n handler = None\n"
974+
" def inner():\n nonlocal handler\n handler = outer\n"
975+
"def early():\n accept_early(handler)\n"
976+
"def caller():\n def nested():\n global handler, other\n"
977+
" handler = outer\n accept_outer(handler)\n"
978+
"def sibling():\n accept_sibling(handler)\n",
979+
"def handler():\n pass\n"
980+
"def make(handler=handler):\n return handler\n"
981+
"def caller():\n global handler other\n handler = make\n make(handler)\n",
982+
};
983+
static const struct {
984+
int source;
985+
const char *marker, *name;
986+
int count, blocked, shadow;
987+
} sites[] = {
988+
{0, "global handler", "handler", 0, 0, 0},
989+
{0, ", other", "other", 0, 0, 0},
990+
{0, "nonlocal handler", "handler", 0, 0, 0},
991+
{0, "accept_early(handler)", "handler", 1, 0, 0},
992+
{0, "accept_outer(handler)", "handler", 1, 1, 0},
993+
{0, "accept_sibling(handler)", "handler", 1, 1, 0},
994+
{1, "global handler", "handler", 0, 0, 0},
995+
{1, "=handler", "handler", 1, 0, 0},
996+
{1, "make(handler)", "handler", 1, 1, 0},
997+
};
998+
int failures = 0;
999+
for (int i = 0; i < (int)(sizeof(sites) / sizeof(sites[0])); i++) {
1000+
const char *source = sources[sites[i].source];
1001+
uint32_t start = lb_identifier_offset(source, sites[i].marker, sites[i].name);
1002+
ASSERT_NEQ(start, UINT32_MAX);
1003+
CBMFileResult *result = lb_extract(source, CBM_LANG_PYTHON, "directives.py");
1004+
ASSERT_NOT_NULL(result);
1005+
ASSERT_EQ(result->parse_incomplete, sites[i].source);
1006+
LBBindingSite got = lb_binding_site(result, NULL, sites[i].name, start);
1007+
cbm_free_result(result);
1008+
if (got.count != sites[i].count || got.blocked_count != sites[i].blocked ||
1009+
got.local_shadow_count != sites[i].shadow) {
1010+
printf(" %s: count %d blocked %d shadow %d\n", sites[i].marker, got.count,
1011+
got.blocked_count, got.local_shadow_count);
1012+
failures++;
1013+
}
1014+
}
1015+
ASSERT_EQ(failures, 0);
1016+
PASS();
1017+
}
1018+
9661019
/* Module assignments participate in name lookup too. A later function must
9671020
* not raw-name-fallback through a module variable to an older same-named
9681021
* callable declaration. */
@@ -1055,6 +1108,7 @@ SUITE(repro_lexical_binding_precision) {
10551108
RUN_TEST(repro_objectscript_udl_set_target_binds_method_local);
10561109
RUN_TEST(repro_python_default_expression_uses_enclosing_namespace);
10571110
RUN_TEST(repro_python_global_assignment_is_module_binding);
1111+
RUN_TEST(repro_python_scope_directives_bind_the_named_scope);
10581112
RUN_TEST(repro_python_module_assignment_blocks_callable_fallback);
10591113
RUN_TEST(repro_go_function_literal_parameter_does_not_leak);
10601114
}

‎tests/test_extraction.c‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10933,6 +10933,49 @@ TEST(extract_rescript_let_bindings_use_the_walk_cursor) {
1093310933
ASSERT_EQ(big_fallbacks, 0);
1093410934
PASS();
1093510935
}
10936+
10937+
/* Every Python usage asks whether it is a global/nonlocal name and whether it
10938+
* sits in a parameter default. Both climbed with ts_node_parent, which
10939+
* descends from the ROOT: O(d^2) for a usage d deep, so one deep expression
10940+
* went cubic (2.2 s / 17 s / >90 s at 500/1000/2000 terms). Count every such
10941+
* root-descending step at N and 2N terms. */
10942+
TEST(extract_python_deep_default_parent_climbs_are_linear) {
10943+
enum { SMALL = 200 };
10944+
uint64_t slow_parents[2];
10945+
for (int round = 0; round < 2; round++) {
10946+
/* def f(x=x + x + ... + x): return x -- a binary_operator chain. */
10947+
int terms = SMALL << round;
10948+
size_t capacity = 32U + (size_t)terms * 4U;
10949+
char *source = malloc(capacity);
10950+
ASSERT_NOT_NULL(source);
10951+
int length = snprintf(source, capacity, "def f(x=x");
10952+
for (int i = 1; i < terms; i++) {
10953+
length += snprintf(source + length, capacity - (size_t)length, " + x");
10954+
}
10955+
length += snprintf(source + length, capacity - (size_t)length, "):\n return x\n");
10956+
cbm_usage_field_lookup_test_reset();
10957+
CBMFileResult *result =
10958+
cbm_extract_file(source, length, CBM_LANG_PYTHON, "proj", "deep.py", 0, NULL, NULL);
10959+
free(source);
10960+
ASSERT_NOT_NULL(result);
10961+
slow_parents[round] = cbm_usage_slow_parent_fallback_test_count();
10962+
/* Anti-vacuous: every default x climbed its chain to the parameter and
10963+
* reads the enclosing namespace; only `return x` is shadowed by it. */
10964+
int defaults = 0;
10965+
for (int i = 0; i < result->usages.count; i++) {
10966+
const CBMUsage *usage = &result->usages.items[i];
10967+
defaults += usage->ref_name && strcmp(usage->ref_name, "x") == 0 &&
10968+
!usage->semantic_reference_local_shadow;
10969+
}
10970+
cbm_free_result(result);
10971+
ASSERT_EQ(defaults, terms);
10972+
}
10973+
fprintf(stderr, " [python-deep-default] slow_parents(%d)=%llu slow_parents(%d)=%llu\n", SMALL,
10974+
(unsigned long long)slow_parents[0], 2 * SMALL, (unsigned long long)slow_parents[1]);
10975+
/* Twice the terms may cost about twice the steps; the cubic climb took 4x. */
10976+
ASSERT_LTE(slow_parents[1], slow_parents[0] * 3U + 64U);
10977+
PASS();
10978+
}
1093610979
#endif
1093710980

1093810981
/* ===================================================================
@@ -13455,6 +13498,7 @@ SUITE(extraction) {
1345513498
RUN_TEST(extract_wide_flat_reference_fields_are_linear);
1345613499
RUN_TEST(extract_csharp_argument_values_use_the_walk_cursor);
1345713500
RUN_TEST(extract_rescript_let_bindings_use_the_walk_cursor);
13501+
RUN_TEST(extract_python_deep_default_parent_climbs_are_linear);
1345813502
#endif
1345913503

1346013504
/* Perl call-graph noise (#459 follow-up) */

0 commit comments

Comments
 (0)