[Aptitude-devel] Search term for existence

[Martin Stjernholm]

Daniel Burrows <dburrows at debian.org> wrote:

>>   ?for p: (?=p
>>            ?exists(?provides(?=p) ?automatic)
>>            ?exists(?provides(?=p) !?installed))
>
>   I see.  BTW, "?for p: ?=p" is a synonym for "?true". :-)

Ah yes, the ?exists clauses by themselves would have sufficed.

>   But IMO what you really want is:
>
>   ?for p: ?reverse-depends(?depends(!?widen(?installed)
>                                     !(?widen(?=p) |
>                                        ?reverse-provides(?widen(?=p)))))
>
>
>   i.e., what has a reverse-dependency that has a dependency that
> is not the same package as p.  (?widen is probably redundant here, but
> I added it for clarity)  This will return packages that are part of an
> ORed dependency and packages that are a real package provided by
> something else.

I get way too many packages when I try that, e.g. essentially every
library I've got installed (I have practically the whole libs section
marked auto, of course). I think the reason is that the ?depends step
goes to _all_ dependencies of those packages, not just "back" along
the same dependency path.

But I think I understand what you're getting at. After tinkering
around a bit, I arrived at this:

  ?automatic
  ?for p: (?provides(?reverse-provides(
                       ?widen(?provides(?reverse-provides(?=p)))
                       !?widen(?installed)))
	   |
	   ?reverse-provides(
	     ?widen(?provides(?=p))
	     !?widen(?installed)))

The first clause in the "|" takes care of package names provided by a
an auto package, and the second cater for other packages that directly
provide an auto package. And all those ?widen do really make a
difference.

To delve into the first clause a bit more: The bit
"?widen(?provides(?reverse-provides(?=p)))" expands to all
alternatives that provide the same package name(s) as p. Then it's
filtered with the uninstalled packages. Then there's another
"?provides(?reverse-provides(...))" around it all to get back to p.
That's a part that would intuitively be replaced by an ?exists, but I
guess being forced to think it through more carefully makes the query
more efficient in this case.

Then to finish it up I added a check that the provided package names
actually are needed to fulfill a dependency of some installed package,
and also filter out essential packages since they aren't ambiguous no
matter what:

  ?automatic
  !?essential
  ?for p: (?provides(?reverse-provides(
		       ?widen(?provides(
				?reverse-depends(
				  ?depends(?reverse-provides(?=p))
				  ?installed)))
		       !?widen(?installed)))
	   |
	   ?reverse-provides(
	     ?widen(?provides(?=p))
	     !?widen(?installed)))

>   At the same time, it won't answer the question you want, since if you
> have
>
> A Depends: B | C
> D Depends: B
>
>   it will return B as a possibly ambiguous install.

True. (Actually, it was when I saw this that I started to feel a need
for ?exists. The case in my previous mail was oversimplified, which I
realized only later.)

> /.../ e.g., should ?all there refer to all the targets of *one*
> dependency of a package, or all the targets of *all* dependencies,
> and once we have chosen one meaning, how do we get the other one as
> an option?  And how do we choose consistently in all cases?  And will
> the default behave as expected for simple cases like
> ?not(?depends(?installed))?

Isn't this rather a problem with ?depends/?reverse-depends themselves
since they lose dependency alternative information? Compare these two
cases:

    Case 1:                Case 2:
    A Depends: B           A Depends: B | C
    A Depends: C

In both cases here, a query ?reverse-depends(A) would return both B
and C, i.e. it "flattens" the returned list so the alternative info in
case 2 is lost.

There are several ways to extend the search language to cope with
this. One would be to make individual dependencies referable as
first-class objects in their own right, so there are e.g. two
dependencies in case 1, "A/dep1" with the Depends link B and "A/dep2"
with the link C, while case 2 has only one dependency "A/dep1" with
two links B and C. But that would among other things complicate the
exposition considerably.

Another option could be to add alternative searches somewhat similar
to the ?broken-... terms:

  ?alternative-<depType>(<from-pattern>, <to-pattern>)
    Given that there are dependencies of type <depType> from any
    package matching <from-pattern> to any package matching
    <to-pattern>, this selects the alternative packages in those
    dependencies.

So ?alternative-depends(A, B) would select no package in case 1 above,
and C in case 2.

Using this, the following query would give all packages p, such that
there exists some package d which depends on p, but that dependency is
fulfilled by some other package too (ignoring ?widen issues here for
simplicity):

  ?for p: ?reverse-depends(
    ?for d: ?depends(?alternative-depends(?and(?d:depends(?=p), ?=d), ?=p)))

(Side note: I'm not sure the ?and(?d:..., ?=d) bit is necessary, but
since a plain ?d:... would match _any_ package (given the pattern
holds), I prefer restricting it to d just to make it easier to think
about, if nothing else.)

?reverse-depends works as a "poor mans ?exists" in the search above.
However, unlike with a real ?exists, we cannot use a double-inversion
to convert it to a "poor mans ?universal", which is what we really
want. But with a real ?exists and ?universal, it's possible to
formulate:

  ?for p: ?universal(
    ?or(?not(?depends(?=p)),
        ?for d: ?not(?exists(
          ?alternative-depends(?and(?d:depends(?=p), ?=d), ?=p)))))

This would read out: "Give me all packages p for which all other
packages either don't depend on p, or for all packages d, there does
not exist any alternative package that fulfills d's dependency on p."

The problem would then be solved by inserting the inverse of this in
the appropriate spot in my query earlier, to filter out the packages
that really are unambiguous dependencies. Not exactly simple, but at
least possible.

I take it your ?all operator would automatically "restrict" the
universe so that the ?or(?not(?depends(?=p)), ...) bit would be
implicit. However in the general case I suspect it's hard to come up
with a simple and natural definition of how that restriction is
calculated, so tools where it is explicit would be useful, at least to
begin with.

The use of ?universal could however be simplified with an ?equal:

  ?equal(<pattern>, <pattern>)
    Returns true (i.e. matches any package) if the two patterns
    matches the same set of packages or versions.

Then the query would get somewhat simpler:

  ?for p: ?equal(
    ?depends(?=p),
    ?for d: ?not(?exists(
      ?alternative-depends(?and(?d:depends(?=p), ?=d), ?=p))))

And if an ?equal is added, then one can of course consider more
similar operators such as ?subset and ?strict-subset.


Although the tools discussed above probably would solve the problem,
it's far from easy to work out these queries (for instance, a case
that still is ignored is if the alternative packages really couldn't
be installed due to conflicts elsewhere). We can step back a step
instead and look at what we really want to answer here, namely: "Give
me all automatically installed packages p, such that if p is
uninstalled, then there is some other solution that satisfies all
remaining dependencies."

Formulating a query like that would mean to make it possible to play
"what-if" games in the search, including running the conflict
resolver, just like one can do in the interactive interface. That'd be
cool, but it's undoubtedly a lot more complicated and slow.


PS. Something else I'd expect in the search language is transitive
closure for the various dependency following terms. For example, it
could look something like this to list all packages that a package foo
depends on, either directly or indirectly:

  ?reverse-depends*(foo)

Not that it's something I have any immediate need for, though.