haskell / haskell/cabal

Flag choices represented somewhat oddly in the search tree

Open
#3,409 2 comments 0 reactions 0 assignees View on GitHub
cabal-install: solver priority: low type: discussion
Dominant language
Haskell
Stars
1.7k
Forks
750
Avg merge
4d 3h
Merged PRs (30d)
28

Description

This is not a new problem, or in fact a problem at all, but it is somewhat odd and since I recorded this as part of the solver conflict set documentation I am writing I figured I might as well document it.

Consider the database:

``` haskell
dbBJ5 :: ExampleDb
dbBJ5 = [ Right $ exAv "A" 1 [exFlag "flagA" [ExFix "B" 1] [ExFix "C" 1]]
, Right $ exAv "B" 1 [ExFix "D" 1]
, Right $ exAv "C" 1 [ExFix "D" 2]
, Right $ exAv "D" 1 []
]
```

The build tree for this database (when solving for `A`) looks like

![bj5-build](https://cloud.githubusercontent.com/assets/935288/15090290/1d5078ae-1456-11e6-949c-2e13618a8bba.png)

Note that every path through this tree makes _two_ choices for the flag `flagA`. @kosmikus said:

> It's not a bug, but admittedly a strange thing. Flags are added to the goal set multiple times in the builder. In the validator, if we discover a flag choice that has already been made, it is removed. There used to be a very subtle reason for this, namely that we used to track dependencies between flags, once again for correct conflict set construction. And the info about how often a flag occurred in the goal set was used to help with that. But it was all wrong. So now, I think this is no longer relevant, and it could be removed in the sense that we do check for duplicates early, rather than only in the validator. After validation, it should not make a difference. But you look before validation here, so you see this ... Even though it may be good to change the behavior here, I'd argue that looking at the tree prior to validation does not really make sense. There is no clear semantics of what the unvalidated tree represents. However, there is a clear idea of what the validated tree represents.

The tree _after_ validation looks like

![bj5](https://cloud.githubusercontent.com/assets/935288/15090286/f0341a74-1455-11e6-979d-9ea68bd8c3bc.png)

This tree is even weirder than the previous one. We will have two `GoalChoice` nodes for `flagA` on every path, but validation has now removed the actual `FChoice` nodes from the tree, so that we have two `GoalChoice` nodes in a row. @kosmikus replied:

> As I said, I agree this is not particularly nice, nor is it really useful for anything anymore, but I don't think it is harmful in any way either, except perhaps for performance, because we have somewhat redundant info lying around. There's also no fundamental problem with having two subsequent goal choice nodes.

Contributor guide

Open the contributing guide

Research direction

Start with the dbBJ5 example and compare the pre-validation and post-validation trees described in the issue. Trace the builder’s repeated flag additions and the validator’s removal of FChoice nodes; confirm whether duplicate GoalChoice nodes have observable effects. Done is either documenting the behavior and its semantics or producing a narrowly agreed change, but the issue does not define which.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
build-system
Issue type
Documentation
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.