Issues with dependency logic in Util::addScript

The new dependency logic as implemented in #30015 is broken if dependencies themselves have dependencies. E.g. when text app depends on viewer and viewer depends on files, the script from text is loaded first while the script from viewer comes later:

The problem is that the files dependency of viewer moves viewer/js/viewer-main to the last element of files, while the viewer dependendy on text moves text/js/text-viewer to the last element of viewer. Viewer is before files but viewer no longer contains viewer/js/viewer-main, so loading text/js/text-viewer from last fails.

self::$scripts from

server/lib/public/Util.php

Line 243 in 791d570

$appScripts = array_map($mapFunc, self::$scripts);

when loading the Collectives app:

{
  "accessibility": {
    "first": [
      "accessibility/l10n/en",
      "accessibility/js/accessibilityoca"
    ]
  },
  "files_sharing": {
    "first": [
      "files_sharing/l10n/en",
      "files_sharing/js/dist/main"
    ]
  },
  "text": {
    "first": [
      "text/l10n/en"
    ]
  },
  "viewer": {
    "first": [
      "viewer/l10n/en"
    ],
    "last": [
      "text/js/text-viewer"
    ]
  },
  "files": {
    "first": [],
    "last": [
      "viewer/js/viewer-main"
    ]
  },
  "theming": {
    "first": [
      "theming/l10n/en",
      "theming/js/theming"
    ]
  },
  "user_status": {
    "first": [
      "user_status/l10n/en",
      "user_status/js/user-status-menu"
    ]
  },
  "core": {
    "first": [],
    "last": [
      "core/js/dist/unified-search"
    ]
  }
}

