00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef SATSOLVER_SOLVER_H
00014 #define SATSOLVER_SOLVER_H
00015
00016 #ifdef __cplusplus
00017 extern "C" {
00018 #endif
00019
00020 #include "pooltypes.h"
00021 #include "pool.h"
00022 #include "repo.h"
00023 #include "queue.h"
00024 #include "bitmap.h"
00025 #include "transaction.h"
00026 #include "rules.h"
00027 #include "problems.h"
00028
00029
00030
00031
00032
00033 typedef void (*BestSolvableCb) (Pool *pool, Queue *canditates);
00034 typedef int (*ArchCheckCb) (Pool *pool, Solvable *solvable1, Solvable *solvable2);
00035 typedef int (*VendorCheckCb) (Pool *pool, Solvable *solvable1, Solvable *solvable2);
00036 typedef void (*UpdateCandidateCb) (Pool *pool, Solvable *solvable, Queue *canditates);
00037
00038
00039 struct _Solver;
00040
00041 typedef struct _Solver {
00042 Pool *pool;
00043 Queue job;
00044
00045 Transaction trans;
00046
00047 Repo *installed;
00048
00049
00050
00051
00052
00053 Rule *rules;
00054 Id nrules;
00055
00056 Queue ruleassertions;
00057
00058
00059
00060 Id rpmrules_end;
00061
00062 Id featurerules;
00063 Id featurerules_end;
00064
00065 Id updaterules;
00066 Id updaterules_end;
00067
00068 Id jobrules;
00069 Id jobrules_end;
00070
00071 Id infarchrules;
00072 Id infarchrules_end;
00073
00074 Id duprules;
00075 Id duprules_end;
00076
00077 Id choicerules;
00078 Id choicerules_end;
00079 Id *choicerules_ref;
00080
00081 Id learntrules;
00082
00083 Map noupdate;
00084
00085 Map noobsoletes;
00086
00087 Map updatemap;
00088 int updatemap_all;
00089
00090 Map fixmap;
00091 int fixmap_all;
00092
00093 Queue weakruleq;
00094 Map weakrulemap;
00095
00096 Id *watches;
00097
00098
00099
00100
00101
00102 Queue ruletojob;
00103
00104
00105 Queue decisionq;
00106 Queue decisionq_why;
00107
00108 Id *decisionmap;
00109
00110
00111
00112
00113
00114 Queue learnt_why;
00115 Queue learnt_pool;
00116
00117 Queue branches;
00118 int (*solution_callback)(struct _Solver *solv, void *data);
00119 void *solution_callback_data;
00120
00121 int propagate_index;
00122
00123 Queue problems;
00124 Queue solutions;
00125
00126 Queue recommendations;
00127 Queue suggestions;
00128 Queue orphaned;
00129
00130 int stats_learned;
00131 int stats_unsolvable;
00132
00133 Map recommendsmap;
00134 Map suggestsmap;
00135 int recommends_index;
00136
00137 Id *obsoletes;
00138 Id *obsoletes_data;
00139 Id *multiversionupdaters;
00140
00141
00142
00143
00144
00145 int fixsystem;
00146 int allowdowngrade;
00147 int allowarchchange;
00148 int allowvendorchange;
00149 int allowuninstall;
00150 int updatesystem;
00151 int noupdateprovide;
00152 int dosplitprovides;
00153 int dontinstallrecommended;
00154 int ignorealreadyrecommended;
00155 int dontshowinstalledrecommended;
00156
00157
00158 int distupgrade;
00159 int distupgrade_removeunsupported;
00160
00161 int noinfarchcheck;
00162
00163
00164
00165
00166
00167
00168
00169
00170
00171
00172 BestSolvableCb bestSolvableCb;
00173
00174
00175
00176
00177
00178
00179
00180
00181 ArchCheckCb archCheckCb;
00182
00183
00184
00185
00186
00187
00188
00189
00190 VendorCheckCb vendorCheckCb;
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200 UpdateCandidateCb updateCandidateCb;
00201
00202
00203
00204 Queue covenantq;
00205
00206
00207 Map dupmap;
00208 int dupmap_all;
00209 Map dupinvolvedmap;
00210
00211 Map droporphanedmap;
00212 int droporphanedmap_all;
00213
00214 Map cleandepsmap;
00215
00216 Queue *ruleinfoq;
00217 } Solver;
00218
00219
00220
00221
00222
00223 #define SOLVER_SOLVABLE 0x01
00224 #define SOLVER_SOLVABLE_NAME 0x02
00225 #define SOLVER_SOLVABLE_PROVIDES 0x03
00226 #define SOLVER_SOLVABLE_ONE_OF 0x04
00227 #define SOLVER_SOLVABLE_REPO 0x05
00228 #define SOLVER_SOLVABLE_ALL 0x06
00229
00230 #define SOLVER_SELECTMASK 0xff
00231
00232 #define SOLVER_NOOP 0x0000
00233 #define SOLVER_INSTALL 0x0100
00234 #define SOLVER_ERASE 0x0200
00235 #define SOLVER_UPDATE 0x0300
00236 #define SOLVER_WEAKENDEPS 0x0400
00237 #define SOLVER_NOOBSOLETES 0x0500
00238 #define SOLVER_LOCK 0x0600
00239 #define SOLVER_DISTUPGRADE 0x0700
00240 #define SOLVER_VERIFY 0x0800
00241 #define SOLVER_DROP_ORPHANED 0x0900
00242 #define SOLVER_USERINSTALLED 0x0a00
00243
00244 #define SOLVER_JOBMASK 0xff00
00245
00246 #define SOLVER_WEAK 0x010000
00247 #define SOLVER_ESSENTIAL 0x020000
00248 #define SOLVER_CLEANDEPS 0x040000
00249
00250 #define SOLVER_SETEV 0x01000000
00251 #define SOLVER_SETEVR 0x02000000
00252 #define SOLVER_SETARCH 0x04000000
00253 #define SOLVER_SETVENDOR 0x08000000
00254 #define SOLVER_SETREPO 0x10000000
00255 #define SOLVER_NOAUTOSET 0x20000000
00256
00257 #define SOLVER_SETMASK 0x2f000000
00258
00259
00260 #if 1
00261 #define SOLVER_INSTALL_SOLVABLE (SOLVER_INSTALL|SOLVER_SOLVABLE)
00262 #define SOLVER_ERASE_SOLVABLE (SOLVER_ERASE|SOLVER_SOLVABLE)
00263 #define SOLVER_INSTALL_SOLVABLE_NAME (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME)
00264 #define SOLVER_ERASE_SOLVABLE_NAME (SOLVER_ERASE|SOLVER_SOLVABLE_NAME)
00265 #define SOLVER_INSTALL_SOLVABLE_PROVIDES (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES)
00266 #define SOLVER_ERASE_SOLVABLE_PROVIDES (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES)
00267 #define SOLVER_INSTALL_SOLVABLE_UPDATE (SOLVER_UPDATE|SOLVER_SOLVABLE)
00268 #define SOLVER_INSTALL_SOLVABLE_ONE_OF (SOLVER_INSTALL|SOLVER_SOLVABLE_ONE_OF)
00269 #define SOLVER_WEAKEN_SOLVABLE_DEPS (SOLVER_WEAKENDEPS|SOLVER_SOLVABLE)
00270 #define SOLVER_NOOBSOLETES_SOLVABLE (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE)
00271 #define SOLVER_NOOBSOLETES_SOLVABLE_NAME (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE_NAME)
00272 #define SOLVER_NOOBSOLETES_SOLVABLE_PROVIDES (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE_PROVIDES)
00273 #endif
00274
00275
00276 #define SOLVER_PROBLEM_UPDATE_RULE SOLVER_RULE_UPDATE
00277 #define SOLVER_PROBLEM_JOB_RULE SOLVER_RULE_JOB
00278 #define SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP
00279 #define SOLVER_PROBLEM_NOT_INSTALLABLE SOLVER_RULE_RPM_NOT_INSTALLABLE
00280 #define SOLVER_PROBLEM_NOTHING_PROVIDES_DEP SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP
00281 #define SOLVER_PROBLEM_SAME_NAME SOLVER_RULE_RPM_SAME_NAME
00282 #define SOLVER_PROBLEM_PACKAGE_CONFLICT SOLVER_RULE_RPM_PACKAGE_CONFLICT
00283 #define SOLVER_PROBLEM_PACKAGE_OBSOLETES SOLVER_RULE_RPM_PACKAGE_OBSOLETES
00284 #define SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE SOLVER_RULE_RPM_PACKAGE_REQUIRES
00285 #define SOLVER_PROBLEM_SELF_CONFLICT SOLVER_RULE_RPM_SELF_CONFLICT
00286 #define SOLVER_PROBLEM_RPM_RULE SOLVER_RULE_RPM
00287 #define SOLVER_PROBLEM_DISTUPGRADE_RULE SOLVER_RULE_DISTUPGRADE
00288 #define SOLVER_PROBLEM_INFARCH_RULE SOLVER_RULE_INFARCH
00289
00290
00291 extern Solver *solver_create(Pool *pool);
00292 extern void solver_free(Solver *solv);
00293 extern void solver_solve(Solver *solv, Queue *job);
00294
00295 extern void solver_run_sat(Solver *solv, int disablerules, int doweak);
00296 extern void solver_reset(Solver *solv);
00297
00298 extern int solver_dep_installed(Solver *solv, Id dep);
00299 extern int solver_splitprovides(Solver *solv, Id dep);
00300
00301 extern void solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap);
00302
00303
00304 extern SolverRuleinfo solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp);
00305
00306
00307 Id *solver_create_decisions_obsoletesmap(Solver *solv);
00308
00309 static inline int
00310 solver_dep_fulfilled(Solver *solv, Id dep)
00311 {
00312 Pool *pool = solv->pool;
00313 Id p, pp;
00314
00315 if (ISRELDEP(dep))
00316 {
00317 Reldep *rd = GETRELDEP(pool, dep);
00318 if (rd->flags == REL_AND)
00319 {
00320 if (!solver_dep_fulfilled(solv, rd->name))
00321 return 0;
00322 return solver_dep_fulfilled(solv, rd->evr);
00323 }
00324 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
00325 return solver_splitprovides(solv, rd->evr);
00326 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
00327 return solver_dep_installed(solv, rd->evr);
00328 }
00329 FOR_PROVIDES(p, pp, dep)
00330 {
00331 if (solv->decisionmap[p] > 0)
00332 return 1;
00333 }
00334 return 0;
00335 }
00336
00337 static inline int
00338 solver_is_supplementing(Solver *solv, Solvable *s)
00339 {
00340 Id sup, *supp;
00341 if (!s->supplements)
00342 return 0;
00343 supp = s->repo->idarraydata + s->supplements;
00344 while ((sup = *supp++) != 0)
00345 if (solver_dep_fulfilled(solv, sup))
00346 return 1;
00347 return 0;
00348 }
00349
00350 static inline int
00351 solver_is_enhancing(Solver *solv, Solvable *s)
00352 {
00353 Id enh, *enhp;
00354 if (!s->enhances)
00355 return 0;
00356 enhp = s->repo->idarraydata + s->enhances;
00357 while ((enh = *enhp++) != 0)
00358 if (solver_dep_fulfilled(solv, enh))
00359 return 1;
00360 return 0;
00361 }
00362
00363 void solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps);
00364 int solver_calc_installsizechange(Solver *solv);
00365 void solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res);
00366
00367 void solver_find_involved(Solver *solv, Queue *installedq, Solvable *s, Queue *q);
00368
00369 static inline void
00370 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
00371 {
00372 pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
00373 }
00374
00375
00376
00377
00378 #define FOR_RULELITERALS(l, dp, r) \
00379 for (l = r->d < 0 ? -r->d - 1 : r->d, \
00380 dp = !l ? &r->w2 : pool->whatprovidesdata + l, \
00381 l = r->p; l; l = (dp != &r->w2 + 1 ? *dp++ : 0))
00382
00383
00384 #define FOR_JOB_SELECT(p, pp, select, what) \
00385 if (select == SOLVER_SOLVABLE_REPO || select == SOLVER_SOLVABLE_ALL) \
00386 p = pp = 0; \
00387 else for (pp = (select == SOLVER_SOLVABLE ? 0 : \
00388 select == SOLVER_SOLVABLE_ONE_OF ? what : \
00389 pool_whatprovides(pool, what)), \
00390 p = (select == SOLVER_SOLVABLE ? what : pool->whatprovidesdata[pp++]) ; p ; p = pool->whatprovidesdata[pp++]) \
00391 if (select != SOLVER_SOLVABLE_NAME || pool_match_nevr(pool, pool->solvables + p, what))
00392
00393 #ifdef __cplusplus
00394 }
00395 #endif
00396
00397 #endif