<?php

/*
 * This file is part of the TYPO3 CMS project.
 *
 * It is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License, either version 2
 * of the License, or any later version.
 *
 * For the full copyright and license information, please read the
 * LICENSE.txt file that was distributed with this source code.
 *
 * The TYPO3 project - inspiring people to share!
 */

namespace TYPO3\CMS\Core\Package;

use Composer\InstalledVersions;
use Symfony\Component\Finder\Finder;
use Symfony\Component\Finder\SplFileInfo;
use TYPO3\CMS\Core\Cache\Event\CacheWarmupEvent;
use TYPO3\CMS\Core\Core\ClassLoadingInformation;
use TYPO3\CMS\Core\Core\Environment;
use TYPO3\CMS\Core\Information\Typo3Information;
use TYPO3\CMS\Core\Package\Cache\PackageCacheEntry;
use TYPO3\CMS\Core\Package\Cache\PackageCacheInterface;
use TYPO3\CMS\Core\Package\Event\PackagesMayHaveChangedEvent;
use TYPO3\CMS\Core\Package\Exception\InvalidPackageKeyException;
use TYPO3\CMS\Core\Package\Exception\InvalidPackageManifestException;
use TYPO3\CMS\Core\Package\Exception\InvalidPackagePathException;
use TYPO3\CMS\Core\Package\Exception\InvalidPackageStateException;
use TYPO3\CMS\Core\Package\Exception\PackageManagerCacheUnavailableException;
use TYPO3\CMS\Core\Package\Exception\PackageStatesFileNotWritableException;
use TYPO3\CMS\Core\Package\Exception\ProtectedPackageKeyException;
use TYPO3\CMS\Core\Package\Exception\UnknownPackageException;
use TYPO3\CMS\Core\Package\Exception\UnknownPackagePathException;
use TYPO3\CMS\Core\Package\MetaData\PackageConstraint;
use TYPO3\CMS\Core\Service\DependencyOrderingService;
use TYPO3\CMS\Core\Service\OpcodeCacheService;
use TYPO3\CMS\Core\SingletonInterface;
use TYPO3\CMS\Core\Utility\ArrayUtility;
use TYPO3\CMS\Core\Utility\GeneralUtility;
use TYPO3\CMS\Core\Utility\PathUtility;

/**
 * The default TYPO3 Package Manager
 *
 * @phpstan-type PackageKey non-empty-string
 * @phpstan-type PackageName non-empty-string
 * @phpstan-type PackageConstraints array{dependencies: list<PackageKey>, suggestions: list<PackageKey>}
 * @phpstan-type StateConfiguration array{packagePath?: non-empty-string}
 * @phpstan-type StatesConfiguration array{packages?: array<PackageKey, StateConfiguration>, version?: int}
 */
class PackageManager implements SingletonInterface
{
    /**
     * @var DependencyOrderingService
     */
    protected $dependencyOrderingService;

    /**
     * @var PackageCacheInterface
     */
    protected $packageCache;

    /**
     * @var array{local?: non-empty-string, system?: non-empty-string}
     */
    protected $packagesBasePaths = [];

    /**
     * @var array<PackageName, PackageKey>
     */
    protected $packageAliasMap = [];

    /**
     * Absolute path leading to the various package directories
     * @var string
     */
    protected $packagesBasePath;

    /**
     * Array of available packages, indexed by package key
     * @var array<PackageKey, PackageInterface>
     */
    protected $packages = [];

    /**
     * @var bool
     */
    protected $availablePackagesScanned = false;

    /**
     * A map between ComposerName and PackageKey, only available when scanAvailablePackages is run,
     * e.g. `['typo3/cms-core' => 'core', 'typo3/cms-backend' => 'backend']`
     * @var array<PackageName, PackageKey>
     */
    protected $composerNameToPackageKeyMap = [];

    /**
     * List of active packages as package key => package object
     * @var array<PackageKey, PackageInterface>
     */
    protected $activePackages = [];

    /**
     * @var string
     */
    protected $packageStatesPathAndFilename;

    /**
     * Package states configuration as stored in the PackageStates.php file
     * @var StatesConfiguration
     */
    protected $packageStatesConfiguration = [];

    /**
     * The regex to match paths with EXT:{package/key}
     */
    protected ?string $packagePathMatchRegex;

    private array $frameworkPackageNames = [];
    private array $installedPackageNames = [];

    public function __construct(DependencyOrderingService $dependencyOrderingService, ?string $packageStatesPathAndFilename = null, ?string $packagesBasePath = null)
    {
        $this->dependencyOrderingService = $dependencyOrderingService;
        $this->packagesBasePath = $packagesBasePath ?? Environment::getProjectPath() . '/';
        $this->packageStatesPathAndFilename = $packageStatesPathAndFilename ?? Environment::getPackageStatesFile();
    }

    /**
     * Access the composer.json of typo3/cms package
     * to find out all framework package names, so that we
     * can safely assume this is not a composer dependency
     */
    private function populateFrameworkAndComposerPackageNames(): void
    {
        $this->frameworkPackageNames = require __DIR__ . '/../../Resources/Private/Php/framework-packages.php';
        $this->installedPackageNames = array_filter(
            InstalledVersions::getInstalledPackages(),
            fn(string $packageName) => !in_array($packageName, $this->frameworkPackageNames, true) && $packageName !== 'typo3/cms',
        );
    }

    /**
     * @internal
     */
    public function setPackageCache(PackageCacheInterface $packageCache)
    {
        $this->packageCache = $packageCache;
    }

