Gentoo Websites Logo
Go to: Gentoo Home Documentation Forums Lists Bugs Planet Store Wiki Get Gentoo!
Bug 347353 - [Future EAPI] REQUIRED_USE USE state constraints
Summary: [Future EAPI] REQUIRED_USE USE state constraints
Status: RESOLVED FIXED
Alias: None
Product: Gentoo Hosted Projects
Classification: Unclassified
Component: PMS/EAPI (show other bugs)
Hardware: All Linux
: High normal (vote)
Assignee: PMS/EAPI
URL: http://dev.gentoo.org/~ferringb/requi...
Whiteboard: in-eapi-4
Keywords:
: 238887 (view as bug list)
Depends on:
Blocks: future-eapi
  Show dependency tree
 
Reported: 2010-11-30 22:04 UTC by Ulrich Müller
Modified: 2011-02-26 06:18 UTC (History)
4 users (show)

See Also:
Package list:
Runtime testing required: ---


Attachments
Proposed patch for PMS (0001-REQUIRED_USE-in-EAPI-4-bug-347353.patch,9.84 KB, patch)
2010-12-04 08:23 UTC, Ulrich Müller
Details | Diff
Updated patch (part 1 of 2) (0001-REQUIRED_USE-in-EAPI-4-bug-347353.patch,10.07 KB, patch)
2010-12-09 22:15 UTC, Ulrich Müller
Details | Diff
Updated patch (part 2 of 2) (0002-New-pkg_required_use-function-in-EAPI-4-bug-347353.patch,4.04 KB, patch)
2010-12-09 22:15 UTC, Ulrich Müller
Details | Diff
Updated patch (part 2 of 2) (0002-New-pkg_required_use-function-in-EAPI-4-bug-347353.patch,2.96 KB, patch)
2010-12-14 07:29 UTC, Ulrich Müller
Details | Diff
0001-Exactly-rather-than-Only-one-of.patch (0001-Exactly-rather-than-Only-one-of.patch,2.48 KB, patch)
2010-12-19 21:37 UTC, Ciaran McCreesh
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ulrich Müller gentoo-dev 2010-11-30 22:04:56 UTC
In today's meeting the council has decided that "REQUIRED_USE" shall be part of EAPI 4. See URL for its specification.
Comment 1 Ciaran McCreesh 2010-11-30 22:10:54 UTC
I notice the spec's missing things like which metadata cache line this goes on. Or is it not cached?
Comment 2 Ulrich Müller gentoo-dev 2010-11-30 22:51:17 UTC
(In reply to comment #1)
> I notice the spec's missing things like which metadata cache line this
> goes on.

As far as I can see, portage uses line 12 for it.

That line was formerly used for CDEPEND (whatever that was), but isn't any more since 2005, so I think that no confusion can arise.
<http://archives.gentoo.org/gentoo-portage-dev/msg_8f0a8505658bb99f642d68c46fa533fc.xml>
Comment 3 Ulrich Müller gentoo-dev 2010-12-04 00:55:13 UTC
Unfortunately, the spec also doesn't say how empty ^^ ( ) groups should behave.

An empty "any-of" group counts as being matched (says PMS), i.e. "|| ( )" evaluates to true.

Should it be the same for the ^^ operator, i.e. should "^^ ( )" evaluate to true? How is it currently implemented in portage?
Comment 4 Zac Medico gentoo-dev 2010-12-04 01:14:40 UTC
(In reply to comment #3)
> An empty "any-of" group counts as being matched (says PMS), i.e. "|| ( )"
> evaluates to true.
> 
> Should it be the same for the ^^ operator, i.e. should "^^ ( )" evaluate to
> true? How is it currently implemented in portage?

"|| ( )" and "^^ ( )" currently behave the same in portage. I've added a test case to show this:

http://git.overlays.gentoo.org/gitweb/?p=proj/portage.git;a=commit;h=8b6a531874f170d5b45926ac3ee766a775a0c11a
Comment 5 Ulrich Müller gentoo-dev 2010-12-04 08:23:36 UTC
Created attachment 256293 [details, diff]
Proposed patch for PMS

First attempt on a wording for PMS.
Please review.
Comment 6 Ciaran McCreesh 2010-12-04 11:57:38 UTC
You need to state what is and isn't allowed to be done if REQUIRED_USE isn't met. In particular, is it legal to run pkg_pretend?

Also, there's a huge quality issue here: how is the package mangler supposed to tell the user *why* it's not happy with flags? REQUIRED_USE provides no way for a good explanation to be provided.
Comment 7 Ulrich Müller gentoo-dev 2010-12-04 13:30:25 UTC
(In reply to comment #6)
> Also, there's a huge quality issue here: how is the package mangler supposed
> to tell the user *why* it's not happy with flags? REQUIRED_USE provides no
> way for a good explanation to be provided.

Portage has a function "human_readable_required_use" which would output something like the following (example REQUIRED_USE taken from ferringb's proposal):

This change violates use flag constraints defined by foo-bar/baz-1.0: 'client? ( !mips? ( any-of (  gtk qt motif ) ) mips? ( only-one-of ( gtk qt motif ) ) )'

I agree that this is not optimal.
Comment 8 Ulrich Müller gentoo-dev 2010-12-04 16:29:00 UTC
(In reply to comment #6)
> You need to state what is and isn't allowed to be done if REQUIRED_USE isn't
> met. In particular, is it legal to run pkg_pretend?

So how about this:
"If the package manager encounters a package version where REQUIRED_USE assertions are not met, it must treat this package version as if it was masked. No phase functions must be called."

Comment 9 Ciaran McCreesh 2010-12-04 16:31:18 UTC
I'm not sure that preventing pkg_pretend calls is necessarily the best thing to do, particularly given the difficulty of giving good explanations of unmet REQUIRED_USE constraints to the user.
Comment 10 Ulrich Müller gentoo-dev 2010-12-04 16:51:27 UTC
That's how it is currently implemented in portage, but of course it can still be discussed.

@ferringb: In <http://archives.gentoo.org/gentoo-dev/msg_b0e868626019f497eba47194c34e5421.xml> you had claimed:

   More importantly, they're also data rather then executable code. Via it
   being data, up front GUI's can tell you exactly what conflicts arise, and
   what needs to be adjusted.

Can you give a sketch of the algorithm that you had in mind?
Comment 11 Ciaran McCreesh 2010-12-04 16:57:34 UTC
An algorithm that gives a suggestion isn't particularly tricky. An algorithm that gives a good suggestion and that never suggests something utterly horrible is impossible.

The problem is that there's nowhere near enough information available about use flags for the package mangler to know which flags it can change safely, or which flags it should consider changing first. There's absolutely nothing telling the package mangler that turning on 'minimal' or that turning off 'acl' is a bad idea, for example.
Comment 12 Ciaran McCreesh 2010-12-04 17:06:14 UTC
I should say, "that gives a suggestion isn't particularly tricky, so long as you either don't require it always to produce a solution, or don't require it to run in P".
Comment 13 Zac Medico gentoo-dev 2010-12-06 17:08:56 UTC
(In reply to comment #9)
> I'm not sure that preventing pkg_pretend calls is necessarily the best thing to
> do, particularly given the difficulty of giving good explanations of unmet
> REQUIRED_USE constraints to the user.

Maybe add a separate function to call if REQUIRED_USE is unsatisfied, analogous to pkg_nofetch.
Comment 14 Ciaran McCreesh 2010-12-06 17:13:46 UTC
What an excellent idea!
Comment 15 Zac Medico gentoo-dev 2010-12-07 00:45:41 UTC
Okay, we can call the new function pkg_required_use or something like that. Obviously, it will only be called if required_use is in DEFINED_PHASES, and if it's not defined then the package manager will only show a generic message about unsatisfied REQUIRED_USE.
Comment 16 Ulrich Müller gentoo-dev 2010-12-09 22:15:06 UTC
Created attachment 256799 [details, diff]
Updated patch (part 1 of 2)

Updated patches:
  - part 1 introduces the REQUIRED_USE variable,
  - part 2 introduces the pkg_required_use function.
Comment 17 Ulrich Müller gentoo-dev 2010-12-09 22:15:33 UTC
Created attachment 256801 [details, diff]
Updated patch (part 2 of 2)
Comment 18 Brian Harring gentoo-dev 2010-12-10 18:21:12 UTC
All- sorry for the delay in responding, been busy.

I don't actually want that function- it dead end's the full goals of this functionality.  The plan I had was thus:

1) get the data in there.
2) PMs grew a dumb algo (as ciaran said, not too hard), that tells you the local conflicts that the resolver hit at that point.  Specifically, dump the REQUIRED_USE in full, then a list of points where current configuration doesn't match- "needed to have either sqlite or mysql on", for example.  If you think through portages previous behaviour for masks, or paludises, something akin.
3) now that the basics are there, deploy it (to allow the tree to be updated), but continue work- specifically enhancing what was written in #2, so that a global optimum can be suggested.

Specifically, while resolving, if a conflict is detected, stop descent at that node, flag it, and keep resolving the rest of the request.  Once the rest is completed, look at the failing/stopped nodes, grab the flag potentials, and map it back against what's actually enabled for the rest of the graph.

Additionally, one can do a shallow look at what the flags actually enable/enforce- beating on mysql again, if the user has mysql merged, the flag is potentially a better choice- that info can be gleaned algorithmically without too much trickery (just do subresolution at that point and check if what the flag turns on is already satisfied).

The point is, things like that make it possible for the resolver to give a suggestion- it still should tell you "conflict found, flags must be choosen", but then it can suggest *which* flags are optimal.

Basically, for #2, it's possible to state "you must choose mysql or sqlite."  If you go and do the function route, than users instead will get told "you must choose mysql or sqlite; ebuild authors recommend sqlite".

#3 however can state "you must choose mysql or sqlite.  You already are enabling mysql, so we suggest that- and here is the metadata.xml defined meaning of mysql/sqlite for this package".

Grok?

Algorithmically, it can pull the necessary info on it's own.  You go the function route, it'll wind up duplicating the basics of it (or just stating "use mysql, sqlite is the suxor"), duplicating it slower, and less completely than what the mangler could do.

This was my original plan, and best I can tell, the best end user experience without requiring each/every ebuild to try and duplicate it.  I'm aware #3 takes some work (I've not even started it for my own for example), so if folk think it's truly impossible to pull it off in a sane time, an interim bit of duct tape might be useful.  If that route is taken, I'm concerned it will get in the way of #3 long term- wind up stopping at a local maximum basically.

Counter args?
Comment 19 Ciaran McCreesh 2010-12-10 18:38:22 UTC
Please explain why the algorithm isn't equivalent to 3SAT, and thus impossible for non-trivial cases.
Comment 20 Brian Harring gentoo-dev 2010-12-10 19:21:38 UTC
(In reply to comment #19)
> Please explain why the algorithm isn't equivalent to 3SAT, and thus impossible
> for non-trivial cases.

The vast majority of package resolution maps back to *sat.  Notice we still manage to get things done despite having that hanging over our heads.

As you noted, it gets algorithmically horrid if each/every node was conflicting in REQUIRED_USE.  That's not the case, and that's an *extreme* degradation- that's frankly the boogeyman, not a real case.  Being that *sat hovers over our head for all resolution anyways, your point is venturing into that territory.

Note I stated that the resolver doesn't have to solve it- just mark the node as failed, and if in resolving it's solution it decides that node was actually needed (everything else was resolved), look at the nodes remaining, take their REQUIRED_USE, and check the flags first level deps it enables.

Final note, as I'm sure you're aware, *sat worst cases are obviously there- not all degrade to it (fortunately a fair amount don't).

If you still think it's impossible, I'm putting it to *you* to disprove it- you claim it's impossible, back up the claim with real world examples that would occur in the tree.
Comment 21 Zac Medico gentoo-dev 2010-12-11 03:45:24 UTC
The idea behind the proposed pkg_required_use() function is that it's not possible for the dependency resolver to read the users's mind. In some cases, there are choices that need to be made by users, and pkg_required_use() can provide important information that will help them to make these choices.
Comment 22 Ulrich Müller gentoo-dev 2010-12-11 10:03:56 UTC
Maybe we should have the council decide on this.
Comment 23 Jorge Manuel B. S. Vicetto Gentoo Infrastructure gentoo-dev 2010-12-11 19:31:08 UTC
I understand both Brian's point about the "danger" of leaving the explaining at maintainer's hands and Zac's / Ciaran's point about being hard (impossible?) to the PM to provide a clear and correct answer in case it's not possible to satisfy REQUIRED_USE.
What I don't understand as I don't have the required background is whether Brian's proposal for the dependency resolver can be implemented or not and whether there's a noticeable impact on performance or not.
Comment 24 Ciaran McCreesh 2010-12-11 19:36:43 UTC
REQUIRED_USE is solvable by the package manager only in extremely trivial cases. The whole "3SAT" thing we're discussing basically means that solving non-trivial cases takes longer than the lifetime of the universe.

To make matters worse, there's no way for the package mangler to know whether the solution it proposes is safe. Given something like:

    REQUIRED_USE="!build? ( acl )"

the package mangler might decide to turn on the 'build' flag, with horrible consequences.
Comment 25 Ulrich Müller gentoo-dev 2010-12-14 07:29:47 UTC
Created attachment 257091 [details, diff]
Updated patch (part 2 of 2)

Small update: We don't need an extra EAPI dependent table for the function.

(This doesn't imply that I'm in favour of pkg_required_use. I can live with it either way.)
Comment 26 Zac Medico gentoo-dev 2010-12-14 13:08:30 UTC
Let me also clarify that I can live without pkg_required_use too. However, if we must provide some function to be called when REQUIRED_USE is unsatisfied (as Ciaran was suggesting to call pkg_pretend in comment #9), then I think it's best to have a specialized pkg_required_use function for this case. If we use pkg_pretend for both cases, then we'll have pkg_pretend being defined and called in cases when such a function call could have been entirely avoided (due to REQUIRED_USE already being satisfied).
Comment 27 Ciaran McCreesh 2010-12-16 15:44:19 UTC
REQUIRED_USE *only* allows the package mangler to figure out if a certain combination is legal; it doesn't give enough information to tell the user why something's illegal, and it doesn't give enough information to try to solve the problem.

Thus, why not make pkg_required_use mandatory for anything using REQUIRED_USE, and avoid ever having the package mangler have to try to provide a decent error from REQUIRED_USE?
Comment 28 Ulrich Müller gentoo-dev 2010-12-18 09:15:55 UTC
(In reply to comment #16)
> Created an attachment (id=256799) [details]
> Updated patch (part 1 of 2)

There were no objections on the first part of the patch, therefore pushed to master.
Comment 29 Ciaran McCreesh 2010-12-19 17:02:57 UTC
Nrm, regarding the naming on that patch... "Exactly one" strikes me as being clearer than "Only one".

"Only one may be selected" is sort of fuzzy as to whether zero is ok or not, but "Exactly one must be selected" is much more specific.
Comment 30 Ulrich Müller gentoo-dev 2010-12-19 17:49:58 UTC
(In reply to comment #29)
> Nrm,

What does this abbreviation mean?

> regarding the naming on that patch... "Exactly one" strikes me as being
> clearer than "Only one".
>
> "Only one may be selected" is sort of fuzzy as to whether zero is ok or not,
> but "Exactly one must be selected" is much more specific.

The specification reads: "In an only-one-of group, exactly one immediate child element must be matched." The name "only-one-of" follows portage.

Do you want to call it an "exactly-one-of group" instead?
Comment 31 Ciaran McCreesh 2010-12-19 17:52:31 UTC
(In reply to comment #30)
> > Nrm,
> 
> What does this abbreviation mean?

Apparently, that I can't type "Hrm" any more.

> The specification reads: "In an only-one-of group, exactly one immediate child
> element must be matched." The name "only-one-of" follows portage.
> 
> Do you want to call it an "exactly-one-of group" instead?

Yeah, I think that's clearer. Consistently saying "exactly" rather than "only" might avoid a bit of confusion.
Comment 32 Ulrich Müller gentoo-dev 2010-12-19 18:11:55 UTC
(In reply to comment #31)
> > Do you want to call it an "exactly-one-of group" instead?
> 
> Yeah, I think that's clearer. Consistently saying "exactly" rather than "only"
> might avoid a bit of confusion.

Go ahead.
Comment 33 Ciaran McCreesh 2010-12-19 21:37:02 UTC
Created attachment 257582 [details, diff]
0001-Exactly-rather-than-Only-one-of.patch

Think this gets all of them
Comment 34 Ulrich Müller gentoo-dev 2010-12-19 22:05:09 UTC
(In reply to comment #33)
> Created an attachment (id=257582) [details]
> 0001-Exactly-rather-than-Only-one-of.patch
> 
> Think this gets all of them

Looks good to me.
Comment 35 Ulrich Müller gentoo-dev 2010-12-30 19:53:15 UTC
EAPI 4 has been approved by the council.
Comment 36 Ulrich Müller gentoo-dev 2011-02-26 06:18:04 UTC
*** Bug 238887 has been marked as a duplicate of this bug. ***