From b8c3a5453120af6509ddd7d66dffc0b8ef417629 Mon Sep 17 00:00:00 2001 From: Glenn L McGrath Date: Fri, 28 Nov 2003 22:38:14 +0000 Subject: Patch from Ian Campbell, fix or'ed dependencies and handle virtual dependencies. --- archival/dpkg.c | 316 ++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 237 insertions(+), 79 deletions(-) (limited to 'archival') diff --git a/archival/dpkg.c b/archival/dpkg.c index 93f9f0673..2ebbbdf4e 100644 --- a/archival/dpkg.c +++ b/archival/dpkg.c @@ -389,8 +389,54 @@ int search_package_hashtable(const unsigned int name, const unsigned int version return(probe_address); } +/* + * This function searches through the entire package_hashtable looking + * for a package which provides "needle". It returns the index into + * the package_hashtable for the provining package. + * + * needle is the index into name_hashtable of the package we are + * looking for. + * + * start_at is the index in the package_hashtable to start looking + * at. If start_at is -1 then start at the beginning. This is to allow + * for repeated searches since more than one package might provide + * needle. + * + * FIXME: I don't think this is very efficient, but I thought I'd keep + * it simple for now until it proves to be a problem. + */ +int search_for_provides(int needle, int start_at) { + int i, j; + common_node_t *p; + for (i = start_at + 1; i < PACKAGE_HASH_PRIME; i++) { + p = package_hashtable[i]; + if ( p == NULL ) continue; + for(j = 0; j < p->num_of_edges; j++) + if ( p->edge[j]->type == EDGE_PROVIDES && p->edge[j]->name == needle ) + return i; + } + return -1; +} + +/* + * Add an edge to a node + */ +void add_edge_to_node(common_node_t *node, edge_t *edge) +{ + node->num_of_edges++; + node->edge = xrealloc(node->edge, sizeof(edge_t) * (node->num_of_edges + 1)); + node->edge[node->num_of_edges - 1] = edge; +} + /* * Create one new node and one new edge for every dependency. + * + * Dependencies which contain multiple alternatives are represented as + * an EDGE_OR_PRE_DEPENDS or EDGE_OR_DEPENDS node, followed by a + * number of EDGE_PRE_DEPENDS or EDGE_DEPENDS nodes. The name field of + * the OR edge contains the full dependency string while the version + * field contains the number of EDGE nodes which follow as part of + * this alternative. */ void add_split_dependencies(common_node_t *parent_node, const char *whole_line, unsigned int edge_type) { @@ -402,25 +448,33 @@ void add_split_dependencies(common_node_t *parent_node, const char *whole_line, char *field2; char *version; edge_t *edge; + edge_t *or_edge; int offset_ch; - int type; field = strtok_r(line, ",", &line_ptr1); do { + /* skip leading spaces */ + field += strspn(field, " "); line2 = bb_xstrdup(field); field2 = strtok_r(line2, "|", &line_ptr2); - if ((edge_type == EDGE_DEPENDS) && (strcmp(field, field2) != 0)) { - type = EDGE_OR_DEPENDS; - } - else if ((edge_type == EDGE_PRE_DEPENDS) && (strcmp(field, field2) != 0)) { - type = EDGE_OR_PRE_DEPENDS; + if ( (edge_type == EDGE_DEPENDS || edge_type == EDGE_PRE_DEPENDS) && + (strcmp(field, field2) != 0)) { + or_edge = (edge_t *)xmalloc(sizeof(edge_t)); + or_edge->type = edge_type + 1; } else { - type = edge_type; + or_edge = NULL; + } + + if ( or_edge ) { + or_edge->name = search_name_hashtable(field); + or_edge->version = 0; // tracks the number of altenatives + + add_edge_to_node(parent_node, or_edge); } do { edge = (edge_t *) xmalloc(sizeof(edge_t)); - edge->type = type; + edge->type = edge_type; /* Skip any extra leading spaces */ field2 += strspn(field2, " "); @@ -470,11 +524,11 @@ void add_split_dependencies(common_node_t *parent_node, const char *whole_line, /* Get the dependency name */ field2[strcspn(field2, " (")] = '\0'; edge->name = search_name_hashtable(field2); - - /* link the new edge to the current node */ - parent_node->num_of_edges++; - parent_node->edge = xrealloc(parent_node->edge, sizeof(edge_t) * (parent_node->num_of_edges + 1)); - parent_node->edge[parent_node->num_of_edges - 1] = edge; + + if ( or_edge ) + or_edge->version++; + + add_edge_to_node(parent_node, edge); } while ((field2 = strtok_r(NULL, "|", &line_ptr2)) != NULL); free(line2); } while ((field = strtok_r(NULL, ",", &line_ptr1)) != NULL); @@ -490,7 +544,8 @@ void free_package(common_node_t *node) for (i = 0; i < node->num_of_edges; i++) { free(node->edge[i]); } - free(node->edge); + if ( node->edge ) + free(node->edge); free(node); } } @@ -627,6 +682,31 @@ void set_status(const unsigned int status_node_num, const char *new_value, const return; } +const char *describe_status(int status_num) { + int status_want, status_state ; + if ( status_hashtable[status_num] == NULL || status_hashtable[status_num]->status == 0 ) + return "is not installed or flagged to be installed\n"; + + status_want = get_status(status_num, 1); + status_state = get_status(status_num, 3); + + if ( status_state == search_name_hashtable("installed") ) { + if ( status_want == search_name_hashtable("install") ) + return "is installed"; + if ( status_want == search_name_hashtable("deinstall") ) + return "is marked to be removed"; + if ( status_want == search_name_hashtable("purge") ) + return "is marked to be purged"; + } + if ( status_want == search_name_hashtable("unknown") ) + return "is in an indeterminate state"; + if ( status_want == search_name_hashtable("install") ) + return "is marked to be installed"; + + return "is not installed or flagged to be installed"; +} + + void index_status_file(const char *filename) { FILE *status_file; @@ -659,7 +739,7 @@ void index_status_file(const char *filename) return; } - +#if 0 /* this code is no longer used */ char *get_depends_field(common_node_t *package, const int depends_type) { char *depends = NULL; @@ -730,6 +810,7 @@ char *get_depends_field(common_node_t *package, const int depends_type) } return(depends); } +#endif void write_buffer_no_status(FILE *new_status_file, const char *control_buffer) { @@ -890,13 +971,34 @@ void write_status_file(deb_file_t **deb_file) } } +/* This function returns TRUE if the given package can statisfy a + * dependency of type depend_type. + * + * A pre-depends is statisfied only if a package is already installed, + * which a regular depends can be satisfied by a package which we want + * to install. + */ +int package_satisfies_dependency(int package, int depend_type) +{ + int status_num = search_status_hashtable(name_hashtable[package_hashtable[package]->name]); + + /* status could be unknown if package is a pure virtual + * provides which cannot satisfy any dependency by itself. + */ + if ( status_hashtable[status_num] == NULL ) + return 0; + + switch (depend_type) { + case EDGE_PRE_DEPENDS: return get_status(status_num, 3) == search_name_hashtable("installed"); + case EDGE_DEPENDS: return get_status(status_num, 1) == search_name_hashtable("install"); + } + return 0; +} + int check_deps(deb_file_t **deb_file, int deb_start, int dep_max_count) { int *conflicts = NULL; int conflicts_num = 0; - int state_status; - int state_flag; - int state_want; int i = deb_start; int j; @@ -952,21 +1054,17 @@ int check_deps(deb_file_t **deb_file, int deb_start, int dep_max_count) for (j = 0; j < package_node->num_of_edges; j++) { const edge_t *package_edge = package_node->edge[j]; - const unsigned int package_num = - search_package_hashtable(package_edge->name, - package_edge->version, package_edge->operator); if (package_edge->type == EDGE_CONFLICTS) { + const unsigned int package_num = + search_package_hashtable(package_edge->name, + package_edge->version, + package_edge->operator); int result = 0; if (package_hashtable[package_num] != NULL) { status_num = search_status_hashtable(name_hashtable[package_hashtable[package_num]->name]); - state_status = get_status(status_num, 3); - state_flag = get_status(status_num, 1); - - result = (state_status == search_name_hashtable("installed")) || - (state_flag == search_name_hashtable("want-install")); - if (result) { + if (get_status(status_num, 1) == search_name_hashtable("install")) { result = test_version(package_hashtable[deb_file[i]->package]->version, package_edge->version, package_edge->operator); } @@ -984,66 +1082,123 @@ int check_deps(deb_file_t **deb_file, int deb_start, int dep_max_count) /* Check dependendcies */ - i = 0; - while (deb_file[i] != NULL) { - const common_node_t *package_node = package_hashtable[deb_file[i]->package]; + for (i = 0; i < PACKAGE_HASH_PRIME; i++) { int status_num = 0; + int number_of_alternatives = 0; + const edge_t * root_of_alternatives; + const common_node_t *package_node = package_hashtable[i]; - status_num = search_status_hashtable(name_hashtable[package_node->name]); - state_status = get_status(status_num, 3); - state_want = get_status(status_num, 1); + /* If the package node does not exist then this + * package is a virtual one. In which case there are + * no dependencies to check. + */ + if ( package_node == NULL ) continue; - if (state_status == search_name_hashtable("installed")) { - i++; + status_num = search_status_hashtable(name_hashtable[package_node->name]); + + /* If there is no status then this package is a + * virtual one provided by something else. In which + * case there are no dependencies to check. + */ + if ( status_hashtable[status_num] == NULL ) continue; + + /* If we don't want this package installed then we may + * as well ignore it's dependencies. + */ + if (get_status(status_num, 1) != search_name_hashtable("install")) { continue; } - for (j = 0; j < package_hashtable[deb_file[i]->package]->num_of_edges; j++) { +#if 0 + /* This might be needed so we don't complain about + * things which are broken but unrelated to the + * packages that are currently being installed + */ + if (state_status == search_name_hashtable("installed")) + continue; +#endif + + /* This code is tested only for EDGE_DEPENDS, sine I + * have no suitable pre-depends available. There is no + * reason that it shouldn't work though :-) + */ + for (j = 0; j < package_node->num_of_edges; j++) { const edge_t *package_edge = package_node->edge[j]; unsigned int package_num; + + if ( package_edge->type == EDGE_OR_PRE_DEPENDS || + package_edge->type == EDGE_OR_DEPENDS ) { /* start an EDGE_OR_ list */ + number_of_alternatives = package_edge->version; + root_of_alternatives = package_edge; + continue; + } else if ( number_of_alternatives == 0 ) { /* not in the middle of an EDGE_OR_ list */ + number_of_alternatives = 1; + root_of_alternatives = NULL; + } package_num = search_package_hashtable(package_edge->name, package_edge->version, package_edge->operator); - switch (package_edge->type) { - case(EDGE_PRE_DEPENDS): - case(EDGE_OR_PRE_DEPENDS): { - int result=1; - /* It must be already installed */ - /* NOTE: This is untested, nothing apropriate in my status file */ - if (package_hashtable[package_num] != NULL) { - status_num = search_status_hashtable(name_hashtable[package_hashtable[package_num]->name]); - state_status = get_status(status_num, 3); - state_want = get_status(status_num, 1); - result = (state_status != search_name_hashtable("installed")); + if (package_edge->type == EDGE_PRE_DEPENDS || + package_edge->type == EDGE_DEPENDS ) { + int result=1; + status_num = 0; + + /* If we are inside an alternative then check + * this edge is the right type. + * + * EDGE_DEPENDS == OR_DEPENDS -1 + * EDGE_PRE_DEPENDS == OR_PRE_DEPENDS -1 + */ + if ( root_of_alternatives && package_edge->type != root_of_alternatives->type - 1) + bb_error_msg_and_die("Fatal error. Package dependencies corrupt: %d != %d - 1 \n", + package_edge->type, root_of_alternatives->type); + + if (package_hashtable[package_num] != NULL) + result = !package_satisfies_dependency(package_num, package_edge->type); + + if (result) { /* check for other package which provide what we are looking for */ + int provider = -1; + + while ( (provider = search_for_provides(package_edge->name, provider) ) > -1 ) { + if ( package_hashtable[provider] == NULL ) { + printf("Have a provider but no package information for it\n"); + continue; + } + result = !package_satisfies_dependency(provider, package_edge->type); + + if ( result == 0 ) + break; } + } - if (result) { - bb_error_msg_and_die("Package %s pre-depends on %s, but it is not installed", + /* It must be already installed, or to be installed */ + number_of_alternatives--; + if (result && number_of_alternatives == 0) { + if ( root_of_alternatives ) + bb_error_msg_and_die( + "Package %s %sdepends on %s, " + "which cannot be satisfied", name_hashtable[package_node->name], - name_hashtable[package_edge->name]); - } - break; - } - case(EDGE_DEPENDS): - case(EDGE_OR_DEPENDS): { - int result=1; - if (package_hashtable[package_num] != NULL) { - status_num = search_status_hashtable(name_hashtable[package_hashtable[package_num]->name]); - state_status = get_status(status_num, 3); - state_want = get_status(status_num, 1); - result=(state_status != search_name_hashtable("installed")) && (state_want != search_name_hashtable("want-install")); - } - /* It must be already installed, or to be installed */ - if (result) { - bb_error_msg_and_die("Package %s depends on %s, but it is not installed, or flaged to be installed", + package_edge->type == EDGE_PRE_DEPENDS ? "pre-" : "", + name_hashtable[root_of_alternatives->name]); + else + bb_error_msg_and_die( + "Package %s %sdepends on %s, which %s\n", name_hashtable[package_node->name], - name_hashtable[package_edge->name]); - } - break; + package_edge->type == EDGE_PRE_DEPENDS ? "pre-" : "", + name_hashtable[package_edge->name], + describe_status(status_num)); + } else if ( result == 0 && number_of_alternatives ) { + /* we've found a package which + * satisfies the dependency, + * so skip over the rest of + * the alternatives. + */ + j += number_of_alternatives; + number_of_alternatives = 0; } } } - i++; } free(conflicts); return(TRUE); @@ -1260,7 +1415,6 @@ void remove_package(const unsigned int package_num, int noisy) rename(conffile_name, list_name); /* Change package status */ - set_status(status_num, "deinstall", 1); set_status(status_num, "config-files", 3); } @@ -1303,7 +1457,6 @@ void purge_package(const unsigned int package_num) } /* Change package status */ - set_status(status_num, "purge", 1); set_status(status_num, "not-installed", 3); } @@ -1501,6 +1654,7 @@ int dpkg_main(int argc, char **argv) if (strcmp(optarg, "depends") == 0) { dpkg_opt |= dpkg_opt_force_ignore_depends; } + break; case 'i': dpkg_opt |= dpkg_opt_install; dpkg_opt |= dpkg_opt_filename; @@ -1566,19 +1720,20 @@ int dpkg_main(int argc, char **argv) /* Add the package to the status hashtable */ if ((dpkg_opt & dpkg_opt_unpack) || (dpkg_opt & dpkg_opt_install)) { - status_node = (status_node_t *) xmalloc(sizeof(status_node_t)); - status_node->package = deb_file[deb_count]->package; /* Try and find a currently installed version of this package */ status_num = search_status_hashtable(name_hashtable[package_hashtable[deb_file[deb_count]->package]->name]); /* If no previous entry was found initialise a new entry */ if ((status_hashtable[status_num] == NULL) || (status_hashtable[status_num]->status == 0)) { + status_node = (status_node_t *) xmalloc(sizeof(status_node_t)); + status_node->package = deb_file[deb_count]->package; /* reinstreq isnt changed to "ok" until the package control info * is written to the status file*/ - status_node->status = search_name_hashtable("want-install reinstreq not-installed"); + status_node->status = search_name_hashtable("install reinstreq not-installed"); status_hashtable[status_num] = status_node; } else { - status_hashtable[status_num]->status = search_name_hashtable("want-install reinstreq installed"); + set_status(status_num, "install", 1); + set_status(status_num, "reinstreq", 2); } } } @@ -1591,20 +1746,24 @@ int dpkg_main(int argc, char **argv) if (package_hashtable[deb_file[deb_count]->package] == NULL) { bb_error_msg_and_die("Package %s is uninstalled or unknown\n", argv[optind]); } - state_status = get_status(search_status_hashtable(name_hashtable[package_hashtable[deb_file[deb_count]->package]->name]), 3); + package_num = deb_file[deb_count]->package; + status_num = search_status_hashtable(name_hashtable[package_hashtable[package_num]->name]); + state_status = get_status(status_num, 3); /* check package status is "installed" */ if (dpkg_opt & dpkg_opt_remove) { if ((strcmp(name_hashtable[state_status], "not-installed") == 0) || (strcmp(name_hashtable[state_status], "config-files") == 0)) { - bb_error_msg_and_die("%s is already removed.", name_hashtable[package_hashtable[deb_file[deb_count]->package]->name]); + bb_error_msg_and_die("%s is already removed.", name_hashtable[package_hashtable[package_num]->name]); } + set_status(status_num, "deinstall", 1); } else if (dpkg_opt & dpkg_opt_purge) { /* if package status is "conf-files" then its ok */ if (strcmp(name_hashtable[state_status], "not-installed") == 0) { - bb_error_msg_and_die("%s is already purged.", name_hashtable[package_hashtable[deb_file[deb_count]->package]->name]); + bb_error_msg_and_die("%s is already purged.", name_hashtable[package_hashtable[package_num]->name]); } + set_status(status_num, "purge", 1); } } deb_count++; @@ -1613,7 +1772,6 @@ int dpkg_main(int argc, char **argv) deb_file[deb_count] = NULL; /* Check that the deb file arguments are installable */ - /* TODO: check dependencies before removing */ if ((dpkg_opt & dpkg_opt_force_ignore_depends) != dpkg_opt_force_ignore_depends) { if (!check_deps(deb_file, 0, deb_count)) { bb_error_msg_and_die("Dependency check failed"); -- cgit v1.2.3