Skip to content

Commit 5dc83ac

Browse files
authored
Merge pull request #2696 from DeusData/fix/py-super-c3-mro
fix(python-lsp): resolve super() through the C3 method resolution order
2 parents 658639e + 7fa5f89 commit 5dc83ac

2 files changed

Lines changed: 258 additions & 0 deletions

File tree

‎internal/cbm/lsp/py_lsp.c‎

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1229,6 +1229,138 @@ static const CBMRegisteredFunc *py_lookup_attribute(PyLSPContext *ctx, const cha
12291229
return py_lookup_attribute_depth(ctx, type_qn, member_name, 0);
12301230
}
12311231

1232+
/* ── super(): the C3 method resolution order ──────────────────────── */
1233+
1234+
/* Longest linearization followed. A longer one (or more bases than this) keeps
1235+
* the base-by-base walk of the caller. */
1236+
#define PY_C3_MAX 64
1237+
1238+
/* The linearizations computed during one super() lookup: every class of a
1239+
* diamond is linearized once, however many paths reach it. */
1240+
typedef struct {
1241+
const char *qn[PY_C3_MAX];
1242+
const char **mro[PY_C3_MAX];
1243+
int len[PY_C3_MAX];
1244+
int count;
1245+
} py_c3_cache_t;
1246+
1247+
static bool py_c3_in_tail(const char *qn, const char *const *seq, int head, int len) {
1248+
for (int k = head + 1; k < len; k++) {
1249+
if (strcmp(seq[k], qn) == 0)
1250+
return true;
1251+
}
1252+
return false;
1253+
}
1254+
1255+
/* The C3 head to take next: the first sequence head that is in no sequence's
1256+
* tail. NULL when every head is blocked (Python rejects such a class). */
1257+
static const char *py_c3_pick(const char **const *seqs, const int *lens, const int *heads,
1258+
int nseq) {
1259+
for (int s = 0; s < nseq; s++) {
1260+
if (heads[s] >= lens[s])
1261+
continue;
1262+
const char *cand = seqs[s][heads[s]];
1263+
bool blocked = false;
1264+
for (int t = 0; t < nseq && !blocked; t++) {
1265+
blocked = heads[t] < lens[t] && py_c3_in_tail(cand, seqs[t], heads[t], lens[t]);
1266+
}
1267+
if (!blocked)
1268+
return cand;
1269+
}
1270+
return NULL;
1271+
}
1272+
1273+
/* Python's method resolution order of `type_qn`: the class, then the C3 merge
1274+
* of its bases' linearizations and of the base list. A common base therefore
1275+
* follows every class deriving from it. Sets *out to an arena array and returns
1276+
* its length, or -1 when there is no C3 order, the hierarchy is deeper than
1277+
* CBM_LSP_MAX_LOOKUP_DEPTH, or the order is longer than PY_C3_MAX. A base the
1278+
* registry does not know (external, unresolved) linearizes to itself. */
1279+
static int py_c3_linearize(PyLSPContext *ctx, py_c3_cache_t *cache, const char *type_qn,
1280+
const char ***out, int depth) {
1281+
for (int c = 0; c < cache->count; c++) {
1282+
if (strcmp(cache->qn[c], type_qn) == 0) {
1283+
*out = cache->mro[c];
1284+
return cache->len[c];
1285+
}
1286+
}
1287+
if (depth > CBM_LSP_MAX_LOOKUP_DEPTH)
1288+
return -1;
1289+
const CBMRegisteredType *rt = cbm_registry_lookup_type(ctx->registry, type_qn);
1290+
if (rt && rt->alias_of)
1291+
return py_c3_linearize(ctx, cache, rt->alias_of, out, depth + 1);
1292+
const char **bases = rt ? rt->embedded_types : NULL;
1293+
int nb = 0;
1294+
while (bases && bases[nb])
1295+
nb++;
1296+
if (nb >= PY_C3_MAX)
1297+
return -1;
1298+
const char **seqs[PY_C3_MAX];
1299+
int lens[PY_C3_MAX];
1300+
int heads[PY_C3_MAX];
1301+
for (int b = 0; b < nb; b++) {
1302+
lens[b] = py_c3_linearize(ctx, cache, bases[b], &seqs[b], depth + 1);
1303+
if (lens[b] < 0)
1304+
return -1;
1305+
heads[b] = 0;
1306+
}
1307+
seqs[nb] = bases;
1308+
lens[nb] = nb;
1309+
heads[nb] = 0;
1310+
const char **mro = (const char **)cbm_arena_alloc(ctx->arena, PY_C3_MAX * sizeof(char *));
1311+
if (!mro)
1312+
return -1;
1313+
int n = 0;
1314+
mro[n++] = type_qn;
1315+
for (;;) {
1316+
bool pending = false;
1317+
for (int s = 0; s <= nb && !pending; s++) {
1318+
pending = heads[s] < lens[s];
1319+
}
1320+
if (!pending)
1321+
break;
1322+
const char *pick = py_c3_pick((const char **const *)seqs, lens, heads, nb + 1);
1323+
if (!pick || n >= PY_C3_MAX)
1324+
return -1;
1325+
mro[n++] = pick;
1326+
for (int s = 0; s <= nb; s++) {
1327+
if (heads[s] < lens[s] && strcmp(seqs[s][heads[s]], pick) == 0)
1328+
heads[s]++;
1329+
}
1330+
}
1331+
if (cache->count < PY_C3_MAX) {
1332+
cache->qn[cache->count] = type_qn;
1333+
cache->mro[cache->count] = mro;
1334+
cache->len[cache->count] = n;
1335+
cache->count++;
1336+
}
1337+
*out = mro;
1338+
return n;
1339+
}
1340+
1341+
/* The method super() reaches from inside `class_qn`: the first class AFTER it in
1342+
* its C3 order that declares `member` itself. *have_mro is false when the
1343+
* hierarchy has no C3 order; the caller then keeps its base-by-base walk. */
1344+
static const CBMRegisteredFunc *py_lookup_super_attribute(PyLSPContext *ctx, const char *class_qn,
1345+
const char *member, bool *have_mro) {
1346+
*have_mro = false;
1347+
if (!ctx || !class_qn || !member)
1348+
return NULL;
1349+
py_c3_cache_t cache;
1350+
cache.count = 0;
1351+
const char **mro = NULL;
1352+
int n = py_c3_linearize(ctx, &cache, class_qn, &mro, 0);
1353+
if (n < 0)
1354+
return NULL;
1355+
*have_mro = true;
1356+
for (int i = 1; i < n; i++) {
1357+
const CBMRegisteredFunc *f = cbm_registry_lookup_method(ctx->registry, mro[i], member);
1358+
if (f)
1359+
return f;
1360+
}
1361+
return NULL;
1362+
}
1363+
12321364
/* Per-file field overlay: look up a (class_qn, field_name) recorded during resolve
12331365
* against the sealed shared registry. Linear scan — the overlay only holds fields
12341366
* discovered in THIS file's own classes, so it is small. */
@@ -2964,6 +3096,22 @@ static void py_emit_call_for(PyLSPContext *ctx, TSNode call_node) {
29643096
const CBMRegisteredType *enclosing =
29653097
cbm_registry_lookup_type(ctx->registry, ctx->enclosing_class_qn);
29663098
if (enclosing && enclosing->embedded_types) {
3099+
// The proxy walks the enclosing class's C3 order, in which a
3100+
// diamond's shared base follows every class deriving from it:
3101+
// RadarrCalendarEntity(RadarrEntity, CalendarEntity) reaches
3102+
// CalendarEntity before Entity, which the first base reaches
3103+
// through its own ancestry. The base-by-base walk below stays for
3104+
// a hierarchy without a C3 order and for an undeclared __init__.
3105+
bool have_mro = false;
3106+
const CBMRegisteredFunc *sf = py_lookup_super_attribute(
3107+
ctx, ctx->enclosing_class_qn, attr_name, &have_mro);
3108+
if (sf) {
3109+
bool is_init = strcmp(attr_name, "__init__") == 0;
3110+
py_emit_resolved_call(ctx, sf->qualified_name,
3111+
is_init ? "lsp_super_init" : "lsp_super",
3112+
is_init ? 0.90f : 0.88f, call_node);
3113+
return;
3114+
}
29673115
for (int i = 0; enclosing->embedded_types[i]; i++) {
29683116
// super().__init__() is a constructor delegation:
29693117
// lsp_super_init is the MORE SPECIFIC, more accurate

‎tests/test_pipeline.c‎

Lines changed: 110 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15211,6 +15211,114 @@ TEST(pipeline_python_local_def_shadows_module_def_parallel_issue1548) {
1521115211
return pyn_run_shadowing(52);
1521215212
}
1521315213

15214+
/* ── super() follows the C3 method resolution order ──────────────── */
15215+
15216+
/* The home-assistant radarr shape: RadarrCalendarEntity(RadarrEntity,
15217+
* CalendarEntity), where RadarrEntity reaches the common base Entity through
15218+
* CoordinatorEntity and CalendarEntity overrides Entity's method. Python's C3
15219+
* order is [RadarrCalendarEntity, RadarrEntity, CoordinatorEntity,
15220+
* CalendarEntity, Entity]: a common base comes after every class that
15221+
* derives from it, so super() reaches CalendarEntity, not Entity through the
15222+
* first base's ancestry. */
15223+
static const char pym_base_py[] = "class Entity:\n"
15224+
" def __init__(self):\n"
15225+
" self.ready = False\n"
15226+
"\n"
15227+
" def write_state(self):\n"
15228+
" return 0\n"
15229+
"\n"
15230+
"class CoordinatorEntity(Entity):\n"
15231+
" pass\n"
15232+
"\n"
15233+
"class CalendarEntity(Entity):\n"
15234+
" def __init__(self):\n"
15235+
" self.events = []\n"
15236+
"\n"
15237+
" def write_state(self):\n"
15238+
" return 1\n";
15239+
15240+
static const char pym_radarr_py[] = "from base import CoordinatorEntity, CalendarEntity\n"
15241+
"\n"
15242+
"class RadarrEntity(CoordinatorEntity):\n"
15243+
" pass\n"
15244+
"\n"
15245+
"class RadarrCalendarEntity(RadarrEntity, CalendarEntity):\n"
15246+
" def __init__(self):\n"
15247+
" super().__init__()\n"
15248+
"\n"
15249+
" def write_state(self):\n"
15250+
" return super().write_state()\n"
15251+
"\n"
15252+
"class PlainCalendar(CalendarEntity):\n"
15253+
" def write_state(self):\n"
15254+
" return super().write_state()\n";
15255+
15256+
static int pym_run_super_c3(int fillers) {
15257+
char tmp[256];
15258+
snprintf(tmp, sizeof(tmp), "/tmp/cbm_py_superc3_XXXXXX");
15259+
if (!cbm_mkdtemp(tmp)) {
15260+
FAIL("tmpdir");
15261+
}
15262+
write_temp_file(tmp, "base.py", pym_base_py);
15263+
write_temp_file(tmp, "radarr.py", pym_radarr_py);
15264+
for (int i = 0; i < fillers; i++) {
15265+
char name[64];
15266+
char body[128];
15267+
snprintf(name, sizeof(name), "filler%d.py", i);
15268+
snprintf(body, sizeof(body), "def filler%d():\n return %d\n", i, i);
15269+
write_temp_file(tmp, name, body);
15270+
}
15271+
char *old_workers = getenv("CBM_WORKERS");
15272+
char *saved = old_workers ? strdup(old_workers) : NULL;
15273+
if (fillers > 0) {
15274+
cbm_setenv("CBM_WORKERS", "4", 1);
15275+
}
15276+
char db_path[512];
15277+
snprintf(db_path, sizeof(db_path), "%s/superc3.db", tmp);
15278+
cbm_pipeline_t *p = cbm_pipeline_new(tmp, db_path, CBM_MODE_FULL);
15279+
int rc = p ? cbm_pipeline_run(p) : -1;
15280+
cbm_store_t *s = rc == 0 ? cbm_store_open_path(db_path) : NULL;
15281+
const char *pr = p ? cbm_pipeline_project_name(p) : NULL;
15282+
const char *rce = "radarr.RadarrCalendarEntity";
15283+
char src[256];
15284+
snprintf(src, sizeof(src), "%s.write_state", rce);
15285+
bool m_c3 = s && pyn_edge(s, pr, src, "base.CalendarEntity.write_state", "CALLS");
15286+
bool m_dfs = s && pyn_edge(s, pr, src, "base.Entity.write_state", "CALLS");
15287+
snprintf(src, sizeof(src), "%s.__init__", rce);
15288+
bool i_c3 = s && pyn_edge(s, pr, src, "base.CalendarEntity.__init__", "CALLS");
15289+
bool i_dfs = s && pyn_edge(s, pr, src, "base.Entity.__init__", "CALLS");
15290+
bool plain = s && pyn_edge(s, pr, "radarr.PlainCalendar.write_state",
15291+
"base.CalendarEntity.write_state", "CALLS");
15292+
if (s) {
15293+
cbm_store_close(s);
15294+
}
15295+
if (p) {
15296+
cbm_pipeline_free(p);
15297+
}
15298+
if (saved) {
15299+
cbm_setenv("CBM_WORKERS", saved, 1);
15300+
free(saved);
15301+
} else {
15302+
cbm_unsetenv("CBM_WORKERS");
15303+
}
15304+
th_rmtree(tmp);
15305+
ASSERT_EQ(rc, 0);
15306+
ASSERT_TRUE(m_c3); /* super().write_state(): CalendarEntity comes before Entity */
15307+
ASSERT_FALSE(m_dfs); /* ... never Entity through RadarrEntity's ancestry */
15308+
ASSERT_TRUE(i_c3); /* super().__init__(): the same order */
15309+
ASSERT_FALSE(i_dfs);
15310+
ASSERT_TRUE(plain); /* control: single inheritance */
15311+
PASS();
15312+
}
15313+
15314+
TEST(pipeline_python_super_follows_c3_mro) {
15315+
return pym_run_super_c3(0);
15316+
}
15317+
15318+
TEST(pipeline_python_super_follows_c3_mro_parallel) {
15319+
return pym_run_super_c3(52);
15320+
}
15321+
1521415322
/* L7 review of #1548: a package __init__.py function can share a submodule's QN
1521515323
* (poetry: layouts/__init__.py `def layout` is the QN prefix of every symbol in
1521615324
* layouts/layout.py). The function-local detection is bounded at the symbol's
@@ -24914,6 +25022,8 @@ SUITE(pipeline) {
2491425022
RUN_TEST(pipeline_python_nested_def_local_after_incremental_issue1548);
2491525023
RUN_TEST(pipeline_python_local_def_shadows_module_def_issue1548);
2491625024
RUN_TEST(pipeline_python_local_def_shadows_module_def_parallel_issue1548);
25025+
RUN_TEST(pipeline_python_super_follows_c3_mro);
25026+
RUN_TEST(pipeline_python_super_follows_c3_mro_parallel);
2491725027
RUN_TEST(pipeline_python_init_function_shares_submodule_qn_issue1548);
2491825028
RUN_TEST(pipeline_python_init_function_shares_submodule_qn_parallel_issue1548);
2491925029
RUN_TEST(pipeline_python_nested_helper_keeps_tests_issue1548);

0 commit comments

Comments
 (0)