    /**
     * Initializes the package manager
     * @internal
     */
    public function initialize()
    {
        try {
            $this->loadPackageManagerStatesFromCache();
        } catch (PackageManagerCacheUnavailableException) {
            $this->loadPackageStates();
            $this->initializePackageObjects();
            $appPackage = new VirtualAppPackage(
                $this,
                Environment::getProjectPath() . '/',
                '',
            );
            $this->registerPackage($appPackage);
            $this->registerActivePackage($appPackage);
            $this->validateResources();
            $this->saveToPackageCache();
        }
    }

    /**
     * @internal
     * @return string|null
     */
    public function getCacheIdentifier()
    {
        try {
            return $this->packageCache->getIdentifier();
        } catch (PackageManagerCacheUnavailableException) {
            return null;
        }
    }

    /**
     * Saves the current state of all relevant information in the package cache
     */
    protected function saveToPackageCache(): void
    {
        // Build cache entry
        $cacheEntry = PackageCacheEntry::fromPackageData(
            $this->packageStatesConfiguration,
            $this->packageAliasMap,
            $this->composerNameToPackageKeyMap,
            $this->packages,
        );
        $this->packageCache->store($cacheEntry);
    }

    /**
     * @todo this does not belong here and should be extracted into a different service
     */
    protected function validateResources(): void
    {
        $publicPrefixes = [];
        foreach ($this->packages as $package) {
            if (!$package instanceof Package) {
                continue;
            }
            $packageKey = $package->getPackageKey();
            $resourcePaths = [];
            foreach ($package->getResources()->getPublicResourceDefinitions() as $resource) {
                $relativePath = $resource->getRelativePath();
                if (
                    str_starts_with($relativePath, '/')
                    || str_ends_with($relativePath, '/')
                    || !GeneralUtility::validPathStr($relativePath)
                ) {
                    throw new \RuntimeException(sprintf(
                        'Invalid relative path "%s" defined by package "%s". Relative paths must not have leading, or trailing slashes, or backpaths (../), or other malicious characters.',
                        $relativePath,
                        $packageKey,
                    ), 1774612899);
                }
                if (isset($resourcePaths[$relativePath])) {
                    throw new \RuntimeException(sprintf(
                        'Relative path "%s" is already defined by package "%s". Resource definitions must be unique.',
                        $relativePath,
                        $packageKey,
                    ), 1774612999);
                }
                $resourcePaths[$relativePath] = true;
                $publicPrefix = $resource->getPublicPrefix();
                if (!is_string($publicPrefix)) {
                    continue;
                }
                if (isset($publicPrefixes[$publicPrefix])) {
                    throw new \RuntimeException(sprintf(
                        'Public prefix "%s" is already defined by package "%s" can not be redefined by package "%s"',
                        $publicPrefix,
                        $publicPrefixes[$publicPrefix],
                        $packageKey,
                    ), 1774612898);
                }
                $publicPrefixes[$publicPrefix] = $packageKey;
            }
        }
    }

    /**
     * Attempts to load the package manager states from cache
     *
     * @throws PackageManagerCacheUnavailableException
     */
    protected function loadPackageManagerStatesFromCache()
    {
        $cacheEntry = $this->packageCache->fetch();
        $this->packageStatesConfiguration = $cacheEntry->getConfiguration();
        $this->packageAliasMap = $cacheEntry->getAliasMap();
        $this->composerNameToPackageKeyMap = $cacheEntry->getComposerNameMap();
        $this->packages = $cacheEntry->getPackages();
    }

    /**
     * Loads the states of available packages from the PackageStates.php file.
     * The result is stored in $this->packageStatesConfiguration.
     *
     * @throws Exception\PackageStatesUnavailableException
     */
    protected function loadPackageStates()
    {
        $this->packageStatesConfiguration = (@include $this->packageStatesPathAndFilename) ?: [];
        PackageCacheEntry::ensureValidPackageConfiguration($this->packageStatesConfiguration);
        $this->registerPackagesFromConfiguration($this->packageStatesConfiguration['packages'], false);
    }

    /**
     * Initializes activePackages property
     *
     * Saves PackageStates.php if list of required extensions has changed.
     */
    protected function initializePackageObjects()
    {
        $requiredPackages = [];
        $activePackages = [];
        foreach ($this->packages as $packageKey => $package) {
            if ($package->isProtected()) {
                $requiredPackages[$packageKey] = $package;
            }
            if (isset($this->packageStatesConfiguration['packages'][$packageKey])) {
                $activePackages[$packageKey] = $package;
            }
        }
        $previousActivePackages = $activePackages;
        $activePackages = array_merge($requiredPackages, $activePackages);

        if ($activePackages != $previousActivePackages) {
            foreach ($requiredPackages as $package) {
                $this->registerActivePackage($package);
            }
            $this->sortAndSavePackageStates();
        }
    }

    protected function registerActivePackage(PackageInterface $package)
    {
        // reset the active packages so they are rebuilt.
        $this->activePackages = [];
        $this->packagePathMatchRegex = null;
        $this->packageStatesConfiguration['packages'][$package->getPackageKey()] = ['packagePath' => str_replace($this->packagesBasePath, '', $package->getPackagePath())];
    }

    /**
     * Scans all directories in the packages directories for available packages.
     * For each package a Package object is created and stored in $this->packages.
     * @internal
     */
    public function scanAvailablePackages()
    {
        if (Environment::isComposerMode()) {
            return;
        }
        $packagePaths = $this->scanPackagePathsForExtensions();
        $packages = [];
        foreach ($packagePaths as $packageKey => $packagePath) {
            $packages[$packageKey] = ['packagePath' => str_replace($this->packagesBasePath, '', $packagePath)];
        }

        $this->availablePackagesScanned = true;
        $registerOnlyNewPackages = !empty($this->packages);
        $this->registerPackagesFromConfiguration($packages, $registerOnlyNewPackages);
    }

