Query::traverseExpressions() is exponential in the nesting depth of QueryExpression, which makes MySQL query compilation hang since 5.4

[nicosp]

Description

Description

Query::traverseExpressions() visits each expression once per path through the tree instead of once, so the number of
visits doubles with every level of nested QueryExpression.

QueryExpression::traverse() is already recursive: for each condition it calls $callback($c) and then
$c->traverse($callback). Query::_expressionsVisitor() passes a callback that recurses into the expression itself:

$expression->traverse(fn($exp) => $this->_expressionsVisitor($exp, $callback));

So every nested expression is walked once by the visitor and once more by QueryExpression::traverse()'s own recursion,
at every level.

Driver::transformQuery() calls traverseExpressions() on every compilation when the driver has expression translators.
Since 5.4 the MySQL driver has them (StringAggExpression, DistinctComparisonExpression), so every sql(), count()
and all() on MySQL/MariaDB pays this cost, even for queries that use neither expression. On 5.3
Mysql::_expressionTranslators() was empty and transformQuery() returned before traversing.

We hit it in production: a search built from 11 and-ed conditions (each an or of 2–4 comparisons) nests 19 levels
deep, and each compilation of the query took 9 seconds (2 ms on 5.3.6). The page counted, fetched and eager-loaded a
belongsToMany with the subquery strategy, so it compiled the conditions 4 times and took 35 seconds.

How to reproduce

No database needed, compiling doesn't connect:

<?php
require 'vendor/autoload.php';

use Cake\Database\Connection;
use Cake\Database\Driver\Mysql;
use Cake\Database\Expression\QueryExpression;

$connection = new Connection(['driver' => new Mysql()]);

foreach ([10, 14, 18, 22] as $depth) {
    $where = new QueryExpression(['a' => 1]);
    for ($i = 0; $i < $depth; $i++) {
        $where = new QueryExpression([$where, new QueryExpression(["b$i" => $i], [], 'OR')]);
    }
    $query = $connection->selectQuery('id', 'things')->where($where);

    $visits = 0;
    $query->traverseExpressions(function () use (&$visits) {
        $visits++;
    });

    $start = microtime(true);
    $query->sql();
    printf("depth %2d: %9d visits, sql() %.3fs\n", $depth, $visits, microtime(true) - $start);
}

Output with CakePHP 5.4.2, PHP 8.4:

depth 10:     10234 visits, sql() 0.007s
depth 14:    163834 visits, sql() 0.099s
depth 18:   2621434 visits, sql() 1.597s
depth 22:  41943034 visits, sql() 25.552s

The tree at depth 22 has fewer than 100 expressions.

Expected

Each expression is visited once, and the translators are applied once per expression.

Possible fix

Either keep _expressionsVisitor() from recursing into what traverse() already recursed into, or have it skip
expressions it has already seen (a WeakMap of visited expressions). We worked around it with a driver subclass that does
the latter in transformQuery(). That brought compilation of our query back to 2–4 ms, and translators still apply
inside subqueries.

CakePHP Version

5.4.2

PHP Version

8.4