glob

commit 57ff969ae4100c65304e53a045b062270cb38756
parent 5722be886a1886244a5bd3c5a66f38673607e53f
Author: Louis Burda <quent.burda@gmail.com>
Date:   Fri, 21 Jun 2024 18:19:39 +0200

Fix matching algorithm and add -a flag

Diffstat:
M
Makefile
 | 
2
+-
M
glob.c
 | 
205
++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------------

2 files changed, 148 insertions(+), 59 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,7 @@
 PREFIX ?= /usr/local
 BINDIR ?= /bin
 
-CFLAGS = -Wunused-variable -Wunused-function -Wconversion
+CFLAGS += -Wunused-variable -Wunused-function -Wconversion
 
 all: glob
 
diff --git a/glob.c b/glob.c
@@ -1,27 +1,44 @@
-#include <limits.h>
-#include <errno.h>
-#include <dirent.h>
-#include <fcntl.h>
+#include <sys/stat.h>
 #include <linux/limits.h>
 #include <sys/types.h>
+#include <dirent.h>
+#include <fcntl.h>
 #include <unistd.h>
+
+#include <errno.h>
 #include <string.h>
 #include <stdio.h>
-#include <stdint.h>
 #include <stdbool.h>
-#include <stdlib.h>
 
-static char *
-esc_strchr(const char *esc, char c)
-{
-	const char *e;
+static bool show_hidden = false;
 
-	for (e = esc; *e; e++) {
-		if (*e == '\\') e++;
-		else if (*e == c) return (char *) e;
+static void glob_r(int fd, char *buf, size_t off, size_t cap, const char *pat);
+
+static bool
+append(char *path, const char *component, size_t *len, size_t cap, size_t off, bool final)
+{
+	if (*len + !final + 1 > cap - off) {
+		fprintf(stderr, "glob: len > PATH_MAX\n");
+		return false;
 	}
+	strncpy(path + off, component, *len);
+	while (*len > 0 && path[off+*len-1] == '/')
+		(*len)--;
+	if (!final) path[off+(*len)++] = '/';
+	path[off+*len] = '\0';
+	return true;
+}
 
-	return NULL;
+static int
+opendirat(int pfd, const char *full, const char *child)
+{
+	int fd = openat(pfd, child, O_DIRECTORY);
+	if (fd < 0) {
+		fprintf(stderr, "glob: openat '%s': %s\n",
+			full, strerror(errno));
+		return -1;
+	}
+	return fd;
 }
 
 static bool
@@ -31,7 +48,7 @@ esc_strcmp(const char **esc, const char **str, const char *except)
 
 	for (e = *esc, s = *str; *s && *e; s++, e++) {
 		if (*e == '\\') e++;
-		else if (strchr(except, *e)) break;
+		else if (strchr(except, *e)) return true;
 		if (*s != *e) return false;
 	}
 	*esc = e;
@@ -73,43 +90,80 @@ match(const char *pat, const char *str)
 	return true;
 }
 
+static bool
+addprefix(char *buf, const char *pat, size_t cap,
+	size_t off, size_t *consumed, size_t *added)
+{
+	const char *slash;
+	const char *star;
+	const char *tok;
+	size_t len;
+
+	*added = *consumed = 0;
+
+	star = strchr(pat, '*');
+	if (!star) {
+		*consumed = *added = strlen(pat);
+		return append(buf, pat, added, cap, off, true);
+	}
+
+	slash = strchr(pat, '/');
+	if (!slash || slash > star)
+		return true;
+
+	tok = pat;
+	do {
+		len = (size_t) (slash + 1 - tok);
+		*consumed += len;
+		if (slash == pat || len > 1) {
+			if (!append(buf, tok, &len, cap, off + *added, !slash))
+				return false;
+			*added += len;
+		}
+		tok = slash + 1;
+		slash = strchr(slash + 1, '/');
+	} while (slash && slash < star);
+
+	return true;
+}
+
 static void
-glob_r(int fd, char *buf, size_t off, size_t n, const char *pat)
+glob_r_match(int fd, char *buf, size_t off, size_t cap, const char *pat)
 {
+	const char *slash;
 	struct dirent *ent;
+	DIR *d;
 	size_t len;
-	char *sep;
 	int sfd;
-	DIR *d;
 
-	d = fdopendir(fd);
-	if (!d) return;
+	if (!(d = fdopendir(fd))) {
+		fprintf(stderr, "glob: opendir '%s': %s\n",
+			*buf ? buf : ".", strerror(errno));
+		return;
+	}
 
-	sep = esc_strchr(pat, '/');
+	slash = strchr(pat, '/');
 	while ((ent = readdir(d))) {
 		if (!strcmp(ent->d_name, ".")) continue;
 		if (!strcmp(ent->d_name, "..")) continue;
-		if (match(pat, ent->d_name)) {
-			if (sep && ent->d_type == DT_DIR) {
-				sfd = openat(fd, ent->d_name, O_DIRECTORY);
-				if (sfd < 0) {
-					fprintf(stderr, "glob: openat '%s%s': %s\n",
-						buf, ent->d_name, strerror(errno));
-					continue;
-				}
-				len = strlen(ent->d_name);
-				if (len + 2 > n - off) {
-					fprintf(stderr, "glob: len > PATH_MAX\n");
-					exit(1);
-				}
-				strcpy(buf + off, ent->d_name);
-				strcpy(buf + off + len, "/");
-				glob_r(sfd, buf, off + len + 1, n, sep + 1);
-				close(sfd);
-			} else {
-				fputs(buf, stdout);
-				puts(ent->d_name);
-			}
+
+		if (*ent->d_name == '.' && !show_hidden) continue;
+
+		if (!match(pat, ent->d_name)) continue;
+
+		if (slash && ent->d_type == DT_DIR) {
+			len = strlen(ent->d_name);
+			if (!append(buf, ent->d_name, &len, cap, off, false))
+				continue;
+			if ((sfd = opendirat(fd, buf, ent->d_name)) < 0)
+				continue;
+			glob_r(sfd, buf, off + len, cap, slash + 1);
+			close(sfd);
+		} else if (!slash) {
+			len = strlen(ent->d_name);
+			if (!append(buf, ent->d_name, &len, cap, off, true))
+				continue;
+			puts(buf);
 		}
 	}
 
@@ -117,31 +171,66 @@ glob_r(int fd, char *buf, size_t off, size_t n, const char *pat)
 }
 
 static void
-glob(const char *pat)
+glob_r(int fd, char *buf, size_t off, size_t cap, const char *pat)
+{
+	struct stat stat;
+	size_t plen;
+	size_t len;
+	int sfd;
+
+	if (!addprefix(buf, pat, cap, off, &plen, &len))
+		return;
+
+	if (len) {
+		if (!pat[plen]) {
+			if (!fstatat(fd, buf + off, &stat, 0)) {
+				puts(buf);
+			}
+		} else {
+			if ((sfd = opendirat(fd, buf, buf + off)) < 0)
+				return;
+			glob_r_match(sfd, buf, off + len, cap, pat + plen);
+			close(sfd);
+		}
+	} else {
+		glob_r_match(fd, buf, off, cap, pat + plen);
+	}
+}
+
+static void
+glob(char *pat)
 {
 	char buf[PATH_MAX];
-	const char *dirname;
-	int fd;
+	char *end;
 
 	buf[0] = '\0';
-	dirname = pat[0] == '/' ? "/" : ".";
-	fd = open(dirname, O_DIRECTORY);
-	if (fd < 0) {
-		fprintf(stderr, "glob: open '%s': %s\n",
-			dirname, strerror(errno));
-		exit(1);
-	}
-	glob_r(fd, buf, 0, PATH_MAX, pat);
-	close(fd);
+
+	end = pat + strlen(pat);
+	while (end > pat && end[-1] == '/')
+		end--;
+	*end = '\0';
+
+	glob_r(AT_FDCWD, buf, 0, PATH_MAX, pat);
 }
 
 int
-main(int argc, const char **argv)
+main(int argc, char **argv)
 {
-	const char **arg;
+	char **arg;
 
 	if (!argc) return 1;
 
-	for (arg = argv + 1; *arg; arg++)
-		glob(*arg);
+	for (arg = argv + 1; *arg; arg++) {
+		if (!strcmp(*arg, "-h")) {
+			printf("Usage: glob [-h] [-a]\n");
+			return 0;
+		} else if (!strcmp(*arg, "-a")) {
+			show_hidden = true;
+		} else {
+			if (!strcmp(*arg, "--")) arg++;
+			break;
+		}
+	}
+
+	for (; *arg; arg++) glob(*arg);
 }