    /**
     * Resolves a path in the form EXT:vendor/package/Path/To/Resource to an absolute filesystem path
     *
     * @throws UnknownPackageException
     * @throws UnknownPackagePathException
     */
    public function resolvePackagePath(string $path): string
    {
        $packageKey = $this->extractPackageKeyFromPackagePath($path);
        $package = $this->getPackage($packageKey);

        return str_replace('EXT:' . $packageKey . '/', $package->getPackagePath(), $path);
    }

    /**
     * Extracts the package key from a path in the form EXT:vendor/package/Path/To/Resource
     *
     * @throws UnknownPackageException
     * @throws UnknownPackagePathException
     * @internal
     */
    public function extractPackageKeyFromPackagePath(string $path): string
    {
        if (!PathUtility::isExtensionPath($path)) {
            throw new UnknownPackageException('Given path is not an extension path starting with "EXT:" ' . $path, 1631630764);
        }
        if (!isset($this->packagePathMatchRegex)) {
            $this->packagePathMatchRegex = sprintf(
                '/^EXT:(%s)\//',
                implode(
                    '|',
                    array_map(
                        static function (string $packageKey): string {
                            return preg_quote($packageKey, '/');
                        },
                        array_merge(
                            array_keys($this->getActivePackages()),
                            array_keys($this->packageAliasMap),
                            array_keys($this->composerNameToPackageKeyMap)
                        )
                    )
                )
            );
        }
        $result = preg_match($this->packagePathMatchRegex, $path, $matches);
        if (!$result || empty($matches[1])) {
            throw new UnknownPackagePathException('Package path "' . $path . '" is not available. Please check if the package referenced in the path exists and that the package key is correct (package keys are case sensitive).', 1631630087);
        }

        return $matches[1];
    }

    /**
     * Event listener to retrigger scanning of available packages.
     */
    public function packagesMayHaveChanged(PackagesMayHaveChangedEvent $event): void
    {
        $this->scanAvailablePackages();
    }

    /**
     * Fetches all directories from sysext/local locations and checks if the extension contains an composer.json
     * with a type "typo3-cms-framework", or "typo3-cms-extension".
     *
     * @return array
     */
    protected function scanPackagePathsForExtensions()
    {
        $collectedExtensionPaths = [];
        $this->populateFrameworkAndComposerPackageNames();
        foreach ($this->getPackageBasePaths() as $packageBasePath) {
            // Only add the extension if we have a composer.json and the extension is not yet registered.
            // This is crucial in order to allow overriding of system extension by local extensions
            // and strongly depends on the order of paths defined in $this->packagesBasePaths.
            $finder = new Finder();
            $finder
                ->name('composer.json')
                ->followLinks()
                ->depth(0)
                ->ignoreUnreadableDirs()
                ->in($packageBasePath);

            /** @var SplFileInfo $fileInfo */
            foreach ($finder as $fileInfo) {
                try {
                    $composerManifest = json_decode($fileInfo->getContents(), false, 512, JSON_THROW_ON_ERROR);
                } catch (\JsonException) {
                    continue;
                }
                $packageType = $composerManifest->type ?? '';
                // Only allow typo3-cms package types
                if (!str_starts_with($packageType, 'typo3-cms-')) {
                    continue;
                }
                $packageProvides = array_keys((array)($composerManifest->extra->{'typo3/cms'}->Package->providesPackages ?? []));
                $this->installedPackageNames = array_merge($this->installedPackageNames, $packageProvides);
                $path = PathUtility::dirname($fileInfo->getPathname());
                // Fix Windows backslashes
                $currentPath = GeneralUtility::fixWindowsFilePath($path) . '/';
                $packageKey = $this->getPackageKeyFromManifest($composerManifest, $currentPath);
                if (!isset($collectedExtensionPaths[$packageKey])) {
                    $collectedExtensionPaths[$packageKey] = $currentPath;
                }
            }
        }
        return $collectedExtensionPaths;
    }

    /**
     * Requires and registers all packages which were defined in packageStatesConfiguration
     *
     * @param array<PackageKey, StateConfiguration> $packages
     * @param bool $registerOnlyNewPackages
     * @throws Exception\InvalidPackageStateException
     * @throws Exception\PackageStatesFileNotWritableException
     */
    protected function registerPackagesFromConfiguration(array $packages, $registerOnlyNewPackages = false)
    {
        $packageStatesHasChanged = false;
        foreach ($packages as $packageKey => $stateConfiguration) {
            if ($registerOnlyNewPackages && $this->isPackageRegistered($packageKey)) {
                continue;
            }

            if (!isset($stateConfiguration['packagePath'])) {
                $this->unregisterPackageByPackageKey($packageKey);
                $packageStatesHasChanged = true;
                continue;
            }

            try {
                $packagePath = PathUtility::sanitizeTrailingSeparator($this->packagesBasePath . $stateConfiguration['packagePath']);
                $package = new Package($this, $packageKey, $packagePath);
            } catch (InvalidPackagePathException|InvalidPackageKeyException|InvalidPackageManifestException $exception) {
                $this->unregisterPackageByPackageKey($packageKey);
                $packageStatesHasChanged = true;
                continue;
            }

            $this->registerPackage($package);
        }
        if ($packageStatesHasChanged) {
            $this->sortAndSavePackageStates();
        }
    }

    /**
     * Register a native TYPO3 package
     *
     * @param PackageInterface $package The Package to be registered
     * @return PackageInterface
     * @throws Exception\InvalidPackageStateException
     * @internal
     */
    public function registerPackage(PackageInterface $package)
    {
        $packageKey = $package->getPackageKey();
        if ($this->isPackageRegistered($packageKey)) {
            throw new InvalidPackageStateException('Package "' . $packageKey . '" is already registered.', 1338996122);
        }
        $composerName = $package->getValueFromComposerManifest('name');
        if ($composerName !== $packageKey) {
            $this->composerNameToPackageKeyMap[$composerName] = $packageKey;
        }
        $this->packages[$packageKey] = $package;

        foreach ($package->getPackageReplacementKeys() as $packageToReplace => $versionConstraint) {
            $this->packageAliasMap[$packageToReplace] = $package->getPackageKey();
        }
        return $package;
    }

