"Cannot autowire service..." when autowiring to new module's service that is yet to be installed

Problem/Motivation

A module that has autowired services that depend on a to-be-installed module cannot be deployed automatically.

module1 has a my.service:

services:
  my.service:
    class: Drupal\mymodule\Service\MyService
    autowire: true

The service depends on My2Service

class MyService {

  public function __construct(protected My2Service $my2Service) {}
}

module2 has a my2.service

services:
  my2.service:
    class: Drupal\my2module\Service\My2Service
    autowire: true
  Drupal\my2module\Service\My2Service: '@my2.service'

Steps to reproduce

1. Enable module 1 without autowiring changes
2. Make autowiring changes that depend on new module 2
3. Add update hook to enable module 2
4. Run `drush updb`

Error:

In DefinitionErrorExceptionPass.php line 51:                                     
                                                                                   
Cannot autowire service "my.service": argument "$my2Service" of method "Drupal\mymodule\Service\MyService::__construct()" has type "\Drupal\my2module\Service\My2Service" but this class couldn't be loaded. Either it was not found or it is missing a parent class or a trait.  

This is manually fixable by using drush to enable the missing module. Using an update hook to enable the module does not work, as it errors out before running the hook.

Proposed resolution

Remaining tasks

User interface changes

Introduced terminology

API changes

Data model changes

Release notes snippet