[pkgman] Let pkgman list leaf packages

[haikupr]

I was trying to shrink the number of installed packages in order to quicken my Haiku's boot time. In order to do so I searched for a canned way to list all the installed leaf packages, ie. the ones which were once installed as a dependency be are now useless to the set of installed packages, and those I could remove safely. I found no easy way to obtain that list. Would it be possible to expand pkgman to be able to only list leaf package? Command line usage could look like pkgman search --leaf or something similar.

[waddlesplash]

I thought we had a ticket similar to this already, but now I can't find it.

[humdinger]

This one: #15567 ?

[waddlesplash]

Indeed so.

[madmax]

Not exactly what you want, but until the function is implemented ​this script can give you a subset of the packages that no other package depends on. Notice though it doesn't know whether they came as a dependency or you installed them yourself.

[bipolar]

Somewhat similar to madmax's script, there's my ​`pkgman search --not-required` proof of concept :-)

Some months ago, I implemented that search --not-required in pkgman proper in two ways:

• ​The first one following that naive/quick-and-dirty implementation (slightly inaccurate, pretty fast!).
• ​the second, more accurate (takes versions into account), but scales poorly with the number of packages.

When used to only list *installed* packages that are not required, both take < 0.25s (having 500+ packages installed), but when doing it for ALL packages, the second version takes around 15 seconds, IIRC (on my Phenom II VM).

I should probably give it another go, and at least submit the second for review, in hopes there's anything salvageable.

Maybe something better can be written, and added to PackageKit's LibsolvSolver::FindPackages(), for example? (task for better programmers than I).

[waddlesplash]

I don't think something could be added to FindPackages, but what about using a BSolverPackageSpecifierList, adding all the requirements to that, using the Solver to get back a BObjectList<BSolverPackage> of all the packages required, and then excluding all the packages that were in that set?

[waddlesplash]

I played around with this for a while but couldn't manage to get anything to work. Ultimately what I came up with was:

static void
filter_required_packages(const BPackageManager& packageManager,
	BObjectList<BSolverPackage>& packages)
{
	std::set<BSolverPackage*> packagesSet;
	BSolverPackageSpecifierList requirements;
	for (int32 i = 0; i < packages.CountItems(); i++) {
		BSolverPackage* package = packages.ItemAt(i);
		if (package->Name().EndsWith("_source") || package->Name().EndsWith("_debuginfo"))
			continue;

		packagesSet.insert(package);

		BObjectList<BPackageResolvableExpression> requiresList
			= package->Info().RequiresList();
		for (int32 j = 0; j < requiresList.CountItems(); j++)
			requirements.AppendSpecifier(requiresList.ItemAt(j)->Name());
	}
	packages.MakeEmpty();

	BObjectList<BSolverPackage> requiredPackages;
	const BSolverPackageSpecifier* unmatched;
	status_t status = packageManager.Solver()->FindPackages(requirements,
		BSolver::B_FIND_INSTALLED_ONLY, requiredPackages, &unmatched);
	if (status != B_OK) {
		fprintf(stderr, "Failed to filter required packages: %s\n", strerror(status));
		if (unmatched != NULL)
			fprintf(stderr, "\t(unmatched: %s)\n", unmatched->SelectString().String());
		return;
	}

	for (int32 i = 0; i < requiredPackages.CountItems(); i++)
		packagesSet.erase(requiredPackages.ItemAt(i));

	std::set<BSolverPackage*>::const_iterator setIterator = packagesSet.begin();
	for (; setIterator != packagesSet.end(); setIterator++)
		packages.AddItem(*setIterator);
}

But this doesn't work because FindPackages just bails immediately claiming it can't find a package matching "haiku". (It's worth noting this uses a different codepath than the regular FindPackages and a different search mechanism; I don't know what else in the code even uses that mechanism, so I don't know whether it works or not.) Additionally it doesn't look very efficient anyway; it just iterates over the whole requirement list and adds packages that match each requirement one by one, rather than all-at-once.

[bipolar]

Mmm, thanks for the pointer! Whatever I can use to transform my ​three nested for loops into something with a lower O() would help a lot!

PackageFS code gives me a headache each time I look at it, but... I will try to give it another go, and see if I can find the right classes/methods to call :-)

Thanks again.

Edit: oops! didn't see your follow up message before posting my reply, waddlesplash. Welp... if it isn't straight forward even for you... I doubt I'll do any better than my first attempt :-D

[waddlesplash]

I really think there should be some way to do this with libsolv, I just am not familiar enough to know what it is. There are a bunch of ways your code could be reworked to a lower O(), I just don't know if that's the route we should take...

[bipolar]

Replying to waddlesplash:

I just don't know if that's the route we should take...

Indeed. I was just brute-forcing it (due to my limited skillset), thus why I didn't even send it for review, and why I hoped that something better could be added to libsolv itself (assuming it wasn't there already, and I just missed it).

Beats not having that info available, if you need it, but... I would also hope for having a better way of getting it :-)

[madmax]

Replying to waddlesplash:

But this doesn't work because FindPackages just bails immediately claiming it can't find a package matching "haiku".

For whatever reason it does work passing flag = 0. And you'll also want ToString() instead of Name() for the requires expression so that it also uses the version and outputs old not required versions of icu, ffmpeg and that kind of packages.

[madmax]

Replying to waddlesplash:

I really think there should be some way to do this with libsolv, I just am not familiar enough to know what it is.

Not familiar either, but browsing SUSE's zypper (and libzypp), I see they use ​solver_get_unneeded.

I also came across SOLVER_CLEANDEPS flag, which might be useful to automatically remove dependencies brought by a package when uninstalling it.

[waddlesplash]

For whatever reason it does work passing flag = 0.

Interesting.

And you'll also want ToString() instead of Name()

I initially did use ToString() but got the same error, so I thought maybe that mode didn't support version restrictions or something.

which might be useful to automatically remove dependencies brought by a package when uninstalling it.

Ultimately we should just store/mark all user-installed packages so "autoremove" and CLEANDEPS can work properly.

[waddlesplash]

On a related note, I think we should move to using a vendored libsolv in-tree rather than the package. Something so critical to package management infrastructure should be managed along with the OS, not as a separate package. We haven't upgraded it for a decade in part because of fear that an upgrade would break something and wouldn't be easily fixed.

[waddlesplash]

Fixed in hrev58434, based on OscarL's version with the real dependency resolver as drafted above plus madmax's tweak and some more error handling.

[haikupr]

After updating to hrev58436, it looks to be inoperative:

~> pkgman search -n
Failed to filter required packages: Name not found
        (unmatched: kirigami_addons1>=1.5.0, required by itinerary)

Itinerary is not installed, Kirigami neither is.

[waddlesplash]

As noted in the commit message, you need to use "-i" for installed-only. Otherwise it'll list all "leaf" package even among those not installed.

[haikupr]

I'm sorry, I let assumptions gained from other OSes drive my test.

Shouldn't -i be implicit when -n is used since -n looks to be useless without -i? I'm sure I will not be the only one to fall in that pit, covering it could be a good thing.

[waddlesplash]

It's not useless, if there weren't inconsistencies in the remote repository then it'd list all the "leaf" packages in the remote repository too.