1 /* 2 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package sun.security.provider.certpath; 26 27 import java.util.ArrayList; 28 import java.util.Collections; 29 import java.util.Iterator; 30 import java.util.List; 31 32 /** 33 * An AdjacencyList is used to store the history of certification paths 34 * attempted in constructing a path from an initiator to a target. The 35 * AdjacencyList is initialized with a <code>List</code> of 36 * <code>List</code>s, where each sub-<code>List</code> contains objects of 37 * type <code>Vertex</code>. A <code>Vertex</code> describes one possible or 38 * actual step in the chain building process, and the associated 39 * <code>Certificate</code>. Specifically, a <code>Vertex</code> object 40 * contains a <code>Certificate</code> and an index value referencing the 41 * next sub-list in the process. If the index value is -1 then this 42 * <code>Vertex</code> doesn't continue the attempted build path. 43 * <p> 44 * Example: 45 * <p> 46 * Attempted Paths:<ul> 47 * <li>C1->C2->C3 48 * <li>C1->C4->C5 49 * <li>C1->C4->C6 50 * <li>C1->C4->C7 51 * <li>C1->C8->C9 52 * <li>C1->C10->C11 53 * </ul> 54 * <p> 55 * AdjacencyList structure:<ul> 56 * <li>AL[0] = C1,1 57 * <li>AL[1] = C2,2 =>C4,3 =>C8,4 =>C10,5 58 * <li>AL[2] = C3,-1 59 * <li>AL[3] = C5,-1 =>C6,-1 =>C7,-1 60 * <li>AL[4] = C9,-1 61 * <li>AL[5] = C11,-1 62 * </ul> 63 * <p> 64 * The iterator method returns objects of type <code>BuildStep</code>, not 65 * objects of type <code>Vertex</code>. 66 * A <code>BuildStep</code> contains a <code>Vertex</code> and a result code, 67 * accessible via getResult method. There are five result values. 68 * <code>POSSIBLE</code> denotes that the current step represents a 69 * <code>Certificate</code> that the builder is considering at this point in 70 * the build. <code>FOLLOW</code> denotes a <code>Certificate</code> (one of 71 * those noted as <code>POSSIBLE</code>) that the builder is using to try 72 * extending the chain. <code>BACK</code> represents that a 73 * <code>FOLLOW</code> was incorrect, and is being removed from the chain. 74 * There is exactly one <code>FOLLOW</code> for each <code>BACK</code>. The 75 * values <code>SUCCEED</code> and <code>FAIL</code> mean that we've come to 76 * the end of the build process, and there will not be any more entries in 77 * the list. 78 * 79 * @see sun.security.provider.certpath.BuildStep 80 * @see sun.security.provider.certpath.Vertex 81 * 82 * @author seth proctor 83 * @since 1.4 84 */ 85 public class AdjacencyList { 86 87 // the actual set of steps the AdjacencyList represents 88 private ArrayList<BuildStep> mStepList; 89 90 // the original list, just for the toString method 91 private List<List<Vertex>> mOrigList; 92 93 /** 94 * Constructs a new <code>AdjacencyList</code> based on the specified 95 * <code>List</code>. See the example above. 96 * 97 * @param list a <code>List</code> of <code>List</code>s of 98 * <code>Vertex</code> objects 99 */ AdjacencyList(List<List<Vertex>> list)100 public AdjacencyList(List<List<Vertex>> list) { 101 mStepList = new ArrayList<BuildStep>(); 102 mOrigList = list; 103 buildList(list, 0, null); 104 } 105 106 /** 107 * Gets an <code>Iterator</code> to iterate over the set of 108 * <code>BuildStep</code>s in build-order. Any attempts to change 109 * the list through the remove method will fail. 110 * 111 * @return an <code>Iterator</code> over the <code>BuildStep</code>s 112 */ iterator()113 public Iterator<BuildStep> iterator() { 114 return Collections.unmodifiableList(mStepList).iterator(); 115 } 116 117 /** 118 * Recursive, private method which actually builds the step list from 119 * the given adjacency list. <code>Follow</code> is the parent BuildStep 120 * that we followed to get here, and if it's null, it means that we're 121 * at the start. 122 */ buildList(List<List<Vertex>> theList, int index, BuildStep follow)123 private boolean buildList(List<List<Vertex>> theList, int index, 124 BuildStep follow) { 125 126 // Each time this method is called, we're examining a new list 127 // from the global list. So, we have to start by getting the list 128 // that contains the set of Vertexes we're considering. 129 List<Vertex> l = theList.get(index); 130 131 // we're interested in the case where all indexes are -1... 132 boolean allNegOne = true; 133 // ...and in the case where every entry has a Throwable 134 boolean allXcps = true; 135 136 for (Vertex v : l) { 137 if (v.getIndex() != -1) { 138 // count an empty list the same as an index of -1...this 139 // is to patch a bug somewhere in the builder 140 if (theList.get(v.getIndex()).size() != 0) 141 allNegOne = false; 142 } else { 143 if (v.getThrowable() == null) 144 allXcps = false; 145 } 146 // every entry, regardless of the final use for it, is always 147 // entered as a possible step before we take any actions 148 mStepList.add(new BuildStep(v, BuildStep.POSSIBLE)); 149 } 150 151 if (allNegOne) { 152 // There are two cases that we could be looking at here. We 153 // may need to back up, or the build may have succeeded at 154 // this point. This is based on whether or not any 155 // exceptions were found in the list. 156 if (allXcps) { 157 // we need to go back...see if this is the last one 158 if (follow == null) 159 mStepList.add(new BuildStep(null, BuildStep.FAIL)); 160 else 161 mStepList.add(new BuildStep(follow.getVertex(), 162 BuildStep.BACK)); 163 164 return false; 165 } else { 166 // we succeeded...now the only question is which is the 167 // successful step? If there's only one entry without 168 // a throwable, then that's the successful step. Otherwise, 169 // we'll have to make some guesses... 170 List<Vertex> possibles = new ArrayList<>(); 171 for (Vertex v : l) { 172 if (v.getThrowable() == null) 173 possibles.add(v); 174 } 175 176 if (possibles.size() == 1) { 177 // real easy...we've found the final Vertex 178 mStepList.add(new BuildStep(possibles.get(0), 179 BuildStep.SUCCEED)); 180 } else { 181 // ok...at this point, there is more than one Cert 182 // which might be the succeed step...how do we know 183 // which it is? I'm going to assume that our builder 184 // algorithm is good enough to know which is the 185 // correct one, and put it first...but a FIXME goes 186 // here anyway, and we should be comparing to the 187 // target/initiator Cert... 188 mStepList.add(new BuildStep(possibles.get(0), 189 BuildStep.SUCCEED)); 190 } 191 192 return true; 193 } 194 } else { 195 // There's at least one thing that we can try before we give 196 // up and go back. Run through the list now, and enter a new 197 // BuildStep for each path that we try to follow. If none of 198 // the paths we try produce a successful end, we're going to 199 // have to back out ourselves. 200 boolean success = false; 201 202 for (Vertex v : l) { 203 204 // Note that we'll only find a SUCCEED case when we're 205 // looking at the last possible path, so we don't need to 206 // consider success in the while loop 207 208 if (v.getIndex() != -1) { 209 if (theList.get(v.getIndex()).size() != 0) { 210 // If the entry we're looking at doesn't have an 211 // index of -1, and doesn't lead to an empty list, 212 // then it's something we follow! 213 BuildStep bs = new BuildStep(v, BuildStep.FOLLOW); 214 mStepList.add(bs); 215 success = buildList(theList, v.getIndex(), bs); 216 } 217 } 218 } 219 220 if (success) { 221 // We're already finished! 222 return true; 223 } else { 224 // We failed, and we've exhausted all the paths that we 225 // could take. The only choice is to back ourselves out. 226 if (follow == null) 227 mStepList.add(new BuildStep(null, BuildStep.FAIL)); 228 else 229 mStepList.add(new BuildStep(follow.getVertex(), 230 BuildStep.BACK)); 231 232 return false; 233 } 234 } 235 } 236 237 /** 238 * Prints out a string representation of this AdjacencyList. 239 * 240 * @return String representation 241 */ 242 @Override toString()243 public String toString() { 244 StringBuilder sb = new StringBuilder("[\n"); 245 246 int i = 0; 247 for (List<Vertex> l : mOrigList) { 248 sb.append("LinkedList[").append(i++).append("]:\n"); 249 250 for (Vertex step : l) { 251 sb.append(step.toString()).append("\n"); 252 } 253 } 254 sb.append("]\n"); 255 256 return sb.toString(); 257 } 258 } 259