--- a/langtools/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/DepsAnalyzer.java	Fri Jun 17 18:17:16 2016 +0100
+++ b/langtools/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/DepsAnalyzer.java	Fri Jun 17 14:33:54 2016 -0700
@@ -181,11 +181,11 @@
      * Returns the dependences, either class name or package name
      * as specified in the given verbose level.
      */
-    Stream<String> dependences() {
+    Set<String> dependences() {
         return analyzer.archives().stream()
                        .map(analyzer::dependences)
                        .flatMap(Set::stream)
-                       .distinct();
+                       .collect(Collectors.toSet());
     }
 
     /**

--- a/langtools/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/JdepsTask.java	Fri Jun 17 18:17:16 2016 +0100
+++ b/langtools/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/JdepsTask.java	Fri Jun 17 14:33:54 2016 -0700
@@ -25,11 +25,8 @@
 
 package com.sun.tools.jdeps;
 
-import static com.sun.tools.jdeps.Analyzer.NOT_FOUND;
-import static com.sun.tools.jdeps.Analyzer.REMOVED_JDK_INTERNALS;
 import static com.sun.tools.jdeps.Analyzer.Type.*;
 import static com.sun.tools.jdeps.JdepsWriter.*;
-import static com.sun.tools.jdeps.JdepsConfiguration.ALL_MODULE_PATH;
 
 import java.io.IOException;
 import java.io.PrintWriter;
@@ -38,17 +35,7 @@
 import java.nio.file.Path;
 import java.nio.file.Paths;
 import java.text.MessageFormat;
-import java.util.ArrayList;
-import java.util.Comparator;
-import java.util.Deque;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Locale;
-import java.util.Map;
-import java.util.MissingResourceException;
-import java.util.ResourceBundle;
-import java.util.Set;
-import java.util.function.Function;
+import java.util.*;
 import java.util.regex.Pattern;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
@@ -598,24 +585,32 @@
                                          name, archive.getPathName())));
 
         if (options.findJDKInternals && !options.nowarning) {
-            Map<String, String> jdkInternals = analyzer.dependences()
-                .collect(Collectors.toMap(Function.identity(), this::replacementFor));
+            Map<String, String> jdkInternals = new TreeMap<>();
+            Set<String> deps = analyzer.dependences();
+            // find the ones with replacement
+            deps.forEach(cn -> replacementFor(cn).ifPresent(
+                repl -> jdkInternals.put(cn, repl))
+            );
+
+            if (!deps.isEmpty()) {
+                log.println();
+                warning("warn.replace.useJDKInternals", getMessage("jdeps.wiki.url"));
+            }
 
             if (!jdkInternals.isEmpty()) {
                 log.println();
-                warning("warn.replace.useJDKInternals", getMessage("jdeps.wiki.url"));
-
-                if (jdkInternals.values().stream().anyMatch(repl -> repl != null)) {
-                    log.println();
-                    log.format("%-40s %s%n", "JDK Internal API", "Suggested Replacement");
-                    log.format("%-40s %s%n", "----------------", "---------------------");
-                        jdkInternals.entrySet().stream()
-                            .filter(e -> e.getValue() != null)
-                            .sorted(Map.Entry.comparingByKey())
-                            .forEach(e -> log.format("%-40s %s%n", e.getKey(), e.getValue()));
-                }
+                log.format("%-40s %s%n", "JDK Internal API", "Suggested Replacement");
+                log.format("%-40s %s%n", "----------------", "---------------------");
+                jdkInternals.entrySet().stream()
+                    .forEach(e -> {
+                        String key = e.getKey();
+                        String[] lines = e.getValue().split("\\n");
+                        for (String s : lines) {
+                            log.format("%-40s %s%n", key, s);
+                            key = "";
+                        }
+                    });
             }
-
         }
         return ok;
     }
@@ -887,7 +882,7 @@
      * Returns the recommended replacement API for the given classname;
      * or return null if replacement API is not known.
      */
-    private String replacementFor(String cn) {
+    private Optional<String> replacementFor(String cn) {
         String name = cn;
         String value = null;
         while (value == null && name != null) {
@@ -899,6 +894,6 @@
                 name = i > 0 ? name.substring(0, i) : null;
             }
         }
-        return value;
+        return Optional.ofNullable(value);
     }
 }

--- a/langtools/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/resources/jdkinternals.properties	Fri Jun 17 18:17:16 2016 +0100
+++ b/langtools/src/jdk.jdeps/share/classes/com/sun/tools/jdeps/resources/jdkinternals.properties	Fri Jun 17 14:33:54 2016 -0700
@@ -22,6 +22,8 @@
 sun.security.krb5=Use com.sun.security.jgss
 sun.security.provider.PolicyFile=Use java.security.Policy.getInstance("JavaPolicy", new URIParameter(uri)) @since 1.6
 sun.security.provider.Sun=Use java.security.Security.getProvider(provider-name) @since 1.3
