From 6e5a5a3b27257f212fcd10a3580cfca3ea224fab Mon Sep 17 00:00:00 2001
From: dzwdz
Date: Wed, 4 Aug 2021 12:27:02 +0200
Subject: partial path_simplify implementation

it currently only checks if the path is valid, it's the bare minimum
needed to write tests
---
 src/kernel/tests/main.c  |  1 +
 src/kernel/tests/tests.h |  1 +
 src/kernel/tests/vfs.c   | 35 +++++++++++++++++++++++++++++++++++
 src/kernel/vfs/path.c    | 44 ++++++++++++++++++++++++++++++++++++++++++++
 src/kernel/vfs/path.h    | 11 +++++++++++
 5 files changed, 92 insertions(+)
 create mode 100644 src/kernel/tests/vfs.c
 create mode 100644 src/kernel/vfs/path.c
 create mode 100644 src/kernel/vfs/path.h

diff --git a/src/kernel/tests/main.c b/src/kernel/tests/main.c
index 8e5842b..db4363f 100644
--- a/src/kernel/tests/main.c
+++ b/src/kernel/tests/main.c
@@ -8,6 +8,7 @@ void tests_all() {
 	_did_tests_fail = false;
 
 	tests_utils();
+	tests_vfs();
 
 	if (_did_tests_fail)
 		panic();
diff --git a/src/kernel/tests/tests.h b/src/kernel/tests/tests.h
index 78397da..5b9697c 100644
--- a/src/kernel/tests/tests.h
+++ b/src/kernel/tests/tests.h
@@ -3,3 +3,4 @@
 void tests_all();
 
 void tests_utils();
+void tests_vfs();
diff --git a/src/kernel/tests/vfs.c b/src/kernel/tests/vfs.c
new file mode 100644
index 0000000..a5a6848
--- /dev/null
+++ b/src/kernel/tests/vfs.c
@@ -0,0 +1,35 @@
+#include <kernel/tests/base.h>
+#include <kernel/util.h>
+#include <kernel/vfs/path.h>
+
+TEST(path_simplify) {
+	char buf[256];
+
+	// some easy valid cases
+	TEST_COND( path_simplify("/asdf", buf, 5));
+	TEST_COND( path_simplify("/asd/", buf, 5));
+	TEST_COND( path_simplify("/a/./", buf, 5));
+	TEST_COND( path_simplify("/a/..", buf, 5));
+	TEST_COND( path_simplify("/a//.", buf, 5));
+
+	// .. going under the root or close to it
+	TEST_COND(!path_simplify("/../123456", buf, 10));
+	TEST_COND(!path_simplify("/./a/../..", buf, 10));
+	TEST_COND( path_simplify("/a/a/../..", buf, 10));
+	TEST_COND(!path_simplify("/////../..", buf, 10));
+	TEST_COND(!path_simplify("//a//../..", buf, 10));
+
+	// relative paths aren't allowed
+	TEST_COND(!path_simplify("apath", buf, 5));
+	TEST_COND(!path_simplify("a/pth", buf, 5));
+	TEST_COND(!path_simplify("../th", buf, 5));
+
+	// this includes empty paths
+	TEST_COND(!path_simplify("", buf, 1));
+
+	// TODO test if the paths are simplified correctly
+}
+
+void tests_vfs() {
+	TEST_RUN(path_simplify);
+}
diff --git a/src/kernel/vfs/path.c b/src/kernel/vfs/path.c
new file mode 100644
index 0000000..8662f03
--- /dev/null
+++ b/src/kernel/vfs/path.c
@@ -0,0 +1,44 @@
+#include <kernel/vfs/path.h>
+#include <kernel/panic.h>
+
+bool path_simplify(const char *in, char *out, size_t len) {
+	if (len == 0)     return false; // empty paths are invalid
+	if (in[0] != '/') return false; // so are relative paths
+
+	int depth = 0;
+	int seg_len; // the length of the current path segment
+
+	for (int i = 0; i < len; i += seg_len + 1) {
+		// TODO implement assert
+		if (in[i] != '/') panic();
+
+		seg_len = 0;
+		for (int j = i + 1; j < len; j++) {
+			if (in[j] == '/') break;
+			seg_len++;
+		}
+
+		/* example iteration, illustrated with terrible ASCII art
+		 *
+		 *          |i=5 |next i = i + seg_len + 1 = 10
+		 *          v    v
+		 *     /some/path/asdf
+		 *           |--|
+		 *           seg_len = 4
+		 *           (segment starts at i+1) */
+
+		if (seg_len == 0 || (seg_len == 1 && in[i + 1] == '.')) {
+			// the segment is // or /./
+			// the depth doesn't change
+		} else if (seg_len == 2 && in[i + 1] == '.' && in[i + 2] == '.') {
+			// the segment is /../
+			if (--depth < 0)
+				return false;
+		} else {
+			// normal segment
+			depth++;
+		}
+	}
+
+	return true;
+}
diff --git a/src/kernel/vfs/path.h b/src/kernel/vfs/path.h
new file mode 100644
index 0000000..22dc754
--- /dev/null
+++ b/src/kernel/vfs/path.h
@@ -0,0 +1,11 @@
+#pragma once
+#include <stdbool.h>
+#include <stddef.h>
+
+/** Reduce a path to its simplest form.
+ * *in and *out can't overlap unless they're equal. Then, the path is modified
+ * in-place.
+ *
+ * @return Was the path valid? If this is false, *out is undefined
+ */
+bool path_simplify(const char *in, char *out, size_t len);
-- 
cgit v1.2.3