After removing files dependency from viewer (in https://github.com/nextcloud/viewer/pull/1081/files#diff-a14aae69340720190ddf327b54675eacd97116b45f5b57f583ddb52829a3f152R41):

{
  "accessibility": {
    "first": [
      "accessibility/l10n/en",
      "accessibility/js/accessibilityoca"
    ]
  },
  "files_sharing": {
    "first": [
      "files_sharing/l10n/en",
      "files_sharing/js/dist/main"
    ]
  },
  "text": {
    "first": [
      "text/l10n/en"
    ]
  },
  "viewer": {
    "first": [
      "viewer/l10n/en",
      "viewer/js/viewer-main"
    ],
    "last": [
      "text/js/text-viewer"
    ]
  },
  "theming": {
    "first": [
      "theming/l10n/en",
      "theming/js/theming"
    ]
  },
  "user_status": {
    "first": [
      "user_status/l10n/en",
      "user_status/js/user-status-menu"
    ]
  },
  "core": {
    "first": [],
    "last": [
      "core/js/dist/unified-search"
    ]
  }
}

So I guess we need to improve the logic and sort scripts by dependencies.

@skjnldsv

@skjnldsv and @juliushaertl

WIP: Sort app scripts by dependencies (Fixes: #30278)

I opened #30279 as a first attempt to fix this.

So I guess we need to improve the logic and sort scripts by dependencies.

https://en.wikipedia.org/wiki/Topological_sorting

WIP: Sort app scripts by dependencies (Fixes: #30278)

Sort app scripts by dependencies (Fixes: #30278)

I agree with you both. And I just realized that the whole dependency order logic is still flawed.

Now the problem is, that uksort() doesn't change the underlying array in place, so using array_search($array) inside the callable doesn't work as expected.

I spent another few hours with thinking and trying and by now I accepted that I won't find a cheap and simple way to sort the associative array self::$scripts by its dependencies.

Let's try a (probably incomplete) description of the problem we face:

When sorting the apps, we get an app to look at and optionally the dependency for the app if defined. If the app has a dependency defined, there's four basic options:
- app and dependency both not in our sorted list yet -> append dependency first, then app
- app not in sorted list, but dependency is -> append app
- app in sorted list, but dependency not -> insert dependency before the app
- app and dependency both in sorted list -> here it gets complicated:
  - order or app and dependency is correct -> nothing to do
  - order of app and dependency is incorrect -> WHAT TO DO HERE?

So let's have a look at the problem "app and dependeny both already in sorted list, but wrong order":

moving dependency before the app might break if this moves the dependency before its own dependencies
moving app after the the dependency might break if this moves the app after apps depending on it
swapping app and dependency might break for both reasons

Well, I guess I just described a theoretical problem of each dependency solving algorithm 😬

The best I could come up with so far, is an algorithm that works as described above. In case of the "app and dependency both already in sorted list, but wrong order", it chooses "move dependency before the app". That implementation passes the unit tests and all manual testing that broke earlier (different subsets of collectives and deck app enabled and browsing files, collectives and deck app respectively). So it's certainly better than what we had so far, but probably not perfect:

		$sortedScripts = [];
		foreach (array_keys(self::$scripts) as $app) {
			$dep = self::$scriptDeps[$app] ?? false;
			if (!array_key_exists($app, $sortedScripts)) {
				// app not listed yet
				if ($dep && !array_key_exists($dep, $sortedScripts)) {
					// add dependency if defined and not listed
					$sortedScripts[$dep] = self::$scripts[$dep] ?? [];
				}
				$sortedScripts[$app] = self::$scripts[$app];
			} elseif ($dep) {
				// app listed and dependency defined
				$appPos = array_search($app, array_keys($sortedScripts), true);
				$depPos = array_search($dep, array_keys($sortedScripts), true);
				if ($depPos !== false) {
					if ($appPos < $depPos) {
						// app and dependency listed, but wrong order
						// -> move dep before app by slicing and merging array
						$depScripts = $sortedScripts[$dep];
						$withoutDepScripts =
							array_slice($sortedScripts, 0, $depPos - 1, true) +
							array_slice($sortedScripts, $depPos - 1, NULL, true);
						$sortedScripts =
							array_slice($withoutDepScripts, 0, $appPos, true) +
							[$dep => $depScripts] +
							array_slice($withoutDepScripts, $appPos, NULL, true);
					}
				} else {
					// app listed, dependency not
					// -> insert dependency before app by slicing and merging array
					$sortedScripts =
						array_slice($sortedScripts, 0, $appPos - 1, true) +
						[$dep => self::$scripts[$dep] ?? []] +
						array_slice($sortedScripts, $appPos - 1, NULL, true);
				}
			}
		}

		// sort core first
		$scripts = array_merge($sortedScripts['core'] ?? [], ...array_values($sortedScripts));

		// Flatten array and remove duplicates
		return array_unique($scripts);

Use a topological sort algorithm. It solves your Problem with the ordering.

I was a bit reluctant to add a PHP dependency for this, but seems like https://github.com/marcj/topsort.php is nice and clean. Shall we use it? I could give it a try. But I didn't contribute much to the server code yet (still kind of a newbie here 😉), and to be honest I don't feel confident enough to take such a decision.

Also, performance is really critical here, as getScripts() is run at the beginning of every browser request, right? Maybe we should even think about caching dependency chains (.e.g using a hash of alphabetical order of all apps in the list as indices)?

Sort app scripts topologically by its dependencies

I couldn't resist and implemented a stripped down version of https://github.com/marcj/topsort.php: #30385

Related unit tests and manuall tests pass 🎉

Sort app scripts topologically by its dependencies

Navigation Menu

Repository navigation

Issues with dependency logic in `Util::addScript` #30278

8 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issues with dependency logic in Util::addScript #30278

Description

Activity

mejo- commented on Dec 15, 2021

mejo- commented on Dec 15, 2021

ChristophWurst commented on Dec 16, 2021

8 remaining items

mejo- commented on Dec 22, 2021

mejo- commented on Dec 22, 2021

ChristophWurst commented on Dec 22, 2021

mejo- commented on Dec 22, 2021

mejo- commented on Dec 23, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

Issues with dependency logic in `Util::addScript` #30278