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        "PMD.CognitiveComplexity" })
110    public ResourcePattern(String pattern) throws ParseException {
111        this.pattern = pattern;
112        Matcher rpm = resourcePattern.matcher(pattern);
113        if (!rpm.matches()) {
114            throw new ParseException("Invalid pattern: " + pattern, 0);
115        }
116        protocol = rpm.group("proto");
117        host = rpm.group("host");
118        port = rpm.group("port");
119        path = rpm.group("path");
120        if (path == null) {
121            pathPatternElements = new String[0][];
122        } else {
123            String[] paths = path.split(",");
124            pathPatternElements = new String[paths.length][];
125            prefixSegs = new int[paths.length];
126            for (int i = 0; i < paths.length; i++) {
127                @SuppressWarnings("PMD.AvoidInstantiatingObjectsInLoops")
128                List<String> segs = new ArrayList<>();
129                prefixSegs[i] = 0;
130                StringTokenizer tokenizer = new StringTokenizer(
131                    paths[i], "/|", true);
132                while (tokenizer.hasMoreTokens()) {
133                    String token = tokenizer.nextToken();
134                    switch (token) {
135                    case "/":
136                        continue;
137                    case "|":
138                        prefixSegs[i] = segs.size();
139                        continue;
140                    default:
141                        segs.add(token);
142                        continue;
143                    }
144                }
145                if (paths[i].endsWith("/") || paths[i].endsWith("|")) {
146                    segs.add("");
147                }
148                pathPatternElements[i] = segs.toArray(new String[0]);
149            }
150        }
151    }
152
153    /**
154     * @return the pattern (string) that was used to create this 
155     * resource pattern.
156     */
157    public String pattern() {
158        return pattern;
159    }
160
161    /**
162     * @return the protocol value specified in the pattern or {@code null}
163     */
164    public String protocol() {
165        return protocol;
166    }
167
168    /**
169     * @return the host value specified in the pattern or {@code null}
170     */
171    public String host() {
172        return host;
173    }
174
175    /**
176     * @return the port value specified in the pattern or {@code null}
177     */
178    public String port() {
179        return port;
180    }
181
182    /**
183     * @return the path value specified in the pattern or {@code null}
184     */
185    public String path() {
186        return path;
187    }
188
189    /**
190     * Matches the given resource URI against the pattern.
191     * 
192     * @param resource the URI specifying the resource to match
193     * @return -1 if the resource does not match, else the number
194     * of prefix segments (which may be 0)
195     */
196    @SuppressWarnings({ "PMD.CyclomaticComplexity", "PMD.NPathComplexity",
197        "PMD.CollapsibleIfStatements", "PMD.DataflowAnomalyAnalysis",
198        "PMD.AvoidDuplicateLiterals" })
199    public int matches(URI resource) {
200        return matches(resource, Integer.MAX_VALUE);
201    }
202
203    /**
204     * Matches the given resource URI against the pattern, comparing
205     * at most the given number of path segments.
206     *
207     * @param resource the URI specifying the resource to match
208     * @param pathSegs the maximum number of path segments to compare
209     * @return -1 if the resource does not match, else the number
210     * of prefix segments (which may be 0)
211     */
212    @SuppressWarnings({ "PMD.CyclomaticComplexity", "PMD.NPathComplexity",
213        "PMD.CollapsibleIfStatements", "PMD.DataflowAnomalyAnalysis",
214        "PMD.CognitiveComplexity" })
215    public int matches(URI resource, int pathSegs) {
216        if (protocol != null && !protocol.equals("*")) {
217            if (resource.getScheme() == null) {
218                return -1;
219            }
220            if (Arrays.stream(protocol.split(","))
221                .noneMatch(proto -> proto.equals(resource.getScheme()))) {
222                return -1;
223            }
224        }
225        if (host != null && !host.equals("*")) {
226            if (resource.getHost() == null
227                || !resource.getHost().equals(host)) {
228                return -1;
229            }
230        }
231        if (port != null && !port.equals("*")) {
232            if (Integer.parseInt(port) != resource.getPort()) {
233                return -1;
234            }
235        }
236
237        String[] reqElements = PathSpliterator.stream(resource.getPath())
238            .skip(1).toArray(size -> new String[size]);
239        String[] reqElementsPlus = null; // Created lazily
240        for (int pathIdx = 0; pathIdx < pathPatternElements.length; pathIdx++) {
241            String[] pathPattern = pathPatternElements[pathIdx];
242            if (prefixSegs[pathIdx] == pathPattern.length - 1
243                && lastIsEmpty(pathPattern)) {
244                // Special case, pattern ends with vertical bar
245                if (reqElementsPlus == null) {
246                    reqElementsPlus = reqElements;
247                    if (!lastIsEmpty(reqElementsPlus)) {
248                        reqElementsPlus = Arrays.copyOf(
249                            reqElementsPlus, reqElementsPlus.length + 1);
250                        reqElementsPlus[reqElementsPlus.length - 1] = "";
251                    }
252                }
253                if (matchPath(pathPattern, reqElementsPlus, pathSegs)) {
254                    return prefixSegs[pathIdx];
255                }
256            } else {
257                if (matchPath(pathPattern, reqElements, pathSegs)) {
258                    return prefixSegs[pathIdx];
259                }
260            }
261        }
262        return -1;
263    }
264
265    /**
266     * Matches the given pattern against the given resource URI.
267     * 
268     * @param pattern the pattern to match
269     * @param resource the URI specifying the resource to match
270     * @return {@code true} if the resource URI matches
271     * @throws ParseException if an invalid pattern is specified
272     */
273    public static boolean matches(String pattern, URI resource)
274            throws ParseException {
275        return (new ResourcePattern(pattern)).matches(resource) >= 0;
276    }
277
278    /**
279     * Matches the given pattern against the given resource URI, comparing
280     * at most the given number of path segments.
281     *
282     * @param pattern the pattern to match
283     * @param resource the URI specifying the resource to match
284     * @param pathSegments the maximum number of path segments to compare
285     * @return {@code true} if the resource URI matches
286     * @throws ParseException if an invalid pattern is specified
287     */
288    public static boolean matches(String pattern, URI resource,
289            int pathSegments)
290            throws ParseException {
291        return (new ResourcePattern(pattern)).matches(resource,
292            pathSegments) >= 0;
293    }
294
295    @SuppressWarnings("PMD.UseVarargs")
296    private static boolean lastIsEmpty(String[] elements) {
297        return elements.length > 0
298            && elements[elements.length - 1].length() == 0;
299    }
300
301    @SuppressWarnings({ "PMD.UseVarargs", "PMD.DataflowAnomalyAnalysis",
302        "PMD.PositionLiteralsFirstInComparisons" })
303    private boolean matchPath(String[] patternElements, String[] reqElements,
304            int maxSegs) {
305        int pathIdx = 0;
306        int reqIdx = 0;
307        int patternEls = Math.min(patternElements.length, maxSegs);
308        int reqEls = Math.min(reqElements.length, maxSegs);
309        while (true) {
310            if (pathIdx == patternEls) {
311                // Reached pattern end, is match if we also reached end
312                // of requested elements.
313                return reqIdx == reqEls;
314            }
315            if (reqIdx == reqEls) {
316                // Not pattern end, but more segments from request
317                // means no match.
318                return false;
319            }
320            String matchElement = patternElements[pathIdx++];
321            if ("**".equals(matchElement)) {
322                // Accept anything left means match.
323                return true;
324            }
325            String reqElement = reqElements[reqIdx++];
326            if (!"*".equals(matchElement) && !matchElement.equals(reqElement)) {
327                // If not equal (or wildcard) we have no match.
328                return false;
329            }
330        }
331
332    }
333
334    /**
335     * Removes the given number of segments (and their trailing slashes)
336     * from the beginning of the path. Segments may be empty. This implies 
337     * that invoking this method with a path that starts with a
338     * slash, the first removed segment is the empty segment
339     * preceding the slash and the starting slash. Put differently, 
340     * invoking this method with an absolute path and 1 makes the path
341     * relative.
342     *
343     * @param path the path
344     * @param segments the number of segments to remove
345     * @return the result
346     */
347    public static String removeSegments(String path, int segments) {
348        return PathSpliterator.stream(path)
349            .skip(segments).collect(Collectors.joining("/"));
350    }
351
352    /**
353     * Splits the given path in a prefix with the given number of
354     * segments and the rest. Like {{@link #removeSegments(String, int)}
355     * but additionally returning the removed segments.
356     *
357     * @param path the path
358     * @param segments the number of segments in the prefi
359     * @return the prefix and the rest
360     */
361    @SuppressWarnings({ "PMD.AssignmentInOperand",
362        "PMD.AvoidLiteralsInIfCondition" })
363    public static String[] split(String path, int segments) {
364        StringBuilder prefix = new StringBuilder();
365        StringBuilder suffix = new StringBuilder();
366        int[] count = { 0 };
367        PathSpliterator.stream(path).forEach(seg -> {
368            if (count[0]++ < segments) {
369                if (count[0] > 1) {
370                    prefix.append('/');
371                }
372                prefix.append(seg);
373            } else {
374                if (count[0] > segments + 1) {
375                    suffix.append('/');
376                }
377                suffix.append(seg);
378            }
379        });
380        return new String[] { prefix.toString(), suffix.toString() };
381    }
382
383    /**
384     * If the URI matches, returns the path split according to 
385     * the matched pattern (see {@link #split(String, int)}).
386     *
387     * @param resource the resource
388     * @return the result.
389     */
390    public Optional<String[]> splitPath(URI resource) {
391        int matchRes = matches(resource);
392        if (matchRes < 0) {
393            return Optional.empty();
394        }
395        return Optional.of(split(resource.getPath(), matchRes + 1));
396    }
397
398    /**
399     * If the URI matches, returns the path without prefix as specified
400     * by the matched pattern (see {@link #split(String, int)}).
401     *
402     * @param resource the resource
403     * @return the result.
404     */
405    @SuppressWarnings("PMD.AssignmentInOperand")
406    public Optional<String> pathRemainder(URI resource) {
407        int matchRes = matches(resource);
408        if (matchRes < 0) {
409            return Optional.empty();
410        }
411        int segments = matchRes + 1;
412        StringBuilder suffix = new StringBuilder();
413        int[] count = { 0 };
414        PathSpliterator.stream(resource.getPath()).forEach(seg -> {
415            if (count[0]++ >= segments) {
416                if (count[0] > segments + 1) {
417                    suffix.append('/');
418                }
419                suffix.append(seg);
420            }
421        });
422        return Optional.of(suffix.toString());
423    }
424
425    /*
426     * (non-Javadoc)
427     * 
428     * @see java.lang.Object#toString()
429     */
430    @Override
431    public String toString() {
432        StringBuilder builder = new StringBuilder(30);
433        builder.append("ResourcePattern [")
434            .append(pattern)
435            .append(']');
436        return builder.toString();
437    }
438
439    /*
440     * (non-Javadoc)
441     * 
442     * @see java.lang.Object#hashCode()
443     */
444    @Override
445    @SuppressWarnings("PMD.DataflowAnomalyAnalysis")
446    public int hashCode() {
447        @SuppressWarnings("PMD.AvoidFinalLocalVariable")
448        final int prime = 31;
449        int result = 1;
450        result = prime * result + ((pattern == null) ? 0 : pattern.hashCode());
451        return result;
452    }
453
454    /*
455     * (non-Javadoc)
456     * 
457     * @see java.lang.Object#equals(java.lang.Object)
458     */
459    @Override
460    public boolean equals(Object obj) {
461        if (this == obj) {
462            return true;
463        }
464        if (obj == null) {
465            return false;
466        }
467        if (getClass() != obj.getClass()) {
468            return false;
469        }
470        ResourcePattern other = (ResourcePattern) obj;
471        if (pattern == null) {
472            if (other.pattern != null) {
473                return false;
474            }
475        } else if (!pattern.equals(other.pattern)) {
476            return false;
477        }
478        return true;
479    }
480
481    /**
482     * Returns the segments of the path. If the path starts with a slash,
483     * an empty string is returned as first segment. If the path ends 
484     * with a slash, an empty string is returned as final segment.
485     */
486    public static class PathSpliterator extends AbstractSpliterator<String> {
487        private StringTokenizer tokenizer;
488        private boolean pendingLeadingEmpty;
489        private boolean pendingTrailingEmpty;
490
491        /**
492         * Creates a new stream for the given path, using "/"
493         * as path separator.
494         * 
495         * @param path the path
496         */
497        public static Stream<String> stream(String path) {
498            return StreamSupport.stream(new PathSpliterator(path), false);
499        }
500
501        /**
502         * Creates a new stream for the given path, using 
503         * the characters from delimiters as seperators.
504         * 
505         * @param path the path
506         * @param delimiters the delimiters
507         */
508        public static Stream<String> stream(String path, String delimiters) {
509            return StreamSupport.stream(
510                new PathSpliterator(path, delimiters), false);
511        }
512
513        /**
514         * Creates a new spliterator for the given path, using "/"
515         * as path separator.
516         * 
517         * @param path the path
518         */
519        public PathSpliterator(String path) {
520            this(path, "/");
521        }
522
523        /**
524         * Creates a new spliterator for the given path, using 
525         * the characters from delimiters as seperators.
526         * 
527         * @param path the path
528         * @param delimiters the delimiters
529         */
530        public PathSpliterator(String path, String delimiters) {
531            super(Long.MAX_VALUE, Spliterator.ORDERED
532                | Spliterator.IMMUTABLE);
533            tokenizer = new StringTokenizer(path, delimiters);
534            pendingLeadingEmpty = path.startsWith("/");
535            pendingTrailingEmpty = path.endsWith("/");
536        }
537
538        /*
539         * (non-Javadoc)
540         * 
541         * @see java.util.Spliterator#tryAdvance(java.util.function.Consumer)
542         */
543        @Override
544        public boolean tryAdvance(Consumer<? super String> consumer) {
545            if (tokenizer == null) {
546                return false;
547            }
548            if (pendingLeadingEmpty) {
549                pendingLeadingEmpty = false;
550                consumer.accept("");
551                return true;
552            }
553            if (tokenizer.hasMoreTokens()) {
554                consumer.accept(tokenizer.nextToken());
555                return true;
556            }
557            tokenizer = null;
558            if (pendingTrailingEmpty) {
559                consumer.accept("");
560                return true;
561            }
562            return false;
563        }
564
565    }
566}