/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements. See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership. The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied. See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.cxf.jaxrs.model;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.ws.rs.Path;
import javax.ws.rs.core.MultivaluedMap;
import javax.ws.rs.core.PathSegment;

import org.apache.cxf.common.util.SystemPropertyAction;
import org.apache.cxf.jaxrs.utils.HttpUtils;
import org.apache.cxf.jaxrs.utils.JAXRSUtils;

public final class URITemplate {

    public static final String TEMPLATE_PARAMETERS = "jaxrs.template.parameters";
    public static final String URI_TEMPLATE = "jaxrs.template.uri";
    public static final String LIMITED_REGEX_SUFFIX = "(/.*)?";
    public static final String FINAL_MATCH_GROUP = "FINAL_MATCH_GROUP";
    private static final String DEFAULT_PATH_VARIABLE_REGEX = "([^/]+?)";
    private static final String CHARACTERS_TO_ESCAPE = ".*+$()";
    private static final String SLASH = "/";
    private static final String SLASH_QUOTE = "/;";
    private static final int MAX_URI_TEMPLATE_CACHE_SIZE = 
        SystemPropertyAction.getInteger("org.apache.cxf.jaxrs.max_uri_template_cache_size", 2000);
    private static final Map<String, URITemplate> URI_TEMPLATE_CACHE = new ConcurrentHashMap<>();
    
    private final String template;
    private final List<String> variables = new ArrayList<>();
    private final List<String> customVariables = new ArrayList<>();
    private final Pattern templateRegexPattern;
    private final String literals;
    private final List<UriChunk> uriChunks;

    public URITemplate(String theTemplate) {
        template = theTemplate;
        StringBuilder literalChars = new StringBuilder();
        StringBuilder patternBuilder = new StringBuilder();
        CurlyBraceTokenizer tok = new CurlyBraceTokenizer(template);
        uriChunks = new ArrayList<>();
        while (tok.hasNext()) {
            String templatePart = tok.next();
            UriChunk chunk = UriChunk.createUriChunk(templatePart);
            uriChunks.add(chunk);
            if (chunk instanceof Literal) {
                String encodedValue = HttpUtils.encodePartiallyEncoded(chunk.getValue(), false);
                String substr = escapeCharacters(encodedValue);
                literalChars.append(substr);
                patternBuilder.append(substr);
            } else if (chunk instanceof Variable) {
                Variable var = (Variable)chunk;
                variables.add(var.getName());
                String pattern = var.getPattern();
                if (pattern != null) {
                    customVariables.add(var.getName());
                    // Add parenthesis to the pattern to identify a regex in the pattern, 
                    // however do not add them if they already exist since that will cause the Matcher
                    // to create extraneous values.  Parens identify a group so multiple parens would
                    // indicate multiple groups.
                    if (pattern.startsWith("(") && pattern.endsWith(")")) {
                        patternBuilder.append(pattern);
                    } else {
                        patternBuilder.append('(');
                        patternBuilder.append(pattern);
                        patternBuilder.append(')');
                    }
                } else {
                    patternBuilder.append(DEFAULT_PATH_VARIABLE_REGEX);
                }
            }
        }
        literals = literalChars.toString();

        int endPos = patternBuilder.length() - 1;
        boolean endsWithSlash = (endPos >= 0) && patternBuilder.charAt(endPos) == '/';
        if (endsWithSlash) {
            patternBuilder.deleteCharAt(endPos);
        }
        patternBuilder.append(LIMITED_REGEX_SUFFIX);

        templateRegexPattern = Pattern.compile(patternBuilder.toString());
    }

    public String getLiteralChars() {
        return literals;
    }

    public String getValue() {
        return template;
    }

    public String getPatternValue() {
        return templateRegexPattern.toString();
    }

    /**
     * List of all variables in order of appearance in template.
     *
     * @return unmodifiable list of variable names w/o patterns, e.g. for "/foo/{v1:\\d}/{v2}" returned list
     *         is ["v1","v2"].
     */
    public List<String> getVariables() {
        return Collections.unmodifiableList(variables);
    }

