<?php

namespace Civi\CompilePlugin;

use Composer\Package\PackageInterface;

class PackageSorter
{
	/**
	 * Given a list of installed packages sort such that dependant
	 * packages come after there dependencies.
	 *
	 * TODO handle cycles.
	 *
	 * @param PackageInterface[] $installedPackages
	 *   All installed packages, including the root.
	 * @return array
	 *   List of installed packages (sorted topologically).
	 *
	 *   Upstream packages with no dependencies come earlier than downstream packages that require them.
	 *
	 *   Ex: [0 => 'very-much/upstream', 1 => 'some-what/midstream', 2 => 'here-now/downstream']
	 */
	public static function sortPackages($installedPackages)
	{
		usort($installedPackages, function ($a, $b) {
		    return strnatcmp($a->getName(), $b->getName());
		});

		// Index mapping all known aliases (provides/replaces) to real names.
		// Array(string $logicalName => string $realName)
		$realNames = [];
		foreach ($installedPackages as $package) {
		    /** @var PackageInterface $package */
		    foreach ($package->getNames() as $alias) {
		        $realNames[$alias] = $package->getName();
		    }
		}

		// Array(string $realName => string[] $realNames)
		$realRequires = [];
		$addRealRequires = function ($package, $target) use (&$realRequires, &$realNames) {
		    if (isset($realNames[$target]) && $realNames[$target] !== $package) {
		        $realRequires[$package][] = $realNames[$target];
		    }
		};
		foreach ($installedPackages as $package) {
		    /** @var PackageInterface $package */
		    foreach ($package->getRequires() as $link) {
		        $addRealRequires($package->getName(), $link->getTarget());
		    }
		    // Unfortunately, cycles are common among suggests/dev-requires... ex: phpunit
		    //foreach ($package->getDevRequires() as $link) {
		    //    $addRealRequires($package->getName(), $link->getTarget());
		    //}
		    //foreach ($package->getSuggests() as $target => $comment) {
		    //    $addRealRequires($package->getName(), $target);
		    //}
		}

		// Unsorted list of packages that need to be visited.
		// Array(string $packageName => PackageInterface $package).
		$todoPackages = [];
		foreach ($installedPackages as $package) {
		    $todoPackages[$package->getName()] = $package;
		}

		// The topologically sorted packages, from least-dependent to most-dependent.
		// Array(string $packageName => PackageInterface $package)
		$sortedPackages = [];

		// A package is "ripe" when all its requirements are met.
		$isRipe = function (PackageInterface $pkg) use (&$sortedPackages, &$realRequires) {
		    foreach ($realRequires[$pkg->getName()] ?? [] as $target) {
		        if (!isset($sortedPackages[$target])) {
		             // printf("[%s] is not ripe due to [%s]\n", $pkg->getName(), $target);
		            return false;
		        }
		    }
		    // printf("[%s] is ripe\n", $pkg->getName());
		    return true;
		};

		// A package is "consumed" when we move it from $todoPackages to $sortedPackages.
		$consumePackage = function (PackageInterface $pkg) use (&$sortedPackages, &$todoPackages) {
		    $sortedPackages[$pkg->getName()] = $pkg;
		    unset($todoPackages[$pkg->getName()]);
		};

		// Main loop: Progressively move ripe packages from $todoPackages to $sortedPackages.
		while (!empty($todoPackages)) {
		    $ripePackages = array_filter($todoPackages, $isRipe);
		    if (empty($ripePackages)) {
		        $todoStr = implode(' ', array_map(
		            function ($p) {
		                return $p->getName();
		            },
		            $todoPackages
		        ));
		        throw new \RuntimeException("Error: Failed to find next installable package. Remaining: $todoStr");
		    }
		    foreach ($ripePackages as $package) {
		        $consumePackage($package);
		    }
		}

		return array_keys($sortedPackages);
	}
}
__halt_compiler();----SIGNATURE:----XJRsILg88qdvCmArxPAreBYAcE6pK6rSB+SMO/3FAAMAhtwdWNGP5aQ7AcsXMvEF2C2hYYDtVhY5yAT9X1/wRHN4/iz87ke+lgGNShDi65GAAf9YZIkUDjruh3/QnqEEsxQSZDLLYEzer8nFdEiWZQKgB0gJ8FU1qC8ygsh7Olw5cntsZetZwHJqr7yWlzDDD+CHsnIb9Xq0Q0RRwCEsPTriFn1b3rdl48V7e86s3VOzQyibmUBF16upnqFmNwWpBZ76MsHeDC59PrzJqeN3V+YMEmPSqYDvzb3r6ZBLGRxA1kFBkSE2wWiqp9kTIh2Udfcb9lrqvLN00vO0bkBfetEq2RckFFQWIBgSh8eAc1tD1mO3uM72n/aUCHaRcN1TTNEGG9nzA5BlASgz24iSlaHqS4Ae59j3I66Cb1ztqmZw+zoNPJUnLzhytCrMKZLQ0j6Ln/2jedrUGpTb3nkgOO6C3Unka7IWOwJyxwRylfflZdkyezlj07+EHGylq8Eu7yMhCkeXDvNdYvEOdOZQeW4Bm4L+03xNeheawG0iO2yMIlg26HsXG/MqdKPMJ0O6bDQvJ1Chkadskjeg/iCsfDTFhhJA0EjX1DPQZ5SgjPYieDaSf7nuGPgXHZnZFHeDCezOCjY+BvweAmFR+TH39Z7w4KQ5rBq879r++vN29fo=----ATTACHMENT:----NDk1MTI4NTI5NTA1OTU5OCA3MjM0NDg3NDM4ODgzOTk5IDE4MDE2NzgzMTMzMzc0ODk=