Merge branch 'main' into find2fdfind2fd

1 files changed, 145 insertions, 86 deletions

diff --git a/src/dstring.c b/src/dstring.c
index f344d09..b5bf3d3 100644
--- a/src/dstring.c
+++ b/src/dstring.c
@@ -1,147 +1,184 @@
-/****************************************************************************
- * bfs                                                                      *
- * Copyright (C) 2016-2022 Tavian Barnes <tavianator@tavianator.com>        *
- *                                                                          *
- * Permission to use, copy, modify, and/or distribute this software for any *
- * purpose with or without fee is hereby granted.                           *
- *                                                                          *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES *
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF         *
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR  *
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES   *
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN    *
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF  *
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.           *
- ****************************************************************************/
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
 
+#include "prelude.h"
 #include "dstring.h"
-#include <assert.h>
+#include "alloc.h"
+#include "bit.h"
+#include "diag.h"
 #include <stdarg.h>
+#include <stddef.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
 /**
- * The memory representation of a dynamic string.  Users get a pointer to data.
+ * The memory representation of a dynamic string.  Users get a pointer to str.
  */
 struct dstring {
-	size_t capacity;
-	size_t length;
-	char data[];
+	/** Capacity of the string, *including* the terminating NUL. */
+	size_t cap;
+	/** Length of the string, *excluding* the terminating NUL. */
+	size_t len;
+	/** The string itself. */
+	alignas(dchar) char str[];
 };
 
