Skip to content

Commit 27c3303

Browse files
authored
Merge pull request #2697 from DeusData/fix/py-attr-c3-mro
fix(python-lsp): look attributes up along the C3 method resolution order
2 parents e6b47a3 + 1501cad commit 27c3303

3 files changed

Lines changed: 264 additions & 71 deletions

File tree

‎internal/cbm/lsp/py_lsp.c‎

Lines changed: 161 additions & 71 deletions
Original file line numberDiff line numberDiff line change
@@ -1224,25 +1224,85 @@ static const CBMRegisteredFunc *py_lookup_attribute_depth(PyLSPContext *ctx, con
12241224
return NULL;
12251225
}
12261226

1227-
static const CBMRegisteredFunc *py_lookup_attribute(PyLSPContext *ctx, const char *type_qn,
1228-
const char *member_name) {
1229-
return py_lookup_attribute_depth(ctx, type_qn, member_name, 0);
1230-
}
1231-
1232-
/* ── super(): the C3 method resolution order ──────────────────────── */
1227+
/* ── The C3 method resolution order ──────────────────────────────── */
12331228

12341229
/* Longest linearization followed. A longer one (or more bases than this) keeps
1235-
* the base-by-base walk of the caller. */
1230+
* the depth-first walk above. */
12361231
#define PY_C3_MAX 64
12371232

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;
1233+
enum { PY_MRO_CACHE_INITIAL_CAP = 64 }; /* power of two (index masking) */
1234+
enum { PY_MRO_CACHE_MAX_CAP = 1 << 20 }; /* hard stop for adversarial files */
1235+
1236+
static uint32_t py_mro_hash(const char *qn) {
1237+
uint32_t h = 2166136261u; /* FNV-1a */
1238+
for (const unsigned char *p = (const unsigned char *)qn; *p; p++) {
1239+
h = (h ^ *p) * 16777619u;
1240+
}
1241+
return h;
1242+
}
1243+
1244+
static const CBMPyMroCacheEntry *py_mro_cache_find(const PyLSPContext *ctx, const char *qn,
1245+
uint32_t h) {
1246+
if (!ctx->mro_cache || ctx->mro_cache_cap == 0)
1247+
return NULL;
1248+
uint32_t mask = (uint32_t)ctx->mro_cache_cap - 1;
1249+
uint32_t idx = h & mask;
1250+
for (int probed = 0; probed < ctx->mro_cache_cap; probed++) {
1251+
const CBMPyMroCacheEntry *e = &ctx->mro_cache[idx];
1252+
if (!e->qn)
1253+
return NULL;
1254+
if (e->hash == h && strcmp(e->qn, qn) == 0)
1255+
return e;
1256+
idx = (idx + 1) & mask;
1257+
}
1258+
return NULL;
1259+
}
1260+
1261+
/* Doubles the table (arena allocation: the old table is freed with the
1262+
* per-file arena). */
1263+
static bool py_mro_cache_grow(PyLSPContext *ctx) {
1264+
if (ctx->mro_cache_cap >= PY_MRO_CACHE_MAX_CAP)
1265+
return false;
1266+
int new_cap = ctx->mro_cache_cap ? ctx->mro_cache_cap * 2 : PY_MRO_CACHE_INITIAL_CAP;
1267+
CBMPyMroCacheEntry *entries = (CBMPyMroCacheEntry *)cbm_arena_alloc(
1268+
ctx->arena, (size_t)new_cap * sizeof(CBMPyMroCacheEntry));
1269+
if (!entries)
1270+
return false;
1271+
memset(entries, 0, (size_t)new_cap * sizeof(CBMPyMroCacheEntry));
1272+
uint32_t mask = (uint32_t)new_cap - 1;
1273+
for (int i = 0; i < ctx->mro_cache_cap; i++) {
1274+
const CBMPyMroCacheEntry *e = &ctx->mro_cache[i];
1275+
if (!e->qn)
1276+
continue;
1277+
uint32_t idx = e->hash & mask;
1278+
while (entries[idx].qn)
1279+
idx = (idx + 1) & mask;
1280+
entries[idx] = *e;
1281+
}
1282+
ctx->mro_cache = entries;
1283+
ctx->mro_cache_cap = new_cap;
1284+
return true;
1285+
}
1286+
1287+
/* Records the order of `qn` (len -1: none). A table that cannot grow only
1288+
* costs a recomputation later. */
1289+
static void py_mro_cache_put(PyLSPContext *ctx, const char *qn, uint32_t h, const char **mro,
1290+
int len) {
1291+
if ((ctx->mro_cache_count + 1) * 4 > ctx->mro_cache_cap * 3 && !py_mro_cache_grow(ctx))
1292+
return;
1293+
const char *key = cbm_arena_strdup(ctx->arena, qn);
1294+
if (!key)
1295+
return;
1296+
uint32_t mask = (uint32_t)ctx->mro_cache_cap - 1;
1297+
uint32_t idx = h & mask;
1298+
while (ctx->mro_cache[idx].qn)
1299+
idx = (idx + 1) & mask;
1300+
ctx->mro_cache[idx].qn = key;
1301+
ctx->mro_cache[idx].hash = h;
1302+
ctx->mro_cache[idx].len = len;
1303+
ctx->mro_cache[idx].mro = mro;
1304+
ctx->mro_cache_count++;
1305+
}
12461306

