/*

 * Copyright (c) 2017, 2018, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package sun.security.util;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.io.IOException;

import java.security.AccessController;

import java.security.PrivilegedAction;

import java.util.Arrays;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.concurrent.ConcurrentHashMap;

import java.util.zip.ZipEntry;

import java.util.zip.ZipInputStream;

import sun.security.ssl.SSLLogger;

/**

 * Allows public suffixes and registered domains to be determined from a

 * string that represents a target domain name. A database of known

 * registered suffixes is used to perform the determination.

 *

 * A public suffix is defined as the rightmost part of a domain name

 * that is not owned by an individual registrant. Examples of

 * public suffixes are:

 *      com

 *      edu

 *      co.uk

 *      k12.ak.us

 *      com.tw

 *      \u7db2\u8def.tw

 *

 * Public suffixes effectively denote registration authorities.

 *

 * A registered domain is a public suffix preceded by one domain label

 * and a ".". Examples are:

 *      oracle.com

 *      mit.edu

 *

 * The internal database is derived from the information maintained at

 * http://publicsuffix.org. The information is fixed for a particular

 * JDK installation, but may be updated in future releases or updates.

 *

 * Because of the large number of top-level domains (TLDs) and public

 * suffix rules, we only load the rules on demand -- from a Zip file

 * containing an entry for each TLD.

 *

 * As each entry is loaded, its data is stored permanently in a cache.

 *

 * The containment hierarchy for the data is shown below:

 *

 * Rules --> contains all the rules for a particular TLD

 *    RuleSet --> contains all the rules that match 1 label

 *    RuleSet --> contains all the rules that match 2 labels

 *    RuleSet --> contains all the rules that match 3 labels

 *      :

 *    RuleSet --> contains all the rules that match N labels

 *      HashSet of rules, where each rule is an exception rule, a "normal"

 *      rule, a wildcard rule (rules that contain a wildcard prefix only),

 *      or a LinkedList of "other" rules

 *

 * The general matching algorithm tries to find a longest match. So, the

 * search begins at the RuleSet with the most labels, and works backwards.

 *

 * Exceptions take priority over all other rules, and if a Rule contains

 * any exceptions, then even if we find a "normal" match, we search all

 * other RuleSets for exceptions. It is assumed that all other rules don't

 * intersect/overlap. If this happens, a match will be returned, but not

 * necessarily the expected one. For a further explanation of the rules,

 * see http://publicsuffix.org/list/.

 *

 * The "other" rules are for the (possible future) case where wildcards

 * are located in a rule any place other than the beginning.

 */

class DomainName {

    /**

     * For efficiency, the set of rules for each TLD is kept

     * in text files and only loaded if needed.

     */

    private static final Map<String, Rules> cache = new ConcurrentHashMap<>();

    private DomainName() {}

    /**

     * Returns the registered domain of the specified domain.

     *

     * @param domain the domain name

     * @return the registered domain, or null if not known or not registerable

     * @throws NullPointerException if domain is null

     */

    public static RegisteredDomain registeredDomain(String domain) {

        Match match = getMatch(domain);

        return (match != null) ? match.registeredDomain() : null;

    }

    private static Match getMatch(String domain) {

        if (domain == null) {

            throw new NullPointerException();

        }

        Rules rules = Rules.getRules(domain);

        return rules == null ? null : rules.match(domain);

    }

    /**

     * A Rules object contains a list of rules for a particular TLD.

     *

     * Rules are stored in a linked list of RuleSet objects. The list is

     * indexed according to the number of labels in the name (minus one)

     * such that all rules with the same number of labels are stored

     * in the same RuleSet.

     *

     * Doing this means we can find the longest match first, and also we

     * can stop comparing as soon as we find a match.

     */

    private static class Rules {

        private final LinkedList<RuleSet> ruleSets = new LinkedList<>();

        private final boolean hasExceptions;

        private Rules(InputStream is) throws IOException {

            InputStreamReader isr = new InputStreamReader(is, "UTF-8");

            BufferedReader reader = new BufferedReader(isr);

            boolean hasExceptions = false;

            String line;

            int type = reader.read();

            while (type != -1 && (line = reader.readLine()) != null) {

                int numLabels = RuleSet.numLabels(line);

                if (numLabels != 0) {

                    RuleSet ruleset = getRuleSet(numLabels - 1);

                    ruleset.addRule(type, line);

                    hasExceptions |= ruleset.hasExceptions;

                }

                type = reader.read();

            }

            this.hasExceptions = hasExceptions;

        }

        static Rules getRules(String domain) {

            String tld = getTopLevelDomain(domain);

            if (tld.isEmpty()) {

                return null;

            }

            return cache.computeIfAbsent(tld, k -> createRules(tld));

        }