    /**
     * List of variables with patterns (regexps). List is subset of elements from {@link #getVariables()}.
     *
     * @return unmodifiable list of variables names w/o patterns.
     */
    public List<String> getCustomVariables() {
        return Collections.unmodifiableList(customVariables);
    }

    private static String escapeCharacters(String expression) {

        int length = expression.length();
        int i = 0;
        char ch = ' ';
        for (; i < length; ++i) {
            ch = expression.charAt(i);
            if (isReservedCharacter(ch)) {
                break;
            }
        }

        if (i == length) {
            return expression;
        }

        // Allows for up to 8 escaped characters before we start creating more
        // StringBuilders. 8 is an arbitrary limit, but it seems to be
        // sufficient in most cases.
        StringBuilder sb = new StringBuilder(length + 8);
        sb.append(expression, 0, i);
        sb.append('\\');
        sb.append(ch);
        ++i;
        for (; i < length; ++i) {
            ch = expression.charAt(i);
            if (isReservedCharacter(ch)) {
                sb.append('\\');
            }
            sb.append(ch);
        }
        return sb.toString();
    }

    private static boolean isReservedCharacter(char ch) {
        return CHARACTERS_TO_ESCAPE.indexOf(ch) != -1;
    }

    public boolean match(String uri, MultivaluedMap<String, String> templateVariableToValue) {

        if (uri == null) {
            return (templateRegexPattern == null) ? true : false;
        }

        if (templateRegexPattern == null) {
            return false;
        }

        Matcher m = templateRegexPattern.matcher(uri);
        if (!m.matches() || template.equals(SLASH) && uri.startsWith(SLASH_QUOTE)) {
            if (uri.contains(";")) {
                // we might be trying to match one or few path segments
                // containing matrix
                // parameters against a clear path segment as in @Path("base").
                List<PathSegment> pList = JAXRSUtils.getPathSegments(template, false);
                List<PathSegment> uList = JAXRSUtils.getPathSegments(uri, false);
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < uList.size(); i++) {
                    final String segment;
                    if (pList.size() > i && pList.get(i).getPath().indexOf('{') == -1) {
                        segment = uList.get(i).getPath();
                    } else {
                        segment = HttpUtils.fromPathSegment(uList.get(i));
                    }
                    if (!segment.isEmpty()) {
                        sb.append(SLASH);
                    }
                    sb.append(segment);
                }
                uri = sb.toString();
                if (uri.isEmpty()) {
                    uri = SLASH;
                }
                m = templateRegexPattern.matcher(uri);
                if (!m.matches()) {
                    return false;
                }
            } else {
                return false;
            }
        }

        // Assign the matched template values to template variables
        int groupCount = m.groupCount();

        int i = 1;
        for (String name : variables) {
            while (i <= groupCount) {
                String value = m.group(i++);
                if ((value == null || value.length() == 0 && i < groupCount)
                    && variables.size() + 1 < groupCount) {
                    continue;
                }
                templateVariableToValue.add(name, value);
                break;
            }
        }
        // The right hand side value, might be used to further resolve
        // sub-resources.

        String finalGroup = i > groupCount ? SLASH : m.group(groupCount);
        if (finalGroup == null || finalGroup.startsWith(SLASH_QUOTE)) {
            finalGroup = SLASH;
        }

        templateVariableToValue.putSingle(FINAL_MATCH_GROUP, finalGroup);

