solver: Interaction of base-shim qualifier and setup qualifier is not correct

[mpickering]

The setup component should be solved independently of the other components, so the decisions about constraints taken in the setup component should not be influenced by decisions taken in other components.

This is witnessed by the following test where the setup and library depend on different versions of base.

-- Works without the base-shimness, choosing different versions of base              
db12s2 :: ExampleDb                                                                  
db12s2 =                                                                             
  let base3 = exInst "base" 3 "base-3-inst" []                                       
      base4 = exInst "base" 4 "base-4-inst" []                                       
   in [ Left base3                                                                   
      , Left base4                                                                   
      , Right $ exAv "A" 1 [ExFix "base" 4]                                          
                  `withSetupDeps` [ExFix "base" 3]                                   
      ]      

        targets: A
        constraints: 
          any.base installed (non-reinstallable package)
          any.ghc-bignum installed (non-reinstallable package)
          any.ghc-prim installed (non-reinstallable package)
          any.ghc installed (non-reinstallable package)
          any.integer-gmp installed (non-reinstallable package)
          any.integer-simple installed (non-reinstallable package)
          any.template-haskell installed (non-reinstallable package)
        preferences: 
        strategy: PreferLatestForSelected
        reorder goals: False
        count conflicts: True
        fine grained conflicts: True
        minimize conflict set: False
        independent goals: False
        avoid reinstalls: False
        shadow packages: False
        strong flags: False
        allow boot library installs: False
        only constrained packages: OnlyConstrainedNone
        max backjumps: infinite
        [__0] trying: A-1.0.0 (user goal)
        [__1] trying: base-4.0.0/installed-inst (dependency of A)
        [__2] next goal: A:setup.base (dependency of A)
        [__2] rejecting: A:setup.base~>base-4.0.0/installed-inst (conflict: A => A:setup.base==3.0.0)
        [__2] skipping: A:setup.base-4.0.0/installed-inst (has the same characteristics that caused the previous version to fail: excluded by constraint '==3.0.0' from 'A')
        [__2] trying: A:setup.base-3.0.0/installed-inst
        [__3] done

However, if the situation is slightly more complicated, and we have the situation where base-3 is a shim for base-4 then things quickly go wrong:

-- | A version of db11 where the dependency on base happens via a setup dependency                  
--                                                                                                  
-- * The setup dependency is solved in it's own qualified scope, so should be solved                
-- independently of the rest of the build plan.                                                     
--                                                                                                  
-- * The setup dependency depends on `base-3`                                                       
--                                                                                                  
-- * A depends on `base-4`, should be fine as the setup stanza should                               
-- be solved independently.                                                                         
db11s :: ExampleDb                                                                                  
db11s =                                                                                                   
  let base3 = exInst "base" 3 "base-3-inst" [base4]                                                  
      base4 = exInst "base" 4 "base-4-inst" []                                                       
   in [ Left base3                                                                                  
      , Left base4                                                                                  
      , Right $ exAv "A" 1 [ExFix "base" 4]                                                         
                  `withSetupDeps` [ExFix "base" 3]                                                  
      ]   


        Unexpected solver log:
        targets: A
        constraints: 
          any.base installed (non-reinstallable package)
          any.ghc-bignum installed (non-reinstallable package)
          any.ghc-prim installed (non-reinstallable package)
          any.ghc installed (non-reinstallable package)
          any.integer-gmp installed (non-reinstallable package)
          any.integer-simple installed (non-reinstallable package)
          any.template-haskell installed (non-reinstallable package)
        preferences: 
        strategy: PreferLatestForSelected
        reorder goals: False
        count conflicts: True
        fine grained conflicts: True
        minimize conflict set: False
        independent goals: False
        avoid reinstalls: False
        shadow packages: False
        strong flags: False
        allow boot library installs: False
        only constrained packages: OnlyConstrainedNone
        max backjumps: infinite
        [__0] trying: A-1.0.0 (user goal)
        [__1] next goal: A.bb.base (dependency of A)
        [__1] rejecting: A.bb.base-4.0.0/installed-inst (conflict: A => A.bb.base==3.0.0)
        [__1] rejecting: A.bb.base-3.0.0/installed-inst (conflict: A => A.bb.base==4.0.0)
        [__1] fail (backjumping, conflict set: A, A.bb.base)
        [__0] fail (backjumping, conflict set: A, A.bb.base)

The issue is that with the current structure of qualified goals, the qualified goal introduced by the base shim obliterates the qualified goal introduced by the setup dependency and therefore the base dependency in the main package and setup stanza is solved under the same qualifier (and hence fails).

I uncovered this issue when working on extending the qualified goals mechanism, so on it's own it can be filled into the niche but it highlights a more general problem with how the code around qualified goals is structured.

[mpickering]

cc @grayjay

[grayjay]

I read some of the code related to base shims, and I think I see why setup dependencies and base shims don't work well together. I don't fully understand the log from the second example, though.

The issue may have been introduced by #3220, which limited the depth of qualifiers to one to prevent infinite loops. The depth limit means that the solver discards the existing setup qualifier when it adds a base qualifier. I also noticed that when base shims are in use, dependencies of base are always given the top-level qualifier, which could cause inconsistent dependencies for a setup component:

cabal/cabal-install-solver/src/Distribution/Solver/Modular/Dependency.hs

Lines 217 to 222 in 4f53a2f

	inheritedQ :: Qualifier
	inheritedQ = case q of
	QualSetup _ -> q
	QualExe _ _ -> q
	QualToplevel -> q
	QualBase _ -> QualToplevel

I think that we could fix these two issues by keeping the limit of one setup or exe qualifier but adding a boolean field to represent the existence of a final base qualifier.

[mpickering]

@grayjay I have fixed the issue on a branch I have by clarifying the difference between a "namespace" and a "qualifier".

• A namespace is used to introduce a permanent new scope, which includes solving transitive dependencies.
• A qualifier is used to introduce a temporary scope for a direct dependency but not transitive dependencies.

The structure of the PackagePath is still non-recursive to prevent the issues in #3220

Therefore most qualified goals are distinguished by a new namespace (and it's fine if these replace each other because they introduce a completely new scope). The base-shim goal is the only example of a "qualifier" goal where the goal does not persist into transitive dependencies.

This simplifies the implementation of qualifyDeps because

• The namespace always get inherited.. unless a new namespace is introduced.
• A qualifier is never inherited, and also reset to TopLevel (if a new qualifier is not introduced).

[grayjay]

I think that the idea of independent goals was that all dependencies of different targets would be independent, including setup and build tool dependencies. So I think that the namespace should continue to always be inherited. We could fix the base shim issue without reducing the set of possible solutions by using types like this:

data PackagePath = PackagePath Namespace Qualifier (Maybe BaseQualifier)

data Namespace = DefaultNamespace | Independent PackageName

data Qualifier =
    QualToplevel
  | QualSetup PackageName
  | QualExe PackageName PackageName

newtype BaseQualifier = BaseQualifier PackageName