-/** Get the string header from the string data pointer. */
-static struct dstring *dstrheader(const char *dstr) {
-	return (struct dstring *)(dstr - offsetof(struct dstring, data));
+#define DSTR_OFFSET offsetof(struct dstring, str)
+
+/** Back up to the header from a pointer to dstring::str. */
+static struct dstring *dstrheader(const dchar *dstr) {
+	return (struct dstring *)(dstr - DSTR_OFFSET);
 }
 
-/** Get the correct size for a dstring with the given capacity. */
-static size_t dstrsize(size_t capacity) {
-	return BFS_FLEX_SIZEOF(struct dstring, data, capacity + 1);
+/**
+ * In some provenance models, the expression `header->str` has its provenance
+ * restricted to just the `str` field itself, making a future dstrheader()
+ * illegal.  This alternative is guaranteed to preserve provenance for the entire
+ * allocation.
+ *
+ * - https://stackoverflow.com/q/25296019
+ * - https://mastodon.social/@void_friend@tech.lgbt/111144859908104311
+ */
+static dchar *dstrdata(struct dstring *header) {
+	return (char *)header + DSTR_OFFSET;
 }
 
 /** Allocate a dstring with the given contents. */
-static char *dstralloc_impl(size_t capacity, size_t length, const char *data) {
+static dchar *dstralloc_impl(size_t cap, size_t len, const char *str) {
 	// Avoid reallocations for small strings
-	if (capacity < 7) {
-		capacity = 7;
+	if (cap < DSTR_OFFSET) {
+		cap = DSTR_OFFSET;
 	}
 
-	struct dstring *header = malloc(dstrsize(capacity));
+	struct dstring *header = ALLOC_FLEX(struct dstring, str, cap);
 	if (!header) {
 		return NULL;
 	}
 
-	header->capacity = capacity;
-	header->length = length;
+	header->cap = cap;
+	header->len = len;
 
-	memcpy(header->data, data, length);
-	header->data[length] = '\0';
-	return header->data;
+	char *ret = dstrdata(header);
+	memcpy(ret, str, len);
+	ret[len] = '\0';
+	return ret;
 }
 
-char *dstralloc(size_t capacity) {
-	return dstralloc_impl(capacity, 0, "");
+dchar *dstralloc(size_t cap) {
+	return dstralloc_impl(cap + 1, 0, "");
 }
 
-char *dstrdup(const char *str) {
-	size_t len = strlen(str);
-	return dstralloc_impl(len, len, str);
+dchar *dstrdup(const char *str) {
+	return dstrxdup(str, strlen(str));
 }
 
-char *dstrndup(const char *str, size_t n) {
-	size_t len = strnlen(str, n);
-	return dstralloc_impl(len, len, str);
+dchar *dstrndup(const char *str, size_t n) {
+	return dstrxdup(str, strnlen(str, n));
 }
 
-size_t dstrlen(const char *dstr) {
-	return dstrheader(dstr)->length;
+dchar *dstrddup(const dchar *dstr) {
+	return dstrxdup(dstr, dstrlen(dstr));
 }
 
-int dstreserve(char **dstr, size_t capacity) {
-	struct dstring *header = dstrheader(*dstr);
+dchar *dstrxdup(const char *str, size_t len) {
+	return dstralloc_impl(len + 1, len, str);
+}
 
-	if (capacity > header->capacity) {
-		capacity *= 2;
+size_t dstrlen(const dchar *dstr) {
+	return dstrheader(dstr)->len;
+}
 
-		header = realloc(header, dstrsize(capacity));
-		if (!header) {
-			return -1;
-		}
-		header->capacity = capacity;
+int dstreserve(dchar **dstr, size_t cap) {
+	if (!*dstr) {
+		*dstr = dstralloc(cap);
+		return *dstr ? 0 : -1;
+	}
 
-		*dstr = header->data;
+	struct dstring *header = dstrheader(*dstr);
+	size_t old_cap = header->cap;
+	size_t new_cap = cap + 1; // Terminating NUL
+	if (old_cap >= new_cap) {
+		return 0;
 	}
 
+	new_cap = bit_ceil(new_cap);
+	header = REALLOC_FLEX(struct dstring, str, header, old_cap, new_cap);
+	if (!header) {
+		return -1;
+	}
+
+	header->cap = new_cap;
+	*dstr = dstrdata(header);
 	return 0;
 }
 
-int dstresize(char **dstr, size_t length) {
-	if (dstreserve(dstr, length) != 0) {
+int dstresize(dchar **dstr, size_t len) {
+	if (dstreserve(dstr, len) != 0) {
 		return -1;
 	}
 
 	struct dstring *header = dstrheader(*dstr);
-	header->length = length;
-	header->data[length] = '\0';
-
+	header->len = len;
+	header->str[len] = '\0';
 	return 0;
 }
 
-/** Common implementation of dstr{cat,ncat,app}. */
-static int dstrcat_impl(char **dest, const char *src, size_t srclen) {
+int dstrcat(dchar **dest, const char *src) {
+	return dstrxcat(dest, src, strlen(src));
+}
+
+int dstrncat(dchar **dest, const char *src, size_t n) {
+	return dstrxcat(dest, src, strnlen(src, n));
+}
+
+int dstrdcat(dchar **dest, const dchar *src) {
+	return dstrxcat(dest, src, dstrlen(src));
+}
+
+int dstrxcat(dchar **dest, const char *src, size_t len) {
 	size_t oldlen = dstrlen(*dest);
-	size_t newlen = oldlen + srclen;
+	size_t newlen = oldlen + len;
 
 	if (dstresize(dest, newlen) != 0) {
 		return -1;
 	}
 
-	memcpy(*dest + oldlen, src, srclen);
+	memcpy(*dest + oldlen, src, len);
 	return 0;
 }
 
-int dstrcat(char **dest, const char *src) {
-	return dstrcat_impl(dest, src, strlen(src));
+int dstrapp(dchar **str, char c) {
+	return dstrxcat(str, &c, 1);
 }
 
-int dstrncat(char **dest, const char *src, size_t n) {
-	return dstrcat_impl(dest, src, strnlen(src, n));
+int dstrcpy(dchar **dest, const char *src) {
+	return dstrxcpy(dest, src, strlen(src));
 }
 
-int dstrdcat(char **dest, const char *src) {
-	return dstrcat_impl(dest, src, dstrlen(src));
+int dstrncpy(dchar **dest, const char *src, size_t n) {
+	return dstrxcpy(dest, src, strnlen(src, n));
 }
 
-int dstrapp(char **str, char c) {
-	return dstrcat_impl(str, &c, 1);
+int dstrdcpy(dchar **dest, const dchar *src) {
+	return dstrxcpy(dest, src, dstrlen(src));
+}
+
+int dstrxcpy(dchar **dest, const char *src, size_t len) {
+	if (dstresize(dest, len) != 0) {
+		return -1;
+	}
+
+	memcpy(*dest, src, len);
+	return 0;
 }
 
 char *dstrprintf(const char *format, ...) {
 	va_list args;
 
 	va_start(args, format);
-	char *str = dstrvprintf(format, args);
+	dchar *str = dstrvprintf(format, args);
 	va_end(args);
 
 	return str;
@@ -149,7 +186,7 @@ char *dstrprintf(const char *format, ...) {
 
 char *dstrvprintf(const char *format, va_list args) {
 	// Guess a capacity to try to avoid reallocating
-	char *str = dstralloc(2*strlen(format));
+	dchar *str = dstralloc(2 * strlen(format));
 	if (!str) {
 		return NULL;
 	}
@@ -162,7 +199,7 @@ char *dstrvprintf(const char *format, va_list args) {
 	return str;
 }
 
-int dstrcatf(char **str, const char *format, ...) {
+int dstrcatf(dchar **str, const char *format, ...) {
 	va_list args;
 
 	va_start(args, format);
@@ -172,48 +209,70 @@ int dstrcatf(char **str, const char *format, ...) {
 	return ret;
 }
 
-int dstrvcatf(char **str, const char *format, va_list args) {
+int dstrvcatf(dchar **str, const char *format, va_list args) {
 	// Guess a capacity to try to avoid calling vsnprintf() twice
 	size_t len = dstrlen(*str);
-	dstreserve(str, len + 2*strlen(format));
-	size_t cap = dstrheader(*str)->capacity;
+	dstreserve(str, len + 2 * strlen(format));
+	size_t cap = dstrheader(*str)->cap;
 
 	va_list copy;
 	va_copy(copy, args);
 
 	char *tail = *str + len;
-	int ret = vsnprintf(tail, cap - len + 1, format, args);
+	size_t tail_cap = cap - len;
+	int ret = vsnprintf(tail, tail_cap, format, args);
 	if (ret < 0) {
 		goto fail;
 	}
 
 	size_t tail_len = ret;
-	if (tail_len > cap - len) {
-		cap = len + tail_len;
-		if (dstreserve(str, cap) != 0) {
+	if (tail_len >= tail_cap) {
+		if (dstreserve(str, len + tail_len) != 0) {
 			goto fail;
 		}
 
 		tail = *str + len;
 		ret = vsnprintf(tail, tail_len + 1, format, copy);
 		if (ret < 0 || (size_t)ret != tail_len) {
-			assert(!"Length of formatted string changed");
+			bfs_bug("Length of formatted string changed");
 			goto fail;
 		}
 	}
 
 	va_end(copy);
 
-	struct dstring *header = dstrheader(*str);
-	header->length += tail_len;
+	dstrheader(*str)->len += tail_len;
 	return 0;
 
 fail:
+	va_end(copy);
 	*tail = '\0';
 	return -1;
 }
 
-void dstrfree(char *dstr) {
+int dstrescat(dchar **dest, const char *str, enum wesc_flags flags) {
+	return dstrnescat(dest, str, SIZE_MAX, flags);
+}
+
+int dstrnescat(dchar **dest, const char *str, size_t n, enum wesc_flags flags) {
+	size_t len = *dest ? dstrlen(*dest) : 0;
+
+	// Worst case growth is `ccc...` => $'\xCC\xCC\xCC...'
+	n = strnlen(str, n);
+	size_t cap = len + 4 * n + 3;
+	if (dstreserve(dest, cap) != 0) {
+		return -1;
+	}
+
+	char *cur = *dest + len;
+	char *end = *dest + cap + 1;
+	cur = wordnesc(cur, end, str, n, flags);
+	bfs_assert(cur != end, "wordesc() result truncated");
+
+	return dstresize(dest, cur - *dest);
+}
+
+void dstrfree(dchar *dstr) {
 	if (dstr) {
 		free(dstrheader(dstr));
 	}