        return true;
    }

    /**
     * Substitutes template variables with listed values. List of values is counterpart for
     * {@link #getVariables() list of variables}. When list of value is shorter than variables substitution
     * is partial. When variable has pattern, value must fit to pattern, otherwise
     * {@link IllegalArgumentException} is thrown.
     * <p>
     * Example1: for template "/{a}/{b}/{a}" {@link #getVariables()} returns "[a, b, a]"; providing here list
     * of value "[foo, bar, baz]" results with "/foo/bar/baz".
     * <p>
     * Example2: for template "/{a}/{b}/{a}" providing list of values "[foo]" results with "/foo/{b}/{a}".
     *
     * @param values values for variables
     * @return template with bound variables.
     * @throws IllegalArgumentException when values is null, any value does not match pattern etc.
     */
    public String substitute(List<String> values) throws IllegalArgumentException {
        if (values == null) {
            throw new IllegalArgumentException("values is null");
        }
        Iterator<String> iter = values.iterator();
        StringBuilder sb = new StringBuilder();
        for (UriChunk chunk : uriChunks) {
            if (chunk instanceof Variable) {
                Variable var = (Variable)chunk;
                if (iter.hasNext()) {
                    String value = iter.next();
                    if (!var.matches(value)) {
                        throw new IllegalArgumentException("Value '" + value + "' does not match variable "
                                                           + var.getName() + " with pattern "
                                                           + var.getPattern());
                    }
                    sb.append(value);
                } else {
                    sb.append(var);
                }
            } else {
                sb.append(chunk);
            }
        }
        return sb.toString();
    }

    String substitute(Map<String, ? extends Object> valuesMap) throws IllegalArgumentException {
        return this.substitute(valuesMap, Collections.<String>emptySet(), false);
    }

    /**
     * Substitutes template variables with mapped values. Variables are mapped to values; if not all variables
     * are bound result will still contain variables. Note that all variables with the same name are replaced
     * by one value.
     * <p>
     * Example: for template "/{a}/{b}/{a}" {@link #getVariables()} returns "[a, b, a]"; providing here
     * mapping "[a: foo, b: bar]" results with "/foo/bar/foo" (full substitution) and for mapping "[b: baz]"
     * result is "{a}/baz/{a}" (partial substitution).
     *
     * @param valuesMap map variables to their values; on each value Object.toString() is called.
     * @return template with bound variables.
     */
    public String substitute(Map<String, ? extends Object> valuesMap,
                             Set<String> encodePathSlashVars,
                             boolean allowUnresolved) throws IllegalArgumentException {
        if (valuesMap == null) {
            throw new IllegalArgumentException("valuesMap is null");
        }
        StringBuilder sb = new StringBuilder();
        for (UriChunk chunk : uriChunks) {
            if (chunk instanceof Variable) {
                Variable var = (Variable)chunk;
                Object value = valuesMap.get(var.getName());
                if (value != null) {
                    String sval = value.toString();
                    if (!var.matches(sval)) {
                        throw new IllegalArgumentException("Value '" + sval + "' does not match variable "
                                                           + var.getName() + " with pattern "
                                                           + var.getPattern());
                    }
                    if (encodePathSlashVars.contains(var.getName())) {
                        sval = sval.replaceAll("/", "%2F");
                    }
                    sb.append(sval);
                } else if (allowUnresolved) {
                    sb.append(chunk);
                } else {
                    throw new IllegalArgumentException("Template variable " + var.getName()
                                                       + " has no matching value");
                }
            } else {
                sb.append(chunk);
            }
        }
        return sb.toString();
    }

    /**
     * Encoded literal characters surrounding template variables,
     * ex. "a {id} b" will be encoded to "a%20{id}%20b"
     * @return encoded value
     */
    public String encodeLiteralCharacters(boolean isQuery) {
        final float encodedRatio = 1.5f;
        StringBuilder sb = new StringBuilder((int)(encodedRatio * template.length()));
        for (UriChunk chunk : uriChunks) {
            String val = chunk.getValue();
            if (chunk instanceof Literal) {
                sb.append(HttpUtils.encodePartiallyEncoded(val, isQuery));
            } else {
                sb.append(val);
            }
        }
        return sb.toString();
    }

    public static URITemplate createTemplate(Path path) {

        return createTemplate(path == null ? null : path.value());
    }

    public static URITemplate createTemplate(String pathValue) {
        if (pathValue == null) {
            pathValue = "/";
        } else if (!pathValue.startsWith("/")) {
            pathValue = "/" + pathValue;
        }
        return createExactTemplate(pathValue);
    }
    
    public static URITemplate createExactTemplate(String pathValue) {
        URITemplate template = URI_TEMPLATE_CACHE.get(pathValue);
        if (template == null) {
            template = new URITemplate(pathValue);
            if (URI_TEMPLATE_CACHE.size() >= MAX_URI_TEMPLATE_CACHE_SIZE) {
                URI_TEMPLATE_CACHE.clear();
            }
            URI_TEMPLATE_CACHE.put(pathValue, template);
        }
        return template;
    }
    
    public static int compareTemplates(URITemplate t1, URITemplate t2) {
        int l1 = t1.getLiteralChars().length();
        int l2 = t2.getLiteralChars().length();
        // descending order
        int result = l1 < l2 ? 1 : l1 > l2 ? -1 : 0;
        if (result == 0) {
            int g1 = t1.getVariables().size();
            int g2 = t2.getVariables().size();
            // descending order
            result = g1 < g2 ? 1 : g1 > g2 ? -1 : 0;
            if (result == 0) {
                int gCustom1 = t1.getCustomVariables().size();
                int gCustom2 = t2.getCustomVariables().size();
                result = gCustom1 < gCustom2 ? 1 : gCustom1 > gCustom2 ? -1 : 0;
                if (result == 0) {
                    result = t1.getPatternValue().compareTo(t2.getPatternValue());
                }
            }
        }

        return result;
    }

    /**
     * Stringified part of URI. Chunk is not URI segment; chunk can span over multiple URI segments or one URI
     * segments can have multiple chunks. Chunk is used to decompose URI of {@link URITemplate} into literals
     * and variables. Example: "foo/bar/{baz}{blah}" is decomposed into chunks: "foo/bar", "{baz}" and
     * "{blah}".
     */
    private abstract static class UriChunk {
        /**
         * Creates object form string.
         *
         * @param uriChunk stringified uri chunk
         * @return If param has variable form then {@link Variable} instance is created, otherwise chunk is
         *         treated as {@link Literal}.
         */
        public static UriChunk createUriChunk(String uriChunk) {
            if (uriChunk == null || "".equals(uriChunk)) {
                throw new IllegalArgumentException("uriChunk is empty");
            }
            UriChunk uriChunkRepresentation = Variable.create(uriChunk);
            if (uriChunkRepresentation == null) {
                uriChunkRepresentation = Literal.create(uriChunk);
            }
            return uriChunkRepresentation;
        }

        public abstract String getValue();

        @Override
        public String toString() {
            return getValue();
        }
    }

    private static final class Literal extends UriChunk {
        private String value;

        private Literal() {
            // empty constructor
        }

        public static Literal create(String uriChunk) {
            if (uriChunk == null || "".equals(uriChunk)) {
                throw new IllegalArgumentException("uriChunk is empty");
            }
            Literal literal = new Literal();
            literal.value = uriChunk;
            return literal;
        }

        @Override
        public String getValue() {
            return value;
        }

    }

    /**
     * Variable of URITemplate. Variable has either "{varname:pattern}" syntax or "{varname}".
     */
    private static final class Variable extends UriChunk {
        private static final Pattern VARIABLE_PATTERN = Pattern.compile("(\\w[-\\w\\.]*[ ]*)(\\:(.+))?");
        private String name;
        private Pattern pattern;

        private Variable() {
            // empty constructor
        }

        /**
         * Creates variable from stringified part of URI.
         *
         * @param uriChunk uriChunk chunk that depicts variable
         * @return Variable if variable was successfully created; null if uriChunk was not a variable
         */
        public static Variable create(String uriChunk) {
            Variable newVariable = new Variable();
            if (uriChunk == null || "".equals(uriChunk)) {
                return null;
            }
            if (CurlyBraceTokenizer.insideBraces(uriChunk)) {
                uriChunk = CurlyBraceTokenizer.stripBraces(uriChunk).trim();
                Matcher matcher = VARIABLE_PATTERN.matcher(uriChunk);
                if (matcher.matches()) {
                    newVariable.name = matcher.group(1).trim();
                    if (matcher.group(2) != null && matcher.group(3) != null) {
                        String patternExpression = matcher.group(3).trim();
                        newVariable.pattern = Pattern.compile(patternExpression);
                    }
                    return newVariable;
                }
            }
            return null;
        }

        public String getName() {
            return name;
        }

        public String getPattern() {
            return pattern != null ? pattern.pattern() : null;
        }

        /**
         * Checks whether value matches variable. If variable has pattern its checked against, otherwise true
         * is returned.
         *
         * @param value value of variable
         * @return true if value is valid for variable, false otherwise.
         */
        public boolean matches(String value) {
            if (pattern == null) {
                return true;
            }
            return pattern.matcher(value).matches();
        }

        @Override
        public String getValue() {
            if (pattern != null) {
                return "{" + name + ":" + pattern + "}";
            }
            return "{" + name + "}";
        }
    }

    /**
     * Splits string into parts inside and outside curly braces. Nested curly braces are ignored and treated
     * as part inside top-level curly braces. Example: string "foo{bar{baz}}blah" is split into three tokens,
     * "foo","{bar{baz}}" and "blah". When closed bracket is missing, whole unclosed part is returned as one
     * token, e.g.: "foo{bar" is split into "foo" and "{bar". When opening bracket is missing, closing
     * bracket is ignored and taken as part of current token e.g.: "foo{bar}baz}blah" is split into "foo",
     * "{bar}" and "baz}blah".
     * <p>
     * This is helper class for {@link URITemplate} that enables recurring literals appearing next to regular
     * expressions e.g. "/foo/{zipcode:[0-9]{5}}/". Nested expressions with closed sections, like open-closed
     * brackets causes expression to be out of regular grammar (is context-free grammar) which are not
     * supported by Java regexp version.
     */
    static class CurlyBraceTokenizer {

        private List<String> tokens = new ArrayList<>();
        private int tokenIdx;

        CurlyBraceTokenizer(String string) {
            boolean outside = true;
            int level = 0;
            int lastIdx = 0;
            int idx;
            for (idx = 0; idx < string.length(); idx++) {
                if (string.charAt(idx) == '{') {
                    if (outside) {
                        if (lastIdx < idx) {
                            tokens.add(string.substring(lastIdx, idx));
                        }
                        lastIdx = idx;
                        outside = false;
                    } else {
                        level++;
                    }
                } else if (string.charAt(idx) == '}' && !outside) {
                    if (level > 0) {
                        level--;
                    } else {
                        if (lastIdx < idx) {
                            tokens.add(string.substring(lastIdx, idx + 1));
                        }
                        lastIdx = idx + 1;
                        outside = true;
                    }
                }
            }
            if (lastIdx < idx) {
                tokens.add(string.substring(lastIdx, idx));
            }
        }

        /**
         * Token is enclosed by curly braces.
         *
         * @param token
         *            text to verify
         * @return true if enclosed, false otherwise.
         */
        public static boolean insideBraces(String token) {
            return token.charAt(0) == '{' && token.charAt(token.length() - 1) == '}';
        }

        /**
         * Strips token from enclosed curly braces. If token is not enclosed method
         * has no side effect.
         *
         * @param token
         *            text to verify
         * @return text stripped from curly brace begin-end pair.
         */
        public static String stripBraces(String token) {
            if (insideBraces(token)) {
                return token.substring(1, token.length() - 1);
            }
            return token;
        }

        public boolean hasNext() {
            return tokens.size() > tokenIdx;
        }

        public String next() {
            if (hasNext()) {
                return tokens.get(tokenIdx++);
            }
            throw new IllegalStateException("no more elements");
        }
    }
}