    /**
     * Unregisters a package from the list of available packages
     *
     * @param string|PackageKey $packageKey Package Key of the package to be unregistered
     */
    protected function unregisterPackageByPackageKey($packageKey)
    {
        try {
            $package = $this->getPackage($packageKey);
            foreach ($package->getPackageReplacementKeys() as $packageToReplace => $versionConstraint) {
                unset($this->packageAliasMap[$packageToReplace]);
            }
        } catch (UnknownPackageException $e) {
        }
        $this->composerNameToPackageKeyMap = array_filter(
            $this->composerNameToPackageKeyMap,
            static function (string $aliasedKey) use ($packageKey): bool {
                return $aliasedKey !== $packageKey;
            }
        );
        unset($this->packages[$packageKey]);
        unset($this->packageStatesConfiguration['packages'][$packageKey]);
    }

    /**
     * Resolves a TYPO3 package key from a composer package name.
     *
     * @param string|PackageName $composerName
     * @return string|PackageKey|PackageName
     * @internal
     */
    public function getPackageKeyFromComposerName($composerName)
    {
        if (isset($this->packageAliasMap[$composerName])) {
            return $this->packageAliasMap[$composerName];
        }
        if (isset($this->composerNameToPackageKeyMap[$composerName])) {
            return $this->composerNameToPackageKeyMap[$composerName];
        }
        return $composerName;
    }

    /**
     * Returns a PackageInterface object for the specified package.
     * A package is available, if the package directory contains valid MetaData information.
     *
     * @param string|PackageKey $packageKey
     * @return PackageInterface The requested package object
     * @throws Exception\UnknownPackageException if the specified package is not known
     */
    public function getPackage($packageKey)
    {
        if (!$this->isPackageRegistered($packageKey) && !$this->isPackageAvailable($packageKey)) {
            throw new UnknownPackageException('Package "' . $packageKey . '" is not available. Please check if the package exists and that the package key is correct (package keys are case sensitive).', 1166546734);
        }
        return $this->packages[$this->getPackageKeyFromComposerName($packageKey)];
    }

    /**
     * Returns TRUE if a package is available (the package's files exist in the packages directory)
     * or FALSE if it's not. If a package is available it doesn't mean necessarily that it's active!
     *
     * @param string|PackageKey $packageKey The key of the package to check
     * @return bool TRUE if the package is available, otherwise FALSE
     */
    public function isPackageAvailable($packageKey)
    {
        if ($this->isPackageRegistered($packageKey)) {
            return true;
        }

        // If activePackages is empty, the PackageManager is currently initializing
        // thus packages should not be scanned
        if (!$this->availablePackagesScanned && !empty($this->activePackages)) {
            $this->scanAvailablePackages();
        }

        return $this->isPackageRegistered($packageKey);
    }

    /**
     * Returns TRUE if a package is activated or FALSE if it's not.
     *
     * @param string|PackageKey $packageKey The key of the package to check
     * @return bool TRUE if package is active, otherwise FALSE
     */
    public function isPackageActive($packageKey)
    {
        $packageKey = $this->getPackageKeyFromComposerName($packageKey);

        return isset($this->packageStatesConfiguration['packages'][$packageKey]);
    }

    /**
     * Deactivates a package and updates the packagestates configuration
     *
     * @param string|PackageKey $packageKey
     * @throws Exception\PackageStatesFileNotWritableException
     * @throws Exception\ProtectedPackageKeyException
     * @throws Exception\UnknownPackageException
     * @internal
     */
    public function deactivatePackage($packageKey)
    {
        if (!$this->isPackageActive($packageKey)) {
            return;
        }
        $package = $this->getPackage($packageKey);
        if ($package->isProtected()) {
            throw new ProtectedPackageKeyException('The package "' . $packageKey . '" is protected and cannot be deactivated.', 1308662891);
        }

        $packagesWithDependencies = $this->sortActivePackagesByDependencies();
        foreach ($packagesWithDependencies as $packageStateKey => $packageStateConfiguration) {
            if ($packageKey === $packageStateKey || empty($packageStateConfiguration['dependencies'])) {
                continue;
            }
            if (in_array($packageKey, $packageStateConfiguration['dependencies'], true)) {
                $this->deactivatePackage($packageStateKey);
            }
        }

        $this->activePackages = [];
        $this->packagePathMatchRegex = null;
        unset($this->packageStatesConfiguration['packages'][$packageKey]);
        $this->sortAndSavePackageStates();
    }

    /**
     * @param string|PackageKey $packageKey
     * @internal
     */
    public function activatePackage($packageKey)
    {
        $package = $this->getPackage($packageKey);
        $this->registerTransientClassLoadingInformationForPackage($package);

        if ($this->isPackageActive($packageKey)) {
            return;
        }

        $this->registerActivePackage($package);
        $this->sortAndSavePackageStates();
    }

    /**
     * @throws \TYPO3\CMS\Core\Exception
     */
    protected function registerTransientClassLoadingInformationForPackage(PackageInterface $package)
    {
        if (Environment::isComposerMode()) {
            return;
        }
        ClassLoadingInformation::registerTransientClassLoadingInformationForPackage($package);
    }

