001/*
002 * JGrapes Event Driven Framework
003 * Copyright (C) 2016-2018 Michael N. Lipp
004 * 
005 * This program is free software; you can redistribute it and/or modify it 
006 * under the terms of the GNU Affero General Public License as published by 
007 * the Free Software Foundation; either version 3 of the License, or 
008 * (at your option) any later version.
009 * 
010 * This program is distributed in the hope that it will be useful, but 
011 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
012 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License 
013 * for more details.
014 * 
015 * You should have received a copy of the GNU Affero General Public License along 
016 * with this program; if not, see <http://www.gnu.org/licenses/>.
017 */
018
019package org.jgrapes.http;
020
021import java.net.URI;
022import java.text.ParseException;
023import java.util.ArrayList;
024import java.util.Arrays;
025import java.util.List;
026import java.util.Optional;
027import java.util.Spliterator;
028import java.util.Spliterators.AbstractSpliterator;
029import java.util.StringTokenizer;
030import java.util.function.Consumer;
031import java.util.regex.Matcher;
032import java.util.regex.Pattern;
033import java.util.stream.Collectors;
034import java.util.stream.Stream;
035import java.util.stream.StreamSupport;
036
037/**
038 * A resource pattern can be used to filter URIs. A pattern looks  
039 * similar to a URI (<code>scheme://host:port/path</code>) with the 
040 * following differences:
041 * 
042 *  * The <em>scheme</em> may be a single protocol name or a list
043 *    of protocol names separated by commas, or an asterisk, which is matched
044 *    by URIs with any scheme. The scheme part ({@code scheme://}) is optional 
045 *    in a pattern. Omitting it is equivalent to specifying an asterisk.
046 *    
047 *  * The <em>host</em> may be a host name or an IP address or an asterisk.
048 *    Unless the value is an asterisk, filtered URIs must match the value
049 *    literally.
050 *    
051 *  * The <em>port</em> may be a number or an asterisk.
052 *    Unless the value is an asterisk, filtered URIs must match it.
053 *   
054 *  * Specifying a port ({@code :port}) is optional. If omitted, 
055 *    it is equivalent to specifying an asterisk.
056 *    
057 *  * If the scheme part is omitted, the {@code host:port} part may 
058 *    completely be left out as well, which is
059 *    equivalent to specifying an asterisk for both host and port.
060 *    
061 *  * The optional path part consist of one or more path separated by commas.
062 *  
063 *    Each path consists of a sequence of names and asterisks separated
064 *    by slashes or a vertical bar ("|"). A name must be matched by the 
065 *    corresponding path element of filtered URIs, an asterisk is matched by 
066 *    any corresponding path element (which, however, must exist in the 
067 *    filtered URI). The final element in 
068 *    the path of a pattern may be two asterisks ({@code **}), which matches 
069 *    any remaining path elements in the filtered URI.
070 *    
071 *    Using a vertical bar instead of a slash separates the path in a
072 *    prefix part and the rest. The number of prefix segments is the
073 *    value returned by the match methods.
074 *    
075 *    If a path ends with a vertical bar and the URI matched with the
076 *    path does not end with a slash, a slash is appended to the URI
077 *    before matching. This causes both `/foo` and `/foo/` to match
078 *    a path `/foo|`. This is usually intended. If you do want to
079 *    treat `/foo` as a leaf, specify `/foo,/foo|` in your pattern.
080 *
081 */
082@SuppressWarnings("PMD.GodClass")
083public class ResourcePattern {
084
085    @SuppressWarnings("PMD.AvoidFieldNameMatchingTypeName")
086    private static Pattern resourcePattern = Pattern.compile(
087        "^((?<proto>[^:]+|\\*)://)?" // Optional protocol (2)
088            + "(" // Start of optional host/port part
089            + "(?<host>([^\\[/\\|][^:/\\|]*)|(\\[[^\\]]*\\]))" // Host (4)
090            + "(:(?<port>([0-9]+)|(\\*)))?" // Optional port (8)
091            + ")?" // End of optional host/port
092            + "(?<path>[/\\|].*)?"); // Finally path (11)
093
094    private final String pattern;
095    private final String protocol;
096    private final String host;
097    private final String port;
098    private final String path;
099    private final String[][] pathPatternElements;
100    private int[] prefixSegs;
101
102    /**
103     * Creates a new resource pattern.
104     * 
105     * @param pattern the pattern to be used for matching
106     * @throws ParseException if an invalid pattern is specified
107     */
108    @SuppressWarnings("PMD.AvoidInstantiatingObjectsInLoops")
109    public ResourcePattern(String pattern) throws ParseException {
110        this.pattern = pattern;
111        Matcher rpm = resourcePattern.matcher(pattern);
112        if (!rpm.matches()) {
113            throw new ParseException("Invalid pattern: " + pattern, 0);
114        }
115        protocol = rpm.group("proto");
116        host = rpm.group("host");
117        port = rpm.group("port");
118        path = rpm.group("path");
119        if (path == null) {
120            pathPatternElements = new String[0][];
121        } else {
122            String[] paths = path.split(",");
123            pathPatternElements = new String[paths.length][];
124            prefixSegs = new int[paths.length];
125            for (int i = 0; i < paths.length; i++) {
126                @SuppressWarnings("PMD.AvoidInstantiatingObjectsInLoops")
127                List<String> segs = new ArrayList<>();
128                prefixSegs[i] = 0;
129                StringTokenizer tokenizer = new StringTokenizer(
130                    paths[i], "/|", true);
131                while (tokenizer.hasMoreTokens()) {
132                    String token = tokenizer.nextToken();
133                    switch (token) {
134                    case "/":
135                        continue;
136                    case "|":
137                        prefixSegs[i] = segs.size();
138                        continue;
139                    default:
140                        segs.add(token);
141                        continue;
142                    }
143                }
144                if (paths[i].endsWith("/") || paths[i].endsWith("|")) {
145                    segs.add("");
146                }
147                pathPatternElements[i] = segs.toArray(new String[0]);
148            }
149        }
150    }
151
152    /**
153     * @return the pattern (string) that was used to create this 
154     * resource pattern.
155     */
156    public String pattern() {
157        return pattern;
158    }
159
160    /**
161     * @return the protocol value specified in the pattern or {@code null}
162     */
163    public String protocol() {
164        return protocol;
165    }
166
167    /**
168     * @return the host value specified in the pattern or {@code null}
169     */
170    public String host() {
171        return host;
172    }
173
174    /**
175     * @return the port value specified in the pattern or {@code null}
176     */
177    public String port() {
178        return port;
179    }
180
181    /**
182     * @return the path value specified in the pattern or {@code null}
183     */
184    public String path() {
185        return path;
186    }
187
188    /**
189     * Matches the given resource URI against the pattern.
190     * 
191     * @param resource the URI specifying the resource to match
192     * @return -1 if the resource does not match, else the number
193     * of prefix segments (which may be 0)
194     */
195    @SuppressWarnings({ "PMD.CyclomaticComplexity", "PMD.NPathComplexity",
196        "PMD.CollapsibleIfStatements", "PMD.DataflowAnomalyAnalysis" })
197    public int matches(URI resource) {
198        return matches(resource, Integer.MAX_VALUE);
199    }
200
201    /**
202     * Matches the given resource URI against the pattern, comparing
203     * at most the given number of path segments.
204     *
205     * @param resource the URI specifying the resource to match
206     * @param pathSegs the maximum number of path segments to compare
207     * @return -1 if the resource does not match, else the number
208     * of prefix segments (which may be 0)
209     */
210    @SuppressWarnings({ "PMD.CyclomaticComplexity", "PMD.NPathComplexity",
211        "PMD.CollapsibleIfStatements", "PMD.DataflowAnomalyAnalysis" })
212    public int matches(URI resource, int pathSegs) {
213        if (protocol != null && !protocol.equals("*")) {
214            if (resource.getScheme() == null) {
215                return -1;
216            }
217            if (Arrays.stream(protocol.split(","))
218                .noneMatch(proto -> proto.equals(resource.getScheme()))) {
219                return -1;
220            }
221        }
222        if (host != null && !host.equals("*")) {
223            if (resource.getHost() == null
224                || !resource.getHost().equals(host)) {
225                return -1;
226            }
227        }
228        if (port != null && !port.equals("*")) {
229            if (Integer.parseInt(port) != resource.getPort()) {
230                return -1;
231            }
232        }
233
234        String[] reqElements = PathSpliterator.stream(resource.getPath())
235            .skip(1).toArray(size -> new String[size]);
236        String[] reqElementsPlus = null; // Created lazily
237        for (int pathIdx = 0; pathIdx < pathPatternElements.length; pathIdx++) {
238            String[] pathPattern = pathPatternElements[pathIdx];
239            if (prefixSegs[pathIdx] == pathPattern.length - 1
240                && lastIsEmpty(pathPattern)) {
241                // Special case, pattern ends with vertical bar
242                if (reqElementsPlus == null) {
243                    reqElementsPlus = reqElements;
244                    if (!lastIsEmpty(reqElementsPlus)) {
245                        reqElementsPlus = Arrays.copyOf(
246                            reqElementsPlus, reqElementsPlus.length + 1);
247                        reqElementsPlus[reqElementsPlus.length - 1] = "";
248                    }
249                }
250                if (matchPath(pathPattern, reqElementsPlus, pathSegs)) {
251                    return prefixSegs[pathIdx];
252                }
253            } else {
254                if (matchPath(pathPattern, reqElements, pathSegs)) {
255                    return prefixSegs[pathIdx];
256                }
257            }
258        }
259        return -1;
260    }
261
262    /**
263     * Matches the given pattern against the given resource URI.
264     * 
265     * @param pattern the pattern to match
266     * @param resource the URI specifying the resource to match
267     * @return {@code true} if the resource URI matches
268     * @throws ParseException if an invalid pattern is specified
269     */
270    public static boolean matches(String pattern, URI resource)
271            throws ParseException {
272        return (new ResourcePattern(pattern)).matches(resource) >= 0;
273    }
274
275    /**
276     * Matches the given pattern against the given resource URI, comparing
277     * at most the given number of path segments.
278     *
279     * @param pattern the pattern to match
280     * @param resource the URI specifying the resource to match
281     * @param pathSegments the maximum number of path segments to compare
282     * @return {@code true} if the resource URI matches
283     * @throws ParseException if an invalid pattern is specified
284     */
285    public static boolean matches(String pattern, URI resource,
286            int pathSegments)
287            throws ParseException {
288        return (new ResourcePattern(pattern)).matches(resource,
289            pathSegments) >= 0;
290    }
291
292    @SuppressWarnings("PMD.UseVarargs")
293    private static boolean lastIsEmpty(String[] elements) {
294        return elements.length > 0
295            && elements[elements.length - 1].length() == 0;
296    }
297
298    @SuppressWarnings({ "PMD.UseVarargs", "PMD.DataflowAnomalyAnalysis",
299        "PMD.PositionLiteralsFirstInComparisons" })
300    private boolean matchPath(String[] patternElements, String[] reqElements,
301            int maxSegs) {
302        int pathIdx = 0;
303        int reqIdx = 0;
304        int patternEls = Math.min(patternElements.length, maxSegs);
305        int reqEls = Math.min(reqElements.length, maxSegs);
306        while (true) {
307            if (pathIdx == patternEls) {
308                // Reached pattern end, is match if we also reached end
309                // of requested elements.
310                return reqIdx == reqEls;
311            }
312            if (reqIdx == reqEls) {
313                // Not pattern end, but more segments from request
314                // means no match.
315                return false;
316            }
317            String matchElement = patternElements[pathIdx++];
318            if ("**".equals(matchElement)) {
319                // Accept anything left means match.
320                return true;
321            }
322            String reqElement = reqElements[reqIdx++];
323            if (!matchElement.equals("*") && !matchElement.equals(reqElement)) {
324                // If not equal (or wildcard) we have no match.
325                return false;
326            }
327        }
328
329    }
330
331    /**
332     * Removes the given number of segments (and their trailing slashes)
333     * from the beginning of the path. Segments may be empty. This implies 
334     * that invoking this method with a path that starts with a
335     * slash, the first removed segment is the empty segment
336     * preceding the slash and the starting slash. Put differently, 
337     * invoking this method with an absolute path and 1 makes the path
338     * relative.
339     *
340     * @param path the path
341     * @param segments the number of segments to remove
342     * @return the result
343     */
344    public static String removeSegments(String path, int segments) {
345        return PathSpliterator.stream(path)
346            .skip(segments).collect(Collectors.joining("/"));
347    }
348
349    /**
350     * Splits the given path in a prefix with the given number of
351     * segments and the rest. Like {{@link #removeSegments(String, int)}
352     * but additionally returning the removed segments.
353     *
354     * @param path the path
355     * @param segments the number of segments in the prefi
356     * @return the prefix and the rest
357     */
358    @SuppressWarnings({ "PMD.AssignmentInOperand",
359        "PMD.AvoidLiteralsInIfCondition" })
360    public static String[] split(String path, int segments) {
361        StringBuilder prefix = new StringBuilder();
362        StringBuilder suffix = new StringBuilder();
363        int[] count = { 0 };
364        PathSpliterator.stream(path).forEach(seg -> {
365            if (count[0]++ < segments) {
366                if (count[0] > 1) {
367                    prefix.append('/');
368                }
369                prefix.append(seg);
370            } else {
371                if (count[0] > segments + 1) {
372                    suffix.append('/');
373                }
374                suffix.append(seg);
375            }
376        });
377        return new String[] { prefix.toString(), suffix.toString() };
378    }
379
380    /**
381     * If the URI matches, returns the path split according to 
382     * the matched pattern (see {@link #split(String, int)}).
383     *
384     * @param resource the resource
385     * @return the result.
386     */
387    public Optional<String[]> splitPath(URI resource) {
388        int matchRes = matches(resource);
389        if (matchRes < 0) {
390            return Optional.empty();
391        }
392        return Optional.of(split(resource.getPath(), matchRes + 1));
393    }
394
395    /**
396     * If the URI matches, returns the path without prefix as specified
397     * by the matched pattern (see {@link #split(String, int)}).
398     *
399     * @param resource the resource
400     * @return the result.
401     */
402    @SuppressWarnings("PMD.AssignmentInOperand")
403    public Optional<String> pathRemainder(URI resource) {
404        int matchRes = matches(resource);
405        if (matchRes < 0) {
406            return Optional.empty();
407        }
408        int segments = matchRes + 1;
409        StringBuilder suffix = new StringBuilder();
410        int[] count = { 0 };
411        PathSpliterator.stream(resource.getPath()).forEach(seg -> {
412            if (count[0]++ >= segments) {
413                if (count[0] > segments + 1) {
414                    suffix.append('/');
415                }
416                suffix.append(seg);
417            }
418        });
419        return Optional.of(suffix.toString());
420    }
421
422    /*
423     * (non-Javadoc)
424     * 
425     * @see java.lang.Object#toString()
426     */
427    @Override
428    public String toString() {
429        StringBuilder builder = new StringBuilder(30);
430        builder.append("ResourcePattern [")
431            .append(pattern)
432            .append(']');
433        return builder.toString();
434    }
435
436    /*
437     * (non-Javadoc)
438     * 
439     * @see java.lang.Object#hashCode()
440     */
441    @Override
442    @SuppressWarnings("PMD.DataflowAnomalyAnalysis")
443    public int hashCode() {
444        @SuppressWarnings("PMD.AvoidFinalLocalVariable")
445        final int prime = 31;
446        int result = 1;
447        result = prime * result + ((pattern == null) ? 0 : pattern.hashCode());
448        return result;
449    }
450
451    /*
452     * (non-Javadoc)
453     * 
454     * @see java.lang.Object#equals(java.lang.Object)
455     */
456    @Override
457    public boolean equals(Object obj) {
458        if (this == obj) {
459            return true;
460        }
461        if (obj == null) {
462            return false;
463        }
464        if (getClass() != obj.getClass()) {
465            return false;
466        }
467        ResourcePattern other = (ResourcePattern) obj;
468        if (pattern == null) {
469            if (other.pattern != null) {
470                return false;
471            }
472        } else if (!pattern.equals(other.pattern)) {
473            return false;
474        }
475        return true;
476    }
477
478    /**
479     * Returns the segments of the path. If the path starts with a slash,
480     * an empty string is returned as first segment. If the path ends 
481     * with a slash, an empty string is returned as final segment.
482     */
483    public static class PathSpliterator extends AbstractSpliterator<String> {
484        private StringTokenizer tokenizer;
485        private boolean pendingLeadingEmpty;
486        private boolean pendingTrailingEmpty;
487
488        /**
489         * Creates a new stream for the given path, using "/"
490         * as path separator.
491         * 
492         * @param path the path
493         */
494        public static Stream<String> stream(String path) {
495            return StreamSupport.stream(new PathSpliterator(path), false);
496        }
497
498        /**
499         * Creates a new stream for the given path, using 
500         * the characters from delimiters as seperators.
501         * 
502         * @param path the path
503         * @param delimiters the delimiters
504         */
505        public static Stream<String> stream(String path, String delimiters) {
506            return StreamSupport.stream(
507                new PathSpliterator(path, delimiters), false);
508        }
509
510        /**
511         * Creates a new spliterator for the given path, using "/"
512         * as path separator.
513         * 
514         * @param path the path
515         */
516        public PathSpliterator(String path) {
517            this(path, "/");
518        }
519
520        /**
521         * Creates a new spliterator for the given path, using 
522         * the characters from delimiters as seperators.
523         * 
524         * @param path the path
525         * @param delimiters the delimiters
526         */
527        public PathSpliterator(String path, String delimiters) {
528            super(Long.MAX_VALUE, Spliterator.ORDERED
529                | Spliterator.IMMUTABLE);
530            tokenizer = new StringTokenizer(path, delimiters);
531            pendingLeadingEmpty = path.startsWith("/");
532            pendingTrailingEmpty = path.endsWith("/");
533        }
534
535        /*
536         * (non-Javadoc)
537         * 
538         * @see java.util.Spliterator#tryAdvance(java.util.function.Consumer)
539         */
540        @Override
541        public boolean tryAdvance(Consumer<? super String> consumer) {
542            if (tokenizer == null) {
543                return false;
544            }
545            if (pendingLeadingEmpty) {
546                pendingLeadingEmpty = false;
547                consumer.accept("");
548                return true;
549            }
550            if (tokenizer.hasMoreTokens()) {
551                consumer.accept(tokenizer.nextToken());
552                return true;
553            }
554            tokenizer = null;
555            if (pendingTrailingEmpty) {
556                consumer.accept("");
557                return true;
558            }
559            return false;
560        }
561
562    }
563}