/*

 * Copyright (c) 2015, 2017, 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.

 *

 * 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.

 */

/*

 * @test

 * @bug 8072692

 * @summary Check the matching implemented by SecurityManager.checkPackageAccess

 * @run main/othervm CheckPackageMatching

 */

import java.security.Security;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collection;

import java.util.Collections;

import java.util.List;

import java.util.StringTokenizer;

/*

 * The purpose of this test is not to verify the content of the package

 * access list - but to ensure that the matching implemented by the

 * SecurityManager is correct. This is why we have our own pattern matching

 * algorithm here.

 */

public class CheckPackageMatching {

    /**

     * The restricted packages listed in the package.access property of the

     * java.security file.

     */

    private static final String[] packages = actual().toArray(new String[0]);

    /**

     * Returns the list of restricted packages in the package.access property.

     */

    private static List<String> actual() {

        String prop = Security.getProperty("package.access");

        List<String> packages = new ArrayList<>();

        if (prop != null && !prop.equals("")) {

            StringTokenizer tok = new StringTokenizer(prop, ",");

            while (tok.hasMoreElements()) {

                String s = tok.nextToken().trim();

                packages.add(s);

            }

        }

        return packages;

    }

    /**

     * PackageMatcher implements a state machine that matches package

     * names against packages parsed from the package access list.

     */

    private abstract static class PackageMatcher {

        // For each state, chars[state] contains the chars that matches.

        private final char[][] chars;

        // For each state, states[state][i] contains the next state to go

        // to when chars[state][i] matches the current character.

        private final int[][] states;

        // Some markers. We're making the assumption that 0

        // cannot be a valid character for a package name.

        //

        // We use 0 for marking that we expect an end of string in

        // char[state][i].

        private static final char END_OF_STRING = 0;

        // This special state value indicates that we expect the string to end

        // there.

        private static final int END_STATE = -1;

        // This special state value indicates that we can accept any character

        // from now on.

        private static final int WILDCARD_STATE = Integer.MIN_VALUE;

        // Create the data for a new state machine to match package names from

        // the array of package names passed as argument.

        // Each package name in the array is expected to end with '.'

        // For each package in packages we're going to compile state data

        // that will match the regexp:

        // ^packages[i].substring(0, packages[i].length()-1).replace(".","\\.")$|^packages[i].replace(".","\\.").*

        //

        // Let's say the package array is:

        //

        // String[] packages = { "sun.", "com.sun.jmx.", "com.sun.proxy.",

        //                       "apple." };

        //

        // then the state machine will need data that looks like:

        //

        // char[][] chars = {

        //    { 'a', 'c', 's' }, { 'p' }, { 'p' }, { 'l' }, { 'e' }, { 0, '.' },

        //    { 'o' }, { 'm' }, { '.' }, { 's' }, { 'u' }, { 'n' }, { '.' },

        //    { 'j', 'p'},

        //    { 'm' }, { 'x' }, { 0, '.' },

        //    { 'r' }, { 'o' }, { 'x' }, { 'y' }, { 0, '.' },

        //    { 'u' }, { 'n' }, { 0, '.' }

        // }

        // int[][] states = {

        //    { 1, 6, 22 }, { 2 }, { 3 }, { 4 }, { 5 },

        //    { END_STATE, WILDCARD_STATE },

        //    { 7 }, { 8 }, { 9 }, { 10 }, { 11 }, { 12 }, { 13 }, { 14, 17 },

        //    { 15 }, { 16 }, { END_STATE, WILDCARD_STATE },

        //    { 18 }, { 19 }, { 20 }, { 21 }, { END_STATE, WILDCARD_STATE },

        //    { 23 }, { 24 }, { END_STATE, WILDCARD_STATE }

        // }

        //

        // The machine will start by loading the chars and states for state 0

        // chars[0] => { 'a', 'c', 's' } states[0] => { 1, 6, 22 }

        // then it examines the char at index 0 in the candidate name.

        // if the char matches one of the characters in chars[0], then it goes

        // to the corresponding state in states[0]. For instance - if the first

        // char in the candidate name is 's', which corresponds to chars[0][2] -

        // then it will proceed with the next char in the candidate name and go

        // to state 22 (as indicated by states[0][2]) - where it will load the

        // chars and states for states 22: chars[22] = { 'u' },

        // states[22] = { 23 } etc... until the candidate char at the current

        // index matches no char in chars[states] => the candidate name doesn't

        // match - or until it finds a success termination condition: the

        // candidate chars are exhausted and states[state][0] is END_STATE, or

        // the candidate chars are not exhausted - and

