1
0

AppScriptSort.php 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105
  1. <?php
  2. /**
  3. * @copyright Copyright (c) 2021, Jonas Meurer <jonas@freesources.org>
  4. *
  5. * @author Jonas Meurer <jonas@freesources.org>
  6. *
  7. * @license GNU AGPL version 3 or any later version
  8. *
  9. * This program is free software: you can redistribute it and/or modify
  10. * it under the terms of the GNU Affero General Public License as
  11. * published by the Free Software Foundation, either version 3 of the
  12. * License, or (at your option) any later version.
  13. *
  14. * This program is distributed in the hope that it will be useful,
  15. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  17. * GNU Affero General Public License for more details.
  18. *
  19. * You should have received a copy of the GNU Affero General Public License
  20. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  21. *
  22. */
  23. namespace OC;
  24. use Psr\Log\LoggerInterface;
  25. /**
  26. * Sort scripts topologically by their dependencies
  27. * Implementation based on https://github.com/marcj/topsort.php
  28. */
  29. class AppScriptSort {
  30. /** @var LoggerInterface */
  31. private $logger;
  32. public function __construct(LoggerInterface $logger) {
  33. $this->logger = $logger;
  34. }
  35. /**
  36. * Recursive topological sorting
  37. *
  38. * @param AppScriptDependency $app
  39. * @param array $parents
  40. * @param array $scriptDeps
  41. * @param array $sortedScriptDeps
  42. */
  43. private function topSortVisit(
  44. AppScriptDependency $app,
  45. array &$parents,
  46. array &$scriptDeps,
  47. array &$sortedScriptDeps): void {
  48. // Detect and log circular dependencies
  49. if (isset($parents[$app->getId()])) {
  50. $this->logger->error('Circular dependency in app scripts at app ' . $app->getId());
  51. }
  52. // If app has not been visited
  53. if (!$app->isVisited()) {
  54. $parents[$app->getId()] = true;
  55. $app->setVisited(true);
  56. foreach ($app->getDeps() as $dep) {
  57. if ($app->getId() === $dep) {
  58. // Ignore dependency on itself
  59. continue;
  60. }
  61. if (isset($scriptDeps[$dep])) {
  62. $newParents = $parents;
  63. $this->topSortVisit($scriptDeps[$dep], $newParents, $scriptDeps, $sortedScriptDeps);
  64. }
  65. }
  66. $sortedScriptDeps[] = $app->getId();
  67. }
  68. }
  69. /**
  70. * @return array scripts sorted by dependencies
  71. */
  72. public function sort(array $scripts, array $scriptDeps): array {
  73. // Sort scriptDeps into sortedScriptDeps
  74. $sortedScriptDeps = [];
  75. foreach ($scriptDeps as $app) {
  76. $parents = [];
  77. $this->topSortVisit($app, $parents, $scriptDeps, $sortedScriptDeps);
  78. }
  79. // Sort scripts into sortedScripts based on sortedScriptDeps order
  80. $sortedScripts = [];
  81. foreach ($sortedScriptDeps as $app) {
  82. $sortedScripts[$app] = $scripts[$app] ?? [];
  83. }
  84. // Add remaining scripts
  85. foreach (array_keys($scripts) as $app) {
  86. if (!isset($sortedScripts[$app])) {
  87. $sortedScripts[$app] = $scripts[$app];
  88. }
  89. }
  90. return $sortedScripts;
  91. }
  92. }