summaryrefslogtreecommitdiff
path: root/src/solver.c
AgeCommit message (Collapse)AuthorFilesLines
2013-01-28solver: remove backjumping by nameTimo Teräs1-28/+3
It is incorrect optimization causing valid solutions to be skipped. Any performance it might've gained, should be fixed by reintroduction of the minimum penalty logic added in previous commit.
2013-01-28solver: reintroduce minimum penalty logicTimo Teräs1-49/+55
Basic per-name per-package specific scoring added.
2013-01-22solver: do not backtrack over "exclude none"Timo Teräs1-1/+8
Otherwise we can return no solution at all instead of partially satisfied solution (and give proper error message).
2013-01-21solver: simplify strength evaluation in constraint handlingTimo Teräs1-20/+8
2013-01-21solver: check if solution is not found at allTimo Teräs1-0/+6
This is an internal error.
2013-01-18solver: fix reset of last_touched to zeroTimo Teräs1-2/+2
2013-01-18solver: some code clean upsTimo Teräs1-5/+5
2013-01-18solver: build fix for debug print on x86_64Natanael Copa1-1/+1
use %zu for size_t
2013-01-18solver: fix name assignment logic to not mess up internal stateTimo Teräs1-11/+10
Should get rid of error messages like: ERROR: Saved_score {4/0/0,74} != score {6/0/0,74}
2012-11-04solver: fix package prefence calculation a bitTimo Teräs1-1/+3
2012-10-08solver: additional backjumping schemeTimo Teräs1-11/+48
Enabled when all attempts to satisfy a name failed, we know that we can ignore all decisions until we find a decision affecting the name we wanted to satisfy.
2012-10-08solver: optimize backjumpingTimo Teräs1-7/+7
to be functional when backtracking
2012-10-08solver: properly calculate decision "strength" with providesTimo Teräs1-17/+13
2012-10-05solver: fix back jumping once moreTimo Teräs1-17/+33
2012-10-05solver: record dependency apk_name in apk_decisionTimo Teräs1-51/+19
We can't just use the primary name, as that would mess up backtracking. We need to record the name which caused the name to get considered - that way the right last_touched_decision is used on backtracking.
2012-10-03solver: various fixesTimo Teräs1-14/+58
* push_decision expects to always get the package primary 'name' as apk_name. ASSERT that and fix problem cases. (though - this might need to be reverted, and store the non primary name in apk_decision instead to accomodate for better backtracking optimizations) * fix error reporting of virtual package names * make 'assign_name' errors soft. the incorrect packages just are no longer consider instead of aborting whole calculation. * fix backtracking of virtual packages that are not depended directly
2012-10-03solver: improve assert error messagesNatanael Copa1-2/+3
Print name of package and void double "ERROR"
2012-10-03solver: fix compile with -Werror on 64bitNatanael Copa1-1/+1
2012-09-20apk: implement --progress-fd to write progress to a specified fdTimo Teräs1-17/+27
2012-04-27solver: fix install_if triggers on cyclic and early depsTimo Teräs1-11/+15
2012-04-27solver: fix backtracking with install_if dependenciesTimo Teräs1-17/+20
2012-03-31solver: fix a type from previous commitTimo Teräs1-1/+1
2012-03-31solver: fix installation of non-repository packagesTimo Teräs1-1/+2
2012-03-01solver: properly set allowed flag for installed packagesTimo Teräs1-3/+6
2012-02-29solver: rename some fieldsTimo Teräs1-24/+25
2012-02-29solver: merge apk_name_state to apk_nameTimo Teräs1-223/+136
apk_name_state is now quite small; and we avoid overhead of two pointers (+ malloc overhead) when we just make it part of apk_name. It also fixes some problems (that got introduced) where apk_name_state was not allocated.
2012-02-29solver, test: make conflicts unconditionalTimo Teräs1-13/+36
Solver will now never report partial solution where a conflict constraint is not satisfied. The is because with --force we might install the partial solution; and if conflicted packages were to be installed we might have extra trouble.
2012-02-28solver: ask confirmation in interactive mode only if there's changesTimo Teräs1-1/+2
2012-02-28solver: do not consider non-allowed packages in main loopTimo Teräs1-43/+32
Instead cache the allowed pinning decision, and use it. Update install decision heuristic to also use this cached information.
2012-02-28solver: consider provided names also for preferenceTimo Teräs1-2/+13
ref #574
2012-02-28solver: fix conflicting provides detectionTimo Teräs1-2/+15
ref #574
2012-02-28solver: allow multiple packages with same virtual providesTimo Teräs1-8/+14
ref #574
2012-02-27solver, test: implements more provides things, add testsTimo Teräs1-30/+92
ref #574
2012-02-27solver: have most inherited things per-package and clean upsTimo Teräs1-156/+168
Required for provides support as package might be pulled in via non-primary package name. This allows relatively easily to pass through inherited flags via the provided names. ref #574.
2012-02-27solver: remove minimum penalty logicTimo Teräs1-49/+7
Reasoning: - it is less useful now that we do not do common dependency merging - provides support would make the required logic overly complicated - callgrind reports that depending on the case it can improve or decrease performance (the overhead pays off only in some cases); the difference is not large either way
2012-02-24solver, dot: elementary provides fixesTimo Teräs1-21/+57
implementation is still not near finished, but now at least it can handle it to a minimum degree. many cases are not done right yet, though. ref #574.
2012-02-24all: introduce apk_provides and use it in apk_nameTimo Teräs1-73/+79
in preparation for provides support. implements also some dependency satisfaction helper routines. ref #574.
2012-02-24solver: unallowed pinning is worse than changing installed packageTimo Teräs1-10/+7
2012-02-24solver: non preferred actions are worse then non preferred pinningTimo Teräs1-6/+16
Otherwise we might start to change packages unexpectedly when not upgrading. This also fixes some other things the solver might've decided to do. Add also few test cases to detect bad behaviour.
2012-02-24test: improve pinning testsTimo Teräs1-1/+4
2012-02-23solver: fix output of broken dependenciesTimo Teräs1-1/+1
2012-02-23solver: report size difference in kibi- or mebibytesTimo Teräs1-5/+11
2012-02-22solver: lock early names that have only single option leftTimo Teräs1-3/+13
care is needed to get the score right.
2012-02-22solver: lazily update name state in main loopTimo Teräs1-171/+125
2012-02-22solver: handle fix/reinstall betterTimo Teräs1-30/+36
In case someone did "fix --force" for package for which we have no APK available, we would uninstall the package instead of silently ignoring the request. This could mean worse things. So now we just consider unavailable packages a bad deal for reinstall requests. And will downgrade if necessary. But if we really don't have any APK available, we just skip the request but report it.
2012-02-22solver: transitive dependency requiringTimo Teräs1-12/+41
If n+1 packages depend A, and A depend on B. Add n+1 dependencies to B. Otherwise if someone conflicts B, B might be left out. Leaving package unassigned is no longer a non-preferred action, this fixes the final test case that was failing. And with --force we might even install that scenario. Add also some debug checks.
2012-02-22solver: remove dependency merging; it's not worth itTimo Teräs1-77/+4
callgrind says it's more overhead than improvement. back jumping effectively prunes all bad trees. but can be added later if it becomes needed; due to e.g. provides support.
2012-02-22db, solver, io: scan cache items at startupTimo Teräs1-42/+36
It is faster to just scan the cache directory for existing packages at startup than trying to faccessat() them on demand. It also makes quite a few parts of the code more readable and simpler.
2012-02-21solver: make apk_score a 64-bit int for speedTimo Teräs1-9/+49
2012-02-21solver: remove unneeded flagTimo Teräs1-4/+1
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-01-08 05:21:12 +0000