        // states[state][chars[state]] is WILDCARD_STATE indicating a '.*' like

        // regexp.

        //

        // [Note that the chars in chars[i] are sorted]

        //

        // The compile(...) method is reponsible for building the state machine

        // data and is called only once in the constructor.

        //

        // The matches(String candidate) method will tell whether the candidate

        // matches by implementing the algorithm described above.

        //

        PackageMatcher(String[] packages) {

            final boolean[] selected = new boolean[packages.length];

            Arrays.fill(selected, true);

            final ArrayList<char[]> charList = new ArrayList<>();

            final ArrayList<int[]> stateList = new ArrayList<>();

            compile(0, 0, packages, selected, charList, stateList);

            chars = charList.toArray(new char[0][0]);

            states = stateList.toArray(new int[0][0]);

        }

        /**

         * Compiles the state machine data (recursive).

         *

         * @param step  The index of the character which we're looking at in

         *              this step.

         * @param state The current state (starts at 0).

         * @param pkgs  The list of packages from which the automaton is built.

         * @param selected  Indicates which packages we're looking at in this

                            step.

         * @param charList  The list from which we will build

                            {@code char[][] chars;}

         * @param stateList The list from which we will build

                            {@code int[][]  states;}

         * @return the next available state.

         */

        private int compile(int step, int state, String[] pkgs,

                            boolean[] selected, ArrayList<char[]> charList,

                            ArrayList<int[]> stateList) {

            final char[] next = new char[pkgs.length];

            final int[] nexti = new int[pkgs.length];

            int j = 0;

            char min = Character.MAX_VALUE; char max = 0;

            for (int i = 0; i < pkgs.length; i++) {

                if (!selected[i]) continue;

                final String p = pkgs[i];

                final int len = p.length();

                if (step > len) {

                    selected[i] = false;

                    continue;

                }

                if (len - 1 == step) {

                    boolean unknown = true;

                    for (int k = 0; k < j ; k++) {

                        if (next[k] == END_OF_STRING) {

                            unknown = false;

                            break;

                        }

                    }

                    if (unknown) {

                        next[j] = END_OF_STRING;

                        j++;

                    }

                    nexti[i] = END_STATE;

                }

                final char c = p.charAt(step);

                nexti[i] = len - 1 == step ? END_STATE : c;

                boolean unknown = j == 0 || c < min || c > max;

                if (!unknown) {

                    if (c != min || c != max) {

                        unknown = true;

                        for (int k = 0; k < j ; k++) {

                            if (next[k] == c) {

                                unknown = false;

                                break;

                            }

                        }

                    }

                }

                if (unknown) {

                    min = min > c ? c : min;

                    max = max < c ? c : max;

                    next[j] = c;

                    j++;

                }

            }

            final char[] nc = new char[j];

            final int[]  nst = new int[j];

            System.arraycopy(next, 0, nc, 0, nc.length);

            Arrays.sort(nc);

            final boolean ns[] = new boolean[pkgs.length];

            charList.ensureCapacity(state + 1);

            stateList.ensureCapacity(state + 1);

            charList.add(state, nc);

            stateList.add(state, nst);

            state = state + 1;

            for (int k = 0; k < nc.length; k++) {

                int selectedCount = 0;

                boolean endStateFound = false;

                boolean wildcardFound = false;

                for (int l = 0; l < nexti.length; l++) {

                    if (!(ns[l] = selected[l])) {

                        continue;

                    }

                    ns[l] = nexti[l] == nc[k] || nexti[l] == END_STATE

                            && nc[k] == '.';

                    endStateFound = endStateFound || nc[k] == END_OF_STRING

                                    && nexti[l] == END_STATE;

                    wildcardFound = wildcardFound || nc[k] == '.'

                                    && nexti[l] == END_STATE;

                    if (ns[l]) {

                        selectedCount++;

                    }

                }

                nst[k] = (endStateFound ? END_STATE

                         : wildcardFound ? WILDCARD_STATE : state);

                if (selectedCount == 0 || wildcardFound) {

                    continue;

                }

                state = compile(step + 1, state, pkgs, ns, charList, stateList);

            }

            return state;

        }

        /**

         * Matches 'pkg' against the list of package names compiled in the

         * state machine data.

         *

         * @param pkg The package name to match. Must not end with '.'.

         * @return true if the package name matches, false otherwise.

         */

