Patch from Ian Campbell, fix or'ed dependencies and handle virtual

dependencies.

1 files changed, 237 insertions, 79 deletions

diff --git a/archival/dpkg.c b/archival/dpkg.c
index 93f9f0673..2ebbbdf4e 100644
--- a/archival/dpkg.c
+++ b/archival/dpkg.c
@@ -390,7 +390,53 @@ int search_package_hashtable(const unsigned int name, const unsigned int version
 }
 
 /*
+ * 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");