MenuTreeStorage::rebuild() invalidates a cache tag for every menu on the site, not just the ones it rebuilds

The real cost shows up on a full cache clear; the volume of menu cache-tag invalidations causes a lot of DB writes. The extra query the fix adds is marginal by comparison.
I updated the IS to clarify.

The script below creates 10K menu links, simulating a large site with many menus (e.g. og_menu, group_content_menu, domain menus). Once populated, compare time drush cr between the two branches. The fix avoids ~10K redundant cache-tag invalidations on every rebuild. Numbers on my machine:
- without fix (main branch): 3.5s
- with fix (MR16126 branch): 1.8s

<?php

/**
 * Populates the site with many content-managed menu links to demonstrate the
 * cost of MenuTreeStorage::rebuild() invalidating a cache tag for every menu on
 * the site. rebuild() runs on every `drush cr`.
 *
 * Each link is a normal MenuLinkContent entity in its own menu, so it has
 * discovered = 0 -- exactly like the menu links a site (or og_menu) creates.
 *
 *   drush scr populate_menus.php     # create the links
 *   time drush cr                    # measure, on 11.x and on the fix branch
 */

// Number of content menus to create. Bump it to make the difference larger.
$count = 10000;

$storage = \Drupal::entityTypeManager()->getStorage('menu_link_content');

// Remove any links from a previous run first, so this is repeatable.
$ids = $storage->getQuery()
  ->accessCheck(FALSE)
  ->condition('menu_name', 'bench_menu_%', 'LIKE')
  ->execute();
if ($ids) {
  $storage->delete($storage->loadMultiple($ids));
}

$t = microtime(TRUE);
for ($i = 0; $i < $count; $i++) {
  $storage->create([
    'title' => 'bench',
    'link' => ['uri' => 'route:<front>'],
    'menu_name' => "bench_menu_$i",
  ])->save();
}
printf("Created %d content menus in %.0fs. Now run: time drush cr\n", $count, microtime(TRUE) - $t);

Sure, done, it's a bit redundant with the comment above anyway.

Thank you for the review @berdir!

Regarding #6, the discovered flag is driven by the link scheme: MenuLinkContent::preSave() only sets rediscover on internal: links, the deriver re-derives just those, and rebuild() marks them discovered = 1.
So in your example, 3 discovered ones are most probably the internal: paths, the entity:node/N ones stay 0 (also why discovered menus stay a small subset).
Internal ones need it because the route can change under them between rebuilds.

#3485030: Avoid saving menu links through node form when they do not change only touches menu_ui AFAICS (MenuUiUtility::menuUiNodeSave()), not MenuTreeStorage, so no overlap here. It skips the entity save when the node form didn't change the link, so it avoids the invalidation on the save path; this issue is about the rebuild path. Complementary.

---

I eventually created 2 branches:
- v1 (MR 16126): still invalidates every menu with discovered links on each rebuild, so it only stops invalidating content-only menus (the og_menu/group case). Small blast radius.
I updated tests use the checksum service now, thanks for the example.
I first tried your array_column($definitions, 'menu_name') suggestion, but found a gap: preSave()/findParent() can store a link in its parent's menu, so the definition menu_name isn't always the stored one. It misses when that inherited menu is declared by no discovered link, e.g. a discovered link parented under a content link (discovered = 0).
So I pushed a test for that scenario (see pipelines) and reverted to the getDiscoveredMenuNames() query, which reads the stored menu_name and doesn't have that issue.

- v2 (MR 16270): only invalidates menus that actually changed, using the resolved menu names from the save. No extra query, and a no-op rebuild invalidates nothing.
But it's a bigger behavioral change: it drops the implicit "every rebuild flushes all menu tags" that some code relied on.
I hit one case in core, the toolbar render is tagged config:system.menu.admin but its content also depends on hook_toolbar_alter, so it went stale when a module altered it without a menu change (fixed by adding config:core.extension to the toolbar element).
Contrib modules/projects may hit similar cases, so v2 would probably need a change record?

So v1 is contained, slightly less precise but safe IMO.
v2 is more correct but a wider/risker change. Should we park v2 for now?