@@ -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
12471307static 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;
0 commit comments