aboutsummaryrefslogtreecommitdiffstats
path: root/src/solver.c
Commit message (Collapse)AuthorAgeFilesLines
...
* solver: implement backwards jumping and various other optimizationsTimo Teräs2012-02-211-149/+215
|
* solver: rewrite backtracking and scoring systemTimo Teräs2012-02-201-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.
* apk: fix some unharmful leaks reported by valgrindTimo Teräs2012-02-171-0/+1
|
* solver: get rid of saved score in backtrackingTimo Teräs2012-02-171-41/+57
| | | | also, discover late if package is needed or not.
* solver: convert some package state flags to bitfieldsTimo Teräs2012-02-161-11/+13
|
* solver: name's unlocked chosen is always next package getting lockedTimo Teräs2012-02-161-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.
* solver: rework internals a bitTimo Teräs2012-02-161-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
* solver: fix allowed pinning calculationTimo Teräs2012-02-161-2/+2
|
* solver: record repository tag, and flags in solutionTimo Teräs2012-02-161-55/+92
| | | | | name state could get overwritten later, so we can't use that when generating the changeset.
* solver: remove an unneeded name state variableTimo Teräs2012-02-161-5/+0
|
* solver, db: repository pinning improvementsTimo Teräs2012-02-151-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
* solver: fix regression from "calculate branch minimum penalty early"Timo Teräs2012-01-201-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.
* solver, upgrade: properly detect missing repository tagsTimo Teräs2012-01-171-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
* solver: fix change ordering of removed pages in relation to installedTimo Teräs2012-01-171-5/+6
|
* solver: calculate branch minimum penalty earlyTimo Teräs2012-01-171-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.
* add: make repository tag pinning strongerTimo Teräs2012-01-131-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.
* solver: print repository tag when committing package changesTimo Teräs2012-01-121-9/+22
|
* db, solver: refuse committing changes if there is missing tagsTimo Teräs2012-01-121-0/+10
|
* solver: report number of (mega)bytes usedTimo Teräs2011-12-271-4/+11
|
* solver: fix error detection for certain unsatisfiability casesTimo Teräs2011-11-231-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.
* solver: fix zero score comparisonTimo Teräs2011-11-011-1/+1
|
* solver: return changeset even for partial solutionsTimo Teräs2011-11-011-12/+8
| | | | otherwise --force does might not work during boot.
* solver: consider world dependencies to determining exit scoreTimo Teräs2011-11-011-2/+4
|
* solver: misc fixesTimo Teräs2011-10-311-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.
* solver: fix indentation of package lists (in interactive mode)Timo Teräs2011-10-291-1/+1
| | | | broken in commit bfd53b59d2e62e17 (print: minor cleanup to indented writer).
* solver, db: implement repository pinningTimo Teräs2011-10-291-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
* solver, pkg: implement versioned conflictsTimo Teräs2011-10-241-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.
* solver: preference scoringTimo Teräs2011-10-141-75/+112
| | | | | Should now choose packages better if the best available version is uninstallable for some reason.
* solver: return error code if things fail during package installTimo Teräs2011-09-281-2/+1
|
* solver: evaluate penalty of unsatisfiable name earlyTimo Teräs2011-09-281-4/+16
| | | | | this prunes the search tree considerably and fixes a speed regression introduced in an earlier commit.
* solver: fix backtrackingTimo Teräs2011-09-221-32/+33
| | | | | | We need to refresh all name states after backtracking as options that were excluding due to topology ordering might have become available.
* solver: inheritable solver flagsTimo Teräs2011-09-161-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.
* solver: fix sorting when solver is used multiple times within runTimo Teräs2011-09-151-1/+2
| | | | | namely this fixes apk upgrade without --no-self-upgrade when the solver is called twice.
* solver: make state pointers completely internalTimo Teräs2011-09-141-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.
* solver, db: run triggers in dependency orderTimo Teräs2011-09-141-4/+45
| | | | fixes #738
* upgrade: reimplement self-upgrade (after solver merge)Timo Teräs2011-09-141-1/+13
|
* all: update copyright year statementTimo Teräs2011-09-131-1/+1
|
* solver: add per-name specific flags, and fix the fix appletTimo Teräs2011-09-131-14/+29
|
* print: minor cleanup to indented writerTimo Teräs2011-09-091-1/+1
|
* del: fix recursive deletion and messages (after solver merge)Timo Teräs2011-09-091-12/+13
| | | | | Deduce the world dependencies to remove locally, and same for the additional messages about packages not deleted.
* applets: start using solver codeTimo Teräs2011-09-091-83/+447
| | | | | | | | | still todo: - 'fix' is missing - 'del -R' does not work - 'upgrade' does not do self-upgrade first ... and a lot of testing.
* solver: report 'complete' solutions with errorsTimo Teräs2011-09-051-28/+27
| | | | | | Allow to select packages that conflict in case we are looking for errors. This allows 'add --force' to install (on boot) the set of packages with minimum conflicts.
* solver: reintroduce install_if supportTimo Teräs2011-08-181-46/+185
| | | | | | * each package name has two sorting positions, one which causes install_if triggers to be run, and other for bulk dependencies * fix also inverted ordering of package installations
* solver: move topology sorting to solver codeTimo Teräs2011-08-051-38/+92
| | | | | this allows quite some optimizations to running time and memory requirements.
* solver: generate proper error messagesTimo Teräs2011-08-011-185/+181
| | | | | | | | | * the solver no longer does look-ahead locking of names (could be possibly optimized later); instead names are now always ordered strictly to properly detect the package names which are unsolveable * basic error tests added, so we can see the most likely problem in dependencies easily
* solver: don't consider package that we can't haveTimo Teräs2011-07-271-2/+26
| | | | | Packages that need (re-)installation but which are not available, are excluded now properly.
* solver: permutate each preferred solution firstTimo Teräs2011-07-271-57/+55
| | | | The first found solution is the most preferred one then.
* solver: new package selection logic (which is not yet used)Timo Teräs2011-07-261-0/+563
* basic code for a backtracking, forward checking dependency satisfier * works better when there are tricky dependencies to solve (when can't just upgrade everything to most preferred versions) * the new code always evaluates all of 'world' constraints (old code just does incremental updates based on heuristics) * is probably somewhat slower than old code (probably unnoticeable difference in most cases) * makes easier to write support for provides and repository pinning * test applet and a bunch of test cases added which uses the new code * from the old feature set install_if is not yet implemented
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-03 14:46:28 +0000