        private static String getTopLevelDomain(String domain) {

            int n = domain.lastIndexOf('.');

            if (n == -1) {

                return domain;

            }

            return domain.substring(n + 1);

        }

        private static Rules createRules(String tld) {

            try (InputStream pubSuffixStream = getPubSuffixStream()) {

                if (pubSuffixStream == null) {

                    return null;

                }

                return getRules(tld, new ZipInputStream(pubSuffixStream));

            } catch (IOException e) {

                if (SSLLogger.isOn && SSLLogger.isOn("ssl")) {

                    SSLLogger.fine(

                        "cannot parse public suffix data for " + tld +

                         ": " + e.getMessage());

                }

                return null;

            }

        }

        private static InputStream getPubSuffixStream() {

            InputStream is = AccessController.doPrivileged(

                new PrivilegedAction<>() {

                    @Override

                    public InputStream run() {

                        File f = new File(System.getProperty("java.home"),

                            "lib/security/public_suffix_list.dat");

                        try {

                            return new FileInputStream(f);

                        } catch (FileNotFoundException e) {

                            return null;

                        }

                    }

                }

            );

            if (is == null) {

                if (SSLLogger.isOn && SSLLogger.isOn("ssl") &&

                        SSLLogger.isOn("trustmanager")) {

                    SSLLogger.fine(

                        "lib/security/public_suffix_list.dat not found");

                }

            }

            return is;

        }

        private static Rules getRules(String tld,

                                      ZipInputStream zis) throws IOException {

            boolean found = false;

            ZipEntry ze = zis.getNextEntry();

            while (ze != null && !found) {

                if (ze.getName().equals(tld)) {

                    found = true;

                } else {

                    ze = zis.getNextEntry();

                }

            }

            if (!found) {

                if (SSLLogger.isOn && SSLLogger.isOn("ssl")) {

                    SSLLogger.fine("Domain " + tld + " not found");

                }

                return null;

            }

            return new Rules(zis);

        }

        /**

         * Return the requested RuleSet. If it hasn't been created yet,

         * create it and any RuleSets leading up to it.

         */

        private RuleSet getRuleSet(int index) {

            if (index < ruleSets.size()) {

                return ruleSets.get(index);

            }

            RuleSet r = null;

            for (int i = ruleSets.size(); i <= index; i++) {

                r = new RuleSet(i + 1);

                ruleSets.add(r);

            }

            return r;

        }

        /**

         * Find a match for the target string.

         */

        Match match(String domain) {

            // Start at the end of the rules list, looking for longest match.

            // After we find a normal match, we only look for exceptions.

            Match possibleMatch = null;

            Iterator<RuleSet> it = ruleSets.descendingIterator();

            while (it.hasNext()) {

                RuleSet ruleSet = it.next();

                Match match = ruleSet.match(domain);

                if (match != null) {

                    if (match.type() == Rule.Type.EXCEPTION || !hasExceptions) {

                        return match;

                    }

                    if (possibleMatch == null) {

                        possibleMatch = match;

                    }

                }

            }

            return possibleMatch;

        }

        /**

         * Represents a set of rules with the same number of labels

         * and for a particular TLD.

         *

         * Examples:

         *      numLabels = 2

         *      names: co.uk, ac.uk

         *      wildcards *.de (only "de" stored in HashSet)

         *      exceptions: !foo.de (stored as "foo.de")

         */

        private static class RuleSet {

            // the number of labels in this ruleset

            private final int numLabels;

            private final Set<Rule> rules = new HashSet<>();

            boolean hasExceptions = false;

            private static final RegisteredDomain.Type[] AUTHS =

                RegisteredDomain.Type.values();

            RuleSet(int n) {

                numLabels = n;

            }

            void addRule(int auth, String rule) {

                if (rule.startsWith("!")) {

                    rules.add(new Rule(rule.substring(1), Rule.Type.EXCEPTION,

                                       AUTHS[auth]));

                    hasExceptions = true;

                } else if (rule.startsWith("*.") &&

                           rule.lastIndexOf('*') == 0) {

                    rules.add(new Rule(rule.substring(2), Rule.Type.WILDCARD,

                                       AUTHS[auth]));

                } else if (rule.indexOf('*') == -1) {

                    // a "normal" label

                    rules.add(new Rule(rule, Rule.Type.NORMAL, AUTHS[auth]));

                } else {

                    // There is a wildcard in a non-leading label. This case

                    // doesn't currently exist, but we need to handle it anyway.

                    rules.add(new OtherRule(rule, AUTHS[auth], split(rule)));

                }

            }