    /**
     * Removes a package from the file system.
     *
     * @param string|PackageKey $packageKey
     * @throws Exception
     * @throws Exception\ProtectedPackageKeyException
     * @throws Exception\UnknownPackageException
     * @internal
     */
    public function deletePackage($packageKey)
    {
        if (!$this->isPackageAvailable($packageKey)) {
            throw new UnknownPackageException('Package "' . $packageKey . '" is not available and cannot be removed.', 1166543253);
        }

        $package = $this->getPackage($packageKey);
        if ($package->isProtected()) {
            throw new ProtectedPackageKeyException('The package "' . $packageKey . '" is protected and cannot be removed.', 1220722120);
        }

        if ($this->isPackageActive($packageKey)) {
            $this->deactivatePackage($packageKey);
        }

        $this->unregisterPackage($package);
        $this->sortAndSavePackageStates();

        $packagePath = $package->getPackagePath();
        $deletion = GeneralUtility::rmdir($packagePath, true);
        if ($deletion === false) {
            throw new Exception('Please check file permissions. The directory "' . $packagePath . '" for package "' . $packageKey . '" could not be removed.', 1301491089);
        }
    }

    /**
     * Returns an array of \TYPO3\CMS\Core\Package objects of all active packages.
     * A package is active, if it is available and has been activated in the package
     * manager settings.
     *
     * @return array<array-key|PackageKey, PackageInterface>
     */
    public function getActivePackages(bool $includeAppPackage = false)
    {
        if (empty($this->activePackages) && !empty($this->packageStatesConfiguration['packages'])) {
            foreach ($this->packageStatesConfiguration['packages'] as $packageKey => $packageConfig) {
                $this->activePackages[$packageKey] = $this->getPackage($packageKey);
            }
        }
        $activePackages = $this->activePackages;
        if (!$includeAppPackage) {
            unset($activePackages[VirtualAppPackage::APP_PACKAGE_KEY]);
        }
        return $activePackages;
    }

    /**
     * Returns TRUE if a package was already registered or FALSE if it's not.
     *
     * @param string|PackageKey $packageKey
     * @return bool
     */
    protected function isPackageRegistered($packageKey)
    {
        $packageKey = $this->getPackageKeyFromComposerName($packageKey);

        return isset($this->packages[$packageKey]);
    }

    /**
     * Orders all active packages by comparing their dependencies. By this, the packages
     * and package configurations arrays holds all packages in the correct
     * initialization order.
     *
     * @return array<PackageKey, PackageConstraints>
     */
    protected function sortActivePackagesByDependencies()
    {
        $packagesWithDependencies = $this->resolvePackageDependencies($this->packageStatesConfiguration['packages']);

        // sort the packages by key at first, so we get a stable sorting of "equivalent" packages afterwards
        ksort($packagesWithDependencies);
        $sortedPackageKeys = $this->sortPackageStatesConfigurationByDependency($packagesWithDependencies);

        // Reorder the packages according to the loading order
        $this->packageStatesConfiguration['packages'] = [];
        foreach ($sortedPackageKeys as $packageKey) {
            $this->registerActivePackage($this->packages[$packageKey]);
        }
        return $packagesWithDependencies;
    }

    /**
     * Resolves the dependent packages from the meta data of all packages recursively. The
     * resolved direct or indirect dependencies of each package will put into the package
     * states configuration array.
     *
     * @param array<PackageKey, mixed> $packageConfig
     * @return array<PackageKey, PackageConstraints>
     */
    protected function resolvePackageDependencies($packageConfig)
    {
        $packagesWithDependencies = [];
        foreach ($packageConfig as $packageKey => $_) {
            $packagesWithDependencies[$packageKey]['dependencies'] = $this->getDependencyArrayForPackage($packageKey);
            $packagesWithDependencies[$packageKey]['suggestions'] = $this->getSuggestionArrayForPackage($packageKey);
        }
        return $packagesWithDependencies;
    }

    /**
     * Returns an array of suggested package keys for the given package.
     *
     * @param string|PackageKey $packageKey The package key to fetch the suggestions for
     * @return list<PackageKey>|null An array of directly suggested packages
     */
    protected function getSuggestionArrayForPackage($packageKey)
    {
        if (!isset($this->packages[$packageKey])) {
            return null;
        }
        $suggestedPackageKeys = [];
        $suggestedPackageConstraints = $this->packages[$packageKey]->getPackageMetaData()->getConstraintsByType(MetaData::CONSTRAINT_TYPE_SUGGESTS);
        foreach ($suggestedPackageConstraints as $constraint) {
            if ($constraint instanceof PackageConstraint) {
                $suggestedPackageName = $constraint->getValue();
                $suggestedPackageKey = $this->getPackageKeyFromComposerName($suggestedPackageName);
                if (isset($this->packages[$suggestedPackageKey])) {
                    $suggestedPackageKeys[] = $suggestedPackageKey;
                }
            }
        }
        return array_reverse($suggestedPackageKeys);
    }

