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
00088 Map updatemap;
00089 Map fixmap;
00090
00091 Queue weakruleq;
00092 Map weakrulemap;
00093
00094 Id *watches;
00095
00096
00097
00098
00099
00100 Queue ruletojob;
00101
00102
00103 Queue decisionq;
00104 Queue decisionq_why;
00105
00106 Id *decisionmap;
00107
00108
00109
00110
00111
00112 Queue learnt_why;
00113 Queue learnt_pool;
00114
00115 Queue branches;
00116 int (*solution_callback)(struct _Solver *solv, void *data);
00117 void *solution_callback_data;
00118
00119 int propagate_index;
00120
00121 Queue problems;
00122 Queue solutions;
00123
00124 Queue recommendations;
00125 Queue suggestions;
00126 Queue orphaned;
00127
00128 int stats_learned;
00129 int stats_unsolvable;
00130
00131 Map recommendsmap;
00132 Map suggestsmap;
00133 int recommends_index;
00134
00135 Id *obsoletes;
00136 Id *obsoletes_data;
00137 Id *multiversionupdaters;
00138
00139
00140
00141
00142
00143 int fixsystem;
00144 int allowdowngrade;
00145 int allowarchchange;
00146 int allowvendorchange;
00147 int allowuninstall;
00148 int updatesystem;
00149 int noupdateprovide;
00150 int dosplitprovides;
00151 int dontinstallrecommended;
00152 int ignorealreadyrecommended;
00153 int dontshowinstalledrecommended;
00154
00155
00156 int distupgrade;
00157 int distupgrade_removeunsupported;
00158
00159 int noinfarchcheck;
00160
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170 BestSolvableCb bestSolvableCb;
00171
00172
00173
00174
00175
00176
00177
00178
00179 ArchCheckCb archCheckCb;
00180
00181
00182
00183
00184
00185
00186
00187
00188 VendorCheckCb vendorCheckCb;
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198 UpdateCandidateCb updateCandidateCb;
00199
00200
00201
00202 Queue covenantq;
00203
00204
00205 Map dupmap;
00206 Map dupinvolvedmap;
00207 Map droporphanedmap;
00208
00209 Queue *ruleinfoq;
00210 } Solver;
00211
00212
00213
00214
00215
00216 #define SOLVER_SOLVABLE 0x01
00217 #define SOLVER_SOLVABLE_NAME 0x02
00218 #define SOLVER_SOLVABLE_PROVIDES 0x03
00219 #define SOLVER_SOLVABLE_ONE_OF 0x04
00220 #define SOLVER_SOLVABLE_REPO 0x05
00221
00222 #define SOLVER_SELECTMASK 0xff
00223
00224 #define SOLVER_NOOP 0x0000
00225 #define SOLVER_INSTALL 0x0100
00226 #define SOLVER_ERASE 0x0200
00227 #define SOLVER_UPDATE 0x0300
00228 #define SOLVER_WEAKENDEPS 0x0400
00229 #define SOLVER_NOOBSOLETES 0x0500
00230 #define SOLVER_LOCK 0x0600
00231 #define SOLVER_DISTUPGRADE 0x0700
00232 #define SOLVER_VERIFY 0x0800
00233 #define SOLVER_DROP_ORPHANED 0x0900
00234
00235 #define SOLVER_JOBMASK 0xff00
00236
00237 #define SOLVER_WEAK 0x010000
00238 #define SOLVER_ESSENTIAL 0x020000
00239
00240
00241 #if 1
00242 #define SOLVER_INSTALL_SOLVABLE (SOLVER_INSTALL|SOLVER_SOLVABLE)
00243 #define SOLVER_ERASE_SOLVABLE (SOLVER_ERASE|SOLVER_SOLVABLE)
00244 #define SOLVER_INSTALL_SOLVABLE_NAME (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME)
00245 #define SOLVER_ERASE_SOLVABLE_NAME (SOLVER_ERASE|SOLVER_SOLVABLE_NAME)
00246 #define SOLVER_INSTALL_SOLVABLE_PROVIDES (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES)
00247 #define SOLVER_ERASE_SOLVABLE_PROVIDES (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES)
00248 #define SOLVER_INSTALL_SOLVABLE_UPDATE (SOLVER_UPDATE|SOLVER_SOLVABLE)
00249 #define SOLVER_INSTALL_SOLVABLE_ONE_OF (SOLVER_INSTALL|SOLVER_SOLVABLE_ONE_OF)
00250 #define SOLVER_WEAKEN_SOLVABLE_DEPS (SOLVER_WEAKENDEPS|SOLVER_SOLVABLE)
00251 #define SOLVER_NOOBSOLETES_SOLVABLE (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE)
00252 #define SOLVER_NOOBSOLETES_SOLVABLE_NAME (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE_NAME)
00253 #define SOLVER_NOOBSOLETES_SOLVABLE_PROVIDES (SOLVER_NOOBSOLETES|SOLVER_SOLVABLE_PROVIDES)
00254 #endif
00255
00256
00257 #define SOLVER_PROBLEM_UPDATE_RULE SOLVER_RULE_UPDATE
00258 #define SOLVER_PROBLEM_JOB_RULE SOLVER_RULE_JOB
00259 #define SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP
00260 #define SOLVER_PROBLEM_NOT_INSTALLABLE SOLVER_RULE_RPM_NOT_INSTALLABLE
00261 #define SOLVER_PROBLEM_NOTHING_PROVIDES_DEP SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP
00262 #define SOLVER_PROBLEM_SAME_NAME SOLVER_RULE_RPM_SAME_NAME
00263 #define SOLVER_PROBLEM_PACKAGE_CONFLICT SOLVER_RULE_RPM_PACKAGE_CONFLICT
00264 #define SOLVER_PROBLEM_PACKAGE_OBSOLETES SOLVER_RULE_RPM_PACKAGE_OBSOLETES
00265 #define SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE SOLVER_RULE_RPM_PACKAGE_REQUIRES
00266 #define SOLVER_PROBLEM_SELF_CONFLICT SOLVER_RULE_RPM_SELF_CONFLICT
00267 #define SOLVER_PROBLEM_RPM_RULE SOLVER_RULE_RPM
00268 #define SOLVER_PROBLEM_DISTUPGRADE_RULE SOLVER_RULE_DISTUPGRADE
00269 #define SOLVER_PROBLEM_INFARCH_RULE SOLVER_RULE_INFARCH
00270
00271
00272 extern Solver *solver_create(Pool *pool);
00273 extern void solver_free(Solver *solv);
00274 extern void solver_solve(Solver *solv, Queue *job);
00275
00276 extern void solver_run_sat(Solver *solv, int disablerules, int doweak);
00277 extern void solver_reset(Solver *solv);
00278
00279 extern int solver_dep_installed(Solver *solv, Id dep);
00280 extern int solver_splitprovides(Solver *solv, Id dep);
00281
00282 extern void solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap);
00283
00284
00285 extern SolverRuleinfo solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp);
00286
00287
00288 Id *solver_create_decisions_obsoletesmap(Solver *solv);
00289
00290 static inline int
00291 solver_dep_fulfilled(Solver *solv, Id dep)
00292 {
00293 Pool *pool = solv->pool;
00294 Id p, pp;
00295
00296 if (ISRELDEP(dep))
00297 {
00298 Reldep *rd = GETRELDEP(pool, dep);
00299 if (rd->flags == REL_AND)
00300 {
00301 if (!solver_dep_fulfilled(solv, rd->name))
00302 return 0;
00303 return solver_dep_fulfilled(solv, rd->evr);
00304 }
00305 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
00306 return solver_splitprovides(solv, rd->evr);
00307 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
00308 return solver_dep_installed(solv, rd->evr);
00309 }
00310 FOR_PROVIDES(p, pp, dep)
00311 {
00312 if (solv->decisionmap[p] > 0)
00313 return 1;
00314 }
00315 return 0;
00316 }
00317
00318 static inline int
00319 solver_is_supplementing(Solver *solv, Solvable *s)
00320 {
00321 Id sup, *supp;
00322 if (!s->supplements)
00323 return 0;
00324 supp = s->repo->idarraydata + s->supplements;
00325 while ((sup = *supp++) != 0)
00326 if (solver_dep_fulfilled(solv, sup))
00327 return 1;
00328 return 0;
00329 }
00330
00331 static inline int
00332 solver_is_enhancing(Solver *solv, Solvable *s)
00333 {
00334 Id enh, *enhp;
00335 if (!s->enhances)
00336 return 0;
00337 enhp = s->repo->idarraydata + s->enhances;
00338 while ((enh = *enhp++) != 0)
00339 if (solver_dep_fulfilled(solv, enh))
00340 return 1;
00341 return 0;
00342 }
00343
00344 void solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps);
00345 int solver_calc_installsizechange(Solver *solv);
00346 void solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res);
00347
00348 void solver_find_involved(Solver *solv, Queue *installedq, Solvable *s, Queue *q);
00349
00350 static inline void
00351 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
00352 {
00353 pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
00354 }
00355
00356
00357
00358
00359 #define FOR_RULELITERALS(l, dp, r) \
00360 for (l = r->d < 0 ? -r->d - 1 : r->d, \
00361 dp = !l ? &r->w2 : pool->whatprovidesdata + l, \
00362 l = r->p; l; l = (dp != &r->w2 + 1 ? *dp++ : 0))
00363
00364
00365 #define FOR_JOB_SELECT(p, pp, select, what) \
00366 if (select == SOLVER_SOLVABLE_REPO) \
00367 p = pp = 0; \
00368 else for (pp = (select == SOLVER_SOLVABLE ? 0 : \
00369 select == SOLVER_SOLVABLE_ONE_OF ? what : \
00370 pool_whatprovides(pool, what)), \
00371 p = (select == SOLVER_SOLVABLE ? what : pool->whatprovidesdata[pp++]) ; p ; p = pool->whatprovidesdata[pp++]) \
00372 if (select != SOLVER_SOLVABLE_NAME || pool_match_nevr(pool, pool->solvables + p, what))
00373
00374 #ifdef __cplusplus
00375 }
00376 #endif
00377
00378 #endif