Bugzilla – Full Text Bug Listing
| Summary: | [planner][metadata] Need ability to "or" and "negate" generic requirements | ||
|---|---|---|---|
| Product: | [Eclipse Project] Equinox | Reporter: | Pascal Rapicault <pascal> |
| Component: | p2 | Assignee: | Pascal Rapicault <pascal> |
| Status: | CLOSED FIXED | QA Contact: | |
| Severity: | normal | ||
| Priority: | P3 | CC: | henrik.lindberg, irbull, leberre, thomas |
| Version: | 3.4 | Keywords: | api, helpwanted |
| Target Milestone: | 3.6 M6 | ||
| Hardware: | PC | ||
| OS: | Windows XP | ||
| Whiteboard: | |||
| Bug Depends on: | |||
| Bug Blocks: | 251167, 270195, 313795 | ||
|
Description
Pascal Rapicault
From an encoding point of view, there is no big difficulty to translate such requirements in the input format of a SAT or PB solver. In the example below, just create two additional variables, V1 and V2: A -> V1 A -> X A -> V2 V1 -> B or C V2 -> Y or Z Adding disjunction will increase the search space for the solver thus it is likely that the resulting SAT problems will be harder to solve. However, we are already using such encoding for managing the different versions of a plugin, so it is likely that for many scenarios, the solver may be able to manage such problems quickly. Given the set of things left to do in 3.5, and that there is no direct need for this. I'm removing the 3.5 milestone and adding the helpwanted keyword in case somebody wanted to take a ownership of this. This would be a valuable addition. Buckminster for instance, provide two different adapters for Subversion (based on Subclipse and Subversive). To install both of them is an error since they extend the same thing. But currently, we have no way of preventing this. This is indeed one of the scenario we would like to cover with this. This will also have an impact on the API. I have released in HEAD initial support for OR and NOT. - The data structures - The changes to the projector and the slicer and tests Things missing - We don't have an API yet and it is currently really ugly especially around ORRequirement - No serialization Questions about the support for or - How can we ensure stability in case of multiple choices? For example ORTesting#testOR3? Is this problem different than in any other case where we have choice between providers of packages? - The current semantics is to ensure at least one of the requirement is met. Do we want a notion of arity? - Given that an ORRequirement is a set of requirements, what happens to getName() and getNamespace()? Questions about the support for negation - Implement support for negation in case of patches (expandRequirementWithPatches) - How do I replace a negation requirement by a patch? - Can a negation be optional? I don't think so. Since the point is to negate something. - What does greed means? Greed is irrelevant in this context since we generally don't want to bring the IU. - If we add arity, would we be better off implementing Negation on a regular requirement but with an arity of 0? General things to add: - check query against QueryableArray, there was some optimized code in there that needs to be reviewed. - check query against IProfile - There is no support for serialization yet >- How can we ensure stability in case of multiple choices? For example >ORTesting#testOR3? Is this problem different than in any other case where we >have choice between providers of packages? We need to order the alternatives in order to ensure reproducible results. >- The current semantics is to ensure at least one of the requirement is met. Do >we want a notion of arity? From a solver point of view, it is no problem to support arity. Why is there no AndRequirement? I realize that AND is the default at top level but don't we still need it in order combine? I.e. (a OR (b AND c)) Also, when negating it would be nice to write: NOT (a AND b AND c) but for the common user, that might not be all clear. Regarding API. We really need interfaces for those new requirement classes in order to support our alternative EMF implementation of a p2 data structure. I can offer to help with both that and the AND requirement if you're not currently working on it. Your help is welcome. At this point the implementation is only a prototype to see the impact on the code and explore with the shape of things. As you can see in comment #6, there is a lot of things to be answered before we can move forward with this. The two main one are: > 1) Given that an ORRequirement is a set of requirements, what happens to getName() and getNamespace()? I have done some exploration to see if we could do without ever exposing namespace and name as part of the API of a IRequiredCapability. Given the code I have seen it seems possible but may require methods like containsNamespace(String) instead of the getNamespace we have today > 2) If we add arity to a regular requirement, would we be better off implementing Negation on a regular requirement but with an arity of 0? This makes is a bit cleaner API wise but still require special handling in the Planner like we do with the current implementation. Daniel, any opinion on that one or on any other points raised in comment #6? As for the "language" authorized, the addition of ORs and NOTs gives us the ability to express CNFs to which everything can be transformed to (http://en.wikipedia.org/wiki/Conjunctive_normal_form). So what I'm arguing is that we may allow the user to express more complex things, but that would be authoring time format. (In reply to comment #6) > > Questions about the support for or > - How can we ensure stability in case of multiple choices? For example > ORTesting#testOR3? Is this problem different than in any other case where we > have choice between providers of packages? With already have the problem with the current encoding, where alternatives exist for providing a given capability. The only wat to ensure stability is to have preferences between alternatives, i.e. to make sure that the value of the final objective function differs depending of the alternative choosen. > - The current semantics is to ensure at least one of the requirement is met. > Do we want a notion of arity? Constraints on arity are available in SAT4J. No problem from an encoding point of view here. > Questions about the support for negation > - Implement support for negation in case of patches > (expandRequirementWithPatches) > - How do I replace a negation requirement by a patch? original A -> not B patch removes negation: A -> not B P P -> (A -> C) > - Can a negation be optional? I don't think so. Since the point is to negate > something. Trying to implement an optional negation does not make sense IMHO. (In reply to comment #10) > As for the "language" authorized, the addition of ORs and NOTs gives us the > ability to express CNFs to which everything can be transformed to > (http://en.wikipedia.org/wiki/Conjunctive_normal_form). So what I'm arguing is > that we may allow the user to express more complex things, but that would be > authoring time format. I would argue that adding AND to the equation greatly increases the readability of many types of expressions. If you have that in tooling only and transform into CNF, how do you transform it back to the more readable form that was used when authoring? (In reply to comment #12) > > I would argue that adding AND to the equation greatly increases the readability > of many types of expressions. If you have that in tooling only and transform > into CNF, how do you transform it back to the more readable form that was used > when authoring? There is no real need to translate back the the authoring language. The CNF is only needed to feed the solver because this is the expected input. It is the business of the solver, or of an intermediate layer, to translate the problem into CNF and to map back an explanation on the CNF into an explanation on the original formula. From p2 users point of view, this should be completely transparent. I would just warn that the more expressive you are, the more time you are likely to spend solving the problem. We can easily find solutions to p2 problems right now because we have few disjunctions. Once you start adding explicit AND, OR, NEG, you greatly increase the possible source of disjunctions, thus the complexity of the problem. (In reply to comment #13) > There is no real need to translate back the the authoring language. > I edit an IU using some tooling. I enter a complex expression involving nested OR/AND/NOT expessions. I save it. Next day I load it again to continue working. I would very much like two things: 1. To use an IU as the persisted format since that is what I'm editing. 2. To see the same expression the second time I edit. I fail to see how to do that without "translating back". In my initial exploration, I had went this route and the complexity of adding what you are asking is high for the number of ppl that will be benefiting from it. Also it makes patching just nearly impossible. For the reading / writing issue, I think requirements could be annotated with the original formula. OK. I give in. I realize that my arguments for the AND aren't strong enough :-) I'll add the API interfaces for ORRequirement and NOTRequirement and also have a look at the namespace issue. Thx ;-) (In reply to comment #14) > (In reply to comment #13) > > There is no real need to translate back the the authoring language. > > > I edit an IU using some tooling. I enter a complex expression involving nested > OR/AND/NOT expessions. I save it. Next day I load it again to continue working. > I would very much like two things: > > 1. To use an IU as the persisted format since that is what I'm editing. > 2. To see the same expression the second time I edit. > > I fail to see how to do that without "translating back". the IU would be persisted with the complex expression. the translation into CNF would only be done at resolving time. (In reply to comment #11) > Trying to implement an optional negation does not make sense IMHO. There might be a case where optional negation does make sense: I have an IU with a two requirements to components A and B-opt (B is optional). Now another vendor provides component C which supersedes the A and B-opt. In my IU, I want express a requirement that can be fulfilled by either one but not both. Simply put I want: (A and B-opt) or C If I normalize that, I get not (not A or not B-opt) or C From a strict boolean standpoint, this can of course be stripped down to A or C but then we loose B-opt in the generated plan. Anyone given this some more thought? Is an optional negation required or do we need the dreaded AND after all? With all the changes that went in, I have confirmed that this is in place. We will need to write more tests. (In reply to comment #21) > With all the changes that went in, I have confirmed that this is in place. > We will need to write more tests. Is there any docs on this? Maybe we can add something to the wiki. |