    /**
     * Saves the current content of $this->packageStatesConfiguration to the
     * PackageStates.php file.
     *
     * @throws Exception\PackageStatesFileNotWritableException
     */
    protected function savePackageStates()
    {
        $this->packageStatesConfiguration['version'] = 5;

        $fileDescription = "# PackageStates.php\n\n";
        $fileDescription .= "# This file is maintained by TYPO3's package management. Although you can edit it\n";
        $fileDescription .= "# manually, you should rather use the extension manager for maintaining packages.\n";
        $fileDescription .= "# This file will be regenerated automatically if it doesn't exist. Deleting this file\n";
        $fileDescription .= "# should, however, never become necessary if you use the package commands.\n";

        if (!@is_writable($this->packageStatesPathAndFilename)) {
            // If file does not exist, try to create it
            $fileHandle = @fopen($this->packageStatesPathAndFilename, 'x');
            if (!$fileHandle) {
                throw new PackageStatesFileNotWritableException(
                    sprintf('We could not update the list of installed packages because the file %s is not writable. Please, check the file system permissions for this file and make sure that the web server can update it.', $this->packageStatesPathAndFilename),
                    1382449759
                );
            }
            fclose($fileHandle);
        }
        $packageConfiguration = $this->packageStatesConfiguration;
        // The VirtualAppPackage must never be written to PackageStates.php
        // It is either pulled from cache, or registered manually after
        // all real packages have been pulled in from disk
        unset($packageConfiguration['packages'][VirtualAppPackage::APP_PACKAGE_KEY]);
        $packageStatesCode = "<?php\n$fileDescription\nreturn " . ArrayUtility::arrayExport($packageConfiguration) . ";\n";
        GeneralUtility::writeFile($this->packageStatesPathAndFilename, $packageStatesCode, true);
        // Cache depends on package states file, therefore we invalidate it
        $this->packageCache->invalidate();

        GeneralUtility::makeInstance(OpcodeCacheService::class)->clearAllActive($this->packageStatesPathAndFilename);
    }

    /**
     * Saves the current content of $this->packageStatesConfiguration to the
     * PackageStates.php file.
     *
     * @throws Exception\PackageStatesFileNotWritableException
     */
    protected function sortAndSavePackageStates()
    {
        $this->sortActivePackagesByDependencies();
        $this->savePackageStates();
    }

    /**
     * Check the conformance of the given package key
     *
     * @param string|PackageKey $packageKey The package key to validate
     * @return bool If the package key is valid, returns TRUE otherwise FALSE
     */
    public function isPackageKeyValid($packageKey)
    {
        return preg_match(PackageInterface::PATTERN_MATCH_EXTENSIONKEY, $packageKey) === 1 || preg_match(PackageInterface::PATTERN_MATCH_COMPOSER_NAME, $packageKey) === 1 || preg_match(PackageInterface::PATTERN_MATCH_PACKAGEKEY, $packageKey) === 1;
    }

    /**
     * Returns an array of \TYPO3\CMS\Core\Package objects of all available packages.
     * A package is available, if the package directory contains valid meta information.
     *
     * @return array<array-key|PackageKey, PackageInterface> Array of PackageInterface
     */
    public function getAvailablePackages()
    {
        if ($this->availablePackagesScanned === false) {
            $this->scanAvailablePackages();
        }

        return $this->packages;
    }

    /**
     * Unregisters a package from the list of available packages
     *
     * @param PackageInterface $package The package to be unregistered
     * @throws Exception\InvalidPackageStateException
     * @internal
     */
    public function unregisterPackage(PackageInterface $package)
    {
        $packageKey = $package->getPackageKey();
        if (!$this->isPackageRegistered($packageKey)) {
            throw new InvalidPackageStateException('Package "' . $packageKey . '" is not registered.', 1338996142);
        }
        $this->unregisterPackageByPackageKey($packageKey);
    }

    /**
     * Reloads a package and its information
     *
     * @param string|PackageKey $packageKey
     * @throws Exception\InvalidPackageStateException if the package isn't available
     * @internal
     */
    public function reloadPackageInformation($packageKey)
    {
        if (!$this->isPackageRegistered($packageKey)) {
            throw new InvalidPackageStateException('Package "' . $packageKey . '" is not registered.', 1436201329);
        }

        $package = $this->packages[$packageKey];
        $packagePath = $package->getPackagePath();
        $newPackage = new Package($this, $packageKey, $packagePath);
        $this->packages[$packageKey] = $newPackage;
        unset($package);
    }

    /**
     * Returns contents of Composer manifest as a stdObject
     *
     * @return \stdClass
     * @throws InvalidPackageManifestException
     * @internal
     */
    public function getComposerManifest(string $manifestPath, bool $isBuildingPackageArtifact = false)
    {
        $composerManifest = new \stdClass();
        if (file_exists($manifestPath . 'composer.json')) {
            $json = file_get_contents($manifestPath . 'composer.json');
            if ($json !== false) {
                $composerManifest = json_decode($json);
            }
            if (!$composerManifest instanceof \stdClass) {
                throw new InvalidPackageManifestException('The composer.json found for extension "' . PathUtility::basename($manifestPath) . '" is invalid!', 1439555561);
            }
        }

        if ($isBuildingPackageArtifact
            // Framework packages (TYPO3 system extensions) derive their version from Typo3Version and are
            // not required to declare "providesPackages". Every other extension must declare the required
            // metadata in composer.json, since ext_emconf.php is no longer evaluated as a fallback for it.
            // @todo validate the contents and availability of the composer manifest instead of applying nullsafe fallbacks here
            || $this->isFrameworkPackage($composerManifest->name ?? '')
            || $this->declaresRequiredPackageMetadata($composerManifest)
        ) {
            return $composerManifest;
        }
        throw new InvalidPackageManifestException(
            sprintf(
                'The composer.json of extension "%s" must declare the extension version and the "providesPackages" definition in the "extra/typo3/cms" section. See %s for details.',
                $this->getPackageKeyFromManifest($composerManifest, $manifestPath),
                Typo3Information::getDocsLink('changelog:deprecation-108345-1774126701'),
            ),
            1780502553
        );
    }

    private function declaresRequiredPackageMetadata(\stdClass $manifest): bool
    {
        return isset($manifest->extra->{'typo3/cms'}->Package->providesPackages)
            && (
                ($manifest->version ?? null) !== null
                || isset($manifest->extra->{'typo3/cms'}->version)
            );
    }

