Remove REQUIREDBY usage from libalpm

Instead of using the often-busted REQUIREDBY entries in the pacman database,
compute them each time they are required. This should help many things:

1. Simplify the codebase
2. Prevent future database corruption
3. Ensure when we do use requiredby, it is always correct
4. Shrink the pmpkg_t memory overhead

Signed-off-by: Dan McGee <dan@archlinux.org>

11 files changed, 18 insertions, 174 deletions

diff --git a/lib/libalpm/add.c b/lib/libalpm/add.c
index 277293f6..d242134a 100644
--- a/lib/libalpm/add.c
+++ b/lib/libalpm/add.c
@@ -804,10 +804,6 @@ static int commit_single_pkg(pmpkg_t *newpkg, int pkg_current, int pkg_count,
 		}
 	}
 
-	/* Update the requiredby field by scanning the whole database
-	 * looking for packages depending on the package to add */
-	_alpm_pkg_update_requiredby(newpkg);
-
 	/* make an install date (in UTC) */
 	newpkg->installdate = time(NULL);
 
@@ -827,9 +823,6 @@ static int commit_single_pkg(pmpkg_t *newpkg, int pkg_current, int pkg_count,
 				alpm_pkg_get_name(newpkg));
 	}
 
-	/* update dependency packages' REQUIREDBY fields */
-	_alpm_trans_update_depends(trans, newpkg);
-
 	if(is_upgrade) {
 		PROGRESS(trans, PM_TRANS_PROGRESS_UPGRADE_START,
 				alpm_pkg_get_name(newpkg), 100, pkg_count, pkg_current);
diff --git a/lib/libalpm/alpm.h b/lib/libalpm/alpm.h
index a279629f..ffcd3870 100644
--- a/lib/libalpm/alpm.h
+++ b/lib/libalpm/alpm.h
@@ -211,7 +211,6 @@ alpm_list_t *alpm_pkg_get_licenses(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_groups(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_depends(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_optdepends(pmpkg_t *pkg);
-alpm_list_t *alpm_pkg_get_requiredby(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_conflicts(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_provides(pmpkg_t *pkg);
 alpm_list_t *alpm_pkg_get_deltas(pmpkg_t *pkg);
diff --git a/lib/libalpm/be_files.c b/lib/libalpm/be_files.c
index 2f88a16d..a6cde689 100644
--- a/lib/libalpm/be_files.c
+++ b/lib/libalpm/be_files.c
@@ -461,10 +461,6 @@ int _alpm_db_read(pmdb_t *db, pmpkg_t *info, pmdbinfrq_t inforeq)
 				while(fgets(line, 512, fp) && strlen(_alpm_strtrim(line))) {
 					info->optdepends = alpm_list_add(info->optdepends, strdup(line));
 				}
-			} else if(!strcmp(line, "%REQUIREDBY%")) {
-				while(fgets(line, 512, fp) && strlen(_alpm_strtrim(line))) {
-					info->requiredby = alpm_list_add(info->requiredby, strdup(line));
-				}
 			} else if(!strcmp(line, "%CONFLICTS%")) {
 				while(fgets(line, 512, fp) && strlen(_alpm_strtrim(line))) {
 					info->conflicts = alpm_list_add(info->conflicts, strdup(line));
@@ -685,13 +681,6 @@ int _alpm_db_write(pmdb_t *db, pmpkg_t *info, pmdbinfrq_t inforeq)
 			}
 			fprintf(fp, "\n");
 		}
-		if(local && info->requiredby) {
-			fputs("%REQUIREDBY%\n", fp);
-			for(lp = info->requiredby; lp; lp = lp->next) {
-				fprintf(fp, "%s\n", (char *)lp->data);
-			}
-			fprintf(fp, "\n");
-		}
 		if(info->conflicts) {
 			fputs("%CONFLICTS%\n", fp);
 			for(lp = info->conflicts; lp; lp = lp->next) {
diff --git a/lib/libalpm/db.c b/lib/libalpm/db.c
index 599d24d0..150b365a 100644
--- a/lib/libalpm/db.c
+++ b/lib/libalpm/db.c
@@ -475,7 +475,6 @@ alpm_list_t SYMEXPORT *alpm_db_get_upgrades(void)
 								pm_errno = PM_ERR_MEMORY;
 								goto error;
 							}
-							dummy->requiredby = alpm_list_strdup(alpm_pkg_get_requiredby(lpkg));
 
 							pmsyncpkg_t *syncpkg;
 							syncpkg = _alpm_sync_find(syncpkgs, alpm_pkg_get_name(spkg));
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index 63775d20..42ceb743 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -254,12 +254,13 @@ alpm_list_t *_alpm_checkdeps(pmdb_t *db, pmtranstype_t op,
 	}
 
 	if(op == PM_TRANS_TYPE_UPGRADE) {
-		/* PM_TRANS_TYPE_UPGRADE handles the backwards dependencies, ie, the packages
-		 * listed in the requiredby field.
+		/* PM_TRANS_TYPE_UPGRADE handles the backwards dependencies, ie,
+		 * the packages listed in the requiredby field.
 		 */
 		for(i = packages; i; i = i->next) {
 			pmpkg_t *newpkg = i->data;
 			pmpkg_t *oldpkg;
+			alpm_list_t *requiredby;
 			if(newpkg == NULL) {
 				_alpm_log(PM_LOG_DEBUG, "null package found in package list\n");
 				continue;
@@ -272,7 +273,9 @@ alpm_list_t *_alpm_checkdeps(pmdb_t *db, pmtranstype_t op,
 									alpm_pkg_get_name(newpkg));
 				continue;
 			}
-			for(j = alpm_pkg_get_requiredby(oldpkg); j; j = j->next) {
+
+			requiredby = alpm_pkg_compute_requiredby(oldpkg);
+			for(j = requiredby; j; j = j->next) {
 				pmpkg_t *p;
 				found = 0;
 
@@ -340,6 +343,7 @@ alpm_list_t *_alpm_checkdeps(pmdb_t *db, pmtranstype_t op,
 					FREE(depend);
 				}
 			}
+			FREELIST(requiredby);
 		}
 	}
 	if(op == PM_TRANS_TYPE_ADD || op == PM_TRANS_TYPE_UPGRADE) {
@@ -394,12 +398,15 @@ alpm_list_t *_alpm_checkdeps(pmdb_t *db, pmtranstype_t op,
 		/* check requiredby fields */
 		for(i = packages; i; i = i->next) {
 			pmpkg_t *rmpkg = alpm_list_getdata(i);
+			alpm_list_t *requiredby;
 
 			if(rmpkg == NULL) {
 				_alpm_log(PM_LOG_DEBUG, "null package found in package list\n");
 				continue;
 			}
-			for(j = alpm_pkg_get_requiredby(rmpkg); j; j = j->next) {
+
+			requiredby = alpm_pkg_compute_requiredby(rmpkg);
+			for(j = requiredby; j; j = j->next) {
 				pmpkg_t *p;
 				found = 0;
 				if(_alpm_pkg_find(j->data, packages)) {
@@ -446,6 +453,7 @@ alpm_list_t *_alpm_checkdeps(pmdb_t *db, pmtranstype_t op,
 					FREE(depend);
 				}
 			}
+			FREELIST(requiredby);
 		}
 	}
 
@@ -559,7 +567,7 @@ pmdepend_t SYMEXPORT *alpm_splitdep(const char *depstring)
 static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets,
 		int include_explicit)
 {
-	alpm_list_t *i;
+	alpm_list_t *i, *requiredby;
 
 	if(_alpm_pkg_find(alpm_pkg_get_name(pkg), targets)) {
 		return(0);
@@ -581,12 +589,15 @@ static int can_remove_package(pmdb_t *db, pmpkg_t *pkg, alpm_list_t *targets,
 	 * if checkdeps detected it would break something */
 
 	/* see if other packages need it */
-	for(i = alpm_pkg_get_requiredby(pkg); i; i = i->next) {
+	requiredby = alpm_pkg_compute_requiredby(pkg);
+	for(i = requiredby; i; i = i->next) {
 		pmpkg_t *reqpkg = _alpm_db_get_pkgfromcache(db, i->data);
 		if(reqpkg && !_alpm_pkg_find(alpm_pkg_get_name(reqpkg), targets)) {
+			FREE(requiredby);
 			return(0);
 		}
 	}
+	FREELIST(requiredby);
 
 	/* it's ok to remove */
 	return(1);
diff --git a/lib/libalpm/package.c b/lib/libalpm/package.c
index 7c2870c2..89785a14 100644
--- a/lib/libalpm/package.c
+++ b/lib/libalpm/package.c
@@ -405,20 +405,6 @@ alpm_list_t SYMEXPORT *alpm_pkg_get_optdepends(pmpkg_t *pkg)
 	return pkg->optdepends;
 }
 
-alpm_list_t SYMEXPORT *alpm_pkg_get_requiredby(pmpkg_t *pkg)
-{
-	ALPM_LOG_FUNC;
-
-	/* Sanity checks */
-	ASSERT(handle != NULL, return(NULL));
-	ASSERT(pkg != NULL, return(NULL));
-
-	if(pkg->origin == PKG_FROM_CACHE && !(pkg->infolevel & INFRQ_DEPENDS)) {
-		_alpm_db_read(pkg->origin_data.db, pkg, INFRQ_DEPENDS);
-	}
-	return pkg->requiredby;
-}
-
 alpm_list_t SYMEXPORT *alpm_pkg_get_conflicts(pmpkg_t *pkg)
 {
 	ALPM_LOG_FUNC;
@@ -695,7 +681,6 @@ pmpkg_t *_alpm_pkg_dup(pmpkg_t *pkg)
 
 	memcpy(newpkg, pkg, sizeof(pmpkg_t));
 	newpkg->licenses    = alpm_list_strdup(alpm_pkg_get_licenses(pkg));
-	newpkg->requiredby = alpm_list_strdup(alpm_pkg_get_requiredby(pkg));
 	newpkg->conflicts  = alpm_list_strdup(alpm_pkg_get_conflicts(pkg));
 	newpkg->files      = alpm_list_strdup(alpm_pkg_get_files(pkg));
 	newpkg->backup     = alpm_list_strdup(alpm_pkg_get_backup(pkg));
@@ -729,7 +714,6 @@ void _alpm_pkg_free(pmpkg_t *pkg)
 	FREELIST(pkg->depends);
 	FREELIST(pkg->optdepends);
 	FREELIST(pkg->conflicts);
-	FREELIST(pkg->requiredby);
 	FREELIST(pkg->groups);
 	FREELIST(pkg->provides);
 	FREELIST(pkg->replaces);
@@ -1098,13 +1082,6 @@ pmpkg_t *_alpm_pkg_find(const char *needle, alpm_list_t *haystack)
 	return(NULL);
 }
 
-/* fill in requiredby field of package,
- * used when we want to install or add a package */
-void _alpm_pkg_update_requiredby(pmpkg_t *pkg)
-{
-	pkg->requiredby = alpm_pkg_compute_requiredby(pkg);
-}
-
 /* TODO this should either be public, or done somewhere else */
 int _alpm_pkg_istoonew(pmpkg_t *pkg)
 {
diff --git a/lib/libalpm/package.h b/lib/libalpm/package.h
index ab93fd86..b125e06c 100644
--- a/lib/libalpm/package.h
+++ b/lib/libalpm/package.h
@@ -72,7 +72,6 @@ struct __pmpkg_t {
 	alpm_list_t *backup;
 	alpm_list_t *depends;
 	alpm_list_t *optdepends;
-	alpm_list_t *requiredby;
 	alpm_list_t *conflicts;
 	alpm_list_t *provides;
 	alpm_list_t *deltas;
@@ -98,7 +97,6 @@ int alpm_pkg_compare_versions(pmpkg_t *local_pkg, pmpkg_t *pkg);
 pmpkg_t *_alpm_pkg_load(const char *pkgfile, unsigned short full);
 pmpkg_t *_alpm_pkg_find(const char *needle, alpm_list_t *haystack);
 int _alpm_pkg_istoonew(pmpkg_t *pkg);
-void _alpm_pkg_update_requiredby(pmpkg_t *pkg);
 int _alpm_pkg_should_ignore(pmpkg_t *pkg);
 
 #endif /* _ALPM_PACKAGE_H */
diff --git a/lib/libalpm/remove.c b/lib/libalpm/remove.c
index 86cfee68..66a1527c 100644
--- a/lib/libalpm/remove.c
+++ b/lib/libalpm/remove.c
@@ -249,7 +249,7 @@ static void unlink_file(pmpkg_t *info, alpm_list_t *lp, pmtrans_t *trans)
 
 int _alpm_remove_commit(pmtrans_t *trans, pmdb_t *db)
 {
-	pmpkg_t *info, *infodup;
+	pmpkg_t *info;
 	alpm_list_t *targ, *lp;
 	int pkg_count;
 
@@ -331,9 +331,6 @@ int _alpm_remove_commit(pmtrans_t *trans, pmdb_t *db)
 			}
 		}
 
-		/* duplicate the package so we can remove the requiredby fields later */
-		infodup = _alpm_pkg_dup(info);
-
 		/* remove the package from the database */
 		_alpm_log(PM_LOG_DEBUG, "updating database\n");
 		_alpm_log(PM_LOG_DEBUG, "removing database entry '%s'\n", pkgname);
@@ -347,10 +344,6 @@ int _alpm_remove_commit(pmtrans_t *trans, pmdb_t *db)
 			          pkgname);
 		}
 		
-		/* update dependency packages' REQUIREDBY fields */
-		_alpm_trans_update_depends(trans, infodup);
-		_alpm_pkg_free(infodup);
-
 		/* call a done event if this isn't an upgrade */
 		if(trans->type != PM_TRANS_TYPE_REMOVEUPGRADE) {
 			EVENT(trans, PM_TRANS_EVT_REMOVE_DONE, info, NULL);
diff --git a/lib/libalpm/sync.c b/lib/libalpm/sync.c
index 336b5848..e5748e6d 100644
--- a/lib/libalpm/sync.c
+++ b/lib/libalpm/sync.c
@@ -137,7 +137,6 @@ static int find_replacements(pmtrans_t *trans, pmdb_t *db_local,
 							pm_errno = PM_ERR_MEMORY;
 							goto error;
 						}
-						dummy->requiredby = alpm_list_strdup(alpm_pkg_get_requiredby(lpkg));
 						/* check if spkg->name is already in the packages list. */
 						sync = _alpm_sync_find(trans->packages, alpm_pkg_get_name(spkg));
 						if(sync) {
@@ -563,7 +562,6 @@ int _alpm_sync_prepare(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t *dbs_sync
 						asked = alpm_list_add(asked, strdup(miss->depend.name));
 						if(doremove) {
 							pmpkg_t *q = _alpm_pkg_dup(local);
-							q->requiredby = alpm_list_strdup(alpm_pkg_get_requiredby(local));
 							if(sync->type != PM_SYNC_TYPE_REPLACE) {
 								/* switch this sync type to REPLACE */
 								sync->type = PM_SYNC_TYPE_REPLACE;
@@ -1241,53 +1239,6 @@ int _alpm_sync_commit(pmtrans_t *trans, pmdb_t *db_local, alpm_list_t **data)
 	_alpm_trans_free(tr);
 	tr = NULL;
 
-	/* propagate replaced packages' requiredby fields to their new owners */
-	if(replaces) {
-		_alpm_log(PM_LOG_DEBUG, "updating database for replaced packages' dependencies\n");
-		for(i = trans->packages; i; i = i->next) {
-			pmsyncpkg_t *sync = i->data;
-			if(sync->type == PM_SYNC_TYPE_REPLACE) {
-				alpm_list_t *j;
-				pmpkg_t *new = _alpm_db_get_pkgfromcache(db_local, alpm_pkg_get_name(sync->pkg));
-				for(j = sync->data; j; j = j->next) {
-					alpm_list_t *k;
-					pmpkg_t *old = j->data;
-					/* merge lists */
-					for(k = alpm_pkg_get_requiredby(old); k; k = k->next) {
-						if(!alpm_list_find_str(alpm_pkg_get_requiredby(new), k->data)) {
-							/* replace old's name with new's name in the requiredby's dependency list */
-							alpm_list_t *m;
-							pmpkg_t *depender = _alpm_db_get_pkgfromcache(db_local, k->data);
-							if(depender == NULL) {
-								/* If the depending package no longer exists in the local db,
-								 * then it must have ALSO conflicted with sync->pkg.  If
-								 * that's the case, then we don't have anything to propagate
-								 * here. */
-								continue;
-							}
-							for(m = alpm_pkg_get_depends(depender); m; m = m->next) {
-								if(!strcmp(m->data, alpm_pkg_get_name(old))) {
-									FREE(m->data);
-									m->data = strdup(alpm_pkg_get_name(new));
-								}
-							}
-							if(_alpm_db_write(db_local, depender, INFRQ_DEPENDS) == -1) {
-								_alpm_log(PM_LOG_ERROR, _("could not update requiredby for database entry %s-%s\n"),
-													alpm_pkg_get_name(new), alpm_pkg_get_version(new));
-							}
-							/* add the new requiredby */
-							new->requiredby = alpm_list_add(alpm_pkg_get_requiredby(new), strdup(k->data));
-						}
-					}
-				}
-				if(_alpm_db_write(db_local, new, INFRQ_DEPENDS) == -1) {
-					_alpm_log(PM_LOG_ERROR, _("could not update new database entry %s-%s\n"),
-										alpm_pkg_get_name(new), alpm_pkg_get_version(new));
-				}
-			}
-		}
-	}
-
 	return(0);
 
 error:
diff --git a/lib/libalpm/trans.c b/lib/libalpm/trans.c
index a5fba845..bcd0707d 100644
--- a/lib/libalpm/trans.c
+++ b/lib/libalpm/trans.c
@@ -438,71 +438,6 @@ int _alpm_trans_commit(pmtrans_t *trans, alpm_list_t **data)
 	return(0);
 }
 
-/* A depends on B through n depends <=> A listed in B's requiredby n times
- * n == 0 or 1 in almost all cases */
-int _alpm_trans_update_depends(pmtrans_t *trans, pmpkg_t *pkg)
-{
-	alpm_list_t *i, *j;
-	alpm_list_t *depends = NULL;
-	const char *pkgname;
-	pmdb_t *localdb;
-
-	ALPM_LOG_FUNC;
-
-	/* Sanity checks */
-	ASSERT(trans != NULL, RET_ERR(PM_ERR_TRANS_NULL, -1));
-	ASSERT(pkg != NULL, RET_ERR(PM_ERR_PKG_INVALID, -1));
-
-	pkgname = alpm_pkg_get_name(pkg);
-	depends = alpm_pkg_get_depends(pkg);
-
-	if(depends) {
-		_alpm_log(PM_LOG_DEBUG, "updating dependency packages 'requiredby' fields for %s-%s\n",
-		          pkgname, pkg->version);
-	} else {
-		_alpm_log(PM_LOG_DEBUG, "package has no dependencies, no other packages to update\n");
-	}
-
-	localdb = alpm_option_get_localdb();
-	for(i = depends; i; i = i->next) {
-		if(!i->data) {
-			continue;
-		}
-		pmdepend_t* dep = alpm_splitdep(i->data);
-		if(dep == NULL) {
-			continue;
-		}
-		for(j = _alpm_db_get_pkgcache(localdb); j; j = j->next) {
-			pmpkg_t *deppkg = j->data;
-			if(deppkg && alpm_depcmp(deppkg, dep)) {
-				/* this is cheating... we call this function to populate the package */
-				alpm_list_t *rqdby = alpm_pkg_get_requiredby(deppkg);
-
-				_alpm_log(PM_LOG_DEBUG, "updating 'requiredby' field for package '%s'\n",
-				          alpm_pkg_get_name(deppkg));
-
-				if(trans->type == PM_TRANS_TYPE_REMOVE
-						|| trans->type == PM_TRANS_TYPE_REMOVEUPGRADE) {
-					void *data = NULL;
-					rqdby = alpm_list_remove(rqdby,	pkgname, _alpm_str_cmp, &data);
-					FREE(data);
-					deppkg->requiredby = rqdby;
-				} else {
-					rqdby = alpm_list_add(rqdby, strdup(pkgname));
-					deppkg->requiredby = rqdby;
-				}
-
-				if(_alpm_db_write(localdb, deppkg, INFRQ_DEPENDS)) {
-					_alpm_log(PM_LOG_ERROR, _("could not update 'requiredby' database entry %s-%s\n"),
-										alpm_pkg_get_name(deppkg), alpm_pkg_get_version(deppkg));
-				}
-			}
-		}
-		FREE(dep);
-	}
-	return(0);
-}
-
 /* A cheap grep for text files, returns 1 if a substring
  * was found in the text file fn, 0 if it wasn't
  */
diff --git a/lib/libalpm/trans.h b/lib/libalpm/trans.h
index f3575895..79b8c20f 100644
--- a/lib/libalpm/trans.h
+++ b/lib/libalpm/trans.h
@@ -78,7 +78,6 @@ int _alpm_trans_sysupgrade(pmtrans_t *trans);
 int _alpm_trans_addtarget(pmtrans_t *trans, char *target);
 int _alpm_trans_prepare(pmtrans_t *trans, alpm_list_t **data);
 int _alpm_trans_commit(pmtrans_t *trans, alpm_list_t **data);
-int _alpm_trans_update_depends(pmtrans_t *trans, pmpkg_t *pkg);
 int _alpm_runscriptlet(const char *root, const char *installfn,
                        const char *script, const char *ver,
                        const char *oldver, pmtrans_t *trans);