        public boolean matches(String pkg) {

            int state = 0;

            int i;

            final int len = pkg.length();

            next: for (i = 0; i <= len; i++) {

                if (state == WILDCARD_STATE) {

                    return true; // all characters will match.

                }

                if (state == END_STATE) {

                    return i == len;

                }

                final char[] ch = chars[state];

                final int[] st = states[state];

                if (i == len) {

                    // matches only if we have exhausted the string.

                    return st[0] == END_STATE;

                }

                if (st[0] == END_STATE && st.length == 1) {

                    // matches only if we have exhausted the string.

                    return i == len;

                }

                final char c = pkg.charAt(i); // look at next char...

                for (int j = st[0] == END_STATE ? 1 : 0; j < ch.length; j++) {

                    final char n = ch[j];

                    if (c == n) {      // found a match

                        state = st[j]; // get the next state.

                        continue next; // go to next state

                    } else if (c < n) {

                        break; // chars are sorted. we won't find it. no match.

                    }

                }

                break; // no match

            }

            return false;

        }

    }

    private static final class TestPackageMatcher extends PackageMatcher {

        private final List<String> list;

        TestPackageMatcher(String[] packages) {

            super(packages);

            this.list = Collections.unmodifiableList(Arrays.asList(packages));

        }

        @Override

        public boolean matches(String pkg) {

            final boolean match1 = super.matches(pkg);

            boolean match2 = false;

            String p2 = pkg + ".";

            for (String p : list) {

                if (pkg.startsWith(p) || p2.equals(p)) {

                    match2 = true;

                    break;

                }

            }

            if (match1 != match2) {

                System.err.println("Test Bug: PackageMatcher.matches(\"" +

                                   pkg + "\") returned " + match1);

                System.err.println("Package Access List is: " + list);

                throw new Error("Test Bug: PackageMatcher.matches(\"" +

                                pkg + "\") returned " + match1);

            }

            return match1;

        }

    }

    private static void smokeTest() {

        // these checks should pass.

        System.getSecurityManager().checkPackageAccess("com.sun.blah");

        System.getSecurityManager().checkPackageAccess("com.sun.jm");

        System.getSecurityManager().checkPackageAccess("com.sun.jmxa");

        System.getSecurityManager().checkPackageAccess("jmx");

        List<String> actual = Arrays.asList(packages);

        if (!actual.contains("sun.misc.")) {

            throw new Error("package.access does not contain 'sun.misc.'");

        }

    }

    // This is a sanity test for our own test code.

    private static void testTheTest(String[] pkgs, char[][] chars,

                                    int[][] states) {

        PackageMatcher m = new TestPackageMatcher(pkgs);

        String unexpected = "";

        if (!Arrays.deepEquals(chars, m.chars)) {

            System.err.println("Char arrays differ");

            if (chars.length != m.chars.length) {

                System.err.println("Char array lengths differ: expected="

                        + chars.length + " actual=" + m.chars.length);

            }

            System.err.println(Arrays.deepToString(m.chars).replace((char)0,

                                                   '0'));

            unexpected = "chars[]";

        }

        if (!Arrays.deepEquals(states, m.states)) {

            System.err.println("State arrays differ");

            if (states.length != m.states.length) {

                System.err.println("Char array lengths differ: expected="

                        + states.length + " actual=" + m.states.length);

            }

            System.err.println(Arrays.deepToString(m.states));

            if (unexpected.length() > 0) {

                unexpected = unexpected + " and ";

            }

            unexpected = unexpected + "states[]";

        }

        if (unexpected.length() > 0) {

            throw new Error("Unexpected "+unexpected+" in PackageMatcher");

        }

        testMatches(m, pkgs);

    }

    // This is a sanity test for our own test code.

