[Aptitude-devel] Search term for existence

[Daniel Burrows]

On Sun, Feb 08, 2009 at 10:14:49PM +0100, Martin Stjernholm <apt at stjernholm.org> was heard to say:
> Daniel Burrows <dburrows at debian.org> wrote:
> >   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.

  Yeah, that's right.

> > /.../ 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:

  Yes, that's right.  I think the conceptual problem here is that all
the terms in the search language are framed around asking questions
about packages (technically, every search pattern is a predicate on
packages), and they cope badly with getting detailed information about
other types of objects.  Even getting version information is a bit
hacky; ?all-version and ?any-version have somewhat shakily defined
meanings IMO.

> 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.

  Depends how you do it (see below).

> 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.

  I think that this is too complicated and hard to comprehend, and also
too specialized.

  (snip ?universal)

  BTW, the reason I'm hesitant to include ?exists and ?universal is
that they make it very tempting to write horrendously inefficient
searches -- the implementation would be to use nested loops over the
database.  I am not going to get into doing relational optimizations
of search queries any time soon -- it would probably be better to just
make a sqlite database and generate queries against it. :-P

  So, I'd ideally like to find a way to do this using combinators that
are based on "walking the graph", so they have somewhat more reasonable
performance.  (e.g., ?depends only tests the dependency relationships
of each package; using ?exists instead would require testing all the
other packages in the cache)

> 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.

  Yeah.  The search code actually has a notion of a current "pool" of
objects that are being tested.  For instance, when checking
dependencies, we test a series of pools consisting of each matching
version in turn (or the package itself if it's a pure virtual package).
The default behavior when we hit an atomic pattern is to match if any
version in the pool matches; the idea would be to have a term that
changes this behavior to "match if all versions match".

  Ouch -- it looks like I actually changed ?all-versions to do this
without updating its documentation.  Bad me. :-(


  Here's what I think is a better way of addressing dependencies.  In
fact, I like it so much that I'll put it on the list of stuff to
implement someday (maybe after the current UI rewrite is done).

  Like I said before, search terms are framed (and understood by users)
as "questions about packages", i.e. predicates.  The natural way to
introduce dependencies, then, is to introduce "questions about
dependencies" -- more predicates.  This eliminates the need to name
them explicitly (while allowing you to do so if desired using the
same constructs that can name packages).

  Some obvious predicates on dependencies:

    ?source(PATTERN) -- match if the source package matches PATTERN.
    ?target(PATTERN) -- match if a package version that exists in
                        the archive satisfies the dependency and
                        matches PATTERN.  (or if a target is a pure
                        virtual package matching PATTERN)
    ?target-package(PATTERN) -- match if any target package matches
                                PATTERN.
    ?target-candidate(PATTERN) -- like ?target-version, but also
                                      matches through Provides (bad
                                      term name).
       *** Add "first-" to any of the three ?target patterns to match
           only the first alternative. ***
    ?type(DEPTYPE)   -- the dependency has a particular type (depends,
                        recommends, etc)
    ?broken          -- the dependency is currently unsatisfied
    ?singular        -- the dependency has only one branch (not
                        including Provides)

  In a more complex language, ?target() would match "version
specifications", which are not versions themselves but can be matched
against versions.  I don't know that this is necessary, though.

  The main syntax I envision for injecting a dependency match is:

    ?has-depends(PATTERN) -- a package (version) has a Depends
                             matching PATTERN.
    ?has-reverse-depends(PATTERN) -- a package (version) has a reverse
                                     Depends matching PATTERN.
    ?has-dependency(PATTERN) -- a package (version) has a dependency of
                                some type matching PATTERN.
    ?has-reverse-dependency(PATTERN) -- a package (version) has a
                                        dependency of some type
                                        matching PATTERN.

  I don't like the similarity between "depends" and "dependency" -- I
also considered "relation", which offers the intriguing idea of
matching over all inter-package relations at once (but what use would
it be?).

> 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.

  That's an interesting idea to keep in mind if I end up implementing
cache-wide terms eventually.

> 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."

  For that, I'd point you at the EDOS project -- aptitude's resolver
code is about finding installation solutions for individual packages,
whereas they do things like archive-wide installability testing.

> 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.

  I think about doing this every so often.  Again, the reason I haven't
is that it seems very specialized.  What if you want to know about
paths containing either depends *or* recommends, for instance?

  However, with the notes about about matching dependencies, I can
suggest:

  ?reverse-relation*(REL-PATTERN, END-PATTERN) -- matches a package if
there is a sequence of relations (or pick a specific relation type)
in which each relation matches REL-PATTERN, the source of each relation
is a target of the next relation, and the source of the last relation
matches END-PATTERN.  REL-PATTERN could be absent for ?reverse-depends*
and friends; it would default to ?type(depends) (or recommends, etc).

  And of course there's a forward version of this too (?relation*).

  Daniel