    /**
     * Returns an array of dependent package keys for the given package. It will
     * do this recursively, so dependencies of dependent packages will also be
     * in the result.
     *
     * @param string|PackageKey $packageKey The package key to fetch the dependencies for
     * @param array $trace An array of already visited package keys, to detect circular dependencies
     * @return list<string>|null An array of direct or indirect dependent packages
     * @throws Exception\InvalidPackageKeyException
     */
    protected function getDependencyArrayForPackage($packageKey, array &$dependentPackageKeys = [], array $trace = [])
    {
        if (!isset($this->packages[$packageKey])) {
            return null;
        }
        if (in_array($packageKey, $trace, true) !== false) {
            return $dependentPackageKeys;
        }
        $trace[] = $packageKey;
        $dependentPackageConstraints = $this->packages[$packageKey]->getPackageMetaData()->getConstraintsByType(MetaData::CONSTRAINT_TYPE_DEPENDS);
        foreach ($dependentPackageConstraints as $constraint) {
            if ($constraint instanceof PackageConstraint) {
                $dependentPackageName = $constraint->getValue();
                // This check is done here for classic mode, to ignore "php" package for
                // dependency ordering of extensions. In Composer mode, packages won't have
                // this dependency tracked anymore at this point.
                if ($dependentPackageName === 'php') {
                    continue;
                }
                $dependentPackageKey = $this->getPackageKeyFromComposerName($dependentPackageName);
                if (in_array($dependentPackageKey, $dependentPackageKeys, true) === false && in_array($dependentPackageKey, $trace, true) === false) {
                    $dependentPackageKeys[] = $dependentPackageKey;
                }
                $this->getDependencyArrayForPackage($dependentPackageKey, $dependentPackageKeys, $trace);
            }
        }
        return array_reverse($dependentPackageKeys);
    }

    /**
     * Resolves package key from Composer manifest
     *
     * If it is a TYPO3 package the name of the containing directory will be used.
     *
     * Else if the composer name of the package matches the first part of the lowercased namespace of the package, the mixed
     * case version of the composer name / namespace will be used, with backslashes replaced by dots.
     *
     * Else the composer name will be used with the slash replaced by a dot
     *
     * @throws Exception\InvalidPackageManifestException
     */
    protected function getPackageKeyFromManifest(\stdClass $manifest, string $packagePath): string
    {
        if (!empty($manifest->extra->{'typo3/cms'}->{'extension-key'})) {
            return $manifest->extra->{'typo3/cms'}->{'extension-key'};
        }
        if (empty($manifest->name) || (isset($manifest->type) && str_starts_with($manifest->type, 'typo3-cms-'))) {
            throw new InvalidPackageManifestException('Invalid composer manifest (no extension key set) in package path: ' . $packagePath, 1348146451);
        }
        return $manifest->name;
    }

    /**
     * The order of paths is crucial for allowing overriding of system extension by local extensions.
     * Pay attention if you change order of the paths here.
     *
     * @return array{local?: string, system?: string}
     */
    protected function getPackageBasePaths()
    {
        if ($this->packagesBasePaths === []) {
            // Check if the directory even exists and if it is not empty
            if (is_dir(Environment::getExtensionsPath()) && $this->hasSubDirectories(Environment::getExtensionsPath())) {
                $this->packagesBasePaths['local'] = Environment::getExtensionsPath() . '/*/';
            }
            $this->packagesBasePaths['system'] = Environment::getFrameworkBasePath() . '/*/';
        }
        return $this->packagesBasePaths;
    }

    /**
     * Returns true if the given path has valid subdirectories, false otherwise.
     */
    protected function hasSubDirectories(string $path): bool
    {
        return !empty(glob(rtrim($path, '/\\') . '/*', GLOB_ONLYDIR));
    }

    /**
     * @param array<PackageKey, PackageConstraints> $packageStatesConfiguration
     * @return list<PackageKey> Returns the packageStatesConfiguration sorted by dependencies
     * @throws \UnexpectedValueException
     */
    protected function sortPackageStatesConfigurationByDependency(array $packageStatesConfiguration)
    {
        return $this->dependencyOrderingService->calculateOrder($this->buildDependencyGraph($packageStatesConfiguration));
    }

    /**
     * Convert the package configuration into a dependency definition
     *
     * This converts "dependencies" and "suggestions" to "after" syntax for the usage in DependencyOrderingService
     *
     * @param array $packageStatesConfiguration
     * @param array $packageKeys
     * @return array
     * @throws \UnexpectedValueException
     */
    protected function convertConfigurationForGraph(array $packageStatesConfiguration, array $packageKeys)
    {
        $dependencies = [];
        foreach ($packageKeys as $packageKey) {
            if (!isset($packageStatesConfiguration[$packageKey]['dependencies']) && !isset($packageStatesConfiguration[$packageKey]['suggestions'])) {
                continue;
            }
            $dependencies[$packageKey] = [
                'after' => [],
            ];
            if (isset($packageStatesConfiguration[$packageKey]['dependencies'])) {
                foreach ($packageStatesConfiguration[$packageKey]['dependencies'] as $dependentPackageKey) {
                    if (!in_array($dependentPackageKey, $packageKeys, true)) {
                        throw new \UnexpectedValueException(
                            'The package "' . $packageKey . '" depends on "'
                            . $dependentPackageKey . '" which is not present in the system.',
                            1519931815
                        );
                    }
                    $dependencies[$packageKey]['after'][] = $dependentPackageKey;
                }
            }
            if (isset($packageStatesConfiguration[$packageKey]['suggestions'])) {
                foreach ($packageStatesConfiguration[$packageKey]['suggestions'] as $suggestedPackageKey) {
                    // skip suggestions on not existing packages
                    if (in_array($suggestedPackageKey, $packageKeys, true)) {
                        // Suggestions actually have never been meant to influence loading order.
                        // We misuse this currently, as there is no other way to influence the loading order
                        // for not-required packages (soft-dependency).
                        // When considering suggestions for the loading order, we might create a cyclic dependency
                        // if the suggested package already has a real dependency on this package, so the suggestion
                        // has do be dropped in this case and must *not* be taken into account for loading order evaluation.
                        $dependencies[$packageKey]['after-resilient'][] = $suggestedPackageKey;
                    }
                }
            }
        }
        return $dependencies;
    }