    private static void testTheTest() {

        final String[] packages2 = { "sun.", "com.sun.jmx.",

                                     "com.sun.proxy.", "apple." };

        final int END_STATE = PackageMatcher.END_STATE;

        final int WILDCARD_STATE = PackageMatcher.WILDCARD_STATE;

        final char[][] chars2 = {

            { 'a', 'c', 's' }, { 'p' }, { 'p' }, { 'l' }, { 'e' }, { 0, '.' },

            { 'o' }, { 'm' }, { '.' }, { 's' }, { 'u' }, { 'n' }, { '.' },

            { 'j', 'p'},

            { 'm' }, { 'x' }, { 0, '.' },

            { 'r' }, { 'o' }, { 'x' }, { 'y' }, { 0, '.' },

            { 'u' }, { 'n' }, { 0, '.' }

         };

         final int[][] states2 = {

            { 1, 6, 22 }, { 2 }, { 3 }, { 4 }, { 5 },

            { END_STATE, WILDCARD_STATE },

            { 7 }, { 8 }, { 9 }, { 10 }, { 11 }, { 12 }, { 13 }, { 14, 17 },

            { 15 }, { 16 }, { END_STATE, WILDCARD_STATE },

            { 18 }, { 19 }, { 20 }, { 21 }, { END_STATE, WILDCARD_STATE },

            { 23 }, { 24 }, { END_STATE, WILDCARD_STATE }

         };

         testTheTest(packages2, chars2, states2);

         final String[] packages3 = { "sun.", "com.sun.pro.",

                                      "com.sun.proxy.", "apple." };

         final char[][] chars3 = {

            { 'a', 'c', 's' }, { 'p' }, { 'p' }, { 'l' }, { 'e' }, { 0, '.' },

            { 'o' }, { 'm' }, { '.' }, { 's' }, { 'u' }, { 'n' }, { '.' },

            { 'p' }, { 'r' }, { 'o' }, { 0, '.', 'x' },

            { 'y' }, { 0, '.' },

            { 'u' }, { 'n' }, { 0, '.' }

         };

         final int[][] states3 = {

            { 1, 6, 19 }, { 2 }, { 3 }, { 4 }, { 5 },

            { END_STATE, WILDCARD_STATE },

            { 7 }, { 8 }, { 9 }, { 10 }, { 11 }, { 12 }, { 13 }, { 14 },

            { 15 }, { 16 }, { END_STATE, WILDCARD_STATE, 17 },

            { 18 }, { END_STATE, WILDCARD_STATE },

            { 20 }, { 21 }, { END_STATE, WILDCARD_STATE }

         };

         testTheTest(packages3, chars3, states3);

    }

    private static volatile boolean sanityTesting = false;

    public static void main(String[] args) {

        System.setSecurityManager(new SecurityManager());

        // Some smoke tests.

        smokeTest();

        System.out.println("Smoke tests passed.");

        // Test our own pattern matching algorithm. Here we actually test

        // the PackageMatcher class from our own test code.

        sanityTesting = true;

        try {

            testTheTest();

            System.out.println("Sanity tests passed.");

        } finally {

            sanityTesting = false;

        }

        // Now test the package matching in the security manager.

        PackageMatcher matcher = new TestPackageMatcher(packages);

        // These should not match.

        for (String pkg : new String[] {"gloups.machin", "su",

                                        "org.jcp.xml.dsig.inter",

                                        "com.sun.jm", "com.sun.jmxa"}) {

            testMatch(matcher, pkg, false, true);

        }

        // These should match.

        for (String pkg : Arrays.asList(

                new String[] {"sun.misc.gloups.machin", "sun.misc",

                              "sun.reflect"})) {

            testMatch(matcher, pkg, true, true);

        }

        // Derive a list of packages that should match or not match from

        // the list in 'packages' - and check that the security manager

        // throws the appropriate exception.

        testMatches(matcher, packages);

    }

    private static void testMatches(PackageMatcher matcher, String[] pkgs) {

        Collection<String> pkglist = Arrays.asList(pkgs);

        PackageMatcher ref = new TestPackageMatcher(packages);

        for (String pkg : pkgs) {

            String candidate = pkg + "toto";

            boolean expected = true;

            testMatch(matcher, candidate, expected,

                      ref.matches(candidate) == expected);

        }

        for (String pkg : pkgs) {

            String candidate = pkg.substring(0, pkg.length() - 1);

            boolean expected = pkglist.contains(candidate + ".");

            testMatch(matcher, candidate, expected,

                      ref.matches(candidate) == expected);

        }

        for (String pkg : pkgs) {

            String candidate = pkg.substring(0, pkg.length() - 2);

            boolean expected = pkglist.contains(candidate + ".");

            testMatch(matcher, candidate, expected,

                      ref.matches(candidate) == expected);

        }

    }

    private static void testMatch(PackageMatcher matcher, String candidate,

                                  boolean expected, boolean testSecurityManager)

    {

        final boolean m = matcher.matches(candidate);

        if (m != expected) {

            final String msg = "\"" + candidate + "\": " +

                (m ? "matches" : "does not match");

            throw new Error("PackageMatcher does not give expected results: "

                            + msg);

        }

        if (sanityTesting) {

            testSecurityManager = false;

        }

        if (testSecurityManager) {

            System.out.println("Access to " + candidate + " should be " +

                               (expected ? "rejected" : "granted"));

            final String errormsg = "\"" + candidate + "\" : " +

                (expected ? "granted" : "not granted");

            try {

                System.getSecurityManager().checkPackageAccess(candidate);

                if (expected) {