stack.ha (5170B)
1 // SPDX-License-Identifier: MPL-2.0 2 // (c) Hare authors <https://harelang.org> 3 4 use bytes; 5 use strings; 6 7 // Appends path elements onto the end of a path buffer. 8 // Returns the new string value of the path. 9 export fn push(buf: *buffer, items: str...) (str | error) = { 10 for (let item .. items) { 11 let elem = strings::toutf8(item); 12 13 for (true) match (bytes::index(elem, SEP)) { 14 case void => 15 buf.end = appendnorm(buf, elem)?; 16 break; 17 case let j: size => 18 if (j == 0 && buf.end == 0) { 19 buf.buf[0] = SEP; 20 buf.end = 1; 21 } else { 22 buf.end = appendnorm(buf, elem[..j])?; 23 }; 24 elem = elem[j+1..]; 25 }; 26 }; 27 return string(buf); 28 }; 29 30 const dot: []u8 = ['.']; 31 const dotdot: []u8 = ['.', '.']; 32 33 // append a path segment to a buffer, preserving normalization. 34 // seg must not contain any [[SEP]]s. if you need to make the path absolute, you 35 // should do that manually. returns the new end of the buffer. 36 // x + => x 37 // x + . => x 38 // / + .. => / 39 // + .. => .. 40 // x/.. + .. => x/../.. 41 // x/y + .. => x 42 // x + y => x/y 43 fn appendnorm(buf: *buffer, seg: []u8) (size | error) = { 44 if (len(seg) == 0 || bytes::equal(dot, seg)) return buf.end; 45 if (bytes::equal(dotdot, seg)) { 46 if (isroot(buf)) return buf.end; 47 const isep = match (bytes::rindex(buf.buf[..buf.end], SEP)) { 48 case void => yield 0z; 49 case let i: size => yield i + 1; 50 }; 51 if (buf.end == 0 || bytes::equal(buf.buf[isep..buf.end], dotdot)) { 52 return appendlit(buf, dotdot)?; 53 } else { 54 return if (isep <= 1) isep else isep - 1; 55 }; 56 } else { 57 return appendlit(buf, seg)?; 58 }; 59 }; 60 61 // append a segment to a buffer, *without* preserving normalization. 62 // returns the new end of the buffer 63 fn appendlit(buf: *buffer, bs: []u8) (size | error) = { 64 let newend = buf.end; 65 if (buf.end == 0 || isroot(buf)) { 66 if (MAX < buf.end + len(bs)) return too_long; 67 } else { 68 if (MAX < buf.end + len(bs) + 1) return too_long; 69 buf.buf[buf.end] = SEP; 70 newend += 1; 71 }; 72 buf.buf[newend..newend+len(bs)] = bs; 73 return newend + len(bs); 74 }; 75 76 77 @test fn push() void = { 78 let buf = init()!; 79 assert(string(&buf) == "."); 80 81 // current dir invariants 82 assert(push(&buf, "")! == "."); 83 assert(push(&buf, ".")! == "."); 84 85 // parent dir invariants 86 assert(push(&buf, "..")! == ".."); 87 assert(push(&buf, "")! == ".."); 88 assert(push(&buf, ".")! == ".."); 89 assert(push(&buf, local("/"))! == ".."); 90 91 assert(set(&buf)! == "."); 92 // root dir invariants 93 assert(push(&buf, local("/"))! == local("/")); 94 assert(push(&buf, "")! == local("/")); 95 assert(push(&buf, ".")! == local("/")); 96 assert(push(&buf, "..")! == local("/")); 97 assert(push(&buf, local("/"))! == local("/")); 98 99 assert(set(&buf)! == "."); 100 // regular path and parent 101 assert(push(&buf, "foo")! == "foo"); 102 assert(push(&buf, ".")! == "foo"); 103 assert(push(&buf, local("/"))! == "foo"); 104 assert(push(&buf, "..")! == "."); 105 106 // multiple segments 107 assert(push(&buf, "a", "b")! == local("a/b")); 108 assert(push(&buf, "..", "c")! == local("a/c")); 109 assert(push(&buf, "..")! == "a"); 110 assert(push(&buf, local("/d"))! == local("a/d")); 111 assert(push(&buf, "..", "..")! == "."); 112 113 // multiple segments, absolute 114 assert(push(&buf, local("/"), "a", "b")! == local("/a/b")); 115 assert(push(&buf, "..", "c")! == local("/a/c")); 116 assert(push(&buf, "..")! == local("/a")); 117 assert(push(&buf, local("/d"))! == local("/a/d")); 118 assert(push(&buf, "..", "..", "..")! == local("/")); 119 }; 120 121 // Examine the final path segment in a buffer. 122 // Returns void if the path is empty or is the root dir. 123 export fn peek(buf: *const buffer) (str | void) = split(buf).1; 124 125 // Remove and return the final path segment in a buffer. 126 // Returns void if the path is empty or is the root dir. 127 export fn pop(buf: *buffer) (str | void) = { 128 const (end, res) = split(buf); 129 buf.end = end; 130 return res; 131 }; 132 133 // helper function for pop/peek, returns (new end of buffer, result) 134 fn split(buf: *buffer) (size, (str | void)) = { 135 if (buf.end == 0 || isroot(buf)) return (buf.end, void); 136 match (bytes::rindex(buf.buf[..buf.end], SEP)) { 137 case void => 138 return (0z, strings::fromutf8_unsafe(buf.buf[..buf.end])); 139 case let i: size => 140 return ( 141 if (i == 0) 1z else i, 142 strings::fromutf8_unsafe(buf.buf[i+1..buf.end]), 143 ); 144 }; 145 }; 146 147 @test fn pop() void = { 148 // empty 149 let buf = init()!; 150 assert(pop(&buf) is void); 151 assert(string(&buf) == "."); 152 153 // root dir 154 buf.end = 0; 155 push(&buf, local("/"))!; 156 assert(pop(&buf) is void); 157 assert(string(&buf) == local("/")); 158 159 // relative file 160 buf.end = 0; 161 push(&buf, "foo")!; 162 assert(pop(&buf) as str == "foo"); 163 assert(string(&buf) == "."); 164 165 // abs file 166 buf.end = 0; 167 push(&buf, local("/foo"))!; 168 assert(pop(&buf) as str == "foo"); 169 assert(string(&buf) == local("/")); 170 }; 171 172 // Returns the parent directory for a given path, without modifying the buffer. 173 // If the path is the root directory, the root directory is returned. The value 174 // is either borrowed from the input or statically allocated; use 175 // [[strings::dup]] to extend its lifetime or modify it. 176 export fn parent(buf: *const buffer) (str | error) = { 177 const newend = appendnorm(buf, dotdot)?; 178 if (newend == 0) return "."; 179 return strings::fromutf8_unsafe(buf.buf[..newend]); 180 };