declare Distrib2= [ package(name: a version: 1 depends: [b c#geq(1) d#leq(5)]) package(name: a version: 2 depends: [b#neq(1) c d]) package(name: b version: 1 depends: [a#geq(1) c#neq(2)]) package(name: b version: 2 depends: [d#gt(1) f]) package(name: b version: 3 depends: [d f#neq(2)]) package(name: c version: 1 depends: nil) package(name: c version: 2 depends: [c#geq(1)]) package(name: c version: 3 depends: nil) package(name:d version: 1 depends: [a#geq(1) c#neq(1)]) ] declare fun {Packages D} % takes as argument a distribution D % returns a record such that % - label is 'versions' % - arity is the list of the names of packages in D % - the value of field p is the sorted list of versions of p in D fun {Partition L} % takes as argument a sorted list of pairs % [ P1#V11 ... P1#V1N1 .... PM#VM1 ... PM VMNM ] % returns % [ P1#[V11 ... V1N1] ... PM#[VM1 ... VMNM] ] fun {PartitionAux CurrName CurrList L} case L of nil then [CurrName#CurrList] [] (HN#HV)|R then if CurrName == HN then {PartitionAux CurrName HV|CurrList R} else (CurrName#CurrList)|{PartitionAux HN [HV] R} end end end in case L of nil then nil [] (HN#HV)|R then {PartitionAux HN [HV] R} end end fun {SortPackagesVersions D} % takes as argument a distribution % returns the ordered list of pairs Name#Version of all packages in D {List.sort {List.map D fun {$ P} P.name#P.version end} fun {$ AN#AV BN#BV} AN < BN orelse AN == BN andthen AV > BV end } end in local V = {Partition {SortPackagesVersions D}} R = {Record.make versions {List.map V fun {$ L#_} L end}} in {List.forAll V proc {$ P#VL} R.P = VL end} R end end declare fun {AtomicDependencyConstraint Sol AllNames Spec} % returns a 0/1 variable, indicating that the atomic dependency Spec % is satisfied in the solution Sol. % AllNames is the set of all names of existing packages. case Spec of P#VConst then if {List.member P AllNames} then case VConst of eq(N) then Sol.P=:N [] neq(N) then {FD.conj Sol.P\=:N Sol.P\=:0} [] gt(N) then Sol.P>:N [] geq(N) then Sol.P>=:N [] lt(N) then {FD.conj Sol.P<:N Sol.P\=:0} [] leq(N) then {FD.conj Sol.P=<:N Sol.P\=:0} end else 0 end [] P then if {List.member P AllNames} then (Sol.P\=:0) else 0 end end end declare fun {Solver Dist Goal} P={Packages Dist} AllNames={Record.arity P} in proc {$ Sol} Sol={Record.make installation AllNames} % initial domains of variables: 0, plus any available version % of the corresponding package {List.forAll AllNames proc {$ PName} Sol.PName :: 0|P.PName end } % goal package must be installed if {List.member Goal AllNames} then Sol.Goal >: 0 else fail end % all dependencies must be satisfied {List.forAll Dist proc {$ Pack} Name=Pack.name Version=Pack.version Dependences=Pack.depends InstalledVersion=Sol.Name in {List.forAll Dependences proc{$ Dep} {FD.impl InstalledVersion=:Version {AtomicDependencyConstraint Sol AllNames Dep} 1} end} end} {FD.distribute ff Sol} end end {Browse {SearchAll {Solver Distrib2 a}}}