    /**
     * Checks whether the given package name is a Composer dependency.
     * In classic mode some dedicated typo3 packages, PHP, composer-runtime-api
     * and PHP extensions are detected as Composer dependency.
     *
     * All other platform packages, if required, must be added to "providesPackages"
     *
     * @internal Only to be called within TYPO3\CMS\Core\Package namespace
     */
    public function isComposerDependency(string $packageName): bool
    {
        if ($this->isFrameworkPackage($packageName)) {
            return false;
        }
        return
            // PHP version
            $packageName === 'php'
            // Composer version
            || $packageName === 'composer-runtime-api'
            // PHP extension
            || str_starts_with($packageName, 'ext-')
            // Installed packages (mostly shipped packages)
            || in_array($packageName, $this->installedPackageNames, true);
    }

    /**
     * @internal Only to be called within TYPO3\CMS\Core\Package namespace
     */
    public function isFrameworkPackage(string $packageName): bool
    {
        if ($this->frameworkPackageNames === []) {
            $this->populateFrameworkAndComposerPackageNames();
        }
        return in_array($packageName, $this->frameworkPackageNames, true);
    }

    /**
     * Adds all root packages of current dependency graph as dependency to all extensions
     *
     * This ensures that the framework extensions (aka sysext) are
     * always loaded first, before any other external extension.
     *
     * @param array<PackageKey, PackageConstraints> $packageStateConfiguration
     * @param list<PackageKey> $rootPackageKeys
     * @return array<PackageKey, PackageConstraints>
     */
    protected function addDependencyToFrameworkToAllExtensions(array $packageStateConfiguration, array $rootPackageKeys)
    {
        $frameworkPackageKeys = $this->findFrameworkPackages($packageStateConfiguration);
        $extensionPackageKeys = array_diff(array_keys($packageStateConfiguration), $frameworkPackageKeys);
        foreach ($extensionPackageKeys as $packageKey) {
            // Remove framework packages from list
            $packageKeysWithoutFramework = array_diff(
                $packageStateConfiguration[$packageKey]['dependencies'],
                $frameworkPackageKeys
            );
            // The order of the array_merge is crucial here,
            // we want the framework first
            $packageStateConfiguration[$packageKey]['dependencies'] = array_merge(
                $rootPackageKeys,
                $packageKeysWithoutFramework
            );
        }
        return $packageStateConfiguration;
    }

    /**
     * Builds the dependency graph for all packages
     *
     * This method also introduces dependencies among the dependencies
     * to ensure the loading order is exactly as specified in the list.
     *
     * @param array<PackageKey, PackageConstraints> $packageStateConfiguration
     * @return array<array-key|PackageKey, array<array-key, bool>>
     */
    protected function buildDependencyGraph(array $packageStateConfiguration)
    {
        $frameworkPackageKeys = $this->findFrameworkPackages($packageStateConfiguration);
        $frameworkPackagesDependencyGraph = $this->dependencyOrderingService->buildDependencyGraph($this->convertConfigurationForGraph($packageStateConfiguration, $frameworkPackageKeys));
        $packageStateConfiguration = $this->addDependencyToFrameworkToAllExtensions($packageStateConfiguration, $this->dependencyOrderingService->findRootIds($frameworkPackagesDependencyGraph));

        $packageKeys = array_keys($packageStateConfiguration);
        return $this->dependencyOrderingService->buildDependencyGraph($this->convertConfigurationForGraph($packageStateConfiguration, $packageKeys));
    }

    /**
     * @param array<PackageKey, PackageConstraints> $packageStateConfiguration
     * @return list<PackageKey>
     */
    protected function findFrameworkPackages(array $packageStateConfiguration)
    {
        $frameworkPackageKeys = [];
        foreach ($packageStateConfiguration as $packageKey => $packageConfiguration) {
            $package = $this->getPackage($packageKey);
            if ($package->getPackageMetaData()->isFrameworkType()) {
                $frameworkPackageKeys[] = $packageKey;
            }
        }

        return $frameworkPackageKeys;
    }

    /**
     * @internal
     */
    public function warmupCaches(CacheWarmupEvent $event): void
    {
        if (Environment::isComposerMode()) {
            return;
        }
        if ($event->hasGroup('system')) {
            if (count($this->packageStatesConfiguration) === 0) {
                $this->loadPackageStates();
                $this->initializePackageObjects();
            }
            $this->validateResources();
            $this->saveToPackageCache();
        }
    }

    /**
     * Create PackageStates.php if missing and LocalConfiguration exists, used to have an Install Tool session running
     *
     * It is fired if PackageStates.php is deleted on a running instance,
     * all packages marked as "part of minimal system" are activated in this case.
     * @param bool $useFactoryDefault if true, use the "isPartOfFactoryDefault" otherwise use "isPartOfMinimalUsableSystem"
     * @internal
     */
    public function recreatePackageStatesFileIfMissing(bool $useFactoryDefault = false): void
    {
        if (!Environment::isComposerMode() && !file_exists($this->packageStatesPathAndFilename)) {
            $packages = $this->getAvailablePackages();
            foreach ($packages as $package) {
                if ($useFactoryDefault ? $package->isPartOfFactoryDefault() : $package->isPartOfMinimalUsableSystem()) {
                    $this->activatePackage($package->getPackageKey());
                }
            }

            $this->sortActivePackagesByDependencies();
            $this->savePackageStates();
        }
    }
}