Na}{

File Content: `PoolOptimizer.php`

<?php

/*
 * This file is part of Composer.
 *
 * (c) Nils Adermann <naderman@naderman.de>
 *     Jordi Boggiano <j.boggiano@seld.be>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Composer\DependencyResolver;

use Composer\Package\AliasPackage;
use Composer\Package\BasePackage;
use Composer\Package\Version\VersionParser;
use Composer\Semver\CompilingMatcher;
use Composer\Semver\Constraint\ConstraintInterface;
use Composer\Semver\Constraint\Constraint;
use Composer\Semver\Constraint\MultiConstraint;
use Composer\Semver\Intervals;

/**
 * Optimizes a given pool
 *
 * @author Yanick Witschi <yanick.witschi@terminal42.ch>
 */
class PoolOptimizer
{
    /**
     * @var PolicyInterface
     */
    private $policy;

    /**
     * @var array<int, true>
     */
    private $irremovablePackages = array();

    /**
     * @var array<string, array<string, ConstraintInterface>>
     */
    private $requireConstraintsPerPackage = array();

    /**
     * @var array<string, array<string, ConstraintInterface>>
     */
    private $conflictConstraintsPerPackage = array();

    /**
     * @var array<int, true>
     */
    private $packagesToRemove = array();

    /**
     * @var array<int, BasePackage[]>
     */
    private $aliasesPerPackage = array();

    /**
     * @var array<string, array<string, string>>
     */
    private $removedVersionsByPackage = array();

    public function __construct(PolicyInterface $policy)
    {
        $this->policy = $policy;
    }

    /**
     * @return Pool
     */
    public function optimize(Request $request, Pool $pool)
    {
        $this->prepare($request, $pool);

        $this->optimizeByIdenticalDependencies($request, $pool);

        $this->optimizeImpossiblePackagesAway($request, $pool);

        $optimizedPool = $this->applyRemovalsToPool($pool);

        // No need to run this recursively at the moment
        // because the current optimizations cannot provide
        // even more gains when ran again. Might change
        // in the future with additional optimizations.

        $this->irremovablePackages = array();
        $this->requireConstraintsPerPackage = array();
        $this->conflictConstraintsPerPackage = array();
        $this->packagesToRemove = array();
        $this->aliasesPerPackage = array();
        $this->removedVersionsByPackage = array();

        return $optimizedPool;
    }

    /**
     * @return void
     */
    private function prepare(Request $request, Pool $pool)
    {
        $irremovablePackageConstraintGroups = array();

        // Mark fixed or locked packages as irremovable
        foreach ($request->getFixedOrLockedPackages() as $package) {
            $irremovablePackageConstraintGroups[$package->getName()][] = new Constraint('==', $package->getVersion());
        }

        // Extract requested package requirements
        foreach ($request->getRequires() as $require => $constraint) {
            $constraint = Intervals::compactConstraint($constraint);
            $this->requireConstraintsPerPackage[$require][(string) $constraint] = $constraint;
        }

        // First pass over all packages to extract information and mark package constraints irremovable
        foreach ($pool->getPackages() as $package) {
            // Extract package requirements
            foreach ($package->getRequires() as $link) {
                $constraint = Intervals::compactConstraint($link->getConstraint());
                $this->requireConstraintsPerPackage[$link->getTarget()][(string) $constraint] = $constraint;
            }
            // Extract package conflicts
            foreach ($package->getConflicts() as $link) {
                $constraint = Intervals::compactConstraint($link->getConstraint());
                $this->conflictConstraintsPerPackage[$link->getTarget()][(string) $constraint] = $constraint;
            }

            // Keep track of alias packages for every package so if either the alias or aliased is kept
            // we keep the others as they are a unit of packages really
            if ($package instanceof AliasPackage) {
                $this->aliasesPerPackage[$package->getAliasOf()->id][] = $package;
            }
        }

        $irremovablePackageConstraints = array();
        foreach ($irremovablePackageConstraintGroups as $packageName => $constraints) {
            $irremovablePackageConstraints[$packageName] = 1 === \count($constraints) ? $constraints[0] : new MultiConstraint($constraints, false);
        }
        unset($irremovablePackageConstraintGroups);

        // Mark the packages as irremovable based on the constraints
        foreach ($pool->getPackages() as $package) {
            if (!isset($irremovablePackageConstraints[$package->getName()])) {
                continue;
            }

            if (CompilingMatcher::match($irremovablePackageConstraints[$package->getName()], Constraint::OP_EQ, $package->getVersion())) {
                $this->markPackageIrremovable($package);
            }
        }
    }

    /**
     * @return void
     */
    private function markPackageIrremovable(BasePackage $package)
    {
        $this->irremovablePackages[$package->id] = true;
        if ($package instanceof AliasPackage) {
            // recursing here so aliasesPerPackage for the aliasOf can be checked
            // and all its aliases marked as irremovable as well
            $this->markPackageIrremovable($package->getAliasOf());
        }
        if (isset($this->aliasesPerPackage[$package->id])) {
            foreach ($this->aliasesPerPackage[$package->id] as $aliasPackage) {
                $this->irremovablePackages[$aliasPackage->id] = true;
            }
        }
    }

    /**
     * @return Pool Optimized pool
     */
    private function applyRemovalsToPool(Pool $pool)
    {
        $packages = array();
        $removedVersions = array();
        foreach ($pool->getPackages() as $package) {
            if (!isset($this->packagesToRemove[$package->id])) {
                $packages[] = $package;
            } else {
                $removedVersions[$package->getName()][$package->getVersion()] = $package->getPrettyVersion();
            }
        }

        $optimizedPool = new Pool($packages, $pool->getUnacceptableFixedOrLockedPackages(), $removedVersions, $this->removedVersionsByPackage);

        return $optimizedPool;
    }

    /**
     * @return void
     */
    private function optimizeByIdenticalDependencies(Request $request, Pool $pool)
    {
        $identicalDefinitionsPerPackage = array();
        $packageIdenticalDefinitionLookup = array();

        foreach ($pool->getPackages() as $package) {

            // If that package was already marked irremovable, we can skip
            // the entire process for it
            if (isset($this->irremovablePackages[$package->id])) {
                continue;
            }

            $this->markPackageForRemoval($package->id);

            $dependencyHash = $this->calculateDependencyHash($package);

            foreach ($package->getNames(false) as $packageName) {

                if (!isset($this->requireConstraintsPerPackage[$packageName])) {
                    continue;
                }

                foreach ($this->requireConstraintsPerPackage[$packageName] as $requireConstraint) {
                    $groupHashParts = array();

                    if (CompilingMatcher::match($requireConstraint, Constraint::OP_EQ, $package->getVersion())) {
                        $groupHashParts[] = 'require:' . (string) $requireConstraint;
                    }

                    if ($package->getReplaces()) {
                        foreach ($package->getReplaces() as $link) {
                            if (CompilingMatcher::match($link->getConstraint(), Constraint::OP_EQ, $package->getVersion())) {
                                // Use the same hash part as the regular require hash because that's what the replacement does
                                $groupHashParts[] = 'require:' . (string) $link->getConstraint();
                            }
                        }
                    }

                    if (isset($this->conflictConstraintsPerPackage[$packageName])) {
                        foreach ($this->conflictConstraintsPerPackage[$packageName] as $conflictConstraint) {
                            if (CompilingMatcher::match($conflictConstraint, Constraint::OP_EQ, $package->getVersion())) {
                                $groupHashParts[] = 'conflict:' . (string) $conflictConstraint;
                            }
                        }
                    }

                    if (!$groupHashParts) {
                        continue;
                    }

                    $groupHash = implode('', $groupHashParts);
                    $identicalDefinitionsPerPackage[$packageName][$groupHash][$dependencyHash][] = $package;
                    $packageIdenticalDefinitionLookup[$package->id][$packageName] = array('groupHash' => $groupHash, 'dependencyHash' => $dependencyHash);
                }
            }
        }

        foreach ($identicalDefinitionsPerPackage as $constraintGroups) {
            foreach ($constraintGroups as $constraintGroup) {
                foreach ($constraintGroup as $packages) {
                    // Only one package in this constraint group has the same requirements, we're not allowed to remove that package
                    if (1 === \count($packages)) {
                        $this->keepPackage($packages[0], $identicalDefinitionsPerPackage, $packageIdenticalDefinitionLookup);
                        continue;
                    }

                    // Otherwise we find out which one is the preferred package in this constraint group which is
                    // then not allowed to be removed either
                    $literals = array();

                    foreach ($packages as $package) {
                        $literals[] = $package->id;
                    }

                    foreach ($this->policy->selectPreferredPackages($pool, $literals) as $preferredLiteral) {
                        $this->keepPackage($pool->literalToPackage($preferredLiteral), $identicalDefinitionsPerPackage, $packageIdenticalDefinitionLookup);
                    }
                }
            }
        }
    }

    /**
     * @return string
     */
    private function calculateDependencyHash(BasePackage $package)
    {
        $hash = '';

        $hashRelevantLinks = array(
            'requires' => $package->getRequires(),
            'conflicts' => $package->getConflicts(),
            'replaces' => $package->getReplaces(),
            'provides' => $package->getProvides()
        );

        foreach ($hashRelevantLinks as $key => $links) {
            if (0 === \count($links)) {
                continue;
            }

            // start new hash section
            $hash .= $key . ':';

            $subhash = array();

            foreach ($links as $link) {
                // To get the best dependency hash matches we should use Intervals::compactConstraint() here.
                // However, the majority of projects are going to specify their constraints already pretty
                // much in the best variant possible. In other words, we'd be wasting time here and it would actually hurt
                // performance more than the additional few packages that could be filtered out would benefit the process.
                $subhash[$link->getTarget()] = (string) $link->getConstraint();
            }

            // Sort for best result
            ksort($subhash);

            foreach ($subhash as $target => $constraint) {
                $hash .= $target . '@' . $constraint;
            }
        }

        return $hash;
    }

    /**
     * @param int $id
     * @return void
     */
    private function markPackageForRemoval($id)
    {
        // We are not allowed to remove packages if they have been marked as irremovable
        if (isset($this->irremovablePackages[$id])) {
            throw new \LogicException('Attempted removing a package which was previously marked irremovable');
        }

        $this->packagesToRemove[$id] = true;
    }

    /**
     * @param array<string, array<string, array<string, list<BasePackage>>>> $identicalDefinitionsPerPackage
     * @param array<int, array<string, array{groupHash: string, dependencyHash: string}>> $packageIdenticalDefinitionLookup
     * @return void
     */
    private function keepPackage(BasePackage $package, $identicalDefinitionsPerPackage, $packageIdenticalDefinitionLookup)
    {
        unset($this->packagesToRemove[$package->id]);

        if ($package instanceof AliasPackage) {
            // recursing here so aliasesPerPackage for the aliasOf can be checked
            // and all its aliases marked to be kept as well
            $this->keepPackage($package->getAliasOf(), $identicalDefinitionsPerPackage, $packageIdenticalDefinitionLookup);
        }

        // record all the versions of the package group so we can list them later in Problem output
        foreach ($package->getNames(false) as $name) {
            if (isset($packageIdenticalDefinitionLookup[$package->id][$name])) {
                $packageGroupPointers = $packageIdenticalDefinitionLookup[$package->id][$name];
                $packageGroup = $identicalDefinitionsPerPackage[$name][$packageGroupPointers['groupHash']][$packageGroupPointers['dependencyHash']];
                foreach ($packageGroup as $pkg) {
                    if ($pkg instanceof AliasPackage && $pkg->getPrettyVersion() === VersionParser::DEFAULT_BRANCH_ALIAS) {
                        $pkg = $pkg->getAliasOf();
                    }
                    $this->removedVersionsByPackage[spl_object_hash($package)][$pkg->getVersion()] = $pkg->getPrettyVersion();
                }
            }
        }

        if (isset($this->aliasesPerPackage[$package->id])) {
            foreach ($this->aliasesPerPackage[$package->id] as $aliasPackage) {
                unset($this->packagesToRemove[$aliasPackage->id]);

                // record all the versions of the package group so we can list them later in Problem output
                foreach ($aliasPackage->getNames(false) as $name) {
                    if (isset($packageIdenticalDefinitionLookup[$aliasPackage->id][$name])) {
                        $packageGroupPointers = $packageIdenticalDefinitionLookup[$aliasPackage->id][$name];
                        $packageGroup = $identicalDefinitionsPerPackage[$name][$packageGroupPointers['groupHash']][$packageGroupPointers['dependencyHash']];
                        foreach ($packageGroup as $pkg) {
                            if ($pkg instanceof AliasPackage && $pkg->getPrettyVersion() === VersionParser::DEFAULT_BRANCH_ALIAS) {
                                $pkg = $pkg->getAliasOf();
                            }
                            $this->removedVersionsByPackage[spl_object_hash($aliasPackage)][$pkg->getVersion()] = $pkg->getPrettyVersion();
                        }
                    }
                }
            }
        }
    }

    /**
     * Use the list of locked packages to constrain the loaded packages
     * This will reduce packages with significant numbers of historical versions to a smaller number
     * and reduce the resulting rule set that is generated
     *
     * @return void
     */
    private function optimizeImpossiblePackagesAway(Request $request, Pool $pool)
    {
        if (count($request->getLockedPackages()) === 0) {
            return;
        }

        $packageIndex = array();

        foreach ($pool->getPackages() as $package) {
            $id = $package->id;

            // Do not remove irremovable packages
            if (isset($this->irremovablePackages[$id])) {
                continue;
            }
            // Do not remove a package aliased by another package, nor aliases
            if (isset($this->aliasesPerPackage[$id]) || $package instanceof AliasPackage) {
                continue;
            }
            // Do not remove locked packages
            if ($request->isFixedPackage($package) || $request->isLockedPackage($package)) {
                continue;
            }

            $packageIndex[$package->getName()][$package->id] = $package;
        }

        foreach ($request->getLockedPackages() as $package) {
            // If this locked package is no longer required by root or anything in the pool, it may get uninstalled so do not apply its requirements
            // In a case where a requirement WERE to appear in the pool by a package that would not be used, it would've been unlocked and so not filtered still
            $isUnusedPackage = true;
            foreach ($package->getNames(false) as $packageName) {
                if (isset($this->requireConstraintsPerPackage[$packageName])) {
                    $isUnusedPackage = false;
                    break;
                }
            }

            if ($isUnusedPackage) {
                continue;
            }

            foreach ($package->getRequires() as $link) {
                $require = $link->getTarget();
                if (!isset($packageIndex[$require])) {
                    continue;
                }

                $linkConstraint = $link->getConstraint();
                foreach ($packageIndex[$require] as $id => $requiredPkg) {
                    if (false === CompilingMatcher::match($linkConstraint, Constraint::OP_EQ, $requiredPkg->getVersion())) {
                        $this->markPackageForRemoval($id);
                        unset($packageIndex[$require][$id]);
                    }
                }
            }
        }
    }
}
Name	Size	Permission
Operation	---	0755
Decisions.php	7391 bytes	0644
DefaultPolicy.php	7674 bytes	0644
GenericRule.php	1955 bytes	0644
LocalRepoTransaction.php	789 bytes	0644
LockTransaction.php	5727 bytes	0644
MultiConflictRule.php	2615 bytes	0644
PolicyInterface.php	905 bytes	0644
Pool.php	8656 bytes	0644
PoolBuilder.php	30872 bytes	0644
PoolOptimizer.php	17838 bytes	0644
Problem.php	27720 bytes	0644
Request.php	8234 bytes	0644
Rule.php	20386 bytes	0644
Rule2Literals.php	2684 bytes	0644
RuleSet.php	5140 bytes	0644
RuleSetGenerator.php	13455 bytes	0644
RuleSetIterator.php	2928 bytes	0644
RuleWatchChain.php	1469 bytes	0644
RuleWatchGraph.php	6487 bytes	0644
RuleWatchNode.php	2932 bytes	0644
Solver.php	26801 bytes	0644
SolverBugException.php	812 bytes	0644
SolverProblemsException.php	5622 bytes	0644
Transaction.php	13968 bytes	0644
Command Bosku:

File Content: PoolOptimizer.php

File Content: `PoolOptimizer.php`