12471307
static bool py_c3_in_tail(const char *qn, const char *const *seq, int head, int len) {
12481308
for (int k = head + 1; k < len; k++) {
@@ -1270,74 +1330,106 @@ static const char *py_c3_pick(const char **const *seqs, const int *lens, const i
12701330
return NULL;
12711331
}
12721332

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;
1333+
/* The C3 merge of `nseq` sequences into mro[1..]: returns the order's length,
1334+
* or -1 when there is none or it is longer than PY_C3_MAX. */
1335+
static int py_c3_merge(const char **const *seqs, const int *lens, int *heads, int nseq,
1336+
const char **mro) {
1337+
int n = 1;
13151338
for (;;) {
13161339
bool pending = false;
1317-
for (int s = 0; s <= nb && !pending; s++) {
1340+
for (int s = 0; s < nseq && !pending; s++) {
13181341
pending = heads[s] < lens[s];
13191342
}
13201343
if (!pending)
1321-
break;
1322-
const char *pick = py_c3_pick((const char **const *)seqs, lens, heads, nb + 1);
1344+
return n;
1345+
const char *pick = py_c3_pick(seqs, lens, heads, nseq);
13231346
if (!pick || n >= PY_C3_MAX)
13241347
return -1;
13251348
mro[n++] = pick;
1326-
for (int s = 0; s <= nb; s++) {
1349+
for (int s = 0; s < nseq; s++) {
13271350
if (heads[s] < lens[s] && strcmp(seqs[s][heads[s]], pick) == 0)
13281351
heads[s]++;
13291352
}
13301353
}
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;
1354+
}
1355+
1356+
/* Python's method resolution order of `type_qn`: the class, then the C3 merge
1357+
* of its bases' linearizations and of the base list. A common base therefore
1358+
* follows every class deriving from it. Computed once per class and file
1359+
* (ctx->mro_cache). Sets *out to an arena array and returns its length, or -1
1360+
* when there is no C3 order, the hierarchy is deeper than
1361+
* CBM_LSP_MAX_LOOKUP_DEPTH, or the order is longer than PY_C3_MAX. A base the
1362+
* registry does not know (external, unresolved) linearizes to itself. Only an
1363+
* order computed from the top (depth 0) is cached as missing: below it, the
1364+
* depth cap may have cut a hierarchy that is fine on its own. */
1365+
static int py_c3_linearize(PyLSPContext *ctx, const char *type_qn, const char ***out, int depth) {
1366+
uint32_t h = py_mro_hash(type_qn);
1367+
const CBMPyMroCacheEntry *hit = py_mro_cache_find(ctx, type_qn, h);
1368+
if (hit) {
1369+
*out = hit->mro;
1370+
return hit->len;
1371+
}
1372+
int n = -1;
1373+
const char **mro = NULL;
1374+
const CBMRegisteredType *rt =
1375+
depth <= CBM_LSP_MAX_LOOKUP_DEPTH ? cbm_registry_lookup_type(ctx->registry, type_qn) : NULL;
1376+
const char **bases = rt ? rt->embedded_types : NULL;
1377+
int nb = 0;
1378+
while (bases && bases[nb])
1379+
nb++;
1380+
if (depth > CBM_LSP_MAX_LOOKUP_DEPTH || nb >= PY_C3_MAX) {
1381+
n = -1;
1382+
} else if (rt && rt->alias_of) {
1383+
n = py_c3_linearize(ctx, rt->alias_of, &mro, depth + 1);
1384+
} else {
1385+
const char ***seqs =
1386+
(const char ***)cbm_arena_alloc(ctx->arena, (size_t)(nb + 1) * sizeof(const char **));
1387+
int *lens = (int *)cbm_arena_alloc(ctx->arena, (size_t)(nb + 1) * 2 * sizeof(int));
1388+
mro = (const char **)cbm_arena_alloc(ctx->arena, PY_C3_MAX * sizeof(const char *));
1389+
bool ok = seqs && lens && mro;
1390+
int *heads = lens ? lens + nb + 1 : NULL;
1391+
for (int b = 0; ok && b < nb; b++) {
1392+
lens[b] = py_c3_linearize(ctx, bases[b], &seqs[b], depth + 1);
1393+
heads[b] = 0;
1394+
ok = lens[b] >= 0;
1395+
}
1396+
if (ok) {
1397+
seqs[nb] = bases;
1398+
lens[nb] = nb;
1399+
heads[nb] = 0;
1400+
mro[0] = cbm_arena_strdup(ctx->arena, type_qn);
1401+
n = mro[0] ? py_c3_merge((const char **const *)seqs, lens, heads, nb + 1, mro) : -1;
1402+
}
1403+
}
1404+
if (n >= 0 || depth == 0)
1405+
py_mro_cache_put(ctx, type_qn, h, n >= 0 ? mro : NULL, n);
1406+
*out = n >= 0 ? mro : NULL;
13381407
return n;
13391408
}
13401409

1410+
/* Attribute lookup along the class's C3 order: the class itself, then each
1411+
* class of its order that declares the member. A hierarchy without a C3 order
1412+
* keeps the depth-first walk. */
1413+
static const CBMRegisteredFunc *py_lookup_attribute(PyLSPContext *ctx, const char *type_qn,
1414+
const char *member_name) {
1415+
if (!ctx || !type_qn || !member_name)
1416+
return NULL;
1417+
const CBMRegisteredFunc *f = cbm_registry_lookup_method(ctx->registry, type_qn, member_name);
1418+
if (f)
1419+
return f;
1420+
const char **mro = NULL;
1421+
int n = py_c3_linearize(ctx, type_qn, &mro, 0);
1422+
if (n < 0)
1423+
return py_lookup_attribute_depth(ctx, type_qn, member_name, 0);
1424+
/* mro[0] is the class itself, already asked, or an alias's target. */
1425+
for (int i = strcmp(mro[0], type_qn) == 0 ? 1 : 0; i < n; i++) {
1426+
f = cbm_registry_lookup_method(ctx->registry, mro[i], member_name);
1427+
if (f)
1428+
return f;
1429+
}
1430+
return NULL;
1431+
}
1432+
13411433
/* The method super() reaches from inside `class_qn`: the first class AFTER it in
13421434
* its C3 order that declares `member` itself. *have_mro is false when the
13431435
* hierarchy has no C3 order; the caller then keeps its base-by-base walk. */
@@ -1346,10 +1438,8 @@ static const CBMRegisteredFunc *py_lookup_super_attribute(PyLSPContext *ctx, con
13461438
*have_mro = false;
13471439
if (!ctx || !class_qn || !member)
13481440
return NULL;
1349-
py_c3_cache_t cache;
1350-
cache.count = 0;
13511441
const char **mro = NULL;
1352-
int n = py_c3_linearize(ctx, &cache, class_qn, &mro, 0);
1442+
int n = py_c3_linearize(ctx, class_qn, &mro, 0);
13531443
if (n < 0)
13541444
return NULL;
13551445
*have_mro = true;

‎internal/cbm/lsp/py_lsp.h‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,16 @@ typedef struct {
3838
const CBMType *result; // full-fidelity result, never NULL in a live entry
3939
} CBMPyTypeCacheEntry;
4040

41+
// A class's C3 method resolution order (py_c3_linearize), computed once per
42+
// class and file. The registry is complete before the walk starts, so an entry
43+
// never goes stale.
44+
typedef struct {
45+
const char *qn; // class QN; NULL marks an empty slot
46+
uint32_t hash; // hash of qn
47+
int len; // entries in mro; -1 = the class has no C3 order
48+
const char **mro; // arena-allocated, mro[0] is the class (or its alias target)
49+
} CBMPyMroCacheEntry;
50+
4151
// PyLSPContext holds state for one Python file's type evaluation.
4252
typedef struct {
4353
CBMArena *arena;
@@ -113,6 +123,11 @@ typedef struct {
113123
int eval_depth; // evaluator recursion depth (PY_LSP_MAX_EVAL_DEPTH)
114124
uint32_t eval_truncations; // depth-cap cutoff count — gates memo inserts
115125
CBMLSPStatus eval_failure; // sticky: explicit failure makes this walk incomplete
126+
// C3 orders of the classes whose attributes this file looks up: one
127+
// linearization per class, open addressing, arena-allocated.
128+
CBMPyMroCacheEntry *mro_cache;
129+
int mro_cache_count; // occupied slots (kept < 75% of cap)
130+
int mro_cache_cap; // power-of-two capacity
116131
// Pending links of the left-associative chains being evaluated
117132
// iteratively (operator, receiver, subscript, conditional and
118133
// parenthesis chains): one stack shared by nested evaluations.

0 commit comments

Comments
 (0)