Attaching the mentioned patch and changelog.
There is also an older version of this patch available, attaching the
interdiff.
Note to self: whitespaces...
Changes:
- Handle OR dependencies:
- parser code stores single dependencies in pkg_info->deps,
OR dependencies in pkg_info->cond_deps
- handle version constraints in dependencies:
- reuse code from dpkg for parsing and comparing
- just store version strings and defer parsing of versions
until needed
- remove parts of OR deps referring to packages older/newer than
what we have.
- remove parts of OR dependencies referring to nonexistent packages
- Deal with provides as OR dependencies:
build hash table mapping provided_name to
list of packages providing it.
Then lookup each package dependency in the hash table,
and replace with :
- provider if only one provider
- an OR dependency with all the providers otherwise
- don't substitute provides on a dependency with a version.
apparently this is what apt-get does. we end up disagreeing
on some packages otherwise.
- Fixed --show-deps, some user packages would show up twice
if they depended on the package through both depends
and provides
- added --removable option:
"Find packages that can *individually* be removed
without triggering other removals. (implies nice-mode OFF).
They may be used, but other packages in the system
provide the same functionality, so they can be removed as
long as these other packages are there.
As these other packages may also be in the list, it may not
be possible to remove returned packages as a group
(deborphan --removable should be re-run after each removal).
On the other hand, it allows to find orphans which would not
be listed without --removable."
In this case we just ignore OR dependencies:
after simplifying OR expressions, all remainging OR expressions
mention at least 2 installed packages. So if a given package is
mentioned in them, we know there's another package in the
system to satisfy the dependency.
- improved speed of dependency checking loop (so much that even
with all the extra version logic etc, it's still way faster!)
loop was o(n^2) on the number of packages, made it o(n) by
storing users in pkg_info.
- some changes are on a compile time switch:
HANDLE_PKG_VERSIONS for the version logic,
COLLECT_USERS for the new dep check loop (if !LOW_MEM)
- i checked --removable output against apt-get (real_removable
script in src/test, (takes forever)), on my system they agree.
Also compared with orig deborphan for a few options (default,
-n, -d, -a). output was same or better. i haven't checked the
others though.
- i'm using glib for the hash tables. I was thinking of linking
statically against glib, this way we only create a build dependency,
not a package one. However this pulls in most of glib and makes
deborphan pretty big so it's really not ideal.
looking for a better way ...
----------
other ideas/misc stuff
- simplify OR dependencies when one other member of the group is in use
(would improve results when not using --removable)
- --show-deps really should be --show-users ?
diff -Nruw deborphan-1.7.23.orig/debian/changelog deborphan-1.7.23.new/debian/changelog
--- deborphan-1.7.23.orig/debian/changelog 2006-11-22 01:20:58.000000000 +0100
+++ deborphan-1.7.23.new/debian/changelog 2007-08-24 15:29:36.000000000 +0200
@@ -1,3 +1,26 @@
+deborphan (1.7.23a) unstable; urgency=low
+
+ * Handle OR dependencies:
+ * Handle version constraints in OR dependencies
+ * Handle provides as OR dependencies:
+ * Fixed --show-deps, some user packages would show up twice
+ if they depended on the package through both depends
+ and provides
+ * added --removable option:
+ "Find packages that can *individually* be removed
+ without triggering other removals. (implies nice-mode OFF).
+ They may be used, but other packages in the system
+ provide the same functionality, so they can be removed as
+ long as these other packages are there.
+ As these other packages may also be in the list, it may not
+ be possible to remove returned packages as a group
+ (deborphan --removable should be re-run after each removal).
+ On the other hand, it allows to find orphans which would not
+ be listed without --removable."
+ * much faster
+
+ -- Matthieu Lucotte <[EMAIL PROTECTED]> Fri, 24 Aug 2007 15:27:44 +0100
+
deborphan (1.7.23) unstable; urgency=low
* Whitespace cleanup in orphaner (closes: #398330).
diff -Nruw deborphan-1.7.23.orig/debian/control deborphan-1.7.23.new/debian/control
--- deborphan-1.7.23.orig/debian/control 2006-10-05 16:33:40.000000000 +0200
+++ deborphan-1.7.23.new/debian/control 2007-08-21 20:05:00.000000000 +0200
@@ -3,7 +3,7 @@
Priority: optional
Maintainer: Peter Palfrader <[EMAIL PROTECTED]>
Standards-Version: 3.7.2
-Build-Depends: debhelper (>= 4), po4a
+Build-Depends: debhelper (>= 4), po4a, libglib2.0-dev
Package: deborphan
Architecture: any
diff -Nruw deborphan-1.7.23.orig/doc/deborphan.1 deborphan-1.7.23.new/doc/deborphan.1
--- deborphan-1.7.23.orig/doc/deborphan.1 2006-10-05 16:12:51.000000000 +0200
+++ deborphan-1.7.23.new/doc/deborphan.1 2007-08-21 19:47:05.000000000 +0200
@@ -55,10 +55,14 @@
.SS "SEARCH MODIFIERS"
.TP
\fB\-n, \-\-nice\-mode\fP
-Turn off nice-mode.
+Turn OFF nice-mode.
Nice-mode checks if there is a package `suggesting' or `recommending' the package.
If one is found, the package will be marked as in use, or, when \fB\-\-show\-deps\fR is used, print out the package suggesting the package as if it were depending on it.
.TP
+\fB\-\-removable\fP
+Find packages that can \fBindividually\fR be removed without triggering other removals. (turns OFF nice-mode).
+They may be used, but other packages in the system provide the same functionality, so they can be removed as long as these other packages are there. As these other packages may also be in the list, it may not be possible to remove returned packages as a group (\fBdeborphan \-\-removable\fR should be re-run after each removal). On the other hand, it allows to find orphans which would not be listed without --removable.
+.TP
\fB-a, \-\-all\-packages\fP
Check all the packages, instead of only those in the libs section. Best used (if at all used) in combination with \fB\-\-priority\fR. This option implies \fB\-\-show-section\fR.
.\" , when compiled with ALL_PACKAGES_IMPLY_SECTION defined (default)
diff -Nruw deborphan-1.7.23.orig/include/deborphan.h deborphan-1.7.23.new/include/deborphan.h
--- deborphan-1.7.23.orig/include/deborphan.h 2005-03-16 15:52:39.000000000 +0100
+++ deborphan-1.7.23.new/include/deborphan.h 2007-08-21 19:47:21.000000000 +0200
@@ -51,9 +51,45 @@
/* Faster than toupper. Less reliable too. */
#define upcase(c) ((c) & 32 ? (c) ^ 32 : (c))
+/* Handle package version constraints in dependencies */
+#define HANDLE_PKG_VERSIONS 1
+
+#ifndef LOW_MEM
+/* o(n) implementation for finding package users
+ * much faster, but consumes more memory
+ * (need to store users for each package) */
+# define COLLECT_USERS 1
+#endif /* LOW_MEM */
+
+#ifdef HANDLE_PKG_VERSIONS
+enum depverrel {
+ dvrf_earlier= 0001,
+ dvrf_later= 0002,
+ dvrf_strict= 0010,
+ dvrf_orequal= 0020,
+ dvrf_builtup= 0100,
+ dvr_none= 0200,
+ dvr_earlierequal= dvrf_builtup | dvrf_earlier | dvrf_orequal,
+ dvr_earlierstrict= dvrf_builtup | dvrf_earlier | dvrf_strict,
+ dvr_laterequal= dvrf_builtup | dvrf_later | dvrf_orequal,
+ dvr_laterstrict= dvrf_builtup | dvrf_later | dvrf_strict,
+ dvr_exact= 0400
+};
+
+typedef struct
+{
+ unsigned long epoch;
+ const char *version;
+ const char *revision;
+} t_versionrevision;
+#endif /* HANDLE_PKG_VERSIONS */
+
typedef struct dep {
char *name;
unsigned int namehash;
+#ifdef HANDLE_PKG_VERSIONS
+ char *version_expr;
+#endif /* HANDLE_PKG_VERSIONS */
} dep;
/* The initial size of the provides[] and deps[] array, when
@@ -65,6 +101,24 @@
#define INIT_PROVIDES_COUNT 4
#define INIT_EXCLUDES_COUNT 4
+/* Array of dep's */
+typedef struct
+{
+ dep *deps;
+ int cnt;
+ int max;
+} t_deps;
+
+/* Array of conditional dependencies, or 'OR dependencies'.
+ * Each conditional dependency is represented by a t_deps
+ */
+typedef struct
+{
+ t_deps **deps;
+ int cnt;
+ int max;
+} t_cond_deps;
+
/* These arrays aren't exactly neat, but it seems they suffice. */
typedef struct pkg_info {
dep self;
@@ -73,15 +127,21 @@
int provides_cnt;
int provides_max;
char *section;
- dep *deps;
- int deps_cnt;
- int deps_max;
+ t_deps *deps; /* simple dependencies */
+ t_cond_deps *cond_deps; /* OR dependencies */
int install;
int hold;
int essential;
int dummy;
int config;
long installed_size;
+#ifdef HANDLE_PKG_VERSIONS
+ char *version; /* version string */
+ t_versionrevision *versionrevision; /* parsed version string */
+#endif /* HANDLE_PKG_VERSIONS */
+#ifdef COLLECT_USERS
+ t_deps *users;
+#endif /* COLLECT_USERS */
struct pkg_info *next;
} pkg_info;
@@ -105,6 +165,7 @@
ZERO_KEEP,
FIND_CONFIG,
SEARCH_LIBDEVEL,
+ REMOVABLE,
NUM_OPTIONS /* THIS HAS TO BE THE LAST OF THIS ENUM! */
};
@@ -145,11 +206,17 @@
void get_pkg_essential (const char *line, pkg_info *package);
void get_pkg_installed_size(const char *line, pkg_info *package);
void get_pkg_dummy (const char *line, pkg_info *package);
+#ifdef HANDLE_PKG_VERSIONS
+void get_pkg_version(const char *line, pkg_info *package);
+#endif /* HANDLE_PKG_VERSIONS */
unsigned int is_library(pkg_info *package, int search_libdevel);
/* libdeps.c */
-void check_lib_deps(pkg_info *package, pkg_info *current_pkg);
+void check_deps(pkg_info *packages);
+
+/* version.c */
+int package_satisfies_version(pkg_info *package, dep *dep);
/* exit.c */
void error(int exit_status, int error_no, const char *format, ...);
diff -Nruw deborphan-1.7.23.orig/include/set.h deborphan-1.7.23.new/include/set.h
--- deborphan-1.7.23.orig/include/set.h 2004-04-21 14:20:43.000000000 +0200
+++ deborphan-1.7.23.new/include/set.h 2007-08-21 19:47:21.000000000 +0200
@@ -14,10 +14,20 @@
#define set_install(p) ((p)->install = 1)
extern dep *set_dep (dep *, const char *);
+dep * set_dep_nodup(dep *p, char *name);
+void free_dep(dep *d);
+void add_dep(t_deps *deps, dep *d);
+int dep_exists(t_deps *deps, dep *d);
+void add_cond_dep(pkg_info *package, t_deps *new_cond_dep);
+t_deps *new_deps(void);
+void free_deps(t_deps *deps);
+void free_cond_deps(t_cond_deps *d);
extern dep *set_provides (pkg_info *, const char *, int);
extern void set_section (pkg_info *, const char *, const char *);
-extern void set_priority (pkg_info *, const char *);
+extern int set_priority (pkg_info *, const char *);
+pkg_info *new_pkg(void);
extern void init_pkg (pkg_info *);
extern void reinit_pkg (pkg_info *);
+void append_pkg(pkg_info **first, pkg_info **last, pkg_info *p);
#endif
diff -Nruw deborphan-1.7.23.orig/include/xalloc.h deborphan-1.7.23.new/include/xalloc.h
--- deborphan-1.7.23.orig/include/xalloc.h 2004-04-21 14:20:43.000000000 +0200
+++ deborphan-1.7.23.new/include/xalloc.h 2007-08-21 19:47:21.000000000 +0200
@@ -11,3 +11,4 @@
inline void *xmalloc(size_t size);
inline void *xrealloc(void *ptr, size_t size);
inline char *xstrdup(const char *s);
+inline char *xstrndup(const char *s, size_t n);
diff -Nruw deborphan-1.7.23.orig/src/CHANGES deborphan-1.7.23.new/src/CHANGES
--- deborphan-1.7.23.orig/src/CHANGES 1970-01-01 01:00:00.000000000 +0100
+++ deborphan-1.7.23.new/src/CHANGES 2007-08-21 21:53:56.000000000 +0200
@@ -0,0 +1,77 @@
+Changes:
+
+- Handle OR dependencies:
+ - parser code stores single dependencies in pkg_info->deps,
+ OR dependencies in pkg_info->cond_deps
+ - handle version constraints in dependencies:
+ - reuse code from dpkg for parsing and comparing
+ - just store version strings and defer parsing of versions
+ until needed
+ - remove parts of OR deps referring to packages older/newer than
+ what we have.
+ - remove parts of OR dependencies referring to nonexistent packages
+
+- Deal with provides as OR dependencies:
+ build hash table mapping provided_name to
+ list of packages providing it.
+ Then lookup each package dependency in the hash table,
+ and replace with :
+ - provider if only one provider
+ - an OR dependency with all the providers otherwise
+ - don't substitute provides on a dependency with a version.
+ apparently this is what apt-get does. we end up disagreeing
+ on some packages otherwise.
+
+- Fixed --show-deps, some user packages would show up twice
+ if they depended on the package through both depends
+ and provides
+
+- added --removable option:
+ "Find packages that can *individually* be removed
+ without triggering other removals. (implies nice-mode OFF).
+ They may be used, but other packages in the system
+ provide the same functionality, so they can be removed as
+ long as these other packages are there.
+ As these other packages may also be in the list, it may not
+ be possible to remove returned packages as a group
+ (deborphan --removable should be re-run after each removal).
+ On the other hand, it allows to find orphans which would not
+ be listed without --removable."
+ In this case we just ignore OR dependencies:
+ after simplifying OR expressions, all remainging OR expressions
+ mention at least 2 installed packages. So if a given package is
+ mentioned in them, we know there's another package in the
+ system to satisfy the dependency.
+
+- improved speed of dependency checking loop (so much that even
+ with all the extra version logic etc, it's still way faster!)
+ loop was o(n^2) on the number of packages, made it o(n) by
+ storing users in pkg_info.
+
+- some changes are on a compile time switch:
+ HANDLE_PKG_VERSIONS for the version logic,
+ COLLECT_USERS for the new dep check loop (if !LOW_MEM)
+
+- i checked --removable output against apt-get (real_removable
+ script in src/test, (takes forever)), on my system they agree.
+ Also compared with orig deborphan for a few options (default,
+ -n, -d, -a). output was same or better. i haven't checked the
+ others though.
+
+- i'm using glib for the hash tables. I was thinking of linking
+ statically against glib, this way we only create a build dependency,
+ not a package one. However this pulls in most of glib and makes
+ deborphan pretty big so it's really not ideal.
+ looking for a better way ...
+
+
+
+----------
+other ideas/misc stuff
+
+
+- simplify OR dependencies when one other member of the group is in use
+ (would improve results when not using --removable)
+
+- --show-deps really should be --show-users ?
+
diff -Nruw deborphan-1.7.23.orig/src/Makefile.am deborphan-1.7.23.new/src/Makefile.am
--- deborphan-1.7.23.orig/src/Makefile.am 2004-04-21 14:20:43.000000000 +0200
+++ deborphan-1.7.23.new/src/Makefile.am 2007-08-21 20:44:40.000000000 +0200
@@ -4,7 +4,7 @@
# $Id: Makefile.am 409 2004-04-21 12:20:43Z weasel $
bin_PROGRAMS = deborphan
-deborphan_SOURCES = deborphan.c exit.c libdeps.c pkginfo.c xalloc.c string.c keep.c file.c set.c
+deborphan_SOURCES = deborphan.c exit.c libdeps.c pkginfo.c xalloc.c string.c keep.c file.c set.c version.c
KEEPNAME = keep
STATEDIR = /var/lib/deborphan
diff -Nruw deborphan-1.7.23.orig/src/Makefile.in deborphan-1.7.23.new/src/Makefile.in
--- deborphan-1.7.23.orig/src/Makefile.in 2006-11-22 01:21:34.000000000 +0100
+++ deborphan-1.7.23.new/src/Makefile.in 2007-08-21 22:10:45.000000000 +0200
@@ -56,7 +56,7 @@
PROGRAMS = $(bin_PROGRAMS)
am_deborphan_OBJECTS = deborphan.$(OBJEXT) exit.$(OBJEXT) \
libdeps.$(OBJEXT) pkginfo.$(OBJEXT) xalloc.$(OBJEXT) \
- string.$(OBJEXT) keep.$(OBJEXT) file.$(OBJEXT) set.$(OBJEXT)
+ string.$(OBJEXT) keep.$(OBJEXT) file.$(OBJEXT) set.$(OBJEXT) version.$(OBJEXT)
deborphan_OBJECTS = $(am_deborphan_OBJECTS)
deborphan_LDADD = $(LDADD)
DEFAULT_INCLUDES = -I. -I$(srcdir) -I$(top_builddir)/include
@@ -84,7 +84,7 @@
CATOBJEXT = @CATOBJEXT@
CC = @CC@
CCDEPMODE = @CCDEPMODE@
-CFLAGS = @CFLAGS@
+CFLAGS = @CFLAGS@ $(shell pkg-config --cflags glib-2.0)
CFLAG_VISIBILITY = @CFLAG_VISIBILITY@
CPP = @CPP@
CPPFLAGS = @CPPFLAGS@
@@ -124,7 +124,7 @@
LIBMULTITHREAD = @LIBMULTITHREAD@
LIBOBJS = @LIBOBJS@
LIBPTH = @LIBPTH@
-LIBS = @LIBS@
+LIBS = @LIBS@ /usr/lib/libglib-2.0.a
LIBTHREAD = @LIBTHREAD@
LTLIBICONV = @LTLIBICONV@
LTLIBINTL = @LTLIBINTL@
@@ -201,7 +201,7 @@
sharedstatedir = @sharedstatedir@
sysconfdir = @sysconfdir@
target_alias = @target_alias@
-deborphan_SOURCES = deborphan.c exit.c libdeps.c pkginfo.c xalloc.c string.c keep.c file.c set.c
+deborphan_SOURCES = deborphan.c exit.c libdeps.c pkginfo.c xalloc.c string.c keep.c file.c set.c version.c
KEEPNAME = keep
STATEDIR = /var/lib/deborphan
KEEPFILE = $(STATEDIR)/$(KEEPNAME)
diff -Nruw deborphan-1.7.23.orig/src/deborphan.c deborphan-1.7.23.new/src/deborphan.c
--- deborphan-1.7.23.orig/src/deborphan.c 2005-03-16 15:52:39.000000000 +0100
+++ deborphan-1.7.23.new/src/deborphan.c 2007-08-24 15:09:11.000000000 +0200
@@ -68,7 +68,7 @@
#else
char *sfile_content, *sfile_content2;
#endif
- pkg_info *package, *this;
+ pkg_info *packages, *this, *last;
int i, argind;
int exclude_list_cnt = 0;
int exclude_list_max = 0;
@@ -114,6 +114,7 @@
{"guess-doc", 0, 0, 16},
{"find-config", 0, 0, 17},
{"libdevel", 0, 0, 18},
+ {"removable", 0, 0, 19},
{"exclude", 1, 0, 'e'},
{0, 0, 0, 0}
};
@@ -256,6 +257,9 @@
case 18:
options[SEARCH_LIBDEVEL] = 1;
break;
+ case 19:
+ options[REMOVABLE] = 1; /* also turns off NICE_MODE afterwards */
+ break;
case 'e':
while ( optarg ) {
char *c_ptr;
@@ -271,8 +275,7 @@
if ( exclude_list_cnt >= exclude_list_max )
error(EXIT_FAILURE, 0, "Too many exclude packages");
c_ptr = strsep(&optarg, ",");
- exclude_list[ exclude_list_cnt ].name = c_ptr;
- exclude_list[ exclude_list_cnt ].namehash = strhash(c_ptr);
+ set_dep_nodup(&exclude_list[exclude_list_cnt], c_ptr);
++exclude_list_cnt;
}
qsort(exclude_list, exclude_list_cnt, sizeof(exclude_list[0]),
@@ -287,6 +290,8 @@
#ifdef DEFAULT_NICE /* Invert the value of nice_mode */
options[NICE_MODE] ^= 1;
#endif
+ if (options[REMOVABLE])
+ options[NICE_MODE] = 0;
if (options[ZERO_KEEP]) {
if (!kfile)
@@ -401,49 +406,56 @@
sfile_content2 = sfile_content;
#endif
- this = package = (pkg_info *) xmalloc(sizeof(pkg_info));
- init_pkg(this);
+ this = new_pkg();
+ packages = last = NULL;
init_pkg_regex();
+ /* Parse status file */
while ((line = nextline(&sfile_content)) != NULL) {
+#ifdef HANDLE_PKG_VERSIONS
+ if ((!strchr("IPpSsEeDdRrVv", *line)) || (*line == ' '))
+#else
if ((!strchr("IPpSsEeDdRr", *line)) || (*line == ' '))
+#endif /* HANDLE_PKG_VERSIONS */
continue;
+#define keep_pkg(this) \
+ ( (this)->self.name && \
+ !( (exclude_list && \
+ bsearch(&(this)->self, exclude_list, exclude_list_cnt, \
+ sizeof(exclude_list[0]), \
+ (int(*)(const void*, const void*))depcmp) ) \
+ || (!(this)->install && !options[FIND_CONFIG]) ) \
+ )
+
if (*line != '\0') {
strstripchr(line, ' ');
get_pkg_info(line, this);
} else {
- if ( (this->self.name && exclude_list &&
- bsearch(&this->self, exclude_list, exclude_list_cnt,
- sizeof(exclude_list[0]),
- (int(*)(const void*, const void*))depcmp) )
- || (!this->install && !options[FIND_CONFIG]) ) {
+ if (!keep_pkg(this))
reinit_pkg(this);
- } else {
- this->next = xmalloc(sizeof(pkg_info));
- this = this->next;
- init_pkg(this);
+ else
+ {
+ append_pkg(&packages, &last, this);
+ this = new_pkg();
}
}
}
+ /* If status file doesn't end with an empty line,
+ * last package hasn't been added.
+ */
+ if (keep_pkg(this))
+ append_pkg(&packages, &last, this);
+
#ifdef LOW_MEM
free(line);
#else
free(sfile_content2);
#endif
- this->next = NULL;
- this = package;
-
- /* Check the dependencies. Last package is handled specially, because it
- is not terminated with a \n in STATUS_FILE. */
- while (this->next) {
- check_lib_deps(package, this);
- this = this->next;
- }
- if (this->install)
- check_lib_deps(package, this);
+ /* For each package, find out if anything depends on it */
+ check_deps(packages);
free_pkg_regex();
diff -Nruw deborphan-1.7.23.orig/src/exit.c deborphan-1.7.23.new/src/exit.c
--- deborphan-1.7.23.orig/src/exit.c 2004-07-13 19:43:53.000000000 +0200
+++ deborphan-1.7.23.new/src/exit.c 2007-08-21 19:47:36.000000000 +0200
@@ -102,6 +102,9 @@
printf(_("-n Enable checks for `recommends' and `suggests'.\n"));
#endif
+ printf(_("--removable Find packages that can individually be removed\n"));
+ printf(_(" without triggering other removals. Disables nice-mode\n"));
+
printf("--all-packages, ");
printf(_("-a Compare all packages, not just libs.\n"));
diff -Nruw deborphan-1.7.23.orig/src/keep.c deborphan-1.7.23.new/src/keep.c
--- deborphan-1.7.23.orig/src/keep.c 2004-04-21 14:20:43.000000000 +0200
+++ deborphan-1.7.23.new/src/keep.c 2007-08-21 19:47:36.000000000 +0200
@@ -21,6 +21,7 @@
#include <deborphan.h>
#include <xalloc.h>
+#include <set.h>
/* If package is a valid package, this function returns 0. On error, it
* returns -1, if it is not a valid package, it returns the position in
@@ -97,8 +98,7 @@
strstripchr(line2, '\n');
- d->name = line2;
- d->namehash = strhash(d->name);
+ set_dep_nodup(d, line2);
d++;
i++;
@@ -219,8 +219,7 @@
dep d;
for (i = 0; list[i]; i++) {
- d.name = list[i];
- d.namehash = strhash(list[i]);
+ set_dep_nodup(&d, list[i]);
if (mustkeep(d))
return i+1;
}
diff -Nruw deborphan-1.7.23.orig/src/libdeps.c deborphan-1.7.23.new/src/libdeps.c
--- deborphan-1.7.23.orig/src/libdeps.c 2006-10-05 18:33:10.000000000 +0200
+++ deborphan-1.7.23.new/src/libdeps.c 2007-08-21 19:47:36.000000000 +0200
@@ -22,17 +22,440 @@
# include <xalloc.h>
#endif
+#include <set.h>
+
+#include <glib.h>
+
extern int options[];
-/* For each package found, this scans the `package' structure, to
- * see if anything depends on it.
+/* Structure mapping a 'provide' name to all the packages providing it. */
+typedef struct
+{
+ dep self; /* name of virtual package (the thing in the 'provides' field) */
+ t_deps *provs; /* providers */
+} t_provide;
+
+static t_provide *
+new_provide(dep *name)
+{
+ t_provide *p = (t_provide *) xmalloc(sizeof(t_provide));
+ memset(p, 0, sizeof(t_provide));
+ p->self = *name;
+ return p;
+}
+
+static void
+add_provide(t_provide *p, dep *d)
+{
+ if (!p->provs)
+ p->provs = new_deps();
+ add_dep(p->provs, d);
+}
+
+static guint
+dep_hash(gconstpointer key)
+{
+ const dep *d = key;
+ return d->namehash;
+}
+
+static gboolean
+dep_equal(gconstpointer a, gconstpointer b)
+{
+ const dep *d1 = a;
+ const dep *d2 = b;
+
+ return pkgcmp(*d1, *d2);
+}
+
+
+/******** package lookup stuff **********/
+
+static GHashTable *package_lookup_ht = NULL;
+
+static void
+package_lookup_init(pkg_info *packages)
+{
+ pkg_info *p = packages;
+
+ package_lookup_ht = g_hash_table_new(dep_hash, dep_equal);
+
+ for (; p; p = p->next)
+ {
+ g_hash_table_insert(package_lookup_ht, &p->self, p);
+ }
+}
+
+/* Quickly find a package by name */
+static pkg_info *
+package_lookup(dep *package_name)
+{
+ return g_hash_table_lookup(package_lookup_ht, package_name);
+}
+
+/******** end package lookup stuff **********/
+
+/* Build hash table mapping 'provide' names to provider packages */
+static GHashTable*
+collect_provides(pkg_info *package)
+{
+ GHashTable *provides_ht = g_hash_table_new(dep_hash, dep_equal);
+ int prov;
+ t_provide *exists, *provide;
+
+ for (; package; package = package->next)
+ {
+ for (prov = 0; prov < package->provides_cnt; prov++)
+ {
+ provide = exists = g_hash_table_lookup(provides_ht, &package->provides[prov]);
+ if (!provide)
+ provide = new_provide(&package->provides[prov]);
+ add_provide(provide, &package->self);
+ if (!exists)
+ g_hash_table_insert(provides_ht, &provide->self, provide);
+ }
+ }
+ return provides_ht;
+}
+
+/* In all packages' dependencies, replace 'provides' by the actual providers */
+static void
+substitute_provides(pkg_info *package, GHashTable *provides_ht)
+{
+ int i, k, l, m;
+ t_provide *provide;
+
+ for (; package; package = package->next)
+ {
+ t_deps *provs, *deps = package->deps;
+
+ /* substitute provides in normal dependencies */
+ for (i = 0; i < deps->cnt; i++)
+ {
+ if (
+#ifdef HANDLE_PKG_VERSIONS
+ /* don't substitute provides on a dependency with a version */
+ !(deps->deps[i].version_expr) &&
+#endif /* HANDLE_PKG_VERSIONS */
+ (provide = g_hash_table_lookup(provides_ht, &deps->deps[i])))
+ {
+ provs = provide->provs;
+ if (provs->cnt == 1)
+ { /* substitute in place */
+ if (!dep_exists(deps, &provs->deps[0]))
+ deps->deps[i] = provs->deps[0];
+ }
+ else
+ { /* remove provide dependency */
+ deps->deps[i] = deps->deps[deps->cnt - 1];
+ deps->cnt--;
+ i--;
+ { /* add packages providing it instead as an OR dependency */
+ t_deps *cond_dep = new_deps();
+ cond_dep->deps = provs->deps;
+ cond_dep->cnt = provs->cnt;
+ cond_dep->max = provs->cnt;
+ add_cond_dep(package, cond_dep);
+ }
+ }
+ }
+ }
+
+ /* substitute provides in conditional dependencies */
+ for (k = 0; k < package->cond_deps->cnt; k++)
+ {
+ t_deps *deps = package->cond_deps->deps[k];
+ for (l = 0; l < deps->cnt; l++)
+ {
+ if (
+#ifdef HANDLE_PKG_VERSIONS
+ /* don't substitute provides on a dependency with a version */
+ !deps->deps[l].version_expr &&
+#endif /* HANDLE_PKG_VERSIONS */
+ (provide = g_hash_table_lookup(provides_ht, &deps->deps[l])))
+ {
+ provs = provide->provs;
+ if (provs->cnt == 1)
+ { /* substitute in place */
+ if (!dep_exists(deps, &provs->deps[0]))
+ deps->deps[l] = provs->deps[0];
+ }
+ else
+ { /* remove provide dependency ... */
+ deps->deps[l] = deps->deps[deps->cnt - 1];
+ deps->cnt--;
+ l--;
+ /* ... and add its providers at the end */
+ for (m = 0; m < provs->cnt; m++)
+ add_dep(deps, &provs->deps[m]);
+ }
+ }
+ }
+ }
+ }
+}
+
+/* In all packages' dependencies, replace 'provides' by the actual providers */
+static void
+handle_provides(pkg_info *package)
+{
+ GHashTable *provides_ht = collect_provides(package);
+ substitute_provides(package, provides_ht);
+}
+
+/* returns TRUE if a package satisfying dependency dep is present */
+static int
+satisfying_package_present(dep *dep)
+{
+ pkg_info *package = package_lookup(dep);
+
+ if (!package)
+ return 0;
+
+#ifdef HANDLE_PKG_VERSIONS
+ if (dep->version_expr)
+ if (!package_satisfies_version(package, dep))
+ return 0;
+#endif /* HANDLE_PKG_VERSIONS */
+
+ return 1;
+}
+
+/* Remove parts of OR dependencies referring to packages that are not present.
+ * This is necessary to figure out if a package is really needed by an OR dependency
+ *
+ * Cleans up OR dependencies afterwards: empty expressions are removed, and
+ * expressions with only one element are moved with the simple dependencies.
*/
-void
-check_lib_deps(pkg_info * package, pkg_info * current_pkg)
+static void
+remove_non_existant_deps(pkg_info *package)
+{
+ int k,l;
+
+ for (; package; package = package->next)
+ {
+ for (k = 0; k < package->cond_deps->cnt; k++)
+ {
+ t_deps *deps = package->cond_deps->deps[k];
+ for (l = 0; l < deps->cnt; l++)
+ {
+ if (!satisfying_package_present(&deps->deps[l]))
+ { /* remove dep */
+ deps->deps[l] = deps->deps[deps->cnt - 1];
+ deps->cnt--;
+ l--;
+ }
+ }
+
+ /* if we removed deps so that there's only one left,
+ * it's not an OR dependency anymore, so move it with normal deps.
+ * When running in nice mode (using suggests, recommends as deps),
+ * we can also end up with a 0 count */
+ if (deps->cnt == 1)
+ {
+ add_dep(package->deps, &deps->deps[0]);
+ deps->cnt = 0;
+ }
+
+ if (deps->cnt == 0)
+ {
+ t_cond_deps *cdeps = package->cond_deps;
+
+ free_deps(deps);
+ deps = NULL;
+ cdeps->deps[k] = cdeps->deps[cdeps->cnt - 1];
+ cdeps->cnt--;
+ k--;
+ }
+ }
+ }
+}
+
+static void
+debug_dump_packages(pkg_info *package)
+{
+ int k,l;
+
+ for (; package; package = package->next)
+ {
+ t_deps *deps = package->deps;
+ printf("::package '%s'\n", package->self.name);
+
+ /* normal explicit deps */
+ printf(":: ");
+ for (l = 0; l < deps->cnt; l++)
+ {
+ if (l && l % 6 == 0)
+ {
+ printf("\n:: ");
+ }
+ printf("%s, ", deps->deps[l].name);
+ }
+ printf("\n");
+
+ /* OR deps (explicit, or through provides) */
+ for (k = 0; k < package->cond_deps->cnt; k++)
+ {
+ t_deps *deps = package->cond_deps->deps[k];
+ printf(":: ");
+ for (l = 0; l < deps->cnt; l++)
+ {
+ printf("| %s", deps->deps[l].name);
+#ifdef HANDLE_PKG_VERSIONS
+ if (deps->deps[l].version_expr)
+ printf(" (%s)", deps->deps[l].version_expr);
+#endif /* HANDLE_PKG_VERSIONS */
+ }
+ printf("\n");
+ }
+ }
+}
+
+#ifdef COLLECT_USERS
+/* o(n) implementation, n = number of packages */
+
+/* Walk through packages and populate users fields */
+static void
+collect_users(pkg_info *packages)
+{
+ pkg_info *used, *package;
+ int k, l;
+
+ for (package = packages; package; package = package->next)
+ {
+ if (!package->users)
+ package->users = new_deps();
+ }
+
+ for (package = packages; package; package = package->next)
+ {
+ t_deps *deps = package->deps;
+
+ for (l = 0; l < deps->cnt; l++)
+ {
+ if ((used = package_lookup(&deps->deps[l])) &&
+ used != package) /* Let's ignore cases where a package depends on itself. See #366028 */
+ add_dep(used->users, &package->self);
+ }
+
+ /* at this point all OR expressions mention at least 2 installed packages
+ * so if a given package is mentioned in them, we know there's another
+ * package in the system to satisfy the dependency. so in the case where
+ * we're looking for removable packages, OR expresions don't bind it.
+ */
+ if (!options[REMOVABLE])
+ for (k = 0; k < package->cond_deps->cnt; k++)
+ {
+ t_deps *deps = package->cond_deps->deps[k];
+
+ for (l = 0; l < deps->cnt; l++)
+ {
+ if ((used = package_lookup(&deps->deps[l])) &&
+ used != package) /* Let's ignore cases where a package depends on itself. See #366028 */
+ add_dep(used->users, &package->self);
+ }
+ }
+ }
+}
+
+/* Find out if there are packages using current_pkg.
+ * Returns true if users are found, 0 otherwise
+ * if options[SHOW_DEPS], accumulate users found in deps_found
+ */
+static int
+find_pkg_users(pkg_info *packages, pkg_info *current_pkg, t_deps *deps_found)
{
- int deps, prov, no_dep_found = 1, search_found = 1;
+ int i;
+
+ if (current_pkg->users->cnt == 0)
+ return 0;
+
+ if (options[SHOW_DEPS])
+ for (i = 0; i < current_pkg->users->cnt; i++)
+ add_dep(deps_found, ¤t_pkg->users->deps[i]);
+
+ return 1;
+}
+
+
+#else
+/* slower o(n^2) implementation, requires less memory though */
+
+
+/* see if package depends on current_pkg through a conditional dependency (or) */
+static inline int
+find_cond_deps(pkg_info *current_pkg, pkg_info *package, t_deps *deps_found)
+{
+ int k, l;
+
+ for (k = 0; k < package->cond_deps->cnt; k++)
+ {
+ t_deps *deps = package->cond_deps->deps[k];
+
+ for (l = 0; l < deps->cnt; l++) {
+ if (pkgcmp(current_pkg->self, deps->deps[l])) {
+ if (options[SHOW_DEPS])
+ add_dep(deps_found, &package->self);
+ else
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+/* scans the `package' structure, to see if anything depends on current_pkg.
+ * Returns true if users are found, 0 otherwise
+ * if options[SHOW_DEPS], accumulate users found in deps_found
+ */
+static int
+find_pkg_users(pkg_info *packages, pkg_info *current_pkg, t_deps *deps_found)
+{
+ int i;
+ pkg_info *p;
+
+ /* Search all (installed) packages for dependencies.
+ */
+ for (p = packages; p; p = p->next)
+ {
+ t_deps *pkg_deps = p->deps;
+ /* Let's ignore cases where a package depends on itself. See #366028 */
+ if (pkgcmp(current_pkg->self, p->self))
+ continue;
+
+ for (i = 0; i < pkg_deps->cnt; i++) {
+ if (pkgcmp(current_pkg->self, pkg_deps->deps[i]))
+ {
+ if (options[SHOW_DEPS])
+ add_dep(deps_found, &p->self);
+ else
+ return 1;
+ }
+ }
+
+ /* at this point all OR expressions mention at least 2 installed packages
+ * so if our current package is mentioned in them, we know there's another
+ * package in the system to satisfy the dependency. so in the case where
+ * we're looking for removable packages, OR expresions don't bind it.
+ */
+ if (!options[REMOVABLE])
+ if (find_cond_deps(current_pkg, p, deps_found))
+ return 1;
+ }
+ return 0;
+}
+
+#endif /* COLLECT_USERS */
+
+
+/* Find out if anything depends on package current_pkg */
+static void
+check_pkg_deps(pkg_info *packages, pkg_info *current_pkg)
+{
+ int no_dep_found = 1, search_found = 1;
int i;
static int j;
+ static t_deps *deps_found = NULL; /* keep it around to avoid having to reallocate every time */
extern char **search_for;
@@ -79,33 +502,18 @@
if (options[SHOW_SECTION])
printf(")");
printf("\n");
+ if (!deps_found)
+ deps_found = new_deps();
}
- /* Search all (installed) packages for dependencies.
- */
- for (; package && no_dep_found; package = package->next) {
- /* Let's ignore cases where a package depends on itself. See #366028 */
- if (pkgcmp(current_pkg->self, package->self))
- continue;
-
- for (deps = 0; deps < package->deps_cnt && no_dep_found; deps++) {
- for (prov = 0; prov < current_pkg->provides_cnt && no_dep_found;
- prov++) {
- if (pkgcmp(current_pkg->provides[prov], package->deps[deps])) {
- if (options[SHOW_DEPS])
- printf(" %s\n", package->self.name);
- else
- no_dep_found = 0;
- }
- }
+ no_dep_found = !find_pkg_users(packages, current_pkg, deps_found);
- if (pkgcmp(current_pkg->self, package->deps[deps])) {
if (options[SHOW_DEPS])
- printf(" %s\n", package->self.name);
- else
- no_dep_found = 0;
- }
- }
+ {
+ for (i = 0; i < deps_found->cnt; i++)
+ printf(" %s\n", deps_found->deps[i].name);
+ /* recycle for next use. contained dep's are copied so don't need freeing */
+ deps_found->cnt = 0;
}
if (no_dep_found && (!options[SHOW_DEPS])) {
@@ -124,3 +532,22 @@
printf("\n");
}
}
+
+/* For each package, find out if anything depends on it */
+void
+check_deps(pkg_info *packages)
+{
+ pkg_info *p;
+
+ package_lookup_init(packages);
+ handle_provides(packages);
+ remove_non_existant_deps(packages);
+/* debug_dump_packages(packages); */
+
+#ifdef COLLECT_USERS
+ collect_users(packages);
+#endif /* COLLECT_USERS */
+
+ for (p = packages; p; p = p->next)
+ check_pkg_deps(packages, p);
+}
diff -Nruw deborphan-1.7.23.orig/src/pkginfo.c deborphan-1.7.23.new/src/pkginfo.c
--- deborphan-1.7.23.orig/src/pkginfo.c 2006-10-05 18:33:10.000000000 +0200
+++ deborphan-1.7.23.new/src/pkginfo.c 2007-08-21 19:47:36.000000000 +0200
@@ -169,6 +169,13 @@
get_pkg_deps(line, package);
break;
}
+ break;
+#ifdef HANDLE_PKG_VERSIONS
+ case 'V': /* Version */
+ get_pkg_version(line, package);
+ break;
+#endif /* HANDLE_PKG_VERSIONS */
+
}
}
@@ -182,8 +189,6 @@
void
get_pkg_installed_size(const char *line, pkg_info *package)
{
- char *sz;
-
if (strncasecmp(line, "Installed-Size:", 15) == 0)
package->installed_size = strtol(line + 15, NULL, 10);
}
@@ -200,50 +205,70 @@
}
}
+#ifdef HANDLE_PKG_VERSIONS
+void
+get_pkg_version(const char *line, pkg_info *package)
+{
+ char *line2;
+
+ line2 = strchr(line, ':')+1;
+ package->version = xstrdup(line2);
+}
+#endif /* HANDLE_PKG_VERSIONS */
+
+#define DEPS_MAX 40
+
void
get_pkg_deps(const char *line, pkg_info * package)
{
- char *tok, *line2, *version = NULL;
- unsigned int num_deps;
- unsigned int i, dup = 0;
- dep d;
+ char *tok, *line2, *version, *version_end = NULL;
+ char *expr = NULL;
line2 = strchr(line, ':')+1;
- num_deps = package->deps_cnt;
+ while ((expr = strsep(&line2, ",")))
+ {
+ dep deps[DEPS_MAX] = {{0, }, };
+ unsigned int num_dep = 0; /* number of dependencies in current expr
+ * (>1 if it contains '|'s ) */
- for (; (tok = strsep(&line2, ",|")); num_deps++) {
+ while ((tok = strsep(&expr, "|")))
+ {
/* Versions are up to dpkg. */
if ((version = strchr(tok, '(')))
- *version = '\0';
-
- set_dep(&d, tok);
- dup = 0;
- for (i = 0; i<num_deps; i++ ) {
- if (pkgcmp(package->deps[i], d)) {
- dup = 1;
- break;
- }
- }
-
- if (dup)
- num_deps--;
- else {
- if (num_deps >= package->deps_max) {
- /* grow deps[] array */
- package->deps_max = package->deps_max ? package->deps_max*2 : INIT_DEPENDS_COUNT;
-#ifdef DEBUG
- fprintf(stderr, "Growing deps field to %d.\n", package->deps_max);
- fflush(stderr);
-#endif /* DEBUG */
- package->deps = xrealloc( package->deps, package->deps_max * sizeof(package->deps[0]) );
+ {
+ *version++ = '\0';
+#ifdef HANDLE_PKG_VERSIONS
+ if ((version_end = strchr(version, ')')))
+ *version_end = 0;
+#endif /* HANDLE_PKG_VERSIONS */
+ }
+
+ set_dep(deps + num_dep, tok);
+#ifdef HANDLE_PKG_VERSIONS
+ if (version)
+ deps[num_dep].version_expr = xstrdup(version);
+#endif /* HANDLE_PKG_VERSIONS */
+ num_dep++;
+ if (num_dep > DEPS_MAX)
+ error(EXIT_FAILURE, 0, "num_dep > DEPS_MAX");
+ }
+
+ if (num_dep == 1) /* simple dependency */
+ add_dep(package->deps, &deps[0]);
+
+ if (num_dep > 1) /* OR dependency */
+ {
+ t_deps *cond_dep = new_deps();
+ int i;
+
+ for (i = 0; i < num_dep; i++)
+ add_dep(cond_dep, &deps[i]);
+ add_cond_dep(package, cond_dep);
}
- package->deps[num_deps] = d;
}
}
- package->deps_cnt = num_deps;
-}
void
get_pkg_priority(const char *line, pkg_info * package)
diff -Nruw deborphan-1.7.23.orig/src/set.c deborphan-1.7.23.new/src/set.c
--- deborphan-1.7.23.orig/src/set.c 2004-04-21 14:20:43.000000000 +0200
+++ deborphan-1.7.23.new/src/set.c 2007-08-21 19:47:36.000000000 +0200
@@ -12,16 +12,117 @@
#include <deborphan.h>
#include <xalloc.h>
+#include <set.h>
dep *
set_dep(dep *p, const char *name)
{
p->name = xstrdup(name);
p->namehash = strhash(name);
+#ifdef HANDLE_PKG_VERSIONS
+ p->version_expr = NULL;
+#endif /* HANDLE_PKG_VERSIONS */
+ return p;
+}
+/* yuck yuck yuck */
+dep *
+set_dep_nodup(dep *p, char *name)
+{
+ p->name = name;
+ p->namehash = strhash(name);
+#ifdef HANDLE_PKG_VERSIONS
+ p->version_expr = NULL;
+#endif /* HANDLE_PKG_VERSIONS */
return p;
}
+void
+free_dep_content(dep *d)
+{
+ free(d->name);
+#ifdef HANDLE_PKG_VERSIONS
+ if (d->version_expr)
+ free(d->version_expr);
+#endif /* HANDLE_PKG_VERSIONS */
+}
+
+int
+dep_exists(t_deps *deps, dep *d)
+{
+ unsigned int i = 0;
+ unsigned int num_deps = deps->cnt;
+
+ for (i = 0; i < num_deps; i++)
+ if (pkgcmp(deps->deps[i], *d))
+ return 1;
+ return 0;
+}
+
+void
+add_dep(t_deps *deps, dep *d)
+{
+ unsigned int i = 0;
+ unsigned int num_deps = deps->cnt;
+
+ /* check for dup's */
+ for (i = 0; i < num_deps; i++ )
+ if (pkgcmp(deps->deps[i], *d))
+ return;
+
+ if (num_deps >= deps->max)
+ {
+ /* grow deps[] array */
+ deps->max = deps->max ? deps->max*2 : INIT_DEPENDS_COUNT;
+#ifdef DEBUG
+ fprintf(stderr, "Growing deps field to %d.\n", deps->max);
+ fflush(stderr);
+#endif /* DEBUG */
+ deps->deps = xrealloc( deps->deps, deps->max * sizeof(deps->deps[0]) );
+ }
+ deps->deps[num_deps] = *d;
+
+ num_deps++;
+ deps->cnt = num_deps;
+}
+
+t_deps *
+new_deps(void)
+{
+ t_deps *d = xmalloc(sizeof(t_deps));
+ memset(d, 0, sizeof(t_deps));
+ return d;
+}
+
+static t_cond_deps *
+new_cond_deps(void)
+{
+ t_cond_deps *d = xmalloc(sizeof(t_cond_deps));
+ memset(d, 0, sizeof(t_cond_deps));
+ return d;
+}
+
+void
+add_cond_dep(pkg_info *package, t_deps *new_cond_dep)
+{
+ t_cond_deps *cond_deps = package->cond_deps;
+ unsigned int num = cond_deps->cnt;
+
+ if (num >= cond_deps->max) {
+ /* grow cond_deps[] array */
+ cond_deps->max = cond_deps->max ? cond_deps->max*2 : INIT_DEPENDS_COUNT;
+#ifdef DEBUG
+ fprintf(stderr, "Growing cond_deps field to %d.\n", cond_deps->max);
+ fflush(stderr);
+#endif /* DEBUG */
+ cond_deps->deps = xrealloc( cond_deps->deps, cond_deps->max * sizeof(cond_deps->deps[0]) );
+ }
+ cond_deps->deps[num] = new_cond_dep;
+
+ num++;
+ cond_deps->cnt = num;
+}
+
dep *
set_provides(pkg_info *p, const char *name, const int i)
{
@@ -29,15 +130,13 @@
/* grow provides[] array */
p->provides_max = p->provides_max ? p->provides_max*2 : INIT_PROVIDES_COUNT;
#ifdef DEBUG
- fprintf(stderr, "Growing provides field to %d\n.", p->provides_max); // FIXME
+ fprintf(stderr, "Growing provides field to %d\n.", p->provides_max);
fflush(stderr);
#endif /* DEBUG */
p->provides = xrealloc( p->provides, p->provides_max * sizeof(p->provides[0]) );
}
- p->provides[i].name = xstrdup(name);
- p->provides[i].namehash = strhash(name);
-
+ set_dep(&p->provides[i], name);
return &(p->provides[i]);
}
@@ -60,26 +159,83 @@
return (p->priority = string_to_priority(priority));
}
+pkg_info *
+new_pkg(void)
+{
+ pkg_info *p = xmalloc(sizeof(pkg_info));
+
+ init_pkg(p);
+ return p;
+}
+
void
init_pkg(pkg_info *p)
{
memset(p, 0, sizeof(pkg_info));
+ p->deps = new_deps();
+ p->cond_deps = new_cond_deps();
+}
+
+void
+free_deps(t_deps *deps)
+{
+ int i;
+
+ for (i = deps->cnt - 1; i >= 0; i--)
+ free_dep_content(&deps->deps[i]);
+ if (deps->max > 0)
+ free(deps->deps);
+ free(deps);
+}
+
+void
+free_cond_deps(t_cond_deps *d)
+{
+ int i;
+
+ for (i = d->cnt - 1; i >= 0; i--)
+ free_deps(d->deps[i]);
+ if (d->max > 0)
+ free(d->deps);
+ free(d);
+}
+
+void
+append_pkg(pkg_info **first, pkg_info **last, pkg_info *p)
+{
+ if (!*last)
+ *last = *first = p;
+ else
+ {
+ (*last)->next = p;
+ *last = p;
+ }
}
void
reinit_pkg(pkg_info *p)
{
int i;
- free(p->self.name);
+
+ free_dep_content(&p->self);
free(p->section);
- for (i = p->deps_cnt-1; i >= 0; i--)
- free(p->deps[i].name);
- if (p->deps_max > 0)
- free(p->deps);
+
+ free_deps(p->deps);
+ p->deps = NULL;
+
+ free_cond_deps(p->cond_deps);
+ p->cond_deps = NULL;
for (i = p->provides_cnt-1; i >= 0; i--)
- free(p->provides[i].name);
+ free_dep_content(&p->provides[i]);
if (p->provides_max > 0)
free(p->provides);
+
+#ifdef HANDLE_PKG_VERSIONS
+ if (p->version)
+ free(p->version);
+ p->version = NULL;
+#endif /* HANDLE_PKG_VERSIONS */
+
init_pkg(p);
}
diff -Nruw deborphan-1.7.23.orig/src/test/real_removables deborphan-1.7.23.new/src/test/real_removables
--- deborphan-1.7.23.orig/src/test/real_removables 1970-01-01 01:00:00.000000000 +0100
+++ deborphan-1.7.23.new/src/test/real_removables 2007-08-21 10:31:07.000000000 +0200
@@ -0,0 +1,11 @@
+#!/bin/bash
+
+COLUMNS=250 dpkg -l | tail -n +6 | grep '^ii' | cut -b5- | cut -d\ -f1 |
+while read p; do
+ echo $p
+ apt-get --simulate remove "$p" > /tmp/real_removables_tmp 2>&1
+# echo apt-get --simulate remove "$p"
+ if grep -q '0 upgraded, 0 newly installed, 1 to remove' /tmp/real_removables_tmp; then
+ echo "removable:$p"
+ fi
+done
diff -Nruw deborphan-1.7.23.orig/src/version.c deborphan-1.7.23.new/src/version.c
--- deborphan-1.7.23.orig/src/version.c 1970-01-01 01:00:00.000000000 +0100
+++ deborphan-1.7.23.new/src/version.c 2007-08-21 19:47:36.000000000 +0200
@@ -0,0 +1,252 @@
+/* version.c - handle package version constraints in dependencies
+ Copyright (C) 2000, 2001, 2002, 2003 Cris van Pelt
+ Copyright (C) 2003, 2004, 2005, 2006 Peter Palfrader
+
+ $Id$
+
+ Distributed under the terms of the Artistic License.
+*/
+
+#include <ctype.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <deborphan.h>
+#include <set.h>
+#include <xalloc.h>
+
+
+#ifdef HANDLE_PKG_VERSIONS
+
+static void parse_version(const char *version, t_versionrevision *vrev);
+
+/*********************** begin code from dpkg *****************************/
+
+/* Reimplementation of the standard ctype.h is* functions. Since gettext
+ * has overloaded the meaning of LC_CTYPE we can't use that to force C
+ * locale, so use these cis* functions instead.
+ */
+static int cisdigit(int c) {
+ return (c>='0') && (c<='9');
+}
+
+static int cisalpha(int c) {
+ return ((c>='a') && (c<='z')) || ((c>='A') && (c<='Z'));
+}
+
+static const char *
+parseversion(t_versionrevision *rversion, const char *string)
+{
+ char *hyphen, *colon, *eepochcolon;
+ const char *end, *ptr;
+ unsigned long epoch;
+
+ if (!*string) return "version string is empty";
+
+ /* trim leading and trailing space */
+ while (*string && (*string == ' ' || *string == '\t') ) string++;
+ /* string now points to the first non-whitespace char */
+ end = string;
+ /* find either the end of the string, or a whitespace char */
+ while (*end && *end != ' ' && *end != '\t' ) end++;
+ /* check for extra chars after trailing space */
+ ptr = end;
+ while (*ptr && ( *ptr == ' ' || *ptr == '\t' ) ) ptr++;
+ if (*ptr) return "version string has embedded spaces";
+
+ colon= strchr(string,':');
+ if (colon) {
+ epoch= strtoul(string,&eepochcolon,10);
+ if (colon != eepochcolon) return "epoch in version is not number";
+ if (!*++colon) return "nothing after colon in version number";
+ string= colon;
+ rversion->epoch= epoch;
+ } else {
+ rversion->epoch= 0;
+ }
+ rversion->version= xstrndup(string, end - string);
+ hyphen= strrchr(rversion->version,'-');
+ if (hyphen) *hyphen++= 0;
+ rversion->revision= hyphen ? hyphen : "";
+
+ return NULL;
+}
+
+
+/* assume ascii; warning: evaluates x multiple times! */
+#define order(x) ((x) == '~' ? -1 \
+ : cisdigit((x)) ? 0 \
+ : !(x) ? 0 \
+ : cisalpha((x)) ? (x) \
+ : (x) + 256)
+
+static int
+verrevcmp(const char *val, const char *ref)
+{
+ if (!val) val= "";
+ if (!ref) ref= "";
+
+ while (*val || *ref) {
+ int first_diff= 0;
+
+ while ( (*val && !cisdigit(*val)) || (*ref && !cisdigit(*ref)) ) {
+ int vc= order(*val), rc= order(*ref);
+ if (vc != rc) return vc - rc;
+ val++; ref++;
+ }
+
+ while ( *val == '0' ) val++;
+ while ( *ref == '0' ) ref++;
+ while (cisdigit(*val) && cisdigit(*ref)) {
+ if (!first_diff) first_diff= *val - *ref;
+ val++; ref++;
+ }
+ if (cisdigit(*val)) return 1;
+ if (cisdigit(*ref)) return -1;
+ if (first_diff) return first_diff;
+ }
+ return 0;
+}
+
+static int
+versioncompare(const t_versionrevision *version,
+ const t_versionrevision *refversion)
+{
+ int r;
+
+ if (version->epoch > refversion->epoch) return 1;
+ if (version->epoch < refversion->epoch) return -1;
+ r= verrevcmp(version->version,refversion->version); if (r) return r;
+ return verrevcmp(version->revision,refversion->revision);
+}
+
+static int
+versionsatisfied3(const t_versionrevision *it,
+ const t_versionrevision *ref,
+ enum depverrel verrel) {
+ int r;
+ if (verrel == dvr_none) return 1;
+ r= versioncompare(it,ref);
+ switch (verrel) {
+ case dvr_earlierequal: return r <= 0;
+ case dvr_laterequal: return r >= 0;
+ case dvr_earlierstrict: return r < 0;
+ case dvr_laterstrict: return r > 0;
+ case dvr_exact: return r == 0;
+ default: error(EXIT_FAILURE, 0, "unknown verrel");
+ }
+ return 0;
+}
+
+/* from f_dependency() in dpkg's fields.c */
+static void
+parse_version_expr_scary_internals(const char *expr,
+ enum depverrel *verrel, t_versionrevision *vrev)
+{
+ char c1, c2;
+ const char *p = expr;
+
+ c1= *p;
+ if (c1 == '<' || c1 == '>') {
+ c2= *++p;
+ *verrel= (c1 == '<') ? dvrf_earlier : dvrf_later;
+ if (c2 == '=') {
+ *verrel |= (dvrf_orequal | dvrf_builtup);
+ p++;
+ } else if (c2 == c1) {
+ *verrel |= (dvrf_strict | dvrf_builtup);
+ p++;
+ } else if (c2 == '<' || c2 == '>') {
+ error(EXIT_FAILURE, 0,
+ " bad version relationship %c%c",
+ c1,c2);
+ *verrel= dvr_none;
+ } else {
+ error(EXIT_FAILURE, 0,
+ " `%c' is obsolete, use `%c=' or `%c%c' instead",
+ c1,c1,c1,c1);
+ *verrel |= (dvrf_orequal | dvrf_builtup);
+ }
+ } else if (c1 == '=') {
+ *verrel= dvr_exact;
+ p++;
+ } else {
+ error(EXIT_FAILURE, 0,
+ " implicit exact match on version number, suggest using `=' instead");
+ *verrel= dvr_exact;
+ }
+
+ if (!isspace(*p) && !isalnum(*p)) {
+ error(EXIT_FAILURE, 0,
+ " version value starts with non-alphanumeric, suggest adding a space");
+ }
+
+ parse_version(p, vrev);
+}
+
+/*********************** end code from dpkg *****************************/
+
+static t_versionrevision*
+new_versionrevision(void)
+{
+ t_versionrevision *rev;
+
+ rev = xmalloc(sizeof(t_versionrevision));
+ memset(rev, 0, sizeof(t_versionrevision));
+ return rev;
+}
+
+static void
+ensure_package_versionrevision(pkg_info *package)
+{
+ if (package->versionrevision)
+ return;
+
+ package->versionrevision = new_versionrevision();
+ parse_version(package->version, package->versionrevision);
+}
+
+static void
+parse_version(const char *version, t_versionrevision *vrev)
+{
+ const char *err = parseversion(vrev, version);
+
+ if (err)
+ error(EXIT_FAILURE, 0, err);
+}
+
+static void
+parse_version_expr(const char* version_expr,
+ t_versionrevision *vrev, enum depverrel *verrel)
+{
+ parse_version_expr_scary_internals(version_expr, verrel, vrev);
+}
+
+static int
+version_satisfied(t_versionrevision *p, t_versionrevision *drev, enum depverrel dverrel)
+{
+ return versionsatisfied3(p, drev, dverrel);
+}
+
+int
+package_satisfies_version(pkg_info *package, dep *dep)
+{
+ t_versionrevision dep_vrev;
+ enum depverrel dep_verrel;
+ int res;
+
+ /* When parsing versions: only about 1/4 of the versions used
+ * in OR expressions are unique (60/224 on my system),
+ * so it looks like a good idea to cache requests.
+ * It makes however no difference in terms of running time.
+ */
+ ensure_package_versionrevision(package);
+ parse_version_expr(dep->version_expr, &dep_vrev, &dep_verrel);
+ res = version_satisfied(package->versionrevision, &dep_vrev, dep_verrel);
+ return res;
+}
+
+
+
+
+#endif /* HANDLE_PKG_VERSIONS */
diff -Nruw deborphan-1.7.23.orig/src/xalloc.c deborphan-1.7.23.new/src/xalloc.c
--- deborphan-1.7.23.orig/src/xalloc.c 2004-04-21 14:20:43.000000000 +0200
+++ deborphan-1.7.23.new/src/xalloc.c 2007-08-21 19:47:36.000000000 +0200
@@ -79,4 +79,15 @@
return t;
}
+inline char *
+xstrndup(const char *s, size_t n)
+{
+ char *t;
+
+ if ((t = strndup(s, n)) == NULL)
+ error(EXIT_FAILURE, errno, "xstrndup: %p, %i", (void *)t, n);
+
+ return t;
+}
+
#endif /* USE_XALLOC */
diff -u deborphan-1.7.23.new/src/deborphan.c deborphan-1.7.23.new/src/deborphan.c
--- deborphan-1.7.23.new/src/deborphan.c 2007-08-21 19:47:36.000000000 +0200
+++ deborphan-1.7.23.new/src/deborphan.c 2007-08-24 15:09:11.000000000 +0200
@@ -258,8 +258,7 @@
options[SEARCH_LIBDEVEL] = 1;
break;
case 19:
- options[REMOVABLE] = 1;
- options[NICE_MODE] = 0;
+ options[REMOVABLE] = 1; /* also turns off NICE_MODE afterwards */
break;
case 'e':
while ( optarg ) {
@@ -289,9 +288,10 @@
}
}
#ifdef DEFAULT_NICE /* Invert the value of nice_mode */
- if (!options[REMOVABLE])
options[NICE_MODE] ^= 1;
#endif
+ if (options[REMOVABLE])
+ options[NICE_MODE] = 0;
if (options[ZERO_KEEP]) {
if (!kfile)
only in patch2:
unchanged:
--- deborphan-1.7.23.orig/debian/changelog 2006-11-22 01:20:58.000000000 +0100
+++ deborphan-1.7.23.new/debian/changelog 2007-08-24 15:29:36.000000000 +0200
@@ -1,3 +1,26 @@
+deborphan (1.7.23a) unstable; urgency=low
+
+ * Handle OR dependencies:
+ * Handle version constraints in OR dependencies
+ * Handle provides as OR dependencies:
+ * Fixed --show-deps, some user packages would show up twice
+ if they depended on the package through both depends
+ and provides
+ * added --removable option:
+ "Find packages that can *individually* be removed
+ without triggering other removals. (implies nice-mode OFF).
+ They may be used, but other packages in the system
+ provide the same functionality, so they can be removed as
+ long as these other packages are there.
+ As these other packages may also be in the list, it may not
+ be possible to remove returned packages as a group
+ (deborphan --removable should be re-run after each removal).
+ On the other hand, it allows to find orphans which would not
+ be listed without --removable."
+ * much faster
+
+ -- Matthieu Lucotte <[EMAIL PROTECTED]> Fri, 24 Aug 2007 15:27:44 +0100
+
deborphan (1.7.23) unstable; urgency=low
* Whitespace cleanup in orphaner (closes: #398330).
