ES
apps/cryo-studio / src / Cryo / PhpCryoReader.php · commit 76aa68d
<?phpdeclare(strict_types=1);namespace App\Cryo;/** * Pure-PHP reader of the .cryo v1 format (same API and results as the * CryoReader class of ext-cryo). Used where ext-cryo is not loaded, e.g. in * the browser build of JumPHP. Layout: see ext-cryo/cryo_format.h. */final class PhpCryoReader{    private const NODE_SIZE = 29; // u32 id, u8 type, u32 class, u64 size, u32 handle, u32 site, u32 epoch    private const EDGE_SIZE = 12;    private const ROOT_SIZE = 9;    private const NONE = -1;          // CRYO_NONE (0xFFFFFFFF) after u32()    private const TWO32 = 4294967296.0;    private const OBJECT = 2;    private const ORPHAN = 4;    private const KINDS = ['?', 'global', 'static_prop', 'frame', 'orphan', 'static_var'];    private const TYPES = ['?', 'array', 'object', 'string', 'ref'];    public int $version = 0;    public int $phpVersion = 0;    public int $epoch = 0;    /** @var list<string> */    private array $strs = [];    /** @var list<array{id:int,type:int,class:int,size:int|float,handle:int,site:int,epoch:int}> */    private array $nodes = [];    private int $nedges = 0;    /** @var list<int> edge from / to / name, file order */    private array $ef = [];    private array $et = [];    private array $en = [];    /** @var list<int> section HASH (optional): raw u32 hash and length per node */    private array $hashes = [];    private array $hlens = [];    /** @var array<int,list<int>>|null adjacency: edge indexes per node, file order */    private ?array $out = null;    private ?array $in = null;    /** @var list<int> optional WRIT (write site per node) and NSTK (stack id per node) */    private array $writ = [];    private array $nstk = [];    /** @var list<list<int>> optional STKS: site ids per stack, innermost first */    private array $stacks = [];    /** @var list<array{kind:int,node:int,name:int}> */    private array $roots = [];    /** @var list<int> */    private array $sites = [];    private function __construct() {}    public static function open(string $file): self    {        $data = @file_get_contents($file);        if ($data === false) {            throw new \RuntimeException("Cannot open $file");        }        return self::fromString($data, $file);    }    public static function fromString(string $data, string $name = 'data'): self    {        if (strlen($data) < 16 || substr($data, 0, 4) !== 'CRYO') {            throw new \RuntimeException("$name is not a .cryo file");        }        $r = new self();        $h = unpack('vversion/vflags/Vphp/Vepoch', $data, 4);        $r->version = $h['version'];        $r->phpVersion = $h['php'];        $r->epoch = $h['epoch'];        if ($r->version !== 1) {            throw new \RuntimeException("Unsupported format version {$r->version}");        }        $len = strlen($data);        $off = 16;        while ($off + 12 <= $len) {            $tag = substr($data, $off, 4);            $slen = self::u64($data, $off + 4);            $off += 12;            if ($slen < 0 || $slen > $len - $off) {                throw new \RuntimeException('Truncated section');            }            match ($tag) {                'STRS' => $r->readStrs($data, $off, $slen),                'NODE' => $r->readNodes($data, $off, $slen),                'EDGE' => $r->readEdges($data, $off, $slen),                'HASH' => $r->readHashes($data, $off, $slen),                'WRIT' => $r->writ = $r->u32s($data, $off, $slen),                'NSTK' => $r->nstk = $r->u32s($data, $off, $slen),                'STKS' => $r->readStacks($data, $off, $slen),                'ROOT' => $r->readRoots($data, $off, $slen),                'SITE' => $r->sites = $slen >= 4 ? array_map(self::u32(...), array_values(unpack('V*', substr($data, $off, $slen - $slen % 4)))) : [],                default => null, // unknown sections are skipped            };            $off += $slen;        }        return $r;    }    private function readStrs(string $d, int $off, int $slen): void    {        if ($slen < 4) {            return;        }        $n = unpack('V', $d, $off)[1];        $q = 4;        for ($i = 0; $i < $n && $q + 4 <= $slen; $i++) {            $l = unpack('V', $d, $off + $q)[1];            $q += 4;            if ($q + $l > $slen) {                break;            }            $this->strs[] = substr($d, $off + $q, $l);            $q += $l;        }    }    private function readNodes(string $d, int $off, int $slen): void    {        $n = intdiv($slen, self::NODE_SIZE);        for ($i = 0; $i < $n; $i++) {            $at = $off + $i * self::NODE_SIZE;            $u = unpack('Vid/Ctype/Vclass', $d, $at) + unpack('Vhandle/Vsite/Vepoch', $d, $at + 17);            $this->nodes[] = [                'id' => $u['id'], 'type' => $u['type'], 'class' => self::u32($u['class']), 'size' => self::u64($d, $at + 9),                'handle' => self::u32($u['handle']), 'site' => self::u32($u['site']), 'epoch' => self::u32($u['epoch']),            ];        }    }    private function readEdges(string $d, int $off, int $slen): void    {        $n = intdiv($slen, self::EDGE_SIZE);        $this->nedges = $n;        if ($n === 0) {            return;        }        $v = unpack('V*', substr($d, $off, $n * self::EDGE_SIZE));        for ($i = 0, $k = 1; $i < $n; $i++, $k += 3) {            $this->ef[] = self::u32($v[$k]);            $this->et[] = self::u32($v[$k + 1]);            $this->en[] = self::u32($v[$k + 2]);        }    }    private function readHashes(string $d, int $off, int $slen): void    {        $n = intdiv($slen, 8);        if ($n === 0) {            return;        }        $v = unpack('V*', substr($d, $off, $n * 8));        for ($i = 0, $k = 1; $i < $n; $i++, $k += 2) {            $this->hashes[] = $v[$k];                                   // raw (negative on 32-bit PHP)            $this->hlens[] = $v[$k + 1] < 0 ? $v[$k + 1] + self::TWO32 : $v[$k + 1];        }    }    /** @return list<int> u32 array (CRYO_NONE = NONE) */    private function u32s(string $d, int $off, int $slen): array    {        $n = intdiv($slen, 4);        return $n ? array_map(self::u32(...), array_values(unpack('V*', substr($d, $off, $n * 4)))) : [];    }    private function readStacks(string $d, int $off, int $slen): void    {        if ($slen < 4 || $this->stacks) {            return;        }        $count = unpack('V', $d, $off)[1];        $q = 4;        for ($i = 0; ($count < 0 || $i < $count) && $q + 4 <= $slen; $i++) {            $nf = unpack('V', $d, $off + $q)[1];            if ($nf < 0 || $nf > intdiv($slen - $q - 4, 4)) {                break;            }            $this->stacks[] = $nf ? array_values(unpack("V$nf", $d, $off + $q + 4)) : [];            $q += 4 + $nf * 4;        }    }    private function readRoots(string $d, int $off, int $slen): void    {        $n = intdiv($slen, self::ROOT_SIZE);        for ($i = 0; $i < $n; $i++) {            $u = unpack('Ckind/Vnode/Vname', $d, $off + $i * self::ROOT_SIZE);            $this->roots[] = ['kind' => $u['kind'], 'node' => self::u32($u['node']), 'name' => self::u32($u['name'])];        }    }    /** u32 as read by unpack('V'): 0xFFFFFFFF (-1 on 32-bit PHP) becomes NONE. */    private static function u32(int $v): int    {        return $v === -1 || $v === 0xFFFFFFFF ? self::NONE : $v;    }    /** Little-endian u64 without pack('P') (32-bit PHP in the browser): an int when it fits, else a float. */    private static function u64(string $d, int $at): int|float    {        $u = unpack('Vlo/Vhi', $d, $at);        $lo = $u['lo'] < 0 ? $u['lo'] + self::TWO32 : $u['lo'];        $hi = $u['hi'] < 0 ? $u['hi'] + self::TWO32 : $u['hi'];        if ($hi === 0) {            return $lo > PHP_INT_MAX ? (float) $lo : (int) $lo;        }        $v = $hi * self::TWO32 + $lo;        return $v <= PHP_INT_MAX ? (int) $v : (float) $v;    }    private function str(int $i): string    {        return $this->strs[$i] ?? '';    }    private function site(int $site): string    {        return $site === self::NONE || !isset($this->sites[$site]) ? '(unknown)' : $this->str($this->sites[$site]);    }    private function write(int $v): ?string    {        $w = $this->writ[$v] ?? self::NONE;        return $w === self::NONE || !isset($this->sites[$w]) ? null : $this->str($this->sites[$w]);    }    /** @return list<string> frames of the allocation stack of node $v ([] if unknown) */    private function stack(int $v): array    {        $id = $this->nstk[$v] ?? self::NONE;        if ($id === self::NONE || !isset($this->stacks[$id])) {            return [];        }        return array_map(fn($site) => $this->site(self::u32($site)), $this->stacks[$id]);    }    /** Aggregation key of node $v for top() / delta(). */    private function key(int $v, string $by): string    {        $n = $this->nodes[$v];        return match ($by) {            'site' => $this->site($n['site']),            'stack' => ($f = $this->stack($v)) ? implode(' <- ', $f) : '(unknown)',            'write' => $this->write($v) ?? '(unknown)',            default => $this->str($n['class']),        };    }    public function info(): array    {        $bytes = $objects = $tracked = $orphans = 0;        foreach ($this->nodes as $n) {            $bytes += $n['size'];            if ($n['type'] === self::OBJECT) {                $objects++;                if ($n['site'] !== self::NONE) {                    $tracked++;                }            }        }        foreach ($this->roots as $rt) {            if ($rt['kind'] === self::ORPHAN) {                $orphans++;            }        }        return [            'format' => $this->version, 'php_version_id' => $this->phpVersion, 'epoch' => $this->epoch,            'nodes' => count($this->nodes), 'edges' => $this->nedges, 'roots' => count($this->roots),            'objects' => $objects, 'objects_with_site' => $tracked, 'orphans' => $orphans,            'sites' => count($this->sites), 'bytes' => $bytes,        ];    }    /**     * Objects grouped by $by ("retained" = by class with the retained size of the class,     * "class", "site", "stack", "write"): list of {<key>, count, bytes[, retained]}.     */    public function top(string $by = 'retained', int $limit = 20): array    {        if (!in_array($by, ['retained', 'class', 'site', 'stack', 'write'], true)) {            throw new \ValueError('PhpCryoReader::top(): Argument #1 ($by) must be "retained", "class", "site", "stack" or "write"');        }        $retained = $by === 'retained';        if ($retained) {            $by = 'class';            $clsRet = $this->classRetained();        }        $agg = [];        foreach ($this->nodes as $v => $n) {            if ($n['type'] !== self::OBJECT) {                continue;            }            $k = $this->key($v, $by);            $agg[$k] ??= [$by => $k, 'count' => 0, 'bytes' => 0] + ($retained ? ['retained' => $clsRet[$n['class']] ?? 0] : []);            $agg[$k]['count']++;            $agg[$k]['bytes'] += $n['size'];        }        $rows = array_values($agg);        usort($rows, fn($x, $y) => [$y['retained'] ?? 0, $y['bytes'], $y['count']] <=> [$x['retained'] ?? 0, $x['bytes'], $x['count']]);        return array_slice($rows, 0, max(0, $limit));    }    public function roots(): array    {        return array_map(fn($rt) => [            'kind' => self::KINDS[$rt['kind'] <= 5 ? $rt['kind'] : 0],            'name' => $this->str($rt['name']),            'node' => $rt['node'],        ], $this->roots);    }    /* ---- Graph queries (M2): same algorithms and orders as ext-cryo ---- */    /** Builds the out / in adjacency once (invalid edges ignored, file order kept). */    private function adj(): void    {        if ($this->out !== null) {            return;        }        $n = count($this->nodes);        $this->out = $n ? array_fill(0, $n, []) : [];        $this->in = $this->out;        foreach ($this->ef as $e => $f) {            $t = $this->et[$e];            if ($f >= 0 && $f < $n && $t >= 0 && $t < $n) {                $this->out[$f][] = $e;                $this->in[$t][] = $e;            }        }    }    private function validNode(int $v): bool    {        return $v >= 0 && $v < count($this->nodes);    }    /** @return array{type:string,class:?string} */    private function typeClass(int $v): array    {        $nd = $this->nodes[$v];        return [            'type' => self::TYPES[$nd['type'] <= 4 ? $nd['type'] : 0],            'class' => $nd['class'] === self::NONE ? null : $this->str($nd['class']),        ];    }    /** Node record: node, type, class, size, site, epoch, handle (null = unknown). */    private function record(int $v): array    {        $nd = $this->nodes[$v];        return ['node' => $v] + $this->typeClass($v) + [            'size' => $nd['size'],            'site' => $nd['site'] !== self::NONE && isset($this->sites[$nd['site']]) ? $this->str($this->sites[$nd['site']]) : null,            'write' => $this->write($v),            'epoch' => $nd['epoch'] === self::NONE ? null : $nd['epoch'],            'handle' => $nd['handle'] === self::NONE ? null : $nd['handle'],        ];    }    /** BFS from the orphan (or non-orphan) roots through unmarked nodes. */    private function bfsMark(array &$mark, bool $orphan, int $val): void    {        $queue = [];        foreach ($this->roots as $rt) {            $v = $rt['node'];            if (($rt['kind'] === self::ORPHAN) !== $orphan || !$this->validNode($v) || isset($mark[$v])) {                continue;            }            $mark[$v] = $val;            $queue[] = $v;        }        for ($head = 0; $head < count($queue); $head++) {            foreach ($this->out[$queue[$head]] as $e) {                $t = $this->et[$e];                if (!isset($mark[$t])) {                    $mark[$t] = $val;                    $queue[] = $t;                }            }        }    }    /** @var list<int>|null BFS distance from the roots (NONE = unreachable) */    private ?array $dist = null;    /** @var array{order:list<int>,idom:array<int,int>,ret:array<int,int|float>}|null */    private ?array $dom = null;    /** @return list<int> distance of every node from the roots */    private function dist(): array    {        if ($this->dist !== null) {            return $this->dist;        }        $this->adj();        $n = count($this->nodes);        $dist = $n ? array_fill(0, $n, self::NONE) : [];        $queue = [];        foreach ($this->roots as $rt) {            $v = $rt['node'];            if ($this->validNode($v) && $dist[$v] === self::NONE) {                $dist[$v] = 0;                $queue[] = $v;            }        }        for ($head = 0; $head < count($queue); $head++) {            $v = $queue[$head];            foreach ($this->out[$v] as $e) {                $t = $this->et[$e];                if ($dist[$t] === self::NONE) {                    $dist[$t] = $dist[$v] + 1;                    $queue[] = $t;                }            }        }        return $this->dist = $dist;    }    private function step(string $kind, string $name, int $v): array    {        return ['kind' => $kind, 'name' => $name, 'node' => $v] + $this->typeClass($v) + ['write' => $this->write($v)];    }    /**     * Up to $max shortest paths from a root to $node: list of paths, each a list of     * {kind, name, node, type, class, write} (first step: the root). [] if unreachable.     */    public function path(int $node, int $max = 5): array    {        if (!$this->validNode($node) || $max <= 0) {            return [];        }        $dist = $this->dist();        if ($dist[$node] === self::NONE) {            return [];        }        $nroots = count($this->roots);        $paths = [];        $nodes = [$node];        $pos = [0];        $edge = [-1];        $sp = 1;        while ($sp && count($paths) < $max) {            $v = $nodes[$sp - 1];            if ($dist[$v] === 0) {                $i = $pos[$sp - 1];                while ($i < $nroots && $this->roots[$i]['node'] !== $v) {                    $i++;                }                if ($i >= $nroots) {                    $sp--;                    continue;                }                $pos[$sp - 1] = $i + 1;                $rt = $this->roots[$i];                $path = [$this->step(self::KINDS[$rt['kind'] <= 5 ? $rt['kind'] : 0], $this->str($rt['name']), $v)];                for ($k = $sp - 1; $k >= 1; $k--) {                    $path[] = $this->step('edge', $this->str($this->en[$edge[$k]]), $nodes[$k - 1]);                }                $paths[] = $path;            } else {                $in = $this->in[$v];                $j = $pos[$sp - 1];                $end = count($in);                while ($j < $end && $dist[$this->ef[$in[$j]]] !== $dist[$v] - 1) {                    $j++;                }                if ($j >= $end) {                    $sp--;                    continue;                }                $pos[$sp - 1] = $j + 1;                $nodes[$sp] = $this->ef[$in[$j]];                $pos[$sp] = 0;                $edge[$sp] = $in[$j];                $sp++;            }        }        return $paths;    }    /** Dominator tree (Cooper-Harvey-Kennedy) and retained sizes, computed once. */    private function dom(): array    {        if ($this->dom !== null) {            return $this->dom;        }        $this->adj();        $n = count($this->nodes);        $S = $n;        $nroots = count($this->roots);        $isRoot = [];        foreach ($this->roots as $rt) {            if ($this->validNode($rt['node'])) {                $isRoot[$rt['node']] = true;            }        }        // iterative DFS from the super-root: postorder numbers        $vis = [$S => true];        $post = $order = [];        $stk = [$S];        $pos = [0];        $sp = 1;        $cnt = 0;        while ($sp) {            $v = $stk[$sp - 1];            $i = $pos[$sp - 1];            if ($v === $S) {                $more = $i < $nroots;                $child = $more ? $this->roots[$i]['node'] : -1;            } else {                $more = $i < count($this->out[$v]);                $child = $more ? $this->et[$this->out[$v][$i]] : -1;            }            if ($more) {                $pos[$sp - 1]++;                if ($this->validNode($child) && !isset($vis[$child])) {                    $vis[$child] = true;                    $stk[$sp] = $child;                    $pos[$sp] = 0;                    $sp++;                }            } else {                $sp--;                $post[$v] = $cnt;                $order[$cnt++] = $v;            }        }        // Cooper-Harvey-Kennedy, reverse postorder until stable        $idom = [$S => $S];        do {            $changed = false;            for ($k = $cnt - 2; $k >= 0; $k--) {                $v = $order[$k];                $nd = -1;                if (isset($isRoot[$v])) {                    $nd = $S;                } else {                    foreach ($this->in[$v] as $e) {                        $p = $this->ef[$e];                        if (!isset($idom[$p])) {                            continue;                        }                        if ($nd === -1) {                            $nd = $p;                            continue;                        }                        $a = $p;                        $b = $nd;                        while ($a !== $b) {                            while ($post[$a] < $post[$b]) {                                $a = $idom[$a];                            }                            while ($post[$b] < $post[$a]) {                                $b = $idom[$b];                            }                        }                        $nd = $a;                    }                }                if ($nd !== -1 && ($idom[$v] ?? -1) !== $nd) {                    $idom[$v] = $nd;                    $changed = true;                }            }        } while ($changed);        // retained sizes: every node before its dominator (postorder)        $ret = [];        for ($k = 0; $k + 1 < $cnt; $k++) {            $ret[$order[$k]] = $this->nodes[$order[$k]]['size'];        }        for ($k = 0; $k + 1 < $cnt; $k++) {            $v = $order[$k];            if ($idom[$v] !== $S) {                $ret[$idom[$v]] += $ret[$v];            }        }        return $this->dom = ['order' => $order, 'idom' => $idom, 'ret' => $ret];    }    /** Retained size of node $v (0 if unreachable). */    private function retained(int $v): int|float    {        return $this->dom()['ret'][$v] ?? 0;    }    /**     * Dominator tree from a super-root linked to every root (Cooper-Harvey-Kennedy),     * nodes that retain the most: list of {node, type, class, self, retained, idom}.     */    public function dominators(int $limit = 20): array    {        $d = $this->dom();        $S = count($this->nodes);        $rows = [];        for ($k = 0; $k + 1 < count($d['order']); $k++) {            $rows[] = [$d['order'][$k], $d['ret'][$d['order'][$k]]];        }        usort($rows, fn($x, $y) => [$y[1], $x[0]] <=> [$x[1], $y[0]]);        $out = [];        foreach (array_slice($rows, 0, max(0, $limit)) as [$v, $r]) {            $out[] = ['node' => $v] + $this->typeClass($v) + [                'self' => $this->nodes[$v]['size'],                'retained' => $r,                'idom' => $d['idom'][$v] === $S ? null : $d['idom'][$v],            ];        }        return $out;    }    /**     * Retained size per class index without double counting: an instance counts     * when no other instance of its class dominates it.     * @return array<int,int|float> class string index => retained     */    private function classRetained(): array    {        $d = $this->dom();        $S = count($this->nodes);        $kids = [];        for ($k = 0; $k + 1 < count($d['order']); $k++) {            $v = $d['order'][$k];            $kids[$d['idom'][$v]][] = $v;        }        $clsRet = $open = [];        $cls = fn(int $v) => $v !== $S && $this->nodes[$v]['type'] === self::OBJECT && $this->nodes[$v]['class'] >= 0            && $this->nodes[$v]['class'] < count($this->strs) ? $this->nodes[$v]['class'] : -1;        $stk = [$S];        $pos = [0];        $sp = 1;        while ($sp) {            $v = $stk[$sp - 1];            if ($pos[$sp - 1] < count($kids[$v] ?? [])) {                $c = $kids[$v][$pos[$sp - 1]++];                $k = $cls($c);                if ($k >= 0) {                    if (($open[$k] ?? 0) === 0) {                        $clsRet[$k] = ($clsRet[$k] ?? 0) + $d['ret'][$c];                    }                    $open[$k] = ($open[$k] ?? 0) + 1;                }                $stk[$sp] = $c;                $pos[$sp] = 0;                $sp++;            } else {                $k = $cls($v);                if ($k >= 0) {                    $open[$k]--;                }                $sp--;            }        }        return $clsRet;    }    /** Objects reachable only from "orphan" roots (uncollected cycles): node records by node id. */    public function orphans(): array    {        $this->adj();        $mark = [];        $this->bfsMark($mark, false, 1);        $this->bfsMark($mark, true, 2);        ksort($mark);        $out = [];        foreach ($mark as $v => $m) {            if ($m === 2 && $this->nodes[$v]['type'] === self::OBJECT) {                $out[] = $this->record($v);            }        }        return $out;    }    /**     * Strings and flat arrays present in several copies with the same content     * (section HASH, [] without it): list of {type, hash, length, count, bytes, wasted, node}.     */    public function dupes(int $limit = 20): array    {        $n = min(count($this->nodes), count($this->hashes));        $groups = [];        for ($v = 0; $v < $n; $v++) {            $h = $this->hashes[$v];            if ($h === 0) {                continue;            }            $t = $this->nodes[$v]['type'];            $size = $this->nodes[$v]['size'];            $key = $t . ':' . $h . ':' . $this->hlens[$v];            if (!isset($groups[$key])) {                $groups[$key] = ['t' => $t, 'h' => sprintf('%08x', $h), 'len' => $this->hlens[$v], 'node' => $v, 'count' => 0, 'bytes' => 0, 'min' => $size];            }            $g = &$groups[$key];            $g['count']++;            $g['bytes'] += $size;            if ($size < $g['min']) {                $g['min'] = $size;            }            unset($g);        }        $rows = [];        foreach ($groups as $g) {            if ($g['count'] >= 2) {                $g['wasted'] = $g['bytes'] - $g['min'];                $rows[] = $g;            }        }        usort($rows, function ($x, $y) {            return ($y['wasted'] <=> $x['wasted']) ?: ($y['count'] <=> $x['count']) ?: ($x['t'] <=> $y['t'])                ?: (strcmp($x['h'], $y['h']) <=> 0) ?: ($x['len'] <=> $y['len']) ?: ($x['node'] <=> $y['node']);        });        $out = [];        foreach (array_slice($rows, 0, max(0, $limit)) as $g) {            $out[] = [                'type' => self::TYPES[$g['t'] <= 4 ? $g['t'] : 0], 'hash' => $g['h'], 'length' => $g['len'],                'count' => $g['count'], 'bytes' => $g['bytes'], 'wasted' => $g['wasted'], 'node' => $g['node'],            ];        }        return $out;    }    private static function space(string $s, int $p): bool    {        return $p < strlen($s) && ($s[$p] === ' ' || $s[$p] === "\t" || $s[$p] === "\n" || $s[$p] === "\r");    }    private static function lower(string $c): bool    {        return $c >= 'a' && $c <= 'z';    }    private const QFIELDS = ['class', 'type', 'site', 'write', 'size', 'retained', 'epoch'];    /** `*` wildcard match (same algorithm as ext-cryo; fnmatch() would treat `\` as an escape). */    public static function glob(string $p, string $s, bool $nocase = false): bool    {        if ($nocase) {            $p = strtolower($p);            $s = strtolower($s);        }        $plen = strlen($p);        $slen = strlen($s);        $pi = $si = $mark = 0;        $star = -1;        while ($si < $slen) {            if ($pi < $plen && $p[$pi] === '*') {                $star = $pi++;                $mark = $si;            } elseif ($pi < $plen && $p[$pi] === $s[$si]) {                $pi++;                $si++;            } elseif ($star !== -1) {                $pi = $star + 1;                $si = ++$mark;            } else {                return false;            }        }        while ($pi < $plen && $p[$pi] === '*') {            $pi++;        }        return $pi === $plen;    }    /**     * Parses the query language: list of [field, op, value(string|float), orBefore].     * @throws \ValueError     */    private static function qParse(string $src): array    {        $len = strlen($src);        $p = 0;        $conds = [];        $orNext = false;        $fail = fn(int $at) => throw new \ValueError('PhpCryoReader::query(): Argument #1 ($expr) invalid query near "' . substr($src, $at) . '"');        while (true) {            while (self::space($src, $p)) $p++;            $term = $p;            $f0 = $p;            while ($p < $len && (self::lower($src[$p]) || $src[$p] === '_')) $p++;            $field = array_search(substr($src, $f0, $p - $f0), self::QFIELDS, true);            if ($field === false || $p === $f0) {                $fail($term);            }            while (self::space($src, $p)) $p++;            $two = substr($src, $p, 2);            if ($two === '>=' || $two === '<=' || $two === '!=') {                $op = $two;                $p += 2;            } elseif ($p < $len && strpbrk($src[$p], '=<>') !== false) {                $op = $src[$p++];            } else {                $fail($p);            }            while (self::space($src, $p)) $p++;            if ($p < $len && $src[$p] === '"') {                $q = strpos($src, '"', $p + 1);                if ($q === false) {                    $fail($p);                }                $value = substr($src, $p + 1, $q - $p - 1);                $v0 = $p + 1;                $p = $q + 1;            } else {                $v0 = $p;                while ($p < $len && !self::space($src, $p)) $p++;                $value = substr($src, $v0, $p - $v0);                if ($value === '') {                    $fail($v0);                }            }            if ($field >= 4) {                if (!preg_match('/^([0-9]{1,15})([kKmMgG]?)$/', $value, $m)) {                    $fail($v0);                }                $mult = ['' => 1.0, 'k' => 1024.0, 'm' => 1048576.0, 'g' => 1073741824.0][strtolower($m[2])];                $value = (float) $m[1] * $mult;            } elseif ($op !== '=' && $op !== '!=') {                $fail($term);            }            $conds[] = [$field, $op, $value, $orNext];            while (self::space($src, $p)) $p++;            if ($p >= $len) {                break;            }            $w0 = $p;            while ($p < $len && self::lower(strtolower($src[$p]))) $p++;            $word = strtolower(substr($src, $w0, $p - $w0));            if ($word === 'and') {                $orNext = false;            } elseif ($word === 'or') {                $orNext = true;            } else {                $fail($w0);            }        }        return $conds;    }    private function qMatch(array $conds, int $v): bool    {        $nd = $this->nodes[$v];        $group = true;        foreach ($conds as [$field, $op, $value, $orBefore]) {            if ($orBefore) {                if ($group) {                    return true;                }                $group = true;            }            if (!$group) {                continue;            }            if ($field < 4) {                $s = match ($field) {                    0 => $nd['class'] !== self::NONE && isset($this->strs[$nd['class']]) ? $this->strs[$nd['class']] : null,                    1 => self::TYPES[$nd['type'] <= 4 ? $nd['type'] : 0],                    2 => $nd['site'] !== self::NONE && isset($this->sites[$nd['site']]) ? $this->str($this->sites[$nd['site']]) : null,                    3 => $this->write($v),                };                $ok = $s === null ? $op === '!=' : (self::glob($value, $s) === ($op === '='));            } else {                $known = $field !== 6 || $nd['epoch'] !== self::NONE;                $x = (float) match ($field) { 4 => $nd['size'], 5 => $this->retained($v), 6 => $nd['epoch'] };                $ok = !$known ? $op === '!=' : match ($op) {                    '=' => $x == $value, '!=' => $x != $value, '>' => $x > $value,                    '<' => $x < $value, '>=' => $x >= $value, '<=' => $x <= $value,                };            }            if (!$ok) {                $group = false;            }        }        return $group;    }    /**     * Node records matching $expr, by node id. A string is a query-language expression     * (`class=App\* and retained>1M or type=string`); an array holds filters: type,     * class (exact), site (substring), min_size, epoch_min, epoch_max, expr, limit (default 100).     */    public function query(string|array $expr): array    {        $filter = is_string($expr) ? ['expr' => $expr] : $expr;        $type = 0;        $cls = $site = null;        $min = 0;        $emin = $emax = null;        $limit = 100;        $conds = [];        $src = null;        foreach ($filter as $k => $val) {            if (!is_string($k)) {                throw new \ValueError('PhpCryoReader::query(): Argument #1 ($expr) must only have string keys');            }            switch ($k) {                case 'type':                    $type = (int) array_search((string) $val, self::TYPES, true);                    if ($type === 0) {                        throw new \ValueError('PhpCryoReader::query(): Argument #1 ($expr) key "type" must be "array", "object", "string" or "ref"');                    }                    break;                case 'class': $cls = (string) $val; break;                case 'site': $site = (string) $val; break;                case 'min_size': $min = (int) $val; break;                case 'epoch_min': $emin = (int) $val; break;                case 'epoch_max': $emax = (int) $val; break;                case 'limit': $limit = (int) $val; break;                case 'expr': $src = (string) $val; break;                default:                    throw new \ValueError("PhpCryoReader::query(): Argument #1 (\$expr) has an unknown key \"$k\"");            }        }        if ($src !== null) {            $conds = self::qParse($src);        }        $out = [];        $n = count($this->nodes);        for ($v = 0; $v < $n && count($out) < $limit; $v++) {            $nd = $this->nodes[$v];            if ($type && $nd['type'] !== $type) {                continue;            }            if ($conds && !$this->qMatch($conds, $v)) {                continue;            }            if ($cls !== null && ($nd['class'] === self::NONE || ($this->strs[$nd['class']] ?? null) !== $cls)) {                continue;            }            if ($site !== null) {                if ($nd['site'] === self::NONE || !isset($this->sites[$nd['site']])) {                    continue;                }                if ($site !== '' && !str_contains($this->str($this->sites[$nd['site']]), $site)) {                    continue;                }            }            if ($min > 0 && $nd['size'] < $min) {                continue;            }            if ($emin !== null && ($nd['epoch'] === self::NONE || $nd['epoch'] < $emin)) {                continue;            }            if ($emax !== null && ($nd['epoch'] === self::NONE || $nd['epoch'] > $emax)) {                continue;            }            $out[] = $this->record($v);        }        return $out;    }    /** Node record + out / in edges ({name, node, type, class}) + roots ({kind, name}); null if no such node. */    public function node(int $id): ?array    {        if (!$this->validNode($id)) {            return null;        }        $this->adj();        $edges = function (array $list, bool $out): array {            $r = [];            foreach ($list as $e) {                $other = $out ? $this->et[$e] : $this->ef[$e];                $r[] = ['name' => $this->str($this->en[$e]), 'node' => $other] + $this->typeClass($other);            }            return $r;        };        $roots = [];        foreach ($this->roots as $rt) {            if ($rt['node'] === $id) {                $roots[] = ['kind' => self::KINDS[$rt['kind'] <= 5 ? $rt['kind'] : 0], 'name' => $this->str($rt['name'])];            }        }        return $this->record($id) + ['stack' => $this->stack($id) ?: null, 'out' => $edges($this->out[$id], true), 'in' => $edges($this->in[$id], false), 'roots' => $roots];    }    /**     * Compares N snapshots of the same process (same results as CryoReader::delta()).     * @param array<string|self> $files paths or already opened readers     * @param array{by?:string}|string $opts "by": view used by ArrayAccess / Countable / foreach     *        ("site", "class" or "stack"; default "site"). A string is taken as "by".     */    public static function delta(array $files, array|string $opts = []): PhpCryoDelta    {        if (!class_exists(PhpCryoDelta::class)) {            require_once __DIR__ . '/PhpCryoDelta.php';        }        $by = is_string($opts) ? $opts : 'site';        if (is_array($opts)) {            foreach ($opts as $k => $v) {                if ($k !== 'by' || !is_string($v)) {                    throw new \ValueError('PhpCryoReader::delta(): Argument #2 ($opts) only accepts the key "by" (string)');                }                $by = $v;            }        }        if (!in_array($by, ['site', 'class', 'stack'], true)) {            throw new \ValueError('PhpCryoReader::delta(): Argument #2 ($opts) "by" must be "site", "class" or "stack"');        }        if (count($files) < 2) {            throw new \ValueError('PhpCryoReader::delta(): Argument #1 ($files) must contain at least 2 snapshots');        }        $snaps = [];        foreach (array_values($files) as $f) {            $snaps[] = [$f instanceof self ? $f : self::open($f), $f instanceof self ? 'data' : (string) $f];        }        usort($snaps, fn($a, $b) => $a[0]->epoch <=> $b[0]->epoch);        $names = array_column($snaps, 1);        $snaps = array_column($snaps, 0);        return new PhpCryoDelta(            ['site' => self::deltaRows($snaps, 'site'), 'class' => self::deltaRows($snaps, 'class'), 'stack' => self::deltaRows($snaps, 'stack')],            self::timeline($snaps, $names),            $by,            end($snaps),            $snaps[0]->epoch,        );    }    private function hRow(array &$rows, string $kind, int|float $score, string $msg, ?int $node, ?string $site, int|float $bytes): void    {        $rows[] = [            'kind' => $kind, 'score' => (int) min(100, $score), 'message' => $msg, 'node' => $node, 'site' => $site,            'bytes' => $bytes, 'path' => $node === null ? null : ($this->path($node, 1)[0] ?? null),        ];    }    private function hCallable(int $t): bool    {        $nd = $this->nodes[$t];        if ($nd['type'] === self::OBJECT && $nd['class'] !== self::NONE && ($this->strs[$nd['class']] ?? null) === 'Closure') {            return true;        }        if ($nd['type'] !== 1 || count($this->out[$t]) !== 2) {            return false;        }        $a = $this->nodes[$this->et[$this->out[$t][0]]]['type'];        $b = $this->nodes[$this->et[$this->out[$t][1]]]['type'];        return ($a === self::OBJECT && $b === 3) || ($a === 3 && $b === self::OBJECT);    }    /**     * Suspicious patterns, by score desc (same rules as CryoReader::heuristics()):     * list of {kind: orphans|static_cache|listeners|memory_log|growth, score, message, node, site, bytes, path}.     * @param list<string> $files 2+ snapshots: growing allocation sites of their delta     */    public function heuristics(array $files = []): array    {        $d = $this->dom();        $n = count($this->nodes);        $S = $n;        $rows = [];        $total = $reach = 0;        foreach ($this->nodes as $v => $nd) {            $total += $nd['size'];            if (isset($d['idom'][$v])) {                $reach += $nd['size'];            }        }        // 1. orphans        $mark = [];        $this->bfsMark($mark, false, 1);        $this->bfsMark($mark, true, 2);        $bytes = $objects = 0;        foreach ($mark as $v => $m) {            if ($m === 2) {                $bytes += $this->nodes[$v]['size'];                if ($this->nodes[$v]['type'] === self::OBJECT) {                    $objects++;                }            }        }        $first = null;        foreach ($this->roots as $rt) {            if ($rt['kind'] === self::ORPHAN && $this->validNode($rt['node'])) {                $first = $rt['node'];                break;            }        }        if ($objects) {            $pct = $total ? (int) floor($bytes * 100 / $total) : 0;            $this->hRow($rows, 'orphans', 50 + $pct, "$objects objects kept alive only by uncollected cycles", $first, null, $bytes);        }        // 2. static caches        $done = [];        foreach ($this->roots as $rt) {            $v = $rt['node'];            if (($rt['kind'] !== 2 && $rt['kind'] !== 5) || !$this->validNode($v) || isset($done[$v])) {                continue;            }            $done[$v] = true;            $ret = ($d['idom'][$v] ?? -1) === $S ? $d['ret'][$v] : 0;            if (!$reach || $ret * 100 <= $reach * 10) {                continue;            }            $pct = (int) floor($ret * 100 / $reach);            $this->hRow($rows, 'static_cache', $pct, $this->str($rt['name']) . " retains $pct% of the reachable heap", $v, null, $ret);        }        // 3. listeners, 4. in-memory logs        foreach ([0, 1] as $pass) {            foreach ($this->nodes as $v => $nd) {                if ($nd['type'] !== 1) {                    continue;                }                $deg = count($this->out[$v]);                if ($deg < ($pass ? 100 : 10)) {                    continue;                }                $hits = 0;                foreach ($this->out[$v] as $e) {                    $t = $this->et[$e];                    if ($pass ? $this->nodes[$t]['type'] === 3 : $this->hCallable($t)) {                        $hits++;                    }                }                $ret = $d['ret'][$v] ?? 0;                if (!$pass && $hits * 10 >= $deg * 8) {                    $this->hRow($rows, 'listeners', 10 + $hits, "array of $hits callables (listeners) that may keep their objects alive", $v, null, $ret);                } elseif ($pass && $hits * 10 >= $deg * 9) {                    $this->hRow($rows, 'memory_log', 20 + intdiv($hits, 20), "array of $hits strings (in-memory log?)", $v, null, $ret);                }            }        }        // 5. growth over the given snapshots        if (count($files) >= 2) {            foreach (self::delta($files)->bySite() as $r) {                if ($r['growing']) {                    $this->hRow($rows, 'growth', 50 + (int) ($r['survival'] * 50),                        "objects allocated at {$r['site']} grow at every snapshot ({$r['survivors']} survivors)", null, $r['site'], $r['bytes_last']);                }            }        }        usort($rows, fn($a, $b) => $b['score'] <=> $a['score']);        return $rows;    }    /**     * Objects per class in two snapshots (same result as cryo_diff()):     * list of {class, count_a, count_b, count_delta, bytes_a, bytes_b, bytes_delta},     * bytes_delta desc, count_delta desc, classes in first-seen order.     */    public static function diff(string|self $a, string|self $b): array    {        $rows = [];        foreach ([$a, $b] as $f => $r) {            $r = $r instanceof self ? $r : self::open($r);            $suffix = $f ? 'b' : 'a';            foreach ($r->nodes as $nd) {                if ($nd['type'] !== self::OBJECT) {                    continue;                }                $c = $r->str($nd['class']);                $rows[$c] ??= ['class' => $c, 'count_a' => 0, 'count_b' => 0, 'count_delta' => 0, 'bytes_a' => 0, 'bytes_b' => 0, 'bytes_delta' => 0];                $rows[$c]["count_$suffix"]++;                $rows[$c]["bytes_$suffix"] += $nd['size'];            }        }        $out = [];        foreach ($rows as $row) {            $row['class'] = (string) $row['class'];            $row['count_delta'] = $row['count_b'] - $row['count_a'];            $row['bytes_delta'] = $row['bytes_b'] - $row['bytes_a'];            $out[] = $row;        }        usort($out, fn($x, $y) => [$y['bytes_delta'], $y['count_delta']] <=> [$x['bytes_delta'], $x['count_delta']]);        return $out;    }    /** @param list<self> $snaps sorted by epoch */    private static function deltaRows(array $snaps, string $by): array    {        $n = count($snaps);        $nint = $n - 1;        $rows = [];        $row = function (string $key) use (&$rows, $nint) {            $rows[$key] ??= ['key' => $key, 'born' => array_fill(0, $nint, 0), 'left' => array_fill(0, $nint, 0), 'bytes' => 0, 'hooks' => []];        };        for ($i = 1; $i < $n; $i++) {            $lo = $snaps[$i - 1]->epoch;            $hi = $snaps[$i]->epoch;            foreach ($snaps[$i]->nodes as $v => $nd) {                if ($nd['type'] !== self::OBJECT || $nd['site'] === self::NONE || $nd['epoch'] === self::NONE) {                    continue;                }                if ($nd['epoch'] <= $lo || $nd['epoch'] > $hi) {                    continue;                }                $k = $snaps[$i]->key($v, $by);                $row($k);                $rows[$k]['born'][$i - 1]++;            }        }        $last = $snaps[$n - 1];        foreach ($last->nodes as $v => $nd) {            if ($nd['type'] !== self::OBJECT || $nd['site'] === self::NONE || $nd['epoch'] === self::NONE) {                continue;            }            if ($nd['epoch'] <= $snaps[0]->epoch) {                continue;            }            for ($i = 1; $i < $n; $i++) {                if ($nd['epoch'] > $snaps[$i - 1]->epoch && $nd['epoch'] <= $snaps[$i]->epoch) {                    $k = $last->key($v, $by);                    $row($k);                    $rows[$k]['left'][$i - 1]++;                    $rows[$k]['bytes'] += $nd['size'];                    $w = $last->write($v);                    if ($w !== null) {                        $rows[$k]['hooks'][$w] = ($rows[$k]['hooks'][$w] ?? 0) + 1;                    }                    break;                }            }        }        $out = [];        foreach ($rows as $r) {            $bornTotal = array_sum($r['born']);            $survivors = array_sum($r['left']);            $growing = true;            for ($i = 0; $i < $nint; $i++) {                if ($r['born'][$i] === 0 || $r['left'][$i] < $r['born'][$i]) {                    $growing = false;                }            }            $best = null;            $bestN = 0;            foreach ($r['hooks'] as $w => $c) {                if ($c > $bestN) {                    $best = (string) $w;                    $bestN = $c;                }            }            $out[] = [                $by => (string) $r['key'],                'new_per_interval' => $r['born'],                'cohort_alive_at_last' => $r['left'],                'survivors' => $survivors,                'survival' => $bornTotal ? (float) $survivors / $bornTotal : 0.0,                'bytes_last' => $r['bytes'],                'growing' => $growing,                'hooked_by' => $best,            ];        }        // growing first, then survivors desc (stable, like ext-cryo)        usort($out, fn($a, $b) => [$b['growing'], $b['survivors']] <=> [$a['growing'], $a['survivors']]);        return $out;    }    /** @param list<self> $snaps sorted by epoch */    private static function timeline(array $snaps, array $names): array    {        $n = count($snaps);        $list = $byClass = $bySite = [];        foreach ($snaps as $i => $s) {            $bytes = $objects = 0;            foreach ($s->nodes as $nd) {                $bytes += $nd['size'];                if ($nd['type'] !== self::OBJECT) {                    continue;                }                $objects++;                $c = $s->str($nd['class']);                $byClass[$c] ??= array_fill(0, $n, 0);                $byClass[$c][$i]++;                $k = $s->site($nd['site']);                $bySite[$k] ??= array_fill(0, $n, 0);                $bySite[$k][$i]++;            }            $list[] = ['file' => $names[$i], 'epoch' => $s->epoch, 'objects' => $objects, 'bytes' => $bytes];        }        return ['snapshots' => $list, 'by_class' => $byClass, 'by_site' => $bySite];    }    /** Splits "file:line function" (leftmost ":digits "). @return array{0:string,1:int}|null */    public static function siteSplit(string $site): ?array    {        return preg_match('/^(.*?):([0-9]{1,9}) /s', $site, $m) ? [$m[1], (int) $m[2]] : null;    }    /** Lines line-2 .. line+2 of the file of a site ([line => text]), null if unreadable. */    public static function code(?string $site): ?array    {        $split = $site === null ? null : self::siteSplit($site);        if ($split === null) {            return null;        }        $data = @file_get_contents($split[0]);        if ($data === false) {            return null;        }        $lines = $data === '' ? [] : explode("\n", $data);        if ($lines && end($lines) === '') {            array_pop($lines);        }        $code = [];        for ($no = max(1, $split[1] - 2); $no <= $split[1] + 2 && $no <= count($lines); $no++) {            $code[$no] = rtrim($lines[$no - 1], "\r\n");        }        return $code;    }    /**     * @internal used by PhpCryoDelta::explain(): typical paths of the survivors of a site     * in this (last) snapshot, grouped by signature, top 3.     */    public function typicalPaths(string $site, int $firstEpoch): array    {        $groups = [];        $seen = 0;        foreach ($this->nodes as $v => $nd) {            if ($seen >= 50) {                break;            }            if ($nd['type'] !== self::OBJECT || $nd['site'] === self::NONE || $nd['epoch'] === self::NONE                || $nd['epoch'] <= $firstEpoch || $this->site($nd['site']) !== $site) {                continue;            }            $seen++;            $p = $this->path($v, 1)[0] ?? null;            if ($p === null) {                continue;            }            $sig = '';            foreach ($p as $step) {                $sig .= $step['kind'] . ':' . (preg_match('/^\[[0-9]+\]$/', $step['name']) ? '[n]' : $step['name']) . '/';            }            if (isset($groups[$sig])) {                $groups[$sig]['count']++;            } else {                $groups[$sig] = ['count' => 1, 'path' => $p];            }        }        $groups = array_values($groups);        usort($groups, fn($a, $b) => $b['count'] <=> $a['count']);        return array_slice($groups, 0, 3);    }}