@@ -1268,11 +1268,6 @@ static const CBMRegisteredFunc *py_lookup_attribute_depth(PyLSPContext *ctx, con
12681268 return NULL ;
12691269}
12701270
1271- static const CBMRegisteredFunc * py_lookup_attribute (PyLSPContext * ctx , const char * type_qn ,
1272- const char * member_name ) {
1273- return py_lookup_attribute_depth (ctx , type_qn , member_name , 0 );
1274- }
1275-
12761271static PyModuleMember py_module_member_exact (PyLSPContext * ctx , const char * module_qn ,
12771272 const char * name ) {
12781273 PyModuleMember m = {0 };
@@ -1352,20 +1347,85 @@ static void py_emit_module_member_call(PyLSPContext *ctx, const char *callee_qn,
13521347 }
13531348}
13541349
1355- /* ── super(): the C3 method resolution order ──────────────────────── */
1350+ /* ── The C3 method resolution order ──────── ──────────────────────── */
13561351
13571352/* Longest linearization followed. A longer one (or more bases than this) keeps
1358- * the base-by-base walk of the caller . */
1353+ * the depth-first walk above . */
13591354#define PY_C3_MAX 64
13601355
1361- /* The linearizations computed during one super() lookup: every class of a
1362- * diamond is linearized once, however many paths reach it. */
1363- typedef struct {
1364- const char * qn [PY_C3_MAX ];
1365- const char * * mro [PY_C3_MAX ];
1366- int len [PY_C3_MAX ];
1367- int count ;
1368- } py_c3_cache_t ;
1356+ enum { PY_MRO_CACHE_INITIAL_CAP = 64 }; /* power of two (index masking) */
1357+ enum { PY_MRO_CACHE_MAX_CAP = 1 << 20 }; /* hard stop for adversarial files */
1358+
1359+ static uint32_t py_mro_hash (const char * qn ) {
1360+ uint32_t h = 2166136261u ; /* FNV-1a */
1361+ for (const unsigned char * p = (const unsigned char * )qn ; * p ; p ++ ) {
1362+ h = (h ^ * p ) * 16777619u ;
1363+ }
1364+ return h ;
1365+ }
1366+
1367+ static const CBMPyMroCacheEntry * py_mro_cache_find (const PyLSPContext * ctx , const char * qn ,
1368+ uint32_t h ) {
1369+ if (!ctx -> mro_cache || ctx -> mro_cache_cap == 0 )
1370+ return NULL ;
1371+ uint32_t mask = (uint32_t )ctx -> mro_cache_cap - 1 ;
1372+ uint32_t idx = h & mask ;
1373+ for (int probed = 0 ; probed < ctx -> mro_cache_cap ; probed ++ ) {
1374+ const CBMPyMroCacheEntry * e = & ctx -> mro_cache [idx ];
1375+ if (!e -> qn )
1376+ return NULL ;
1377+ if (e -> hash == h && strcmp (e -> qn , qn ) == 0 )
1378+ return e ;
1379+ idx = (idx + 1 ) & mask ;
1380+ }
1381+ return NULL ;
1382+ }
1383+
1384+ /* Doubles the table (arena allocation: the old table is freed with the
1385+ * per-file arena). */
1386+ static bool py_mro_cache_grow (PyLSPContext * ctx ) {
1387+ if (ctx -> mro_cache_cap >= PY_MRO_CACHE_MAX_CAP )
1388+ return false;
1389+ int new_cap = ctx -> mro_cache_cap ? ctx -> mro_cache_cap * 2 : PY_MRO_CACHE_INITIAL_CAP ;
1390+ CBMPyMroCacheEntry * entries = (CBMPyMroCacheEntry * )cbm_arena_alloc (
1391+ ctx -> arena , (size_t )new_cap * sizeof (CBMPyMroCacheEntry ));
1392+ if (!entries )
1393+ return false;
1394+ memset (entries , 0 , (size_t )new_cap * sizeof (CBMPyMroCacheEntry ));
1395+ uint32_t mask = (uint32_t )new_cap - 1 ;
1396+ for (int i = 0 ; i < ctx -> mro_cache_cap ; i ++ ) {
1397+ const CBMPyMroCacheEntry * e = & ctx -> mro_cache [i ];
1398+ if (!e -> qn )
1399+ continue ;
1400+ uint32_t idx = e -> hash & mask ;
1401+ while (entries [idx ].qn )
1402+ idx = (idx + 1 ) & mask ;
1403+ entries [idx ] = * e ;
1404+ }
1405+ ctx -> mro_cache = entries ;
1406+ ctx -> mro_cache_cap = new_cap ;
1407+ return true;
1408+ }
1409+
1410+ /* Records the order of `qn` (len -1: none). A table that cannot grow only
1411+ * costs a recomputation later. */
1412+ static void py_mro_cache_put (PyLSPContext * ctx , const char * qn , uint32_t h , const char * * mro ,
1413+ int len ) {
1414+ if ((ctx -> mro_cache_count + 1 ) * 4 > ctx -> mro_cache_cap * 3 && !py_mro_cache_grow (ctx ))
1415+ return ;
1416+ const char * key = cbm_arena_strdup (ctx -> arena , qn );
1417+ if (!key )
1418+ return ;
1419+ uint32_t mask = (uint32_t )ctx -> mro_cache_cap - 1 ;
1420+ uint32_t idx = h & mask ;
1421+ while (ctx -> mro_cache [idx ].qn )
1422+ idx = (idx + 1 ) & mask ;
1423+ ctx -> mro_cache [idx ].qn = key ;
1424+ ctx -> mro_cache [idx ].hash = h ;
1425+ ctx -> mro_cache [idx ].len = len ;
1426+ ctx -> mro_cache [idx ].mro = mro ;
1427+ ctx -> mro_cache_count ++ ;
1428+ }
13691429
13701430static bool py_c3_in_tail (const char * qn , const char * const * seq , int head , int len ) {
13711431 for (int k = head + 1 ; k < len ; k ++ ) {
@@ -1393,74 +1453,106 @@ static const char *py_c3_pick(const char **const *seqs, const int *lens, const i
13931453 return NULL ;
13941454}
13951455
1396- /* Python's method resolution order of `type_qn`: the class, then the C3 merge
1397- * of its bases' linearizations and of the base list. A common base therefore
1398- * follows every class deriving from it. Sets *out to an arena array and returns
1399- * its length, or -1 when there is no C3 order, the hierarchy is deeper than
1400- * CBM_LSP_MAX_LOOKUP_DEPTH, or the order is longer than PY_C3_MAX. A base the
1401- * registry does not know (external, unresolved) linearizes to itself. */
1402- static int py_c3_linearize (PyLSPContext * ctx , py_c3_cache_t * cache , const char * type_qn ,
1403- const char * * * out , int depth ) {
1404- for (int c = 0 ; c < cache -> count ; c ++ ) {
1405- if (strcmp (cache -> qn [c ], type_qn ) == 0 ) {
1406- * out = cache -> mro [c ];
1407- return cache -> len [c ];
1408- }
1409- }
1410- if (depth > CBM_LSP_MAX_LOOKUP_DEPTH )
1411- return -1 ;
1412- const CBMRegisteredType * rt = cbm_registry_lookup_type (ctx -> registry , type_qn );
1413- if (rt && rt -> alias_of )
1414- return py_c3_linearize (ctx , cache , rt -> alias_of , out , depth + 1 );
1415- const char * * bases = rt ? rt -> embedded_types : NULL ;
1416- int nb = 0 ;
1417- while (bases && bases [nb ])
1418- nb ++ ;
1419- if (nb >= PY_C3_MAX )
1420- return -1 ;
1421- const char * * seqs [PY_C3_MAX ];
1422- int lens [PY_C3_MAX ];
1423- int heads [PY_C3_MAX ];
1424- for (int b = 0 ; b < nb ; b ++ ) {
1425- lens [b ] = py_c3_linearize (ctx , cache , bases [b ], & seqs [b ], depth + 1 );
1426- if (lens [b ] < 0 )
1427- return -1 ;
1428- heads [b ] = 0 ;
1429- }
1430- seqs [nb ] = bases ;
1431- lens [nb ] = nb ;
1432- heads [nb ] = 0 ;
1433- const char * * mro = (const char * * )cbm_arena_alloc (ctx -> arena , PY_C3_MAX * sizeof (char * ));
1434- if (!mro )
1435- return -1 ;
1436- int n = 0 ;
1437- mro [n ++ ] = type_qn ;
1456+ /* The C3 merge of `nseq` sequences into mro[1..]: returns the order's length,
1457+ * or -1 when there is none or it is longer than PY_C3_MAX. */
1458+ static int py_c3_merge (const char * * const * seqs , const int * lens , int * heads , int nseq ,
1459+ const char * * mro ) {
1460+ int n = 1 ;
14381461 for (;;) {
14391462 bool pending = false;
1440- for (int s = 0 ; s <= nb && !pending ; s ++ ) {
1463+ for (int s = 0 ; s < nseq && !pending ; s ++ ) {
14411464 pending = heads [s ] < lens [s ];
14421465 }
14431466 if (!pending )
1444- break ;
1445- const char * pick = py_c3_pick (( const char * * const * ) seqs , lens , heads , nb + 1 );
1467+ return n ;
1468+ const char * pick = py_c3_pick (seqs , lens , heads , nseq );
14461469 if (!pick || n >= PY_C3_MAX )
14471470 return -1 ;
14481471 mro [n ++ ] = pick ;
1449- for (int s = 0 ; s <= nb ; s ++ ) {
1472+ for (int s = 0 ; s < nseq ; s ++ ) {
14501473 if (heads [s ] < lens [s ] && strcmp (seqs [s ][heads [s ]], pick ) == 0 )
14511474 heads [s ]++ ;
14521475 }
14531476 }
1454- if (cache -> count < PY_C3_MAX ) {
1455- cache -> qn [cache -> count ] = type_qn ;
1456- cache -> mro [cache -> count ] = mro ;
1457- cache -> len [cache -> count ] = n ;
1458- cache -> count ++ ;
1459- }
1460- * out = mro ;
1477+ }
1478+
1479+ /* Python's method resolution order of `type_qn`: the class, then the C3 merge
1480+ * of its bases' linearizations and of the base list. A common base therefore
1481+ * follows every class deriving from it. Computed once per class and file
1482+ * (ctx->mro_cache). Sets *out to an arena array and returns its length, or -1
1483+ * when there is no C3 order, the hierarchy is deeper than
1484+ * CBM_LSP_MAX_LOOKUP_DEPTH, or the order is longer than PY_C3_MAX. A base the
1485+ * registry does not know (external, unresolved) linearizes to itself. Only an
1486+ * order computed from the top (depth 0) is cached as missing: below it, the
1487+ * depth cap may have cut a hierarchy that is fine on its own. */
1488+ static int py_c3_linearize (PyLSPContext * ctx , const char * type_qn , const char * * * out , int depth ) {
1489+ uint32_t h = py_mro_hash (type_qn );
1490+ const CBMPyMroCacheEntry * hit = py_mro_cache_find (ctx , type_qn , h );
1491+ if (hit ) {
1492+ * out = hit -> mro ;
1493+ return hit -> len ;
1494+ }
1495+ int n = -1 ;
1496+ const char * * mro = NULL ;
1497+ const CBMRegisteredType * rt =
1498+ depth <= CBM_LSP_MAX_LOOKUP_DEPTH ? cbm_registry_lookup_type (ctx -> registry , type_qn ) : NULL ;
1499+ const char * * bases = rt ? rt -> embedded_types : NULL ;
1500+ int nb = 0 ;
1501+ while (bases && bases [nb ])
1502+ nb ++ ;
1503+ if (depth > CBM_LSP_MAX_LOOKUP_DEPTH || nb >= PY_C3_MAX ) {
1504+ n = -1 ;
1505+ } else if (rt && rt -> alias_of ) {
1506+ n = py_c3_linearize (ctx , rt -> alias_of , & mro , depth + 1 );
1507+ } else {
1508+ const char * * * seqs =
1509+ (const char * * * )cbm_arena_alloc (ctx -> arena , (size_t )(nb + 1 ) * sizeof (const char * * ));
1510+ int * lens = (int * )cbm_arena_alloc (ctx -> arena , (size_t )(nb + 1 ) * 2 * sizeof (int ));
1511+ mro = (const char * * )cbm_arena_alloc (ctx -> arena , PY_C3_MAX * sizeof (const char * ));
1512+ bool ok = seqs && lens && mro ;
1513+ int * heads = lens ? lens + nb + 1 : NULL ;
1514+ for (int b = 0 ; ok && b < nb ; b ++ ) {
1515+ lens [b ] = py_c3_linearize (ctx , bases [b ], & seqs [b ], depth + 1 );
1516+ heads [b ] = 0 ;
1517+ ok = lens [b ] >= 0 ;
1518+ }
1519+ if (ok ) {
1520+ seqs [nb ] = bases ;
1521+ lens [nb ] = nb ;
1522+ heads [nb ] = 0 ;
1523+ mro [0 ] = cbm_arena_strdup (ctx -> arena , type_qn );
1524+ n = mro [0 ] ? py_c3_merge ((const char * * const * )seqs , lens , heads , nb + 1 , mro ) : -1 ;
1525+ }
1526+ }
1527+ if (n >= 0 || depth == 0 )
1528+ py_mro_cache_put (ctx , type_qn , h , n >= 0 ? mro : NULL , n );
1529+ * out = n >= 0 ? mro : NULL ;
14611530 return n ;
14621531}
14631532
1533+ /* Attribute lookup along the class's C3 order: the class itself, then each
1534+ * class of its order that declares the member. A hierarchy without a C3 order
1535+ * keeps the depth-first walk. */
1536+ static const CBMRegisteredFunc * py_lookup_attribute (PyLSPContext * ctx , const char * type_qn ,
1537+ const char * member_name ) {
1538+ if (!ctx || !type_qn || !member_name )
1539+ return NULL ;
1540+ const CBMRegisteredFunc * f = cbm_registry_lookup_method (ctx -> registry , type_qn , member_name );
1541+ if (f )
1542+ return f ;
1543+ const char * * mro = NULL ;
1544+ int n = py_c3_linearize (ctx , type_qn , & mro , 0 );
1545+ if (n < 0 )
1546+ return py_lookup_attribute_depth (ctx , type_qn , member_name , 0 );
1547+ /* mro[0] is the class itself, already asked, or an alias's target. */
1548+ for (int i = strcmp (mro [0 ], type_qn ) == 0 ? 1 : 0 ; i < n ; i ++ ) {
1549+ f = cbm_registry_lookup_method (ctx -> registry , mro [i ], member_name );
1550+ if (f )
1551+ return f ;
1552+ }
1553+ return NULL ;
1554+ }
1555+
14641556/* The method super() reaches from inside `class_qn`: the first class AFTER it in
14651557 * its C3 order that declares `member` itself. *have_mro is false when the
14661558 * hierarchy has no C3 order; the caller then keeps its base-by-base walk. */
@@ -1469,10 +1561,8 @@ static const CBMRegisteredFunc *py_lookup_super_attribute(PyLSPContext *ctx, con
14691561 * have_mro = false;
14701562 if (!ctx || !class_qn || !member )
14711563 return NULL ;
1472- py_c3_cache_t cache ;
1473- cache .count = 0 ;
14741564 const char * * mro = NULL ;
1475- int n = py_c3_linearize (ctx , & cache , class_qn , & mro , 0 );
1565+ int n = py_c3_linearize (ctx , class_qn , & mro , 0 );
14761566 if (n < 0 )
14771567 return NULL ;
14781568 * have_mro = true;
0 commit comments