Cache intermediate CA separately

Intermediate CAs are cached in order to support servers that fail to
sent a complete chain to a root. These certificates should be cached to
support these servers but these certificates must not be trusted as
trust anchors. Store them separately to prevent confusion between
trusted roots and cached intermediates.

(cherry-picked from commit 198aca1fb638a2a98e89fb9f284108ad576d0c3b)
Bug: 26232830
Change-Id: I520f50729b55fc7412c7d133335bc9e3c190bbf6
(cherry picked from commit c4ab1b959280413fb11bf4fd7f6b4c2ba38bd779)
diff --git a/src/platform/java/org/conscrypt/TrustManagerImpl.java b/src/platform/java/org/conscrypt/TrustManagerImpl.java
index 2af84d6..e705a6e 100644
--- a/src/platform/java/org/conscrypt/TrustManagerImpl.java
+++ b/src/platform/java/org/conscrypt/TrustManagerImpl.java
@@ -78,12 +78,17 @@
     private final CertPathValidator validator;
 
     /**
-     * An index of TrustAnchor instances that we've seen. Unlike the
-     * TrustedCertificateStore, this may contain intermediate CAs.
+     * An index of TrustAnchor instances that we've seen.
      */
     private final TrustedCertificateIndex trustedCertificateIndex;
 
     /**
+     * An index of intermediate certificates that we've seen. These certificates are NOT implicitly
+     * trusted and must still form a valid chain to an anchor.
+     */
+    private final TrustedCertificateIndex intermediateIndex;
+
+    /**
      * This is lazily initialized in the AndroidCAStore case since it
      * forces us to bring all the CAs into memory. In the
      * non-AndroidCAStore, we initialize this as part of the
@@ -160,6 +165,7 @@
         this.validator = validatorLocal;
         this.factory = factoryLocal;
         this.trustedCertificateIndex = trustedCertificateIndexLocal;
+        this.intermediateIndex = new TrustedCertificateIndex();
         this.acceptedIssuers = acceptedIssuersLocal;
         this.err = errLocal;
     }
@@ -336,7 +342,7 @@
             // will have been removed in
             // cleanupCertChainAndFindTrustAnchors.  http://b/3404902
             for (int i = 1; i < newChain.length; i++) {
-                trustedCertificateIndex.index(newChain[i]);
+                intermediateIndex.index(newChain[i]);
             }
         } catch (InvalidAlgorithmParameterException e) {
             throw new CertificateException(e);
@@ -397,7 +403,28 @@
             }
         }
 
-        // 2. Find the trust anchor in the chain, if any
+        // 2. Add any missing intermediates to the chain
+        while (true) {
+            TrustAnchor nextIntermediate =
+                    intermediateIndex.findByIssuerAndSignature(chain[currIndex]);
+            if (nextIntermediate == null) {
+                break;
+            }
+            // Append intermediate
+            X509Certificate cert = nextIntermediate.getTrustedCert();
+            // don't mutate original chain, which may be directly from an SSLSession
+            if (chain == original) {
+                chain = original.clone();
+            }
+            // Grow the chain if needed
+            if (currIndex == chain.length - 1) {
+                chain = Arrays.copyOf(chain, chain.length * 2);
+            }
+            chain[currIndex + 1] = cert;
+            currIndex++;
+        }
+
+        // 3. Find the trust anchor in the chain, if any
         int anchorIndex;
         for (anchorIndex = 0; anchorIndex <= currIndex; anchorIndex++) {
             // If the current cert is a TrustAnchor, we can ignore the rest of the chain.
@@ -409,13 +436,13 @@
             }
         }
 
-        // 3. If the chain is now shorter, copy to an appropriately sized array.
+        // 4. If the chain is now shorter, copy to an appropriately sized array.
         int chainLength = anchorIndex;
         X509Certificate[] newChain = ((chainLength == chain.length)
                                       ? chain
                                       : Arrays.copyOf(chain, chainLength));
 
-        // 4. If we didn't find a trust anchor earlier, look for one now
+        // 5. If we didn't find a trust anchor earlier, look for one now
         if (trustAnchors.isEmpty()) {
             TrustAnchor trustAnchor = findTrustAnchorByIssuerAndSignature(newChain[anchorIndex-1]);
             if (trustAnchor != null) {