summaryrefslogtreecommitdiff
path: root/src/solver.c
AgeCommit message (Collapse)AuthorFilesLines
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
2012-02-21solver: implement backwards jumping and various other optimizationsTimo Teräs1-149/+215
2012-02-20solver: rewrite backtracking and scoring systemTimo Teräs1-406/+690
* properly do absolute scoring now, the previous scoring where preference could get reduced could have caused incorrect early pruning of search tree * backtracking is now separated from package state, and first branching point is the decision if a name is left unassigned or if something _has_ to be assigned. this allows multiple future search tree optimizations like handling of common dependencies early. * merge common dependency names early to provide deeper forward checking.
2012-02-17apk: fix some unharmful leaks reported by valgrindTimo Teräs1-0/+1
2012-02-17solver: get rid of saved score in backtrackingTimo Teräs1-41/+57
also, discover late if package is needed or not.
2012-02-16solver: convert some package state flags to bitfieldsTimo Teräs1-11/+13
2012-02-16solver: name's unlocked chosen is always next package getting lockedTimo Teräs1-35/+28
Instead of "skipping" certain packages, we include them as-if required, and at expansion time we decide if they actually need to be considered for installation. This cleans up the expansion main loop a little bit and makes the code work together better.
2012-02-16solver: rework internals a bitTimo Teräs1-138/+190
* cleaned up little bit on the internal state machine * the decision applying mechanism now aborts early to avoid work if we are approaching bad solution candidate * package availability checking is now done on-demand; which could still be improved
2012-02-16solver: fix allowed pinning calculationTimo Teräs1-2/+2
2012-02-16solver: record repository tag, and flags in solutionTimo Teräs1-55/+92
name state could get overwritten later, so we can't use that when generating the changeset.
2012-02-16solver: remove an unneeded name state variableTimo Teräs1-5/+0
2012-02-15solver, db: repository pinning improvementsTimo Teräs1-48/+73
* solver internally calculates now using tags; not repository masks * installeddb now contains the tag name where the package came from -> we can now handle upgrades properly * the pinning is still a preference, and not strictly enforced; versioned dependencies may overrule preference
2012-01-20solver: fix regression from "calculate branch minimum penalty early"Timo Teräs1-7/+21
Forgot to reset per-name penalty when it got locked by apply_decision. This also fine tunes compare_package_preference() to always prefer packages specified on command line speeding up calculation certain complicated solutions.
2012-01-17solver, upgrade: properly detect missing repository tagsTimo Teräs1-2/+2
* upgrade needs explicit check so we don't try self-upgrade (which would print additional messages on screen) * add can fix problems, so check against the new world * merge the code in few places
2012-01-17solver: fix change ordering of removed pages in relation to installedTimo Teräs1-5/+6
2012-01-17solver: calculate branch minimum penalty earlyTimo Teräs1-55/+97
Previously we would cache the penalty when evaluating the final solution, and adding that until we backtrack to first topology position changing that penalty. However, we can just keep track of minimum penalty based on name state, and add it. This allows us to bail out early on bad branches because we know in advance how things will turn out.
2012-01-13add: make repository tag pinning strongerTimo Teräs1-8/+19
Previously we would not upgrade just by doing "apk add foo@tag" if foo was already installed. It required explicit '-u'. This allows 'apk add' to explicitly prefer the newly specified pinning.
2012-01-12solver: print repository tag when committing package changesTimo Teräs1-9/+22
2012-01-12db, solver: refuse committing changes if there is missing tagsTimo Teräs1-0/+10
2011-12-27solver: report number of (mega)bytes usedTimo Teräs1-4/+11
2011-11-23solver: fix error detection for certain unsatisfiability casesTimo Teräs1-2/+46
did not properly detect as error if name could not be satisfied due to being available in tagged repository which is not enabled.
2011-11-01solver: fix zero score comparisonTimo Teräs1-1/+1
2011-11-01solver: return changeset even for partial solutionsTimo Teräs1-12/+8
otherwise --force does might not work during boot.
2011-11-01solver: consider world dependencies to determining exit scoreTimo Teräs1-2/+4
2011-10-31solver: misc fixesTimo Teräs1-9/+22
caused upgrading package X with "apk add path/to/x...apk" where the package file was not in any repository to not work properly.
2011-10-29solver: fix indentation of package lists (in interactive mode)Timo Teräs1-1/+1
broken in commit bfd53b59d2e62e17 (print: minor cleanup to indented writer).
2011-10-29solver, db: implement repository pinningTimo Teräs1-5/+34
Improves /etc/apk/repositories format so you can say: http://nl.alpinelinux.org/alpine/v2.3/main @edge http://nl.alpinelinux.org/alpine/edge/main @testing http://nl.alpinelinux.org/alpine/edge/testing After which you can pin dependencies to these tags using: apk add stableapp newapp@edge bleedingapp@testing Apk will now by default only use the untagged repositories, but adding a tag to specific dependency: 1. will prefer that tag for the name 2. allowing pulling in dependencies from that tag (though, it prefers untagged packages to satisfy deps if possible) fixes #575
2011-10-24solver, pkg: implement versioned conflictsTimo Teräs1-6/+4
One can now say in dependency "!foo<2" which means, that if foo is installed, it needs to be >=2, but it's not a required dependency.
2011-10-14solver: preference scoringTimo Teräs1-75/+112
Should now choose packages better if the best available version is uninstallable for some reason.
2011-09-28solver: return error code if things fail during package installTimo Teräs1-2/+1
2011-09-28solver: evaluate penalty of unsatisfiable name earlyTimo Teräs1-4/+16
this prunes the search tree considerably and fixes a speed regression introduced in an earlier commit.
2011-09-22solver: fix backtrackingTimo Teräs1-32/+33
We need to refresh all name states after backtracking as options that were excluding due to topology ordering might have become available.
2011-09-16solver: inheritable solver flagsTimo Teräs1-26/+108
allow per-name solver flags to be inheritable, and use them in self-upgrade, add -u and the fix applet. this gives more familiar behaviour for the upgrades.
2011-09-15solver: fix sorting when solver is used multiple times within runTimo Teräs1-1/+2
namely this fixes apk upgrade without --no-self-upgrade when the solver is called twice.
2011-09-14solver: make state pointers completely internalTimo Teräs1-32/+29
the only bit of information needed in solver commit is the "hard" topology sorting information for trigger ordering. fixes a bug in "apk del" which uses the state pointers to do intermediate calculations between solution solving and commit.
2011-09-14solver, db: run triggers in dependency orderTimo Teräs1-4/+45
fixes #738
2011-09-14upgrade: reimplement self-upgrade (after solver merge)Timo Teräs1-1/+13
2011-09-13all: update copyright year statementTimo Teräs1-1/+1
2011-09-13solver: add per-name specific flags, and fix the fix appletTimo Teräs1-14/+29
2011-09-09print: minor cleanup to indented writerTimo Teräs1-1/+1
2011-09-09del: fix recursive deletion and messages (after solver merge)Timo Teräs1-12/+13
Deduce the world dependencies to remove locally, and same for the additional messages about packages not deleted.
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-11-13 15:28:28 +0000