From 55d1186ed64c35b27f7a6acae2821b81c648c377 Mon Sep 17 00:00:00 2001 From: Jon Marius Venstad Date: Fri, 8 Apr 2022 11:44:56 +0200 Subject: Constant time append to Path as well, and add length() --- .../vespa/config/server/http/ContentHandler.java | 2 +- .../src/main/java/com/yahoo/restapi/Path.java | 11 +-- .../hosted/controller/proxy/ProxyRequest.java | 6 +- .../restapi/application/ServiceApiResponse.java | 4 +- .../configserver/ConfigServerApiHandler.java | 2 +- vespajlib/src/main/java/ai/vespa/http/HttpURL.java | 100 ++++++++++++++------- .../src/test/java/ai/vespa/http/HttpURLTest.java | 3 +- 7 files changed, 85 insertions(+), 43 deletions(-) diff --git a/configserver/src/main/java/com/yahoo/vespa/config/server/http/ContentHandler.java b/configserver/src/main/java/com/yahoo/vespa/config/server/http/ContentHandler.java index 2989eee0b55..7aa9e0aa92c 100644 --- a/configserver/src/main/java/com/yahoo/vespa/config/server/http/ContentHandler.java +++ b/configserver/src/main/java/com/yahoo/vespa/config/server/http/ContentHandler.java @@ -63,7 +63,7 @@ public class ContentHandler { } private static List listSortedFiles(ApplicationFile file, Path path, boolean recursive) { - if ( ! path.segments().isEmpty() && ! path.hasTrailingSlash()) { + if (path.length() > 0 && ! path.hasTrailingSlash()) { return List.of(file); } List files = file.listFiles(recursive); diff --git a/container-core/src/main/java/com/yahoo/restapi/Path.java b/container-core/src/main/java/com/yahoo/restapi/Path.java index 40f281a948e..80f9391fb56 100644 --- a/container-core/src/main/java/com/yahoo/restapi/Path.java +++ b/container-core/src/main/java/com/yahoo/restapi/Path.java @@ -56,16 +56,17 @@ public class Path { } if (matchPrefix) { - if (path.segments().size() < specElements.size()) return false; + if (path.length() < specElements.size()) return false; } else { // match exact - if (path.segments().size() != specElements.size()) return false; + if (path.length() != specElements.size()) return false; } - + + List segments = path.segments(); for (int i = 0; i < specElements.size(); i++) { if (specElements.get(i).startsWith("{") && specElements.get(i).endsWith("}")) // placeholder - values.put(specElements.get(i).substring(1, specElements.get(i).length() - 1), path.segments().get(i)); - else if ( ! specElements.get(i).equals(path.segments().get(i))) + values.put(specElements.get(i).substring(1, specElements.get(i).length() - 1), segments.get(i)); + else if ( ! specElements.get(i).equals(segments.get(i))) return false; } diff --git a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/proxy/ProxyRequest.java b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/proxy/ProxyRequest.java index 8b89c2300e4..79f0088a214 100644 --- a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/proxy/ProxyRequest.java +++ b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/proxy/ProxyRequest.java @@ -33,8 +33,8 @@ public class ProxyRequest { ProxyRequest(Method method, URI uri, Map> headers, InputStream body, List targets, Path path) { this.requestUri = HttpURL.from(uri); - if ( requestUri.path().segments().size() < path.segments().size() - || ! requestUri.path().tail(path.segments().size()).equals(path)) { + if ( requestUri.path().length() < path.length() + || ! requestUri.path().tail(path.length()).equals(path)) { throw new IllegalArgumentException(Text.format("Request %s does not end with proxy %s", requestUri.path(), path)); } if (targets.isEmpty()) { @@ -69,7 +69,7 @@ public class ProxyRequest { } public URI getControllerPrefixUri() { - Path prefixPath = requestUri.path().cut(targetPath.segments().size()).withTrailingSlash(); + Path prefixPath = requestUri.path().cut(targetPath.length()).withTrailingSlash(); return requestUri.withPath(prefixPath).withQuery(Query.empty()).asURI(); } diff --git a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/application/ServiceApiResponse.java b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/application/ServiceApiResponse.java index 41d891a0987..67b47aa976a 100644 --- a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/application/ServiceApiResponse.java +++ b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/application/ServiceApiResponse.java @@ -173,8 +173,8 @@ class ServiceApiResponse extends HttpResponse { private HttpURL generateLocalLinkPrefix(String identifier, Path restPath) { Path proxiedPath = Path.parse(identifier).append(restPath); - if (requestUri.path().tail(proxiedPath.segments().size()).equals(proxiedPath)) { - return requestUri.withPath(requestUri.path().cut(proxiedPath.segments().size())); + if (requestUri.path().tail(proxiedPath.length()).equals(proxiedPath)) { + return requestUri.withPath(requestUri.path().cut(proxiedPath.length())); } else { throw new IllegalStateException("Expected the resource " + requestUri.path() + " to end with " + proxiedPath); } diff --git a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/configserver/ConfigServerApiHandler.java b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/configserver/ConfigServerApiHandler.java index 99632203645..8caa741d737 100644 --- a/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/configserver/ConfigServerApiHandler.java +++ b/controller-server/src/main/java/com/yahoo/vespa/hosted/controller/restapi/configserver/ConfigServerApiHandler.java @@ -94,7 +94,7 @@ public class ConfigServerApiHandler extends AuditLoggingRequestHandler { throw new IllegalArgumentException("No such zone: " + zoneId.value()); } - if (path.getRest().segments().size() < 2 || ! WHITELISTED_APIS.contains(path.getRest().head(2).withTrailingSlash())) { + if (path.getRest().length() < 2 || ! WHITELISTED_APIS.contains(path.getRest().head(2).withTrailingSlash())) { return ErrorResponse.forbidden("Cannot access " + path.getRest() + " through /configserver/v1, following APIs are permitted: " + WHITELISTED_APIS.stream() .map(p -> "/" + String.join("/", p.segments()) + "/") diff --git a/vespajlib/src/main/java/ai/vespa/http/HttpURL.java b/vespajlib/src/main/java/ai/vespa/http/HttpURL.java index 22fe4adff27..5527d877a17 100644 --- a/vespajlib/src/main/java/ai/vespa/http/HttpURL.java +++ b/vespajlib/src/main/java/ai/vespa/http/HttpURL.java @@ -199,14 +199,28 @@ public class HttpURL { public static class Path { + private static class Node { + + final Node next; + final String value; + + Node(Node next, String value) { + this.next = next; + this.value = value; + } + + } + private static final Path empty = empty(HttpURL::requirePathSegment); - private final List segments; + private final Node head; + private final int length; private final boolean trailingSlash; private final UnaryOperator validator; - private Path(List segments, boolean trailingSlash, UnaryOperator validator) { - this.segments = requireNonNull(segments); + private Path(Node head, int length, boolean trailingSlash, UnaryOperator validator) { + this.head = head; + this.length = length; this.trailingSlash = trailingSlash; this.validator = requireNonNull(validator); } @@ -218,7 +232,7 @@ public class HttpURL { /** Creates a new, empty path, with a trailing slash, using the indicated validator for segments. */ public static Path empty(Consumer validator) { - return new Path(List.of(), true, segmentValidator(validator)); + return new Path(null, 0, true, segmentValidator(validator)); } /** Parses the given raw, normalized path string; this ignores whether the path is absolute or relative. */ @@ -228,13 +242,12 @@ public class HttpURL { /** Parses the given raw, normalized path string; this ignores whether the path is absolute or relative.) */ public static Path parse(String raw, Consumer validator) { - Path base = new Path(List.of(), raw.endsWith("/"), segmentValidator(validator)); + Path path = new Path(null, 0, raw.endsWith("/"), segmentValidator(validator)); if (raw.startsWith("/")) raw = raw.substring(1); - if (raw.isEmpty()) return base; - List segments = new ArrayList<>(); - for (String segment : raw.split("/")) segments.add(decode(segment, UTF_8)); - if (segments.isEmpty()) requireNonNormalizable(""); // Raw path was only slashes. - return base.append(segments); + if (raw.isEmpty()) return path; + for (String segment : raw.split("/")) path = path.append(decode(segment, UTF_8)); + if (path.length == 0) requireNonNormalizable(""); // Raw path was only slashes. + return path; } private static UnaryOperator segmentValidator(Consumer validator) { @@ -253,22 +266,34 @@ public class HttpURL { /** Returns a copy of this where only the first segments are retained, and with a trailing slash. */ public Path head(int count) { - return count == segments.size() ? this : new Path(segments.subList(0, count), true, validator); + requireInRange(count, "head count", 0, length); + Node node = head; + for (int i = count; i < length; i++) + node = node.next; + + return new Path(node, count, true, validator); } /** Returns a copy of this where only the last segments are retained. */ public Path tail(int count) { - return count == segments.size() ? this : new Path(segments.subList(segments.size() - count, segments.size()), trailingSlash, validator); + requireInRange(count, "tail count", 0, length); + return count == length ? this : new Path(head, count, trailingSlash, validator); } /** Returns a copy of this where the first segments are skipped. */ public Path skip(int count) { - return count == 0 ? this : new Path(segments.subList(count, segments.size()), trailingSlash, validator); + requireInRange(count, "skip count", 0, length); + return count == 0 ? this : new Path(head, length - count, trailingSlash, validator); } /** Returns a copy of this where the last segments are cut off, and with a trailing slash. */ public Path cut(int count) { - return count == 0 ? this : new Path(segments.subList(0, segments.size() - count), true, validator); + requireInRange(count, "cut count", 0, length); + Node node = head; + for (int i = 0; i < count; i++) + node = node.next; + + return new Path(node, length - count, true, validator); } /** Returns a copy of this with the decoded segment appended at the end; it may not be either of {@code ""}, {@code "."} or {@code ".."}. */ @@ -278,7 +303,7 @@ public class HttpURL { /** Returns a copy of this all segments of the other path appended, with a trailing slash as per the appendage. */ public Path append(Path other) { - return append(other.segments, other.trailingSlash); + return append(other.segments(), other.trailingSlash); } /** Returns a copy of this all given segments appended, with a trailing slash as per this path. */ @@ -286,10 +311,14 @@ public class HttpURL { return append(segments, trailingSlash); } - private Path append(List segments, boolean trailingSlash) { - List copy = new ArrayList<>(this.segments); - for (String segment : segments) copy.add(validator.apply(segment)); - return new Path(copy, trailingSlash, validator); + private Path append(Iterable segments, boolean trailingSlash) { + Node node = head; + int count = 0; + for (String segment : segments) { + node = new Node(node, validator.apply(segment)); + count++; + } + return new Path(node, length + count, trailingSlash, validator); } /** Whether this path has a trailing slash. */ @@ -299,23 +328,34 @@ public class HttpURL { /** Returns a copy of this which encodes a trailing slash. */ public Path withTrailingSlash() { - return new Path(segments, true, validator); + return new Path(head, length, true, validator); } /** Returns a copy of this which does not encode a trailing slash. */ public Path withoutTrailingSlash() { - return new Path(segments, false, validator); + return new Path(head, length, false, validator); } - /** The URL decoded segments that make up this path; never {@code null}, {@code ""}, {@code "."} or {@code ".."}. */ + /** A mutable copy of the URL decoded segments that make up this path; never {@code null}, {@code ""}, {@code "."} or {@code ".."}. */ public List segments() { - return Collections.unmodifiableList(segments); + ArrayList list = new ArrayList<>(length); + for (int i = 0; i < length; i++) list.add(null); + Node node = head; + for (int i = length; i-- > 0; node = node.next) + list.set(i, node.value); + + return list; + } + + /** The number of segments in this path. */ + public int length() { + return length; } /** A raw path string which parses to this, by splitting on {@code "/"}, and then URL decoding. */ private String raw() { StringJoiner joiner = new StringJoiner("/", "/", trailingSlash ? "/" : "").setEmptyValue(trailingSlash ? "/" : ""); - for (String segment : segments) joiner.add(encode(segment, UTF_8)); + for (String segment : segments()) joiner.add(encode(segment, UTF_8)); return joiner.toString(); } @@ -330,12 +370,12 @@ public class HttpURL { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Path path = (Path) o; - return trailingSlash == path.trailingSlash && segments.equals(path.segments); + return trailingSlash == path.trailingSlash && segments().equals(path.segments()); } @Override public int hashCode() { - return Objects.hash(segments, trailingSlash); + return Objects.hash(segments(), trailingSlash); } } @@ -466,8 +506,8 @@ public class HttpURL { } /** - * The URL decoded key-value pairs that make up this query; - * keys and values may be {@code ""}, and values are {@code null} when only key was specified. + * A mutable copy of the URL decoded key-value pairs that make up this query. + * Keys and values may be {@code ""}, and values are {@code null} when only key was specified. * When a key was used multiple times, this map contains only the last value associated with the key. */ public Map lastEntries() { @@ -479,8 +519,8 @@ public class HttpURL { } /** - * The URL decoded key-value pairs that make up this query; - * keys and values may be {@code ""}, and values (not lists of values) are {@code null} when only key was specified. + * A mutable copy of the URL decoded key-value pairs that make up this query. + * Keys and values may be {@code ""}, and values (not lists of values) are {@code null} when only key was specified. * When a key was used multiple times, this map lists the values in the same order as they were given. */ public Map> entries() { diff --git a/vespajlib/src/test/java/ai/vespa/http/HttpURLTest.java b/vespajlib/src/test/java/ai/vespa/http/HttpURLTest.java index 409daaabc13..8e3029009b0 100644 --- a/vespajlib/src/test/java/ai/vespa/http/HttpURLTest.java +++ b/vespajlib/src/test/java/ai/vespa/http/HttpURLTest.java @@ -8,6 +8,7 @@ import org.junit.jupiter.api.Test; import java.net.URI; import java.util.ArrayList; +import java.util.HashSet; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; @@ -141,7 +142,7 @@ class HttpURLTest { assertThrows(IllegalArgumentException.class, () -> path.append("???")).getMessage()); - assertEquals("fromIndex(2) > toIndex(1)", + assertEquals("skip count must be at least '0' and at most '1', but got: '2'", assertThrows(IllegalArgumentException.class, () -> path.cut(2).skip(2)).getMessage()); -- cgit v1.2.3