            Match match(String domain) {

                Match match = null;

                for (Rule rule : rules) {

                    switch (rule.type) {

                        case NORMAL:

                            if (match == null) {

                                match = matchNormal(domain, rule);

                            }

                            break;

                        case WILDCARD:

                            if (match == null) {

                                match = matchWildcard(domain, rule);

                            }

                            break;

                        case OTHER:

                            if (match == null) {

                                match = matchOther(domain, rule);

                            }

                            break;

                        case EXCEPTION:

                            Match excMatch = matchException(domain, rule);

                            if (excMatch != null) {

                                return excMatch;

                            }

                            break;

                    }

                }

                return match;

            }

            private static LinkedList<String> split(String rule) {

                String[] labels = rule.split("\\.");

                return new LinkedList<>(Arrays.asList(labels));

            }

            private static int numLabels(String rule) {

                if (rule.isEmpty()) {

                    return 0;

                }

                int len = rule.length();

                int count = 0;

                int index = 0;

                while (index < len) {

                    int pos;

                    if ((pos = rule.indexOf('.', index)) == -1) {

                        return count + 1;

                    }

                    index = pos + 1;

                    count++;

                }

                return count;

            }

            /**

             * Check for a match with an explicit name rule or a wildcard rule

             * (i.e., a non-exception rule).

             */

            private Match matchNormal(String domain, Rule rule) {

                int index = labels(domain, numLabels);

                if (index == -1) {

                    return null;

                }

                // Check for explicit names.

                String substring = domain.substring(index);

                if (rule.domain.equals(substring)) {

                    return new CommonMatch(domain, rule, index);

                }

                return null;

            }

            private Match matchWildcard(String domain, Rule rule) {

                // Now check for wildcards. In this case, there is one fewer

                // label than numLabels.

                int index = labels(domain, numLabels - 1);

                if (index > 0) {

                    String substring = domain.substring(index);

                    if (rule.domain.equals(substring)) {

                        return new CommonMatch(domain, rule,

                                               labels(domain, numLabels));

                    }

                }

                return null;

            }

            /**

             * Check for a match with an exception rule.

             */

            private Match matchException(String domain, Rule rule) {

                int index = labels(domain, numLabels);

                if (index == -1) {

                    return null;

                }

                String substring = domain.substring(index);

                if (rule.domain.equals(substring)) {

                    return new CommonMatch(domain, rule,

                                           labels(domain, numLabels - 1));

                }

                return null;

            }

            /**

             * A left-to-right comparison of labels.

             * The simplest approach to doing match() would be to

             * use a descending iterator giving a right-to-left comparison.

             * But, it's more efficient to do left-to-right compares

             * because the left most labels are the ones most likely to be

             * different. We just have to figure out which label to start at.

             */

            private Match matchOther(String domain, Rule rule) {

                OtherRule otherRule = (OtherRule)rule;

                LinkedList<String> target = split(domain);

                int diff = target.size() - numLabels;

                if (diff < 0) {

                    return null;

                }

                boolean found = true;

                for (int i = 0; i < numLabels; i++) {

                    String ruleLabel = otherRule.labels.get(i);

                    String targetLabel = target.get(i + diff);

                    if (ruleLabel.charAt(0) != '*' &&

                        !ruleLabel.equalsIgnoreCase(targetLabel)) {

                        found = false;

                        break;

                    }

                }

                if (found) {

                    return new OtherMatch(rule, numLabels, target);

                }

                return null;

            }

            /**

             * Returns a substring (index) with the n right-most labels from s.

             * Returns -1 if s does not have at least n labels, 0, if the

             * substring is s.

             */

            private static int labels(String s, int n) {

                if (n < 1) {

                    return -1;

                }

                int index = s.length();

                for (int i = 0; i < n; i++) {

                    int next = s.lastIndexOf('.', index);

                    if (next == -1) {

                        if (i == n - 1) {

                            return 0;

                        } else {

                            return -1;

                        }

                    }

                    index = next - 1;

                }

                return index + 2;

            }

        }

    }

    private static class Rule {

        enum Type { EXCEPTION, NORMAL, OTHER, WILDCARD }

        String domain;

        Type type;

        RegisteredDomain.Type auth;

        Rule(String domain, Type type, RegisteredDomain.Type auth) {

            this.domain = domain;

            this.type = type;

            this.auth = auth;

        }

    }

    private static class OtherRule extends Rule {

        List<String> labels;

        OtherRule(String domain, RegisteredDomain.Type auth,

                  List<String> labels) {

            super(domain, Type.OTHER, auth);

            this.labels = labels;

        }

    }

    /**

     * Represents a string's match with a rule in the public suffix list.

     */

    private interface Match {

        RegisteredDomain registeredDomain();

        Rule.Type type();

    }

    private static class RegisteredDomainImpl implements RegisteredDomain {

        private final String name;

        private final Type type;