a_12_planner.lua 30.9 KB
Newer Older
1
--[[
2
Copyright 2016-2017, CZ.NIC z.s.p.o. (http://www.nic.cz/)
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

This file is part of the turris updater.

Updater is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Updater is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Updater.  If not, see <http://www.gnu.org/licenses/>.
]]--

local ipairs = ipairs
local pairs = pairs
local type = type
23 24
local tostring = tostring
local error = error
25
local next = next
26 27
local assert = assert
local unpack = unpack
28 29
local table = table
local DIE = DIE
30
local DBG = DBG
Karel Koci's avatar
Karel Koci committed
31
local TRACE = TRACE
32
local WARN = WARN
Karel Koci's avatar
Karel Koci committed
33
local picosat = picosat
34 35
local utils = require "utils"
local backend = require "backend"
36
local requests = require "requests"
37
local postprocess = require "postprocess"
38

39
module "planner"
40

41
-- luacheck: globals required_pkgs candidates_choose filter_required pkg_dep_iterate plan_sorter sat_penalize sat_pkg_group sat_dep sat_dep_traverse
42

43
-- Choose candidates that complies to version requirement.
44
function candidates_choose(candidates, pkg_name, version, repository)
45
	assert(version or repository)
46
	-- repository is table of strings and objects, canonize to objects and add it to set.
47 48 49 50 51 52 53 54 55
	local repos = {}
	for _, repo in pairs(repository or {}) do
		assert(type(repo) == 'string' or type(repo) == 'table')
		if type(repo) == 'string' then
			repos[requests.known_repositories[repo]] = true
		else
			repos[repo] = true
		end
	end
56 57 58

	local compliant = {}
	for _, candidate in pairs(candidates) do
59 60 61 62
		assert(candidate.Version) -- Version have to be there but candidate.repo might not if it is content from configuration not from repository
		-- Add candidates matching version and repository limitation. Package
		-- supplied using content field in configuration has no repository, so it
		-- is never added when repository limitation is specified.
63 64
		if (not version or (candidate.Package == pkg_name and backend.version_match(candidate.Version, version))) and
				(not repository or (candidate.repo and repos[candidate.repo])) then
65 66
			table.insert(compliant, candidate)
		end
67
	end
68
	return compliant
69
end
70

71
-- Adds penalty variable for given var.
72
function sat_penalize(state, activator, var, penalty_group, lastpen)
73 74
	if not lastpen then
		return 0 -- skip first one, it isn't penalized.
75
	end
76 77 78
	if not activator then
		activator = state.sat.v_true -- if no activator given than it should be always active
	end
79
	local penalty = state.sat:var()
Karel Koci's avatar
Karel Koci committed
80
	TRACE("SAT add penalty variable " .. tostring(penalty) .. " for variable " .. tostring(var))
81
	-- penalty => not pen
82
	state.sat:clause(-activator, -penalty, -var)
83 84
	if lastpen ~= 0 then
		-- previous penalty variable implies this one
85
		state.sat:clause(-activator, -lastpen, penalty)
86 87 88 89 90 91
	end
	table.insert(penalty_group, penalty)
	return penalty
end

-- Returns sat variable for package group of given name. If it is not yet added, then we create new variable for it and also for all its dependencies and candidates.
92
-- Note that this have to work if the group is unknown (dependency on package we don't know)
93
function sat_pkg_group(state, name)
94
	if state.pkg2sat[name] then
95 96 97 98
		return state.pkg2sat[name] -- Already added package group, return its variable.
	end
	-- Create new variable for this package
	local pkg_var = state.sat:var()
Karel Koci's avatar
Karel Koci committed
99
	TRACE("SAT add package " .. name .. " with var: " .. tostring(pkg_var))
100 101 102 103
	state.pkg2sat[name] = pkg_var
	local pkg = state.pkgs[name]
	-- Add candidates for this package group
	local sat_candidates = {}
104
	local sat_candidates_exclusive = {} -- only candidates with same name as package group are exclusive
105 106 107 108 109
	local lastpen = nil
	local candidates = (pkg and pkg.candidates) or {}
	-- We expect here that candidates are sorted by their priority.
	-- At first we just add variables for them
	for _, candidate in ipairs(candidates) do
110 111 112 113
		local cand
		-- Candidate might exists if it provides some other package
		if not state.candidate2sat[candidate] then
			cand = state.sat:var()
Karel Koci's avatar
Karel Koci committed
114
			TRACE("SAT add candidate " .. candidate.Package .. " for group: " .. name .. " version:" .. (candidate.Version or "") .. " var:" .. tostring(cand))
115 116 117 118
			state.candidate2sat[candidate] = cand
		else
			cand = state.candidate2sat[candidate]
		end
119
		state.sat:clause(-cand, pkg_var) -- candidate implies its package group
120 121 122 123 124
		if candidate.Package == name then -- Only candidates of this package group are exclusive. There is no reason why candidates from other packages should be exclusive (they are in their own package group).
			for _, o_cand in pairs(sat_candidates_exclusive) do
				state.sat:clause(-cand, -o_cand) -- ensure candidates exclusivity
			end
			table.insert(sat_candidates_exclusive, cand)
125
		end
126
		lastpen = sat_penalize(state, nil, cand, state.penalty_candidates, lastpen) -- penalize candidates
127 128 129
		table.insert(sat_candidates, cand)
	end
	-- We solve dependency afterward to ensure that even when they are cyclic, we won't encounter package group in sat that don't have its candidates in sat yet.
130
	-- Candidate from other package might not be processed yet, we ensure here also that its package group is added
131 132
	-- Field deps for candidates and modifier of package group should be string or table of type 'dep-*'. nil or empty table means no dependencies.
	for i = 1, #sat_candidates do
133 134 135 136
		if candidates[i].Package ~= name then
			sat_pkg_group(state, candidates[i].Package) -- Ensure that candidate's package is also added
			-- Note: not processing dependencies here ensures that dependencies are added only once
		elseif candidates[i].deps and (type(candidates[i].deps) ~= 'table' or next(candidates[i].deps)) then
137
			local dep = sat_dep_traverse(state, sat_candidates[i], candidates[i].deps)
138
			state.sat:clause(-sat_candidates[i], dep) -- candidate implies its dependencies
139
		end
140 141 142 143 144
	end
	if next(sat_candidates) then
		state.sat:clause(-pkg_var, unpack(sat_candidates)) -- package group implies that at least one candidate is chosen
	else
		if not utils.multi_index(pkg, "modifier", "virtual") then -- For virtual package, no candidates is correct state
Karel Koci's avatar
Karel Koci committed
145
			TRACE("SAT group " .. name .. " has no candidate")
146
			state.missing[name] = pkg_var -- store that this package group has no candidates
147 148
		end
	end
149 150 151
	-- Add dependencies of package group
	local deps = utils.multi_index(pkg, 'modifier', 'deps')
	if deps and (type(deps) ~= 'table' or deps.tp) then
152
		local dep = sat_dep_traverse(state, pkg_var, deps)
153 154 155 156 157 158
		state.sat:clause(-pkg_var, dep)
	end
	-- And return variable for this package
	return pkg_var
end

159
-- Returns sat variable for specified requirements on given package.
160 161 162 163 164 165 166
function sat_dep(state, pkg, version, repository)
	local name = pkg.name or pkg
	local group_var = sat_pkg_group(state, name) -- This also ensures that candidates are in sat
	-- If we specify version then this is request not to whole package group but to some selection of candidates
	if version or repository then
		assert(type(pkg) == 'table') -- If version specified than we should have package not just package group name
		local var = state.sat:var()
Karel Koci's avatar
Karel Koci committed
167
		TRACE("SAT add candidate selection " .. name .. " var:" .. tostring(var))
168 169 170 171 172
		-- Imply group it self. If we have some candidates, then its just
		-- useless clause. But for no candidates, we ensure that at least some
		-- version of package will be installed if not required one.
		-- Note that that can happen only when we ignore missing dependencies.
		state.sat:clause(-var, group_var)
173
		if utils.multi_index(state.pkgs[name], 'modifier', 'virtual') then
174 175
			WARN('Package ' .. name .. ' requested with version or repository, but it is virtual. Resolved as missing.')
			state.missing[pkg] = var
176
			return var
177
		end
178
		local chosen_candidates = candidates_choose(utils.multi_index(state.pkgs[name], 'candidates') or {}, name, version, repository) -- Note: package don't have to exist (dependency on unknown package)
179 180 181 182
		if next(chosen_candidates) then
			-- We add here basically or, but without penalizations. Penalization is ensured from dep_pkg_group.
			local vars = utils.map(chosen_candidates, function(i, candidate)
				assert(state.candidate2sat[candidate]) -- candidate we require should be already in sat
183
				state.sat:clause(-state.candidate2sat[candidate], var) -- candidate => var
184 185
				return i, state.candidate2sat[candidate]
			end)
186
			state.sat:clause(-var, unpack(vars)) -- var => (candidate or candidate or ...)
187
		else
Karel Koci's avatar
Karel Koci committed
188
			TRACE("SAT candidate selection empty")
189
			state.missing[pkg] = var -- store that this package (as object not group) points to no candidate
190
		end
191 192 193
		return var
	else
		return group_var
194
	end
195 196
end

197 198
-- Recursively adds dependency to sat. It returns sat variable for whole dependency.
function sat_dep_traverse(state, activator, deps)
199
	if type(deps) == 'string' or deps.tp == 'package' or deps.tp == 'dep-package' then
200
		return sat_dep(state, deps, deps.version)
201 202 203 204
	end
	if deps.tp == 'dep-not' then
		assert(#deps.sub == 1)
		-- just do negation of var, so 'not' is propagated to upper clause
205
		return -sat_dep_traverse(state, activator, deps.sub[1])
206 207 208
	end
	local wvar = state.sat:var()
	if deps.tp == 'dep-and' then
209
		TRACE("SAT dep and var: " .. tostring(wvar))
210
		-- wid => var for every variable. Result is that they are all in and statement.
211
		local vars = {}
212
		for _, sub in ipairs(deps.sub or deps) do
213 214 215
			local var = sat_dep_traverse(state, activator, sub)
			state.sat:clause(-activator, -wvar, var) -- wvar => var
			table.insert(vars, -var)
216
		end
217
		state.sat:clause(-activator, wvar, unpack(vars)) -- (var and var and ...) => wvar
218
	elseif deps.tp == 'dep-or' then
219
		TRACE("SAT dep or var: " .. tostring(wvar))
220 221 222 223
		-- If wvar is true, at least one of sat variables must also be true, so vwar => vars...
		local vars = {}
		local lastpen = nil
		for _, sub in ipairs(deps.sub) do
224 225 226
			local var = sat_dep_traverse(state, activator, sub)
			state.sat:clause(-activator, -var, wvar) -- var => wvar
			lastpen = sat_penalize(state, activator, var, state.penalty_or, lastpen)
227
			table.insert(vars, var)
228
		end
229
		state.sat:clause(-activator, -wvar, unpack(vars)) -- wvar => (var and var and ...)
230 231
	else
		error(utils.exception('bad value', "Invalid dependency description " .. (deps.tp or "<nil>")))
232
	end
233
	return wvar
234 235 236 237 238 239
end

--[[
Build dependencies for all touched packages. We do it recursively across
dependencies of requested packages, this makes searched space smaller and building
it faster.
240

241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
Note that we are not checking if package has some real candidates or if it even
exists. This must be resolved later.
Initialize and execute sat_build. This returns table containing following fields:
 pkg2sat - Name of package group to associated sat variable
 candidate2sat - Candidate object to associated sat variable
 req2sat - Request object to associated sat variable
 missing - Table of all package groups (key is string) and dependencies on specific candidates (key is table), where value is sat variable
 penalty_candidates - Array of arrays of penalty variables for candidates.
 penalty_or - Array of arrays of penalty variables for or dependencies.
]]
local function sat_build(sat, pkgs, requests)
	local state = {
		pkg2sat = {},
		candidate2sat = {},
		req2sat = {},
256
		missing = {}, -- This is table where key is either package group (string) or specific package (object) and value is SAT variable (number)
257 258 259 260 261
		penalty_candidates = {},
		penalty_or = {},
		pkgs = pkgs, -- pass pkgs to other sat_* functions this way
		sat = sat -- picosat object
	}
262 263
	-- Go trough requests and add them to SAT
	for _, req in ipairs(requests) do
264
		if not pkgs[req.package.name] and not req.optional then
265 266
			error(utils.exception('inconsistent', "Requested package " .. req.package.name .. " doesn't exists."))
		end
267
		local req_var = sat:var()
Karel Koci's avatar
Karel Koci committed
268
		TRACE("SAT add request for " .. req.package.name .. " var:" .. tostring(req_var))
269
		local target_var = sat_dep(state, req.package, req.version, req.repository)
270 271 272 273 274 275 276
		if req.tp == 'install' then
			sat:clause(-req_var, target_var) -- implies true
		elseif req.tp == 'uninstall' then
			sat:clause(-req_var, -target_var) -- implies false
		else
			error(utils.exception('bad value', "Unknown type " .. tostring(req.tp)))
		end
277
		state.req2sat[req] = req_var
278
	end
279
	return state
280 281
end

282

283
-- Iterate trough all packages in given dependency tree.
284 285 286
-- TODO This goes trough all dependencies, so even negative dependencies and
-- packages used only as conditionals are returned. This is harmless for what we
-- are using it for, but would be better return only real dependencies.
287 288 289 290 291 292 293 294 295 296 297 298
local function pkg_dep_iterate_internal(deps)
	if #deps == 0 then
		return nil
	end
	local d = deps[#deps]
	deps[#deps] = nil
	if type(d) == 'string' or d.tp == 'package' or d.tp == 'dep-package' then
		return deps, d
	else
		assert(type(d) == 'table')
		utils.arr_append(deps, d.sub or d)
		return pkg_dep_iterate_internal(deps)
299
	end
300 301 302
end
function pkg_dep_iterate(pkg_deps)
	return pkg_dep_iterate_internal, { pkg_deps }
303 304 305 306 307 308 309 310
end

--[[
Create new plan, sorted so that packages with dependency on some other installed
package is planned after such package. This is not of course always possible
and so when we encounter cyclic dependencies we just cut circle in some random
point and prints warning for packages that will be inconsistent during
installation process. Exception is critical packages, for those no cycles are
311 312 313 314 315
allowed and result would be an error.
If packages has no candidate (so can't be installed) we fail or we print warning
if it should be ignored. We remember whole stack of previous packages to check if
some other planned package won't be affected too.
Function returns sorted plan.
316 317 318 319 320 321 322 323 324
]]--
local function build_plan(pkgs, requests, sat, satmap)
	local plan = {}
	local planned = {} -- Table where key is name of already planned package group and value is index in plan
	local wstack = {} -- array of packages we work on
	local inwstack = {} -- table of all packages we work on where key is name and value is index
	local inconsistent = {} -- Set of potentially inconsistent packages (might fail their post-install scrips)
	local missing_dep = {} -- Set of all packages that depends on some missing dependency
	--[[
325 326 327 328 329 330 331
	Plans given package (request) and all of its dependencies. Argument plan_pkg is
	"package" or "dep-package" or string (name of package group). ignore_missing
	is extra option of package allowing ignore of missing dependencies.
	ignore_missing_pkg is extra option of package allowing to ignore request if
	there is not target for such package. And parent_str is string used for
	warning and error messages containing information about who requested given
	package.
332
	--]]
333 334
	local function pkg_plan(plan_pkg, ignore_missing, ignore_missing_pkg, parent_str)
		local name = plan_pkg.name or plan_pkg -- it can be object of type "package" or "dep-package" or string containing name of package group
335 336 337 338
		if not sat[satmap.pkg2sat[name]] then -- This package group is not selected, so we ignore it.
			-- Note: In special case when package provides its own dependency package group might not be selected and so we should at least return enpty table
			return {}
		end
339 340
		local missing_pkg = satmap.missing[plan_pkg] or satmap.missing[name]
		if missing_pkg and sat[missing_pkg] then -- If missing package (name) or package dependency (plan_pkg) is selected
341 342 343 344 345 346 347 348
			if ignore_missing or ignore_missing_pkg then
				missing_dep[name] = true
				utils.table_merge(missing_dep, utils.arr2set(wstack)) -- Whole working stack is now missing dependency
				WARN(parent_str .. " " .. name .. " that is missing, ignoring as requested.")
			else
				error(utils.exception('inconsistent', parent_str .. " " .. name .. " that is not available."))
			end
		end
349 350 351 352 353 354 355 356
		if planned[name] then -- Already in plan, which is OK
			if missing_dep[name] then -- Package was added to plan with ignored missing dependency
				if ignore_missing or ignore_missing_pkg then
					WARN(parent_str .. " " .. name .. " that's missing or misses some dependency. Ignoring as requested")
				else
					error(utils.exception('inconsistent', parent_str .. " " .. name .. " that's missing or misses some dependency. See previous warnings for more info."))
				end
			end
357
			return {plan[planned[name]]}
358
		end
359
		local pkg = pkgs[name]
360 361 362 363 364 365 366 367 368 369 370
		-- Check for cycles --
		if inwstack[name] then -- Already working on it. Found cycle.
			for i = inwstack[name], #wstack, 1 do
				local inc_name = wstack[i]
				if not inconsistent[inc_name] then -- Do not warn again
					WARN("Package " .. inc_name .. " is in cyclic dependency. It might fail its post-install script.")
				end
				inconsistent[inc_name] = true
			end
			return
		end
371 372
		-- Found selected candidates for this package group
		local candidates = {}
373 374
		for _, cand in pairs((pkg or {}).candidates or {}) do
			if sat[satmap.candidate2sat[cand]] then
375 376 377 378 379 380 381 382 383
				if cand.Package == name then
					-- If we have candidate that is from this package that use is exclusively.
					candidates = {cand}
					break -- SAT ensures that there is always only the one such candidate so we ignore the rest
				else
					-- Otherwise collect all candidates that provide this package
					-- Note: We can't decide which one is the one providing this package so we plan them all.
					table.insert(candidates, cand)
				end
384 385
			end
		end
386
		if not next(candidates) and not utils.multi_index(pkg, 'modifier', 'virtual') then return end -- If no candidates, then we have nothing to be planned. Exception is if this is virtual package.
387 388 389
		-- Recursively add all packages this package depends on --
		inwstack[name] = #wstack + 1 -- Signal that we are working on this package group.
		table.insert(wstack, name)
390
		for _, p in pkg_dep_iterate(utils.multi_index(pkg, 'modifier', 'deps') or {}) do -- plan package group dependencies
391
			pkg_plan(p, ignore_missing or utils.multi_index(pkg, 'modifier', 'optional'), false, "Package " .. name .. " requires package")
392
		end
393 394 395 396 397 398
		if not next(candidates) then return end -- We have no candidate, but we passed previous check because it's virtual
		local r = {}
		local no_pkg_candidate = true
		for _, candidate in pairs(candidates) do -- Now plan candidate's dependencies and packages that provides this package
			if candidate.Package ~= name then
				-- If Candidate is from other group, then plan that group instead now.
399
				utils.arr_append(r, pkg_plan(candidate.Package, ignore_missing, ignore_missing_pkg, parent_str) or {})
400 401 402 403
				-- Candidate dependencies are planed as part of pkg_plan call here
			else
				no_pkg_candidate = false
				for _, p in pkg_dep_iterate(utils.multi_index(candidate, 'deps') or {}) do
404
					pkg_plan(p, ignore_missing or utils.multi_index(pkg, 'modifier', 'optional'), false, "Package " .. name .. " requires package")
405 406 407
				end
			end
		end
408 409
		table.remove(wstack, inwstack[name])
		inwstack[name] = nil -- Our recursive work on this package group ended.
410 411
		if no_pkg_candidate then
			return r -- in r we have candidates providing this package
412
		end
413 414
		-- And finally plan it --
		planned[name] = #plan + 1
415
		r = {
416
			action = 'require',
417
			package = candidates[1],
418
			modifier = (pkg or {}).modifier or {},
419
			critical = false,
420 421 422
			name = name
		}
		plan[#plan + 1] = r
423
		return {r}
424 425
	end

426
	-- We plan packages with immediate replan first to ensure that such replan happens as soon as possible.
427
	for name, pkg in pairs(pkgs) do
428
		-- pkgs contains all packages so we have to check if package is in sat at all
429
		if utils.multi_index(pkg, 'modifier', 'replan') == "immediate" and satmap.pkg2sat[name] and not (satmap.missing[pkg] or satmap.missing[name]) then -- we ignore missing packages, as they wouldn't be planned anyway and error or warning should be given by requests and other packages later on.
430 431 432 433
			pkg_plan(name, false, false, 'Planned package with replan enabled'); -- we don't expect to see this parent_str because we are planning this first, but it theoretically can happen so this makes at least some what sense.
		end
	end

434
	for _, req in pairs(requests) do
435 436
		if sat[satmap.req2sat[req]] then -- Plan only if we can satisfy given request
			if req.tp == "install" then -- And if it is install request, uninstall requests are resolved by not being planned.
437
				local pln = pkg_plan(req.package, false, req.optional, 'Requested package')
438
				-- Note that if pln is nil than we ignored missing package. We have to compute with that here
439 440
				if pln then
					if req.reinstall then
441 442 443
						for _, p in pairs(pln) do
							p.action = 'reinstall'
						end
444 445
					end
					if req.critical then
446 447 448 449 450
						for _, p in pairs(pln) do
							p.critical = true
							if inconsistent[p.name] then -- Check if critical didn't end up in cyclic dependency (Note name from returned package was used not request because it might have been provided by some other package)
								error(utils.exception('inconsistent', 'Package ' .. req.package.name .. ' is requested as critical. Cyclic dependency is not allowed for critical requests.', { critical = true }))
							end
451 452
						end
					end
453
				end
454
			end
455 456 457 458 459 460 461 462 463 464 465
		else
			-- We don't expect critical. If critical request wasn't satisfied we already failed.
			local str_ver = ""
			if req.version then
				str_ver = " version:" .. tostring(req.package.version)
			end
			local str_repo = ""
			if req.repository then
				str_repo = " repository:" .. tostring(req.repository.name)
			end
			WARN("Request not satisfied to " .. req.tp .. " package: " .. req.package.name .. str_ver .. str_repo)
466 467 468 469 470 471
		end
	end

	return plan
end

472 473 474 475 476
--[[
Take list of available packages (in the format of pkg candidate groups
produced in postprocess.available_packages) and list of requests what
to install and remove. Produce list of packages, in the form:
{
477
  {action = "require"/"reinstall", package = pkg_source, modifier = modifier}
478 479 480
}

The action specifies if the package should be made present in the system (installed
481
if missing) or reinstalled (installed no matter if it is already present)
482 483 484 485 486 487 488 489 490
• Required to be installed
• Required to be reinstalled even when already present (they ARE part of the previous set)

The pkg_source is the package object (in case it contains the source field or is virtual)
or the description produced from parsing the repository. The modifier is the object
constructed from package objects during the aggregation, holding additional processing
info (hooks, etc).
]]
function required_pkgs(pkgs, requests)
Karel Koci's avatar
Karel Koci committed
491
	local sat = picosat.new()
492
	-- Tables that's mapping packages, requests and candidates with sat variables
493
	local satmap = sat_build(sat, pkgs, requests)
494 495 496 497 498 499 500 501

	-- Sort all requests to groups by priority
	local reqs_by_priority = {}
	local reqs_critical = {}
	for _, req in pairs(requests) do
		if req.tp == 'install' and req.critical then
			table.insert(reqs_critical, req)
		else
502
			assert(req.priority)
503 504 505
			if not reqs_by_priority[req.priority] then reqs_by_priority[req.priority] = {} end
			if req.tp ~= (utils.map(reqs_by_priority[req.priority], function(_, r) return r.package.name, r.tp end)[req.package.name] or req.tp) then
				error(utils.exception('invalid-request', 'Requested both Install and Uninstall with same priority for package ' .. req.package.name))
506
			end
507
			table.insert(reqs_by_priority[req.priority], req)
508
		end
509
	end
510
	reqs_by_priority = utils.arr_inv(utils.arr_prune(reqs_by_priority))
511 512 513 514 515 516 517

	-- Executes sat solver and adds clauses for maximal satisfiable set
	local function clause_max_satisfiable()
		sat:satisfiable()
		local maxassume = sat:max_satisfiable() -- assume only maximal satisfiable set
		for assum, _ in pairs(maxassume) do
			sat:clause(assum)
518
		end
519 520 521 522
		sat:satisfiable() -- Reset assumptions (TODO isn't there better solution to reset assumptions?)
	end

	-- Install critical packages requests (set all critical packages to be true)
523
	DBG("Resolving critical packages")
524 525 526 527 528
	for _, req in ipairs(reqs_critical) do
		sat:clause(satmap.req2sat[req])
	end
	if not sat:satisfiable() then
		-- TODO This exception should probably be saying more about why. We can assume variables first and inspect maximal satisfiable set then.
529
		error(utils.exception('inconsistent', "Packages marked as critical can't satisfy their dependencies together.", {critical = true}))
530 531 532
	end

	-- Install and Uninstall requests.
533
	DBG("Resolving Install and Uninstall requests")
534
	for _, reqs in ipairs(reqs_by_priority) do
535 536 537
		for _, req in pairs(reqs) do
			-- Assume all request for this priority
			sat:assume(satmap.req2sat[req])
538
		end
539
		clause_max_satisfiable()
540
	end
541

542
	-- Deny any packages missing, without candidates or dependency on missing version if possible
543
	DBG("Denying packages without any candidate")
544 545
	for _, var in pairs(satmap.missing) do
		sat:assume(-var)
546
	end
547 548
	clause_max_satisfiable()

Karel Koci's avatar
Karel Koci committed
549
	-- Chose alternatives with penalty variables
550
	DBG("Forcing penalty on expressions with free alternatives")
551
	local function penalize(penalties)
552 553
		for _, penalty in ipairs(penalties) do
			sat:assume(penalty)
554 555
		end
		clause_max_satisfiable()
Karel Koci's avatar
Karel Koci committed
556
	end
557 558 559
	-- Candidates has precedence before dependencies, because we prefer newest possible package.
	penalize(satmap.penalty_candidates)
	penalize(satmap.penalty_or)
560 561

	-- Now solve all packages selections from dependencies of already selected packages
562
	DBG("Deducing minimal set of required packages")
563 564 565 566 567 568 569 570 571 572 573
	for _, var in pairs(satmap.pkg2sat) do
		-- We assume false (not selected) for all packages
		sat:assume(-var)
	end
	clause_max_satisfiable()
	-- We call this here again to calculate variables with all new clauses.
	-- Previous call in clause_max_satisfiable is with assumptions, so results
	-- from such calls aren't correct.
	sat:satisfiable() -- Set variables to result values

	return build_plan(pkgs, requests, sat, satmap)
574 575
end

576
--[[
577 578
Go trough the list of requests and create list of all packages required to be
installed. Those packages are not on system at all or are in different versions.
579
]]
580
local function check_install_version(status, requests)
581 582
	local installed = {}
	for pkg, desc in pairs(status) do
583 584 585
		if not desc.Status or desc.Status[3] == "installed" then
			installed[pkg] = desc.Version or ""
		end
586 587
	end
	local unused = utils.clone(installed)
588
	local install = {}
589 590 591
	-- Go through the requests and look which ones are needed and which ones are satisfied
	for _, request in ipairs(requests) do
		local installed_version = installed[request.name]
592 593
		-- TODO: Handle stand-alone packages
		local requested_version = utils.multi_index(request, "package", "Version") or ""
594 595
		if request.action == "require" then
			if not installed_version or installed_version ~= requested_version then
596
				DBG("Want to install " .. request.name)
597
				install[request.name] = request
598 599 600 601 602 603
			else
				DBG("Package " .. request.name .. " already installed")
			end
			unused[request.name] = nil
		elseif request.action == "reinstall" then
			DBG("Want to reinstall " .. request.name)
604
			install[request.name] = request
605 606 607 608 609
			unused[request.name] = nil
		else
			DIE("Unknown action " .. request.action)
		end
	end
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638
	return install, unused
end

--[[
Creates table containing inverted dependencies for given requests. Returned table
has as key name of package and as value set of all packages depending on it.
Example: A -> B -> C results to {["C"] = {["B"] = true}, ["B"] = {["A"] = true}}
]]
local function invert_dependencies(requests)
	local inv = {}
	for _, req in pairs(requests) do
		local alldeps = utils.arr_prune({ req.package.deps, req.modifier.deps })
		for _, dep in pkg_dep_iterate(alldeps) do
			local dname = dep.name or dep
			if not inv[dname] then inv[dname] = {} end
			inv[dname][req.name] = true
		end
	end
	return inv
end

--[[
Go trough the list of requests and install package if it depends on package that
changed its ABI. And also install additional packages listed in abi_change and
abi_change_deep fields.
]]
local function check_abi_change(requests, install)
	local reqs = utils.map(requests, function(_, v) return v.name, v end)
	-- Build inverted dependencies
639
	local invdep -- initialized
640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688
	local function abi_changed(name, abi_ch, causepkg)
		-- Ignore package that we don't request. Also ignore if no abi change is
		-- passed and package is not going to be installed.
		if not reqs[name] or not (install[name] or abi_ch) then
			return
		end
		if not install[name] then
			DBG("ABI change of " .. causepkg .. " causes reinstall of " .. name)
			install[name] = reqs[name]
		end
		local request = reqs[name]
		local dep_abi_ch
		for p in pairs(request.modifier.abi_change or {}) do
			if type(p) == 'table' or type(p) == 'string' then
				abi_changed(p.name or p, abi_ch or "shallow", name)
			elseif type(p) == 'boolean' then
				-- Note: shallow can be overridden by deep afterwards
				dep_abi_ch = abi_ch or "shallow"
			end
		end
		for p in pairs(request.modifier.abi_change_deep or {}) do
			if type(p) == 'table' or type(p) == 'string' then
				abi_changed(p.name or p, "deep", name)
			elseif type(p) == 'boolean' then
				dep_abi_ch = "deep"
			end
		end
		if abi_ch == "deep" then
			dep_abi_ch = abi_ch
		end
		if dep_abi_ch then
			if not invdep then
				invdep = invert_dependencies(requests)
			end
			for name in pairs(invdep[name] or {}) do
				abi_changed(name, dep_abi_ch, name)
			end
		end
	end
	for reqname, _ in pairs(install) do
		abi_changed(reqname, nil, "")
	end
	return install
end

--[[
Go trough the list of unused installed packages and marks them for removal.
]]
local function check_removal(status, unused)
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711
	-- TODO report cycles in dependencies
	local unused_sorted = {}
	local sort_buff = {}
	local function sort_unused(pkg)
		if not sort_buff[pkg] then
			sort_buff[pkg] = true
			-- Unfortunately we have to go trough all dependencies to ensure correct order.
			local deps = postprocess.deps_canon(utils.multi_index(status, pkg, "Depends") or {})
			for _, deppkg in pkg_dep_iterate(deps) do
				sort_unused(deppkg.name or deppkg)
			end
			if unused[pkg] then
				unused[pkg] = nil
				DBG("Want to remove left-over package " .. pkg)
				table.insert(unused_sorted, {
					action = "remove",
					name = pkg,
					package = status[pkg]
				})
			end
			-- Ignore packages that are used or not installed at all
		end
	end
712
	for pkg in pairs(unused) do
713
		sort_unused(pkg)
714
	end
715 716 717 718 719 720 721 722 723
	return utils.arr_inv(unused_sorted)
end

--[[
Go through the list of requests on the input. Pass the needed ones through and
leave the extra (eg. requiring already installed package) out. And creates
additional requests with action "remove", such package is present on system, but
is not required any more and should be removed.
]]
724
function filter_required(status, requests, allow_replan)
725 726 727 728 729 730 731 732 733 734 735 736 737
	local install, unused = check_install_version(status, requests)
	install = check_abi_change(requests, install)
	local result = {}
	local replan = false -- If we are requested to replan after some package, drop the rest of the plan
	for _, request in ipairs(requests) do
		if install[request.name] then
			local req = request
			if request.action == "reinstall" then
				-- Make a shallow copy and change the action requested
				req = utils.shallow_copy(request)
				req.action = "require"
			end
			table.insert(result, req)
738
			if request.modifier.replan == "immediate" and allow_replan then
739 740 741
				replan = true
				break
			end
742 743
		end
	end
744
	if not replan then
745
		-- We don't remove unused packages just yet if we do immediate replan, we do it after the replanning.
746 747
		utils.arr_append(result, check_removal(status, unused))
	end
748 749 750
	return result
end

751
return _M