+sun.security.util.HostnameChecker=Use javax.net.ssl.SSLParameters.setEndpointIdentificationAlgorithm("HTTPS") @since 1.7\n\
+or javax.net.ssl.HttpsURLConnection.setHostnameVerifier() @since 1.4
 sun.security.util.SecurityConstants=Use appropriate java.security.Permission subclass @since 1.1
 sun.security.x509.X500Name=Use javax.security.auth.x500.X500Principal @since 1.4
 sun.tools.jar=Use java.util.jar or jar tool @since 1.2

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/langtools/test/tools/jdeps/jdkinternals/ShowReplacement.java	Fri Jun 17 14:33:54 2016 -0700
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2016, 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 8159524
+ * @summary Tests JDK internal APIs with and without replacements
+ * @library ../lib
+ * @modules jdk.jdeps/com.sun.tools.jdeps
+ * @build CompilerUtils JdepsUtil
+ * @run testng ShowReplacement
+ */
+
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.Map;
+
+import org.testng.annotations.BeforeTest;
+import org.testng.annotations.Test;
+
+import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertTrue;
+
+public class ShowReplacement {
+    private static final String TEST_SRC = System.getProperty("test.src");
+
+    private static final Path CLASSES_DIR = Paths.get("classes");
+
+    private static final Map<String, String> REPLACEMENTS = Map.of(
+        "sun.security.util.HostnameChecker",
+        "Use javax.net.ssl.SSLParameters.setEndpointIdentificationAlgorithm(\"HTTPS\") @since 1.7",
+        "",
+        "or javax.net.ssl.HttpsURLConnection.setHostnameVerifier() @since 1.4");
+
+    /**
+     * Compiles classes used by the test
+     */
+    @BeforeTest
+    public void compileAll() throws Exception {
+        CompilerUtils.cleanDir(CLASSES_DIR);
+
+        assertTrue(CompilerUtils.compile(Paths.get(TEST_SRC, "p"),
+                                         CLASSES_DIR,
+                                         "-XaddExports:java.base/sun.security.util=ALL-UNNAMED"));
+    }
+
+    @Test
+    public void withReplacement() {
+        Path file = Paths.get("p", "WithRepl.class");
+        String[] output = JdepsUtil.jdeps("-jdkinternals", CLASSES_DIR.resolve(file).toString());
+        int i = 0;
+        while (!output[i].contains("Suggested Replacement")) {
+            i++;
+        }
+
+        // must match the number of JDK internal APIs
+        int count = output.length-i-2;
+        assertEquals(count, REPLACEMENTS.size());
+
+        for (int j=i+2; j < output.length; j++) {
+            String line = output[j];
+            int pos = line.indexOf("Use ");
+            if (pos < 0)
+                pos = line.indexOf("or");
+
+            assertTrue(pos > 0);
+            String name = line.substring(0, pos).trim();
+            String repl = line.substring(pos, line.length()).trim();
+            assertEquals(REPLACEMENTS.get(name), repl);
+        }
+    }
+
+    @Test
+    public void noReplacement() {
+        Path file = Paths.get("p", "NoRepl.class");
+        String[] output = JdepsUtil.jdeps("-jdkinternals", CLASSES_DIR.resolve(file).toString());
+        int i = 0;
+        // expect no replacement
+        while (i < output.length && !output[i].contains("Suggested Replacement")) {
+            i++;
+        }
+
+        // no replacement
+        assertEquals(output.length-i, 0);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/langtools/test/tools/jdeps/jdkinternals/p/NoRepl.java	Fri Jun 17 14:33:54 2016 -0700
@@ -0,0 +1,34 @@
+/*
+ * Copyright (c) 2016, 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.
+ */
+
+package p;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import sun.security.util.DerEncoder;
+
+public class NoRepl implements DerEncoder {
+    public void derEncode(OutputStream out) throws IOException {
+        throw new IOException();
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/langtools/test/tools/jdeps/jdkinternals/p/WithRepl.java	Fri Jun 17 14:33:54 2016 -0700
@@ -0,0 +1,32 @@
+/*
+ * Copyright (c) 2016, 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.
+ */
+
+package p;
+
+import sun.security.util.HostnameChecker;
+
+public class WithRepl {
+   public static void main(String[] argv) throws Exception {
+        HostnameChecker hc = HostnameChecker.getInstance(HostnameChecker.TYPE_LDAP);
+   }
+}