Implement -L/-follow.

4 files changed, 110 insertions, 34 deletions

diff --git a/bftw.c b/bftw.c
index e445432..d2a73d6 100644
--- a/bftw.c
+++ b/bftw.c
@@ -27,7 +27,9 @@
 #include <dirent.h>
 #include <errno.h>
 #include <fcntl.h>
+#include <limits.h>
 #include <stdbool.h>
+#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sys/stat.h>
@@ -104,6 +106,11 @@ struct dircache_entry {
 	/** Reference count. */
 	size_t refcount;
 
+	/** The device number, for cycle detection. */
+	dev_t dev;
+	/** The inode number, for cycle detection. */
+	ino_t ino;
+
 	/** The offset of this directory in the full path. */
 	size_t nameoff;
 	/** The length of the directory's name. */
@@ -438,11 +445,7 @@ static struct dircache_entry *dirqueue_pop(struct dirqueue *queue) {
 	return entry;
 }
 
-static void ftwbuf_set_error(struct BFTW *ftwbuf, int error) {
-	ftwbuf->typeflag = BFTW_ERROR;
-	ftwbuf->error = error;
-}
-
+/** Fill in ftwbuf fields with information from a struct dirent. */
 static void ftwbuf_use_dirent(struct BFTW *ftwbuf, const struct dirent *de) {
 #if defined(_DIRENT_HAVE_D_TYPE) || defined(DT_DIR)
 	switch (de->d_type) {
@@ -471,6 +474,7 @@ static void ftwbuf_use_dirent(struct BFTW *ftwbuf, const struct dirent *de) {
 #endif
 }
 
+/** Call stat() and use the results. */
 static int ftwbuf_stat(struct BFTW *ftwbuf, struct stat *sb, int flags) {
 	int ret = fstatat(ftwbuf->at_fd, ftwbuf->at_path, sb, flags);
 	if (ret != 0) {
@@ -534,13 +538,14 @@ struct bftw_state {
 
 	/** The cache of open directories. */
 	struct dircache cache;
+
+	/** The queue of directories left to explore. */
+	struct dirqueue queue;
 	/** The current dircache entry. */
 	struct dircache_entry *current;
 	/** The current traversal status. */
 	enum bftw_status status;
 
-	/** The queue of directories left to explore. */
-	struct dirqueue queue;
 	/** The current path being explored. */
 	struct dynstr path;
 
@@ -561,10 +566,10 @@ static void bftw_state_init(struct bftw_state *state, bftw_fn *fn, int nopenfd,
 	state->error = 0;
 
 	dircache_init(&state->cache, nopenfd);
-	state->current = NULL;
-	state->status = BFTW_CURRENT;
 
 	dirqueue_init(&state->queue);
+	state->current = NULL;
+	state->status = BFTW_CURRENT;
 
 	dynstr_init(&state->path);
 }
@@ -586,6 +591,15 @@ static int bftw_path_concat(struct bftw_state *state, const char *subpath) {
 }
 
 /**
+ * Record an error.
+ */
+static void bftw_set_error(struct bftw_state *state, int error) {
+	state->error = error;
+	state->ftwbuf.error = error;
+	state->ftwbuf.typeflag = BFTW_ERROR;
+}
+
+/**
  * Initialize the buffers with data about the current path.
  */
 static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de) {
@@ -620,16 +634,15 @@ static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de)
 		ftwbuf->typeflag = BFTW_UNKNOWN;
 	}
 
-	bool follow;
-	if (state->flags & BFTW_FOLLOW_ROOT) {
-		follow = !state->current;
-	} else {
-		follow = false;
-	}
+	bool follow = state->flags & (current ? BFTW_FOLLOW_NONROOT : BFTW_FOLLOW_ROOT);
+
+	bool detect_cycles = (state->flags & BFTW_DETECT_CYCLES)
+		&& state->status == BFTW_CHILD;
 
 	if ((state->flags & BFTW_STAT)
 	    || ftwbuf->typeflag == BFTW_UNKNOWN
-	    || (ftwbuf->typeflag == BFTW_LNK && follow)) {
+	    || (ftwbuf->typeflag == BFTW_LNK && follow)
+	    || (ftwbuf->typeflag == BFTW_DIR && detect_cycles)) {
 		int flags = follow ? 0 : AT_SYMLINK_NOFOLLOW;
 
 		int ret = ftwbuf_stat(ftwbuf, &state->statbuf, flags);
@@ -640,8 +653,19 @@ static void bftw_init_buffers(struct bftw_state *state, const struct dirent *de)
 		}
 
 		if (ret != 0) {
-			state->error = errno;
-			ftwbuf_set_error(ftwbuf, state->error);
+			bftw_set_error(state, errno);
+			return;
+		}
+
+		if (ftwbuf->typeflag == BFTW_DIR && detect_cycles) {
+			dev_t dev = ftwbuf->statbuf->st_dev;
+			ino_t ino = ftwbuf->statbuf->st_ino;
+			for (const struct dircache_entry *entry = current; entry; entry = entry->parent) {
+				if (dev == entry->dev && ino == entry->ino) {
+					bftw_set_error(state, ELOOP);
+					return;
+				}
+			}
 		}
 	}
 }
@@ -673,10 +697,30 @@ static int bftw_handle_path(struct bftw_state *state) {
 }
 
 /**
+ * Add a new entry to the cache.
+ */
+static struct dircache_entry *bftw_add(struct bftw_state *state, const char *name) {
+	struct dircache_entry *entry = dircache_add(&state->cache, state->current, name);
+	if (!entry) {
+		return NULL;
+	}
+
+	if (state->flags & BFTW_DETECT_CYCLES) {
+		const struct stat *statbuf = state->ftwbuf.statbuf;
+		if (statbuf) {
+			entry->dev = statbuf->st_dev;
+			entry->ino = statbuf->st_ino;
+		}
+	}
+
+	return entry;
+}
+
+/**
  * Push a new entry onto the queue.
  */
 static int bftw_push(struct bftw_state *state, const char *name) {
-	struct dircache_entry *entry = dircache_add(&state->cache, state->current, name);
+	struct dircache_entry *entry = bftw_add(state, name);
 	if (!entry) {
 		return -1;
 	}
@@ -791,7 +835,7 @@ int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void
 
 	// Now start the breadth-first search
 
-	state.current = dircache_add(&state.cache, NULL, path);
+	state.current = bftw_add(&state, path);
 	if (!state.current) {
 		goto fail;
 	}
@@ -803,10 +847,10 @@ int bftw(const char *path, bftw_fn *fn, int nopenfd, enum bftw_flags flags, void
 
 		DIR *dir = dircache_entry_open(&state.cache, state.current, state.path.str);
 		if (!dir) {
-			state.error = errno;
+			int error = errno;
 
 			bftw_init_buffers(&state, NULL);
-			ftwbuf_set_error(&state.ftwbuf, state.error);
+			bftw_set_error(&state, error);
 
 			switch (bftw_handle_path(&state)) {
 			case BFTW_CONTINUE:
diff --git a/bftw.h b/bftw.h
index 4b81123..6f6108b 100644
--- a/bftw.h
+++ b/bftw.h
@@ -105,13 +105,19 @@ typedef enum bftw_action bftw_fn(struct BFTW *ftwbuf, void *ptr);
  */
 enum bftw_flags {
 	/** stat() each encountered file. */
-	BFTW_STAT        = 1 << 0,
+	BFTW_STAT           = 1 << 0,
 	/** Attempt to recover from encountered errors. */
-	BFTW_RECOVER     = 1 << 1,
+	BFTW_RECOVER        = 1 << 1,
 	/** Visit directories in post-order as well as pre-order. */
-	BFTW_DEPTH       = 1 << 2,
+	BFTW_DEPTH          = 1 << 2,
 	/** If the initial path is a symbolic link, follow it. */
-	BFTW_FOLLOW_ROOT = 1 << 3,
+	BFTW_FOLLOW_ROOT    = 1 << 3,
+	/** Follow non-root symbolic links. */
+	BFTW_FOLLOW_NONROOT = 1 << 4,
+	/** Follow all symbolic links. */
+	BFTW_FOLLOW         = BFTW_FOLLOW_ROOT | BFTW_FOLLOW_NONROOT,
+	/** Detect directory cycles. */
+	BFTW_DETECT_CYCLES  = 1 << 5,
 };
 
 /**
diff --git a/parse.c b/parse.c
index 93657c8..4613aed 100644
--- a/parse.c
+++ b/parse.c
@@ -345,7 +345,7 @@ static struct expr *parse_acnewer(struct parser_state *state, const char *option
 
 	struct stat sb;
 
-	bool follow = state->cl->flags & BFTW_FOLLOW_ROOT;
+	bool follow = state->cl->flags & BFTW_FOLLOW;
 	int flags = follow ? 0 : AT_SYMLINK_NOFOLLOW;
 
 	if (fstatat(AT_FDCWD, expr->sdata, &sb, flags) != 0) {
@@ -471,18 +471,26 @@ static struct expr *parse_literal(struct parser_state *state) {
 	switch (arg[1]) {
 	case 'P':
 		if (strcmp(arg, "-P") == 0) {
-			state->cl->flags &= ~BFTW_FOLLOW_ROOT;
+			state->cl->flags &= ~(BFTW_FOLLOW | BFTW_DETECT_CYCLES);
 			return new_option(state, arg);
 		}
 		break;
 
 	case 'H':
 		if (strcmp(arg, "-H") == 0) {
+			state->cl->flags &= ~(BFTW_FOLLOW_NONROOT | BFTW_DETECT_CYCLES);
 			state->cl->flags |= BFTW_FOLLOW_ROOT;
 			return new_option(state, arg);
 		}
 		break;
 
+	case 'L':
+		if (strcmp(arg, "-L") == 0) {
+			state->cl->flags |= BFTW_FOLLOW | BFTW_DETECT_CYCLES;
+			return new_option(state, arg);
+		}
+		break;
+
 	case 'a':
 		if (strcmp(arg, "-amin") == 0) {
 			return parse_acmtime(state, arg, ATIME, MINUTES);
@@ -529,6 +537,9 @@ static struct expr *parse_literal(struct parser_state *state) {
 	case 'f':
 		if (strcmp(arg, "-false") == 0) {
 			return &expr_false;
+		} else if (strcmp(arg, "-follow") == 0) {
+			state->cl->flags |= BFTW_FOLLOW | BFTW_DETECT_CYCLES;
+			return new_option(state, arg);
 		}
 		break;
 
diff --git a/tests.sh b/tests.sh
index 493bfab..8c8c347 100755
--- a/tests.sh
+++ b/tests.sh
@@ -33,10 +33,10 @@ function links_structure() {
     touchp "$1/a"
     ln -s a "$1/b"
     ln "$1/a" "$1/c"
-    mkdir -p "$1/d/e"
-    ln -s ../../d "$1/d/e/f"
-    touchp "$1/d/e/g"
-    ln -s q "$1/d/e/h"
+    mkdir -p "$1/d/e/f"
+    ln -s ../../d "$1/d/e/g"
+    ln -s d/e "$1/h"
+    ln -s q "$1/d/e/i"
 }
 
 # Checks for any (order-independent) differences between bfs and find
@@ -171,10 +171,25 @@ function test_0023() {
 
 function test_0024() {
     links_structure "$1"
-    find_diff -H "$1/d/e/h"
+    find_diff -H "$1/d/e/i"
 }
 
-for i in {1..24}; do
+function test_0025() {
+    links_structure "$1"
+    find_diff -L "$1" 2>/dev/null
+}
+
+function test_0026() {
+    links_structure "$1"
+    find_diff "$1" -follow 2>/dev/null
+}
+
+function test_0027() {
+    links_structure "$1"
+    find_diff -L "$1" -depth 2>/dev/null
+}
+
+for i in {1..27}; do
     dir="$(mktemp -d "${TMPDIR:-/tmp}"/bfs.XXXXXXXXXX)"
     test="test_$(printf '%04d' $i)"
     "$test" "$dir"